COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/array_map_factory.h @ 965:1e16b8dac159

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

hugo -> lemon

File size: 7.6 KB
Line 
1// -*- c++ -*-
2#ifndef ARRAY_MAP_H
3#define ARRAY_MAP_H
4
5#include <memory>
6
7#include "extended_pair.h"
8
9namespace lemon {
10       
11  template <typename MapRegistry> class ArrayMapFactory {
12               
13  public:
14               
15    typedef typename MapRegistry::Graph Graph;
16    typedef typename MapRegistry::Key Key;
17    typedef typename MapRegistry::KeyIt KeyIt;
18
19    typedef typename MapRegistry::MapBase MapBase;
20               
21    template <typename V, typename A = std::allocator<V> >
22    class Map : public MapBase {
23   
24      public:
25
26      typedef V Value;
27      typedef A Allocator;
28
29       
30      Map() : values(0), capacity(0) {}
31                       
32      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
33        allocate_memory();
34        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
35          int id = getGraph()->id(it);
36          allocator.construct(&(values[id]), Value());
37        }                                                               
38      }
39
40      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
41        allocate_memory();
42        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
43          int id = getGraph()->id(it);
44          allocator.construct(&(values[id]), v);
45        }                                                               
46      }
47
48      Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
49        capacity = copy.capacity;
50        if (capacity == 0) return;
51        values = allocator.allocate(capacity);
52        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
53          int id = getGraph()->id(it);
54          allocator.construct(&(values[id]), copy.values[id]);
55        }
56      }
57
58      template <typename CMap> Map(const CMap& copy)
59        : capacity(0), values(0), MapBase(copy) {
60        if (getGraph()) {
61          allocate_memory();
62          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
63            set(it, copy[it]);
64          }
65        }
66      }
67
68      Map& operator=(const Map& copy) {
69        if (&copy == this) return;
70        if (capacity != 0) {
71          destroy();
72          allocator.deallocate(values, capacity);
73        }
74        capacity = copy.capacity;
75        if (capacity == 0) return;
76        values = allocator.allocate(capacity);
77        for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
78          int id = getGraph()->id(it);
79          allocator.construct(&(values[id]), copy.values[id]);
80        }
81      }
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          allocate_memory();
90          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
91            set(it, copy[it]);
92          }
93        }
94      }
95                               
96      virtual ~Map() {
97        if (capacity != 0) {
98          destroy();
99          allocator.deallocate(values, capacity);
100        }
101      }
102       
103       
104      Value& operator[](const Key& key) {
105        int id = getGraph()->id(key);
106        return values[id];
107      }
108               
109      const Value& operator[](const Key& key) const {
110        int id = getGraph()->id(key);
111        return values[id];
112      }
113       
114      const Value& get(const Key& key) const {
115        int id = getGraph()->id(key);
116        return values[id];
117      }
118               
119      void set(const Key& key, const Value& val) {
120        int id = getGraph()->id(key);
121        values[id] = val;
122      }
123               
124      void add(const Key& key) {
125        int id = getGraph()->id(key);
126        if (id >= capacity) {
127          int new_capacity = (capacity == 0 ? 1 : capacity);
128          while (new_capacity <= id) {
129            new_capacity <<= 1;
130          }
131          Value* new_values = allocator.allocate(new_capacity);;
132          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
133            int jd = getGraph()->id(it);
134            if (id != jd) {
135              allocator.construct(&(new_values[jd]), values[jd]);
136              allocator.destroy(&(values[jd]));
137            }
138          }
139          if (capacity != 0) allocator.deallocate(values, capacity);
140          values = new_values;
141          capacity = new_capacity;
142        }
143        allocator.construct(&(values[id]), Value());
144      }
145               
146      void erase(const Key& key) {
147        int id = getGraph()->id(key);
148        allocator.destroy(&(values[id]));
149      }
150       
151      class iterator {
152        friend class Map;
153        friend class const_iterator;
154      private:
155
156        /** Private constructor to initalize the the iterators returned
157         *  by the begin() and end().
158         */
159        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
160
161      public:
162
163        /** Default constructor.
164         */
165        iterator() {}
166
167        typedef extended_pair<const Key&, const Key&,
168                              Value&, Value&> Reference;
169
170        /** Dereference operator for map.
171         */     
172        Reference operator*() {
173          return Reference(it, (*map)[it]);
174        }
175
176        class Pointer {
177          friend class iterator;
178        private:
179          Reference data;
180          Pointer(const Key& key, Value& val) : data(key, val) {}
181        public:
182          Reference* operator->() {return &data;}
183        };
184
185        /** Arrow operator for map.
186         */     
187        Pointer operator->() {
188          return Pointer(it, ((*map)[it]));
189        }
190
191        /** The pre increment operator of the map.
192         */
193        iterator& operator++() {
194          map->getGraph()->next(it);
195          return *this;
196        }
197
198        /** The post increment operator of the map.
199         */
200        iterator operator++(int) {
201          iterator tmp(it);
202          map.getGraph()->next(it);
203          return tmp;
204        }
205
206        /** The equality operator of the map.
207         */
208        bool operator==(const_iterator p_it) {
209          return p_it.it == it;
210        }
211       
212        /** The not-equality operator of the map.
213         */
214        bool operator!=(const_iterator p_it) {
215          return !(*this == p_it);
216        }
217
218       
219      private:
220        Map* map;
221        KeyIt it;
222      };
223
224      /** Returns the begin iterator of the map.
225       */
226      iterator begin() {
227        return iterator(*this, KeyIt(*getGraph()));
228      }
229
230      /** Returns the end iterator of the map.
231       */
232      iterator end() {
233        return iterator(*this, INVALID);
234      }
235
236      class const_iterator {
237        friend class Map;
238        friend class iterator;
239      private:
240
241        /** Private constructor to initalize the the iterators returned
242         *  by the begin() and end().
243         */
244        const_iterator (const Map& pmap, const KeyIt& pit)
245          : map(&pmap), it(pit) {}
246
247      public:
248
249        /** Default constructor.
250         */
251        const_iterator() {}
252
253        /** Constructor to convert iterator to const_iterator.
254         */
255        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
256     
257        typedef extended_pair<const Key&, const Key&,
258          const Value&, const Value&> Reference;
259
260        /** Dereference operator for map.
261         */     
262        Reference operator*() {
263          return Reference(it, (*map)[it]);
264        }
265
266
267        class Pointer {
268          friend class const_iterator;
269        private:
270          Reference data;
271          Pointer(const Key& key, const Value& val) : data(key, val) {}
272        public:
273          Reference* operator->() {return &data;}
274        };
275
276        /** Arrow operator for map.
277         */     
278        Pointer operator->() {
279          return Pointer(it, ((*map)[it]));
280        }
281
282        /** The pre increment operator of the map.
283         */
284        const_iterator& operator++() {
285          map->getGraph()->next(it);
286          return *this;
287        }
288
289        /** The post increment operator of the map.
290         */
291        const_iterator operator++(int) {
292          const_iterator tmp(it);
293          map->getGraph()->next(it);
294          return tmp;
295        }
296
297        /** The equality operator of the map.
298         */
299        bool operator==(const_iterator p_it) {
300          return p_it.it == it;
301        }
302       
303        /** The not-equality operator of the map.
304         */
305        bool operator!=(const_iterator p_it) {
306          return !(*this == p_it);
307        }
308       
309
310      private:
311        const Map* map;
312        KeyIt it;
313      };
314
315      /** Returns the begin const_iterator of the map.
316       */
317      const_iterator begin() const {
318        return const_iterator(*this, KeyIt(*getGraph()));
319      }
320
321      /** Returns the end const_iterator of the map.
322       */
323      const_iterator end() const {
324        return const_iterator(*this, INVALID);
325      }
326
327    private:
328     
329      void allocate_memory() {
330        int max_id = -1;
331        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
332          int id = getGraph()->id(it);
333          if (id > max_id) {
334            max_id = id;
335          }                     
336        }
337        if (max_id == -1) {
338          capacity = 0;
339          values = 0;
340          return;
341        }
342        capacity = 1;
343        while (capacity <= max_id) {
344          capacity <<= 1;
345        }
346        values = allocator.allocate(capacity); 
347      }     
348      int capacity;
349      Value* values;
350      Allocator allocator;
351    };         
352  };
353}
354
355#endif
Note: See TracBrowser for help on using the repository browser.