src/galeshapley.cpp

   1 #include "galeshapley.h"
   2 #include <map>
   3 #include <deque>
   4 #include <string>
   5 #include <cassert>
   6 #include <iostream>
   7 #include <algorithm>
   8
   9 GaleShapley::
  10 GaleShapley()
  11 {
  12 }
  13
  14 void
  15 GaleShapley::
  16 primera_ronda()
  17 {
  18         for (personas_type::iterator ih = hombres.begin();
  19                         ih != hombres.end(); ++ih)
  20         {
  21                 (*ih)->declarar_a(*((*ih)->prefs[0]));
  22         }
  23         for (personas_type::iterator im = mujeres.begin();
  24                         im != mujeres.end(); ++im)
  25         {
  26                 Persona& m = **im;
  27                 if (m.ofertas.empty())
  28                         continue;
  29                 m.ordenar_ofertas();
  30                 Persona& prometido = *(m.ofertas.front());
  31                 m.ofertas.pop_front();
  32                 m.comprometer_con(prometido);
  33         }
  34 }
  35
  36 void
  37 GaleShapley::
  38 nesima_ronda()
  39 {
  40         for (personas_type::iterator ih = hombres.begin();
  41                         ih != hombres.end(); ++ih)
  42         {
  43                 Persona& h = **ih;
  44                 if (h.estado == Persona::COMPROMETIDO)
  45                         continue;
  46
  47                 Persona* pm = 0;
  48                 for (personas_type::iterator im = h.prefs.begin();
  49                                 im != h.prefs.end(); ++im)
  50                 {
  51                         pm = *im;
  52                         if (std::find(h.rechazos.begin(), h.rechazos.end(), pm)
  53                                         != h.rechazos.end()) // Si está
  54                                 continue;
  55                         break;
  56                 }
  57                 assert(pm);
  58                 h.declarar_a(*pm);
  59         }
  60
  61         for (personas_type::iterator im = mujeres.begin();
  62                         im != mujeres.end(); ++im)
  63         {
  64                 Persona& m = **im;
  65                 if (m.ofertas.empty())
  66                         continue;
  67
  68                 m.ordenar_ofertas();
  69                 Persona* ph = m.ofertas.front();
  70                 m.ofertas.pop_front();
  71                 if (m.estado == Persona::COMPROMETIDO)
  72                 {
  73                         if (m.cmp(*(m.pareja), *ph) < 0)
  74                         {
  75                                 // la oferta es mejor, rompemos el compromiso
  76                                 m.comprometer_con(*ph);
  77                         }
  78                         else
  79                         {
  80                                 // estamos mejor con nuestra pareja actual, asi
  81                                 // que no hacemos mas que rechazar a todos
  82                                 // (incluyendo el mejor candidato)
  83                                 for (Persona::ofertas_type::iterator i
  84                                                 = m.ofertas.begin();
  85                                                 i != m.ofertas.end(); ++i)
  86                                         (*i)->rechazos.push_back(&m);
  87                                 ph->rechazos.push_back(&m);
  88                                 m.ofertas.clear();
  89                         }
  90                 }
  91                 else
  92                 {
  93                         m.comprometer_con(*ph);
  94                 }
  95         }
  96 }
  97
  98 bool
  99 GaleShapley::
 100 todos_h_comprometidos() const
 101 {
 102         // FIXME: podemos ver de poner esto adentro de nesima_ronda()
 103         for (personas_type::const_iterator ih = hombres.begin();
 104                         ih != hombres.end(); ++ih)
 105                 if ((*ih)->estado != Persona::COMPROMETIDO)
 106                         return false;
 107         return true;
 108 }
 109
 110
 111 void
 112 GaleShapley::
 113 casamentear()
 114 {
 115         primera_ronda();
 116         while (!todos_h_comprometidos())
 117                 nesima_ronda();
 118 }
 119