bug in RC
[anna.git] / 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 throw() {
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 throw() {
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   throw(RuntimeException) {
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 throw() { 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() throw() {
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   throw(RuntimeException) {
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) throw() { 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   throw() {
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   throw() {
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 throw() {
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) throw() { 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) throw() { return *ii; }
188
189 private:
190   LessT a_lessT;
191   LessKey a_lessKey;
192 };
193
194 }
195
196 #endif
197