COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/array_map.h @ 1669:66ae78d29f1e

Last change on this file since 1669:66ae78d29f1e was 1669:66ae78d29f1e, checked in by Balazs Dezso, 14 years ago

Template assign operator for graph maps.

Some naming and coding conventions.

File size: 7.1 KB
Line 
1/* -*- C++ -*-
2 * lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_ARRAY_MAP_H
18#define LEMON_ARRAY_MAP_H
19
20#include <memory>
21#include <lemon/bits/map_iterator.h>
22#include <lemon/concept_check.h>
23#include <lemon/concept/maps.h>
24
25/// \ingroup graphmapfactory
26/// \file
27/// \brief Graph maps that construct and destruct
28/// their elements dynamically.
29
30namespace lemon {
31
32  /// \ingroup graphmapfactory
33  ///
34  /// \brief Graph map based on the array storage.
35  ///
36  /// The ArrayMap template class is graph map structure what
37  /// automatically updates the map when a key is added to or erased from
38  /// the map. This map uses the allocators to implement
39  /// the container functionality.
40  ///
41  /// The template parameter is the AlterationNotifier that the maps
42  /// will belong to and the Value.
43
44  template <typename _Graph,
45            typename _Item,
46            typename _Value>
47  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
48
49    typedef _Item Item;
50  public:
51               
52    /// The graph type of the maps.
53    typedef _Graph Graph;
54    /// The key type of the maps.
55    typedef _Item Key;
56
57    typedef AlterationNotifier<_Item> Registry;
58
59    /// The MapBase of the Map which imlements the core regisitry function.
60    typedef typename Registry::ObserverBase Parent;
61               
62    /// The value type of the map.
63    typedef _Value Value;
64
65
66  private:
67    typedef std::allocator<Value> Allocator;
68
69
70  public:
71
72    /// Graph and Registry initialized map constructor.
73    ArrayMap(const Graph& _g) : graph(&_g) {
74      Item it;
75      attach(_g.getNotifier(Item()));
76      allocate_memory();
77      for (graph->first(it); it != INVALID; graph->next(it)) {
78        int id = graph->id(it);;
79        allocator.construct(&(values[id]), Value());
80      }                                                         
81    }
82
83    /// Constructor to use default value to initialize the map.
84
85    /// It constrates a map and initialize all of the the map.
86
87    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
88      Item it;
89      attach(_g.getNotifier(_Item()));
90      allocate_memory();
91      for (graph->first(it); it != INVALID; graph->next(it)) {
92        int id = graph->id(it);;
93        allocator.construct(&(values[id]), _v);
94      }                                                         
95    }
96
97    /// Constructor to copy a map of the same map type.
98     
99    ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
100      if (copy.attached()) {
101        attach(*copy.getRegistry());
102      }
103      capacity = copy.capacity;
104      if (capacity == 0) return;
105      values = allocator.allocate(capacity);
106      Item it;
107      for (graph->first(it); it != INVALID; graph->next(it)) {
108        int id = graph->id(it);;
109        allocator.construct(&(values[id]), copy.values[id]);
110      }
111    }
112
113    /// \brief The destructor of the map.
114    ///     
115    /// The destructor of the map.
116    virtual ~ArrayMap() {     
117      if (attached()) {
118        clear();
119        detach();
120      }
121    }
122               
123  private:
124
125    ArrayMap& operator=(const ArrayMap&);
126
127  protected:
128
129    using Parent::attach;
130    using Parent::detach;
131    using Parent::attached;
132
133    const Graph* getGraph() {
134      return graph;
135    }
136
137
138  public:
139
140    ///The subscript operator. The map can be subscripted by the
141    ///actual keys of the graph.
142     
143    Value& operator[](const Key& key) {
144      int id = graph->id(key);
145      return values[id];
146    }
147               
148
149    ///The const subscript operator. The map can be subscripted by the
150    ///actual keys of the graph.
151     
152    const Value& operator[](const Key& key) const {
153      int id = graph->id(key);
154      return values[id];
155    }
156       
157    /// Setter function of the map. Equivalent with map[key] = val.
158    /// This is a compatibility feature with the not dereferable maps.
159     
160    void set(const Key& key, const Value& val) {
161      (*this)[key] = val;
162    }
163
164  protected:
165   
166    /// Add a new key to the map. It called by the map registry.
167     
168    void add(const Key& key) {
169      int id = graph->id(key);
170      if (id >= capacity) {
171        int new_capacity = (capacity == 0 ? 1 : capacity);
172        while (new_capacity <= id) {
173          new_capacity <<= 1;
174        }
175        Value* new_values = allocator.allocate(new_capacity);
176        Item it;
177        for (graph->first(it); it != INVALID; graph->next(it)) {
178          int jd = graph->id(it);;
179          if (id != jd) {
180            allocator.construct(&(new_values[jd]), values[jd]);
181            allocator.destroy(&(values[jd]));
182          }
183        }
184        if (capacity != 0) allocator.deallocate(values, capacity);
185        values = new_values;
186        capacity = new_capacity;
187      }
188      allocator.construct(&(values[id]), Value());
189    }
190
191    void add(const std::vector<Key>& keys) {
192      int max_id = -1;
193      for (int i = 0; i < (int)keys.size(); ++i) {
194        int id = graph->id(keys[i]);
195        if (id > max_id) {
196          max_id = id;
197        }
198      }
199      if (max_id >= capacity) {
200        int new_capacity = (capacity == 0 ? 1 : capacity);
201        while (new_capacity <= max_id) {
202          new_capacity <<= 1;
203        }
204        Value* new_values = allocator.allocate(new_capacity);
205        Item it;
206        for (graph->first(it); it != INVALID; graph->next(it)) {
207          int id = graph->id(it);
208          bool found = false;
209          for (int i = 0; i < (int)keys.size(); ++i) {
210            int jd = graph->id(keys[i]);
211            if (id == jd) {
212              found = true;
213              break;
214            }
215          }
216          if (found) continue;
217          allocator.construct(&(new_values[id]), values[id]);
218          allocator.destroy(&(values[id]));
219        }
220        if (capacity != 0) allocator.deallocate(values, capacity);
221        values = new_values;
222        capacity = new_capacity;
223      }
224      for (int i = 0; i < (int)keys.size(); ++i) {
225        int id = graph->id(keys[i]);
226        allocator.construct(&(values[id]), Value());
227      }
228    }
229               
230    /// Erase a key from the map. It called by the map registry.
231     
232    void erase(const Key& key) {
233      int id = graph->id(key);
234      allocator.destroy(&(values[id]));
235    }
236
237    void erase(const std::vector<Key>& keys) {
238      for (int i = 0; i < (int)keys.size(); ++i) {
239        int id = graph->id(keys[i]);
240        allocator.destroy(&(values[id]));
241      }
242    }
243
244    void build() {
245      allocate_memory();
246      Item it;
247      for (graph->first(it); it != INVALID; graph->next(it)) {
248        int id = graph->id(it);;
249        allocator.construct(&(values[id]), Value());
250      }                                                         
251    }
252
253    void clear() {     
254      if (capacity != 0) {
255        Item it;
256        for (graph->first(it); it != INVALID; graph->next(it)) {
257          int id = graph->id(it);
258          allocator.destroy(&(values[id]));
259        }                                                               
260        allocator.deallocate(values, capacity);
261        capacity = 0;
262      }
263    }
264
265  private:
266     
267    void allocate_memory() {
268      int max_id = graph->maxId(_Item());
269      if (max_id == -1) {
270        capacity = 0;
271        values = 0;
272        return;
273      }
274      capacity = 1;
275      while (capacity <= max_id) {
276        capacity <<= 1;
277      }
278      values = allocator.allocate(capacity);   
279    }     
280
281    const Graph* graph;
282    int capacity;
283    Value* values;
284    Allocator allocator;
285
286  };           
287
288}
289
290#endif //LEMON_ARRAY_MAP_H
Note: See TracBrowser for help on using the repository browser.