1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/bits/array_map.h Tue Apr 05 12:30:46 2005 +0000
1.3 @@ -0,0 +1,377 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_ARRAY_MAP_H
1.21 +#define LEMON_ARRAY_MAP_H
1.22 +
1.23 +#include <memory>
1.24 +#include <lemon/bits/map_iterator.h>
1.25 +
1.26 +///\ingroup graphmaps
1.27 +///\file
1.28 +///\brief Graph maps that construates and destruates
1.29 +///their elements dynamically.
1.30 +
1.31 +namespace lemon {
1.32 +
1.33 +
1.34 + /// \addtogroup graphmaps
1.35 + /// @{
1.36 +
1.37 + /** The ArrayMap template class is graph map structure what
1.38 + * automatically updates the map when a key is added to or erased from
1.39 + * the map. This map factory uses the allocators to implement
1.40 + * the container functionality.
1.41 + *
1.42 + * The template parameter is the AlterationNotifier that the maps
1.43 + * will belong to and the Value.
1.44 + */
1.45 +
1.46 + template <typename _Graph,
1.47 + typename _Item,
1.48 + typename _Value>
1.49 + class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
1.50 +
1.51 + typedef _Item Item;
1.52 + public:
1.53 +
1.54 + /// The graph type of the maps.
1.55 + typedef _Graph Graph;
1.56 + /// The key type of the maps.
1.57 + typedef _Item Key;
1.58 +
1.59 + typedef AlterationNotifier<_Item> Registry;
1.60 +
1.61 + /// The MapBase of the Map which imlements the core regisitry function.
1.62 + typedef typename Registry::ObserverBase Parent;
1.63 +
1.64 + /// The value type of the map.
1.65 + typedef _Value Value;
1.66 +
1.67 +
1.68 + private:
1.69 + typedef std::allocator<Value> Allocator;
1.70 +
1.71 +
1.72 + public:
1.73 +
1.74 + /** Graph and Registry initialized map constructor.
1.75 + */
1.76 + ArrayMap(const Graph& _g) : graph(&_g) {
1.77 + Item it;
1.78 + attach(_g.getNotifier(Item()));
1.79 + allocate_memory();
1.80 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.81 + int id = graph->id(it);;
1.82 + allocator.construct(&(values[id]), Value());
1.83 + }
1.84 + }
1.85 +
1.86 + /// Constructor to use default value to initialize the map.
1.87 +
1.88 + /// It constrates a map and initialize all of the the map.
1.89 +
1.90 + ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
1.91 + Item it;
1.92 + attach(_g.getNotifier(_Item()));
1.93 + allocate_memory();
1.94 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.95 + int id = graph->id(it);;
1.96 + allocator.construct(&(values[id]), _v);
1.97 + }
1.98 + }
1.99 +
1.100 + /** Constructor to copy a map of the same map type.
1.101 + */
1.102 + ArrayMap(const ArrayMap& copy) {
1.103 + if (copy.attached()) {
1.104 + attach(*copy.getRegistry());
1.105 + }
1.106 + capacity = copy.capacity;
1.107 + if (capacity == 0) return;
1.108 + values = allocator.allocate(capacity);
1.109 + Item it;
1.110 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.111 + int id = graph->id(it);;
1.112 + allocator.construct(&(values[id]), copy.values[id]);
1.113 + }
1.114 + }
1.115 +
1.116 + using Parent::attach;
1.117 + using Parent::detach;
1.118 + using Parent::attached;
1.119 +
1.120 + /** Assign operator to copy a map of the same map type.
1.121 + */
1.122 + ArrayMap& operator=(const ArrayMap& copy) {
1.123 + if (© == this) return *this;
1.124 +
1.125 + if (graph != copy.graph) {
1.126 + if (attached()) {
1.127 + clear();
1.128 + detach();
1.129 + }
1.130 + if (copy.attached()) {
1.131 + attach(*copy.getRegistry());
1.132 + }
1.133 + capacity = copy.capacity;
1.134 + if (capacity == 0) return *this;
1.135 + values = allocator.allocate(capacity);
1.136 + }
1.137 +
1.138 + Item it;
1.139 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.140 + int id = graph->id(it);;
1.141 + allocator.construct(&(values[id]), copy.values[id]);
1.142 + }
1.143 +
1.144 + return *this;
1.145 + }
1.146 +
1.147 + /** The destructor of the map.
1.148 + */
1.149 + virtual ~ArrayMap() {
1.150 + if (attached()) {
1.151 + clear();
1.152 + detach();
1.153 + }
1.154 + }
1.155 +
1.156 +
1.157 + /**
1.158 + * The subscript operator. The map can be subscripted by the
1.159 + * actual keys of the graph.
1.160 + */
1.161 + Value& operator[](const Key& key) {
1.162 + int id = graph->id(key);
1.163 + return values[id];
1.164 + }
1.165 +
1.166 + /**
1.167 + * The const subscript operator. The map can be subscripted by the
1.168 + * actual keys of the graph.
1.169 + */
1.170 + const Value& operator[](const Key& key) const {
1.171 + int id = graph->id(key);
1.172 + return values[id];
1.173 + }
1.174 +
1.175 + /** Setter function of the map. Equivalent with map[key] = val.
1.176 + * This is a compatibility feature with the not dereferable maps.
1.177 + */
1.178 + void set(const Key& key, const Value& val) {
1.179 + (*this)[key] = val;
1.180 + }
1.181 +
1.182 + /** Add a new key to the map. It called by the map registry.
1.183 + */
1.184 + void add(const Key& key) {
1.185 + int id = graph->id(key);
1.186 + if (id >= capacity) {
1.187 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.188 + while (new_capacity <= id) {
1.189 + new_capacity <<= 1;
1.190 + }
1.191 + Value* new_values = allocator.allocate(new_capacity);
1.192 + Item it;
1.193 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.194 + int jd = graph->id(it);;
1.195 + if (id != jd) {
1.196 + allocator.construct(&(new_values[jd]), values[jd]);
1.197 + allocator.destroy(&(values[jd]));
1.198 + }
1.199 + }
1.200 + if (capacity != 0) allocator.deallocate(values, capacity);
1.201 + values = new_values;
1.202 + capacity = new_capacity;
1.203 + }
1.204 + allocator.construct(&(values[id]), Value());
1.205 + }
1.206 +
1.207 + /** Erase a key from the map. It called by the map registry.
1.208 + */
1.209 + void erase(const Key& key) {
1.210 + int id = graph->id(key);
1.211 + allocator.destroy(&(values[id]));
1.212 + }
1.213 +
1.214 + void build() {
1.215 + allocate_memory();
1.216 + Item it;
1.217 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.218 + int id = graph->id(it);;
1.219 + allocator.construct(&(values[id]), Value());
1.220 + }
1.221 + }
1.222 +
1.223 + void clear() {
1.224 + if (capacity != 0) {
1.225 + Item it;
1.226 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.227 + int id = graph->id(it);;
1.228 + allocator.destroy(&(values[id]));
1.229 + }
1.230 + allocator.deallocate(values, capacity);
1.231 + capacity = 0;
1.232 + }
1.233 + }
1.234 +
1.235 + const Graph* getGraph() {
1.236 + return graph;
1.237 + }
1.238 +
1.239 +// /// The stl compatible pair iterator of the map.
1.240 +// typedef MapIterator<ArrayMap> Iterator;
1.241 +// /// The stl compatible const pair iterator of the map.
1.242 +// typedef MapConstIterator<ArrayMap> ConstIterator;
1.243 +
1.244 +// /** Returns the begin iterator of the map.
1.245 +// */
1.246 +// Iterator begin() {
1.247 +// return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.248 +// }
1.249 +
1.250 +// /** Returns the end iterator of the map.
1.251 +// */
1.252 +// Iterator end() {
1.253 +// return Iterator(*this, INVALID);
1.254 +// }
1.255 +
1.256 +// /** Returns the begin ConstIterator of the map.
1.257 +// */
1.258 +// ConstIterator begin() const {
1.259 +// return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.260 +// }
1.261 +
1.262 +// /** Returns the end const_iterator of the map.
1.263 +// */
1.264 +// ConstIterator end() const {
1.265 +// return ConstIterator(*this, INVALID);
1.266 +// }
1.267 +
1.268 +// /// The KeySet of the Map.
1.269 +// typedef MapConstKeySet<ArrayMap> ConstKeySet;
1.270 +
1.271 +// /// KeySet getter function.
1.272 +// ConstKeySet keySet() const {
1.273 +// return ConstKeySet(*this);
1.274 +// }
1.275 +
1.276 +// /// The ConstValueSet of the Map.
1.277 +// typedef MapConstValueSet<ArrayMap> ConstValueSet;
1.278 +
1.279 +// /// ConstValueSet getter function.
1.280 +// ConstValueSet valueSet() const {
1.281 +// return ConstValueSet(*this);
1.282 +// }
1.283 +
1.284 +// /// The ValueSet of the Map.
1.285 +// typedef MapValueSet<ArrayMap> ValueSet;
1.286 +
1.287 +// /// ValueSet getter function.
1.288 +// ValueSet valueSet() {
1.289 +// return ValueSet(*this);
1.290 +// }
1.291 +
1.292 + private:
1.293 +
1.294 + void allocate_memory() {
1.295 + int max_id = graph->maxId(_Item());
1.296 + if (max_id == -1) {
1.297 + capacity = 0;
1.298 + values = 0;
1.299 + return;
1.300 + }
1.301 + capacity = 1;
1.302 + while (capacity <= max_id) {
1.303 + capacity <<= 1;
1.304 + }
1.305 + values = allocator.allocate(capacity);
1.306 + }
1.307 +
1.308 + const Graph* graph;
1.309 + int capacity;
1.310 + Value* values;
1.311 + Allocator allocator;
1.312 +
1.313 + };
1.314 +
1.315 + template <typename _Base>
1.316 + class ArrayMappableGraphExtender : public _Base {
1.317 + public:
1.318 +
1.319 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.320 + typedef _Base Parent;
1.321 +
1.322 + typedef typename Parent::Node Node;
1.323 + typedef typename Parent::NodeIt NodeIt;
1.324 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
1.325 +
1.326 + typedef typename Parent::Edge Edge;
1.327 + typedef typename Parent::EdgeIt EdgeIt;
1.328 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
1.329 +
1.330 +
1.331 +
1.332 + template <typename _Value>
1.333 + class NodeMap
1.334 + : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
1.335 + public:
1.336 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.337 +
1.338 + typedef typename Graph::Node Node;
1.339 + typedef typename Graph::NodeIt NodeIt;
1.340 +
1.341 + typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
1.342 +
1.343 + //typedef typename Parent::Graph Graph;
1.344 + typedef typename Parent::Value Value;
1.345 +
1.346 + NodeMap(const Graph& g)
1.347 + : Parent(g) {}
1.348 + NodeMap(const Graph& g, const Value& v)
1.349 + : Parent(g, v) {}
1.350 +
1.351 + };
1.352 +
1.353 + template <typename _Value>
1.354 + class EdgeMap
1.355 + : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
1.356 + public:
1.357 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.358 +
1.359 + typedef typename Graph::Edge Edge;
1.360 + typedef typename Graph::EdgeIt EdgeIt;
1.361 +
1.362 + typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
1.363 +
1.364 + //typedef typename Parent::Graph Graph;
1.365 + typedef typename Parent::Value Value;
1.366 +
1.367 + EdgeMap(const Graph& g)
1.368 + : Parent(g) {}
1.369 + EdgeMap(const Graph& g, const Value& v)
1.370 + : Parent(g, v) {}
1.371 +
1.372 + };
1.373 +
1.374 + };
1.375 +
1.376 +/// @}
1.377 +
1.378 +}
1.379 +
1.380 +#endif //LEMON_ARRAY_MAP_H