COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/array_map.h @ 978:175cf8c3a994

Last change on this file since 978:175cf8c3a994 was 978:175cf8c3a994, checked in by Mihaly Barasz, 16 years ago

"make check" pass under gcc-3.4.3

File size: 10.6 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
24///\ingroup graphmaps
25///\file
26///\brief Graph maps that construates and destruates
27///their elements dynamically.
28
29namespace lemon {
30
31
32  /// \addtogroup graphmaps
33  /// @{
34       
35  /** The ArrayMap template class is graph map structure what
36   *  automatically updates the map when a key is added to or erased from
37   *  the map. This map factory uses the allocators to implement
38   *  the container functionality.
39   *
40   *  The template parameter is the MapRegistry that the maps
41   *  will belong to and the ValueType.
42   */
43
44  template <typename _Graph,
45            typename _Item,
46            typename _ItemIt,
47            typename _IdMap,
48            typename _Value>
49  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
50
51  public:
52               
53    /// The graph type of the maps.
54    typedef _Graph Graph;
55    /// The key type of the maps.
56    typedef _Item KeyType;
57
58    typedef AlterationObserverRegistry<_Item> Registry;
59
60  private:
61    /// The iterator to iterate on the keys.
62    typedef _ItemIt KeyIt;
63
64    typedef _IdMap IdMap;
65
66    typedef _Value Value;
67
68    /// The MapBase of the Map which imlements the core regisitry function.
69    typedef typename Registry::ObserverBase Parent;
70               
71   
72  public:
73
74    /// The value type of the map.
75    typedef Value ValueType;
76    /// The reference type of the map;
77    typedef Value& ReferenceType;
78    /// The pointer type of the map;
79    typedef Value* PointerType;
80
81    /// The const value type of the map.
82    typedef const Value ConstValueType;
83    /// The const reference type of the map;
84    typedef const Value& ConstReferenceType;
85    /// The pointer type of the map;
86    typedef const Value* ConstPointerType;
87
88
89  private:
90    typedef std::allocator<Value> Allocator;
91
92
93  public:
94
95    /** Graph and Registry initialized map constructor.
96     */
97    ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
98      attach(_r);
99      allocate_memory();
100      for (KeyIt it(*graph); it != INVALID; ++it) {
101        int id = IdMap(*graph)[it];
102        allocator.construct(&(values[id]), Value());
103      }                                                         
104    }
105
106    /// Constructor to use default value to initialize the map.
107
108    /// It constrates a map and initialize all of the the map.
109
110    ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
111      attach(_r);
112      allocate_memory();
113      for (KeyIt it(*graph); it != INVALID; ++it) {
114        int id = IdMap(*graph)[it];
115        allocator.construct(&(values[id]), _v);
116      }                                                         
117    }
118
119    /** Constructor to copy a map of the same map type.
120     */
121    ArrayMap(const ArrayMap& copy) {
122      if (copy.attached()) {
123        attach(*copy.getRegistry());
124      }
125      capacity = copy.capacity;
126      if (capacity == 0) return;
127      values = allocator.allocate(capacity);
128      for (KeyIt it(*graph); it != INVALID; ++it) {
129        int id = IdMap(*graph)[it];
130        allocator.construct(&(values[id]), copy.values[id]);
131      }
132    }
133
134    using Parent::attach;
135    using Parent::detach;
136    using Parent::attached;
137
138    /** Assign operator to copy a map of the same map type.
139     */
140    ArrayMap& operator=(const ArrayMap& copy) {
141      if (&copy == this) return *this;
142     
143      if (graph != copy.graph) {
144        if (attached()) {
145          clear();
146          detach();
147        }
148        if (copy.attached()) {
149          attach(*copy.getRegistry());
150        }
151        capacity = copy.capacity;
152        if (capacity == 0) return *this;
153        values = allocator.allocate(capacity);     
154      }
155
156      for (KeyIt it(*graph); it != INVALID; ++it) {
157        int id = IdMap(*graph)[it];
158        allocator.construct(&(values[id]), copy.values[id]);
159      }
160
161      return *this;
162    }
163
164    /** The destructor of the map.
165     */
166    virtual ~ArrayMap() {     
167      if (attached()) {
168        clear();
169        detach();
170      }
171    }
172       
173       
174    /**
175     * The subscript operator. The map can be subscripted by the
176     * actual keys of the graph.
177     */
178    ReferenceType operator[](const KeyType& key) {
179      int id = IdMap(*graph)[key];
180      return values[id];
181    }
182               
183    /**
184     * The const subscript operator. The map can be subscripted by the
185     * actual keys of the graph.
186     */
187    ConstReferenceType operator[](const KeyType& key) const {
188      int id = IdMap(*graph)[key];
189      return values[id];
190    }
191       
192    /** Setter function of the map. Equivalent with map[key] = val.
193     *  This is a compatibility feature with the not dereferable maps.
194     */
195    void set(const KeyType& key, const ValueType& val) {
196      (*this)[key] = val;
197    }
198               
199    /** Add a new key to the map. It called by the map registry.
200     */
201    void add(const KeyType& key) {
202      int id = IdMap(*graph)[key];
203      if (id >= capacity) {
204        int new_capacity = (capacity == 0 ? 1 : capacity);
205        while (new_capacity <= id) {
206          new_capacity <<= 1;
207        }
208        Value* new_values = allocator.allocate(new_capacity);
209        for (KeyIt it(*graph); it != INVALID; ++it) {
210          int jd = IdMap(*graph)[it];
211          if (id != jd) {
212            allocator.construct(&(new_values[jd]), values[jd]);
213            allocator.destroy(&(values[jd]));
214          }
215        }
216        if (capacity != 0) allocator.deallocate(values, capacity);
217        values = new_values;
218        capacity = new_capacity;
219      }
220      allocator.construct(&(values[id]), Value());
221    }
222               
223    /** Erase a key from the map. It called by the map registry.
224     */
225    void erase(const KeyType& key) {
226      int id = IdMap(*graph)[key];
227      allocator.destroy(&(values[id]));
228    }
229
230    void build() {
231      allocate_memory();
232      for (KeyIt it(*graph); it != INVALID; ++it) {
233        int id = IdMap(*graph)[it];
234        allocator.construct(&(values[id]), Value());
235      }                                                         
236    }
237
238    void clear() {     
239      if (capacity != 0) {
240        for (KeyIt it(*graph); it != INVALID; ++it) {
241          int id = IdMap(*graph)[it];
242          allocator.destroy(&(values[id]));
243        }                                                               
244        allocator.deallocate(values, capacity);
245        capacity = 0;
246      }
247    }
248
249//     /// The stl compatible pair iterator of the map.
250//     typedef MapIterator<ArrayMap> Iterator;
251//     /// The stl compatible const pair iterator of the map.
252//     typedef MapConstIterator<ArrayMap> ConstIterator;
253
254//     /** Returns the begin iterator of the map.
255//      */
256//     Iterator begin() {
257//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
258//     }
259
260//     /** Returns the end iterator of the map.
261//      */
262//     Iterator end() {
263//       return Iterator(*this, INVALID);
264//     }
265
266//     /** Returns the begin ConstIterator of the map.
267//      */
268//     ConstIterator begin() const {
269//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
270//     }
271
272//     /** Returns the end const_iterator of the map.
273//      */
274//     ConstIterator end() const {
275//       return ConstIterator(*this, INVALID);
276//     }
277
278//     /// The KeySet of the Map.
279//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
280
281//     /// KeySet getter function.
282//     ConstKeySet keySet() const {
283//       return ConstKeySet(*this);
284//     }
285
286//     /// The ConstValueSet of the Map.
287//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
288
289//     /// ConstValueSet getter function.
290//     ConstValueSet valueSet() const {
291//       return ConstValueSet(*this);
292//     }
293
294//     /// The ValueSet of the Map.
295//     typedef MapValueSet<ArrayMap> ValueSet;
296
297//     /// ValueSet getter function.
298//     ValueSet valueSet() {
299//       return ValueSet(*this);
300//     }
301
302  private:
303     
304    void allocate_memory() {
305      int max_id = IdMap(*graph).maxId();
306      if (max_id == -1) {
307        capacity = 0;
308        values = 0;
309        return;
310      }
311      capacity = 1;
312      while (capacity <= max_id) {
313        capacity <<= 1;
314      }
315      values = allocator.allocate(capacity);   
316    }     
317
318    const Graph* graph;
319    int capacity;
320    Value* values;
321    Allocator allocator;
322
323  public:
324//     // STL  compatibility typedefs.
325//     typedef Iterator iterator;
326//     typedef ConstIterator const_iterator;
327//     typedef typename Iterator::PairValueType value_type;
328//     typedef typename Iterator::KeyType key_type;
329//     typedef typename Iterator::ValueType data_type;
330//     typedef typename Iterator::PairReferenceType reference;
331//     typedef typename Iterator::PairPointerType pointer;
332//     typedef typename ConstIterator::PairReferenceType const_reference;
333//     typedef typename ConstIterator::PairPointerType const_pointer;
334//     typedef int difference_type;             
335  };           
336
337  template <typename _Base>
338  class ArrayMappableGraphExtender : public _Base {
339  public:
340
341    typedef ArrayMappableGraphExtender<_Base> Graph;
342    typedef _Base Parent;
343
344    typedef typename Parent::Node Node;
345    typedef typename Parent::NodeIt NodeIt;
346    typedef typename Parent::NodeIdMap NodeIdMap;
347    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
348
349    typedef typename Parent::Edge Edge;
350    typedef typename Parent::EdgeIt EdgeIt;
351    typedef typename Parent::EdgeIdMap EdgeIdMap;
352    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
353
354   
355
356    template <typename _Value>
357    class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
358    public:
359      typedef ArrayMappableGraphExtender<_Base> Graph;
360
361      typedef typename Graph::Node Node;
362      typedef typename Graph::NodeIt NodeIt;
363      typedef typename Graph::NodeIdMap NodeIdMap;
364
365      typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
366
367      typedef typename Parent::Graph Graph;
368      typedef typename Parent::Value Value;
369
370      NodeMap(const Graph& g)
371        : Parent(g, g.getNodeObserverRegistry()) {}
372      NodeMap(const Graph& g, const Value& v)
373        : Parent(g, g.getNodeObserverRegistry(), v) {}
374
375    };
376
377    template <typename _Value>
378    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
379    public:
380      typedef ArrayMappableGraphExtender<_Base> Graph;
381
382      typedef typename Graph::Edge Edge;
383      typedef typename Graph::EdgeIt EdgeIt;
384      typedef typename Graph::EdgeIdMap EdgeIdMap;
385
386      typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
387
388      typedef typename Parent::Graph Graph;
389      typedef typename Parent::Value Value;
390
391      EdgeMap(const Graph& g)
392        : Parent(g, g.getEdgeObserverRegistry()) {}
393      EdgeMap(const Graph& g, const Value& v)
394        : Parent(g, g.getEdgeObserverRegistry(), v) {}
395
396    };
397   
398  };
399
400/// @}
401
402}
403
404#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.