COIN-OR::LEMON - Graph Library

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