COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/vector_map_factory.h @ 700:236117f60eee

Last change on this file since 700:236117f60eee was 700:236117f60eee, checked in by Balazs Dezso, 16 years ago

* empty log message *

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