cambios_para_backtracking

diff --git a/src/Makefile b/src/Makefile
index d31fe561ce524e5179165883664b81a32412bf95..056e370a4e888005c24591bdcbeb700fb8e660dc 100644 (file)
--- 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 737674024568b5b627b07e13d1dc6babb90e10c0..4bb730bcf00a79034f9f42de4c368dd472129ee6 100644 (file)
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -1,25 +1,60 @@
+#include "backtracking.h"
 #include "galeshapley.h"
 #include "parser.h"
 #include <iostream>
 
-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 da34453f676f597bc31dcb0756c53a912ffa5d26..e35f0421eca2c879ffc1243601681e508601e340 100644 (file)
--- 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 925cdff811fc29d4dc9a49399242dcaae36a0a35..d46090a794b03ac52894e0bec62b229cb57bf007 100644 (file)
--- 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 17a601e8668c3673ccb94cd71b32526c20579206..fff9fef25f7db0c5fd6b2d1964627750d1b45a8c 100644 (file)
--- a/src/susanita.cpp
+++ b/src/susanita.cpp
@@ -1,9 +1,29 @@
 #include "susanita.h"
 #include <cassert>
 #include <iostream>
+#include <algorithm>
 
-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;\r
        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";