1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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>
31 // \brief Graph map based on the array storage.
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;
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);
107 // \brief Constructor to copy a map of the same map type.
109 // Constructor to copy a map of the same map type.
110 ArrayMap(const ArrayMap& copy) : Parent() {
111 if (copy.attached()) {
112 attach(*copy.notifier());
114 capacity = copy.capacity;
115 if (capacity == 0) return;
116 values = allocator.allocate(capacity);
117 Notifier* nf = Parent::notifier();
119 for (nf->first(it); it != INVALID; nf->next(it)) {
120 int id = nf->id(it);;
121 allocator.construct(&(values[id]), copy.values[id]);
125 // \brief Assign operator.
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.
132 ArrayMap& operator=(const ArrayMap& cmap) {
133 return operator=<ArrayMap>(cmap);
137 // \brief Template assign operator.
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.
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();
148 for (nf->first(it); it != INVALID; nf->next(it)) {
155 // \brief The destructor of the map.
157 // The destructor of the map.
158 virtual ~ArrayMap() {
167 using Parent::attach;
168 using Parent::detach;
169 using Parent::attached;
173 // \brief The subscript operator.
175 // The subscript operator. The map can be subscripted by the
176 // actual keys of the graph.
177 Value& operator[](const Key& key) {
178 int id = Parent::notifier()->id(key);
182 // \brief The const subscript operator.
184 // The const subscript operator. The map can be subscripted by the
185 // actual keys of the graph.
186 const Value& operator[](const Key& key) const {
187 int id = Parent::notifier()->id(key);
191 // \brief Setter function of the map.
193 // Setter function of the map. Equivalent with map[key] = val.
194 // This is a compatibility feature with the not dereferable maps.
195 void set(const Key& key, const Value& val) {
201 // \brief Adds a new key to the map.
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.
205 virtual void add(const Key& key) {
206 Notifier* nf = Parent::notifier();
207 int id = nf->id(key);
208 if (id >= capacity) {
209 int new_capacity = (capacity == 0 ? 1 : capacity);
210 while (new_capacity <= id) {
213 Value* new_values = allocator.allocate(new_capacity);
215 for (nf->first(it); it != INVALID; nf->next(it)) {
216 int jd = nf->id(it);;
218 allocator.construct(&(new_values[jd]), values[jd]);
219 allocator.destroy(&(values[jd]));
222 if (capacity != 0) allocator.deallocate(values, capacity);
224 capacity = new_capacity;
226 allocator.construct(&(values[id]), Value());
229 // \brief Adds more new keys to the map.
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.
233 virtual void add(const std::vector<Key>& keys) {
234 Notifier* nf = Parent::notifier();
236 for (int i = 0; i < int(keys.size()); ++i) {
237 int id = nf->id(keys[i]);
242 if (max_id >= capacity) {
243 int new_capacity = (capacity == 0 ? 1 : capacity);
244 while (new_capacity <= max_id) {
247 Value* new_values = allocator.allocate(new_capacity);
249 for (nf->first(it); it != INVALID; nf->next(it)) {
252 for (int i = 0; i < int(keys.size()); ++i) {
253 int jd = nf->id(keys[i]);
260 allocator.construct(&(new_values[id]), values[id]);
261 allocator.destroy(&(values[id]));
263 if (capacity != 0) allocator.deallocate(values, capacity);
265 capacity = new_capacity;
267 for (int i = 0; i < int(keys.size()); ++i) {
268 int id = nf->id(keys[i]);
269 allocator.construct(&(values[id]), Value());
273 // \brief Erase a key from the map.
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.
277 virtual void erase(const Key& key) {
278 int id = Parent::notifier()->id(key);
279 allocator.destroy(&(values[id]));
282 // \brief Erase more keys from the map.
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.
286 virtual void erase(const std::vector<Key>& keys) {
287 for (int i = 0; i < int(keys.size()); ++i) {
288 int id = Parent::notifier()->id(keys[i]);
289 allocator.destroy(&(values[id]));
293 // \brief Buildes the map.
295 // It buildes the map. It called by the observer notifier
296 // and it overrides the build() member function of the observer base.
297 virtual void build() {
298 Notifier* nf = Parent::notifier();
301 for (nf->first(it); it != INVALID; nf->next(it)) {
302 int id = nf->id(it);;
303 allocator.construct(&(values[id]), Value());
307 // \brief Clear the map.
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.
311 virtual void clear() {
312 Notifier* nf = Parent::notifier();
315 for (nf->first(it); it != INVALID; nf->next(it)) {
317 allocator.destroy(&(values[id]));
319 allocator.deallocate(values, capacity);
326 void allocate_memory() {
327 int max_id = Parent::notifier()->maxId();
334 while (capacity <= max_id) {
337 values = allocator.allocate(capacity);