X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/blobdiff_plain/bf62b54574e0957ccde11a1bf49889986051cff0..08496388378e6399c127cf6c569f411add13e9a7:/src/galeshapley.cpp

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index b50f5bc..c71c650 100644
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -16,6 +16,7 @@ void
 GaleShapley::
 primera_ronda() // O(N^2.log(N))
 {
+	cant_comprometidos = 0;
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
 	{
@@ -31,12 +32,13 @@ primera_ronda() // O(N^2.log(N))
 		Persona& prometido = *(m.ofertas.front()); // O(1)
 		m.ofertas.pop_front(); // O(1)
 		m.comprometer_con(prometido); // O(N)
+		cant_comprometidos++;
 	}
 }
 
 void
 GaleShapley::
-nesima_ronda() // O(N^2.log(N))
+nesima_ronda() // O(N^2)
 {
 	// Todo el for es O(N^2)
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
@@ -77,6 +79,8 @@ nesima_ronda() // O(N^2.log(N))
 			if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
 			{
 				// la oferta es mejor, rompemos el compromiso
+				// No cambiamos la cantidad de comprometidos
+				// porque estamos cambiando uno por otro
 				m.comprometer_con(*ph); // O(N)
 			}
 			else
@@ -87,7 +91,7 @@ nesima_ronda() // O(N^2.log(N))
 				for (Persona::ofertas_type::iterator i // O(N)
 						= m.ofertas.begin();
 						i != m.ofertas.end(); ++i)
-					(*i)->rechazos[(&m)->nombre] = &m;
+					(*i)->rechazos[(&m)->nombre] = &m;//O(1)
 
 				ph->rechazos[(&m)->nombre] = &m;
 				m.ofertas.clear(); // O(N)
@@ -96,29 +100,28 @@ nesima_ronda() // O(N^2.log(N))
 		else
 		{
 			m.comprometer_con(*ph); // O(N)
+			cant_comprometidos++;
 		}
 	}
 }
 
 bool
 GaleShapley::
-todos_h_comprometidos() const // O(N)
+todos_h_comprometidos() const // O(1)
 {
-	// FIXME: podemos ver de poner esto adentro de nesima_ronda()
-	for (personas_type::const_iterator ih = hombres.begin(); // O(N)
-			ih != hombres.end(); ++ih)
-		if ((*ih)->estado != Persona::COMPROMETIDO)
-			return false;
-	return true;
+	if (cant_comprometidos == capacidad) {
+		return true;
+	}
+	return false;
 }
 
 
 void
 GaleShapley::
-casamentear() // O(N^3.log(N))
+casamentear() // O(N^2)
 {
-	primera_ronda(); // O(N^2.log(N))
-	while (!todos_h_comprometidos()) // O(N)
-		nesima_ronda(); // O(N^2.log(N))
+	primera_ronda(); // O(N^2)
+	while (!todos_h_comprometidos()) // O(1)
+		nesima_ronda(); // O(N^2)
 }