COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/bits/array_map.h @ 209:765619b7cbb2

Last change on this file since 209:765619b7cbb2 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 12 years ago

Apply unify-sources.sh to the source tree

File size: 10.3 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[107]5 * Copyright (C) 2003-2008
[57]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
[209]41  /// the map. This map uses the allocators to implement
[57]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>
[209]47  class ArrayMap
[57]48    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
49  public:
[209]50    /// The graph type of the maps.
[57]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;
[209]72
[57]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)) {
[209]87        int id = nf->id(it);;
88        allocator.construct(&(values[id]), Value());
89      }
[57]90    }
91
[209]92    /// \brief Constructor to use default value to initialize the map.
[57]93    ///
[209]94    /// It constructs a map and initialize all of the the map.
[57]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)) {
[209]101        int id = nf->id(it);;
102        allocator.construct(&(values[id]), value);
103      }
[57]104    }
105
106    /// \brief Constructor to copy a map of the same map type.
107    ///
[209]108    /// Constructor to copy a map of the same map type.
[57]109    ArrayMap(const ArrayMap& copy) : Parent() {
110      if (copy.attached()) {
[209]111        attach(*copy.notifier());
[57]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)) {
[209]119        int id = nf->id(it);;
120        allocator.construct(&(values[id]), copy.values[id]);
[57]121      }
122    }
123
124    /// \brief Assign operator.
125    ///
126    /// This operator assigns for each item in the map the
[209]127    /// value mapped to the same item in the copied map.
[57]128    /// The parameter map should be indiced with the same
129    /// itemset because this assign operator does not change
[209]130    /// the container of the map.
[57]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
[209]141    /// is assigned by the value of the given ReadMap.
[57]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.
[209]154    ///
[57]155    /// The destructor of the map.
[209]156    virtual ~ArrayMap() {
[57]157      if (attached()) {
[209]158        clear();
159        detach();
[57]160      }
161    }
[209]162
[57]163  protected:
164
165    using Parent::attach;
166    using Parent::detach;
167    using Parent::attached;
168
169  public:
170
[209]171    /// \brief The subscript operator.
[57]172    ///
173    /// The subscript operator. The map can be subscripted by the
[209]174    /// actual keys of the graph.
[57]175    Value& operator[](const Key& key) {
176      int id = Parent::notifier()->id(key);
177      return values[id];
[209]178    }
179
[57]180    /// \brief The const subscript operator.
181    ///
182    /// The const subscript operator. The map can be subscripted by the
[209]183    /// actual keys of the graph.
[57]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.
[209]190    ///
[57]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.
[209]200    ///
[57]201    /// It adds a new key to the map. It called by the observer notifier
[209]202    /// and it overrides the add() member function of the observer base.
[57]203    virtual void add(const Key& key) {
204      Notifier* nf = Parent::notifier();
205      int id = nf->id(key);
206      if (id >= capacity) {
[209]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;
[57]223      }
224      allocator.construct(&(values[id]), Value());
225    }
226
227    /// \brief Adds more new keys to the map.
[209]228    ///
[57]229    /// It adds more new keys to the map. It called by the observer notifier
[209]230    /// and it overrides the add() member function of the observer base.
[57]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) {
[209]235        int id = nf->id(keys[i]);
236        if (id > max_id) {
237          max_id = id;
238        }
[57]239      }
240      if (max_id >= capacity) {
[209]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;
[57]264      }
265      for (int i = 0; i < int(keys.size()); ++i) {
[209]266        int id = nf->id(keys[i]);
267        allocator.construct(&(values[id]), Value());
[57]268      }
269    }
[209]270
[57]271    /// \brief Erase a key from the map.
272    ///
273    /// Erase a key from the map. It called by the observer notifier
[209]274    /// and it overrides the erase() member function of the observer base.
[57]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
[209]283    /// and it overrides the erase() member function of the observer base.
[57]284    virtual void erase(const std::vector<Key>& keys) {
285      for (int i = 0; i < int(keys.size()); ++i) {
[209]286        int id = Parent::notifier()->id(keys[i]);
287        allocator.destroy(&(values[id]));
[57]288      }
289    }
290
291    /// \brief Buildes the map.
[209]292    ///
[57]293    /// It buildes the map. It called by the observer notifier
[209]294    /// and it overrides the build() member function of the observer base.
[57]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)) {
[209]300        int id = nf->id(it);;
301        allocator.construct(&(values[id]), Value());
302      }
[57]303    }
304
305    /// \brief Clear the map.
306    ///
307    /// It erase all items from the map. It called by the observer notifier
[209]308    /// and it overrides the clear() member function of the observer base.
309    virtual void clear() {
[57]310      Notifier* nf = Parent::notifier();
311      if (capacity != 0) {
[209]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;
[57]319      }
320    }
321
322  private:
[209]323
[57]324    void allocate_memory() {
325      int max_id = Parent::notifier()->maxId();
326      if (max_id == -1) {
[209]327        capacity = 0;
328        values = 0;
329        return;
[57]330      }
331      capacity = 1;
332      while (capacity <= max_id) {
[209]333        capacity <<= 1;
[57]334      }
[209]335      values = allocator.allocate(capacity);
336    }
[57]337
338    int capacity;
339    Value* values;
340    Allocator allocator;
341
[209]342  };
[57]343
344}
345
[209]346#endif
Note: See TracBrowser for help on using the repository browser.