COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/array_map.h @ 898:c46cfb2651ec

Last change on this file since 898:c46cfb2651ec was 897:ef09eee53b09, checked in by Balazs Dezso, 20 years ago

The default constructors are removed from the maps.
The ArrayMap? is the map structure of the graphs.

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