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