Actualizar comentarios de los ordenes.

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

diff --git a/src/persona.cpp b/src/persona.cpp
index e35f0421eca2c879ffc1243601681e508601e340..0016f3e01eb7aa559744ae90c40e78370ebf916b 100644 (file)
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -4,8 +4,9 @@
 
 /// Constructor
 Persona::
 
 /// Constructor
 Persona::

-Persona(const std::string& nombre, sexo_type sexo):
-       nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0)
+Persona(const std::string& nombre, sexo_type sexo, size_type cap):
+       nombre(nombre), prefs_hash(cap), estado(SOLTERO), sexo(sexo),
+       pareja(0), rechazos(cap)

 {
 }
 
 {
 }
 


@@ -58,17 +59,16 @@ operator<< (std::ostream& os, const Persona& p)
 }
 
 /// Función de comparación entre dos personas según nuestras preferencias
 }
 
 /// Función de comparación entre dos personas según nuestras preferencias

-bool
+int

 Persona::
 Persona::

-cmp(const Persona& p1, const Persona& p2) const
+cmp(const Persona& p1, const Persona& p2) const // O(1)

 {
 {

-       prefs_type::const_iterator pos_p1
-               = std::find(prefs.begin(), prefs.end(), &p1);
-       prefs_type::const_iterator pos_p2
-               = std::find(prefs.begin(), prefs.end(), &p2);
-       if (pos_p1 < pos_p2)
+       int i1 = prefs_hash.get(p1.nombre); // O(1)
+       int i2 = prefs_hash.get(p2.nombre); // O(1)
+
+       if (i1 < i2)

                return 1;
                return 1;

-       if (pos_p1 == pos_p2)
+       if (i1 == i2)

                return 0;
        return -1;
 }
                return 0;
        return -1;
 }


@@ -84,7 +84,7 @@ namespace
                /// devuelve true si p1 < p2
                bool operator ()(const Persona* const p1, const Persona* const p2)
                {
                /// devuelve true si p1 < p2
                bool operator ()(const Persona* const p1, const Persona* const p2)
                {

-                       return p.cmp(*p1, *p2) < 0;
+                       return p.cmp(*p1, *p2) < 0; // O(N)

                }
        };
 }
                }
        };
 }


@@ -92,27 +92,28 @@ namespace
 /// Ordenamos las ofertas segun nuestras preferencias
 void
 Persona::
 /// Ordenamos las ofertas segun nuestras preferencias
 void
 Persona::

-ordenar_ofertas()
+ordenar_ofertas() // O(N.log(N))

 {
        // este sort es in-place y O(N.log(N))
        // Más info en: http://www.sgi.com/tech/stl/sort.html
 {
        // este sort es in-place y O(N.log(N))
        // Más info en: http://www.sgi.com/tech/stl/sort.html

+       // PersonaCmp() es O(1), asi que el orden es el mismo.

        std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
 }
 
 /// Nos declaramos a la persona p
 void
 Persona::
        std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
 }
 
 /// Nos declaramos a la persona p
 void
 Persona::

-declarar_a(Persona& p)
+declarar_a(Persona& p) // O(1)

 {
        estado = DECLARADO;
        pareja = &p;
 {
        estado = DECLARADO;
        pareja = &p;

-       p.ofertas.push_back(this);
+       p.ofertas.push_back(this); // O(1)

 }
 
 /// Nos comprometemos con la persona p, quien se nos habia declarado previamente
 void
 Persona::
 }
 
 /// Nos comprometemos con la persona p, quien se nos habia declarado previamente
 void
 Persona::

-comprometer_con(Persona& p)
+comprometer_con(Persona& p) // O(N) ( es O(len(ofertas)) )

 {
        assert(p.estado == DECLARADO);
        assert(p.pareja == this);
 {
        assert(p.estado == DECLARADO);
        assert(p.pareja == this);


@@ -123,7 +124,7 @@ comprometer_con(Persona& p)
                assert(pareja != 0);
                pareja->estado = SOLTERO;
                pareja->pareja = 0;
                assert(pareja != 0);
                pareja->estado = SOLTERO;
                pareja->pareja = 0;

-               pareja->rechazos.push_back(this);
+               pareja->rechazos[this->nombre] = this; // O(1)

        }
 
        // nos comprometemos
        }
 
        // nos comprometemos


@@ -133,12 +134,12 @@ comprometer_con(Persona& p)
        p.pareja = this;
 
        // si tenemos ofertas, las rechazamos
        p.pareja = this;
 
        // si tenemos ofertas, las rechazamos

-       for (ofertas_type::iterator pretendiente = ofertas.begin();
+       for (ofertas_type::iterator pretendiente = ofertas.begin(); // O(N)

                        pretendiente != ofertas.end(); ++pretendiente)
        {
                        pretendiente != ofertas.end(); ++pretendiente)
        {

-               (*pretendiente)->rechazos.push_back(this);
+               (*pretendiente)->rechazos[this->nombre] = this; // O(1)

        }
        }

-       ofertas.clear();
+       ofertas.clear(); // O(N)

 }
 
 // Nos comprometemos con la otra persona y a ella la comprometemos con nosotros
 }
 
 // Nos comprometemos con la otra persona y a ella la comprometemos con nosotros