COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/vector_map_factory.h @ 798:6d1abeb62dd3

Last change on this file since 798:6d1abeb62dd3 was 798:6d1abeb62dd3, checked in by Balazs Dezso, 16 years ago
File size: 8.1 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       
26  template <typename MapRegistry>
27  class VectorMapFactory {
28  public:
29               
30    /// The graph type of the maps.
31    typedef typename MapRegistry::Graph Graph;
32    /// The key type of the maps.
33    typedef typename MapRegistry::KeyType KeyType;
34    /// The iterator to iterate on the keys.
35    typedef typename MapRegistry::KeyIt KeyIt;
36
37    /// The MapBase of the Map which imlements the core regisitry function.
38    typedef typename MapRegistry::MapBase MapBase;
39
40               
41    /** The template Map type.
42     */
43    template <typename V>
44    class Map : public MapBase {
45
46      typedef std::vector<V> Container;
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 typename Container::reference Reference;
57      /// The pointer type of the map;
58      typedef typename Container::pointer 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 typename Container::const_reference ConstReference;
64      /// The pointer type of the map;
65      typedef typename Container::const_pointer ConstPointer;
66
67      /** Default constructor for the map.
68       */
69      Map() {}
70               
71      /** Graph and Registry initialized map constructor.
72       */
73      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
74        init();
75      }
76
77      /** Constructor to use default value to initialize the map.
78       */
79      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
80        for (KeyIt it(*getGraph()); it != INVALID; ++it) {
81          int id = getGraph()->id(it);
82          if (id >= (int)container.size()) {
83            container.resize(id + 1);
84          }
85          set(it, v);
86        }
87      }
88
89      /** Constructor to copy a map of an other map type.
90       */
91      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
92        if (getGraph()) {
93          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
94            int id = getGraph()->id(it);
95            if (id >= (int)container.size()) {
96              container.resize(id + 1);
97            }
98            set(it, copy[it]);
99          }
100        }
101      }
102
103      /** Assign operator to copy a map an other map type.
104       */
105      template <typename CMap> Map& operator=(const CMap& copy) {
106        if (getGraph()) {
107          destroy();
108        }
109        this->MapBase::operator=(copy);
110        if (getGraph()) {
111          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
112            int id = getGraph()->id(it);
113            if (id >= (int)container.size()) {
114              container.resize(id + 1);
115            }
116            set(it, copy[it]);
117          }
118        }
119        return *this;
120      }
121
122      /** The destructor of the map.
123       */
124      virtual ~Map() {
125      }
126               
127      /**
128       * The subscript operator. The map can be subscripted by the
129       * actual keys of the graph.
130       */
131<<<<<<< .mine
132      Reference operator[](const Key& key) {
133=======
134      typename Container::reference operator[](const KeyType& key) {
135>>>>>>> .r1091
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<<<<<<< .mine
145      ConstReference operator[](const Key& key) const {
146=======
147      typename Container::const_reference operator[](const KeyType& key) const {
148>>>>>>> .r1091
149        int id = getGraph()->id(key);
150        return container[id];
151      }
152
153      /** Setter function of the map. Equivalent with map[key] = val.
154       *  This is a compatibility feature with the not dereferable maps.
155       */
156      void set(const KeyType& key, const Value& val) {
157        int id = getGraph()->id(key);
158        container[id] = val;
159      }
160               
161      /** Add a new key to the map. It called by the map registry.
162       */
163      void add(const KeyType& key) {
164        int id = getGraph()->id(key);
165        if (id >= (int)container.size()) {
166          container.resize(id + 1);
167        }
168      }
169               
170      /** Erase a key from the map. It called by the map registry.
171       */
172      void erase(const KeyType& key) {}
173
174      /** Clear the data structure.
175       */
176      void clear() {
177        container.clear();
178      }
179
180      /** Compatible iterator with the stl maps' iterators.
181       *  It iterates on pairs of a key and a value.
182       */
183      class iterator {
184        friend class Map;
185        friend class const_iterator;
186      private:
187
188        /** Private constructor to initalize the the iterators returned
189         *  by the begin() and end().
190         */
191        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
192
193      public:
194
195        /** Default constructor.
196         */
197        iterator() {}
198
199        typedef extended_pair<const KeyType&, const KeyType&,
200                              Map::Reference, Map::Reference> Reference;
201
202        /** Dereference operator for map.
203         */     
204        Reference operator*() {
205          return Reference(it, (*map)[it]);
206        }
207
208        class Pointer {
209          friend class iterator;
210        private:
211          Reference data;
212          Pointer(const KeyType& key, Value& val) : data(key, val) {}
213        public:
214          Reference* operator->() {return &data;}
215        };
216
217        /** Arrow operator for map.
218         */     
219        Pointer operator->() {
220          return Pointer(it, ((*map)[it]));
221        }
222
223        /** The pre increment operator of the map.
224         */
225        iterator& operator++() {
226          ++it;
227          return *this;
228        }
229
230        /** The post increment operator of the map.
231         */
232        iterator operator++(int) {
233          iterator tmp(it);
234          ++it;
235          return tmp;
236        }
237
238        /** The equality operator of the map.
239         */
240        bool operator==(const_iterator p_it) {
241          return p_it.it == it;
242        }
243       
244        /** The not-equality operator of the map.
245         */
246        bool operator!=(const_iterator p_it) {
247          return !(*this == p_it);
248        }
249
250       
251      private:
252        Map* map;
253        KeyIt it;
254      };
255
256      /** Returns the begin iterator of the map.
257       */
258      iterator begin() {
259        return iterator(*this, KeyIt(*getGraph()));
260      }
261
262      /** Returns the end iterator of the map.
263       */
264      iterator end() {
265        return iterator(*this, INVALID);
266      }
267
268      class const_iterator {
269        friend class Map;
270        friend class iterator;
271      private:
272
273        /** Private constructor to initalize the the iterators returned
274         *  by the begin() and end().
275         */
276        const_iterator (const Map& pmap, const KeyIt& pit)
277          : map(&pmap), it(pit) {}
278
279      public:
280
281        /** Default constructor.
282         */
283        const_iterator() {}
284
285        /** Constructor to convert iterator to const_iterator.
286         */
287        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
288     
289        typedef extended_pair<const KeyType&, const KeyType&,
290          Map::ConstReference, Map::ConstReference> Reference;
291
292        /** Dereference operator for map.
293         */     
294        Reference operator*() {
295          return Reference(it, (*map)[it]);
296        }
297
298
299        class Pointer {
300          friend class const_iterator;
301        private:
302          Reference data;
303          Pointer(const KeyType& key, const Value& val) : 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.