From: Ezequiel Date: Sun, 6 Nov 2005 21:06:01 +0000 (+0000) Subject: cambios_para_backtracking X-Git-Tag: darcs_import~37 X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/commitdiff_plain/e712cf784660fb25651128c4626c9c337a9ae7ce cambios_para_backtracking --- diff --git a/src/Makefile b/src/Makefile index d31fe56..056e370 100644 --- a/src/Makefile +++ b/src/Makefile @@ -10,19 +10,29 @@ endif target = tdatp2 -objetos = persona.o susanita.o galeshapley.o parser.o main.o +objetos = persona.o hashtable.o susanita.o galeshapley.o backtracking.o parser.o main.o all: $(target) -persona.o: persona.cpp persona.h +persona_h = persona.h +persona.o: persona.cpp $(persona_h) -susanita.o: susanita.cpp susanita.h persona.h +hashtable_h = hashtable.h $(persona_h) +hashtable.o: hashtable.cpp $(hashtable_h) -galeshapley.o: galeshapley.cpp galeshapley.h susanita.h persona.h +susanita_h = susanita.h $(hashtable_h) +susanita.o: susanita.cpp $(susanita_h) -parser.o: parser.cpp parser.h persona.h susanita.h +galeshapley_h = galeshapley.h $(susanita_h) +galeshapley.o: galeshapley.cpp $(galeshapley_h) -main.o: main.cpp parser.h susanita.h galeshapley.h +backtracking_h = backtracking.h $(susanita_h) +backtracking.o: backtracking.cpp $(backtracking_h) + +parser_h = parser.h $(susanita_h) +parser.o: parser.cpp $(parser_h) + +main.o: main.cpp $(parser_h) $(galeshapley_h) ${bactraking_h} $(target): $(objetos) $(CXX) $(LDFLAGS) $(objetos) $(LOADLIBES) $(LDLIBS) -o $(target) diff --git a/src/main.cpp b/src/main.cpp index 7376740..4bb730b 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1,25 +1,60 @@ +#include "backtracking.h" #include "galeshapley.h" #include "parser.h" #include -int main(int argc, char* argv[]) +int +main(int argc, char* argv[]) { - if (argc != 2) + switch (argc) { - std::cerr << "Uso: " << argv[0] << " [archivo_entrada]\n"; - return 1; - } + case 2: //Gale-Sharpley por default + { + // N * 2 para asegurar que el hash este ocupado al 50% y sea O(1) + GaleShapley gs(Parser::get_n(argv[1]) * 2); + Parser p(gs); + + if (!p.input(argv[1])) + { + std::cerr << "Error al abrir el archivo '" << argv[1] << "'\n"; + return 2; + } + gs.casamentear(); + p.output(); + + break; + } + case 3: // BackTracking se especifica con tercer parámetro "-bt" + { + if (strcmp(argv[2], "-bt")) + { + std::cerr << "Uso: " << argv[0] << " archivo_entrada [-bt]\n"; + return 1; + } - GaleShapley gs; - Parser p(gs); + // N * 2 para asegurar que el hash este ocupado al 50% y sea O(1) + BackTracking bt(Parser::get_n(argv[1]) * 2); + Parser p(bt); - if (!p.input(argv[1])) - { - std::cerr << "Error al abrir el archivo '" << argv[1] << "'\n"; - return 2; + if (!p.input(argv[1])) + { + std::cerr << "Error al abrir el archivo '" << argv[1] << "'\n"; + return 2; + } + + bt.casamentear(); + + break; + } + + default: + std::cerr << "Uso: " << argv[0] << " archivo_entrada [-bt]\n"; + return 1; } - gs.casamentear(); - p.output(); + + // Todo OK + return 0; + } diff --git a/src/persona.cpp b/src/persona.cpp index da34453..e35f042 100644 --- a/src/persona.cpp +++ b/src/persona.cpp @@ -141,3 +141,31 @@ comprometer_con(Persona& p) ofertas.clear(); } +// Nos comprometemos con la otra persona y a ella la comprometemos con nosotros +void +Persona:: +comprometer_con_bt(Persona& p) +{ + // nos comprometemos + estado = COMPROMETIDO; + pareja = &p; + p.estado = COMPROMETIDO; + p.pareja = this; +} + +// Rompemos el compromiso existente +void +Persona:: +romper_compromiso(Persona& p) +{ + assert(pareja == &p); + assert(p.pareja == this); + + // rompemos el compromiso + estado = SOLTERO; + pareja = 0; + p.estado = SOLTERO; + p.pareja = 0; +} + + diff --git a/src/persona.h b/src/persona.h index 925cdff..d46090a 100644 --- a/src/persona.h +++ b/src/persona.h @@ -56,7 +56,12 @@ struct Persona /// Nos comprometemos con la persona p, quien se nos habia declarado /// previamente void comprometer_con(Persona& p); - + + // Nos comprometemos con la otra persona y a ella la comprometemos con nosotros + void comprometer_con_bt(Persona& p); + + // Rompemos el compromiso + void romper_compromiso(Persona& p); }; /// Para representación diff --git a/src/susanita.cpp b/src/susanita.cpp index 17a601e..fff9fef 100644 --- a/src/susanita.cpp +++ b/src/susanita.cpp @@ -1,9 +1,29 @@ #include "susanita.h" #include #include +#include -Susanita::~Susanita() +Susanita:: +Susanita(size_type capacidad): + nombres(capacidad) +{ +} + +// Uso interno +namespace +{ + /// Mata a una persona + void matar(Persona* p) + { + delete p; + } +} + +Susanita:: +~Susanita() { + std::for_each(hombres.begin(), hombres.end(), matar); + std::for_each(mujeres.begin(), mujeres.end(), matar); } void @@ -12,7 +32,7 @@ add_persona(Persona* pp) { // XXX cual sería el problema que agregue una persona repetida? // Reemplazaría a la anterior nomás - assert(nombres.find(pp->nombre) == nombres.end()); + assert(nombres[pp->nombre] == 0); // Muere si hay nombres repetidos nombres[pp->nombre] = pp; switch (pp->sexo) @@ -30,20 +50,18 @@ add_persona(Persona* pp) Persona* Susanita:: -get_persona(const std::string& nombre) const +get_persona(const std::string& nombre) { - nombres_type::const_iterator ip = nombres.find(nombre); - if (ip == nombres.end()) // No está - return 0; - return ip->second; + return nombres[nombre]; } void Susanita:: mostrar_estado(int mostrar_prios) const { + personas_type::const_iterator ih; std::cout << "Personas\n"; - for (personas_type::const_iterator ih = hombres.begin(); + for (ih = hombres.begin(); ih != hombres.end(); ++ih) std::cout << **ih << "\n"; std::cout << "\n"; @@ -56,7 +74,7 @@ mostrar_estado(int mostrar_prios) const return; std::cout << "Prioridades\n"; - for (personas_type::const_iterator ih = hombres.begin(); + for (ih = hombres.begin(); ih != hombres.end(); ++ih) { Persona& h = **ih; std::cout << h << "\n"; @@ -67,7 +85,7 @@ mostrar_estado(int mostrar_prios) const } } std::cout << "\n"; - for (personas_type::const_iterator ih = mujeres.begin(); + for (ih = mujeres.begin(); ih != mujeres.end(); ++ih) { Persona& h = **ih; std::cout << h << "\n";