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