COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/array_map.h @ 500:8a144437db7d

Last change on this file since 500:8a144437db7d was 314:2cc60866a0c9, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Doc reorganization + improvements

  • Reorganize several tools (move them to other modules).
  • Add new module for map concepts.
  • Remove the doc of all tools in lemon/bits.
  • Improvements in groups.dox.
  • Fix some doxygen warnings.
File size: 10.2 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
[314]29// \ingroup graphbits
30// \file
31// \brief Graph map based on the array storage.
[57]32
33namespace lemon {
34
[314]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.
[57]46  template <typename _Graph, typename _Item, typename _Value>
[209]47  class ArrayMap
[57]48    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
49  public:
[314]50    // The graph type of the maps.
[57]51    typedef _Graph Graph;
[314]52    // The item type of the map.
[57]53    typedef _Item Item;
[314]54    // The reference map tag.
[57]55    typedef True ReferenceMapTag;
56
[314]57    // The key type of the maps.
[57]58    typedef _Item Key;
[314]59    // The value type of the map.
[57]60    typedef _Value Value;
61
[314]62    // The const reference type of the map.
[57]63    typedef const _Value& ConstReference;
[314]64    // The reference type of the map.
[57]65    typedef _Value& Reference;
66
[314]67    // The notifier type.
[57]68    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
69
[314]70    // The MapBase of the Map which imlements the core regisitry function.
[57]71    typedef typename Notifier::ObserverBase Parent;
[209]72
[57]73  private:
74    typedef std::allocator<Value> Allocator;
75
76  public:
77
[314]78    // \brief Graph initialized map constructor.
79    //
80    // Graph initialized map constructor.
[57]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
[314]92    // \brief Constructor to use default value to initialize the map.
93    //
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
[263]106  private:
[314]107    // \brief Constructor to copy a map of the same map type.
108    //
109    // Constructor to copy a map of the same map type.
[57]110    ArrayMap(const ArrayMap& copy) : Parent() {
111      if (copy.attached()) {
[209]112        attach(*copy.notifier());
[57]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)) {
[209]120        int id = nf->id(it);;
121        allocator.construct(&(values[id]), copy.values[id]);
[57]122      }
123    }
124
[314]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.
[57]132    ArrayMap& operator=(const ArrayMap& cmap) {
133      return operator=<ArrayMap>(cmap);
134    }
135
136
[314]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.
[57]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
[263]154  public:
[314]155    // \brief The destructor of the map.
156    //
157    // The destructor of the map.
[209]158    virtual ~ArrayMap() {
[57]159      if (attached()) {
[209]160        clear();
161        detach();
[57]162      }
163    }
[209]164
[57]165  protected:
166
167    using Parent::attach;
168    using Parent::detach;
169    using Parent::attached;
170
171  public:
172
[314]173    // \brief The subscript operator.
174    //
175    // The subscript operator. The map can be subscripted by the
176    // actual keys of the graph.
[57]177    Value& operator[](const Key& key) {
178      int id = Parent::notifier()->id(key);
179      return values[id];
[209]180    }
181
[314]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.
[57]186    const Value& operator[](const Key& key) const {
187      int id = Parent::notifier()->id(key);
188      return values[id];
189    }
190
[314]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.
[57]195    void set(const Key& key, const Value& val) {
196      (*this)[key] = val;
197    }
198
199  protected:
200
[314]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.
[57]205    virtual void add(const Key& key) {
206      Notifier* nf = Parent::notifier();
207      int id = nf->id(key);
208      if (id >= capacity) {
[209]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;
[57]225      }
226      allocator.construct(&(values[id]), Value());
227    }
228
[314]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.
[57]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) {
[209]237        int id = nf->id(keys[i]);
238        if (id > max_id) {
239          max_id = id;
240        }
[57]241      }
242      if (max_id >= capacity) {
[209]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;
[57]266      }
267      for (int i = 0; i < int(keys.size()); ++i) {
[209]268        int id = nf->id(keys[i]);
269        allocator.construct(&(values[id]), Value());
[57]270      }
271    }
[209]272
[314]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.
[57]277    virtual void erase(const Key& key) {
278      int id = Parent::notifier()->id(key);
279      allocator.destroy(&(values[id]));
280    }
281
[314]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.
[57]286    virtual void erase(const std::vector<Key>& keys) {
287      for (int i = 0; i < int(keys.size()); ++i) {
[209]288        int id = Parent::notifier()->id(keys[i]);
289        allocator.destroy(&(values[id]));
[57]290      }
291    }
292
[314]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.
[57]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)) {
[209]302        int id = nf->id(it);;
303        allocator.construct(&(values[id]), Value());
304      }
[57]305    }
306
[314]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.
[209]311    virtual void clear() {
[57]312      Notifier* nf = Parent::notifier();
313      if (capacity != 0) {
[209]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;
[57]321      }
322    }
323
324  private:
[209]325
[57]326    void allocate_memory() {
327      int max_id = Parent::notifier()->maxId();
328      if (max_id == -1) {
[209]329        capacity = 0;
330        values = 0;
331        return;
[57]332      }
333      capacity = 1;
334      while (capacity <= max_id) {
[209]335        capacity <<= 1;
[57]336      }
[209]337      values = allocator.allocate(capacity);
338    }
[57]339
340    int capacity;
341    Value* values;
342    Allocator allocator;
343
[209]344  };
[57]345
346}
347
[209]348#endif
Note: See TracBrowser for help on using the repository browser.