From 85126dc2ec08ec3d74bb0932630d1b6b58392f45 Mon Sep 17 00:00:00 2001
From: Alberto Bertogli <albertogli@telpin.com.ar>
Date: Mon, 7 Nov 2005 01:14:12 +0000
Subject: [PATCH 1/1] Agregar una tabla de hash para las preferencias. Ademas
 de la lista de preferencias, agregar una tabla hash que relacione el nombre
 de la persona con el numero de preferencia, arrancando de 0.

Esto nos permite comparar en O(1) y asi bajar significativamente los ordenes
de varios algoritmos.

En un patch subsecuente se actualizaran los comentarios con los ordenes donde
corresponda.
---
 src/parser.cpp  |  4 +++-
 src/persona.cpp | 16 ++++++++--------
 src/persona.h   | 10 ++++++++--
 3 files changed, 19 insertions(+), 11 deletions(-)

diff --git a/src/parser.cpp b/src/parser.cpp
index fa2b16a..c4453cc 100644
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -75,7 +75,7 @@ input(const std::string& filename)
 			susanita.add_persona(pp);
 		}
 
-		Persona::prefs_type prefs;
+		int count = 0;
 		while (ss)
 		{
 			std::string nombre = get_hasta(ss, ',');
@@ -90,6 +90,8 @@ input(const std::string& filename)
 				susanita.add_persona(ppp);
 			}
 			pp->prefs.push_back(ppp);
+			pp->prefs_hash[ppp->nombre] = count;
+			count++;
 		}
 	}
 	return true;
diff --git a/src/persona.cpp b/src/persona.cpp
index c93b069..607e0e8 100644
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -5,7 +5,8 @@
 /// Constructor
 Persona::
 Persona(const std::string& nombre, sexo_type sexo, size_type cap):
-	nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0), rechazos(cap)
+	nombre(nombre), prefs_hash(cap), estado(SOLTERO), sexo(sexo),
+	pareja(0), rechazos(cap)
 {
 }
 
@@ -60,15 +61,14 @@ operator<< (std::ostream& os, const Persona& p)
 /// Función de comparación entre dos personas según nuestras preferencias
 int
 Persona::
-cmp(const Persona& p1, const Persona& p2) const // O(N)
+cmp(const Persona& p1, const Persona& p2) const // O(1)
 {
-	prefs_type::const_iterator pos_p1
-		= std::find(prefs.begin(), prefs.end(), &p1); // O(N)
-	prefs_type::const_iterator pos_p2
-		= std::find(prefs.begin(), prefs.end(), &p2); // O(N)
-	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;
 }
diff --git a/src/persona.h b/src/persona.h
index 9077014..6f44c88 100644
--- a/src/persona.h
+++ b/src/persona.h
@@ -27,9 +27,15 @@ struct Persona
 	/// Nombre de la persona, sólo con fines de representación
 	std::string nombre;
 
-	/// Lista de personas que prefiere, la primera de la lista es la
-	/// que mejor posicionada esta
+	/// Para la lista de personas que prefiere usamos dos estructuras: la
+	/// primera es una lista en donde el primer elemento es la persona
+	/// mejor posicionada; la segunda es un hash indexado por el nombre de
+	/// la persona, y como valor la posicion numerica.
+	/// Esta dualidad nos permite tener iteracion en orden, O(1) en
+	/// encontrar el mejor, y O(1) en ver quien es el preferido entre dos
+	/// personas.
 	prefs_type prefs;
+	HashTable<int> prefs_hash;
 
 	/// Estado de la persona
 	estado_type estado;
-- 
2.43.0