COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/vector_map_factory.h @ 702:4207f82a1778

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