Agrega gráficos de orden y otras correcciones mínimas al informe.

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

diff --git a/src/persona.cpp b/src/persona.cpp
index 607e0e8a0d36f0fff0464c9cdcb3490d61984e4c..7cd2843f9e941f0a534a85ba336fa2330e8461fa 100644 (file)
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -1,4 +1,5 @@
 #include "persona.h"
 #include "persona.h"

+#include "heap.h"

 #include <algorithm>
 #include <cassert>
 
 #include <algorithm>
 #include <cassert>
 


@@ -79,35 +80,48 @@ namespace
        /// Functor de ordenamiento auxiliar
        struct PersonaCmp
        {
        /// Functor de ordenamiento auxiliar
        struct PersonaCmp
        {

-               Persona& p;
+               const Persona& p;

                PersonaCmp(Persona& p): p(p) {}
                /// devuelve true si p1 < p2
                PersonaCmp(Persona& p): p(p) {}
                /// devuelve true si p1 < p2

-               bool operator ()(const Persona* const p1, const Persona* const p2)
+               bool operator ()(const Persona* const p1, const Persona* const p2) const

                {
                {

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

                }
        };
 }
 
                }
        };
 }
 

-/// Ordenamos las ofertas segun nuestras preferencias
+/// Inserta nueva oferta

 void
 Persona::
 void
 Persona::

-ordenar_ofertas() // O(N^2.log(N^2))
+push_oferta(Persona* p) // O(log(N))

 {
 {

-       // este sort es in-place y O(N.log(N))
-       // Más info en: http://www.sgi.com/tech/stl/sort.html
-       // Pero el PersonaCmp() es O(N)
-       std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
+       heap_push(ofertas, p, PersonaCmp(*this));
+}
+
+/// Obtiene mejor oferta (sin eliminar)
+Persona*
+Persona::
+top_oferta() const // O(1)
+{
+       return ofertas.back();
+}
+
+/// Obtiene y elimina mejor oferta
+Persona*
+Persona::
+pop_oferta() // O(log(N))
+{
+       return heap_pop(ofertas, PersonaCmp(*this));

 }
 
 /// Nos declaramos a la persona p
 void
 Persona::
 }
 
 /// Nos declaramos a la persona p
 void
 Persona::

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

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

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

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