COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map.h @ 822:88226d9fe821

Last change on this file since 822:88226d9fe821 was 822:88226d9fe821, checked in by Balazs Dezso, 20 years ago

The MapFactories? have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.

File size: 7.4 KB
Line 
1// -*- c++ -*-
2#ifndef ARRAY_MAP_H
3#define ARRAY_MAP_H
4
5#include <memory>
6
7#include <hugo/map_iterator.h>
8
9///\ingroup graphmaps
10///\file
11///\brief Graph maps that construates and destruates
12///their elements dynamically.
13
14namespace hugo {
15
16
17  /// \addtogroup graphmaps
18  /// @{
19       
20  /** The ArrayMap template class is graph map structure what
21   *  automatically updates the map when a key is added to or erased from
22   *  the map. This map factory uses the allocators to implement
23   *  the container functionality.
24   *
25   *  The template parameter is the MapRegistry that the maps
26   *  will belong to and the ValueType.
27   */
28
29  template <typename MapRegistry, typename Value>
30  class ArrayMap : public MapRegistry::MapBase {
31               
32  public:
33               
34    /// The graph type of the maps.
35    typedef typename MapRegistry::Graph Graph;
36    /// The key type of the maps.
37    typedef typename MapRegistry::KeyType KeyType;
38    /// The iterator to iterate on the keys.
39    typedef typename MapRegistry::KeyIt KeyIt;
40
41    /// The MapBase of the Map which imlements the core regisitry function.
42    typedef typename MapRegistry::MapBase MapBase;
43               
44   
45  public:
46
47    /// The value type of the map.
48    typedef Value ValueType;
49    /// The reference type of the map;
50    typedef Value& ReferenceType;
51    /// The pointer type of the map;
52    typedef Value* PointerType;
53
54    /// The const value type of the map.
55    typedef const Value ConstValueType;
56    /// The const reference type of the map;
57    typedef const Value& ConstReferenceType;
58    /// The pointer type of the map;
59    typedef const Value* ConstPointerType;
60
61
62    typedef std::allocator<Value> Allocator;
63
64       
65    /** Default constructor for the map.
66     */
67    ArrayMap() : values(0), capacity(0) {}
68                       
69    /** Graph and Registry initialized map constructor.
70     */
71    ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
72      allocate_memory();
73      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
74        int id = MapBase::getGraph()->id(it);
75        allocator.construct(&(values[id]), Value());
76      }                                                         
77    }
78
79    /** Constructor to use default value to initialize the map.
80     */
81    ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
82      : MapBase(g, r) {
83      allocate_memory();
84      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
85        int id = MapBase::getGraph()->id(it);
86        allocator.construct(&(values[id]), v);
87      }                                                         
88    }
89
90    /** Constructor to copy a map of the same map type.
91     */
92    ArrayMap(const ArrayMap& copy) : MapBase(*copy.graph, *copy.registry) {
93      capacity = copy.capacity;
94      if (capacity == 0) return;
95      values = allocator.allocate(capacity);
96      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
97        int id = MapBase::getGraph()->id(it);
98        allocator.construct(&(values[id]), copy.values[id]);
99      }
100    }
101
102    /** Constructor to copy a map of an other map type.
103     */
104    template <typename CMap> ArrayMap(const CMap& copy)
105      : MapBase(copy), capacity(0), values(0) {
106      if (MapBase::getGraph()) {
107        allocate_memory();
108        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
109          set(it, copy[it]);
110        }
111      }
112    }
113
114    /** Assign operator to copy a map of the same map type.
115     */
116    ArrayMap& operator=(const ArrayMap& copy) {
117      if (&copy == this) return *this;
118      if (capacity != 0) {
119        MapBase::destroy();
120        allocator.deallocate(values, capacity);
121      }
122      capacity = copy.capacity;
123      if (capacity == 0) return *this;
124      values = allocator.allocate(capacity);
125      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
126        int id = MapBase::getGraph()->id(it);
127        allocator.construct(&(values[id]), copy.values[id]);
128      }
129      return *this;
130    }
131
132    /** Assign operator to copy a map an other map type.
133     */
134    template <typename CMap> ArrayMap& operator=(const CMap& copy) {
135      if (MapBase::getGraph()) {
136        MapBase::destroy();
137      }
138      MapBase::operator=(copy);
139      if (MapBase::getGraph()) {
140        allocate_memory();
141        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
142          set(it, copy[it]);
143        }
144      }
145      return *this;
146    }
147                               
148    /** The destructor of the map.
149     */
150    virtual ~ArrayMap() {
151      if (capacity != 0) {
152        MapBase::destroy();
153        allocator.deallocate(values, capacity);
154      }
155    }
156       
157       
158    /**
159     * The subscript operator. The map can be subscripted by the
160     * actual keys of the graph.
161     */
162    ReferenceType operator[](const KeyType& key) {
163      int id = MapBase::getGraph()->id(key);
164      return values[id];
165    }
166               
167    /**
168     * The const subscript operator. The map can be subscripted by the
169     * actual keys of the graph.
170     */
171    ConstReferenceType operator[](const KeyType& key) const {
172      int id = MapBase::getGraph()->id(key);
173      return values[id];
174    }
175       
176    /** Setter function of the map. Equivalent with map[key] = val.
177     *  This is a compatibility feature with the not dereferable maps.
178     */
179    void set(const KeyType& key, const ValueType& val) {
180      int id = MapBase::getGraph()->id(key);
181      values[id] = val;
182    }
183               
184    /** Add a new key to the map. It called by the map registry.
185     */
186    void add(const KeyType& key) {
187      int id = MapBase::getGraph()->id(key);
188      if (id >= capacity) {
189        int new_capacity = (capacity == 0 ? 1 : capacity);
190        while (new_capacity <= id) {
191          new_capacity <<= 1;
192        }
193        Value* new_values = allocator.allocate(new_capacity);;
194        for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
195          int jd = MapBase::getGraph()->id(it);
196          if (id != jd) {
197            allocator.construct(&(new_values[jd]), values[jd]);
198            allocator.destroy(&(values[jd]));
199          }
200        }
201        if (capacity != 0) allocator.deallocate(values, capacity);
202        values = new_values;
203        capacity = new_capacity;
204      }
205      allocator.construct(&(values[id]), Value());
206    }
207               
208    /** Erase a key from the map. It called by the map registry.
209     */
210    void erase(const KeyType& key) {
211      int id = MapBase::getGraph()->id(key);
212      allocator.destroy(&(values[id]));
213    }
214
215    /** Clear the data structure.
216     */
217    void clear() {     
218      if (capacity != 0) {
219        MapBase::destroy();
220        allocator.deallocate(values, capacity);
221        capacity = 0;
222      }
223    }
224
225    /// The stl compatible pair iterator of the map.
226    typedef MapIterator<ArrayMap> Iterator;
227    /// The stl compatible const pair iterator of the map.
228    typedef MapConstIterator<ArrayMap> ConstIterator;
229
230    /** Returns the begin iterator of the map.
231     */
232    Iterator begin() {
233      return Iterator(*this, KeyIt(*MapBase::getGraph()));
234    }
235
236    /** Returns the end iterator of the map.
237     */
238    Iterator end() {
239      return Iterator(*this, INVALID);
240    }
241
242    /** Returns the begin ConstIterator of the map.
243     */
244    ConstIterator begin() const {
245      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
246    }
247
248    /** Returns the end const_iterator of the map.
249     */
250    ConstIterator end() const {
251      return ConstIterator(*this, INVALID);
252    }
253
254  private:
255     
256    void allocate_memory() {
257      int max_id = -1;
258      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
259        int id = MapBase::getGraph()->id(it);
260        if (id > max_id) {
261          max_id = id;
262        }                       
263      }
264      if (max_id == -1) {
265        capacity = 0;
266        values = 0;
267        return;
268      }
269      capacity = 1;
270      while (capacity <= max_id) {
271        capacity <<= 1;
272      }
273      values = allocator.allocate(capacity);   
274    }     
275
276    int capacity;
277    Value* values;
278    Allocator allocator;
279  };           
280
281/// @}
282
283}
284
285#endif
Note: See TracBrowser for help on using the repository browser.