COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/vector_map_factory.h @ 1021:fd1d073b6557

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

hugo -> lemon

File size: 7.2 KB
RevLine 
[703]1// -*- c++ -*-
[571]2#ifndef VECTOR_MAP_H
3#define VECTOR_MAP_H
4
5#include <vector>
6
[702]7#include "extended_pair.h"
8
[921]9namespace lemon {
[700]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   */
[571]18       
[627]19  template <typename MapRegistry>
[700]20  class VectorMapFactory {
21  public:
[627]22               
[700]23    /// The graph type of the maps.
[627]24    typedef typename MapRegistry::Graph Graph;
[700]25    /// The key type of the maps.
[627]26    typedef typename MapRegistry::Key Key;
[700]27    /// The iterator to iterate on the keys.
[627]28    typedef typename MapRegistry::KeyIt KeyIt;
29
[700]30    /// The MapBase of the Map which imlements the core regisitry function.
[627]31    typedef typename MapRegistry::MapBase MapBase;
[698]32
[627]33               
[700]34    /** The template Map type.
35     */
[627]36    template <typename V>
[700]37    class Map : public MapBase {
38    public:
39
40      /// The value type of the map.
[627]41      typedef V Value;
[700]42
43      typedef std::vector<Value> Container;     
44
45      /** Default constructor for the map.
46       */
[627]47      Map() {}
[700]48               
49      /** Graph and Registry initialized map constructor.
50       */
51      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
[627]52        init();
53      }
[700]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)) {
[703]59          int id = getGraph->id(it);
60          if (id >= container.size) {
61            container.resize(id + 1);
62          }
63          set(it, v);
[700]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)) {
[703]72            int id = getGraph->id(it);
73            if (id >= container.size) {
74              container.resize(id + 1);
75            }
[700]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)) {
[703]90            int id = getGraph->id(it);
91            if (id >= container.size) {
92              container.resize(id + 1);
93            }
[700]94            set(it, copy[it]);
95          }
96        }
97      }
98
99      /** The destructor of the map.
100       */
[627]101      virtual ~Map() {
102      }
[700]103               
104      /**
105       * The subscript operator. The map can be subscripted by the
106       * actual keys of the graph.
107       */
[698]108      typename Container::reference operator[](const Key& key) {
[700]109        int id = getGraph()->id(key);
[627]110        return container[id];
111      }
[571]112               
[700]113      /**
114       * The const subscript operator. The map can be subscripted by the
115       * actual keys of the graph.
116       */
[698]117      typename Container::const_reference operator[](const Key& key) const {
[700]118        int id = getGraph()->id(key);
[627]119        return container[id];
120      }
[700]121
122      /** Setter function of the map. Equivalent with map[key] = val.
123       *  This is a compatibility feature with the not dereferable maps.
124       */
[627]125      void set(const Key& key, const Value& val) {
[700]126        int id = getGraph()->id(key);
[627]127        container[id] = val;
128      }
129               
[700]130      /** Add a new key to the map. It called by the map registry.
131       */
[627]132      void add(const Key& key) {
[700]133        int id = getGraph()->id(key);
[627]134        if (id >= container.size()) {
135          container.resize(id + 1);
136        }
137      }
138               
[700]139      /** Erease a key from the map. It called by the map registry.
140       */
[627]141      void erase(const Key& key) {}
[698]142
[700]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;
[698]149      private:
150
[700]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
[698]156      public:
[700]157
158        /** Default constructor.
159         */
[698]160        iterator() {}
[700]161
[703]162        typedef extended_pair<const Key&, const Key&,
163                              Value&, Value&> Reference;
164
[700]165        /** Dereference operator for map.
166         */     
[703]167        Reference operator*() {
168          return Reference(it, (*map)[it]);
[698]169        }
170
[702]171        class Pointer {
172          friend class iterator;
173        private:
[703]174          Reference data;
[702]175          Pointer(const Key& key, Value& val) : data(key, val) {}
176        public:
[703]177          Reference* operator->() {return &data;}
[702]178        };
179
[700]180        /** Arrow operator for map.
181         */     
[702]182        Pointer operator->() {
183          return Pointer(it, ((*map)[it]));
[700]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        }
[702]212
[700]213       
[698]214      private:
[700]215        Map* map;
[698]216        KeyIt it;
217      };
218
[700]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;
[627]234      private:
[700]235
236        /** Private constructor to initalize the the iterators returned
237         *  by the begin() and end().
238         */
[703]239        const_iterator (const Map& pmap, const KeyIt& pit)
240          : map(&pmap), it(pit) {}
[700]241
242      public:
243
244        /** Default constructor.
245         */
246        const_iterator() {}
247
248        /** Constructor to convert iterator to const_iterator.
249         */
[703]250        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
[700]251     
[703]252        typedef extended_pair<const Key&, const Key&,
253          const Value&, const Value&> Reference;
254
[700]255        /** Dereference operator for map.
256         */     
[703]257        Reference operator*() {
258          return Reference(it, (*map)[it]);
[700]259        }
260
[703]261
[702]262        class Pointer {
263          friend class const_iterator;
264        private:
[703]265          Reference data;
[702]266          Pointer(const Key& key, const Value& val) : data(key, val) {}
267        public:
[703]268          Reference* operator->() {return &data;}
[702]269        };
[703]270
[700]271        /** Arrow operator for map.
272         */     
[703]273        Pointer operator->() {
274          return Pointer(it, ((*map)[it]));
[700]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       
[702]304
[700]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:
[571]323               
[627]324      Container container;
[698]325
[627]326    };
[571]327               
[627]328  };
[700]329
[571]330}
331
332#endif
Note: See TracBrowser for help on using the repository browser.