From ded3be7064779d67ca83084d6479f270c3fe955f Mon Sep 17 00:00:00 2001
From: Ezequiel <ezequielinfo@yahoo.com.ar>
Date: Sun, 6 Nov 2005 21:08:43 +0000
Subject: [PATCH 1/1] fuentes_backtracking

---
 src/backtracking.cpp | 92 ++++++++++++++++++++++++++++++++++++++++++++
 src/backtracking.h   | 33 ++++++++++++++++
 2 files changed, 125 insertions(+)
 create mode 100644 src/backtracking.cpp
 create mode 100644 src/backtracking.h

diff --git a/src/backtracking.cpp b/src/backtracking.cpp
new file mode 100644
index 0000000..69f43da
--- /dev/null
+++ b/src/backtracking.cpp
@@ -0,0 +1,92 @@
+#include "backtracking.h"
+
+BackTracking::
+BackTracking(size_type capacidad) : Susanita(capacidad)
+{}
+
+/* Llamada recursiva: Ensaya una alternativa desde el hombre iH hasta el final de la lista */
+void BackTracking::Ensayar(personas_type::iterator iH) 
+{
+	/* Recorro todas las mujeres de este hombre */
+	for (personas_type::iterator iM = (*iH)->prefs.begin(); iM != (*iH)->prefs.end(); ++iM)
+	{
+		/* Si la mujer está soltera y la pareja es estable*/
+		if (((*iM)->estado == Persona::SOLTERO) && ParejaEstable(iM, iH))
+		{
+			/* Se comprometen */
+			(*iM)->comprometer_con_bt(**iH);
+
+			/* Si quedan hombres solteros */
+			if (!(*iH == *(hombres.rbegin())))
+			{
+				/* Sigo armando parejas estables */
+				Ensayar(iH+1);
+			}
+			else
+			{
+				/* Si este es el último hombre entonces tengo una configuración estable */
+				Parser p(*this);
+				p.output();
+				//this->mostrar_estado();
+			}
+			
+			/* Rompo el compromiso */
+			(*iM)->romper_compromiso(**iH);
+		}
+		
+	}
+}
+
+bool BackTracking::ParejaEstable(personas_type::iterator Mujer, personas_type::iterator Hombre)
+{
+	/* Una pareja (Mujer,Hombre) es estable si no existe: */
+	/* 1) ninguna mujer iM por la que Hombre tenga más preferencia que Mujer, y que a su vez iM prefiera más a Hombre que a su actual pareja */
+	/* 2) ningún hombre iH por el que Mujer tenga más preferencia que Hombre, y que a su vez iH prefiera más a Mujer que a su actual pareja */
+	
+	
+	bool Estable = true;
+	
+	/* Tomo la primer mujer de la lista de preferencias del hombre */
+	personas_type::iterator iM = (*Hombre)->prefs.begin();
+	
+	
+	/* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
+	while((iM<Mujer) && Estable)
+	{
+		/* Si la mujer no está soltera */
+		if ((*iM)->estado != Persona::SOLTERO)
+		{
+			/* Me fijo si me prefiere más que al que tiene ahora */
+			Estable = (std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre) > std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),(*iM)->pareja));
+		}
+	
+		iM++;
+	}
+	
+	/* Calculo dónde está el hombre actual en la lista de preferencias de la mujer */
+	personas_type::iterator iHombre = std::find((*iM)->prefs.begin(),(*iM)->prefs.end(),*Hombre);
+	
+	/* Tomo el primer hombre de la lista de preferencias de la mujer */
+	personas_type::iterator iH = (*Mujer)->prefs.begin();
+	
+	/* Mientras no encuentre a la mujer actual (o sea, voy viendo a las que prefiero más que a la candidata) */
+	while((iH<iHombre) && Estable)
+	{
+		/* Si el hombre no está soltero */
+		if ((*iH)->estado != Persona::SOLTERO)
+		{
+			/* Me fijo si me prefiere más que a la que tiene ahora */
+			Estable = (std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),*Mujer) > std::find((*iH)->prefs.begin(),(*iH)->prefs.end(),(*iH)->pareja));
+		}
+		
+		iH++;
+	}	
+	
+	return Estable;
+}
+
+void BackTracking::casamentear()
+{
+	/* Entrada a la llamada recursiva con el primer hombre de la lista */
+	Ensayar(hombres.begin());
+}
diff --git a/src/backtracking.h b/src/backtracking.h
new file mode 100644
index 0000000..2a84d49
--- /dev/null
+++ b/src/backtracking.h
@@ -0,0 +1,33 @@
+#ifndef _BACKTRACKING_H_
+#define _BACKTRACKING_H_
+
+#include "persona.h"
+#include "susanita.h"
+#include "parser.h"
+#include <map>
+#include <deque>
+#include <string>
+
+#ifdef __VC++__
+/* find_if está en <algorithm> en VC++ */
+#include <algorithm>
+#endif
+
+struct BackTracking : Susanita
+{
+	/// Constructor
+	BackTracking(size_type capacidad);
+
+	/// Empieza a emparejar gente
+	void casamentear();
+
+	private:
+	
+	/* Llamada recursiva: Ensaya una alternativa con el N-ésimo hombre */
+	void Ensayar(personas_type::iterator iH);
+	
+	/* Determina si la pareja es estable */
+	bool ParejaEstable(personas_type::iterator Mujer, personas_type::iterator Hombre);
+};
+
+#endif /* _BACKTRACKING_H_ */
-- 
2.43.0