X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/blobdiff_plain/eda6c3de95b70888e567be5f4bca0ccfa7518ec0..48e5fe7766ed449568d5e5949c0621d5ffe5897b:/src/galeshapley.cpp

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index 613c8b7..b50f5bc 100644
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -7,37 +7,39 @@
 #include <algorithm>
 
 GaleShapley::
-GaleShapley()
+GaleShapley(size_type capacidad):
+	Susanita(capacidad)
 {
 }
 
 void
 GaleShapley::
-primera_ronda()
+primera_ronda() // O(N^2.log(N))
 {
-	for (personas_type::iterator ih = hombres.begin();
+	for (personas_type::iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
 	{
-		(*ih)->declarar_a(*((*ih)->prefs[0]));
+		(*ih)->declarar_a(*((*ih)->prefs.front())); // O(1)
 	}
-	for (personas_type::iterator im = mujeres.begin();
+	for (personas_type::iterator im = mujeres.begin(); // O(N)
 			im != mujeres.end(); ++im)
 	{
 		Persona& m = **im;
-		if (m.ofertas.empty())
+		if (m.ofertas.empty()) // O(1)
 			continue;
-		m.ordenar_ofertas();
-		Persona& prometido = *(m.ofertas.front());
-		m.ofertas.pop_front();
-		m.comprometer_con(prometido);
+		m.ordenar_ofertas(); // O(N.log(N))
+		Persona& prometido = *(m.ofertas.front()); // O(1)
+		m.ofertas.pop_front(); // O(1)
+		m.comprometer_con(prometido); // O(N)
 	}
 }
 
 void
 GaleShapley::
-nesima_ronda()
+nesima_ronda() // O(N^2.log(N))
 {
-	for (personas_type::iterator ih = hombres.begin();
+	// Todo el for es O(N^2)
+	for (personas_type::iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
 	{
 		Persona& h = **ih;
@@ -45,62 +47,65 @@ nesima_ronda()
 			continue;
 
 		Persona* pm = 0;
-		for (personas_type::iterator im = h.prefs.begin();
+		for (personas_type::iterator im = h.prefs.begin(); // O(N)
 				im != h.prefs.end(); ++im)
 		{
 			pm = *im;
-			if (std::find(h.rechazos.begin(), h.rechazos.end(), pm)
-					!= h.rechazos.end()) // Si está
+
+			if (h.rechazos[pm->nombre] != NULL) // O(1)
+				// Si está
 				continue;
 			break;
 		}
-		assert(pm);
-		h.declarar_a(*pm);
+		assert(h.rechazos[pm->nombre] == NULL);
+		h.declarar_a(*pm); // O(1)
 	}
 
-	for (personas_type::iterator im = mujeres.begin();
+	// Todo el for es O(N^2.log(N))
+	for (personas_type::iterator im = mujeres.begin(); // O(N)
 			im != mujeres.end(); ++im)
 	{
 		Persona& m = **im;
-		if (m.ofertas.empty())
+		if (m.ofertas.empty()) // O(1)
 			continue;
 
-		m.ordenar_ofertas();
-		Persona* ph = m.ofertas.front();
-		m.ofertas.pop_front();
+		m.ordenar_ofertas(); // O(N.log(N))
+		Persona* ph = m.ofertas.front(); // O(1)
+		m.ofertas.pop_front(); // O(1)
 		if (m.estado == Persona::COMPROMETIDO)
 		{
-			if (m.cmp(*(m.pareja), *ph) < 0)
+			if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
 			{
 				// la oferta es mejor, rompemos el compromiso
-				m.comprometer_con(*ph);
+				m.comprometer_con(*ph); // O(N)
 			}
 			else
 			{
 				// estamos mejor con nuestra pareja actual, asi
 				// que no hacemos mas que rechazar a todos
 				// (incluyendo el mejor candidato)
-				for (Persona::ofertas_type::iterator i
+				for (Persona::ofertas_type::iterator i // O(N)
 						= m.ofertas.begin();
 						i != m.ofertas.end(); ++i)
-					(*i)->rechazos.push_back(&m);
-				ph->rechazos.push_back(&m);
-				m.ofertas.clear();
+					(*i)->rechazos[(&m)->nombre] = &m;
+
+				ph->rechazos[(&m)->nombre] = &m;
+				m.ofertas.clear(); // O(N)
 			}
 		}
 		else
 		{
-			m.comprometer_con(*ph);
+			m.comprometer_con(*ph); // O(N)
 		}
 	}
 }
 
 bool
 GaleShapley::
-todos_h_comprometidos() const
+todos_h_comprometidos() const // O(N)
 {
 	// FIXME: podemos ver de poner esto adentro de nesima_ronda()
-	for (personas_type::const_iterator ih = hombres.begin();
+	for (personas_type::const_iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
 		if ((*ih)->estado != Persona::COMPROMETIDO)
 			return false;
@@ -110,10 +115,10 @@ todos_h_comprometidos() const
 
 void
 GaleShapley::
-casamentear()
+casamentear() // O(N^3.log(N))
 {
-	primera_ronda();
-	while (!todos_h_comprometidos())
-		nesima_ronda();
+	primera_ronda(); // O(N^2.log(N))
+	while (!todos_h_comprometidos()) // O(N)
+		nesima_ronda(); // O(N^2.log(N))
 }