COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 2202:09cbc87cb4ab

Last change on this file since 2202:09cbc87cb4ab was 2202:09cbc87cb4ab, checked in by Balazs Dezso, 13 years ago

New map type based on array map for debugging purpose

It checks multiple allocation and deallocation of map values and
some consistency.

todo:
clarification of debugging concepts
assertions - exceptions - debug
revision of attic/debug.h

motto:
testing is at least so important as coding

File size: 10.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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/concept/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.getNotifier(Item()));
83      allocate_memory();
84      Notifier* notifier = Parent::getNotifier();
85      Item it;
86      for (notifier->first(it); it != INVALID; notifier->next(it)) {
87        int id = notifier->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.getNotifier(Item()));
97      allocate_memory();
98      Notifier* notifier = Parent::getNotifier();
99      Item it;
100      for (notifier->first(it); it != INVALID; notifier->next(it)) {
101        int id = notifier->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.getNotifier());
112      }
113      capacity = copy.capacity;
114      if (capacity == 0) return;
115      values = allocator.allocate(capacity);
116      Notifier* notifier = Parent::getNotifier();
117      Item it;
118      for (notifier->first(it); it != INVALID; notifier->next(it)) {
119        int id = notifier->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<concept::ReadMap<Key, _Value>, CMap>();
145      const typename Parent::Notifier* notifier = Parent::getNotifier();
146      Item it;
147      for (notifier->first(it); it != INVALID; notifier->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::getNotifier()->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::getNotifier()->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* notifier = Parent::getNotifier();
205      int id = notifier->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 (notifier->first(it); it != INVALID; notifier->next(it)) {
214          int jd = notifier->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* notifier = Parent::getNotifier();
233      int max_id = -1;
234      for (int i = 0; i < (int)keys.size(); ++i) {
235        int id = notifier->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 (notifier->first(it); it != INVALID; notifier->next(it)) {
248          int id = notifier->id(it);
249          bool found = false;
250          for (int i = 0; i < (int)keys.size(); ++i) {
251            int jd = notifier->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 = notifier->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::getNotifier()->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::getNotifier()->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* notifier = Parent::getNotifier();
297      allocate_memory();
298      Item it;
299      for (notifier->first(it); it != INVALID; notifier->next(it)) {
300        int id = notifier->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* notifier = Parent::getNotifier();
311      if (capacity != 0) {
312        Item it;
313        for (notifier->first(it); it != INVALID; notifier->next(it)) {
314          int id = notifier->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::getNotifier()->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.