3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_ARRAY_MAP_H
20 #define LEMON_BITS_ARRAY_MAP_H
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>
29 /// \ingroup graphbits
31 /// \brief Graph map based on the array storage.
35 /// \ingroup graphbits
37 /// \brief Graph map based on the array storage.
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.
44 /// The template parameters are the Graph the current Item type and
45 /// the Value type of the map.
46 template <typename _Graph, typename _Item, typename _Value>
48 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
50 /// The graph type of the maps.
52 /// The item type of the map.
54 /// The reference map tag.
55 typedef True ReferenceMapTag;
57 /// The key type of the maps.
59 /// The value type of the map.
62 /// The const reference type of the map.
63 typedef const _Value& ConstReference;
64 /// The reference type of the map.
65 typedef _Value& Reference;
67 /// The notifier type.
68 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
70 /// The MapBase of the Map which imlements the core regisitry function.
71 typedef typename Notifier::ObserverBase Parent;
74 typedef std::allocator<Value> Allocator;
78 /// \brief Graph initialized map constructor.
80 /// Graph initialized map constructor.
81 explicit ArrayMap(const Graph& graph) {
82 Parent::attach(graph.notifier(Item()));
84 Notifier* nf = Parent::notifier();
86 for (nf->first(it); it != INVALID; nf->next(it)) {
88 allocator.construct(&(values[id]), Value());
92 /// \brief Constructor to use default value to initialize the map.
94 /// It constructs a map and initialize all of the the map.
95 ArrayMap(const Graph& graph, const Value& value) {
96 Parent::attach(graph.notifier(Item()));
98 Notifier* nf = Parent::notifier();
100 for (nf->first(it); it != INVALID; nf->next(it)) {
101 int id = nf->id(it);;
102 allocator.construct(&(values[id]), value);
106 /// \brief Constructor to copy a map of the same map type.
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());
113 capacity = copy.capacity;
114 if (capacity == 0) return;
115 values = allocator.allocate(capacity);
116 Notifier* nf = Parent::notifier();
118 for (nf->first(it); it != INVALID; nf->next(it)) {
119 int id = nf->id(it);;
120 allocator.construct(&(values[id]), copy.values[id]);
124 /// \brief Assign operator.
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);
136 /// \brief Template assign operator.
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();
147 for (nf->first(it); it != INVALID; nf->next(it)) {
153 /// \brief The destructor of the map.
155 /// The destructor of the map.
156 virtual ~ArrayMap() {
165 using Parent::attach;
166 using Parent::detach;
167 using Parent::attached;
171 /// \brief The subscript operator.
173 /// The subscript operator. The map can be subscripted by the
174 /// actual keys of the graph.
175 Value& operator[](const Key& key) {
176 int id = Parent::notifier()->id(key);
180 /// \brief The const subscript operator.
182 /// The const subscript operator. The map can be subscripted by the
183 /// actual keys of the graph.
184 const Value& operator[](const Key& key) const {
185 int id = Parent::notifier()->id(key);
189 /// \brief Setter function of the map.
191 /// Setter function of the map. Equivalent with map[key] = val.
192 /// This is a compatibility feature with the not dereferable maps.
193 void set(const Key& key, const Value& val) {
199 /// \brief Adds a new key to the map.
201 /// It adds a new key to the map. It called by the observer notifier
202 /// and it overrides the add() member function of the observer base.
203 virtual void add(const Key& key) {
204 Notifier* nf = Parent::notifier();
205 int id = nf->id(key);
206 if (id >= capacity) {
207 int new_capacity = (capacity == 0 ? 1 : capacity);
208 while (new_capacity <= id) {
211 Value* new_values = allocator.allocate(new_capacity);
213 for (nf->first(it); it != INVALID; nf->next(it)) {
214 int jd = nf->id(it);;
216 allocator.construct(&(new_values[jd]), values[jd]);
217 allocator.destroy(&(values[jd]));
220 if (capacity != 0) allocator.deallocate(values, capacity);
222 capacity = new_capacity;
224 allocator.construct(&(values[id]), Value());
227 /// \brief Adds more new keys to the map.
229 /// It adds more new keys to the map. It called by the observer notifier
230 /// and it overrides the add() member function of the observer base.
231 virtual void add(const std::vector<Key>& keys) {
232 Notifier* nf = Parent::notifier();
234 for (int i = 0; i < int(keys.size()); ++i) {
235 int id = nf->id(keys[i]);
240 if (max_id >= capacity) {
241 int new_capacity = (capacity == 0 ? 1 : capacity);
242 while (new_capacity <= max_id) {
245 Value* new_values = allocator.allocate(new_capacity);
247 for (nf->first(it); it != INVALID; nf->next(it)) {
250 for (int i = 0; i < int(keys.size()); ++i) {
251 int jd = nf->id(keys[i]);
258 allocator.construct(&(new_values[id]), values[id]);
259 allocator.destroy(&(values[id]));
261 if (capacity != 0) allocator.deallocate(values, capacity);
263 capacity = new_capacity;
265 for (int i = 0; i < int(keys.size()); ++i) {
266 int id = nf->id(keys[i]);
267 allocator.construct(&(values[id]), Value());
271 /// \brief Erase a key from the map.
273 /// Erase a key from the map. It called by the observer notifier
274 /// and it overrides the erase() member function of the observer base.
275 virtual void erase(const Key& key) {
276 int id = Parent::notifier()->id(key);
277 allocator.destroy(&(values[id]));
280 /// \brief Erase more keys from the map.
282 /// Erase more keys from the map. It called by the observer notifier
283 /// and it overrides the erase() member function of the observer base.
284 virtual void erase(const std::vector<Key>& keys) {
285 for (int i = 0; i < int(keys.size()); ++i) {
286 int id = Parent::notifier()->id(keys[i]);
287 allocator.destroy(&(values[id]));
291 /// \brief Buildes the map.
293 /// It buildes the map. It called by the observer notifier
294 /// and it overrides the build() member function of the observer base.
295 virtual void build() {
296 Notifier* nf = Parent::notifier();
299 for (nf->first(it); it != INVALID; nf->next(it)) {
300 int id = nf->id(it);;
301 allocator.construct(&(values[id]), Value());
305 /// \brief Clear the map.
307 /// It erase all items from the map. It called by the observer notifier
308 /// and it overrides the clear() member function of the observer base.
309 virtual void clear() {
310 Notifier* nf = Parent::notifier();
313 for (nf->first(it); it != INVALID; nf->next(it)) {
315 allocator.destroy(&(values[id]));
317 allocator.deallocate(values, capacity);
324 void allocate_memory() {
325 int max_id = Parent::notifier()->maxId();
332 while (capacity <= max_id) {
335 values = allocator.allocate(capacity);