include/anna/core/util/MultiMap.hpp

   1 // ANNA - Anna is Not Nothingness Anymore                                                         //
   2 //                                                                                                //
   3 // (c) Copyright 2005-2015 Eduardo Ramos Testillano & Francisco Ruiz Rayo                         //
   4 //                                                                                                //
   5 // See project site at http://redmine.teslayout.com/projects/anna-suite                           //
   6 // See accompanying file LICENSE or copy at http://www.teslayout.com/projects/public/anna.LICENSE //
   7
   8
   9 #ifndef anna_core_util_MultiMap_hpp
  10 #define anna_core_util_MultiMap_hpp
  11
  12 // Solaris std::multimap is missing !!
  13
  14 #include <algorithm>
  15 #include <functional>
  16 #include <vector>
  17
  18 #include <anna/core/RuntimeException.hpp>
  19 #include <anna/config/defines.hpp>
  20
  21 namespace anna {
  22
  23 /**
  24    Patron para ordenar instancias de objetos en base de una clave. El uso de este patrón está aconsejado cuando
  25    tenemos que gestionar cientos o miles de objetos. La eficiencia de los borrado y las inserciones es O(log N).
  26
  27    \param T Clase del patron.
  28    \param SortBy Clase que ofrece el valor por el que ordenar. Debe implementar un metodo constante con la
  29     signatura: TKey value (const T*)
  30    \param TKey Tipo de clave usado para calcular la ordenacion. Debe implementar los operadores '=', '<' y '==' y el
  31    contructor copia.
  32 */
  33 template < typename T, typename SortBy, typename TKey = int > class MultiMap : public std::vector <T*> {
  34   struct LessT : public std::binary_function <T*, T*, bool> {
  35     bool operator()(const T* first, const T* second) const {
  36       return SortBy::value(first) < SortBy::value(second);
  37     }
  38   };
  39
  40   // El orden de los operandos está impuesto por cómo se invoca al operator() desde stl_algo.h (2685).
  41   struct LessKey : public std::binary_function <T*, TKey, bool> {
  42     bool operator()(const T* _vv, const TKey& searched) const {
  43       return SortBy::value(_vv) < searched;
  44     }
  45   };
  46
  47 public:
  48   typedef typename std::vector <T*> container;
  49   typedef typename container::iterator iterator;
  50   typedef typename container::const_iterator const_iterator;
  51   typedef typename container::value_type value_type;
  52
  53   /**
  54      Constructor.
  55   */
  56   MultiMap() {;}
  57
  58   /**
  59      Constructor copia.
  60      \param other Instancia de la que copiar.
  61   */
  62   explicit MultiMap(const MultiMap& other) : container(other) {}
  63
  64   /**
  65      Destructor.
  66   */
  67   virtual ~MultiMap() { this->clear(); }
  68
  69   /**
  70      Incorpora la instancia recibida como parametro en la lista ordenada de objetos.
  71      \param _vv Instancia a guardar en el map. Si es NULL la operacion no tendra ningun efecto.
  72      \return \em true si ha registrado la nueva instancia o \em false en otro caso.
  73   */
  74   bool add(T* _vv)
  75   noexcept(false) {
  76     if(_vv == NULL)
  77       return false;
  78
  79     iterator maxii = this->end();
  80     iterator ii = std::upper_bound(this->begin(), maxii, _vv, a_lessT);
  81
  82     if(ii == maxii)
  83       this->push_back(_vv);
  84     else
  85       this->insert(ii, _vv);
  86
  87     return true;
  88   }
  89
  90   /**
  91      Devolvera \em true si la instancia recibida como parametro esta contenido en el
  92      map o \em en otro caso. Si la instancia recibida es NULL siempre devolvera \em false.
  93      \param _vv Instancia a comprobar.
  94      \return \em true si la instancia recibida como parametro esta contenido en el
  95      map o \em en otro caso.
  96   */
  97   bool contains(const T* _vv) const { return (_vv == NULL) ? false : (find(SortBy::value(_vv)) != NULL); }
  98
  99   /**
 100    * Borra las entradas contenidas en el vector ordenado y libera la memoria asociada a las mismas.
 101    */
 102   void clearAndDestroy() {
 103     for(iterator ii = this->begin(), maxii = this->end(); ii != maxii; ii ++)
 104       delete data(ii);
 105
 106     this->clear();
 107   }
 108
 109   /**
 110      Elimina la instancia recibida como parametro de la lista ordenada de objetos, pero no se libera su memoria.
 111      \param _vv Instancia a guardar en el map. Si es NULL la operacion no tendra ningun efecto.
 112      \return La instancia correspondiente a la entrada borrada o NULL si no se encontró ninguna entrada válida.
 113   */
 114   T* erase(const T* _vv)
 115   noexcept(false) {
 116     if(_vv == NULL)
 117       return NULL;
 118
 119     iterator maxii = this->end();
 120     iterator ii = std::lower_bound(this->begin(), this->end(), _vv, a_lessT);
 121
 122     if(ii == maxii)
 123       return NULL;
 124
 125     T* dd = data(ii);
 126
 127     if(!(SortBy::value(_vv) == SortBy::value(dd)))
 128       return NULL;
 129
 130     container::erase(ii);
 131     return dd;
 132   }
 133
 134   /**
 135    * Borra la entrada asociada al iterador recibido. El iterador recibido deja de ser válido.
 136    * \param ii Posición a borrar
 137    * \return La nueva posición a la que debería pasar el iterador una vez borrada la entrada.
 138    *
 139    */
 140   iterator erase_iterator(iterator ii) { return container::erase(ii); }
 141
 142   /**
 143      Devuelve la instancia asociada a la clave recibida como parametro o NULL si no existe.
 144      \param key Clave a buscar en el map.
 145      \return la instancia asociada a la clave recibida como parametro o NULL si no existe.
 146   */
 147   T* find(const TKey& key)
 148   {
 149     iterator maxii = this->end();
 150     iterator ii = lower_bound(this->begin(), maxii, key, a_lessKey);
 151
 152     if(ii == maxii)
 153       return NULL;
 154
 155     T* pos = data(ii);
 156     return (SortBy::value(pos) == key) ? pos : NULL;
 157   }
 158
 159   /**
 160    * Devuelve el iterador a la instancia asociada a la clave recibida.
 161    * \return el iterador a la instancia asociada a la clave recibida.
 162    */
 163   iterator find_iterator(const TKey& key)
 164   {
 165     return lower_bound(this->begin(), this->end(), key, a_lessKey);
 166   }
 167
 168   /**
 169      Devuelve la instancia asociada a la clave recibida como parametro o NULL si no existe.
 170      \param key Clave a buscar en el map.
 171      \return la instancia asociada a la clave recibida como parametro o NULL si no existe.
 172   */
 173   const T* find(const TKey& key) const {
 174     return const_cast <MultiMap <T, SortBy, TKey>*>(this)->find(key);
 175   }
 176
 177   /**
 178      Devuelve el objeto referenciado por el iterador.
 179      \return El objeto referenciado por el iterador.
 180   */
 181   static T* data(iterator ii) { return *ii; }
 182
 183   /**
 184      Devuelve el objeto referenciado por el iterador.
 185      \return El objeto referenciado por el iterador.
 186   */
 187   static const T* data(const_iterator ii) { return *ii; }
 188
 189 private:
 190   LessT a_lessT;
 191   LessKey a_lessKey;
 192 };
 193
 194 }
 195
 196 #endif
 197