COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map.h @ 873:f3a30fda2e49

Last change on this file since 873:f3a30fda2e49 was 844:9bf990cb066d, checked in by Balazs Dezso, 20 years ago

Bug fix in the symmetric maps.
Faster map initialization.
Iterators and Containers STL compatible.

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