1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/array_map.h Wed Sep 08 12:06:45 2004 +0000
1.3 @@ -0,0 +1,285 @@
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 <hugo/map_iterator.h>
1.11 +
1.12 +///\ingroup graphmaps
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 graphmaps
1.21 + /// @{
1.22 +
1.23 + /** The ArrayMap template class is graph map structure what
1.24 + * automatically updates the map when a key is added to or erased from
1.25 + * the map. This map factory uses the allocators to implement
1.26 + * the container functionality.
1.27 + *
1.28 + * The template parameter is the MapRegistry that the maps
1.29 + * will belong to and the ValueType.
1.30 + */
1.31 +
1.32 + template <typename MapRegistry, typename Value>
1.33 + class ArrayMap : public MapRegistry::MapBase {
1.34 +
1.35 + public:
1.36 +
1.37 + /// The graph type of the maps.
1.38 + typedef typename MapRegistry::Graph Graph;
1.39 + /// The key type of the maps.
1.40 + typedef typename MapRegistry::KeyType KeyType;
1.41 + /// The iterator to iterate on the keys.
1.42 + typedef typename MapRegistry::KeyIt KeyIt;
1.43 +
1.44 + /// The MapBase of the Map which imlements the core regisitry function.
1.45 + typedef typename MapRegistry::MapBase MapBase;
1.46 +
1.47 +
1.48 + public:
1.49 +
1.50 + /// The value type of the map.
1.51 + typedef Value ValueType;
1.52 + /// The reference type of the map;
1.53 + typedef Value& ReferenceType;
1.54 + /// The pointer type of the map;
1.55 + typedef Value* PointerType;
1.56 +
1.57 + /// The const value type of the map.
1.58 + typedef const Value ConstValueType;
1.59 + /// The const reference type of the map;
1.60 + typedef const Value& ConstReferenceType;
1.61 + /// The pointer type of the map;
1.62 + typedef const Value* ConstPointerType;
1.63 +
1.64 +
1.65 + typedef std::allocator<Value> Allocator;
1.66 +
1.67 +
1.68 + /** Default constructor for the map.
1.69 + */
1.70 + ArrayMap() : values(0), capacity(0) {}
1.71 +
1.72 + /** Graph and Registry initialized map constructor.
1.73 + */
1.74 + ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.75 + allocate_memory();
1.76 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.77 + int id = MapBase::getGraph()->id(it);
1.78 + allocator.construct(&(values[id]), Value());
1.79 + }
1.80 + }
1.81 +
1.82 + /** Constructor to use default value to initialize the map.
1.83 + */
1.84 + ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
1.85 + : MapBase(g, r) {
1.86 + allocate_memory();
1.87 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.88 + int id = MapBase::getGraph()->id(it);
1.89 + allocator.construct(&(values[id]), v);
1.90 + }
1.91 + }
1.92 +
1.93 + /** Constructor to copy a map of the same map type.
1.94 + */
1.95 + ArrayMap(const ArrayMap& copy) : MapBase(*copy.graph, *copy.registry) {
1.96 + capacity = copy.capacity;
1.97 + if (capacity == 0) return;
1.98 + values = allocator.allocate(capacity);
1.99 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.100 + int id = MapBase::getGraph()->id(it);
1.101 + allocator.construct(&(values[id]), copy.values[id]);
1.102 + }
1.103 + }
1.104 +
1.105 + /** Constructor to copy a map of an other map type.
1.106 + */
1.107 + template <typename CMap> ArrayMap(const CMap& copy)
1.108 + : MapBase(copy), capacity(0), values(0) {
1.109 + if (MapBase::getGraph()) {
1.110 + allocate_memory();
1.111 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.112 + set(it, copy[it]);
1.113 + }
1.114 + }
1.115 + }
1.116 +
1.117 + /** Assign operator to copy a map of the same map type.
1.118 + */
1.119 + ArrayMap& operator=(const ArrayMap& copy) {
1.120 + if (© == this) return *this;
1.121 + if (capacity != 0) {
1.122 + MapBase::destroy();
1.123 + allocator.deallocate(values, capacity);
1.124 + }
1.125 + capacity = copy.capacity;
1.126 + if (capacity == 0) return *this;
1.127 + values = allocator.allocate(capacity);
1.128 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.129 + int id = MapBase::getGraph()->id(it);
1.130 + allocator.construct(&(values[id]), copy.values[id]);
1.131 + }
1.132 + return *this;
1.133 + }
1.134 +
1.135 + /** Assign operator to copy a map an other map type.
1.136 + */
1.137 + template <typename CMap> ArrayMap& operator=(const CMap& copy) {
1.138 + if (MapBase::getGraph()) {
1.139 + MapBase::destroy();
1.140 + }
1.141 + MapBase::operator=(copy);
1.142 + if (MapBase::getGraph()) {
1.143 + allocate_memory();
1.144 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.145 + set(it, copy[it]);
1.146 + }
1.147 + }
1.148 + return *this;
1.149 + }
1.150 +
1.151 + /** The destructor of the map.
1.152 + */
1.153 + virtual ~ArrayMap() {
1.154 + if (capacity != 0) {
1.155 + MapBase::destroy();
1.156 + allocator.deallocate(values, capacity);
1.157 + }
1.158 + }
1.159 +
1.160 +
1.161 + /**
1.162 + * The subscript operator. The map can be subscripted by the
1.163 + * actual keys of the graph.
1.164 + */
1.165 + ReferenceType operator[](const KeyType& key) {
1.166 + int id = MapBase::getGraph()->id(key);
1.167 + return values[id];
1.168 + }
1.169 +
1.170 + /**
1.171 + * The const subscript operator. The map can be subscripted by the
1.172 + * actual keys of the graph.
1.173 + */
1.174 + ConstReferenceType operator[](const KeyType& key) const {
1.175 + int id = MapBase::getGraph()->id(key);
1.176 + return values[id];
1.177 + }
1.178 +
1.179 + /** Setter function of the map. Equivalent with map[key] = val.
1.180 + * This is a compatibility feature with the not dereferable maps.
1.181 + */
1.182 + void set(const KeyType& key, const ValueType& val) {
1.183 + int id = MapBase::getGraph()->id(key);
1.184 + values[id] = val;
1.185 + }
1.186 +
1.187 + /** Add a new key to the map. It called by the map registry.
1.188 + */
1.189 + void add(const KeyType& key) {
1.190 + int id = MapBase::getGraph()->id(key);
1.191 + if (id >= capacity) {
1.192 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.193 + while (new_capacity <= id) {
1.194 + new_capacity <<= 1;
1.195 + }
1.196 + Value* new_values = allocator.allocate(new_capacity);;
1.197 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.198 + int jd = MapBase::getGraph()->id(it);
1.199 + if (id != jd) {
1.200 + allocator.construct(&(new_values[jd]), values[jd]);
1.201 + allocator.destroy(&(values[jd]));
1.202 + }
1.203 + }
1.204 + if (capacity != 0) allocator.deallocate(values, capacity);
1.205 + values = new_values;
1.206 + capacity = new_capacity;
1.207 + }
1.208 + allocator.construct(&(values[id]), Value());
1.209 + }
1.210 +
1.211 + /** Erase a key from the map. It called by the map registry.
1.212 + */
1.213 + void erase(const KeyType& key) {
1.214 + int id = MapBase::getGraph()->id(key);
1.215 + allocator.destroy(&(values[id]));
1.216 + }
1.217 +
1.218 + /** Clear the data structure.
1.219 + */
1.220 + void clear() {
1.221 + if (capacity != 0) {
1.222 + MapBase::destroy();
1.223 + allocator.deallocate(values, capacity);
1.224 + capacity = 0;
1.225 + }
1.226 + }
1.227 +
1.228 + /// The stl compatible pair iterator of the map.
1.229 + typedef MapIterator<ArrayMap> Iterator;
1.230 + /// The stl compatible const pair iterator of the map.
1.231 + typedef MapConstIterator<ArrayMap> ConstIterator;
1.232 +
1.233 + /** Returns the begin iterator of the map.
1.234 + */
1.235 + Iterator begin() {
1.236 + return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.237 + }
1.238 +
1.239 + /** Returns the end iterator of the map.
1.240 + */
1.241 + Iterator end() {
1.242 + return Iterator(*this, INVALID);
1.243 + }
1.244 +
1.245 + /** Returns the begin ConstIterator of the map.
1.246 + */
1.247 + ConstIterator begin() const {
1.248 + return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.249 + }
1.250 +
1.251 + /** Returns the end const_iterator of the map.
1.252 + */
1.253 + ConstIterator end() const {
1.254 + return ConstIterator(*this, INVALID);
1.255 + }
1.256 +
1.257 + private:
1.258 +
1.259 + void allocate_memory() {
1.260 + int max_id = -1;
1.261 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.262 + int id = MapBase::getGraph()->id(it);
1.263 + if (id > max_id) {
1.264 + max_id = id;
1.265 + }
1.266 + }
1.267 + if (max_id == -1) {
1.268 + capacity = 0;
1.269 + values = 0;
1.270 + return;
1.271 + }
1.272 + capacity = 1;
1.273 + while (capacity <= max_id) {
1.274 + capacity <<= 1;
1.275 + }
1.276 + values = allocator.allocate(capacity);
1.277 + }
1.278 +
1.279 + int capacity;
1.280 + Value* values;
1.281 + Allocator allocator;
1.282 + };
1.283 +
1.284 +/// @}
1.285 +
1.286 +}
1.287 +
1.288 +#endif
2.1 --- a/src/hugo/array_map_factory.h Wed Sep 08 11:58:06 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,444 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#ifndef ARRAY_MAP_FACTORY_H
2.6 -#define ARRAY_MAP_FACTORY_H
2.7 -
2.8 -#include <memory>
2.9 -
2.10 -#include <hugo/extended_pair.h>
2.11 -
2.12 -///\ingroup graphmapfactory
2.13 -///\file
2.14 -///\brief Graph maps that construates and destruates
2.15 -///their elements dynamically.
2.16 -
2.17 -namespace hugo {
2.18 -
2.19 -
2.20 -/// \addtogroup graphmapfactory
2.21 -/// @{
2.22 -
2.23 - /** The ArrayMapFactory template class is a factory class
2.24 - * to create maps for the edge and nodes. This map factory
2.25 - * uses the allocators to implement the container function.
2.26 - *
2.27 - * The template parameter is the MapRegistry that the maps
2.28 - * will belong to.
2.29 - */
2.30 -
2.31 - template <typename MapRegistry>
2.32 - class ArrayMapFactory {
2.33 -
2.34 - public:
2.35 -
2.36 - /// The graph type of the maps.
2.37 - typedef typename MapRegistry::Graph Graph;
2.38 - /// The key type of the maps.
2.39 - typedef typename MapRegistry::KeyType KeyType;
2.40 - /// The iterator to iterate on the keys.
2.41 - typedef typename MapRegistry::KeyIt KeyIt;
2.42 -
2.43 - /// The MapBase of the Map which imlements the core regisitry function.
2.44 - typedef typename MapRegistry::MapBase MapBase;
2.45 -
2.46 - /** The template Map type.
2.47 - */
2.48 - template <typename V, typename A = std::allocator<V> >
2.49 - class Map : public MapBase {
2.50 -
2.51 - public:
2.52 -
2.53 - /// The value type of the map.
2.54 - typedef V ValueType;
2.55 -
2.56 - /// The value type of the map.
2.57 - typedef V Value;
2.58 - /// The reference type of the map;
2.59 - typedef Value& Reference;
2.60 - /// The pointer type of the map;
2.61 - typedef Value* Pointer;
2.62 -
2.63 - /// The const value type of the map.
2.64 - typedef const Value ConstValue;
2.65 - /// The const reference type of the map;
2.66 - typedef const Value& ConstReference;
2.67 - /// The pointer type of the map;
2.68 - typedef const Value* ConstPointer;
2.69 -
2.70 -
2.71 - typedef A Allocator;
2.72 -
2.73 -
2.74 - /** Default constructor for the map.
2.75 - */
2.76 - Map() : values(0), capacity(0) {}
2.77 -
2.78 - /** Graph and Registry initialized map constructor.
2.79 - */
2.80 - Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
2.81 - allocate_memory();
2.82 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.83 - int id = MapBase::getGraph()->id(it);
2.84 - allocator.construct(&(values[id]), Value());
2.85 - }
2.86 - }
2.87 -
2.88 - /** Constructor to use default value to initialize the map.
2.89 - */
2.90 - Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
2.91 - allocate_memory();
2.92 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.93 - int id = MapBase::getGraph()->id(it);
2.94 - allocator.construct(&(values[id]), v);
2.95 - }
2.96 - }
2.97 -
2.98 - /** Constructor to copy a map of the same map type.
2.99 - */
2.100 - Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
2.101 - capacity = copy.capacity;
2.102 - if (capacity == 0) return;
2.103 - values = allocator.allocate(capacity);
2.104 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.105 - int id = MapBase::getGraph()->id(it);
2.106 - allocator.construct(&(values[id]), copy.values[id]);
2.107 - }
2.108 - }
2.109 -
2.110 - /** Constructor to copy a map of an other map type.
2.111 - */
2.112 - template <typename CMap> Map(const CMap& copy)
2.113 - : MapBase(copy), capacity(0), values(0) {
2.114 - if (MapBase::getGraph()) {
2.115 - allocate_memory();
2.116 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.117 - set(it, copy[it]);
2.118 - }
2.119 - }
2.120 - }
2.121 -
2.122 - /** Assign operator to copy a map of the same map type.
2.123 - */
2.124 - Map& operator=(const Map& copy) {
2.125 - if (© == this) return *this;
2.126 - if (capacity != 0) {
2.127 - MapBase::destroy();
2.128 - allocator.deallocate(values, capacity);
2.129 - }
2.130 - capacity = copy.capacity;
2.131 - if (capacity == 0) return *this;
2.132 - values = allocator.allocate(capacity);
2.133 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.134 - int id = MapBase::getGraph()->id(it);
2.135 - allocator.construct(&(values[id]), copy.values[id]);
2.136 - }
2.137 - return *this;
2.138 - }
2.139 -
2.140 - /** Assign operator to copy a map an other map type.
2.141 - */
2.142 - template <typename CMap> Map& operator=(const CMap& copy) {
2.143 - if (MapBase::getGraph()) {
2.144 - MapBase::destroy();
2.145 - }
2.146 - MapBase::operator=(copy);
2.147 - if (MapBase::getGraph()) {
2.148 - allocate_memory();
2.149 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.150 - set(it, copy[it]);
2.151 - }
2.152 - }
2.153 - return *this;
2.154 - }
2.155 -
2.156 - /** The destructor of the map.
2.157 - */
2.158 - virtual ~Map() {
2.159 - if (capacity != 0) {
2.160 - MapBase::destroy();
2.161 - allocator.deallocate(values, capacity);
2.162 - }
2.163 - }
2.164 -
2.165 -
2.166 - /**
2.167 - * The subscript operator. The map can be subscripted by the
2.168 - * actual keys of the graph.
2.169 - */
2.170 - Value& operator[](const KeyType& key) {
2.171 - int id = MapBase::getGraph()->id(key);
2.172 - return values[id];
2.173 - }
2.174 -
2.175 - /**
2.176 - * The const subscript operator. The map can be subscripted by the
2.177 - * actual keys of the graph.
2.178 - */
2.179 - const Value& operator[](const KeyType& key) const {
2.180 - int id = MapBase::getGraph()->id(key);
2.181 - return values[id];
2.182 - }
2.183 -
2.184 - /** Setter function of the map. Equivalent with map[key] = val.
2.185 - * This is a compatibility feature with the not dereferable maps.
2.186 - */
2.187 - void set(const KeyType& key, const Value& val) {
2.188 - int id = MapBase::getGraph()->id(key);
2.189 - values[id] = val;
2.190 - }
2.191 -
2.192 - /** Add a new key to the map. It called by the map registry.
2.193 - */
2.194 - void add(const KeyType& key) {
2.195 - int id = MapBase::getGraph()->id(key);
2.196 - if (id >= capacity) {
2.197 - int new_capacity = (capacity == 0 ? 1 : capacity);
2.198 - while (new_capacity <= id) {
2.199 - new_capacity <<= 1;
2.200 - }
2.201 - Value* new_values = allocator.allocate(new_capacity);;
2.202 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.203 - int jd = MapBase::getGraph()->id(it);
2.204 - if (id != jd) {
2.205 - allocator.construct(&(new_values[jd]), values[jd]);
2.206 - allocator.destroy(&(values[jd]));
2.207 - }
2.208 - }
2.209 - if (capacity != 0) allocator.deallocate(values, capacity);
2.210 - values = new_values;
2.211 - capacity = new_capacity;
2.212 - }
2.213 - allocator.construct(&(values[id]), Value());
2.214 - }
2.215 -
2.216 - /** Erase a key from the map. It called by the map registry.
2.217 - */
2.218 - void erase(const KeyType& key) {
2.219 - int id = MapBase::getGraph()->id(key);
2.220 - allocator.destroy(&(values[id]));
2.221 - }
2.222 -
2.223 - /** Clear the data structure.
2.224 - */
2.225 - void clear() {
2.226 - if (capacity != 0) {
2.227 - MapBase::destroy();
2.228 - allocator.deallocate(values, capacity);
2.229 - capacity = 0;
2.230 - }
2.231 - }
2.232 -
2.233 - class iterator;
2.234 - class const_iterator;
2.235 -
2.236 - /** Compatible iterator with the stl maps' iterators.
2.237 - * It iterates on pairs of a key and a value.
2.238 - */
2.239 - class iterator {
2.240 - friend class Map;
2.241 - friend class const_iterator;
2.242 - private:
2.243 -
2.244 - /** Private constructor to initalize the the iterators returned
2.245 - * by the begin() and end().
2.246 - */
2.247 - iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
2.248 -
2.249 - public:
2.250 -
2.251 - /** Default constructor.
2.252 - */
2.253 - iterator() {}
2.254 -
2.255 - typedef extended_pair<const KeyType&, const KeyType&,
2.256 - Value&, Value&> Reference;
2.257 -
2.258 - /** Dereference operator for map.
2.259 - */
2.260 - Reference operator*() {
2.261 - return Reference(it, (*map)[it]);
2.262 - }
2.263 -
2.264 - class Pointer {
2.265 - friend class iterator;
2.266 - private:
2.267 - Reference data;
2.268 - Pointer(const KeyType& key, Value& val) : data(key, val) {}
2.269 - public:
2.270 - Reference* operator->() {return &data;}
2.271 - };
2.272 -
2.273 - /** Arrow operator for map.
2.274 - */
2.275 - Pointer operator->() {
2.276 - return Pointer(it, ((*map)[it]));
2.277 - }
2.278 -
2.279 - /** The pre increment operator of the map.
2.280 - */
2.281 - iterator& operator++() {
2.282 - ++it;
2.283 - return *this;
2.284 - }
2.285 -
2.286 - /** The post increment operator of the map.
2.287 - */
2.288 - iterator operator++(int) {
2.289 - iterator tmp(it);
2.290 - ++it;
2.291 - return tmp;
2.292 - }
2.293 -
2.294 - /** The equality operator of the map.
2.295 - */
2.296 - bool operator==(const_iterator p_it) {
2.297 - return p_it.it == it;
2.298 - }
2.299 -
2.300 - /** The not-equality operator of the map.
2.301 - */
2.302 - bool operator!=(const_iterator p_it) {
2.303 - return !(*this == p_it);
2.304 - }
2.305 -
2.306 -
2.307 - private:
2.308 - Map* map;
2.309 - KeyIt it;
2.310 - };
2.311 -
2.312 - /** Returns the begin iterator of the map.
2.313 - */
2.314 - iterator begin() {
2.315 - return iterator(*this, KeyIt(*MapBase::getGraph()));
2.316 - }
2.317 -
2.318 - /** Returns the end iterator of the map.
2.319 - */
2.320 - iterator end() {
2.321 - return iterator(*this, INVALID);
2.322 - }
2.323 -
2.324 - class const_iterator {
2.325 - friend class Map;
2.326 - friend class iterator;
2.327 - private:
2.328 -
2.329 - /** Private constructor to initalize the the iterators returned
2.330 - * by the begin() and end().
2.331 - */
2.332 - const_iterator (const Map& pmap, const KeyIt& pit)
2.333 - : map(&pmap), it(pit) {}
2.334 -
2.335 - public:
2.336 -
2.337 - /** Default constructor.
2.338 - */
2.339 - const_iterator() {}
2.340 -
2.341 - /** Constructor to convert iterator to const_iterator.
2.342 - */
2.343 - const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
2.344 -
2.345 - typedef extended_pair<const KeyType&, const KeyType&,
2.346 - const Value&, const Value&> Reference;
2.347 -
2.348 - /** Dereference operator for map.
2.349 - */
2.350 - Reference operator*() {
2.351 - return Reference(it, (*map)[it]);
2.352 - }
2.353 -
2.354 -
2.355 - class Pointer {
2.356 - friend class const_iterator;
2.357 - private:
2.358 - Reference data;
2.359 - Pointer(const KeyType& key, const Value& val) : data(key, val) {}
2.360 - public:
2.361 - Reference* operator->() {return &data;}
2.362 - };
2.363 -
2.364 - /** Arrow operator for map.
2.365 - */
2.366 - Pointer operator->() {
2.367 - return Pointer(it, ((*map)[it]));
2.368 - }
2.369 -
2.370 - /** The pre increment operator of the map.
2.371 - */
2.372 - const_iterator& operator++() {
2.373 - ++it;
2.374 - return *this;
2.375 - }
2.376 -
2.377 - /** The post increment operator of the map.
2.378 - */
2.379 - const_iterator operator++(int) {
2.380 - const_iterator tmp(it);
2.381 - ++it;
2.382 - return tmp;
2.383 - }
2.384 -
2.385 - /** The equality operator of the map.
2.386 - */
2.387 - bool operator==(const_iterator p_it) {
2.388 - return p_it.it == it;
2.389 - }
2.390 -
2.391 - /** The not-equality operator of the map.
2.392 - */
2.393 - bool operator!=(const_iterator p_it) {
2.394 - return !(*this == p_it);
2.395 - }
2.396 -
2.397 -
2.398 - private:
2.399 - const Map* map;
2.400 - KeyIt it;
2.401 - };
2.402 -
2.403 - /** Returns the begin const_iterator of the map.
2.404 - */
2.405 - const_iterator begin() const {
2.406 - return const_iterator(*this, KeyIt(*MapBase::getGraph()));
2.407 - }
2.408 -
2.409 - /** Returns the end const_iterator of the map.
2.410 - */
2.411 - const_iterator end() const {
2.412 - return const_iterator(*this, INVALID);
2.413 - }
2.414 -
2.415 - private:
2.416 -
2.417 - void allocate_memory() {
2.418 - int max_id = -1;
2.419 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.420 - int id = MapBase::getGraph()->id(it);
2.421 - if (id > max_id) {
2.422 - max_id = id;
2.423 - }
2.424 - }
2.425 - if (max_id == -1) {
2.426 - capacity = 0;
2.427 - values = 0;
2.428 - return;
2.429 - }
2.430 - capacity = 1;
2.431 - while (capacity <= max_id) {
2.432 - capacity <<= 1;
2.433 - }
2.434 - values = allocator.allocate(capacity);
2.435 - }
2.436 -
2.437 - int capacity;
2.438 - Value* values;
2.439 - Allocator allocator;
2.440 - };
2.441 - };
2.442 -
2.443 -/// @}
2.444 -
2.445 -}
2.446 -
2.447 -#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/hugo/default_map.h Wed Sep 08 12:06:45 2004 +0000
3.3 @@ -0,0 +1,115 @@
3.4 +// -*- c++ -*-
3.5 +#ifndef DEFAULT_MAP_H
3.6 +#define DEFAULT_MAP_H
3.7 +
3.8 +
3.9 +#include <hugo/array_map.h>
3.10 +#include <hugo/vector_map.h>
3.11 +
3.12 +///\ingroup graphmaps
3.13 +///\file
3.14 +///\brief Graph maps that construates and destruates
3.15 +///their elements dynamically.
3.16 +
3.17 +namespace hugo {
3.18 +
3.19 +/// \addtogroup graphmaps
3.20 +/// @{
3.21 +
3.22 + /** The ArrayMap template class is graph map structure what
3.23 + * automatically updates the map when a key is added to or erased from
3.24 + * the map. This map uses the VectorMap if the ValueType is a primitive
3.25 + * type and the ArrayMap for the other cases.
3.26 + *
3.27 + * The template parameter is the MapRegistry that the maps
3.28 + * will belong to and the ValueType.
3.29 + */
3.30 +
3.31 +
3.32 + /** Macro to implement the DefaultMap.
3.33 + */
3.34 +#define DEFAULT_MAP_BODY(DynMap, Value) \
3.35 + { \
3.36 + typedef DynMap<MapRegistry, Value> MapImpl; \
3.37 + \
3.38 + public: \
3.39 + \
3.40 + typedef typename MapRegistry::Graph Graph; \
3.41 + \
3.42 + DefaultMap() : MapImpl() {} \
3.43 + \
3.44 + DefaultMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {} \
3.45 + \
3.46 + DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \
3.47 + : MapImpl(g, r, v) {} \
3.48 + \
3.49 + DefaultMap(const DefaultMap& copy) \
3.50 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
3.51 + \
3.52 + template <typename CMap> DefaultMap(const CMap& copy) : MapImpl(copy) {} \
3.53 + \
3.54 + DefaultMap& operator=(const DefaultMap& copy) { \
3.55 + MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
3.56 + return *this; \
3.57 + } \
3.58 + \
3.59 + template <typename CMap> DefaultMap& operator=(const CMap& copy) { \
3.60 + MapImpl::operator=(copy); \
3.61 + return *this; \
3.62 + } \
3.63 + \
3.64 + };
3.65 +
3.66 +
3.67 + template <typename MapRegistry, typename Type>
3.68 + class DefaultMap : public ArrayMap<MapRegistry, Type>
3.69 + DEFAULT_MAP_BODY(ArrayMap, Type);
3.70 +
3.71 + template <typename MapRegistry>
3.72 + class DefaultMap<MapRegistry, bool>
3.73 + : public VectorMap<MapRegistry, bool>
3.74 + DEFAULT_MAP_BODY(VectorMap, bool);
3.75 +
3.76 + template <typename MapRegistry>
3.77 + class DefaultMap<MapRegistry, char>
3.78 + : public VectorMap<MapRegistry, char>
3.79 + DEFAULT_MAP_BODY(VectorMap, char);
3.80 +
3.81 + template <typename MapRegistry>
3.82 + class DefaultMap<MapRegistry, int>
3.83 + : public VectorMap<MapRegistry, int>
3.84 + DEFAULT_MAP_BODY(VectorMap, int);
3.85 +
3.86 + template <typename MapRegistry>
3.87 + class DefaultMap<MapRegistry, short>
3.88 + : public VectorMap<MapRegistry, short>
3.89 + DEFAULT_MAP_BODY(VectorMap, short);
3.90 +
3.91 + template <typename MapRegistry>
3.92 + class DefaultMap<MapRegistry, long>
3.93 + : public VectorMap<MapRegistry, long>
3.94 + DEFAULT_MAP_BODY(VectorMap, long);
3.95 +
3.96 + template <typename MapRegistry>
3.97 + class DefaultMap<MapRegistry, float>
3.98 + : public VectorMap<MapRegistry, float>
3.99 + DEFAULT_MAP_BODY(VectorMap, float);
3.100 +
3.101 + template <typename MapRegistry>
3.102 + class DefaultMap<MapRegistry, double>
3.103 + : public VectorMap<MapRegistry, double>
3.104 + DEFAULT_MAP_BODY(VectorMap, double);
3.105 +
3.106 + template <typename MapRegistry>
3.107 + class DefaultMap<MapRegistry, long double>
3.108 + : public VectorMap<MapRegistry, long double>
3.109 + DEFAULT_MAP_BODY(VectorMap, long double);
3.110 +
3.111 + template <typename MapRegistry, typename Type>
3.112 + class DefaultMap<MapRegistry, Type*>
3.113 + : public VectorMap<MapRegistry, Type*>
3.114 + DEFAULT_MAP_BODY(VectorMap, Type*);
3.115 +
3.116 +}
3.117 +
3.118 +#endif
4.1 --- a/src/hugo/default_map_factory.h Wed Sep 08 11:58:06 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,181 +0,0 @@
4.4 -// -*- c++ -*-
4.5 -#ifndef DEFAULT_MAP_FACTORY_H
4.6 -#define DEFAULT_MAP_FACTORY_H
4.7 -
4.8 -
4.9 -#include <hugo/array_map_factory.h>
4.10 -#include <hugo/vector_map_factory.h>
4.11 -
4.12 -///\ingroup graphmapfactory
4.13 -///\file
4.14 -///\brief Graph maps that construates and destruates
4.15 -///their elements dynamically.
4.16 -
4.17 -namespace hugo {
4.18 -
4.19 -/// \addtogroup graphmapfactory
4.20 -/// @{
4.21 -
4.22 -#define DEFAULT_MAP_BODY(Factory, Val) \
4.23 - { \
4.24 - typedef typename Factory<MapRegistry>::template Map<Val> MapImpl; \
4.25 - \
4.26 - public: \
4.27 - \
4.28 - typedef typename MapRegistry::Graph Graph; \
4.29 - typedef typename MapRegistry::KeyType KeyType; \
4.30 - typedef typename MapRegistry::KeyIt KeyIt; \
4.31 - typedef Val Value; \
4.32 - \
4.33 - typedef typename MapRegistry::MapBase MapBase; \
4.34 - \
4.35 - DefaultMap() : MapImpl() {} \
4.36 - \
4.37 - DefaultMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {} \
4.38 - \
4.39 - DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \
4.40 - : MapImpl(g, r, v) {} \
4.41 - \
4.42 - DefaultMap(const DefaultMap& copy) \
4.43 - : MapImpl(static_cast<const MapImpl&>(copy)) {} \
4.44 - \
4.45 - template <typename CMap> DefaultMap(const CMap& copy) : MapImpl(copy) {} \
4.46 - \
4.47 - DefaultMap& operator=(const DefaultMap& copy) { \
4.48 - MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
4.49 - return *this; \
4.50 - } \
4.51 - \
4.52 - template <typename CMap> DefaultMap& operator=(const CMap& copy) { \
4.53 - MapImpl::operator=(copy); \
4.54 - return *this; \
4.55 - } \
4.56 - \
4.57 - };
4.58 -
4.59 -
4.60 - template <typename MapRegistry, typename Type>
4.61 - class DefaultMap : public ArrayMapFactory<MapRegistry>::template Map<Type>
4.62 - DEFAULT_MAP_BODY(ArrayMapFactory, Type);
4.63 -
4.64 - template <typename MapRegistry>
4.65 - class DefaultMap<MapRegistry, bool>
4.66 - : public VectorMapFactory<MapRegistry>::template Map<bool>
4.67 - DEFAULT_MAP_BODY(VectorMapFactory, bool);
4.68 -
4.69 - template <typename MapRegistry>
4.70 - class DefaultMap<MapRegistry, char>
4.71 - : public VectorMapFactory<MapRegistry>::template Map<char>
4.72 - DEFAULT_MAP_BODY(VectorMapFactory, char);
4.73 -
4.74 - template <typename MapRegistry>
4.75 - class DefaultMap<MapRegistry, int>
4.76 - : public VectorMapFactory<MapRegistry>::template Map<int>
4.77 - DEFAULT_MAP_BODY(VectorMapFactory, int);
4.78 -
4.79 - template <typename MapRegistry>
4.80 - class DefaultMap<MapRegistry, short>
4.81 - : public VectorMapFactory<MapRegistry>::template Map<short>
4.82 - DEFAULT_MAP_BODY(VectorMapFactory, short);
4.83 -
4.84 - template <typename MapRegistry>
4.85 - class DefaultMap<MapRegistry, long>
4.86 - : public VectorMapFactory<MapRegistry>::template Map<long>
4.87 - DEFAULT_MAP_BODY(VectorMapFactory, long);
4.88 -
4.89 - template <typename MapRegistry>
4.90 - class DefaultMap<MapRegistry, float>
4.91 - : public VectorMapFactory<MapRegistry>::template Map<float>
4.92 - DEFAULT_MAP_BODY(VectorMapFactory, float);
4.93 -
4.94 - template <typename MapRegistry>
4.95 - class DefaultMap<MapRegistry, double>
4.96 - : public VectorMapFactory<MapRegistry>::template Map<double>
4.97 - DEFAULT_MAP_BODY(VectorMapFactory, double);
4.98 -
4.99 - template <typename MapRegistry>
4.100 - class DefaultMap<MapRegistry, long double>
4.101 - : public VectorMapFactory<MapRegistry>::template Map<long double>
4.102 - DEFAULT_MAP_BODY(VectorMapFactory, long double);
4.103 -
4.104 - template <typename MapRegistry, typename Type>
4.105 - class DefaultMap<MapRegistry, Type*>
4.106 - : public VectorMapFactory<MapRegistry>::template Map<Type*>
4.107 - DEFAULT_MAP_BODY(VectorMapFactory, Type*);
4.108 -
4.109 -
4.110 - /** The DefaultMapFactory template class is a factory class
4.111 - * to create maps for the edge and nodes. This map factory
4.112 - * uses the VectorMapFactory if the ValueType is a primitive
4.113 - * type and the ArrayMapFactory for the other cases.
4.114 - *
4.115 - * The template parameter is the MapRegistry that the maps
4.116 - * will belong to.
4.117 - */
4.118 -
4.119 - template <typename MapRegistry>
4.120 - class DefaultMapFactory {
4.121 -
4.122 - public:
4.123 - /// The graph type of the maps.
4.124 - typedef typename MapRegistry::Graph Graph;
4.125 - /// The key type of the maps.
4.126 - typedef typename MapRegistry::KeyType KeyType;
4.127 - /// The iterator to iterate on the keys.
4.128 - typedef typename MapRegistry::KeyIt KeyIt;
4.129 -
4.130 - /// The MapBase of the Map which imlements the core regisitry function.
4.131 - typedef typename MapRegistry::MapBase MapBase;
4.132 -
4.133 -
4.134 - /** The template Map type.
4.135 - */
4.136 - template <typename V>
4.137 - class Map : public DefaultMap<MapRegistry, V> {
4.138 -
4.139 - typedef DefaultMap<MapRegistry, V> MapImpl;
4.140 -
4.141 - public:
4.142 -
4.143 - typedef V Value;
4.144 -
4.145 - /** Default constructor for the map.
4.146 - */
4.147 - Map() : MapImpl() {}
4.148 -
4.149 - /** Graph and Registry initialized map constructor.
4.150 - */
4.151 - Map(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
4.152 -
4.153 - /** Constructor to use default value to initialize the map.
4.154 - */
4.155 - Map(const Graph& g, MapRegistry& r, const Value& v) : MapImpl(g, r, v) {}
4.156 -
4.157 - /** Constructor to copy a map of the same map type.
4.158 - */
4.159 - Map(const Map& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {}
4.160 -
4.161 - /** Constructor to copy a map of an other map type.
4.162 - */
4.163 - template <typename CMap> Map(const CMap& copy) : MapImpl(copy) {}
4.164 -
4.165 - /** Assign operator to copy a map of the same map type.
4.166 - */
4.167 - Map& operator=(const Map& copy) {
4.168 - MapImpl::operator=(static_cast<const MapImpl&>(copy));
4.169 - return *this;
4.170 - }
4.171 -
4.172 - /** Assign operator to copy a map an other map type.
4.173 - */
4.174 - template <typename CMap> Map& operator=(const CMap& copy) {
4.175 - MapImpl::operator=(copy);
4.176 - return *this;
4.177 - }
4.178 -
4.179 - };
4.180 -
4.181 - };
4.182 -}
4.183 -
4.184 -#endif
5.1 --- a/src/hugo/full_graph.h Wed Sep 08 11:58:06 2004 +0000
5.2 +++ b/src/hugo/full_graph.h Wed Sep 08 12:06:45 2004 +0000
5.3 @@ -13,7 +13,9 @@
5.4 #include <hugo/invalid.h>
5.5
5.6 #include <hugo/map_registry.h>
5.7 -#include <hugo/default_map_factory.h>
5.8 +#include <hugo/default_map.h>
5.9 +
5.10 +#include <hugo/map_defines.h>
5.11
5.12 namespace hugo {
5.13
5.14 @@ -47,8 +49,11 @@
5.15 class OutEdgeIt;
5.16 class InEdgeIt;
5.17
5.18 +
5.19 + /// Creating map registries.
5.20 CREATE_MAP_REGISTRIES;
5.21 - CREATE_MAPS(DefaultMapFactory);
5.22 + /// Creating node and edge maps.
5.23 + CREATE_MAPS(DefaultMap);
5.24
5.25 public:
5.26
6.1 --- a/src/hugo/list_graph.h Wed Sep 08 11:58:06 2004 +0000
6.2 +++ b/src/hugo/list_graph.h Wed Sep 08 12:06:45 2004 +0000
6.3 @@ -13,9 +13,9 @@
6.4 #include <hugo/invalid.h>
6.5
6.6 #include <hugo/map_registry.h>
6.7 -#include <hugo/default_map_factory.h>
6.8 +#include <hugo/default_map.h>
6.9
6.10 -#include <hugo/sym_map_factory.h>
6.11 +#include <hugo/sym_map.h>
6.12
6.13 #include <hugo/map_defines.h>
6.14
6.15 @@ -79,8 +79,10 @@
6.16 class OutEdgeIt;
6.17 class InEdgeIt;
6.18
6.19 + /// Creating map registries.
6.20 CREATE_MAP_REGISTRIES;
6.21 - CREATE_MAPS(DefaultMapFactory);
6.22 + /// Creating node and edge maps.
6.23 + CREATE_MAPS(DefaultMap);
6.24
6.25 public:
6.26
6.27 @@ -443,12 +445,13 @@
6.28
6.29 typedef SymListGraph Graph;
6.30
6.31 - KEEP_NODE_MAP(ListGraph);
6.32 - KEEP_EDGE_MAP(ListGraph);
6.33 + /// Importing maps from the base class ListGraph.
6.34 + KEEP_MAPS(ListGraph, SymListGraph);
6.35
6.36 + /// Creating symmetric map registry.
6.37 CREATE_SYM_EDGE_MAP_REGISTRY;
6.38 - CREATE_SYM_EDGE_MAP_FACTORY(DefaultMapFactory);
6.39 - IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
6.40 + /// Creating symmetric edge map.
6.41 + CREATE_SYM_EDGE_MAP(DefaultMap);
6.42
6.43 SymListGraph() : ListGraph() { }
6.44 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
6.45 @@ -529,8 +532,40 @@
6.46 class OutEdgeIt;
6.47 class InEdgeIt;
6.48
6.49 - CREATE_MAP_REGISTRIES;
6.50 - CREATE_MAPS(DefaultMapFactory);
6.51 + /// Creating node map registry.
6.52 + CREATE_NODE_MAP_REGISTRY;
6.53 + /// Creating node maps.
6.54 + CREATE_NODE_MAP(DefaultMap);
6.55 +
6.56 + /// Creating empty map structure for edges.
6.57 + template <typename Value>
6.58 + class EdgeMap {
6.59 + public:
6.60 + EdgeMap() {}
6.61 + EdgeMap(const Graph&) {}
6.62 + EdgeMap(const Graph&, const Value&) {}
6.63 +
6.64 + EdgeMap(const EdgeMap&) {}
6.65 + template <typename CMap> EdgeMap(const CMap&) {}
6.66 +
6.67 + EdgeMap& operator=(const EdgeMap&) {}
6.68 + template <typename CMap> EdgeMap& operator=(const CMap&) {}
6.69 +
6.70 + class ConstIterator {
6.71 + public:
6.72 + bool operator==(const ConstIterator&) {return true;}
6.73 + bool operator!=(const ConstIterator&) {return false;}
6.74 + };
6.75 +
6.76 + typedef ConstIterator Iterator;
6.77 +
6.78 + Iterator begin() { return Iterator();}
6.79 + Iterator end() { return Iterator();}
6.80 +
6.81 + ConstIterator begin() const { return ConstIterator();}
6.82 + ConstIterator end() const { return ConstIterator();}
6.83 +
6.84 + };
6.85
6.86 public:
6.87
6.88 @@ -848,9 +883,13 @@
6.89 class InEdgeIt;
6.90
6.91
6.92 + /// Creating edge map registry.
6.93 CREATE_EDGE_MAP_REGISTRY;
6.94 - CREATE_EDGE_MAP_FACTORY(DefaultMapFactory);
6.95 - IMPORT_EDGE_MAP(EdgeMapFactory);
6.96 + /// Creating edge maps.
6.97 + CREATE_EDGE_MAP(DefaultMap);
6.98 +
6.99 + /// Importing node maps from the NodeGraphType.
6.100 + IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
6.101
6.102
6.103 public:
6.104 @@ -1090,42 +1129,7 @@
6.105 : Edge(_G.nodes[v].first_in), G(&_G) { }
6.106 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
6.107 };
6.108 -
6.109
6.110 - template <typename V> class NodeMap
6.111 - : public NodeGraphType::template NodeMap<V>
6.112 - {
6.113 - //This is a must, the constructors need it.
6.114 - typedef typename NodeGraphType::template NodeMap<V> MapImpl;
6.115 - typedef V Value;
6.116 - public:
6.117 - NodeMap() : MapImpl() {}
6.118 -
6.119 - NodeMap(const EdgeSet& graph)
6.120 - : MapImpl(graph.G) { }
6.121 -
6.122 - NodeMap(const EdgeSet& graph, const Value& value)
6.123 - : MapImpl(graph.G, value) { }
6.124 -
6.125 - NodeMap(const NodeMap& copy)
6.126 - : MapImpl(static_cast<const MapImpl&>(copy)) {}
6.127 -
6.128 - template<typename CMap>
6.129 - NodeMap(const CMap& copy)
6.130 - : MapImpl(copy) { }
6.131 -
6.132 - NodeMap& operator=(const NodeMap& copy) {
6.133 - MapImpl::operator=(static_cast<const MapImpl&>(copy));
6.134 - return *this;
6.135 - }
6.136 -
6.137 - template <typename CMap>
6.138 - NodeMap& operator=(const CMap& copy) {
6.139 - MapImpl::operator=(copy);
6.140 - return *this;
6.141 - }
6.142 -
6.143 - };
6.144 };
6.145
6.146 template<typename GG>
7.1 --- a/src/hugo/map_defines.h Wed Sep 08 11:58:06 2004 +0000
7.2 +++ b/src/hugo/map_defines.h Wed Sep 08 12:06:45 2004 +0000
7.3 @@ -2,7 +2,7 @@
7.4 #ifndef MAP_DEFINES_H
7.5 #define MAP_DEFINES_H
7.6
7.7 -///\ingroup graphmapfactory
7.8 +///\ingroup graphmaps
7.9 ///\file
7.10 ///\brief Defines to help creating graph maps.
7.11
7.12 @@ -29,38 +29,22 @@
7.13 CREATE_NODE_MAP_REGISTRY \
7.14 CREATE_EDGE_MAP_REGISTRY
7.15
7.16 -/** Creates a concrete factory type from a template map
7.17 - * factory to use as node map factory.
7.18 - */
7.19 -#define CREATE_NODE_MAP_FACTORY(TemplateFactory) \
7.20 -typedef TemplateFactory<NodeMapRegistry> NodeMapFactory;
7.21 -
7.22 -/** Creates a concrete factory type from a template map
7.23 - * factory to use as edge map factory.
7.24 - */
7.25 -#define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \
7.26 -typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory;
7.27 -
7.28 -/** Creates both map factories.
7.29 - */
7.30 -#define CREATE_MAP_FACTORIES(TemplateFactory) \
7.31 -CREATE_NODE_MAP_FACTORY(TemplateFactory) \
7.32 -CREATE_EDGE_MAP_FACTORY(TemplateFactory)
7.33 -
7.34 -/** Import a map from a concrete map factory. The import method is
7.35 +/** Creates a map from a template map. The import method is
7.36 * an overloading of the map type.
7.37 * The reason to use these macro is that the c++ does not support
7.38 * the template typedefs. If a future release of the c++
7.39 * supports this feature it should be fixed.
7.40 */
7.41 -#define IMPORT_NODE_MAP(Factory) \
7.42 -template <typename V> \
7.43 -class NodeMap : public Factory::template Map<V> { \
7.44 -typedef typename Factory::template Map<V> MapImpl; \
7.45 +#define CREATE_NODE_MAP(DynMap) \
7.46 +template <typename Value> \
7.47 +class NodeMap : public DynMap<NodeMapRegistry, Value> { \
7.48 +typedef DynMap<NodeMapRegistry, Value> MapImpl; \
7.49 public: \
7.50 NodeMap() {} \
7.51 -NodeMap(const Graph& g) : MapImpl(g, g.node_maps) {} \
7.52 -NodeMap(const Graph& g, const V& v) : MapImpl(g, g.node_maps, v) {} \
7.53 +NodeMap(const typename MapImpl::Graph& g) \
7.54 + : MapImpl(g, g.node_maps) {} \
7.55 +NodeMap(const typename MapImpl::Graph& g, const Value& v) \
7.56 + : MapImpl(g, g.node_maps, v) {} \
7.57 NodeMap(const NodeMap& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.58 template <typename CMap> NodeMap(const CMap& copy) : MapImpl(copy) {} \
7.59 NodeMap& operator=(const NodeMap& copy) { \
7.60 @@ -73,20 +57,22 @@
7.61 } \
7.62 };
7.63
7.64 -/** Import a map from a concrete map factory. The import method is
7.65 +/** Creates a map from a template map. The import method is
7.66 * an overloading of the map type.
7.67 * The reason to use these macro is that the c++ does not support
7.68 * the template typedefs. If a future release of the c++
7.69 * supports this feature it should be fixed.
7.70 */
7.71 -#define IMPORT_EDGE_MAP(Factory) \
7.72 -template <typename V> \
7.73 -class EdgeMap : public Factory::template Map<V> { \
7.74 -typedef typename Factory::template Map<V> MapImpl; \
7.75 +#define CREATE_EDGE_MAP(DynMap) \
7.76 +template <typename Value> \
7.77 +class EdgeMap : public DynMap<EdgeMapRegistry, Value> { \
7.78 +typedef DynMap<EdgeMapRegistry, Value> MapImpl; \
7.79 public: \
7.80 EdgeMap() {} \
7.81 -EdgeMap(const Graph& g) : MapImpl(g, g.edge_maps) {} \
7.82 -EdgeMap(const Graph& g, const V& v) : MapImpl(g, g.edge_maps, v) {} \
7.83 +EdgeMap(const typename MapImpl::Graph& g) \
7.84 + : MapImpl(g, g.edge_maps) {} \
7.85 +EdgeMap(const typename MapImpl::Graph& g, const Value& v) \
7.86 + : MapImpl(g, g.edge_maps, v) {} \
7.87 EdgeMap(const EdgeMap& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.88 template <typename CMap> EdgeMap(const CMap& copy) : MapImpl(copy) {} \
7.89 EdgeMap& operator=(const EdgeMap& copy) { \
7.90 @@ -99,12 +85,11 @@
7.91 } \
7.92 };
7.93
7.94 -/** This macro creates both map factories and imports both maps.
7.95 +/** This macro creates both maps.
7.96 */
7.97 -#define CREATE_MAPS(TemplateFactory) \
7.98 -CREATE_MAP_FACTORIES(TemplateFactory) \
7.99 -IMPORT_NODE_MAP(NodeMapFactory) \
7.100 -IMPORT_EDGE_MAP(EdgeMapFactory)
7.101 +#define CREATE_MAPS(DynMap) \
7.102 +CREATE_NODE_MAP(DynMap) \
7.103 +CREATE_EDGE_MAP(DynMap)
7.104
7.105 /** This macro creates MapRegistry for Symmetric Edge Maps.
7.106 */
7.107 @@ -113,109 +98,119 @@
7.108 typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
7.109 mutable EdgeMapRegistry sym_edge_maps;
7.110
7.111 -/** Creates a concrete factory type from a template map
7.112 - * factory to use as edge map factory.
7.113 - */
7.114 -#define CREATE_SYM_EDGE_MAP_FACTORY(TemplateFactory) \
7.115 -typedef SymMapFactory<SymEdgeMapRegistry, TemplateFactory > \
7.116 -SymEdgeMapFactory;
7.117
7.118 -/** Import a map from a concrete map factory. The import method is
7.119 +/** Creates a map from a template map. The import method is
7.120 * an overloading of the map type.
7.121 * The reason to use these macro is that the c++ does not support
7.122 * the template typedefs. If a future release of the c++
7.123 * supports this feature it should be fixed.
7.124 */
7.125 -#define IMPORT_SYM_EDGE_MAP(Factory) \
7.126 -template <typename V> \
7.127 -class SymEdgeMap : public Factory::template Map<V> { \
7.128 -typedef typename Factory::template Map<V> MapImpl; \
7.129 -public: \
7.130 -SymEdgeMap() {} \
7.131 -SymEdgeMap(const Graph& g) : MapImpl(g, g.sym_edge_maps) {} \
7.132 -SymEdgeMap(const Graph& g, const V& v) : MapImpl(g, g.sym_edge_maps, v) {} \
7.133 -SymEdgeMap(const SymEdgeMap& copy) \
7.134 - : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.135 -template <typename CMap> SymEdgeMap(const CMap& copy) : MapImpl(copy) {} \
7.136 -SymEdgeMap& operator=(const SymEdgeMap& copy) { \
7.137 - MapImpl::operator=(static_cast<const MapImpl&>(copy));\
7.138 - return *this; \
7.139 -} \
7.140 -template <typename CMap> SymEdgeMap& operator=(const CMap& copy) { \
7.141 - MapImpl::operator=(copy);\
7.142 - return *this; \
7.143 -} \
7.144 +#define CREATE_SYM_EDGE_MAP(DynMap) \
7.145 +template <typename Value> \
7.146 +class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \
7.147 + typedef SymMap<DynMap, SymEdgeMapRegistry, Value> MapImpl; \
7.148 + public: \
7.149 +\
7.150 + SymEdgeMap() {} \
7.151 +\
7.152 + SymEdgeMap(const typename MapImpl::Graph& g) \
7.153 + : MapImpl(g, g.sym_edge_maps) {} \
7.154 +\
7.155 + SymEdgeMap(const typename MapImpl::Graph& g, const Value& v) \
7.156 + : MapImpl(g, g.sym_edge_maps, v) {} \
7.157 +\
7.158 + SymEdgeMap(const SymEdgeMap& copy) \
7.159 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.160 +\
7.161 + template <typename CMap> SymEdgeMap(const CMap& copy) : MapImpl(copy) {} \
7.162 + SymEdgeMap& operator=(const SymEdgeMap& copy) { \
7.163 + MapImpl::operator=(static_cast<const MapImpl&>(copy));\
7.164 + return *this; \
7.165 + } \
7.166 +\
7.167 + template <typename CMap> SymEdgeMap& operator=(const CMap& copy) { \
7.168 + MapImpl::operator=(copy);\
7.169 + return *this; \
7.170 + } \
7.171 };
7.172
7.173
7.174 -#define KEEP_NODE_MAP(GraphBase) \
7.175 - template <typename V> class NodeMap \
7.176 - : public GraphBase::template NodeMap<V> \
7.177 - { \
7.178 - typedef typename GraphBase::template NodeMap<V> MapImpl; \
7.179 - typedef V Value; \
7.180 - public: \
7.181 - NodeMap() : MapImpl() {} \
7.182 +/** This is a macro to import an node map into a graph class.
7.183 + */
7.184 +#define IMPORT_NODE_MAP(From, from, To, to) \
7.185 +template <typename Value> \
7.186 +class NodeMap \
7.187 + : public From::template NodeMap<Value> { \
7.188 + typedef typename From::template NodeMap<Value> MapImpl; \
7.189 + public: \
7.190 + NodeMap() : MapImpl() {} \
7.191 \
7.192 - NodeMap(const Graph& graph) \
7.193 - : MapImpl(static_cast<const GraphBase&>(graph)) { } \
7.194 + NodeMap(const To& to) \
7.195 + : MapImpl(static_cast<const From&>(from)) { } \
7.196 \
7.197 - NodeMap(const Graph& graph, const Value& value) \
7.198 - : MapImpl(static_cast<const GraphBase&>(graph), value) { } \
7.199 + NodeMap(const To& to, const Value& value) \
7.200 + : MapImpl(static_cast<const From&>(from), value) { } \
7.201 \
7.202 - NodeMap(const NodeMap& copy) \
7.203 - : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.204 + NodeMap(const NodeMap& copy) \
7.205 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.206 \
7.207 - template<typename CMap> \
7.208 - NodeMap(const CMap& copy) \
7.209 - : MapImpl(copy) {} \
7.210 + template<typename CMap> \
7.211 + NodeMap(const CMap& copy) \
7.212 + : MapImpl(copy) {} \
7.213 \
7.214 - NodeMap& operator=(const NodeMap& copy) { \
7.215 - MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
7.216 - return *this; \
7.217 - } \
7.218 + NodeMap& operator=(const NodeMap& copy) { \
7.219 + MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
7.220 + return *this; \
7.221 + } \
7.222 \
7.223 - template <typename CMap> \
7.224 - NodeMap& operator=(const CMap& copy) { \
7.225 - MapImpl::operator=(copy); \
7.226 - return *this; \
7.227 - } \
7.228 - };
7.229 + template <typename CMap> \
7.230 + NodeMap& operator=(const CMap& copy) { \
7.231 + MapImpl::operator=(copy); \
7.232 + return *this; \
7.233 + } \
7.234 +};
7.235
7.236 -#define KEEP_EDGE_MAP(GraphBase) \
7.237 - template <typename V> class EdgeMap \
7.238 - : public GraphBase::template EdgeMap<V> \
7.239 - { \
7.240 - typedef typename GraphBase::template EdgeMap<V> MapImpl; \
7.241 - typedef V Value; \
7.242 - public: \
7.243 - EdgeMap() : MapImpl() {} \
7.244 +/** This is a macro to import an edge map into a graph class.
7.245 + */
7.246 +#define IMPORT_EDGE_MAP(From, from, To, to) \
7.247 +template <typename Value> \
7.248 +class EdgeMap \
7.249 + : public From::template EdgeMap<Value> { \
7.250 + typedef typename From::template EdgeMap<Value> MapImpl; \
7.251 + public: \
7.252 + EdgeMap() : MapImpl() {} \
7.253 \
7.254 - EdgeMap(const Graph& graph) \
7.255 - : MapImpl(static_cast<const GraphBase&>(graph)) { } \
7.256 + EdgeMap(const To& to) \
7.257 + : MapImpl(static_cast<const From&>(from)) { } \
7.258 \
7.259 - EdgeMap(const Graph& graph, const Value& value) \
7.260 - : MapImpl(static_cast<const GraphBase&>(graph), value) { } \
7.261 + EdgeMap(const To& to, const Value& value) \
7.262 + : MapImpl(static_cast<const From&>(from), value) { } \
7.263 \
7.264 - EdgeMap(const EdgeMap& copy) \
7.265 - : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.266 + EdgeMap(const EdgeMap& copy) \
7.267 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
7.268 \
7.269 - template<typename CMap> \
7.270 - EdgeMap(const CMap& copy) \
7.271 - : MapImpl(copy) {} \
7.272 + template<typename CMap> \
7.273 + EdgeMap(const CMap& copy) \
7.274 + : MapImpl(copy) {} \
7.275 \
7.276 - EdgeMap& operator=(const EdgeMap& copy) { \
7.277 - MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
7.278 - return *this; \
7.279 - } \
7.280 + EdgeMap& operator=(const EdgeMap& copy) { \
7.281 + MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
7.282 + return *this; \
7.283 + } \
7.284 \
7.285 - template <typename CMap> \
7.286 - EdgeMap& operator=(const CMap& copy) { \
7.287 - MapImpl::operator=(copy); \
7.288 - return *this; \
7.289 - } \
7.290 - };
7.291 + template <typename CMap> \
7.292 + EdgeMap& operator=(const CMap& copy) { \
7.293 + MapImpl::operator=(copy); \
7.294 + return *this; \
7.295 + } \
7.296 +};
7.297
7.298 +
7.299 +/** This is a macro to keep the node and edge maps for a graph class.
7.300 + */
7.301 +#define KEEP_MAPS(From, To) \
7.302 +IMPORT_EDGE_MAP(From, graph, To, graph) \
7.303 +IMPORT_NODE_MAP(From, graph, To, graph)
7.304
7.305 /// @}
7.306
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/hugo/map_iterator.h Wed Sep 08 12:06:45 2004 +0000
8.3 @@ -0,0 +1,243 @@
8.4 +// -*- c++ -*-
8.5 +#ifndef MAP_ITERATOR_H
8.6 +#define MAP_ITERATOR_H
8.7 +
8.8 +#include <hugo/extended_pair.h>
8.9 +
8.10 +namespace hugo {
8.11 +
8.12 +
8.13 + template <typename Map>
8.14 + class MapIterator;
8.15 +
8.16 + template <typename Map>
8.17 + class MapConstIterator;
8.18 +
8.19 + /** Compatible iterator with the stl maps' iterators.
8.20 + * It iterates on pairs of a key and a value.
8.21 + */
8.22 + template <typename Map>
8.23 + class MapIterator {
8.24 + // friend class Map;
8.25 + friend class MapConstIterator<Map>;
8.26 +
8.27 + public:
8.28 +
8.29 + /// The key type of the iterator.
8.30 + typedef typename Map::KeyType KeyType;
8.31 + /// The iterator to iterate on the keys.
8.32 + typedef typename Map::KeyIt KeyIt;
8.33 +
8.34 + /// The value type of the iterator.
8.35 + typedef typename Map::ValueType ValueType;
8.36 + /// The reference type of the iterator.
8.37 + typedef typename Map::ReferenceType ReferenceType;
8.38 + /// The pointer type of the iterator.
8.39 + typedef typename Map::PointerType PointerType;
8.40 +
8.41 + /// The const value type of the iterator.
8.42 + typedef typename Map::ConstValueType ConstValueType;
8.43 + /// The const reference type of the iterator.
8.44 + typedef typename Map::ConstReferenceType ConstReferenceType;
8.45 + /// The pointer type of the iterator.
8.46 + typedef typename Map::ConstPointerType ConstPointerType;
8.47 +
8.48 + public:
8.49 +
8.50 + /** Constructor to initalize the the iterators returned
8.51 + * by the begin() and end().
8.52 + */
8.53 + MapIterator (Map& pmap, const KeyIt& pit)
8.54 + : map(&pmap), it(pit) {}
8.55 +
8.56 + public:
8.57 +
8.58 + /** Default constructor.
8.59 + */
8.60 + MapIterator() {}
8.61 +
8.62 + typedef extended_pair<const KeyType&, const KeyType&,
8.63 + ReferenceType, ReferenceType> PairReferenceType;
8.64 +
8.65 + /** Dereference operator for map.
8.66 + */
8.67 + PairReferenceType operator*() {
8.68 + return PairReferenceType(it, (*map)[it]);
8.69 + }
8.70 +
8.71 + class PairPointerType {
8.72 + friend class MapIterator;
8.73 + private:
8.74 + PairReferenceType data;
8.75 + PairPointerType(const KeyType& key, ReferenceType val)
8.76 + : data(key, val) {}
8.77 + public:
8.78 + PairReferenceType* operator->() {return &data;}
8.79 + };
8.80 +
8.81 + /** Arrow operator for map.
8.82 + */
8.83 + PairPointerType operator->() {
8.84 + return PairPointerType(it, ((*map)[it]));
8.85 + }
8.86 +
8.87 + /** The pre increment operator of the map.
8.88 + */
8.89 + MapIterator& operator++() {
8.90 + ++it;
8.91 + return *this;
8.92 + }
8.93 +
8.94 + /** The post increment operator of the map.
8.95 + */
8.96 + MapIterator operator++(int) {
8.97 + MapIterator tmp(it);
8.98 + ++it;
8.99 + return tmp;
8.100 + }
8.101 +
8.102 + /** The equality operator of the map.
8.103 + */
8.104 + bool operator==(const MapIterator& p_it) const {
8.105 + return p_it.it == it;
8.106 + }
8.107 +
8.108 + /** The not-equality operator of the map.
8.109 + */
8.110 + bool operator!=(const MapIterator& p_it) const {
8.111 + return !(*this == p_it);
8.112 + }
8.113 +
8.114 + /** The equality operator of the map.
8.115 + */
8.116 + bool operator==(const MapConstIterator<Map>& p_it) const {
8.117 + return p_it.it == it;
8.118 + }
8.119 +
8.120 + /** The not-equality operator of the map.
8.121 + */
8.122 + bool operator!=(const MapConstIterator<Map>& p_it) const {
8.123 + return !(*this == p_it);
8.124 + }
8.125 +
8.126 + private:
8.127 + Map* map;
8.128 + KeyIt it;
8.129 + };
8.130 +
8.131 + /** Compatible iterator with the stl maps' iterators.
8.132 + * It iterates on pairs of a key and a value.
8.133 + */
8.134 + template <typename Map>
8.135 + class MapConstIterator {
8.136 + // friend class Map;
8.137 + friend class MapIterator<Map>;
8.138 +
8.139 + public:
8.140 +
8.141 + /// The key type of the iterator.
8.142 + typedef typename Map::KeyType KeyType;
8.143 + /// The iterator to iterate on the keys.
8.144 + typedef typename Map::KeyIt KeyIt;
8.145 +
8.146 + /// The value type of the iterator.
8.147 + typedef typename Map::ValueType ValueType;
8.148 + /// The reference type of the iterator.
8.149 + typedef typename Map::ReferenceType ReferenceType;
8.150 + /// The pointer type of the iterator.
8.151 + typedef typename Map::PointerType PointerType;
8.152 +
8.153 + /// The const value type of the iterator.
8.154 + typedef typename Map::ConstValueType ConstValueType;
8.155 + /// The const reference type of the iterator.
8.156 + typedef typename Map::ConstReferenceType ConstReferenceType;
8.157 + /// The pointer type of the iterator.
8.158 + typedef typename Map::ConstPointerType ConstPointerType;
8.159 +
8.160 + public:
8.161 +
8.162 + /** Constructor to initalize the the iterators returned
8.163 + * by the begin() and end().
8.164 + */
8.165 +
8.166 + MapConstIterator (const Map& pmap, const KeyIt& pit)
8.167 + : map(&pmap), it(pit) {}
8.168 +
8.169 + public:
8.170 +
8.171 + /** Default constructor.
8.172 + */
8.173 + MapConstIterator() {}
8.174 +
8.175 + typedef extended_pair<const KeyType&, const KeyType&,
8.176 + ConstReferenceType, ConstReferenceType> PairReferenceType;
8.177 +
8.178 + /** Dereference operator for map.
8.179 + */
8.180 + PairReferenceType operator*() {
8.181 + return PairReferenceType(it, (*map)[it]);
8.182 + }
8.183 +
8.184 + class PairPointerType {
8.185 + friend class MapConstIterator;
8.186 + private:
8.187 + PairReferenceType data;
8.188 + PairPointerType(const KeyType& key, ConstReferenceType val)
8.189 + : data(key, val) {}
8.190 + public:
8.191 + PairReferenceType* operator->() {return &data;}
8.192 + };
8.193 +
8.194 + /** Arrow operator for map.
8.195 + */
8.196 + PairPointerType operator->() {
8.197 + return PairPointerType(it, ((*map)[it]));
8.198 + }
8.199 +
8.200 + /** The pre increment operator of the map.
8.201 + */
8.202 + MapConstIterator& operator++() {
8.203 + ++it;
8.204 + return *this;
8.205 + }
8.206 +
8.207 + /** The post increment operator of the map.
8.208 + */
8.209 + MapConstIterator operator++(int) {
8.210 + MapConstIterator<Map> tmp(it);
8.211 + ++it;
8.212 + return tmp;
8.213 + }
8.214 +
8.215 + /** The equality operator of the map.
8.216 + */
8.217 + bool operator==(const MapIterator<Map>& p_it) const {
8.218 + return p_it.it == it;
8.219 + }
8.220 +
8.221 + /** The not-equality operator of the map.
8.222 + */
8.223 + bool operator!=(const MapIterator<Map>& p_it) const {
8.224 + return !(*this == p_it);
8.225 + }
8.226 +
8.227 + /** The equality operator of the map.
8.228 + */
8.229 + bool operator==(const MapConstIterator& p_it) const {
8.230 + return p_it.it == it;
8.231 + }
8.232 +
8.233 + /** The not-equality operator of the map.
8.234 + */
8.235 + bool operator!=(const MapConstIterator& p_it) const {
8.236 + return !(*this == p_it);
8.237 + }
8.238 +
8.239 + private:
8.240 + const Map* map;
8.241 + KeyIt it;
8.242 + };
8.243 +
8.244 +}
8.245 +
8.246 +#endif
9.1 --- a/src/hugo/map_registry.h Wed Sep 08 11:58:06 2004 +0000
9.2 +++ b/src/hugo/map_registry.h Wed Sep 08 12:06:45 2004 +0000
9.3 @@ -28,8 +28,6 @@
9.4 typedef K KeyType;
9.5 typedef KIt KeyIt;
9.6
9.7 -
9.8 -
9.9 /**
9.10 * MapBase is the base class of the registered maps.
9.11 * It defines the core modification operations on the maps and
10.1 --- a/src/hugo/smart_graph.h Wed Sep 08 11:58:06 2004 +0000
10.2 +++ b/src/hugo/smart_graph.h Wed Sep 08 12:06:45 2004 +0000
10.3 @@ -12,8 +12,9 @@
10.4
10.5 #include <hugo/invalid.h>
10.6
10.7 -#include <hugo/default_map_factory.h>
10.8 -#include <hugo/sym_map_factory.h>
10.9 +#include <hugo/default_map.h>
10.10 +#include <hugo/sym_map.h>
10.11 +
10.12 #include <hugo/map_registry.h>
10.13
10.14 #include <hugo/map_defines.h>
10.15 @@ -72,8 +73,10 @@
10.16 class OutEdgeIt;
10.17 class InEdgeIt;
10.18
10.19 + /// Creating map registries.
10.20 CREATE_MAP_REGISTRIES;
10.21 - CREATE_MAPS(DefaultMapFactory);
10.22 + /// Creating node and edge maps.
10.23 + CREATE_MAPS(DefaultMap);
10.24
10.25 public:
10.26
10.27 @@ -314,12 +317,14 @@
10.28 public:
10.29 typedef SymSmartGraph Graph;
10.30
10.31 - KEEP_NODE_MAP(SmartGraph);
10.32 - KEEP_EDGE_MAP(SmartGraph);
10.33 + /// Importing maps from the base class ListGraph.
10.34 + KEEP_MAPS(SmartGraph, SymSmartGraph);
10.35
10.36 + /// Creating symmetric map registry.
10.37 CREATE_SYM_EDGE_MAP_REGISTRY;
10.38 - CREATE_SYM_EDGE_MAP_FACTORY(DefaultMapFactory);
10.39 - IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
10.40 + /// Creating symmetric edge map.
10.41 + CREATE_SYM_EDGE_MAP(DefaultMap);
10.42 +
10.43
10.44 SymSmartGraph() : SmartGraph() { }
10.45 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/src/hugo/sym_map.h Wed Sep 08 12:06:45 2004 +0000
11.3 @@ -0,0 +1,170 @@
11.4 +// -*- c++ -*-
11.5 +#ifndef SYM_MAP_H
11.6 +#define SYM_MAP_H
11.7 +
11.8 +///\ingroup graphmaps
11.9 +///\file
11.10 +///\brief Graph maps that construates and destruates
11.11 +///their elements dynamically.
11.12 +
11.13 +namespace hugo {
11.14 +
11.15 +/// \addtogroup graphmaps
11.16 +/// @{
11.17 +
11.18 + /** The SymEdgeIt is wrapper class for the EdgeIt. It can be used to
11.19 + * iterate on the symmetric maps when all of the edge - reverse edge pair
11.20 + * has different parity.
11.21 + */
11.22 +
11.23 + template <typename Graph, typename Edge, typename EdgeIt>
11.24 + class SymEdgeIt : public EdgeIt {
11.25 + public:
11.26 +
11.27 + /** Default constructor.
11.28 + */
11.29 + SymEdgeIt()
11.30 + : EdgeIt() {}
11.31 +
11.32 + /** Graph initialized constructor.
11.33 + */
11.34 + SymEdgeIt(const Graph& graph)
11.35 + : EdgeIt(graph) {
11.36 + while ( (n & 1) && n != -1) {
11.37 + EdgeIt::operator++();
11.38 + }
11.39 + }
11.40 +
11.41 + /** Creating invelid SymEdgeIt.
11.42 + */
11.43 + SymEdgeIt(Invalid invalid)
11.44 + : EdgeIt(invalid) {}
11.45 +
11.46 + /** SymEdgeIt from the given Edge.
11.47 + */
11.48 + SymEdgeIt(const Graph& graph, const Edge& edge)
11.49 + : EdgeIt(graph, edge) {
11.50 + while ( (n & 1) && n != -1) {
11.51 + EdgeIt::operator++();
11.52 + }
11.53 + }
11.54 +
11.55 + /** Increase operator.
11.56 + */
11.57 + SymEdgeIt& operator++() {
11.58 + EdgeIt::operator++();
11.59 + while ( (n & 1) && n != -1) {
11.60 + EdgeIt::operator++();
11.61 + }
11.62 + return *this;
11.63 + }
11.64 + };
11.65 +
11.66 + /** The SymMap template class is graph map structure what
11.67 + * wraps an other map structure to use as symmetric map structure.
11.68 + *
11.69 + * The template parameter is the MapRegistry that the maps
11.70 + * will belong to and the ValueType.
11.71 + */
11.72 + template <template <typename, typename> class DynMap,
11.73 + typename MapRegistry, typename Value>
11.74 + class SymMap : public DynMap<MapRegistry, Value>{
11.75 +
11.76 + private:
11.77 +
11.78 + typedef DynMap<MapRegistry, Value> MapImpl;
11.79 +
11.80 + public:
11.81 +
11.82 + /// The graph type of the maps.
11.83 + typedef typename MapRegistry::Graph Graph;
11.84 +
11.85 + typedef typename MapImpl::KeyType KeyType;
11.86 +
11.87 + public:
11.88 +
11.89 +
11.90 + /** Default constructor for the map.
11.91 + */
11.92 + SymMap() : MapImpl() {}
11.93 +
11.94 + /** Graph and Registry initialized map constructor.
11.95 + */
11.96 + SymMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
11.97 +
11.98 + /** Constructor to use default value to initialize the map.
11.99 + */
11.100 + SymMap(const Graph& g, MapRegistry& r, const Value& v)
11.101 + : MapImpl(g, r, v) {}
11.102 +
11.103 + /** Constructor to copy a map of the same map type.
11.104 + */
11.105 + SymMap(const SymMap& copy)
11.106 + : MapImpl(static_cast<const MapImpl&>(copy)) {}
11.107 +
11.108 + /** Constructor to copy a map of an other map type.
11.109 + */
11.110 + template <typename CMap> SymMap(const CMap& copy)
11.111 + : MapImpl(copy) {}
11.112 +
11.113 + /** Assign operator to copy a map of the same map type.
11.114 + */
11.115 + SymMap& operator=(const SymMap& copy) {
11.116 + MapImpl::operator=(static_cast<const MapImpl&>(copy));
11.117 + return *this;
11.118 + }
11.119 +
11.120 + /** Assign operator to copy a map of an other map type.
11.121 + */
11.122 + template <typename CMap> SymMap& operator=(const CMap& copy) {
11.123 + MapImpl::operator=(copy);
11.124 + return *this;
11.125 + }
11.126 +
11.127 + /**
11.128 + * The subscript operator. The map can be subscripted by the
11.129 + * actual keys of the graph.
11.130 + */
11.131 + typename MapImpl::ReferenceType operator[](const KeyType& key) {
11.132 + int id = MapImpl::getGraph()->id(key);
11.133 + return MapImpl::operator[](id >> 1);
11.134 + }
11.135 +
11.136 + /**
11.137 + * The const subscript operator. The map can be subscripted by the
11.138 + * actual keys of the graph.
11.139 + */
11.140 + typename MapImpl::ConstReferenceType operator[](const KeyType& key) const {
11.141 + int id = MapImpl::getGraph()->id(key);
11.142 + return MapImpl::operator[](id >> 1);
11.143 + }
11.144 +
11.145 + /** Setter function of the map. Equivalent with map[key] = val.
11.146 + * This is a compatibility feature with the not dereferable maps.
11.147 + */
11.148 + void set(const KeyType& key, const typename MapImpl::ValueType& val) {
11.149 + int id = MapImpl::getGraph()->id(key);
11.150 + MapImpl::operator[](id >> 1) = val;
11.151 + }
11.152 +
11.153 + /** Add a new key to the map. It called by the map registry.
11.154 + */
11.155 + void add(const KeyType& key) {
11.156 + int id = MapImpl::getGraph()->id(key);
11.157 + if (id & 1) return;
11.158 + MapImpl::add(key);
11.159 + }
11.160 +
11.161 + /** Erase a key from the map. It called by the map registry.
11.162 + */
11.163 + void erase(const KeyType& key) {
11.164 + int id = MapImpl::getGraph()->id(key);
11.165 + if (id & 1) return;
11.166 + MapImpl::add(key);
11.167 + }
11.168 + };
11.169 +
11.170 + /// @}
11.171 +}
11.172 +
11.173 +#endif
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/hugo/vector_map.h Wed Sep 08 12:06:45 2004 +0000
12.3 @@ -0,0 +1,216 @@
12.4 +// -*- c++ -*-
12.5 +#ifndef VECTOR_MAP_H
12.6 +#define VECTOR_MAP_H
12.7 +
12.8 +#include <vector>
12.9 +
12.10 +#include <hugo/map_iterator.h>
12.11 +
12.12 +///\ingroup graphmaps
12.13 +///\file
12.14 +///\brief Vector based graph maps.
12.15 +
12.16 +namespace hugo {
12.17 +
12.18 + /// \addtogroup graphmaps
12.19 + /// @{
12.20 +
12.21 + /** The ArrayMap template class is graph map structure what
12.22 + * automatically updates the map when a key is added to or erased from
12.23 + * the map. This map factory uses the allocators to implement
12.24 + * the container functionality. This map factory
12.25 + * uses the std::vector to implement the container function.
12.26 + *
12.27 + * The template parameter is the MapRegistry that the maps
12.28 + * will belong to and the ValueType.
12.29 + *
12.30 + * \todo It should use a faster initialization using the maxNodeId() or
12.31 + * maxEdgeId() function of the graph instead of iterating through each
12.32 + * edge/node.
12.33 + */
12.34 +
12.35 + template <typename MapRegistry, typename Value>
12.36 + class VectorMap : public MapRegistry::MapBase {
12.37 + public:
12.38 +
12.39 + /// The graph type of the maps.
12.40 + typedef typename MapRegistry::Graph Graph;
12.41 + /// The key type of the maps.
12.42 + typedef typename MapRegistry::KeyType KeyType;
12.43 + /// The iterator to iterate on the keys.
12.44 + typedef typename MapRegistry::KeyIt KeyIt;
12.45 +
12.46 + /// The map type.
12.47 + typedef VectorMap Map;
12.48 + /// The MapBase of the Map which implements the core regisitry function.
12.49 + typedef typename MapRegistry::MapBase MapBase;
12.50 +
12.51 + private:
12.52 +
12.53 + /// The container type of the map.
12.54 + typedef std::vector<Value> Container;
12.55 +
12.56 + public:
12.57 +
12.58 +
12.59 + /// The value type of the map.
12.60 + typedef Value ValueType;
12.61 + /// The reference type of the map;
12.62 + typedef typename Container::reference ReferenceType;
12.63 + /// The pointer type of the map;
12.64 + typedef typename Container::pointer PointerType;
12.65 +
12.66 + /// The const value type of the map.
12.67 + typedef const Value ConstValueType;
12.68 + /// The const reference type of the map;
12.69 + typedef typename Container::const_reference ConstReferenceType;
12.70 + /// The pointer type of the map;
12.71 + typedef typename Container::const_pointer ConstPointerType;
12.72 +
12.73 + /** Default constructor for the map.
12.74 + */
12.75 + VectorMap() {}
12.76 +
12.77 + /** Graph and Registry initialized map constructor.
12.78 + */
12.79 + VectorMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
12.80 + init();
12.81 + }
12.82 +
12.83 + /** Constructor to use default value to initialize the map.
12.84 + */
12.85 + VectorMap(const Graph& g, MapRegistry& r, const Value& v)
12.86 + : MapBase(g, r) {
12.87 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
12.88 + int id = getGraph()->id(it);
12.89 + if (id >= (int)container.size()) {
12.90 + container.resize(id + 1);
12.91 + }
12.92 + set(it, v);
12.93 + }
12.94 + }
12.95 +
12.96 + /** Constructor to copy a map of an other map type.
12.97 + */
12.98 + template <typename CMap> VectorMap(const CMap& copy) : MapBase(copy) {
12.99 + if (getGraph()) {
12.100 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
12.101 + int id = getGraph()->id(it);
12.102 + if (id >= (int)container.size()) {
12.103 + container.resize(id + 1);
12.104 + }
12.105 + set(it, copy[it]);
12.106 + }
12.107 + }
12.108 + }
12.109 +
12.110 + /** Assign operator to copy a map an other map type.
12.111 + */
12.112 + template <typename CMap> VectorMap& operator=(const CMap& copy) {
12.113 + if (getGraph()) {
12.114 + destroy();
12.115 + }
12.116 + this->MapBase::operator=(copy);
12.117 + if (getGraph()) {
12.118 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
12.119 + int id = getGraph()->id(it);
12.120 + if (id >= (int)container.size()) {
12.121 + container.resize(id + 1);
12.122 + }
12.123 + set(it, copy[it]);
12.124 + }
12.125 + }
12.126 + return *this;
12.127 + }
12.128 +
12.129 + /** The destructor of the map.
12.130 + */
12.131 + virtual ~VectorMap() {
12.132 + }
12.133 +
12.134 + /**
12.135 + * The subscript operator. The map can be subscripted by the
12.136 + * actual keys of the graph.
12.137 + */
12.138 + ReferenceType operator[](const KeyType& key) {
12.139 + int id = getGraph()->id(key);
12.140 + return container[id];
12.141 + }
12.142 +
12.143 + /**
12.144 + * The const subscript operator. The map can be subscripted by the
12.145 + * actual keys of the graph.
12.146 + */
12.147 + ConstReferenceType operator[](const KeyType& key) const {
12.148 + int id = getGraph()->id(key);
12.149 + return container[id];
12.150 + }
12.151 +
12.152 + /** Setter function of the map. Equivalent with map[key] = val.
12.153 + * This is a compatibility feature with the not dereferable maps.
12.154 + */
12.155 + void set(const KeyType& key, const ValueType& val) {
12.156 + int id = getGraph()->id(key);
12.157 + container[id] = val;
12.158 + }
12.159 +
12.160 + /** Add a new key to the map. It called by the map registry.
12.161 + */
12.162 + void add(const KeyType& key) {
12.163 + int id = getGraph()->id(key);
12.164 + if (id >= (int)container.size()) {
12.165 + container.resize(id + 1);
12.166 + }
12.167 + }
12.168 +
12.169 + /** Erase a key from the map. It called by the map registry.
12.170 + */
12.171 + void erase(const KeyType& key) {}
12.172 +
12.173 + /** Clear the data structure.
12.174 + */
12.175 + void clear() {
12.176 + container.clear();
12.177 + }
12.178 +
12.179 + /// The stl compatible pair iterator of the map.
12.180 + typedef MapIterator<VectorMap> Iterator;
12.181 + /// The stl compatible const pair iterator of the map.
12.182 + typedef MapConstIterator<VectorMap> ConstIterator;
12.183 +
12.184 + /** Returns the begin iterator of the map.
12.185 + */
12.186 + Iterator begin() {
12.187 + return Iterator(*this, KeyIt(*MapBase::getGraph()));
12.188 + }
12.189 +
12.190 + /** Returns the end iterator of the map.
12.191 + */
12.192 + Iterator end() {
12.193 + return Iterator(*this, INVALID);
12.194 + }
12.195 +
12.196 + /** Returns the begin ConstIterator of the map.
12.197 + */
12.198 + ConstIterator begin() const {
12.199 + return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
12.200 + }
12.201 +
12.202 + /** Returns the end const_iterator of the map.
12.203 + */
12.204 + ConstIterator end() const {
12.205 + return ConstIterator(*this, INVALID);
12.206 + }
12.207 +
12.208 + private:
12.209 +
12.210 + Container container;
12.211 +
12.212 +
12.213 + };
12.214 +
12.215 + /// @}
12.216 +
12.217 +}
12.218 +
12.219 +#endif
13.1 --- a/src/hugo/vector_map_factory.h Wed Sep 08 11:58:06 2004 +0000
13.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
13.3 @@ -1,373 +0,0 @@
13.4 -// -*- c++ -*-
13.5 -#ifndef VECTOR_MAP_H
13.6 -#define VECTOR_MAP_H
13.7 -
13.8 -#include <vector>
13.9 -
13.10 -#include <hugo/extended_pair.h>
13.11 -
13.12 -///\ingroup graphmapfactory
13.13 -///\file
13.14 -///\brief Vector based graph maps.
13.15 -
13.16 -namespace hugo {
13.17 -
13.18 - /// \addtogroup graphmapfactory
13.19 - /// @{
13.20 -
13.21 - /** The VectorMapFactory template class is a factory class
13.22 - * to create maps for the edge and nodes. This map factory
13.23 - * uses the std::vector to implement the container function.
13.24 - *
13.25 - * The template parameter is the MapRegistry that the maps
13.26 - * will belong to.
13.27 - *
13.28 - * \todo It should use a faster initialization using the maxNodeId() or
13.29 - * maxEdgeId() function of the graph istead of iterating through each
13.30 - * edge/node.
13.31 - */
13.32 -
13.33 - template <typename MapRegistry>
13.34 - class VectorMapFactory {
13.35 - public:
13.36 -
13.37 - /// The graph type of the maps.
13.38 - typedef typename MapRegistry::Graph Graph;
13.39 - /// The key type of the maps.
13.40 - typedef typename MapRegistry::KeyType KeyType;
13.41 - /// The iterator to iterate on the keys.
13.42 - typedef typename MapRegistry::KeyIt KeyIt;
13.43 -
13.44 - /// The MapBase of the Map which imlements the core regisitry function.
13.45 - typedef typename MapRegistry::MapBase MapBase;
13.46 -
13.47 -
13.48 - /** The template Map type.
13.49 - */
13.50 - template <typename V>
13.51 - class Map : public MapBase {
13.52 -
13.53 - typedef std::vector<V> Container;
13.54 -
13.55 - public:
13.56 -
13.57 - /// The value type of the map.
13.58 - typedef V ValueType;
13.59 -
13.60 - /// The value type of the map.
13.61 - typedef V Value;
13.62 - /// The reference type of the map;
13.63 - typedef typename Container::reference Reference;
13.64 - /// The pointer type of the map;
13.65 - typedef typename Container::pointer Pointer;
13.66 -
13.67 - /// The const value type of the map.
13.68 - typedef const Value ConstValue;
13.69 - /// The const reference type of the map;
13.70 - typedef typename Container::const_reference ConstReference;
13.71 - /// The pointer type of the map;
13.72 - typedef typename Container::const_pointer ConstPointer;
13.73 -
13.74 - /** Default constructor for the map.
13.75 - */
13.76 - Map() {}
13.77 -
13.78 - /** Graph and Registry initialized map constructor.
13.79 - */
13.80 - Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
13.81 - init();
13.82 - }
13.83 -
13.84 - /** Constructor to use default value to initialize the map.
13.85 - */
13.86 - Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
13.87 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
13.88 - int id = getGraph()->id(it);
13.89 - if (id >= (int)container.size()) {
13.90 - container.resize(id + 1);
13.91 - }
13.92 - set(it, v);
13.93 - }
13.94 - }
13.95 -
13.96 - /** Constructor to copy a map of an other map type.
13.97 - */
13.98 - template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
13.99 - if (getGraph()) {
13.100 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
13.101 - int id = getGraph()->id(it);
13.102 - if (id >= (int)container.size()) {
13.103 - container.resize(id + 1);
13.104 - }
13.105 - set(it, copy[it]);
13.106 - }
13.107 - }
13.108 - }
13.109 -
13.110 - /** Assign operator to copy a map an other map type.
13.111 - */
13.112 - template <typename CMap> Map& operator=(const CMap& copy) {
13.113 - if (getGraph()) {
13.114 - destroy();
13.115 - }
13.116 - this->MapBase::operator=(copy);
13.117 - if (getGraph()) {
13.118 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
13.119 - int id = getGraph()->id(it);
13.120 - if (id >= (int)container.size()) {
13.121 - container.resize(id + 1);
13.122 - }
13.123 - set(it, copy[it]);
13.124 - }
13.125 - }
13.126 - return *this;
13.127 - }
13.128 -
13.129 - /** The destructor of the map.
13.130 - */
13.131 - virtual ~Map() {
13.132 - }
13.133 -
13.134 - /**
13.135 - * The subscript operator. The map can be subscripted by the
13.136 - * actual keys of the graph.
13.137 - */
13.138 - Reference operator[](const KeyType& key) {
13.139 - int id = getGraph()->id(key);
13.140 - return container[id];
13.141 - }
13.142 -
13.143 - /**
13.144 - * The const subscript operator. The map can be subscripted by the
13.145 - * actual keys of the graph.
13.146 - */
13.147 - ConstReference operator[](const KeyType& key) const {
13.148 - int id = getGraph()->id(key);
13.149 - return container[id];
13.150 - }
13.151 -
13.152 - /** Setter function of the map. Equivalent with map[key] = val.
13.153 - * This is a compatibility feature with the not dereferable maps.
13.154 - */
13.155 - void set(const KeyType& key, const Value& val) {
13.156 - int id = getGraph()->id(key);
13.157 - container[id] = val;
13.158 - }
13.159 -
13.160 - /** Add a new key to the map. It called by the map registry.
13.161 - */
13.162 - void add(const KeyType& key) {
13.163 - int id = getGraph()->id(key);
13.164 - if (id >= (int)container.size()) {
13.165 - container.resize(id + 1);
13.166 - }
13.167 - }
13.168 -
13.169 - /** Erase a key from the map. It called by the map registry.
13.170 - */
13.171 - void erase(const KeyType& key) {}
13.172 -
13.173 - /** Clear the data structure.
13.174 - */
13.175 - void clear() {
13.176 - container.clear();
13.177 - }
13.178 -
13.179 - class iterator;
13.180 - class const_iterator;
13.181 -
13.182 - /** Compatible iterator with the stl maps' iterators.
13.183 - * It iterates on pairs of a key and a value.
13.184 - */
13.185 - class iterator {
13.186 - friend class Map;
13.187 - friend class const_iterator;
13.188 - private:
13.189 -
13.190 - /** Private constructor to initalize the the iterators returned
13.191 - * by the begin() and end().
13.192 - */
13.193 - iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
13.194 -
13.195 - public:
13.196 -
13.197 - /** Default constructor.
13.198 - */
13.199 - iterator() {}
13.200 -
13.201 - typedef extended_pair<const KeyType&, const KeyType&,
13.202 - Map::Reference, Map::Reference> Reference;
13.203 -
13.204 - /** Dereference operator for map.
13.205 - */
13.206 - Reference operator*() {
13.207 - return Reference(it, (*map)[it]);
13.208 - }
13.209 -
13.210 - class Pointer {
13.211 - friend class iterator;
13.212 - private:
13.213 - Reference data;
13.214 - Pointer(const KeyType& key, Map::Reference val) : data(key, val) {}
13.215 - public:
13.216 - Reference* operator->() {return &data;}
13.217 - };
13.218 -
13.219 - /** Arrow operator for map.
13.220 - */
13.221 - Pointer operator->() {
13.222 - return Pointer(it, ((*map)[it]));
13.223 - }
13.224 -
13.225 - /** The pre increment operator of the map.
13.226 - */
13.227 - iterator& operator++() {
13.228 - ++it;
13.229 - return *this;
13.230 - }
13.231 -
13.232 - /** The post increment operator of the map.
13.233 - */
13.234 - iterator operator++(int) {
13.235 - iterator tmp(it);
13.236 - ++it;
13.237 - return tmp;
13.238 - }
13.239 -
13.240 - /** The equality operator of the map.
13.241 - */
13.242 - bool operator==(const_iterator p_it) {
13.243 - return p_it.it == it;
13.244 - }
13.245 -
13.246 - /** The not-equality operator of the map.
13.247 - */
13.248 - bool operator!=(const_iterator p_it) {
13.249 - return !(*this == p_it);
13.250 - }
13.251 -
13.252 -
13.253 - private:
13.254 - Map* map;
13.255 - KeyIt it;
13.256 - };
13.257 -
13.258 - /** Returns the begin iterator of the map.
13.259 - */
13.260 - iterator begin() {
13.261 - return iterator(*this, KeyIt(*getGraph()));
13.262 - }
13.263 -
13.264 - /** Returns the end iterator of the map.
13.265 - */
13.266 - iterator end() {
13.267 - return iterator(*this, INVALID);
13.268 - }
13.269 -
13.270 - class const_iterator {
13.271 - friend class Map;
13.272 - friend class iterator;
13.273 - private:
13.274 -
13.275 - /** Private constructor to initalize the the iterators returned
13.276 - * by the begin() and end().
13.277 - */
13.278 - const_iterator (const Map& pmap, const KeyIt& pit)
13.279 - : map(&pmap), it(pit) {}
13.280 -
13.281 - public:
13.282 -
13.283 - /** Default constructor.
13.284 - */
13.285 - const_iterator() {}
13.286 -
13.287 - /** Constructor to convert iterator to const_iterator.
13.288 - */
13.289 - const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
13.290 -
13.291 - typedef extended_pair<const KeyType&, const KeyType&,
13.292 - Map::ConstReference, Map::ConstReference> Reference;
13.293 -
13.294 - /** Dereference operator for map.
13.295 - */
13.296 - Reference operator*() {
13.297 - return Reference(it, (*map)[it]);
13.298 - }
13.299 -
13.300 -
13.301 - class Pointer {
13.302 - friend class const_iterator;
13.303 - private:
13.304 - Reference data;
13.305 - Pointer(const KeyType& key, Map::ConstReference val)
13.306 - : data(key, val) {}
13.307 - public:
13.308 - Reference* operator->() {return &data;}
13.309 - };
13.310 -
13.311 - /** Arrow operator for map.
13.312 - */
13.313 - Pointer operator->() {
13.314 - return Pointer(it, ((*map)[it]));
13.315 - }
13.316 -
13.317 - /** The pre increment operator of the map.
13.318 - */
13.319 - const_iterator& operator++() {
13.320 - ++it;
13.321 - return *this;
13.322 - }
13.323 -
13.324 - /** The post increment operator of the map.
13.325 - */
13.326 - const_iterator operator++(int) {
13.327 - const_iterator tmp(it);
13.328 - ++it;
13.329 - return tmp;
13.330 - }
13.331 -
13.332 - /** The equality operator of the map.
13.333 - */
13.334 - bool operator==(const_iterator p_it) {
13.335 - return p_it.it == it;
13.336 - }
13.337 -
13.338 - /** The not-equality operator of the map.
13.339 - */
13.340 - bool operator!=(const_iterator p_it) {
13.341 - return !(*this == p_it);
13.342 - }
13.343 -
13.344 -
13.345 - private:
13.346 - const Map* map;
13.347 - KeyIt it;
13.348 - };
13.349 -
13.350 - /** Returns the begin const_iterator of the map.
13.351 - */
13.352 - const_iterator begin() const {
13.353 - return const_iterator(*this, KeyIt(*getGraph()));
13.354 - }
13.355 -
13.356 - /** Returns the end const_iterator of the map.
13.357 - */
13.358 - const_iterator end() const {
13.359 - return const_iterator(*this, INVALID);
13.360 - }
13.361 -
13.362 - private:
13.363 -
13.364 - Container container;
13.365 -
13.366 - };
13.367 -
13.368 - };
13.369 -
13.370 -
13.371 - /// @}
13.372 -
13.373 -
13.374 -}
13.375 -
13.376 -#endif