Some just writeable bool maps.
2 * lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_ARRAY_MAP_H
18 #define LEMON_ARRAY_MAP_H
21 #include <lemon/bits/map_iterator.h>
22 #include <lemon/concept_check.h>
23 #include <lemon/concept/maps.h>
25 /// \ingroup graphmapfactory
27 /// \brief Graph maps that construct and destruct
28 /// their elements dynamically.
32 /// \ingroup graphmapfactory
34 /// \brief Graph map based on the array storage.
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.
41 /// The template parameter is the AlterationNotifier that the maps
42 /// will belong to and the Value.
44 template <typename _Graph,
47 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
51 /// The graph type of the maps.
53 /// The reference map tag.
54 typedef True ReferenceMapTag;
56 /// The key type of the maps.
58 /// The value type of the map.
60 /// The const reference type of the map.
61 typedef const _Value& ConstReference;
62 /// The reference type of the map.
63 typedef _Value& Reference;
65 typedef const Value ConstValue;
66 typedef Value* Pointer;
67 typedef const Value* ConstPointer;
69 typedef AlterationNotifier<_Item> Registry;
71 /// The MapBase of the Map which imlements the core regisitry function.
72 typedef typename Registry::ObserverBase Parent;
77 typedef std::allocator<Value> Allocator;
82 /// \brief Graph initialized map constructor.
84 /// Graph initialized map constructor.
85 ArrayMap(const Graph& _g) : graph(&_g) {
87 attach(_g.getNotifier(Item()));
89 for (graph->first(it); it != INVALID; graph->next(it)) {
90 int id = graph->id(it);;
91 allocator.construct(&(values[id]), Value());
95 /// \brief Constructor to use default value to initialize the map.
97 /// It constructs a map and initialize all of the the map.
98 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
100 attach(_g.getNotifier(_Item()));
102 for (graph->first(it); it != INVALID; graph->next(it)) {
103 int id = graph->id(it);;
104 allocator.construct(&(values[id]), _v);
108 /// \brief Constructor to copy a map of the same map type.
110 /// Constructor to copy a map of the same map type.
111 ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
112 if (copy.attached()) {
113 attach(*copy.getRegistry());
115 capacity = copy.capacity;
116 if (capacity == 0) return;
117 values = allocator.allocate(capacity);
119 for (graph->first(it); it != INVALID; graph->next(it)) {
120 int id = graph->id(it);;
121 allocator.construct(&(values[id]), copy.values[id]);
125 /// \brief The destructor of the map.
127 /// The destructor of the map.
128 virtual ~ArrayMap() {
137 ArrayMap& operator=(const ArrayMap&);
141 using Parent::attach;
142 using Parent::detach;
143 using Parent::attached;
145 const Graph* getGraph() {
152 /// \brief The subscript operator.
154 /// The subscript operator. The map can be subscripted by the
155 /// actual keys of the graph.
156 Value& operator[](const Key& key) {
157 int id = graph->id(key);
161 /// \brief The const subscript operator.
163 /// The const subscript operator. The map can be subscripted by the
164 /// actual keys of the graph.
165 const Value& operator[](const Key& key) const {
166 int id = graph->id(key);
170 /// \brief Setter function of the map.
172 /// Setter function of the map. Equivalent with map[key] = val.
173 /// This is a compatibility feature with the not dereferable maps.
174 void set(const Key& key, const Value& val) {
180 /// Add a new key to the map. It called by the map registry.
182 virtual void add(const Key& key) {
183 int id = graph->id(key);
184 if (id >= capacity) {
185 int new_capacity = (capacity == 0 ? 1 : capacity);
186 while (new_capacity <= id) {
189 Value* new_values = allocator.allocate(new_capacity);
191 for (graph->first(it); it != INVALID; graph->next(it)) {
192 int jd = graph->id(it);;
194 allocator.construct(&(new_values[jd]), values[jd]);
195 allocator.destroy(&(values[jd]));
198 if (capacity != 0) allocator.deallocate(values, capacity);
200 capacity = new_capacity;
202 allocator.construct(&(values[id]), Value());
205 virtual void add(const std::vector<Key>& keys) {
207 for (int i = 0; i < (int)keys.size(); ++i) {
208 int id = graph->id(keys[i]);
213 if (max_id >= capacity) {
214 int new_capacity = (capacity == 0 ? 1 : capacity);
215 while (new_capacity <= max_id) {
218 Value* new_values = allocator.allocate(new_capacity);
220 for (graph->first(it); it != INVALID; graph->next(it)) {
221 int id = graph->id(it);
223 for (int i = 0; i < (int)keys.size(); ++i) {
224 int jd = graph->id(keys[i]);
231 allocator.construct(&(new_values[id]), values[id]);
232 allocator.destroy(&(values[id]));
234 if (capacity != 0) allocator.deallocate(values, capacity);
236 capacity = new_capacity;
238 for (int i = 0; i < (int)keys.size(); ++i) {
239 int id = graph->id(keys[i]);
240 allocator.construct(&(values[id]), Value());
244 /// Erase a key from the map. It called by the map registry.
246 virtual void erase(const Key& key) {
247 int id = graph->id(key);
248 allocator.destroy(&(values[id]));
251 virtual void erase(const std::vector<Key>& keys) {
252 for (int i = 0; i < (int)keys.size(); ++i) {
253 int id = graph->id(keys[i]);
254 allocator.destroy(&(values[id]));
258 virtual void build() {
261 for (graph->first(it); it != INVALID; graph->next(it)) {
262 int id = graph->id(it);;
263 allocator.construct(&(values[id]), Value());
267 virtual void clear() {
270 for (graph->first(it); it != INVALID; graph->next(it)) {
271 int id = graph->id(it);
272 allocator.destroy(&(values[id]));
274 allocator.deallocate(values, capacity);
281 void allocate_memory() {
282 int max_id = graph->maxId(_Item());
289 while (capacity <= max_id) {
292 values = allocator.allocate(capacity);
304 #endif //LEMON_ARRAY_MAP_H