COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map_factory.h @ 786:d7b3b13b9df6

Last change on this file since 786:d7b3b13b9df6 was 786:d7b3b13b9df6, checked in by Alpar Juttner, 16 years ago

Change 'Key' to 'KeyType?' (possibly temporarily).

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