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