1.1 --- a/src/work/deba/array_map_factory.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,355 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef ARRAY_MAP_H
1.6 -#define ARRAY_MAP_H
1.7 -
1.8 -#include <memory>
1.9 -
1.10 -#include "extended_pair.h"
1.11 -
1.12 -namespace lemon {
1.13 -
1.14 - template <typename MapRegistry> class ArrayMapFactory {
1.15 -
1.16 - public:
1.17 -
1.18 - typedef typename MapRegistry::Graph Graph;
1.19 - typedef typename MapRegistry::Key Key;
1.20 - typedef typename MapRegistry::KeyIt KeyIt;
1.21 -
1.22 - typedef typename MapRegistry::MapBase MapBase;
1.23 -
1.24 - template <typename V, typename A = std::allocator<V> >
1.25 - class Map : public MapBase {
1.26 -
1.27 - public:
1.28 -
1.29 - typedef V Value;
1.30 - typedef A Allocator;
1.31 -
1.32 -
1.33 - Map() : values(0), capacity(0) {}
1.34 -
1.35 - Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.36 - allocate_memory();
1.37 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.38 - int id = getGraph()->id(it);
1.39 - allocator.construct(&(values[id]), Value());
1.40 - }
1.41 - }
1.42 -
1.43 - Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
1.44 - allocate_memory();
1.45 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.46 - int id = getGraph()->id(it);
1.47 - allocator.construct(&(values[id]), v);
1.48 - }
1.49 - }
1.50 -
1.51 - Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
1.52 - capacity = copy.capacity;
1.53 - if (capacity == 0) return;
1.54 - values = allocator.allocate(capacity);
1.55 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.56 - int id = getGraph()->id(it);
1.57 - allocator.construct(&(values[id]), copy.values[id]);
1.58 - }
1.59 - }
1.60 -
1.61 - template <typename CMap> Map(const CMap& copy)
1.62 - : capacity(0), values(0), MapBase(copy) {
1.63 - if (getGraph()) {
1.64 - allocate_memory();
1.65 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.66 - set(it, copy[it]);
1.67 - }
1.68 - }
1.69 - }
1.70 -
1.71 - Map& operator=(const Map& copy) {
1.72 - if (© == this) return;
1.73 - if (capacity != 0) {
1.74 - destroy();
1.75 - allocator.deallocate(values, capacity);
1.76 - }
1.77 - capacity = copy.capacity;
1.78 - if (capacity == 0) return;
1.79 - values = allocator.allocate(capacity);
1.80 - for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.81 - int id = getGraph()->id(it);
1.82 - allocator.construct(&(values[id]), copy.values[id]);
1.83 - }
1.84 - }
1.85 -
1.86 - template <typename CMap> Map& operator=(const CMap& copy) {
1.87 - if (getGraph()) {
1.88 - destroy();
1.89 - }
1.90 - this->MapBase::operator=(copy);
1.91 - if (getGraph()) {
1.92 - allocate_memory();
1.93 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.94 - set(it, copy[it]);
1.95 - }
1.96 - }
1.97 - }
1.98 -
1.99 - virtual ~Map() {
1.100 - if (capacity != 0) {
1.101 - destroy();
1.102 - allocator.deallocate(values, capacity);
1.103 - }
1.104 - }
1.105 -
1.106 -
1.107 - Value& operator[](const Key& key) {
1.108 - int id = getGraph()->id(key);
1.109 - return values[id];
1.110 - }
1.111 -
1.112 - const Value& operator[](const Key& key) const {
1.113 - int id = getGraph()->id(key);
1.114 - return values[id];
1.115 - }
1.116 -
1.117 - const Value& get(const Key& key) const {
1.118 - int id = getGraph()->id(key);
1.119 - return values[id];
1.120 - }
1.121 -
1.122 - void set(const Key& key, const Value& val) {
1.123 - int id = getGraph()->id(key);
1.124 - values[id] = val;
1.125 - }
1.126 -
1.127 - void add(const Key& key) {
1.128 - int id = getGraph()->id(key);
1.129 - if (id >= capacity) {
1.130 - int new_capacity = (capacity == 0 ? 1 : capacity);
1.131 - while (new_capacity <= id) {
1.132 - new_capacity <<= 1;
1.133 - }
1.134 - Value* new_values = allocator.allocate(new_capacity);;
1.135 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.136 - int jd = getGraph()->id(it);
1.137 - if (id != jd) {
1.138 - allocator.construct(&(new_values[jd]), values[jd]);
1.139 - allocator.destroy(&(values[jd]));
1.140 - }
1.141 - }
1.142 - if (capacity != 0) allocator.deallocate(values, capacity);
1.143 - values = new_values;
1.144 - capacity = new_capacity;
1.145 - }
1.146 - allocator.construct(&(values[id]), Value());
1.147 - }
1.148 -
1.149 - void erase(const Key& key) {
1.150 - int id = getGraph()->id(key);
1.151 - allocator.destroy(&(values[id]));
1.152 - }
1.153 -
1.154 - class iterator {
1.155 - friend class Map;
1.156 - friend class const_iterator;
1.157 - private:
1.158 -
1.159 - /** Private constructor to initalize the the iterators returned
1.160 - * by the begin() and end().
1.161 - */
1.162 - iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.163 -
1.164 - public:
1.165 -
1.166 - /** Default constructor.
1.167 - */
1.168 - iterator() {}
1.169 -
1.170 - typedef extended_pair<const Key&, const Key&,
1.171 - Value&, Value&> Reference;
1.172 -
1.173 - /** Dereference operator for map.
1.174 - */
1.175 - Reference operator*() {
1.176 - return Reference(it, (*map)[it]);
1.177 - }
1.178 -
1.179 - class Pointer {
1.180 - friend class iterator;
1.181 - private:
1.182 - Reference data;
1.183 - Pointer(const Key& key, Value& val) : data(key, val) {}
1.184 - public:
1.185 - Reference* operator->() {return &data;}
1.186 - };
1.187 -
1.188 - /** Arrow operator for map.
1.189 - */
1.190 - Pointer operator->() {
1.191 - return Pointer(it, ((*map)[it]));
1.192 - }
1.193 -
1.194 - /** The pre increment operator of the map.
1.195 - */
1.196 - iterator& operator++() {
1.197 - map->getGraph()->next(it);
1.198 - return *this;
1.199 - }
1.200 -
1.201 - /** The post increment operator of the map.
1.202 - */
1.203 - iterator operator++(int) {
1.204 - iterator tmp(it);
1.205 - map.getGraph()->next(it);
1.206 - return tmp;
1.207 - }
1.208 -
1.209 - /** The equality operator of the map.
1.210 - */
1.211 - bool operator==(const_iterator p_it) {
1.212 - return p_it.it == it;
1.213 - }
1.214 -
1.215 - /** The not-equality operator of the map.
1.216 - */
1.217 - bool operator!=(const_iterator p_it) {
1.218 - return !(*this == p_it);
1.219 - }
1.220 -
1.221 -
1.222 - private:
1.223 - Map* map;
1.224 - KeyIt it;
1.225 - };
1.226 -
1.227 - /** Returns the begin iterator of the map.
1.228 - */
1.229 - iterator begin() {
1.230 - return iterator(*this, KeyIt(*getGraph()));
1.231 - }
1.232 -
1.233 - /** Returns the end iterator of the map.
1.234 - */
1.235 - iterator end() {
1.236 - return iterator(*this, INVALID);
1.237 - }
1.238 -
1.239 - class const_iterator {
1.240 - friend class Map;
1.241 - friend class iterator;
1.242 - private:
1.243 -
1.244 - /** Private constructor to initalize the the iterators returned
1.245 - * by the begin() and end().
1.246 - */
1.247 - const_iterator (const Map& pmap, const KeyIt& pit)
1.248 - : map(&pmap), it(pit) {}
1.249 -
1.250 - public:
1.251 -
1.252 - /** Default constructor.
1.253 - */
1.254 - const_iterator() {}
1.255 -
1.256 - /** Constructor to convert iterator to const_iterator.
1.257 - */
1.258 - const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
1.259 -
1.260 - typedef extended_pair<const Key&, const Key&,
1.261 - const Value&, const Value&> Reference;
1.262 -
1.263 - /** Dereference operator for map.
1.264 - */
1.265 - Reference operator*() {
1.266 - return Reference(it, (*map)[it]);
1.267 - }
1.268 -
1.269 -
1.270 - class Pointer {
1.271 - friend class const_iterator;
1.272 - private:
1.273 - Reference data;
1.274 - Pointer(const Key& key, const Value& val) : data(key, val) {}
1.275 - public:
1.276 - Reference* operator->() {return &data;}
1.277 - };
1.278 -
1.279 - /** Arrow operator for map.
1.280 - */
1.281 - Pointer operator->() {
1.282 - return Pointer(it, ((*map)[it]));
1.283 - }
1.284 -
1.285 - /** The pre increment operator of the map.
1.286 - */
1.287 - const_iterator& operator++() {
1.288 - map->getGraph()->next(it);
1.289 - return *this;
1.290 - }
1.291 -
1.292 - /** The post increment operator of the map.
1.293 - */
1.294 - const_iterator operator++(int) {
1.295 - const_iterator tmp(it);
1.296 - map->getGraph()->next(it);
1.297 - return tmp;
1.298 - }
1.299 -
1.300 - /** The equality operator of the map.
1.301 - */
1.302 - bool operator==(const_iterator p_it) {
1.303 - return p_it.it == it;
1.304 - }
1.305 -
1.306 - /** The not-equality operator of the map.
1.307 - */
1.308 - bool operator!=(const_iterator p_it) {
1.309 - return !(*this == p_it);
1.310 - }
1.311 -
1.312 -
1.313 - private:
1.314 - const Map* map;
1.315 - KeyIt it;
1.316 - };
1.317 -
1.318 - /** Returns the begin const_iterator of the map.
1.319 - */
1.320 - const_iterator begin() const {
1.321 - return const_iterator(*this, KeyIt(*getGraph()));
1.322 - }
1.323 -
1.324 - /** Returns the end const_iterator of the map.
1.325 - */
1.326 - const_iterator end() const {
1.327 - return const_iterator(*this, INVALID);
1.328 - }
1.329 -
1.330 - private:
1.331 -
1.332 - void allocate_memory() {
1.333 - int max_id = -1;
1.334 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.335 - int id = getGraph()->id(it);
1.336 - if (id > max_id) {
1.337 - max_id = id;
1.338 - }
1.339 - }
1.340 - if (max_id == -1) {
1.341 - capacity = 0;
1.342 - values = 0;
1.343 - return;
1.344 - }
1.345 - capacity = 1;
1.346 - while (capacity <= max_id) {
1.347 - capacity <<= 1;
1.348 - }
1.349 - values = allocator.allocate(capacity);
1.350 - }
1.351 - int capacity;
1.352 - Value* values;
1.353 - Allocator allocator;
1.354 - };
1.355 - };
1.356 -}
1.357 -
1.358 -#endif