Correct the english name of EGRES.
2 * src/lemon/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) {
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() {
155 * The subscript operator. The map can be subscripted by the
156 * actual keys of the graph.
158 Value& operator[](const Key& key) {
159 int id = graph->id(key);
164 * The const subscript operator. The map can be subscripted by the
165 * actual keys of the graph.
167 const Value& operator[](const Key& key) const {
168 int id = graph->id(key);
172 /** Setter function of the map. Equivalent with map[key] = val.
173 * This is a compatibility feature with the not dereferable maps.
175 void set(const Key& key, const Value& val) {
179 /** Add a new key to the map. It called by the map registry.
181 void add(const Key& key) {
182 int id = graph->id(key);
183 if (id >= capacity) {
184 int new_capacity = (capacity == 0 ? 1 : capacity);
185 while (new_capacity <= id) {
188 Value* new_values = allocator.allocate(new_capacity);
190 for (graph->first(it); it != INVALID; graph->next(it)) {
191 int jd = graph->id(it);;
193 allocator.construct(&(new_values[jd]), values[jd]);
194 allocator.destroy(&(values[jd]));
197 if (capacity != 0) allocator.deallocate(values, capacity);
199 capacity = new_capacity;
201 allocator.construct(&(values[id]), Value());
204 /** Erase a key from the map. It called by the map registry.
206 void erase(const Key& key) {
207 int id = graph->id(key);
208 allocator.destroy(&(values[id]));
214 for (graph->first(it); it != INVALID; graph->next(it)) {
215 int id = graph->id(it);;
216 allocator.construct(&(values[id]), Value());
223 for (graph->first(it); it != INVALID; graph->next(it)) {
224 int id = graph->id(it);;
225 allocator.destroy(&(values[id]));
227 allocator.deallocate(values, capacity);
232 const Graph* getGraph() {
236 // /// The stl compatible pair iterator of the map.
237 // typedef MapIterator<ArrayMap> Iterator;
238 // /// The stl compatible const pair iterator of the map.
239 // typedef MapConstIterator<ArrayMap> ConstIterator;
241 // /** Returns the begin iterator of the map.
243 // Iterator begin() {
244 // return Iterator(*this, KeyIt(*MapBase::getGraph()));
247 // /** Returns the end iterator of the map.
250 // return Iterator(*this, INVALID);
253 // /** Returns the begin ConstIterator of the map.
255 // ConstIterator begin() const {
256 // return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
259 // /** Returns the end const_iterator of the map.
261 // ConstIterator end() const {
262 // return ConstIterator(*this, INVALID);
265 // /// The KeySet of the Map.
266 // typedef MapConstKeySet<ArrayMap> ConstKeySet;
268 // /// KeySet getter function.
269 // ConstKeySet keySet() const {
270 // return ConstKeySet(*this);
273 // /// The ConstValueSet of the Map.
274 // typedef MapConstValueSet<ArrayMap> ConstValueSet;
276 // /// ConstValueSet getter function.
277 // ConstValueSet valueSet() const {
278 // return ConstValueSet(*this);
281 // /// The ValueSet of the Map.
282 // typedef MapValueSet<ArrayMap> ValueSet;
284 // /// ValueSet getter function.
285 // ValueSet valueSet() {
286 // return ValueSet(*this);
291 void allocate_memory() {
292 int max_id = graph->maxId(_Item());
299 while (capacity <= max_id) {
302 values = allocator.allocate(capacity);
312 template <typename _Base>
313 class ArrayMappableGraphExtender : public _Base {
316 typedef ArrayMappableGraphExtender<_Base> Graph;
317 typedef _Base Parent;
319 typedef typename Parent::Node Node;
320 typedef typename Parent::NodeIt NodeIt;
321 typedef typename Parent::NodeNotifier NodeObserverRegistry;
323 typedef typename Parent::Edge Edge;
324 typedef typename Parent::EdgeIt EdgeIt;
325 typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
329 template <typename _Value>
331 : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
333 typedef ArrayMappableGraphExtender<_Base> Graph;
335 typedef typename Graph::Node Node;
336 typedef typename Graph::NodeIt NodeIt;
338 typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
340 //typedef typename Parent::Graph Graph;
341 typedef typename Parent::Value Value;
343 NodeMap(const Graph& g)
345 NodeMap(const Graph& g, const Value& v)
350 template <typename _Value>
352 : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
354 typedef ArrayMappableGraphExtender<_Base> Graph;
356 typedef typename Graph::Edge Edge;
357 typedef typename Graph::EdgeIt EdgeIt;
359 typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
361 //typedef typename Parent::Graph Graph;
362 typedef typename Parent::Value Value;
364 EdgeMap(const Graph& g)
366 EdgeMap(const Graph& g, const Value& v)
377 #endif //LEMON_ARRAY_MAP_H