1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/array_map.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,369 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/bits/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 Research Group on Combinatorial Optimization, 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) : Parent() {
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 + ///The subscript operator. The map can be subscripted by the
1.158 + ///actual keys of the graph.
1.159 +
1.160 + Value& operator[](const Key& key) {
1.161 + int id = graph->id(key);
1.162 + return values[id];
1.163 + }
1.164 +
1.165 +
1.166 + ///The const subscript operator. The map can be subscripted by the
1.167 + ///actual keys of the graph.
1.168 +
1.169 + const Value& operator[](const Key& key) const {
1.170 + int id = graph->id(key);
1.171 + return values[id];
1.172 + }
1.173 +
1.174 + /// Setter function of the map. Equivalent with map[key] = val.
1.175 + /// This is a compatibility feature with the not dereferable maps.
1.176 +
1.177 + void set(const Key& key, const Value& val) {
1.178 + (*this)[key] = val;
1.179 + }
1.180 +
1.181 + /// Add a new key to the map. It called by the map registry.
1.182 +
1.183 + void add(const Key& key) {
1.184 + int id = graph->id(key);
1.185 + if (id >= capacity) {
1.186 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.187 + while (new_capacity <= id) {
1.188 + new_capacity <<= 1;
1.189 + }
1.190 + Value* new_values = allocator.allocate(new_capacity);
1.191 + Item it;
1.192 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.193 + int jd = graph->id(it);;
1.194 + if (id != jd) {
1.195 + allocator.construct(&(new_values[jd]), values[jd]);
1.196 + allocator.destroy(&(values[jd]));
1.197 + }
1.198 + }
1.199 + if (capacity != 0) allocator.deallocate(values, capacity);
1.200 + values = new_values;
1.201 + capacity = new_capacity;
1.202 + }
1.203 + allocator.construct(&(values[id]), Value());
1.204 + }
1.205 +
1.206 + void add(const std::vector<Key>& keys) {
1.207 + int max_id = -1;
1.208 + for (int i = 0; i < (int)keys.size(); ++i) {
1.209 + int id = graph->id(keys[i]);
1.210 + if (id > max_id) {
1.211 + max_id = id;
1.212 + }
1.213 + }
1.214 + if (max_id >= capacity) {
1.215 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.216 + while (new_capacity <= max_id) {
1.217 + new_capacity <<= 1;
1.218 + }
1.219 + Value* new_values = allocator.allocate(new_capacity);
1.220 + Item it;
1.221 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.222 + int id = graph->id(it);
1.223 + bool found = false;
1.224 + for (int i = 0; i < (int)keys.size(); ++i) {
1.225 + int jd = graph->id(keys[i]);
1.226 + if (id == jd) {
1.227 + found = true;
1.228 + break;
1.229 + }
1.230 + }
1.231 + if (found) continue;
1.232 + allocator.construct(&(new_values[id]), values[id]);
1.233 + allocator.destroy(&(values[id]));
1.234 + }
1.235 + if (capacity != 0) allocator.deallocate(values, capacity);
1.236 + values = new_values;
1.237 + capacity = new_capacity;
1.238 + }
1.239 + for (int i = 0; i < (int)keys.size(); ++i) {
1.240 + int id = graph->id(keys[i]);
1.241 + allocator.construct(&(values[id]), Value());
1.242 + }
1.243 + }
1.244 +
1.245 + /// Erase a key from the map. It called by the map registry.
1.246 +
1.247 + void erase(const Key& key) {
1.248 + int id = graph->id(key);
1.249 + allocator.destroy(&(values[id]));
1.250 + }
1.251 +
1.252 + void erase(const std::vector<Key>& keys) {
1.253 + for (int i = 0; i < (int)keys.size(); ++i) {
1.254 + int id = graph->id(keys[i]);
1.255 + allocator.destroy(&(values[id]));
1.256 + }
1.257 + }
1.258 +
1.259 + void build() {
1.260 + allocate_memory();
1.261 + Item it;
1.262 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.263 + int id = graph->id(it);;
1.264 + allocator.construct(&(values[id]), Value());
1.265 + }
1.266 + }
1.267 +
1.268 + void clear() {
1.269 + if (capacity != 0) {
1.270 + Item it;
1.271 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.272 + int id = graph->id(it);
1.273 + allocator.destroy(&(values[id]));
1.274 + }
1.275 + allocator.deallocate(values, capacity);
1.276 + capacity = 0;
1.277 + }
1.278 + }
1.279 +
1.280 + const Graph* getGraph() {
1.281 + return graph;
1.282 + }
1.283 +
1.284 + private:
1.285 +
1.286 + void allocate_memory() {
1.287 + int max_id = graph->maxId(_Item());
1.288 + if (max_id == -1) {
1.289 + capacity = 0;
1.290 + values = 0;
1.291 + return;
1.292 + }
1.293 + capacity = 1;
1.294 + while (capacity <= max_id) {
1.295 + capacity <<= 1;
1.296 + }
1.297 + values = allocator.allocate(capacity);
1.298 + }
1.299 +
1.300 + const Graph* graph;
1.301 + int capacity;
1.302 + Value* values;
1.303 + Allocator allocator;
1.304 +
1.305 + };
1.306 +
1.307 + template <typename _Base>
1.308 + class ArrayMappableGraphExtender : public _Base {
1.309 + public:
1.310 +
1.311 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.312 + typedef _Base Parent;
1.313 +
1.314 + typedef typename Parent::Node Node;
1.315 + typedef typename Parent::NodeIt NodeIt;
1.316 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
1.317 +
1.318 + typedef typename Parent::Edge Edge;
1.319 + typedef typename Parent::EdgeIt EdgeIt;
1.320 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
1.321 +
1.322 +
1.323 +
1.324 + template <typename _Value>
1.325 + class NodeMap
1.326 + : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
1.327 + public:
1.328 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.329 +
1.330 + typedef typename Graph::Node Node;
1.331 + typedef typename Graph::NodeIt NodeIt;
1.332 +
1.333 + typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
1.334 +
1.335 + //typedef typename Parent::Graph Graph;
1.336 + typedef typename Parent::Value Value;
1.337 +
1.338 + NodeMap(const Graph& g)
1.339 + : Parent(g) {}
1.340 + NodeMap(const Graph& g, const Value& v)
1.341 + : Parent(g, v) {}
1.342 +
1.343 + };
1.344 +
1.345 + template <typename _Value>
1.346 + class EdgeMap
1.347 + : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
1.348 + public:
1.349 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.350 +
1.351 + typedef typename Graph::Edge Edge;
1.352 + typedef typename Graph::EdgeIt EdgeIt;
1.353 +
1.354 + typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
1.355 +
1.356 + //typedef typename Parent::Graph Graph;
1.357 + typedef typename Parent::Value Value;
1.358 +
1.359 + EdgeMap(const Graph& g)
1.360 + : Parent(g) {}
1.361 + EdgeMap(const Graph& g, const Value& v)
1.362 + : Parent(g, v) {}
1.363 +
1.364 + };
1.365 +
1.366 + };
1.367 +
1.368 +/// @}
1.369 +
1.370 +}
1.371 +
1.372 +#endif //LEMON_ARRAY_MAP_H