X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/blobdiff_plain/a86e26ae42584c979262de7f6ddefa815ac7c625..3cf8caf3c30d7790d1467466ecd556b399cbb301:/src/persona.cpp

diff --git a/src/persona.cpp b/src/persona.cpp
index ca121a4..7cd2843 100644
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -1,11 +1,13 @@
 #include "persona.h"
+#include "heap.h"
 #include <algorithm>
 #include <cassert>
 
 /// 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 +60,16 @@ operator<< (std::ostream& os, const Persona& p)
 }
 
 /// Función de comparación entre dos personas según nuestras preferencias
-bool
+int
 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;
-	if (pos_p1 == pos_p2)
+	if (i1 == i2)
 		return 0;
 	return -1;
 }
@@ -79,40 +80,54 @@ namespace
 	/// Functor de ordenamiento auxiliar
 	struct PersonaCmp
 	{
-		Persona& p;
+		const Persona& p;
 		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;
+			return p.cmp(*p1, *p2) > 0; // O(1)
 		}
 	};
 }
 
-/// Ordenamos las ofertas segun nuestras preferencias
+/// Inserta nueva oferta
 void
 Persona::
-ordenar_ofertas()
+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
-	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::
-declarar_a(Persona& p)
+declarar_a(Persona& p) // O(log(N))
 {
 	estado = DECLARADO;
 	pareja = &p;
-	p.ofertas.push_back(this);
+	p.push_oferta(this); // O(log(N))
 }
 
 /// 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);
@@ -123,7 +138,7 @@ comprometer_con(Persona& p)
 		assert(pareja != 0);
 		pareja->estado = SOLTERO;
 		pareja->pareja = 0;
-		pareja->rechazos.push_back(&p);
+		pareja->rechazos[this->nombre] = this; // O(1)
 	}
 
 	// nos comprometemos
@@ -133,11 +148,39 @@ comprometer_con(Persona& p)
 	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)->rechazos.push_back(&p);
+		(*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
+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;
+}
+
+