1.1 --- a/src/lemon/bits/array_map.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,369 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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