COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/bits/array_map.h @ 62:4790635473ef

Last change on this file since 62:4790635473ef was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 17 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 9.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_ARRAY_MAP_H
20#define LEMON_BITS_ARRAY_MAP_H
21
22#include <memory>
23
24#include <lemon/bits/traits.h>
25#include <lemon/bits/alteration_notifier.h>
26#include <lemon/concept_check.h>
27#include <lemon/concepts/maps.h>
28
29/// \ingroup graphbits
30/// \file
31/// \brief Graph map based on the array storage.
32
33namespace lemon {
34
35  /// \ingroup graphbits
36  ///
37  /// \brief Graph map based on the array storage.
38  ///
39  /// The ArrayMap template class is graph map structure what
40  /// automatically updates the map when a key is added to or erased from
41  /// the map. This map uses the allocators to implement
42  /// the container functionality.
43  ///
44  /// The template parameters are the Graph the current Item type and
45  /// the Value type of the map.
46  template <typename _Graph, typename _Item, typename _Value>
47  class ArrayMap
48    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
49  public:
50    /// The graph type of the maps.
51    typedef _Graph Graph;
52    /// The item type of the map.
53    typedef _Item Item;
54    /// The reference map tag.
55    typedef True ReferenceMapTag;
56
57    /// The key type of the maps.
58    typedef _Item Key;
59    /// The value type of the map.
60    typedef _Value Value;
61
62    /// The const reference type of the map.
63    typedef const _Value& ConstReference;
64    /// The reference type of the map.
65    typedef _Value& Reference;
66
67    /// The notifier type.
68    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
69
70    /// The MapBase of the Map which imlements the core regisitry function.
71    typedef typename Notifier::ObserverBase Parent;
72               
73  private:
74    typedef std::allocator<Value> Allocator;
75
76  public:
77
78    /// \brief Graph initialized map constructor.
79    ///
80    /// Graph initialized map constructor.
81    explicit ArrayMap(const Graph& graph) {
82      Parent::attach(graph.notifier(Item()));
83      allocate_memory();
84      Notifier* nf = Parent::notifier();
85      Item it;
86      for (nf->first(it); it != INVALID; nf->next(it)) {
87        int id = nf->id(it);;
88        allocator.construct(&(values[id]), Value());
89      }                                                         
90    }
91
92    /// \brief Constructor to use default value to initialize the map.
93    ///
94    /// It constructs a map and initialize all of the the map.
95    ArrayMap(const Graph& graph, const Value& value) {
96      Parent::attach(graph.notifier(Item()));
97      allocate_memory();
98      Notifier* nf = Parent::notifier();
99      Item it;
100      for (nf->first(it); it != INVALID; nf->next(it)) {
101        int id = nf->id(it);;
102        allocator.construct(&(values[id]), value);
103      }                                                         
104    }
105
106    /// \brief Constructor to copy a map of the same map type.
107    ///
108    /// Constructor to copy a map of the same map type.     
109    ArrayMap(const ArrayMap& copy) : Parent() {
110      if (copy.attached()) {
111        attach(*copy.notifier());
112      }
113      capacity = copy.capacity;
114      if (capacity == 0) return;
115      values = allocator.allocate(capacity);
116      Notifier* nf = Parent::notifier();
117      Item it;
118      for (nf->first(it); it != INVALID; nf->next(it)) {
119        int id = nf->id(it);;
120        allocator.construct(&(values[id]), copy.values[id]);
121      }
122    }
123
124    /// \brief Assign operator.
125    ///
126    /// This operator assigns for each item in the map the
127    /// value mapped to the same item in the copied map. 
128    /// The parameter map should be indiced with the same
129    /// itemset because this assign operator does not change
130    /// the container of the map.
131    ArrayMap& operator=(const ArrayMap& cmap) {
132      return operator=<ArrayMap>(cmap);
133    }
134
135
136    /// \brief Template assign operator.
137    ///
138    /// The given parameter should be conform to the ReadMap
139    /// concecpt and could be indiced by the current item set of
140    /// the NodeMap. In this case the value for each item
141    /// is assigned by the value of the given ReadMap.
142    template <typename CMap>
143    ArrayMap& operator=(const CMap& cmap) {
144      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
145      const typename Parent::Notifier* nf = Parent::notifier();
146      Item it;
147      for (nf->first(it); it != INVALID; nf->next(it)) {
148        set(it, cmap[it]);
149      }
150      return *this;
151    }
152
153    /// \brief The destructor of the map.
154    ///     
155    /// The destructor of the map.
156    virtual ~ArrayMap() {     
157      if (attached()) {
158        clear();
159        detach();
160      }
161    }
162               
163  protected:
164
165    using Parent::attach;
166    using Parent::detach;
167    using Parent::attached;
168
169  public:
170
171    /// \brief The subscript operator.
172    ///
173    /// The subscript operator. The map can be subscripted by the
174    /// actual keys of the graph.
175    Value& operator[](const Key& key) {
176      int id = Parent::notifier()->id(key);
177      return values[id];
178    }
179               
180    /// \brief The const subscript operator.
181    ///
182    /// The const subscript operator. The map can be subscripted by the
183    /// actual keys of the graph.
184    const Value& operator[](const Key& key) const {
185      int id = Parent::notifier()->id(key);
186      return values[id];
187    }
188
189    /// \brief Setter function of the map.
190    ///
191    /// Setter function of the map. Equivalent with map[key] = val.
192    /// This is a compatibility feature with the not dereferable maps.
193    void set(const Key& key, const Value& val) {
194      (*this)[key] = val;
195    }
196
197  protected:
198
199    /// \brief Adds a new key to the map.
200    ///         
201    /// It adds a new key to the map. It called by the observer notifier
202    /// and it overrides the add() member function of the observer base.     
203    virtual void add(const Key& key) {
204      Notifier* nf = Parent::notifier();
205      int id = nf->id(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        Item it;
213        for (nf->first(it); it != INVALID; nf->next(it)) {
214          int jd = nf->id(it);;
215          if (id != jd) {
216            allocator.construct(&(new_values[jd]), values[jd]);
217            allocator.destroy(&(values[jd]));
218          }
219        }
220        if (capacity != 0) allocator.deallocate(values, capacity);
221        values = new_values;
222        capacity = new_capacity;
223      }
224      allocator.construct(&(values[id]), Value());
225    }
226
227    /// \brief Adds more new keys to the map.
228    ///         
229    /// It adds more new keys to the map. It called by the observer notifier
230    /// and it overrides the add() member function of the observer base.     
231    virtual void add(const std::vector<Key>& keys) {
232      Notifier* nf = Parent::notifier();
233      int max_id = -1;
234      for (int i = 0; i < int(keys.size()); ++i) {
235        int id = nf->id(keys[i]);
236        if (id > max_id) {
237          max_id = id;
238        }
239      }
240      if (max_id >= capacity) {
241        int new_capacity = (capacity == 0 ? 1 : capacity);
242        while (new_capacity <= max_id) {
243          new_capacity <<= 1;
244        }
245        Value* new_values = allocator.allocate(new_capacity);
246        Item it;
247        for (nf->first(it); it != INVALID; nf->next(it)) {
248          int id = nf->id(it);
249          bool found = false;
250          for (int i = 0; i < int(keys.size()); ++i) {
251            int jd = nf->id(keys[i]);
252            if (id == jd) {
253              found = true;
254              break;
255            }
256          }
257          if (found) continue;
258          allocator.construct(&(new_values[id]), values[id]);
259          allocator.destroy(&(values[id]));
260        }
261        if (capacity != 0) allocator.deallocate(values, capacity);
262        values = new_values;
263        capacity = new_capacity;
264      }
265      for (int i = 0; i < int(keys.size()); ++i) {
266        int id = nf->id(keys[i]);
267        allocator.construct(&(values[id]), Value());
268      }
269    }
270               
271    /// \brief Erase a key from the map.
272    ///
273    /// Erase a key from the map. It called by the observer notifier
274    /// and it overrides the erase() member function of the observer base.     
275    virtual void erase(const Key& key) {
276      int id = Parent::notifier()->id(key);
277      allocator.destroy(&(values[id]));
278    }
279
280    /// \brief Erase more keys from the map.
281    ///
282    /// Erase more keys from the map. It called by the observer notifier
283    /// and it overrides the erase() member function of the observer base.     
284    virtual void erase(const std::vector<Key>& keys) {
285      for (int i = 0; i < int(keys.size()); ++i) {
286        int id = Parent::notifier()->id(keys[i]);
287        allocator.destroy(&(values[id]));
288      }
289    }
290
291    /// \brief Buildes the map.
292    ///
293    /// It buildes the map. It called by the observer notifier
294    /// and it overrides the build() member function of the observer base.
295    virtual void build() {
296      Notifier* nf = Parent::notifier();
297      allocate_memory();
298      Item it;
299      for (nf->first(it); it != INVALID; nf->next(it)) {
300        int id = nf->id(it);;
301        allocator.construct(&(values[id]), Value());
302      }                                                         
303    }
304
305    /// \brief Clear the map.
306    ///
307    /// It erase all items from the map. It called by the observer notifier
308    /// and it overrides the clear() member function of the observer base.     
309    virtual void clear() {     
310      Notifier* nf = Parent::notifier();
311      if (capacity != 0) {
312        Item it;
313        for (nf->first(it); it != INVALID; nf->next(it)) {
314          int id = nf->id(it);
315          allocator.destroy(&(values[id]));
316        }                                                               
317        allocator.deallocate(values, capacity);
318        capacity = 0;
319      }
320    }
321
322  private:
323     
324    void allocate_memory() {
325      int max_id = Parent::notifier()->maxId();
326      if (max_id == -1) {
327        capacity = 0;
328        values = 0;
329        return;
330      }
331      capacity = 1;
332      while (capacity <= max_id) {
333        capacity <<= 1;
334      }
335      values = allocator.allocate(capacity);   
336    }     
337
338    int capacity;
339    Value* values;
340    Allocator allocator;
341
342  };           
343
344}
345
346#endif
Note: See TracBrowser for help on using the repository browser.