1 // ANNA - Anna is Not Nothingness Anymore
3 // (c) Copyright 2005-2014 Eduardo Ramos Testillano & Francisco Ruiz Rayo
5 // http://redmine.teslayout.com/projects/anna-suite
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions
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
17 // * Neither the name of the copyright holder 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.
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.
33 // Authors: eduardo.ramos.testillano@gmail.com
34 // cisco.tierra@gmail.com
37 #ifndef anna_core_util_MultiMap_hpp
38 #define anna_core_util_MultiMap_hpp
40 // Solaris std::multimap is missing !!
46 #include <anna/core/RuntimeException.hpp>
47 #include <anna/config/defines.hpp>
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).
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
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);
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;
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;
88 \param other Instancia de la que copiar.
90 explicit MultiMap(const MultiMap& other) : container(other) {}
95 virtual ~MultiMap() { this->clear(); }
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.
103 throw(RuntimeException) {
107 iterator maxii = this->end();
108 iterator ii = std::upper_bound(this->begin(), maxii, _vv, a_lessT);
111 this->push_back(_vv);
113 this->insert(ii, _vv);
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.
125 bool contains(const T* _vv) const throw() { return (_vv == NULL) ? false : (find(SortBy::value(_vv)) != NULL); }
128 * Borra las entradas contenidas en el vector ordenado y libera la memoria asociada a las mismas.
130 void clearAndDestroy() throw() {
131 for(iterator ii = this->begin(), maxii = this->end(); ii != maxii; ii ++)
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.
142 T* erase(const T* _vv)
143 throw(RuntimeException) {
147 iterator maxii = this->end();
148 iterator ii = std::lower_bound(this->begin(), this->end(), _vv, a_lessT);
155 if(!(SortBy::value(_vv) == SortBy::value(dd)))
158 container::erase(ii);
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.
168 iterator erase_iterator(iterator ii) throw() { return container::erase(ii); }
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.
175 T* find(const TKey& key)
177 iterator maxii = this->end();
178 iterator ii = lower_bound(this->begin(), maxii, key, a_lessKey);
184 return (SortBy::value(pos) == key) ? pos : NULL;
188 * Devuelve el iterador a la instancia asociada a la clave recibida.
189 * \return el iterador a la instancia asociada a la clave recibida.
191 iterator find_iterator(const TKey& key)
193 return lower_bound(this->begin(), this->end(), key, a_lessKey);
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.
201 const T* find(const TKey& key) const throw() {
202 return const_cast <MultiMap <T, SortBy, TKey>*>(this)->find(key);
206 Devuelve el objeto referenciado por el iterador.
207 \return El objeto referenciado por el iterador.
209 static T* data(iterator ii) throw() { return *ii; }
212 Devuelve el objeto referenciado por el iterador.
213 \return El objeto referenciado por el iterador.
215 static const T* data(const_iterator ii) throw() { return *ii; }