COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map_factory.h @ 783:81bf2d766164

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