COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map_factory.h @ 804:6874a72dbdc5

Last change on this file since 804:6874a72dbdc5 was 799:3393abe30678, checked in by Balazs Dezso, 20 years ago
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      /** Compatible iterator with the stl maps' iterators.
231       *  It iterates on pairs of a key and a value.
232       */
233      class iterator {
234        friend class Map;
235        friend class const_iterator;
236      private:
237
238        /** Private constructor to initalize the the iterators returned
239         *  by the begin() and end().
240         */
241        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
242
243      public:
244
245        /** Default constructor.
246         */
247        iterator() {}
248
249        typedef extended_pair<const KeyType&, const KeyType&,
250                              Value&, Value&> Reference;
251
252        /** Dereference operator for map.
253         */     
254        Reference operator*() {
255          return Reference(it, (*map)[it]);
256        }
257
258        class Pointer {
259          friend class iterator;
260        private:
261          Reference data;
262          Pointer(const KeyType& key, Value& val) : data(key, val) {}
263        public:
264          Reference* operator->() {return &data;}
265        };
266
267        /** Arrow operator for map.
268         */     
269        Pointer operator->() {
270          return Pointer(it, ((*map)[it]));
271        }
272
273        /** The pre increment operator of the map.
274         */
275        iterator& operator++() {
276          ++it;
277          return *this;
278        }
279
280        /** The post increment operator of the map.
281         */
282        iterator operator++(int) {
283          iterator tmp(it);
284          ++it;
285          return tmp;
286        }
287
288        /** The equality operator of the map.
289         */
290        bool operator==(const_iterator p_it) {
291          return p_it.it == it;
292        }
293       
294        /** The not-equality operator of the map.
295         */
296        bool operator!=(const_iterator p_it) {
297          return !(*this == p_it);
298        }
299
300       
301      private:
302        Map* map;
303        KeyIt it;
304      };
305
306      /** Returns the begin iterator of the map.
307       */
308      iterator begin() {
309        return iterator(*this, KeyIt(*MapBase::getGraph()));
310      }
311
312      /** Returns the end iterator of the map.
313       */
314      iterator end() {
315        return iterator(*this, INVALID);
316      }
317
318      class const_iterator {
319        friend class Map;
320        friend class iterator;
321      private:
322
323        /** Private constructor to initalize the the iterators returned
324         *  by the begin() and end().
325         */
326        const_iterator (const Map& pmap, const KeyIt& pit)
327          : map(&pmap), it(pit) {}
328
329      public:
330
331        /** Default constructor.
332         */
333        const_iterator() {}
334
335        /** Constructor to convert iterator to const_iterator.
336         */
337        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
338     
339        typedef extended_pair<const KeyType&, const KeyType&,
340          const Value&, const Value&> Reference;
341
342        /** Dereference operator for map.
343         */     
344        Reference operator*() {
345          return Reference(it, (*map)[it]);
346        }
347
348
349        class Pointer {
350          friend class const_iterator;
351        private:
352          Reference data;
353          Pointer(const KeyType& key, const Value& val) : data(key, val) {}
354        public:
355          Reference* operator->() {return &data;}
356        };
357
358        /** Arrow operator for map.
359         */     
360        Pointer operator->() {
361          return Pointer(it, ((*map)[it]));
362        }
363
364        /** The pre increment operator of the map.
365         */
366        const_iterator& operator++() {
367          ++it;
368          return *this;
369        }
370
371        /** The post increment operator of the map.
372         */
373        const_iterator operator++(int) {
374          const_iterator tmp(it);
375          ++it;
376          return tmp;
377        }
378
379        /** The equality operator of the map.
380         */
381        bool operator==(const_iterator p_it) {
382          return p_it.it == it;
383        }
384       
385        /** The not-equality operator of the map.
386         */
387        bool operator!=(const_iterator p_it) {
388          return !(*this == p_it);
389        }
390       
391
392      private:
393        const Map* map;
394        KeyIt it;
395      };
396
397      /** Returns the begin const_iterator of the map.
398       */
399      const_iterator begin() const {
400        return const_iterator(*this, KeyIt(*MapBase::getGraph()));
401      }
402
403      /** Returns the end const_iterator of the map.
404       */
405      const_iterator end() const {
406        return const_iterator(*this, INVALID);
407      }
408
409    private:
410     
411      void allocate_memory() {
412        int max_id = -1;
413        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
414          int id = MapBase::getGraph()->id(it);
415          if (id > max_id) {
416            max_id = id;
417          }                     
418        }
419        if (max_id == -1) {
420          capacity = 0;
421          values = 0;
422          return;
423        }
424        capacity = 1;
425        while (capacity <= max_id) {
426          capacity <<= 1;
427        }
428        values = allocator.allocate(capacity); 
429      }     
430
431      int capacity;
432      Value* values;
433      Allocator allocator;
434    };         
435  };
436
437/// @}
438
439}
440
441#endif
Note: See TracBrowser for help on using the repository browser.