1.1 --- a/src/hugo/array_map_factory.h Wed Sep 08 11:58:06 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,444 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef ARRAY_MAP_FACTORY_H
1.6 -#define ARRAY_MAP_FACTORY_H
1.7 -
1.8 -#include <memory>
1.9 -
1.10 -#include <hugo/extended_pair.h>
1.11 -
1.12 -///\ingroup graphmapfactory
1.13 -///\file
1.14 -///\brief Graph maps that construates and destruates
1.15 -///their elements dynamically.
1.16 -
1.17 -namespace hugo {
1.18 -
1.19 -
1.20 -/// \addtogroup graphmapfactory
1.21 -/// @{
1.22 -
1.23 - /** The ArrayMapFactory template class is a factory class
1.24 - * to create maps for the edge and nodes. This map factory
1.25 - * uses the allocators to implement the container function.
1.26 - *
1.27 - * The template parameter is the MapRegistry that the maps
1.28 - * will belong to.
1.29 - */
1.30 -
1.31 - template <typename MapRegistry>
1.32 - class ArrayMapFactory {
1.33 -
1.34 - public:
1.35 -
1.36 - /// The graph type of the maps.
1.37 - typedef typename MapRegistry::Graph Graph;
1.38 - /// The key type of the maps.
1.39 - typedef typename MapRegistry::KeyType KeyType;
1.40 - /// The iterator to iterate on the keys.
1.41 - typedef typename MapRegistry::KeyIt KeyIt;
1.42 -
1.43 - /// The MapBase of the Map which imlements the core regisitry function.
1.44 - typedef typename MapRegistry::MapBase MapBase;
1.45 -
1.46 - /** The template Map type.
1.47 - */
1.48 - template <typename V, typename A = std::allocator<V> >
1.49 - class Map : public MapBase {
1.50 -
1.51 - public:
1.52 -
1.53 - /// The value type of the map.
1.54 - typedef V ValueType;
1.55 -
1.56 - /// The value type of the map.
1.57 - typedef V Value;
1.58 - /// The reference type of the map;
1.59 - typedef Value& Reference;
1.60 - /// The pointer type of the map;
1.61 - typedef Value* Pointer;
1.62 -
1.63 - /// The const value type of the map.
1.64 - typedef const Value ConstValue;
1.65 - /// The const reference type of the map;
1.66 - typedef const Value& ConstReference;
1.67 - /// The pointer type of the map;
1.68 - typedef const Value* ConstPointer;
1.69 -
1.70 -
1.71 - typedef A Allocator;
1.72 -
1.73 -
1.74 - /** Default constructor for the map.
1.75 - */
1.76 - Map() : values(0), capacity(0) {}
1.77 -
1.78 - /** Graph and Registry initialized map constructor.
1.79 - */
1.80 - Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.81 - allocate_memory();
1.82 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.83 - int id = MapBase::getGraph()->id(it);
1.84 - allocator.construct(&(values[id]), Value());
1.85 - }
1.86 - }
1.87 -
1.88 - /** Constructor to use default value to initialize the map.
1.89 - */
1.90 - Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
1.91 - allocate_memory();
1.92 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.93 - int id = MapBase::getGraph()->id(it);
1.94 - allocator.construct(&(values[id]), v);
1.95 - }
1.96 - }
1.97 -
1.98 - /** Constructor to copy a map of the same map type.
1.99 - */
1.100 - Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
1.101 - capacity = copy.capacity;
1.102 - if (capacity == 0) return;
1.103 - values = allocator.allocate(capacity);
1.104 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.105 - int id = MapBase::getGraph()->id(it);
1.106 - allocator.construct(&(values[id]), copy.values[id]);
1.107 - }
1.108 - }
1.109 -
1.110 - /** Constructor to copy a map of an other map type.
1.111 - */
1.112 - template <typename CMap> Map(const CMap& copy)
1.113 - : MapBase(copy), capacity(0), values(0) {
1.114 - if (MapBase::getGraph()) {
1.115 - allocate_memory();
1.116 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.117 - set(it, copy[it]);
1.118 - }
1.119 - }
1.120 - }
1.121 -
1.122 - /** Assign operator to copy a map of the same map type.
1.123 - */
1.124 - Map& operator=(const Map& copy) {
1.125 - if (© == this) return *this;
1.126 - if (capacity != 0) {
1.127 - MapBase::destroy();
1.128 - allocator.deallocate(values, capacity);
1.129 - }
1.130 - capacity = copy.capacity;
1.131 - if (capacity == 0) return *this;
1.132 - values = allocator.allocate(capacity);
1.133 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.134 - int id = MapBase::getGraph()->id(it);
1.135 - allocator.construct(&(values[id]), copy.values[id]);
1.136 - }
1.137 - return *this;
1.138 - }
1.139 -
1.140 - /** Assign operator to copy a map an other map type.
1.141 - */
1.142 - template <typename CMap> Map& operator=(const CMap& copy) {
1.143 - if (MapBase::getGraph()) {
1.144 - MapBase::destroy();
1.145 - }
1.146 - MapBase::operator=(copy);
1.147 - if (MapBase::getGraph()) {
1.148 - allocate_memory();
1.149 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.150 - set(it, copy[it]);
1.151 - }
1.152 - }
1.153 - return *this;
1.154 - }
1.155 -
1.156 - /** The destructor of the map.
1.157 - */
1.158 - virtual ~Map() {
1.159 - if (capacity != 0) {
1.160 - MapBase::destroy();
1.161 - allocator.deallocate(values, capacity);
1.162 - }
1.163 - }
1.164 -
1.165 -
1.166 - /**
1.167 - * The subscript operator. The map can be subscripted by the
1.168 - * actual keys of the graph.
1.169 - */
1.170 - Value& operator[](const KeyType& key) {
1.171 - int id = MapBase::getGraph()->id(key);
1.172 - return values[id];
1.173 - }
1.174 -
1.175 - /**
1.176 - * The const subscript operator. The map can be subscripted by the
1.177 - * actual keys of the graph.
1.178 - */
1.179 - const Value& operator[](const KeyType& key) const {
1.180 - int id = MapBase::getGraph()->id(key);
1.181 - return values[id];
1.182 - }
1.183 -
1.184 - /** Setter function of the map. Equivalent with map[key] = val.
1.185 - * This is a compatibility feature with the not dereferable maps.
1.186 - */
1.187 - void set(const KeyType& key, const Value& val) {
1.188 - int id = MapBase::getGraph()->id(key);
1.189 - values[id] = val;
1.190 - }
1.191 -
1.192 - /** Add a new key to the map. It called by the map registry.
1.193 - */
1.194 - void add(const KeyType& key) {
1.195 - int id = MapBase::getGraph()->id(key);
1.196 - if (id >= capacity) {
1.197 - int new_capacity = (capacity == 0 ? 1 : capacity);
1.198 - while (new_capacity <= id) {
1.199 - new_capacity <<= 1;
1.200 - }
1.201 - Value* new_values = allocator.allocate(new_capacity);;
1.202 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.203 - int jd = MapBase::getGraph()->id(it);
1.204 - if (id != jd) {
1.205 - allocator.construct(&(new_values[jd]), values[jd]);
1.206 - allocator.destroy(&(values[jd]));
1.207 - }
1.208 - }
1.209 - if (capacity != 0) allocator.deallocate(values, capacity);
1.210 - values = new_values;
1.211 - capacity = new_capacity;
1.212 - }
1.213 - allocator.construct(&(values[id]), Value());
1.214 - }
1.215 -
1.216 - /** Erase a key from the map. It called by the map registry.
1.217 - */
1.218 - void erase(const KeyType& key) {
1.219 - int id = MapBase::getGraph()->id(key);
1.220 - allocator.destroy(&(values[id]));
1.221 - }
1.222 -
1.223 - /** Clear the data structure.
1.224 - */
1.225 - void clear() {
1.226 - if (capacity != 0) {
1.227 - MapBase::destroy();
1.228 - allocator.deallocate(values, capacity);
1.229 - capacity = 0;
1.230 - }
1.231 - }
1.232 -
1.233 - class iterator;
1.234 - class const_iterator;
1.235 -
1.236 - /** Compatible iterator with the stl maps' iterators.
1.237 - * It iterates on pairs of a key and a value.
1.238 - */
1.239 - class iterator {
1.240 - friend class Map;
1.241 - friend class const_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 - iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.248 -
1.249 - public:
1.250 -
1.251 - /** Default constructor.
1.252 - */
1.253 - iterator() {}
1.254 -
1.255 - typedef extended_pair<const KeyType&, const KeyType&,
1.256 - Value&, Value&> Reference;
1.257 -
1.258 - /** Dereference operator for map.
1.259 - */
1.260 - Reference operator*() {
1.261 - return Reference(it, (*map)[it]);
1.262 - }
1.263 -
1.264 - class Pointer {
1.265 - friend class iterator;
1.266 - private:
1.267 - Reference data;
1.268 - Pointer(const KeyType& key, Value& val) : data(key, val) {}
1.269 - public:
1.270 - Reference* operator->() {return &data;}
1.271 - };
1.272 -
1.273 - /** Arrow operator for map.
1.274 - */
1.275 - Pointer operator->() {
1.276 - return Pointer(it, ((*map)[it]));
1.277 - }
1.278 -
1.279 - /** The pre increment operator of the map.
1.280 - */
1.281 - iterator& operator++() {
1.282 - ++it;
1.283 - return *this;
1.284 - }
1.285 -
1.286 - /** The post increment operator of the map.
1.287 - */
1.288 - iterator operator++(int) {
1.289 - iterator tmp(it);
1.290 - ++it;
1.291 - return tmp;
1.292 - }
1.293 -
1.294 - /** The equality operator of the map.
1.295 - */
1.296 - bool operator==(const_iterator p_it) {
1.297 - return p_it.it == it;
1.298 - }
1.299 -
1.300 - /** The not-equality operator of the map.
1.301 - */
1.302 - bool operator!=(const_iterator p_it) {
1.303 - return !(*this == p_it);
1.304 - }
1.305 -
1.306 -
1.307 - private:
1.308 - Map* map;
1.309 - KeyIt it;
1.310 - };
1.311 -
1.312 - /** Returns the begin iterator of the map.
1.313 - */
1.314 - iterator begin() {
1.315 - return iterator(*this, KeyIt(*MapBase::getGraph()));
1.316 - }
1.317 -
1.318 - /** Returns the end iterator of the map.
1.319 - */
1.320 - iterator end() {
1.321 - return iterator(*this, INVALID);
1.322 - }
1.323 -
1.324 - class const_iterator {
1.325 - friend class Map;
1.326 - friend class iterator;
1.327 - private:
1.328 -
1.329 - /** Private constructor to initalize the the iterators returned
1.330 - * by the begin() and end().
1.331 - */
1.332 - const_iterator (const Map& pmap, const KeyIt& pit)
1.333 - : map(&pmap), it(pit) {}
1.334 -
1.335 - public:
1.336 -
1.337 - /** Default constructor.
1.338 - */
1.339 - const_iterator() {}
1.340 -
1.341 - /** Constructor to convert iterator to const_iterator.
1.342 - */
1.343 - const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
1.344 -
1.345 - typedef extended_pair<const KeyType&, const KeyType&,
1.346 - const Value&, const Value&> Reference;
1.347 -
1.348 - /** Dereference operator for map.
1.349 - */
1.350 - Reference operator*() {
1.351 - return Reference(it, (*map)[it]);
1.352 - }
1.353 -
1.354 -
1.355 - class Pointer {
1.356 - friend class const_iterator;
1.357 - private:
1.358 - Reference data;
1.359 - Pointer(const KeyType& key, const Value& val) : data(key, val) {}
1.360 - public:
1.361 - Reference* operator->() {return &data;}
1.362 - };
1.363 -
1.364 - /** Arrow operator for map.
1.365 - */
1.366 - Pointer operator->() {
1.367 - return Pointer(it, ((*map)[it]));
1.368 - }
1.369 -
1.370 - /** The pre increment operator of the map.
1.371 - */
1.372 - const_iterator& operator++() {
1.373 - ++it;
1.374 - return *this;
1.375 - }
1.376 -
1.377 - /** The post increment operator of the map.
1.378 - */
1.379 - const_iterator operator++(int) {
1.380 - const_iterator tmp(it);
1.381 - ++it;
1.382 - return tmp;
1.383 - }
1.384 -
1.385 - /** The equality operator of the map.
1.386 - */
1.387 - bool operator==(const_iterator p_it) {
1.388 - return p_it.it == it;
1.389 - }
1.390 -
1.391 - /** The not-equality operator of the map.
1.392 - */
1.393 - bool operator!=(const_iterator p_it) {
1.394 - return !(*this == p_it);
1.395 - }
1.396 -
1.397 -
1.398 - private:
1.399 - const Map* map;
1.400 - KeyIt it;
1.401 - };
1.402 -
1.403 - /** Returns the begin const_iterator of the map.
1.404 - */
1.405 - const_iterator begin() const {
1.406 - return const_iterator(*this, KeyIt(*MapBase::getGraph()));
1.407 - }
1.408 -
1.409 - /** Returns the end const_iterator of the map.
1.410 - */
1.411 - const_iterator end() const {
1.412 - return const_iterator(*this, INVALID);
1.413 - }
1.414 -
1.415 - private:
1.416 -
1.417 - void allocate_memory() {
1.418 - int max_id = -1;
1.419 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.420 - int id = MapBase::getGraph()->id(it);
1.421 - if (id > max_id) {
1.422 - max_id = id;
1.423 - }
1.424 - }
1.425 - if (max_id == -1) {
1.426 - capacity = 0;
1.427 - values = 0;
1.428 - return;
1.429 - }
1.430 - capacity = 1;
1.431 - while (capacity <= max_id) {
1.432 - capacity <<= 1;
1.433 - }
1.434 - values = allocator.allocate(capacity);
1.435 - }
1.436 -
1.437 - int capacity;
1.438 - Value* values;
1.439 - Allocator allocator;
1.440 - };
1.441 - };
1.442 -
1.443 -/// @}
1.444 -
1.445 -}
1.446 -
1.447 -#endif