Handling simultan edge adding.
Fixed bug: directed edge maps for undir graphs
2 * src/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>
25 ///\brief Graph maps that construates and destruates
26 ///their elements dynamically.
31 /// \addtogroup graphmaps
34 /// The ArrayMap template class is graph map structure what
35 /// automatically updates the map when a key is added to or erased from
36 /// the map. This map factory uses the allocators to implement
37 /// the container functionality.
39 /// The template parameter is the AlterationNotifier that the maps
40 /// will belong to and the Value.
43 template <typename _Graph,
46 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
51 /// The graph type of the maps.
53 /// The key type of the maps.
56 typedef AlterationNotifier<_Item> Registry;
58 /// The MapBase of the Map which imlements the core regisitry function.
59 typedef typename Registry::ObserverBase Parent;
61 /// The value type of the map.
66 typedef std::allocator<Value> Allocator;
71 /// Graph and Registry initialized map constructor.
73 ArrayMap(const Graph& _g) : graph(&_g) {
75 attach(_g.getNotifier(Item()));
77 for (graph->first(it); it != INVALID; graph->next(it)) {
78 int id = graph->id(it);;
79 allocator.construct(&(values[id]), Value());
83 /// Constructor to use default value to initialize the map.
85 /// It constrates a map and initialize all of the the map.
87 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
89 attach(_g.getNotifier(_Item()));
91 for (graph->first(it); it != INVALID; graph->next(it)) {
92 int id = graph->id(it);;
93 allocator.construct(&(values[id]), _v);
97 /// Constructor to copy a map of the same map type.
99 ArrayMap(const ArrayMap& copy) : Parent() {
100 if (copy.attached()) {
101 attach(*copy.getRegistry());
103 capacity = copy.capacity;
104 if (capacity == 0) return;
105 values = allocator.allocate(capacity);
107 for (graph->first(it); it != INVALID; graph->next(it)) {
108 int id = graph->id(it);;
109 allocator.construct(&(values[id]), copy.values[id]);
113 using Parent::attach;
114 using Parent::detach;
115 using Parent::attached;
117 /// Assign operator to copy a map of the same map type.
119 ArrayMap& operator=(const ArrayMap& copy) {
120 if (© == this) return *this;
122 if (graph != copy.graph) {
127 if (copy.attached()) {
128 attach(*copy.getRegistry());
130 capacity = copy.capacity;
131 if (capacity == 0) return *this;
132 values = allocator.allocate(capacity);
136 for (graph->first(it); it != INVALID; graph->next(it)) {
137 int id = graph->id(it);;
138 allocator.construct(&(values[id]), copy.values[id]);
144 /// The destructor of the map.
146 virtual ~ArrayMap() {
154 ///The subscript operator. The map can be subscripted by the
155 ///actual keys of the graph.
157 Value& operator[](const Key& key) {
158 int id = graph->id(key);
163 ///The const subscript operator. The map can be subscripted by the
164 ///actual keys of the graph.
166 const Value& operator[](const Key& key) const {
167 int id = graph->id(key);
171 /// Setter function of the map. Equivalent with map[key] = val.
172 /// This is a compatibility feature with the not dereferable maps.
174 void set(const Key& key, const Value& val) {
178 /// Add a new key to the map. It called by the map registry.
180 void add(const Key& key) {
181 int id = graph->id(key);
182 if (id >= capacity) {
183 int new_capacity = (capacity == 0 ? 1 : capacity);
184 while (new_capacity <= id) {
187 Value* new_values = allocator.allocate(new_capacity);
189 for (graph->first(it); it != INVALID; graph->next(it)) {
190 int jd = graph->id(it);;
192 allocator.construct(&(new_values[jd]), values[jd]);
193 allocator.destroy(&(values[jd]));
196 if (capacity != 0) allocator.deallocate(values, capacity);
198 capacity = new_capacity;
200 allocator.construct(&(values[id]), Value());
203 void add(const std::vector<Key>& keys) {
205 for (int i = 0; i < (int)keys.size(); ++i) {
206 int id = graph->id(keys[i]);
211 if (max_id >= capacity) {
212 int new_capacity = (capacity == 0 ? 1 : capacity);
213 while (new_capacity <= max_id) {
216 Value* new_values = allocator.allocate(new_capacity);
218 for (graph->first(it); it != INVALID; graph->next(it)) {
219 int id = graph->id(it);
221 for (int i = 0; i < (int)keys.size(); ++i) {
222 int jd = graph->id(keys[i]);
229 allocator.construct(&(new_values[id]), values[id]);
230 allocator.destroy(&(values[id]));
232 if (capacity != 0) allocator.deallocate(values, capacity);
234 capacity = new_capacity;
236 for (int i = 0; i < (int)keys.size(); ++i) {
237 int id = graph->id(keys[i]);
238 allocator.construct(&(values[id]), Value());
242 /// Erase a key from the map. It called by the map registry.
244 void erase(const Key& key) {
245 int id = graph->id(key);
246 allocator.destroy(&(values[id]));
249 void erase(const std::vector<Key>& keys) {
250 for (int i = 0; i < (int)keys.size(); ++i) {
251 int id = graph->id(keys[i]);
252 allocator.destroy(&(values[id]));
259 for (graph->first(it); it != INVALID; graph->next(it)) {
260 int id = graph->id(it);;
261 allocator.construct(&(values[id]), Value());
268 for (graph->first(it); it != INVALID; graph->next(it)) {
269 int id = graph->id(it);
270 allocator.destroy(&(values[id]));
272 allocator.deallocate(values, capacity);
277 const Graph* getGraph() {
283 void allocate_memory() {
284 int max_id = graph->maxId(_Item());
291 while (capacity <= max_id) {
294 values = allocator.allocate(capacity);
304 template <typename _Base>
305 class ArrayMappableGraphExtender : public _Base {
308 typedef ArrayMappableGraphExtender<_Base> Graph;
309 typedef _Base Parent;
311 typedef typename Parent::Node Node;
312 typedef typename Parent::NodeIt NodeIt;
313 typedef typename Parent::NodeNotifier NodeObserverRegistry;
315 typedef typename Parent::Edge Edge;
316 typedef typename Parent::EdgeIt EdgeIt;
317 typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
321 template <typename _Value>
323 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
325 typedef ArrayMappableGraphExtender<_Base> Graph;
327 typedef typename Graph::Node Node;
328 typedef typename Graph::NodeIt NodeIt;
330 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
332 //typedef typename Parent::Graph Graph;
333 typedef typename Parent::Value Value;
335 NodeMap(const Graph& g)
337 NodeMap(const Graph& g, const Value& v)
342 template <typename _Value>
344 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
346 typedef ArrayMappableGraphExtender<_Base> Graph;
348 typedef typename Graph::Edge Edge;
349 typedef typename Graph::EdgeIt EdgeIt;
351 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
353 //typedef typename Parent::Graph Graph;
354 typedef typename Parent::Value Value;
356 EdgeMap(const Graph& g)
358 EdgeMap(const Graph& g, const Value& v)
369 #endif //LEMON_ARRAY_MAP_H