COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1996:5dc13b93f8b4

Last change on this file since 1996:5dc13b93f8b4 was 1996:5dc13b93f8b4, checked in by Balazs Dezso, 15 years ago

Some documentation arrangement modification

File size: 7.8 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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).
[906]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
[1996]19#ifndef LEMON_BITS_ARRAY_MAP_H
20#define LEMON_BITS_ARRAY_MAP_H
[822]21
22#include <memory>
[1810]23#include <lemon/bits/map_extender.h>
[1813]24#include <lemon/bits/alteration_notifier.h>
[1669]25#include <lemon/concept_check.h>
26#include <lemon/concept/maps.h>
[822]27
[1996]28/// \ingroup graphbits
[1669]29/// \file
30/// \brief Graph maps that construct and destruct
31/// their elements dynamically.
[822]32
[921]33namespace lemon {
[822]34
[1996]35  /// \ingroup graphbits
[1669]36  ///
37  /// \brief Graph map based on the array storage.
38  ///
[1414]39  /// The ArrayMap template class is graph map structure what
[1910]40  /// automatically indates the map when a key is added to or erased from
[1669]41  /// the map. This map uses the allocators to implement
[1414]42  /// the container functionality.
43  ///
44  /// The template parameter is the AlterationNotifier that the maps
45  /// will belong to and the Value.
[822]46
[946]47  template <typename _Graph,
48            typename _Item,
49            typename _Value>
[1039]50  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
[897]51
[1267]52    typedef _Item Item;
[822]53  public:
54    /// The graph type of the maps.
[946]55    typedef _Graph Graph;
[1719]56    /// The reference map tag.
57    typedef True ReferenceMapTag;
58
[822]59    /// The key type of the maps.
[987]60    typedef _Item Key;
[1719]61    /// The value type of the map.
62    typedef _Value Value;
63    /// The const reference type of the map.
64    typedef const _Value& ConstReference;
65    /// The reference type of the map.
66    typedef _Value& Reference;
67
68    typedef const Value ConstValue;
69    typedef Value* Pointer;
70    typedef const Value* ConstPointer;
[946]71
[1039]72    typedef AlterationNotifier<_Item> Registry;
[946]73
[822]74    /// The MapBase of the Map which imlements the core regisitry function.
[946]75    typedef typename Registry::ObserverBase Parent;
[822]76               
77
78
[946]79  private:
[822]80    typedef std::allocator<Value> Allocator;
81
[946]82
83  public:
84
[1719]85    /// \brief Graph initialized map constructor.
[1703]86    ///
[1719]87    /// Graph initialized map constructor.
[980]88    ArrayMap(const Graph& _g) : graph(&_g) {
[1267]89      Item it;
90      attach(_g.getNotifier(Item()));
[822]91      allocate_memory();
[1267]92      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]93        int id = graph->id(it);;
[822]94        allocator.construct(&(values[id]), Value());
95      }                                                         
96    }
97
[1703]98    /// \brief Constructor to use default value to initialize the map.
99    ///
100    /// It constructs a map and initialize all of the the map.
[980]101    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
[1267]102      Item it;
[1039]103      attach(_g.getNotifier(_Item()));
[822]104      allocate_memory();
[1267]105      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]106        int id = graph->id(it);;
[946]107        allocator.construct(&(values[id]), _v);
[822]108      }                                                         
109    }
110
[1703]111    /// \brief Constructor to copy a map of the same map type.
112    ///
113    /// Constructor to copy a map of the same map type.     
[1613]114    ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
[946]115      if (copy.attached()) {
116        attach(*copy.getRegistry());
117      }
[822]118      capacity = copy.capacity;
119      if (capacity == 0) return;
120      values = allocator.allocate(capacity);
[1267]121      Item it;
122      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]123        int id = graph->id(it);;
[891]124        allocator.construct(&(values[id]), copy.values[id]);
[822]125      }
126    }
127
[1669]128    /// \brief The destructor of the map.
129    ///     
[1414]130    /// The destructor of the map.
[946]131    virtual ~ArrayMap() {     
132      if (attached()) {
133        clear();
134        detach();
[822]135      }
136    }
[1669]137               
138  private:
139
140    ArrayMap& operator=(const ArrayMap&);
141
142  protected:
143
144    using Parent::attach;
145    using Parent::detach;
146    using Parent::attached;
147
148    const Graph* getGraph() {
149      return graph;
150    }
151
152
153  public:
154
[1703]155    /// \brief The subscript operator.
156    ///
157    /// The subscript operator. The map can be subscripted by the
158    /// actual keys of the graph.
[1267]159    Value& operator[](const Key& key) {
[980]160      int id = graph->id(key);
[822]161      return values[id];
162    }
163               
[1703]164    /// \brief The const subscript operator.
165    ///
166    /// The const subscript operator. The map can be subscripted by the
167    /// actual keys of the graph.
[1267]168    const Value& operator[](const Key& key) const {
[980]169      int id = graph->id(key);
[822]170      return values[id];
171    }
[1703]172
173    /// \brief Setter function of the map.
174    ///
[1414]175    /// Setter function of the map. Equivalent with map[key] = val.
176    /// This is a compatibility feature with the not dereferable maps.
[987]177    void set(const Key& key, const Value& val) {
[946]178      (*this)[key] = val;
[822]179    }
[1669]180
181  protected:
[1703]182
[1414]183    /// Add a new key to the map. It called by the map registry.
[1703]184         
185    virtual void add(const Key& key) {
[980]186      int id = graph->id(key);
[822]187      if (id >= capacity) {
188        int new_capacity = (capacity == 0 ? 1 : capacity);
189        while (new_capacity <= id) {
190          new_capacity <<= 1;
191        }
[946]192        Value* new_values = allocator.allocate(new_capacity);
[1267]193        Item it;
194        for (graph->first(it); it != INVALID; graph->next(it)) {
[980]195          int jd = graph->id(it);;
[822]196          if (id != jd) {
197            allocator.construct(&(new_values[jd]), values[jd]);
198            allocator.destroy(&(values[jd]));
199          }
200        }
201        if (capacity != 0) allocator.deallocate(values, capacity);
202        values = new_values;
203        capacity = new_capacity;
204      }
205      allocator.construct(&(values[id]), Value());
206    }
[1414]207
[1703]208    virtual void add(const std::vector<Key>& keys) {
[1414]209      int max_id = -1;
210      for (int i = 0; i < (int)keys.size(); ++i) {
211        int id = graph->id(keys[i]);
212        if (id > max_id) {
213          max_id = id;
214        }
215      }
216      if (max_id >= capacity) {
217        int new_capacity = (capacity == 0 ? 1 : capacity);
218        while (new_capacity <= max_id) {
219          new_capacity <<= 1;
220        }
221        Value* new_values = allocator.allocate(new_capacity);
222        Item it;
223        for (graph->first(it); it != INVALID; graph->next(it)) {
224          int id = graph->id(it);
225          bool found = false;
226          for (int i = 0; i < (int)keys.size(); ++i) {
227            int jd = graph->id(keys[i]);
228            if (id == jd) {
229              found = true;
230              break;
231            }
232          }
233          if (found) continue;
234          allocator.construct(&(new_values[id]), values[id]);
235          allocator.destroy(&(values[id]));
236        }
237        if (capacity != 0) allocator.deallocate(values, capacity);
238        values = new_values;
239        capacity = new_capacity;
240      }
241      for (int i = 0; i < (int)keys.size(); ++i) {
242        int id = graph->id(keys[i]);
243        allocator.construct(&(values[id]), Value());
244      }
245    }
[822]246               
[1414]247    /// Erase a key from the map. It called by the map registry.
248     
[1703]249    virtual void erase(const Key& key) {
[980]250      int id = graph->id(key);
[822]251      allocator.destroy(&(values[id]));
252    }
253
[1703]254    virtual void erase(const std::vector<Key>& keys) {
[1414]255      for (int i = 0; i < (int)keys.size(); ++i) {
256        int id = graph->id(keys[i]);
257        allocator.destroy(&(values[id]));
258      }
259    }
260
[1703]261    virtual void build() {
[946]262      allocate_memory();
[1267]263      Item it;
264      for (graph->first(it); it != INVALID; graph->next(it)) {
[980]265        int id = graph->id(it);;
[946]266        allocator.construct(&(values[id]), Value());
267      }                                                         
268    }
269
[1703]270    virtual void clear() {     
[822]271      if (capacity != 0) {
[1267]272        Item it;
273        for (graph->first(it); it != INVALID; graph->next(it)) {
[1414]274          int id = graph->id(it);
[946]275          allocator.destroy(&(values[id]));
276        }                                                               
[822]277        allocator.deallocate(values, capacity);
278        capacity = 0;
279      }
280    }
281
282  private:
283     
284    void allocate_memory() {
[980]285      int max_id = graph->maxId(_Item());
[822]286      if (max_id == -1) {
287        capacity = 0;
288        values = 0;
289        return;
290      }
291      capacity = 1;
292      while (capacity <= max_id) {
293        capacity <<= 1;
294      }
295      values = allocator.allocate(capacity);   
296    }     
297
[946]298    const Graph* graph;
[822]299    int capacity;
300    Value* values;
301    Allocator allocator;
[844]302
[822]303  };           
304
305}
306
[1996]307#endif
Note: See TracBrowser for help on using the repository browser.