COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/vector_map_factory.h @ 786:d7b3b13b9df6

Last change on this file since 786:d7b3b13b9df6 was 786:d7b3b13b9df6, checked in by Alpar Juttner, 16 years ago

Change 'Key' to 'KeyType?' (possibly temporarily).

File size: 7.4 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   *  use 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    public:
46
47      /// The value type of the map.
48      typedef V Value;
49
50      typedef std::vector<Value> Container;     
51
52      /** Default constructor for the map.
53       */
54      Map() {}
55               
56      /** Graph and Registry initialized map constructor.
57       */
58      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
59        init();
60      }
61
62      /** Constructor to use default value to initialize the map.
63       */
64      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
65        for (KeyIt it(*getGraph()); it != INVALID; ++it) {
66          int id = getGraph()->id(it);
67          if (id >= container.size()) {
68            container.resize(id + 1);
69          }
70          set(it, v);
71        }
72      }
73
74      /** Constructor to copy a map of an other map type.
75       */
76      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
77        if (getGraph()) {
78          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
79            int id = getGraph()->id(it);
80            if (id >= container.size()) {
81              container.resize(id + 1);
82            }
83            set(it, copy[it]);
84          }
85        }
86      }
87
88      /** Assign operator to copy a map an other map type.
89       */
90      template <typename CMap> Map& operator=(const CMap& copy) {
91        if (getGraph()) {
92          destroy();
93        }
94        this->MapBase::operator=(copy);
95        if (getGraph()) {
96          for (KeyIt it(*getGraph()); it != INVALID; ++it) {
97            int id = getGraph()->id(it);
98            if (id >= container.size()) {
99              container.resize(id + 1);
100            }
101            set(it, copy[it]);
102          }
103        }
104      }
105
106      /** The destructor of the map.
107       */
108      virtual ~Map() {
109      }
110               
111      /**
112       * The subscript operator. The map can be subscripted by the
113       * actual keys of the graph.
114       */
115      typename Container::reference operator[](const KeyType& key) {
116        int id = getGraph()->id(key);
117        return container[id];
118      }
119               
120      /**
121       * The const subscript operator. The map can be subscripted by the
122       * actual keys of the graph.
123       */
124      typename Container::const_reference operator[](const KeyType& key) const {
125        int id = getGraph()->id(key);
126        return container[id];
127      }
128
129      /** Setter function of the map. Equivalent with map[key] = val.
130       *  This is a compatibility feature with the not dereferable maps.
131       */
132      void set(const KeyType& key, const Value& val) {
133        int id = getGraph()->id(key);
134        container[id] = val;
135      }
136               
137      /** Add a new key to the map. It called by the map registry.
138       */
139      void add(const KeyType& key) {
140        int id = getGraph()->id(key);
141        if (id >= container.size()) {
142          container.resize(id + 1);
143        }
144      }
145               
146      /** Erase a key from the map. It called by the map registry.
147       */
148      void erase(const KeyType& key) {}
149
150      /** Clear the data structure.
151       */
152      void clear() {
153        container.clear();
154      }
155
156      /** Compatible iterator with the stl maps' iterators.
157       *  It iterates on pairs of a key and a value.
158       */
159      class iterator {
160        friend class Map;
161        friend class const_iterator;
162      private:
163
164        /** Private constructor to initalize the the iterators returned
165         *  by the begin() and end().
166         */
167        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
168
169      public:
170
171        /** Default constructor.
172         */
173        iterator() {}
174
175        typedef extended_pair<const KeyType&, const KeyType&,
176                              Value&, Value&> Reference;
177
178        /** Dereference operator for map.
179         */     
180        Reference operator*() {
181          return Reference(it, (*map)[it]);
182        }
183
184        class Pointer {
185          friend class iterator;
186        private:
187          Reference data;
188          Pointer(const KeyType& key, Value& val) : data(key, val) {}
189        public:
190          Reference* operator->() {return &data;}
191        };
192
193        /** Arrow operator for map.
194         */     
195        Pointer operator->() {
196          return Pointer(it, ((*map)[it]));
197        }
198
199        /** The pre increment operator of the map.
200         */
201        iterator& operator++() {
202          ++it;
203          return *this;
204        }
205
206        /** The post increment operator of the map.
207         */
208        iterator operator++(int) {
209          iterator tmp(it);
210          ++it;
211          return tmp;
212        }
213
214        /** The equality operator of the map.
215         */
216        bool operator==(const_iterator p_it) {
217          return p_it.it == it;
218        }
219       
220        /** The not-equality operator of the map.
221         */
222        bool operator!=(const_iterator p_it) {
223          return !(*this == p_it);
224        }
225
226       
227      private:
228        Map* map;
229        KeyIt it;
230      };
231
232      /** Returns the begin iterator of the map.
233       */
234      iterator begin() {
235        return iterator(*this, KeyIt(*getGraph()));
236      }
237
238      /** Returns the end iterator of the map.
239       */
240      iterator end() {
241        return iterator(*this, INVALID);
242      }
243
244      class const_iterator {
245        friend class Map;
246        friend class iterator;
247      private:
248
249        /** Private constructor to initalize the the iterators returned
250         *  by the begin() and end().
251         */
252        const_iterator (const Map& pmap, const KeyIt& pit)
253          : map(&pmap), it(pit) {}
254
255      public:
256
257        /** Default constructor.
258         */
259        const_iterator() {}
260
261        /** Constructor to convert iterator to const_iterator.
262         */
263        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
264     
265        typedef extended_pair<const KeyType&, const KeyType&,
266          const Value&, const Value&> Reference;
267
268        /** Dereference operator for map.
269         */     
270        Reference operator*() {
271          return Reference(it, (*map)[it]);
272        }
273
274
275        class Pointer {
276          friend class const_iterator;
277        private:
278          Reference data;
279          Pointer(const KeyType& key, const Value& val) : data(key, val) {}
280        public:
281          Reference* operator->() {return &data;}
282        };
283
284        /** Arrow operator for map.
285         */     
286        Pointer operator->() {
287          return Pointer(it, ((*map)[it]));
288        }
289
290        /** The pre increment operator of the map.
291         */
292        const_iterator& operator++() {
293          ++it;
294          return *this;
295        }
296
297        /** The post increment operator of the map.
298         */
299        const_iterator operator++(int) {
300          const_iterator tmp(it);
301          ++it;
302          return tmp;
303        }
304
305        /** The equality operator of the map.
306         */
307        bool operator==(const_iterator p_it) {
308          return p_it.it == it;
309        }
310       
311        /** The not-equality operator of the map.
312         */
313        bool operator!=(const_iterator p_it) {
314          return !(*this == p_it);
315        }
316       
317
318      private:
319        const Map* map;
320        KeyIt it;
321      };
322
323      /** Returns the begin const_iterator of the map.
324       */
325      const_iterator begin() const {
326        return const_iterator(*this, KeyIt(*getGraph()));
327      }
328
329      /** Returns the end const_iterator of the map.
330       */
331      const_iterator end() const {
332        return const_iterator(*this, INVALID);
333      }
334
335      private:
336               
337      Container container;
338
339    };
340               
341  };
342
343 
344  /// @}
345 
346
347}
348
349#endif
Note: See TracBrowser for help on using the repository browser.