COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/array_map_factory.h @ 702:4207f82a1778

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