COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/array_map.h @ 946:c94ef40a22ce

Last change on this file since 946:c94ef40a22ce was 946:c94ef40a22ce, checked in by Mihaly Barasz, 20 years ago

The graph_factory branch (@ 1321) has been merged to trunk.

File size: 10.5 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    /** Assign operator to copy a map of the same map type.
135     */
136    ArrayMap& operator=(const ArrayMap& copy) {
137      if (&copy == this) return *this;
138     
139      if (graph != copy.graph) {
140        if (attached()) {
141          clear();
142          detach();
143        }
144        if (copy.attached()) {
145          attach(*copy.getRegistry());
146        }
147        capacity = copy.capacity;
148        if (capacity == 0) return *this;
149        values = allocator.allocate(capacity);     
150      }
151
152      for (KeyIt it(*graph); it != INVALID; ++it) {
153        int id = IdMap(*graph)[it];
154        allocator.construct(&(values[id]), copy.values[id]);
155      }
156
157      return *this;
158    }
159
160    /** The destructor of the map.
161     */
162    virtual ~ArrayMap() {     
163      if (attached()) {
164        clear();
165        detach();
166      }
167    }
168       
169       
170    /**
171     * The subscript operator. The map can be subscripted by the
172     * actual keys of the graph.
173     */
174    ReferenceType operator[](const KeyType& key) {
175      int id = IdMap(*graph)[key];
176      return values[id];
177    }
178               
179    /**
180     * The const subscript operator. The map can be subscripted by the
181     * actual keys of the graph.
182     */
183    ConstReferenceType operator[](const KeyType& key) const {
184      int id = IdMap(*graph)[key];
185      return values[id];
186    }
187       
188    /** Setter function of the map. Equivalent with map[key] = val.
189     *  This is a compatibility feature with the not dereferable maps.
190     */
191    void set(const KeyType& key, const ValueType& val) {
192      (*this)[key] = val;
193    }
194               
195    /** Add a new key to the map. It called by the map registry.
196     */
197    void add(const KeyType& key) {
198      int id = IdMap(*graph)[key];
199      if (id >= capacity) {
200        int new_capacity = (capacity == 0 ? 1 : capacity);
201        while (new_capacity <= id) {
202          new_capacity <<= 1;
203        }
204        Value* new_values = allocator.allocate(new_capacity);
205        for (KeyIt it(*graph); it != INVALID; ++it) {
206          int jd = IdMap(*graph)[it];
207          if (id != jd) {
208            allocator.construct(&(new_values[jd]), values[jd]);
209            allocator.destroy(&(values[jd]));
210          }
211        }
212        if (capacity != 0) allocator.deallocate(values, capacity);
213        values = new_values;
214        capacity = new_capacity;
215      }
216      allocator.construct(&(values[id]), Value());
217    }
218               
219    /** Erase a key from the map. It called by the map registry.
220     */
221    void erase(const KeyType& key) {
222      int id = IdMap(*graph)[key];
223      allocator.destroy(&(values[id]));
224    }
225
226    void build() {
227      allocate_memory();
228      for (KeyIt it(*graph); it != INVALID; ++it) {
229        int id = IdMap(*graph)[it];
230        allocator.construct(&(values[id]), Value());
231      }                                                         
232    }
233
234    void clear() {     
235      if (capacity != 0) {
236        for (KeyIt it(*graph); it != INVALID; ++it) {
237          int id = IdMap(*graph)[it];
238          allocator.destroy(&(values[id]));
239        }                                                               
240        allocator.deallocate(values, capacity);
241        capacity = 0;
242      }
243    }
244
245//     /// The stl compatible pair iterator of the map.
246//     typedef MapIterator<ArrayMap> Iterator;
247//     /// The stl compatible const pair iterator of the map.
248//     typedef MapConstIterator<ArrayMap> ConstIterator;
249
250//     /** Returns the begin iterator of the map.
251//      */
252//     Iterator begin() {
253//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
254//     }
255
256//     /** Returns the end iterator of the map.
257//      */
258//     Iterator end() {
259//       return Iterator(*this, INVALID);
260//     }
261
262//     /** Returns the begin ConstIterator of the map.
263//      */
264//     ConstIterator begin() const {
265//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
266//     }
267
268//     /** Returns the end const_iterator of the map.
269//      */
270//     ConstIterator end() const {
271//       return ConstIterator(*this, INVALID);
272//     }
273
274//     /// The KeySet of the Map.
275//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
276
277//     /// KeySet getter function.
278//     ConstKeySet keySet() const {
279//       return ConstKeySet(*this);
280//     }
281
282//     /// The ConstValueSet of the Map.
283//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
284
285//     /// ConstValueSet getter function.
286//     ConstValueSet valueSet() const {
287//       return ConstValueSet(*this);
288//     }
289
290//     /// The ValueSet of the Map.
291//     typedef MapValueSet<ArrayMap> ValueSet;
292
293//     /// ValueSet getter function.
294//     ValueSet valueSet() {
295//       return ValueSet(*this);
296//     }
297
298  private:
299     
300    void allocate_memory() {
301      int max_id = IdMap(*graph).maxId();
302      if (max_id == -1) {
303        capacity = 0;
304        values = 0;
305        return;
306      }
307      capacity = 1;
308      while (capacity <= max_id) {
309        capacity <<= 1;
310      }
311      values = allocator.allocate(capacity);   
312    }     
313
314    const Graph* graph;
315    int capacity;
316    Value* values;
317    Allocator allocator;
318
319  public:
320//     // STL  compatibility typedefs.
321//     typedef Iterator iterator;
322//     typedef ConstIterator const_iterator;
323//     typedef typename Iterator::PairValueType value_type;
324//     typedef typename Iterator::KeyType key_type;
325//     typedef typename Iterator::ValueType data_type;
326//     typedef typename Iterator::PairReferenceType reference;
327//     typedef typename Iterator::PairPointerType pointer;
328//     typedef typename ConstIterator::PairReferenceType const_reference;
329//     typedef typename ConstIterator::PairPointerType const_pointer;
330//     typedef int difference_type;             
331  };           
332
333  template <typename _Base>
334  class ArrayMappableGraphExtender : public _Base {
335  public:
336
337    typedef ArrayMappableGraphExtender<_Base> Graph;
338    typedef _Base Parent;
339
340    typedef typename Parent::Node Node;
341    typedef typename Parent::NodeIt NodeIt;
342    typedef typename Parent::NodeIdMap NodeIdMap;
343    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
344
345    typedef typename Parent::Edge Edge;
346    typedef typename Parent::EdgeIt EdgeIt;
347    typedef typename Parent::EdgeIdMap EdgeIdMap;
348    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
349
350   
351
352    template <typename _Value>
353    class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
354    public:
355      typedef ArrayMappableGraphExtender<_Base> Graph;
356
357      typedef typename Graph::Node Node;
358      typedef typename Graph::NodeIt NodeIt;
359      typedef typename Graph::NodeIdMap NodeIdMap;
360
361      typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
362
363      typedef typename Parent::Graph Graph;
364      typedef typename Parent::Value Value;
365
366      NodeMap(const Graph& g)
367        : Parent(g, g.getNodeObserverRegistry()) {}
368      NodeMap(const Graph& g, const Value& v)
369        : Parent(g, g.getNodeObserverRegistry(), v) {}
370
371    };
372
373    template <typename _Value>
374    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
375    public:
376      typedef ArrayMappableGraphExtender<_Base> Graph;
377
378      typedef typename Graph::Edge Edge;
379      typedef typename Graph::EdgeIt EdgeIt;
380      typedef typename Graph::EdgeIdMap EdgeIdMap;
381
382      typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
383
384      typedef typename Parent::Graph Graph;
385      typedef typename Parent::Value Value;
386
387      EdgeMap(const Graph& g)
388        : Parent(g, g.getEdgeObserverRegistry()) {}
389      EdgeMap(const Graph& g, const Value& v)
390        : Parent(g, g.getEdgeObserverRegistry(), v) {}
391
392    };
393   
394  };
395
396/// @}
397
398}
399
400#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.