COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/array_map.h @ 969:6dd226d3dcba

Last change on this file since 969:6dd226d3dcba was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 15 years ago

Unify the sources (#339)

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