COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/array_map.h @ 938:70e2886211d5

Last change on this file since 938:70e2886211d5 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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