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>
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);
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);