COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/array_map.h @ 291:d901321d6555

Last change on this file since 291:d901321d6555 was 263:be8a861d3bb7, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Make copy constr and op= of the default maps private (ticket #137)

File size: 10.3 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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  private:
107    /// \brief Constructor to copy a map of the same map type.
108    ///
109    /// Constructor to copy a map of the same map type.
110    ArrayMap(const ArrayMap& copy) : Parent() {
111      if (copy.attached()) {
112        attach(*copy.notifier());
113      }
114      capacity = copy.capacity;
115      if (capacity == 0) return;
116      values = allocator.allocate(capacity);
117      Notifier* nf = Parent::notifier();
118      Item it;
119      for (nf->first(it); it != INVALID; nf->next(it)) {
120        int id = nf->id(it);;
121        allocator.construct(&(values[id]), copy.values[id]);
122      }
123    }
124
125    /// \brief Assign operator.
126    ///
127    /// This operator assigns for each item in the map the
128    /// value mapped to the same item in the copied map.
129    /// The parameter map should be indiced with the same
130    /// itemset because this assign operator does not change
131    /// the container of the map.
132    ArrayMap& operator=(const ArrayMap& cmap) {
133      return operator=<ArrayMap>(cmap);
134    }
135
136
137    /// \brief Template assign operator.
138    ///
139    /// The given parameter should be conform to the ReadMap
140    /// concecpt and could be indiced by the current item set of
141    /// the NodeMap. In this case the value for each item
142    /// is assigned by the value of the given ReadMap.
143    template <typename CMap>
144    ArrayMap& operator=(const CMap& cmap) {
145      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
146      const typename Parent::Notifier* nf = Parent::notifier();
147      Item it;
148      for (nf->first(it); it != INVALID; nf->next(it)) {
149        set(it, cmap[it]);
150      }
151      return *this;
152    }
153
154  public:
155    /// \brief The destructor of the map.
156    ///
157    /// The destructor of the map.
158    virtual ~ArrayMap() {
159      if (attached()) {
160        clear();
161        detach();
162      }
163    }
164
165  protected:
166
167    using Parent::attach;
168    using Parent::detach;
169    using Parent::attached;
170
171  public:
172
173    /// \brief The subscript operator.
174    ///
175    /// The subscript operator. The map can be subscripted by the
176    /// actual keys of the graph.
177    Value& operator[](const Key& key) {
178      int id = Parent::notifier()->id(key);
179      return values[id];
180    }
181
182    /// \brief The const subscript operator.
183    ///
184    /// The const subscript operator. The map can be subscripted by the
185    /// actual keys of the graph.
186    const Value& operator[](const Key& key) const {
187      int id = Parent::notifier()->id(key);
188      return values[id];
189    }
190
191    /// \brief Setter function of the map.
192    ///
193    /// Setter function of the map. Equivalent with map[key] = val.
194    /// This is a compatibility feature with the not dereferable maps.
195    void set(const Key& key, const Value& val) {
196      (*this)[key] = val;
197    }
198
199  protected:
200
201    /// \brief Adds a new key to the map.
202    ///
203    /// It adds a new key to the map. It called by the observer notifier
204    /// and it overrides the add() member function of the observer base.
205    virtual void add(const Key& key) {
206      Notifier* nf = Parent::notifier();
207      int id = nf->id(key);
208      if (id >= capacity) {
209        int new_capacity = (capacity == 0 ? 1 : capacity);
210        while (new_capacity <= id) {
211          new_capacity <<= 1;
212        }
213        Value* new_values = allocator.allocate(new_capacity);
214        Item it;
215        for (nf->first(it); it != INVALID; nf->next(it)) {
216          int jd = nf->id(it);;
217          if (id != jd) {
218            allocator.construct(&(new_values[jd]), values[jd]);
219            allocator.destroy(&(values[jd]));
220          }
221        }
222        if (capacity != 0) allocator.deallocate(values, capacity);
223        values = new_values;
224        capacity = new_capacity;
225      }
226      allocator.construct(&(values[id]), Value());
227    }
228
229    /// \brief Adds more new keys to the map.
230    ///
231    /// It adds more new keys to the map. It called by the observer notifier
232    /// and it overrides the add() member function of the observer base.
233    virtual void add(const std::vector<Key>& keys) {
234      Notifier* nf = Parent::notifier();
235      int max_id = -1;
236      for (int i = 0; i < int(keys.size()); ++i) {
237        int id = nf->id(keys[i]);
238        if (id > max_id) {
239          max_id = id;
240        }
241      }
242      if (max_id >= capacity) {
243        int new_capacity = (capacity == 0 ? 1 : capacity);
244        while (new_capacity <= max_id) {
245          new_capacity <<= 1;
246        }
247        Value* new_values = allocator.allocate(new_capacity);
248        Item it;
249        for (nf->first(it); it != INVALID; nf->next(it)) {
250          int id = nf->id(it);
251          bool found = false;
252          for (int i = 0; i < int(keys.size()); ++i) {
253            int jd = nf->id(keys[i]);
254            if (id == jd) {
255              found = true;
256              break;
257            }
258          }
259          if (found) continue;
260          allocator.construct(&(new_values[id]), values[id]);
261          allocator.destroy(&(values[id]));
262        }
263        if (capacity != 0) allocator.deallocate(values, capacity);
264        values = new_values;
265        capacity = new_capacity;
266      }
267      for (int i = 0; i < int(keys.size()); ++i) {
268        int id = nf->id(keys[i]);
269        allocator.construct(&(values[id]), Value());
270      }
271    }
272
273    /// \brief Erase a key from the map.
274    ///
275    /// Erase a key from the map. It called by the observer notifier
276    /// and it overrides the erase() member function of the observer base.
277    virtual void erase(const Key& key) {
278      int id = Parent::notifier()->id(key);
279      allocator.destroy(&(values[id]));
280    }
281
282    /// \brief Erase more keys from the map.
283    ///
284    /// Erase more keys from the map. It called by the observer notifier
285    /// and it overrides the erase() member function of the observer base.
286    virtual void erase(const std::vector<Key>& keys) {
287      for (int i = 0; i < int(keys.size()); ++i) {
288        int id = Parent::notifier()->id(keys[i]);
289        allocator.destroy(&(values[id]));
290      }
291    }
292
293    /// \brief Buildes the map.
294    ///
295    /// It buildes the map. It called by the observer notifier
296    /// and it overrides the build() member function of the observer base.
297    virtual void build() {
298      Notifier* nf = Parent::notifier();
299      allocate_memory();
300      Item it;
301      for (nf->first(it); it != INVALID; nf->next(it)) {
302        int id = nf->id(it);;
303        allocator.construct(&(values[id]), Value());
304      }
305    }
306
307    /// \brief Clear the map.
308    ///
309    /// It erase all items from the map. It called by the observer notifier
310    /// and it overrides the clear() member function of the observer base.
311    virtual void clear() {
312      Notifier* nf = Parent::notifier();
313      if (capacity != 0) {
314        Item it;
315        for (nf->first(it); it != INVALID; nf->next(it)) {
316          int id = nf->id(it);
317          allocator.destroy(&(values[id]));
318        }
319        allocator.deallocate(values, capacity);
320        capacity = 0;
321      }
322    }
323
324  private:
325
326    void allocate_memory() {
327      int max_id = Parent::notifier()->maxId();
328      if (max_id == -1) {
329        capacity = 0;
330        values = 0;
331        return;
332      }
333      capacity = 1;
334      while (capacity <= max_id) {
335        capacity <<= 1;
336      }
337      values = allocator.allocate(capacity);
338    }
339
340    int capacity;
341    Value* values;
342    Allocator allocator;
343
344  };
345
346}
347
348#endif
Note: See TracBrowser for help on using the repository browser.