COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/array_map.h @ 451:09e416d35896

Last change on this file since 451:09e416d35896 was 373:f58410582b9b, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc improvements for the graph related tools in lemon/bits

File size: 10.2 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 that automatically
40  // updates the map when a key is added to or erased from the graph.
41  // This map uses the allocators to implement the container functionality.
42  //
43  // The template parameters are the Graph, the current Item type and
44  // the Value type of the map.
45  template <typename _Graph, typename _Item, typename _Value>
46  class ArrayMap
47    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
48  public:
49    // The graph type.
50    typedef _Graph Graph;
51    // The item type.
52    typedef _Item Item;
53    // The reference map tag.
54    typedef True ReferenceMapTag;
55
56    // The key type of the map.
57    typedef _Item Key;
58    // The value type of the map.
59    typedef _Value Value;
60
61    // The const reference type of the map.
62    typedef const _Value& ConstReference;
63    // The reference type of the map.
64    typedef _Value& Reference;
65
66    // The notifier type.
67    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
68
69    // The MapBase of the Map which imlements the core regisitry function.
70    typedef typename Notifier::ObserverBase Parent;
71
72  private:
73    typedef std::allocator<Value> Allocator;
74
75  public:
76
77    // \brief Graph initialized map constructor.
78    //
79    // Graph initialized map constructor.
80    explicit ArrayMap(const Graph& graph) {
81      Parent::attach(graph.notifier(Item()));
82      allocate_memory();
83      Notifier* nf = Parent::notifier();
84      Item it;
85      for (nf->first(it); it != INVALID; nf->next(it)) {
86        int id = nf->id(it);;
87        allocator.construct(&(values[id]), Value());
88      }
89    }
90
91    // \brief Constructor to use default value to initialize the map.
92    //
93    // It constructs a map and initialize all of the the map.
94    ArrayMap(const Graph& graph, const Value& value) {
95      Parent::attach(graph.notifier(Item()));
96      allocate_memory();
97      Notifier* nf = Parent::notifier();
98      Item it;
99      for (nf->first(it); it != INVALID; nf->next(it)) {
100        int id = nf->id(it);;
101        allocator.construct(&(values[id]), value);
102      }
103    }
104
105  private:
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  public:
154    // \brief The destructor of the map.
155    //
156    // The destructor of the map.
157    virtual ~ArrayMap() {
158      if (attached()) {
159        clear();
160        detach();
161      }
162    }
163
164  protected:
165
166    using Parent::attach;
167    using Parent::detach;
168    using Parent::attached;
169
170  public:
171
172    // \brief The subscript operator.
173    //
174    // The subscript operator. The map can be subscripted by the
175    // actual keys of the graph.
176    Value& operator[](const Key& key) {
177      int id = Parent::notifier()->id(key);
178      return values[id];
179    }
180
181    // \brief The const subscript operator.
182    //
183    // The const subscript operator. The map can be subscripted by the
184    // actual keys of the graph.
185    const Value& operator[](const Key& key) const {
186      int id = Parent::notifier()->id(key);
187      return values[id];
188    }
189
190    // \brief Setter function of the map.
191    //
192    // Setter function of the map. Equivalent with map[key] = val.
193    // This is a compatibility feature with the not dereferable maps.
194    void set(const Key& key, const Value& val) {
195      (*this)[key] = val;
196    }
197
198  protected:
199
200    // \brief Adds a new key to the map.
201    //
202    // It adds a new key to the map. It is called by the observer notifier
203    // and it overrides the add() member function of the observer base.
204    virtual void add(const Key& key) {
205      Notifier* nf = Parent::notifier();
206      int id = nf->id(key);
207      if (id >= capacity) {
208        int new_capacity = (capacity == 0 ? 1 : capacity);
209        while (new_capacity <= id) {
210          new_capacity <<= 1;
211        }
212        Value* new_values = allocator.allocate(new_capacity);
213        Item it;
214        for (nf->first(it); it != INVALID; nf->next(it)) {
215          int jd = nf->id(it);;
216          if (id != jd) {
217            allocator.construct(&(new_values[jd]), values[jd]);
218            allocator.destroy(&(values[jd]));
219          }
220        }
221        if (capacity != 0) allocator.deallocate(values, capacity);
222        values = new_values;
223        capacity = new_capacity;
224      }
225      allocator.construct(&(values[id]), Value());
226    }
227
228    // \brief Adds more new keys to the map.
229    //
230    // It adds more new keys to the map. It is called by the observer notifier
231    // and it overrides the add() member function of the observer base.
232    virtual void add(const std::vector<Key>& keys) {
233      Notifier* nf = Parent::notifier();
234      int max_id = -1;
235      for (int i = 0; i < int(keys.size()); ++i) {
236        int id = nf->id(keys[i]);
237        if (id > max_id) {
238          max_id = id;
239        }
240      }
241      if (max_id >= capacity) {
242        int new_capacity = (capacity == 0 ? 1 : capacity);
243        while (new_capacity <= max_id) {
244          new_capacity <<= 1;
245        }
246        Value* new_values = allocator.allocate(new_capacity);
247        Item it;
248        for (nf->first(it); it != INVALID; nf->next(it)) {
249          int id = nf->id(it);
250          bool found = false;
251          for (int i = 0; i < int(keys.size()); ++i) {
252            int jd = nf->id(keys[i]);
253            if (id == jd) {
254              found = true;
255              break;
256            }
257          }
258          if (found) continue;
259          allocator.construct(&(new_values[id]), values[id]);
260          allocator.destroy(&(values[id]));
261        }
262        if (capacity != 0) allocator.deallocate(values, capacity);
263        values = new_values;
264        capacity = new_capacity;
265      }
266      for (int i = 0; i < int(keys.size()); ++i) {
267        int id = nf->id(keys[i]);
268        allocator.construct(&(values[id]), Value());
269      }
270    }
271
272    // \brief Erase a key from the map.
273    //
274    // Erase a key from the map. It is called by the observer notifier
275    // and it overrides the erase() member function of the observer base.
276    virtual void erase(const Key& key) {
277      int id = Parent::notifier()->id(key);
278      allocator.destroy(&(values[id]));
279    }
280
281    // \brief Erase more keys from the map.
282    //
283    // Erase more keys from the map. It is called by the observer notifier
284    // and it overrides the erase() member function of the observer base.
285    virtual void erase(const std::vector<Key>& keys) {
286      for (int i = 0; i < int(keys.size()); ++i) {
287        int id = Parent::notifier()->id(keys[i]);
288        allocator.destroy(&(values[id]));
289      }
290    }
291
292    // \brief Builds the map.
293    //
294    // It builds the map. It is called by the observer notifier
295    // and it overrides the build() member function of the observer base.
296    virtual void build() {
297      Notifier* nf = Parent::notifier();
298      allocate_memory();
299      Item it;
300      for (nf->first(it); it != INVALID; nf->next(it)) {
301        int id = nf->id(it);;
302        allocator.construct(&(values[id]), Value());
303      }
304    }
305
306    // \brief Clear the map.
307    //
308    // It erase all items from the map. It is called by the observer notifier
309    // and it overrides the clear() member function of the observer base.
310    virtual void clear() {
311      Notifier* nf = Parent::notifier();
312      if (capacity != 0) {
313        Item it;
314        for (nf->first(it); it != INVALID; nf->next(it)) {
315          int id = nf->id(it);
316          allocator.destroy(&(values[id]));
317        }
318        allocator.deallocate(values, capacity);
319        capacity = 0;
320      }
321    }
322
323  private:
324
325    void allocate_memory() {
326      int max_id = Parent::notifier()->maxId();
327      if (max_id == -1) {
328        capacity = 0;
329        values = 0;
330        return;
331      }
332      capacity = 1;
333      while (capacity <= max_id) {
334        capacity <<= 1;
335      }
336      values = allocator.allocate(capacity);
337    }
338
339    int capacity;
340    Value* values;
341    Allocator allocator;
342
343  };
344
345}
346
347#endif
Note: See TracBrowser for help on using the repository browser.