COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map_factory.h @ 817:3e30caeb9c00

Last change on this file since 817:3e30caeb9c00 was 817:3e30caeb9c00, checked in by Balazs Dezso, 16 years ago

Some warining fix in maps.

File size: 10.1 KB
Line 
1// -*- c++ -*-
2#ifndef ARRAY_MAP_FACTORY_H
3#define ARRAY_MAP_FACTORY_H
4
5#include <memory>
6
7#include <hugo/extended_pair.h>
8
9///\ingroup graphmapfactory
10///\file
11///\brief Graph maps that construates and destruates
12///their elements dynamically.
13
14namespace hugo {
15
16
17/// \addtogroup graphmapfactory
18/// @{
19       
20  /** The ArrayMapFactory template class is a factory class
21   *  to create maps for the edge and nodes. This map factory
22   *  uses the allocators to implement the container function.
23   *
24   *  The template parameter is the MapRegistry that the maps
25   *  will belong to.
26   */
27
28  template <typename MapRegistry>
29  class ArrayMapFactory {
30               
31  public:
32               
33    /// The graph type of the maps.
34    typedef typename MapRegistry::Graph Graph;
35    /// The key type of the maps.
36    typedef typename MapRegistry::KeyType KeyType;
37    /// The iterator to iterate on the keys.
38    typedef typename MapRegistry::KeyIt KeyIt;
39
40    /// The MapBase of the Map which imlements the core regisitry function.
41    typedef typename MapRegistry::MapBase MapBase;
42               
43    /** The template Map type.
44     */
45    template <typename V, typename A = std::allocator<V> >
46    class Map : public MapBase {
47   
48      public:
49
50      /// The value type of the map.
51      typedef V ValueType;
52
53      /// The value type of the map.
54      typedef V Value;
55      /// The reference type of the map;
56      typedef Value& Reference;
57      /// The pointer type of the map;
58      typedef Value* Pointer;
59
60      /// The const value type of the map.
61      typedef const Value ConstValue;
62      /// The const reference type of the map;
63      typedef const Value& ConstReference;
64      /// The pointer type of the map;
65      typedef const Value* ConstPointer;
66
67
68      typedef A Allocator;
69
70       
71      /** Default constructor for the map.
72       */
73      Map() : values(0), capacity(0) {}
74                       
75      /** Graph and Registry initialized map constructor.
76       */
77      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
78        allocate_memory();
79        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
80          int id = MapBase::getGraph()->id(it);
81          allocator.construct(&(values[id]), Value());
82        }                                                               
83      }
84
85      /** Constructor to use default value to initialize the map.
86       */
87      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
88        allocate_memory();
89        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
90          int id = MapBase::getGraph()->id(it);
91          allocator.construct(&(values[id]), v);
92        }                                                               
93      }
94
95      /** Constructor to copy a map of the same map type.
96       */
97      Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
98        capacity = copy.capacity;
99        if (capacity == 0) return;
100        values = allocator.allocate(capacity);
101        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
102          int id = MapBase::getGraph()->id(it);
103          allocator.construct(&(values[id]), copy.values[id]);
104        }
105      }
106
107      /** Constructor to copy a map of an other map type.
108       */
109      template <typename CMap> Map(const CMap& copy)
110        : MapBase(copy), capacity(0), values(0) {
111        if (MapBase::getGraph()) {
112          allocate_memory();
113          for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
114            set(it, copy[it]);
115          }
116        }
117      }
118
119      /** Assign operator to copy a map of the same map type.
120       */
121      Map& operator=(const Map& copy) {
122        if (&copy == this) return *this;
123        if (capacity != 0) {
124          MapBase::destroy();
125          allocator.deallocate(values, capacity);
126        }
127        capacity = copy.capacity;
128        if (capacity == 0) return *this;
129        values = allocator.allocate(capacity);
130        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
131          int id = MapBase::getGraph()->id(it);
132          allocator.construct(&(values[id]), copy.values[id]);
133        }
134        return *this;
135      }
136
137      /** Assign operator to copy a map an other map type.
138       */
139      template <typename CMap> Map& operator=(const CMap& copy) {
140        if (MapBase::getGraph()) {
141          MapBase::destroy();
142        }
143        MapBase::operator=(copy);
144        if (MapBase::getGraph()) {
145          allocate_memory();
146          for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
147            set(it, copy[it]);
148          }
149        }
150        return *this;
151      }
152                               
153      /** The destructor of the map.
154       */
155      virtual ~Map() {
156        if (capacity != 0) {
157          MapBase::destroy();
158          allocator.deallocate(values, capacity);
159        }
160      }
161       
162       
163      /**
164       * The subscript operator. The map can be subscripted by the
165       * actual keys of the graph.
166       */
167      Value& operator[](const KeyType& key) {
168        int id = MapBase::getGraph()->id(key);
169        return values[id];
170      }
171               
172      /**
173       * The const subscript operator. The map can be subscripted by the
174       * actual keys of the graph.
175       */
176      const Value& operator[](const KeyType& key) const {
177        int id = MapBase::getGraph()->id(key);
178        return values[id];
179      }
180       
181      /** Setter function of the map. Equivalent with map[key] = val.
182       *  This is a compatibility feature with the not dereferable maps.
183       */
184      void set(const KeyType& key, const Value& val) {
185        int id = MapBase::getGraph()->id(key);
186        values[id] = val;
187      }
188               
189      /** Add a new key to the map. It called by the map registry.
190       */
191      void add(const KeyType& key) {
192        int id = MapBase::getGraph()->id(key);
193        if (id >= capacity) {
194          int new_capacity = (capacity == 0 ? 1 : capacity);
195          while (new_capacity <= id) {
196            new_capacity <<= 1;
197          }
198          Value* new_values = allocator.allocate(new_capacity);;
199          for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
200            int jd = MapBase::getGraph()->id(it);
201            if (id != jd) {
202              allocator.construct(&(new_values[jd]), values[jd]);
203              allocator.destroy(&(values[jd]));
204            }
205          }
206          if (capacity != 0) allocator.deallocate(values, capacity);
207          values = new_values;
208          capacity = new_capacity;
209        }
210        allocator.construct(&(values[id]), Value());
211      }
212               
213      /** Erase a key from the map. It called by the map registry.
214       */
215      void erase(const KeyType& key) {
216        int id = MapBase::getGraph()->id(key);
217        allocator.destroy(&(values[id]));
218      }
219
220      /** Clear the data structure.
221       */
222      void clear() {   
223        if (capacity != 0) {
224          MapBase::destroy();
225          allocator.deallocate(values, capacity);
226          capacity = 0;
227        }
228      }
229
230      class iterator;
231      class const_iterator;
232       
233      /** Compatible iterator with the stl maps' iterators.
234       *  It iterates on pairs of a key and a value.
235       */
236      class iterator {
237        friend class Map;
238        friend class const_iterator;
239      private:
240
241        /** Private constructor to initalize the the iterators returned
242         *  by the begin() and end().
243         */
244        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
245
246      public:
247
248        /** Default constructor.
249         */
250        iterator() {}
251
252        typedef extended_pair<const KeyType&, const KeyType&,
253                              Value&, Value&> Reference;
254
255        /** Dereference operator for map.
256         */     
257        Reference operator*() {
258          return Reference(it, (*map)[it]);
259        }
260
261        class Pointer {
262          friend class iterator;
263        private:
264          Reference data;
265          Pointer(const KeyType& key, Value& val) : data(key, val) {}
266        public:
267          Reference* operator->() {return &data;}
268        };
269
270        /** Arrow operator for map.
271         */     
272        Pointer operator->() {
273          return Pointer(it, ((*map)[it]));
274        }
275
276        /** The pre increment operator of the map.
277         */
278        iterator& operator++() {
279          ++it;
280          return *this;
281        }
282
283        /** The post increment operator of the map.
284         */
285        iterator operator++(int) {
286          iterator tmp(it);
287          ++it;
288          return tmp;
289        }
290
291        /** The equality operator of the map.
292         */
293        bool operator==(const_iterator p_it) {
294          return p_it.it == it;
295        }
296       
297        /** The not-equality operator of the map.
298         */
299        bool operator!=(const_iterator p_it) {
300          return !(*this == p_it);
301        }
302
303       
304      private:
305        Map* map;
306        KeyIt it;
307      };
308
309      /** Returns the begin iterator of the map.
310       */
311      iterator begin() {
312        return iterator(*this, KeyIt(*MapBase::getGraph()));
313      }
314
315      /** Returns the end iterator of the map.
316       */
317      iterator end() {
318        return iterator(*this, INVALID);
319      }
320
321      class const_iterator {
322        friend class Map;
323        friend class iterator;
324      private:
325
326        /** Private constructor to initalize the the iterators returned
327         *  by the begin() and end().
328         */
329        const_iterator (const Map& pmap, const KeyIt& pit)
330          : map(&pmap), it(pit) {}
331
332      public:
333
334        /** Default constructor.
335         */
336        const_iterator() {}
337
338        /** Constructor to convert iterator to const_iterator.
339         */
340        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
341     
342        typedef extended_pair<const KeyType&, const KeyType&,
343          const Value&, const Value&> Reference;
344
345        /** Dereference operator for map.
346         */     
347        Reference operator*() {
348          return Reference(it, (*map)[it]);
349        }
350
351
352        class Pointer {
353          friend class const_iterator;
354        private:
355          Reference data;
356          Pointer(const KeyType& key, const Value& val) : data(key, val) {}
357        public:
358          Reference* operator->() {return &data;}
359        };
360
361        /** Arrow operator for map.
362         */     
363        Pointer operator->() {
364          return Pointer(it, ((*map)[it]));
365        }
366
367        /** The pre increment operator of the map.
368         */
369        const_iterator& operator++() {
370          ++it;
371          return *this;
372        }
373
374        /** The post increment operator of the map.
375         */
376        const_iterator operator++(int) {
377          const_iterator tmp(it);
378          ++it;
379          return tmp;
380        }
381
382        /** The equality operator of the map.
383         */
384        bool operator==(const_iterator p_it) {
385          return p_it.it == it;
386        }
387       
388        /** The not-equality operator of the map.
389         */
390        bool operator!=(const_iterator p_it) {
391          return !(*this == p_it);
392        }
393       
394
395      private:
396        const Map* map;
397        KeyIt it;
398      };
399
400      /** Returns the begin const_iterator of the map.
401       */
402      const_iterator begin() const {
403        return const_iterator(*this, KeyIt(*MapBase::getGraph()));
404      }
405
406      /** Returns the end const_iterator of the map.
407       */
408      const_iterator end() const {
409        return const_iterator(*this, INVALID);
410      }
411
412    private:
413     
414      void allocate_memory() {
415        int max_id = -1;
416        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
417          int id = MapBase::getGraph()->id(it);
418          if (id > max_id) {
419            max_id = id;
420          }                     
421        }
422        if (max_id == -1) {
423          capacity = 0;
424          values = 0;
425          return;
426        }
427        capacity = 1;
428        while (capacity <= max_id) {
429          capacity <<= 1;
430        }
431        values = allocator.allocate(capacity); 
432      }     
433
434      int capacity;
435      Value* values;
436      Allocator allocator;
437    };         
438  };
439
440/// @}
441
442}
443
444#endif
Note: See TracBrowser for help on using the repository browser.