Agregar la capacidad como un atributo de Susanita.

[z.facultad/75.29/susanita.git] / src / galeshapley.cpp

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index 613c8b76cff06bf8c3fd9f18a56657adf386e8a6..b50f5bc861591f25a8c2e00c21ebdbc24a9d3cf9 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -7,37 +7,39 @@
 #include <algorithm>
 
 GaleShapley::
-GaleShapley()
+GaleShapley(size_type capacidad):
+       Susanita(capacidad)
 {
 }
 
 void
 GaleShapley::
-primera_ronda()
+primera_ronda() // O(N^2.log(N))
 {
-       for (personas_type::iterator ih = hombres.begin();
+       for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
-               (*ih)->declarar_a(*((*ih)->prefs[0]));
+               (*ih)->declarar_a(*((*ih)->prefs.front())); // O(1)
        }
-       for (personas_type::iterator im = mujeres.begin();
+       for (personas_type::iterator im = mujeres.begin(); // O(N)
                        im != mujeres.end(); ++im)
        {
                Persona& m = **im;
-               if (m.ofertas.empty())
+               if (m.ofertas.empty()) // O(1)
                        continue;
-               m.ordenar_ofertas();
-               Persona& prometido = *(m.ofertas.front());
-               m.ofertas.pop_front();
-               m.comprometer_con(prometido);
+               m.ordenar_ofertas(); // O(N.log(N))
+               Persona& prometido = *(m.ofertas.front()); // O(1)
+               m.ofertas.pop_front(); // O(1)
+               m.comprometer_con(prometido); // O(N)
        }
 }
 
 void
 GaleShapley::
-nesima_ronda()
+nesima_ronda() // O(N^2.log(N))
 {
-       for (personas_type::iterator ih = hombres.begin();
+       // Todo el for es O(N^2)
+       for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
                Persona& h = **ih;
@@ -45,62 +47,65 @@ nesima_ronda()
                        continue;
 
                Persona* pm = 0;
-               for (personas_type::iterator im = h.prefs.begin();
+               for (personas_type::iterator im = h.prefs.begin(); // O(N)
                                im != h.prefs.end(); ++im)
                {
                        pm = *im;
-                       if (std::find(h.rechazos.begin(), h.rechazos.end(), pm)
-                                       != h.rechazos.end()) // Si está
+
+                       if (h.rechazos[pm->nombre] != NULL) // O(1)
+                               // Si está
                                continue;
                        break;
                }
-               assert(pm);
-               h.declarar_a(*pm);
+               assert(h.rechazos[pm->nombre] == NULL);
+               h.declarar_a(*pm); // O(1)
        }
 
-       for (personas_type::iterator im = mujeres.begin();
+       // Todo el for es O(N^2.log(N))
+       for (personas_type::iterator im = mujeres.begin(); // O(N)
                        im != mujeres.end(); ++im)
        {
                Persona& m = **im;
-               if (m.ofertas.empty())
+               if (m.ofertas.empty()) // O(1)
                        continue;
 
-               m.ordenar_ofertas();
-               Persona* ph = m.ofertas.front();
-               m.ofertas.pop_front();
+               m.ordenar_ofertas(); // O(N.log(N))
+               Persona* ph = m.ofertas.front(); // O(1)
+               m.ofertas.pop_front(); // O(1)
                if (m.estado == Persona::COMPROMETIDO)
                {
-                       if (m.cmp(*(m.pareja), *ph) < 0)
+                       if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
                        {
                                // la oferta es mejor, rompemos el compromiso
-                               m.comprometer_con(*ph);
+                               m.comprometer_con(*ph); // O(N)
                        }
                        else
                        {
                                // estamos mejor con nuestra pareja actual, asi
                                // que no hacemos mas que rechazar a todos
                                // (incluyendo el mejor candidato)
-                               for (Persona::ofertas_type::iterator i
+                               for (Persona::ofertas_type::iterator i // O(N)
                                                = m.ofertas.begin();
                                                i != m.ofertas.end(); ++i)
-                                       (*i)->rechazos.push_back(&m);
-                               ph->rechazos.push_back(&m);
-                               m.ofertas.clear();
+                                       (*i)->rechazos[(&m)->nombre] = &m;
+
+                               ph->rechazos[(&m)->nombre] = &m;
+                               m.ofertas.clear(); // O(N)
                        }
                }
                else
                {
-                       m.comprometer_con(*ph);
+                       m.comprometer_con(*ph); // O(N)
                }
        }
 }
 
 bool
 GaleShapley::
-todos_h_comprometidos() const
+todos_h_comprometidos() const // O(N)
 {
        // FIXME: podemos ver de poner esto adentro de nesima_ronda()
-       for (personas_type::const_iterator ih = hombres.begin();
+       for (personas_type::const_iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
                if ((*ih)->estado != Persona::COMPROMETIDO)
                        return false;
@@ -110,10 +115,10 @@ todos_h_comprometidos() const
 
 void
 GaleShapley::
-casamentear()
+casamentear() // O(N^3.log(N))
 {
-       primera_ronda();
-       while (!todos_h_comprometidos())
-               nesima_ronda();
+       primera_ronda(); // O(N^2.log(N))
+       while (!todos_h_comprometidos()) // O(N)
+               nesima_ronda(); // O(N^2.log(N))
 }