COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/vector_map_factory.h @ 963:5a7556e9e340

Last change on this file since 963:5a7556e9e340 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

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