include/anna/core/util/MultiMap.hpp

   1 // ANNA - Anna is Not 'N' Anymore
   2 //
   3 // (c) Copyright 2005-2014 Eduardo Ramos Testillano & Francisco Ruiz Rayo
   4 //
   5 // https://bitbucket.org/testillano/anna
   6 //
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions
   9 // are met:
  10 //
  11 //     * Redistributions of source code must retain the above copyright
  12 // notice, this list of conditions and the following disclaimer.
  13 //     * Redistributions in binary form must reproduce the above
  14 // copyright notice, this list of conditions and the following disclaimer
  15 // in the documentation and/or other materials provided with the
  16 // distribution.
  17 //     * Neither the name of Google Inc. nor the names of its
  18 // contributors may be used to endorse or promote products derived from
  19 // this software without specific prior written permission.
  20 //
  21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 //
  33 // Authors: eduardo.ramos.testillano@gmail.com
  34 //          cisco.tierra@gmail.com
  35
  36
  37 #ifndef anna_core_util_MultiMap_hpp
  38 #define anna_core_util_MultiMap_hpp
  39
  40 // Solaris std::multimap is missing !!
  41
  42 #include <algorithm>
  43 #include <functional>
  44 #include <vector>
  45
  46 #include <anna/core/RuntimeException.hpp>
  47 #include <anna/config/defines.hpp>
  48
  49 namespace anna {
  50
  51 /**
  52    Patron para ordenar instancias de objetos en base de una clave. El uso de este patrón está aconsejado cuando
  53    tenemos que gestionar cientos o miles de objetos. La eficiencia de los borrado y las inserciones es O(log N).
  54
  55    \param T Clase del patron.
  56    \param SortBy Clase que ofrece el valor por el que ordenar. Debe implementar un metodo constante con la
  57     signatura: TKey value (const T*)
  58    \param TKey Tipo de clave usado para calcular la ordenacion. Debe implementar los operadores '=', '<' y '==' y el
  59    contructor copia.
  60 */
  61 template < typename T, typename SortBy, typename TKey = int > class MultiMap : public std::vector <T*> {
  62   struct LessT : public std::binary_function <T*, T*, bool> {
  63     bool operator()(const T* first, const T* second) const throw() {
  64       return SortBy::value(first) < SortBy::value(second);
  65     }
  66   };
  67
  68   // El orden de los operandos está impuesto por cómo se invoca al operator() desde stl_algo.h (2685).
  69   struct LessKey : public std::binary_function <T*, TKey, bool> {
  70     bool operator()(const T* _vv, const TKey& searched) const throw() {
  71       return SortBy::value(_vv) < searched;
  72     }
  73   };
  74
  75 public:
  76   typedef typename std::vector <T*> container;
  77   typedef typename container::iterator iterator;
  78   typedef typename container::const_iterator const_iterator;
  79   typedef typename container::value_type value_type;
  80
  81   /**
  82      Constructor.
  83   */
  84   MultiMap() {;}
  85
  86   /**
  87      Constructor copia.
  88      \param other Instancia de la que copiar.
  89   */
  90   explicit MultiMap(const MultiMap& other) : container(other) {}
  91
  92   /**
  93      Destructor.
  94   */
  95   virtual ~MultiMap() { this->clear(); }
  96
  97   /**
  98      Incorpora la instancia recibida como parametro en la lista ordenada de objetos.
  99      \param _vv Instancia a guardar en el map. Si es NULL la operacion no tendra ningun efecto.
 100      \return \em true si ha registrado la nueva instancia o \em false en otro caso.
 101   */
 102   bool add(T* _vv)
 103   throw(RuntimeException) {
 104     if(_vv == NULL)
 105       return false;
 106
 107     iterator maxii = this->end();
 108     iterator ii = std::upper_bound(this->begin(), maxii, _vv, a_lessT);
 109
 110     if(ii == maxii)
 111       this->push_back(_vv);
 112     else
 113       this->insert(ii, _vv);
 114
 115     return true;
 116   }
 117
 118   /**
 119      Devolvera \em true si la instancia recibida como parametro esta contenido en el
 120      map o \em en otro caso. Si la instancia recibida es NULL siempre devolvera \em false.
 121      \param _vv Instancia a comprobar.
 122      \return \em true si la instancia recibida como parametro esta contenido en el
 123      map o \em en otro caso.
 124   */
 125   bool contains(const T* _vv) const throw() { return (_vv == NULL) ? false : (find(SortBy::value(_vv)) != NULL); }
 126
 127   /**
 128    * Borra las entradas contenidas en el vector ordenado y libera la memoria asociada a las mismas.
 129    */
 130   void clearAndDestroy() throw() {
 131     for(iterator ii = this->begin(), maxii = this->end(); ii != maxii; ii ++)
 132       delete data(ii);
 133
 134     this->clear();
 135   }
 136
 137   /**
 138      Elimina la instancia recibida como parametro de la lista ordenada de objetos, pero no se libera su memoria.
 139      \param _vv Instancia a guardar en el map. Si es NULL la operacion no tendra ningun efecto.
 140      \return La instancia correspondiente a la entrada borrada o NULL si no se encontró ninguna entrada válida.
 141   */
 142   T* erase(const T* _vv)
 143   throw(RuntimeException) {
 144     if(_vv == NULL)
 145       return NULL;
 146
 147     iterator maxii = this->end();
 148     iterator ii = std::lower_bound(this->begin(), this->end(), _vv, a_lessT);
 149
 150     if(ii == maxii)
 151       return NULL;
 152
 153     T* dd = data(ii);
 154
 155     if(!(SortBy::value(_vv) == SortBy::value(dd)))
 156       return NULL;
 157
 158     container::erase(ii);
 159     return dd;
 160   }
 161
 162   /**
 163    * Borra la entrada asociada al iterador recibido. El iterador recibido deja de ser válido.
 164    * \param ii Posición a borrar
 165    * \return La nueva posición a la que debería pasar el iterador una vez borrada la entrada.
 166    *
 167    */
 168   iterator erase_iterator(iterator ii) throw() { return container::erase(ii); }
 169
 170   /**
 171      Devuelve la instancia asociada a la clave recibida como parametro o NULL si no existe.
 172      \param key Clave a buscar en el map.
 173      \return la instancia asociada a la clave recibida como parametro o NULL si no existe.
 174   */
 175   T* find(const TKey& key)
 176   throw() {
 177     iterator maxii = this->end();
 178     iterator ii = lower_bound(this->begin(), maxii, key, a_lessKey);
 179
 180     if(ii == maxii)
 181       return NULL;
 182
 183     T* pos = data(ii);
 184     return (SortBy::value(pos) == key) ? pos : NULL;
 185   }
 186
 187   /**
 188    * Devuelve el iterador a la instancia asociada a la clave recibida.
 189    * \return el iterador a la instancia asociada a la clave recibida.
 190    */
 191   iterator find_iterator(const TKey& key)
 192   throw() {
 193     return lower_bound(this->begin(), this->end(), key, a_lessKey);
 194   }
 195
 196   /**
 197      Devuelve la instancia asociada a la clave recibida como parametro o NULL si no existe.
 198      \param key Clave a buscar en el map.
 199      \return la instancia asociada a la clave recibida como parametro o NULL si no existe.
 200   */
 201   const T* find(const TKey& key) const throw() {
 202     return const_cast <MultiMap <T, SortBy, TKey>*>(this)->find(key);
 203   }
 204
 205   /**
 206      Devuelve el objeto referenciado por el iterador.
 207      \return El objeto referenciado por el iterador.
 208   */
 209   static T* data(iterator ii) throw() { return *ii; }
 210
 211   /**
 212      Devuelve el objeto referenciado por el iterador.
 213      \return El objeto referenciado por el iterador.
 214   */
 215   static const T* data(const_iterator ii) throw() { return *ii; }
 216
 217 private:
 218   LessT a_lessT;
 219   LessKey a_lessKey;
 220 };
 221
 222 }
 223
 224 #endif
 225