1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/array_map_factory.h Thu Sep 02 10:07:30 2004 +0000
1.3 @@ -0,0 +1,366 @@
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 +namespace hugo {
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(*MapBase::getGraph()); it != INVALID; ++it) {
1.38 + int id = MapBase::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(*MapBase::getGraph()); it != INVALID; ++it) {
1.46 + int id = MapBase::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(*MapBase::getGraph()); it != INVALID; ++it) {
1.56 + int id = MapBase::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 (MapBase::getGraph()) {
1.64 + allocate_memory();
1.65 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++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 *this;
1.73 + if (capacity != 0) {
1.74 + MapBase::destroy();
1.75 + allocator.deallocate(values, capacity);
1.76 + }
1.77 + capacity = copy.capacity;
1.78 + if (capacity == 0) return *this;
1.79 + values = allocator.allocate(capacity);
1.80 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.81 + int id = MapBase::getGraph()->id(it);
1.82 + allocator.construct(&(values[id]), copy.values[id]);
1.83 + }
1.84 + return *this;
1.85 + }
1.86 +
1.87 + template <typename CMap> Map& operator=(const CMap& copy) {
1.88 + if (MapBase::getGraph()) {
1.89 + MapBase::destroy();
1.90 + }
1.91 + MapBase::operator=(copy);
1.92 + if (MapBase::getGraph()) {
1.93 + allocate_memory();
1.94 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.95 + set(it, copy[it]);
1.96 + }
1.97 + }
1.98 + return *this;
1.99 + }
1.100 +
1.101 + virtual ~Map() {
1.102 + if (capacity != 0) {
1.103 + MapBase::destroy();
1.104 + allocator.deallocate(values, capacity);
1.105 + }
1.106 + }
1.107 +
1.108 +
1.109 + Value& operator[](const Key& key) {
1.110 + int id = MapBase::getGraph()->id(key);
1.111 + return values[id];
1.112 + }
1.113 +
1.114 + const Value& operator[](const Key& key) const {
1.115 + int id = MapBase::getGraph()->id(key);
1.116 + return values[id];
1.117 + }
1.118 +
1.119 + const Value& get(const Key& key) const {
1.120 + int id = MapBase::getGraph()->id(key);
1.121 + return values[id];
1.122 + }
1.123 +
1.124 + void set(const Key& key, const Value& val) {
1.125 + int id = MapBase::getGraph()->id(key);
1.126 + values[id] = val;
1.127 + }
1.128 +
1.129 + void add(const Key& key) {
1.130 + int id = MapBase::getGraph()->id(key);
1.131 + if (id >= capacity) {
1.132 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.133 + while (new_capacity <= id) {
1.134 + new_capacity <<= 1;
1.135 + }
1.136 + Value* new_values = allocator.allocate(new_capacity);;
1.137 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.138 + int jd = MapBase::getGraph()->id(it);
1.139 + if (id != jd) {
1.140 + allocator.construct(&(new_values[jd]), values[jd]);
1.141 + allocator.destroy(&(values[jd]));
1.142 + }
1.143 + }
1.144 + if (capacity != 0) allocator.deallocate(values, capacity);
1.145 + values = new_values;
1.146 + capacity = new_capacity;
1.147 + }
1.148 + allocator.construct(&(values[id]), Value());
1.149 + }
1.150 +
1.151 + void erase(const Key& key) {
1.152 + int id = MapBase::getGraph()->id(key);
1.153 + allocator.destroy(&(values[id]));
1.154 + }
1.155 +
1.156 + void clear() {
1.157 + if (capacity != 0) {
1.158 + MapBase::destroy();
1.159 + allocator.deallocate(values, capacity);
1.160 + capacity = 0;
1.161 + }
1.162 + }
1.163 +
1.164 + class iterator {
1.165 + friend class Map;
1.166 + friend class const_iterator;
1.167 + private:
1.168 +
1.169 + /** Private constructor to initalize the the iterators returned
1.170 + * by the begin() and end().
1.171 + */
1.172 + iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.173 +
1.174 + public:
1.175 +
1.176 + /** Default constructor.
1.177 + */
1.178 + iterator() {}
1.179 +
1.180 + typedef extended_pair<const Key&, const Key&,
1.181 + Value&, Value&> Reference;
1.182 +
1.183 + /** Dereference operator for map.
1.184 + */
1.185 + Reference operator*() {
1.186 + return Reference(it, (*map)[it]);
1.187 + }
1.188 +
1.189 + class Pointer {
1.190 + friend class iterator;
1.191 + private:
1.192 + Reference data;
1.193 + Pointer(const Key& key, Value& val) : data(key, val) {}
1.194 + public:
1.195 + Reference* operator->() {return &data;}
1.196 + };
1.197 +
1.198 + /** Arrow operator for map.
1.199 + */
1.200 + Pointer operator->() {
1.201 + return Pointer(it, ((*map)[it]));
1.202 + }
1.203 +
1.204 + /** The pre increment operator of the map.
1.205 + */
1.206 + iterator& operator++() {
1.207 + ++it;
1.208 + return *this;
1.209 + }
1.210 +
1.211 + /** The post increment operator of the map.
1.212 + */
1.213 + iterator operator++(int) {
1.214 + iterator tmp(it);
1.215 + ++it;
1.216 + return tmp;
1.217 + }
1.218 +
1.219 + /** The equality operator of the map.
1.220 + */
1.221 + bool operator==(const_iterator p_it) {
1.222 + return p_it.it == it;
1.223 + }
1.224 +
1.225 + /** The not-equality operator of the map.
1.226 + */
1.227 + bool operator!=(const_iterator p_it) {
1.228 + return !(*this == p_it);
1.229 + }
1.230 +
1.231 +
1.232 + private:
1.233 + Map* map;
1.234 + KeyIt it;
1.235 + };
1.236 +
1.237 + /** Returns the begin iterator of the map.
1.238 + */
1.239 + iterator begin() {
1.240 + return iterator(*this, KeyIt(*MapBase::getGraph()));
1.241 + }
1.242 +
1.243 + /** Returns the end iterator of the map.
1.244 + */
1.245 + iterator end() {
1.246 + return iterator(*this, INVALID);
1.247 + }
1.248 +
1.249 + class const_iterator {
1.250 + friend class Map;
1.251 + friend class iterator;
1.252 + private:
1.253 +
1.254 + /** Private constructor to initalize the the iterators returned
1.255 + * by the begin() and end().
1.256 + */
1.257 + const_iterator (const Map& pmap, const KeyIt& pit)
1.258 + : map(&pmap), it(pit) {}
1.259 +
1.260 + public:
1.261 +
1.262 + /** Default constructor.
1.263 + */
1.264 + const_iterator() {}
1.265 +
1.266 + /** Constructor to convert iterator to const_iterator.
1.267 + */
1.268 + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
1.269 +
1.270 + typedef extended_pair<const Key&, const Key&,
1.271 + const Value&, const Value&> Reference;
1.272 +
1.273 + /** Dereference operator for map.
1.274 + */
1.275 + Reference operator*() {
1.276 + return Reference(it, (*map)[it]);
1.277 + }
1.278 +
1.279 +
1.280 + class Pointer {
1.281 + friend class const_iterator;
1.282 + private:
1.283 + Reference data;
1.284 + Pointer(const Key& key, const Value& val) : data(key, val) {}
1.285 + public:
1.286 + Reference* operator->() {return &data;}
1.287 + };
1.288 +
1.289 + /** Arrow operator for map.
1.290 + */
1.291 + Pointer operator->() {
1.292 + return Pointer(it, ((*map)[it]));
1.293 + }
1.294 +
1.295 + /** The pre increment operator of the map.
1.296 + */
1.297 + const_iterator& operator++() {
1.298 + ++it;
1.299 + return *this;
1.300 + }
1.301 +
1.302 + /** The post increment operator of the map.
1.303 + */
1.304 + const_iterator operator++(int) {
1.305 + const_iterator tmp(it);
1.306 + ++it;
1.307 + return tmp;
1.308 + }
1.309 +
1.310 + /** The equality operator of the map.
1.311 + */
1.312 + bool operator==(const_iterator p_it) {
1.313 + return p_it.it == it;
1.314 + }
1.315 +
1.316 + /** The not-equality operator of the map.
1.317 + */
1.318 + bool operator!=(const_iterator p_it) {
1.319 + return !(*this == p_it);
1.320 + }
1.321 +
1.322 +
1.323 + private:
1.324 + const Map* map;
1.325 + KeyIt it;
1.326 + };
1.327 +
1.328 + /** Returns the begin const_iterator of the map.
1.329 + */
1.330 + const_iterator begin() const {
1.331 + return const_iterator(*this, KeyIt(*MapBase::getGraph()));
1.332 + }
1.333 +
1.334 + /** Returns the end const_iterator of the map.
1.335 + */
1.336 + const_iterator end() const {
1.337 + return const_iterator(*this, INVALID);
1.338 + }
1.339 +
1.340 + private:
1.341 +
1.342 + void allocate_memory() {
1.343 + int max_id = -1;
1.344 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.345 + int id = MapBase::getGraph()->id(it);
1.346 + if (id > max_id) {
1.347 + max_id = id;
1.348 + }
1.349 + }
1.350 + if (max_id == -1) {
1.351 + capacity = 0;
1.352 + values = 0;
1.353 + return;
1.354 + }
1.355 + capacity = 1;
1.356 + while (capacity <= max_id) {
1.357 + capacity <<= 1;
1.358 + }
1.359 + values = allocator.allocate(capacity);
1.360 + }
1.361 +
1.362 + int capacity;
1.363 + Value* values;
1.364 + Allocator allocator;
1.365 + };
1.366 + };
1.367 +}
1.368 +
1.369 +#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/extended_pair.h Thu Sep 02 10:07:30 2004 +0000
2.3 @@ -0,0 +1,65 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef EXTENDED_PAIR_H
2.6 +#define EXTENDED_PAIR_H
2.7 +
2.8 +template <typename T1, typename A1, typename T2, typename A2>
2.9 +struct extended_pair {
2.10 + typedef T1 first_type;
2.11 + typedef T2 second_type;
2.12 +
2.13 + extended_pair() : first(), second() {}
2.14 +
2.15 + extended_pair(A1 f, A2 s) : first(f), second(s) {}
2.16 +
2.17 + template <class Pair>
2.18 + extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
2.19 +
2.20 + T1 first;
2.21 + T2 second;
2.22 +};
2.23 +
2.24 +template <typename T1, typename T2,
2.25 + typename LA1, typename LA2, typename RA1, typename RA2>
2.26 +bool operator==(const extended_pair<T1, LA1, T2, LA2>& left,
2.27 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.28 + return left.first == right.first && left.second == right.second;
2.29 +}
2.30 +
2.31 +template <typename T1, typename T2,
2.32 + typename LA1, typename LA2, typename RA1, typename RA2>
2.33 +bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left,
2.34 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.35 + return !(left == right);
2.36 +}
2.37 +
2.38 +template <typename T1, typename T2,
2.39 + typename LA1, typename LA2, typename RA1, typename RA2>
2.40 +bool operator<(const extended_pair<T1, LA1, T2, LA2>& left,
2.41 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.42 + if (left.first == right.first) return left.second == right.second;
2.43 + return left.first < right.first;
2.44 +}
2.45 +
2.46 +template <typename T1, typename T2,
2.47 + typename LA1, typename LA2, typename RA1, typename RA2>
2.48 +bool operator>(const extended_pair<T1, LA1, T2, LA2>& left,
2.49 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.50 + return right < left;
2.51 +}
2.52 +
2.53 +template <typename T1, typename T2,
2.54 + typename LA1, typename LA2, typename RA1, typename RA2>
2.55 +bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left,
2.56 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.57 + return !(right > left);
2.58 +}
2.59 +
2.60 +template <typename T1, typename T2,
2.61 + typename LA1, typename LA2, typename RA1, typename RA2>
2.62 +bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left,
2.63 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.64 + return !(right < left);
2.65 +}
2.66 +
2.67 +
2.68 +#endif
3.1 --- a/src/hugo/full_graph.h Wed Sep 01 15:37:36 2004 +0000
3.2 +++ b/src/hugo/full_graph.h Thu Sep 02 10:07:30 2004 +0000
3.3 @@ -8,10 +8,13 @@
3.4 ///\brief FullGraph and SymFullGraph classes.
3.5
3.6 #include <vector>
3.7 -#include <limits.h>
3.8 +#include <climits>
3.9
3.10 #include <hugo/invalid.h>
3.11
3.12 +#include <hugo/map_registry.h>
3.13 +#include <hugo/array_map_factory.h>
3.14 +
3.15 namespace hugo {
3.16
3.17 /// \addtogroup graphs
3.18 @@ -33,18 +36,19 @@
3.19 int NodeNum;
3.20 int EdgeNum;
3.21 public:
3.22 - template <typename T> class EdgeMap;
3.23 - template <typename T> class NodeMap;
3.24 +
3.25 + typedef FullGraph Graph;
3.26
3.27 class Node;
3.28 class Edge;
3.29 +
3.30 class NodeIt;
3.31 class EdgeIt;
3.32 class OutEdgeIt;
3.33 class InEdgeIt;
3.34
3.35 - template <typename T> class NodeMap;
3.36 - template <typename T> class EdgeMap;
3.37 + CREATE_MAP_REGISTRIES;
3.38 + CREATE_MAPS(ArrayMapFactory);
3.39
3.40 public:
3.41
3.42 @@ -85,7 +89,7 @@
3.43 /// \return The found edge or INVALID if there is no such an edge.
3.44 Edge findEdge(Node u,Node v, Edge prev = INVALID)
3.45 {
3.46 - return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
3.47 + return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
3.48 }
3.49
3.50
3.51 @@ -187,110 +191,6 @@
3.52 { if(!((++n)%G->NodeNum)) n=-1; return *this; }
3.53 };
3.54
3.55 - template <typename T> class NodeMap
3.56 - {
3.57 - std::vector<T> container;
3.58 -
3.59 - public:
3.60 - typedef T ValueType;
3.61 - typedef Node KeyType;
3.62 -
3.63 - NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
3.64 - NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
3.65 - NodeMap(const NodeMap<T> &m) : container(m.container) { }
3.66 -
3.67 - template<typename TT> friend class NodeMap;
3.68 - ///\todo It can copy between different types.
3.69 - template<typename TT> NodeMap(const NodeMap<TT> &m)
3.70 - : container(m.container.size())
3.71 - {
3.72 - typename std::vector<TT>::const_iterator i;
3.73 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.74 - i!=m.container.end();
3.75 - i++)
3.76 - container.push_back(*i);
3.77 - }
3.78 - void set(Node n, T a) { container[n.n]=a; }
3.79 - //'T& operator[](Node n)' would be wrong here
3.80 - typename std::vector<T>::reference
3.81 - operator[](Node n) { return container[n.n]; }
3.82 - //'const T& operator[](Node n)' would be wrong here
3.83 - typename std::vector<T>::const_reference
3.84 - operator[](Node n) const { return container[n.n]; }
3.85 -
3.86 - ///\warning There is no safety check at all!
3.87 - ///Using operator = between maps attached to different graph may
3.88 - ///cause serious problem.
3.89 - ///\todo Is this really so?
3.90 - ///\todo It can copy between different types.
3.91 - const NodeMap<T>& operator=(const NodeMap<T> &m)
3.92 - {
3.93 - container = m.container;
3.94 - return *this;
3.95 - }
3.96 - template<typename TT>
3.97 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
3.98 - {
3.99 - std::copy(m.container.begin(), m.container.end(), container.begin());
3.100 - return *this;
3.101 - }
3.102 -
3.103 - void update() {} //Useless for Dynamic Maps
3.104 - void update(T a) {} //Useless for Dynamic Maps
3.105 - };
3.106 -
3.107 - template <typename T> class EdgeMap
3.108 - {
3.109 - std::vector<T> container;
3.110 -
3.111 - public:
3.112 - typedef T ValueType;
3.113 - typedef Edge KeyType;
3.114 -
3.115 - EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
3.116 - EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { }
3.117 - EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
3.118 -
3.119 - template<typename TT> friend class EdgeMap;
3.120 - ///\todo It can copy between different types.
3.121 - ///\todo We could use 'copy'
3.122 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
3.123 - container(m.container.size())
3.124 - {
3.125 - typename std::vector<TT>::const_iterator i;
3.126 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.127 - i!=m.container.end();
3.128 - i++)
3.129 - container.push_back(*i);
3.130 - }
3.131 - void set(Edge n, T a) { container[n.n]=a; }
3.132 - //T get(Edge n) const { return container[n.n]; }
3.133 - typename std::vector<T>::reference
3.134 - operator[](Edge n) { return container[n.n]; }
3.135 - typename std::vector<T>::const_reference
3.136 - operator[](Edge n) const { return container[n.n]; }
3.137 -
3.138 - ///\warning There is no safety check at all!
3.139 - ///Using operator = between maps attached to different graph may
3.140 - ///cause serious problem.
3.141 - ///\todo Is this really so?
3.142 - ///\todo It can copy between different types.
3.143 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
3.144 - {
3.145 - container = m.container;
3.146 - return *this;
3.147 - }
3.148 - template<typename TT>
3.149 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
3.150 - {
3.151 - std::copy(m.container.begin(), m.container.end(), container.begin());
3.152 - return *this;
3.153 - }
3.154 -
3.155 - void update() {}
3.156 - void update(T a) {}
3.157 - };
3.158 -
3.159 };
3.160
3.161 /// @}
4.1 --- a/src/hugo/list_graph.h Wed Sep 01 15:37:36 2004 +0000
4.2 +++ b/src/hugo/list_graph.h Thu Sep 02 10:07:30 2004 +0000
4.3 @@ -8,16 +8,24 @@
4.4 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
4.5
4.6 #include <vector>
4.7 -#include <limits.h>
4.8 +#include <climits>
4.9
4.10 #include <hugo/invalid.h>
4.11
4.12 +#include <hugo/map_registry.h>
4.13 +#include <hugo/array_map_factory.h>
4.14 +
4.15 +#include <hugo/sym_map_factory.h>
4.16 +
4.17 +#include <hugo/map_defines.h>
4.18 +
4.19 +
4.20 namespace hugo {
4.21
4.22 /// \addtogroup graphs
4.23 /// @{
4.24
4.25 - class SymListGraph;
4.26 +// class SymListGraph;
4.27
4.28 ///A list graph class.
4.29
4.30 @@ -56,36 +64,13 @@
4.31 //The first free edge
4.32 int first_free_edge;
4.33
4.34 - protected:
4.35 + public:
4.36
4.37 - template <typename Key> class DynMapBase
4.38 - {
4.39 - protected:
4.40 - const ListGraph* G;
4.41 - public:
4.42 - virtual void add(const Key k) = 0;
4.43 - virtual void erase(const Key k) = 0;
4.44 - DynMapBase(const ListGraph &_G) : G(&_G) {}
4.45 - virtual ~DynMapBase() {}
4.46 - friend class ListGraph;
4.47 - };
4.48 -
4.49 - public:
4.50 - template <typename T> class EdgeMap;
4.51 - template <typename T> class NodeMap;
4.52 + typedef ListGraph Graph;
4.53
4.54 class Node;
4.55 class Edge;
4.56
4.57 - // protected:
4.58 - // HELPME:
4.59 - protected:
4.60 - ///\bug It must be public because of SymEdgeMap.
4.61 - ///
4.62 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.63 - ///\bug It must be public because of SymEdgeMap.
4.64 - ///
4.65 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.66
4.67 public:
4.68
4.69 @@ -93,24 +78,21 @@
4.70 class EdgeIt;
4.71 class OutEdgeIt;
4.72 class InEdgeIt;
4.73 -
4.74 +
4.75 + CREATE_MAP_REGISTRIES;
4.76 + CREATE_MAPS(ArrayMapFactory);
4.77 +
4.78 public:
4.79
4.80 - ListGraph() : nodes(), first_node(-1),
4.81 - first_free_node(-1), edges(), first_free_edge(-1) {}
4.82 - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
4.83 - first_free_node(_g.first_free_node),
4.84 - edges(_g.edges),
4.85 - first_free_edge(_g.first_free_edge) {}
4.86 + ListGraph()
4.87 + : nodes(), first_node(-1),
4.88 + first_free_node(-1), edges(), first_free_edge(-1) {}
4.89 +
4.90 + ListGraph(const ListGraph &_g)
4.91 + : nodes(_g.nodes), first_node(_g.first_node),
4.92 + first_free_node(_g.first_free_node), edges(_g.edges),
4.93 + first_free_edge(_g.first_free_edge) {}
4.94
4.95 - ~ListGraph()
4.96 - {
4.97 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.98 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.99 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.100 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.101 - }
4.102 -
4.103 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
4.104 int edgeNum() const { return edges.size(); } //FIXME: What is this?
4.105
4.106 @@ -170,8 +152,7 @@
4.107 Node nn; nn.n=n;
4.108
4.109 //Update dynamic maps
4.110 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.111 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
4.112 + node_maps.add(nn);
4.113
4.114 return nn;
4.115 }
4.116 @@ -202,8 +183,7 @@
4.117 Edge e; e.n=n;
4.118
4.119 //Update dynamic maps
4.120 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.121 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
4.122 + edge_maps.add(e);
4.123
4.124 return e;
4.125 }
4.126 @@ -244,8 +224,8 @@
4.127
4.128 //Update dynamic maps
4.129 Edge e; e.n=n;
4.130 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.131 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
4.132 + edge_maps.erase(e);
4.133 +
4.134 }
4.135
4.136 public:
4.137 @@ -265,16 +245,17 @@
4.138 first_free_node = n;
4.139
4.140 //Update dynamic maps
4.141 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.142 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
4.143 + node_maps.erase(nn);
4.144 +
4.145 }
4.146
4.147 void erase(Edge e) { eraseEdge(e.n); }
4.148
4.149 - ///\bug Dynamic maps must be updated!
4.150 - ///
4.151 void clear() {
4.152 - nodes.clear();edges.clear();
4.153 + edge_maps.clear();
4.154 + edges.clear();
4.155 + node_maps.clear();
4.156 + nodes.clear();
4.157 first_node=first_free_node=first_free_edge=-1;
4.158 }
4.159
4.160 @@ -410,188 +391,6 @@
4.161 // ///Validity check
4.162 // operator bool() { return Edge::operator bool(); }
4.163 };
4.164 -
4.165 - template <typename T> class NodeMap : public DynMapBase<Node>
4.166 - {
4.167 - std::vector<T> container;
4.168 -
4.169 - public:
4.170 - typedef T ValueType;
4.171 - typedef Node KeyType;
4.172 -
4.173 - NodeMap(const ListGraph &_G) :
4.174 - DynMapBase<Node>(_G), container(_G.maxNodeId())
4.175 - {
4.176 - G->dyn_node_maps.push_back(this);
4.177 - }
4.178 - NodeMap(const ListGraph &_G,const T &t) :
4.179 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
4.180 - {
4.181 - G->dyn_node_maps.push_back(this);
4.182 - }
4.183 -
4.184 - NodeMap(const NodeMap<T> &m) :
4.185 - DynMapBase<Node>(*m.G), container(m.container)
4.186 - {
4.187 - G->dyn_node_maps.push_back(this);
4.188 - }
4.189 -
4.190 - template<typename TT> friend class NodeMap;
4.191 -
4.192 - ///\todo It can copy between different types.
4.193 - ///
4.194 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
4.195 - DynMapBase<Node>(*m.G), container(m.container.size())
4.196 -
4.197 - {
4.198 - G->dyn_node_maps.push_back(this);
4.199 - typename std::vector<TT>::const_iterator i;
4.200 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.201 - i!=m.container.end();
4.202 - i++)
4.203 - container.push_back(*i);
4.204 - }
4.205 - ~NodeMap()
4.206 - {
4.207 - if(G) {
4.208 - std::vector<DynMapBase<Node>* >::iterator i;
4.209 - for(i=G->dyn_node_maps.begin();
4.210 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
4.211 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
4.212 - //A better way to do that: (Is this really important?)
4.213 - if(*i==this) {
4.214 - *i=G->dyn_node_maps.back();
4.215 - G->dyn_node_maps.pop_back();
4.216 - }
4.217 - }
4.218 - }
4.219 -
4.220 - void add(const Node k)
4.221 - {
4.222 - if(k.n>=int(container.size())) container.resize(k.n+1);
4.223 - }
4.224 -
4.225 - void erase(const Node) { }
4.226 -
4.227 - void set(Node n, T a) { container[n.n]=a; }
4.228 - //'T& operator[](Node n)' would be wrong here
4.229 - typename std::vector<T>::reference
4.230 - operator[](Node n) { return container[n.n]; }
4.231 - //'const T& operator[](Node n)' would be wrong here
4.232 - typename std::vector<T>::const_reference
4.233 - operator[](Node n) const { return container[n.n]; }
4.234 -
4.235 - ///\warning There is no safety check at all!
4.236 - ///Using operator = between maps attached to different graph may
4.237 - ///cause serious problem.
4.238 - ///\todo Is this really so?
4.239 - ///\todo It can copy between different types.
4.240 - const NodeMap<T>& operator=(const NodeMap<T> &m)
4.241 - {
4.242 - container = m.container;
4.243 - return *this;
4.244 - }
4.245 - template<typename TT>
4.246 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
4.247 - {
4.248 - std::copy(m.container.begin(), m.container.end(), container.begin());
4.249 - return *this;
4.250 - }
4.251 -
4.252 - void update() {} //Useless for Dynamic Maps
4.253 - void update(T a) {} //Useless for Dynamic Maps
4.254 - };
4.255 -
4.256 - template <typename T> class EdgeMap : public DynMapBase<Edge>
4.257 - {
4.258 - protected:
4.259 - std::vector<T> container;
4.260 -
4.261 - public:
4.262 - typedef T ValueType;
4.263 - typedef Edge KeyType;
4.264 -
4.265 - EdgeMap(const ListGraph &_G) :
4.266 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
4.267 - {
4.268 - //FIXME: What if there are empty Id's?
4.269 - //FIXME: Can I use 'this' in a constructor?
4.270 - G->dyn_edge_maps.push_back(this);
4.271 - }
4.272 - EdgeMap(const ListGraph &_G,const T &t) :
4.273 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
4.274 - {
4.275 - G->dyn_edge_maps.push_back(this);
4.276 - }
4.277 - EdgeMap(const EdgeMap<T> &m) :
4.278 - DynMapBase<Edge>(*m.G), container(m.container)
4.279 - {
4.280 - G->dyn_edge_maps.push_back(this);
4.281 - }
4.282 -
4.283 - template<typename TT> friend class EdgeMap;
4.284 -
4.285 - ///\todo It can copy between different types.
4.286 - ///
4.287 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
4.288 - DynMapBase<Edge>(*m.G), container(m.container.size())
4.289 - {
4.290 - G->dyn_edge_maps.push_back(this);
4.291 - typename std::vector<TT>::const_iterator i;
4.292 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.293 - i!=m.container.end();
4.294 - i++)
4.295 - container.push_back(*i);
4.296 - }
4.297 - ~EdgeMap()
4.298 - {
4.299 - if(G) {
4.300 - std::vector<DynMapBase<Edge>* >::iterator i;
4.301 - for(i=G->dyn_edge_maps.begin();
4.302 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
4.303 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.304 - //A better way to do that: (Is this really important?)
4.305 - if(*i==this) {
4.306 - *i=G->dyn_edge_maps.back();
4.307 - G->dyn_edge_maps.pop_back();
4.308 - }
4.309 - }
4.310 - }
4.311 -
4.312 - void add(const Edge k)
4.313 - {
4.314 - if(k.n>=int(container.size())) container.resize(k.n+1);
4.315 - }
4.316 - void erase(const Edge) { }
4.317 -
4.318 - void set(Edge n, T a) { container[n.n]=a; }
4.319 - //T get(Edge n) const { return container[n.n]; }
4.320 - typename std::vector<T>::reference
4.321 - operator[](Edge n) { return container[n.n]; }
4.322 - typename std::vector<T>::const_reference
4.323 - operator[](Edge n) const { return container[n.n]; }
4.324 -
4.325 - ///\warning There is no safety check at all!
4.326 - ///Using operator = between maps attached to different graph may
4.327 - ///cause serious problem.
4.328 - ///\todo Is this really so?
4.329 - ///\todo It can copy between different types.
4.330 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
4.331 - {
4.332 - container = m.container;
4.333 - return *this;
4.334 - }
4.335 - template<typename TT>
4.336 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
4.337 - {
4.338 - std::copy(m.container.begin(), m.container.end(), container.begin());
4.339 - return *this;
4.340 - }
4.341 -
4.342 - void update() {} //Useless for DynMaps
4.343 - void update(T a) {} //Useless for DynMaps
4.344 - };
4.345 -
4.346 };
4.347
4.348 ///Graph for bidirectional edges.
4.349 @@ -615,12 +414,19 @@
4.350 ///
4.351 ///\todo this date structure need some reconsiderations. Maybe it
4.352 ///should be implemented independently from ListGraph.
4.353 -
4.354 +
4.355 class SymListGraph : public ListGraph
4.356 {
4.357 public:
4.358 - template<typename T> class SymEdgeMap;
4.359 - template<typename T> friend class SymEdgeMap;
4.360 +
4.361 + typedef SymListGraph Graph;
4.362 +
4.363 + KEEP_NODE_MAP(ListGraph);
4.364 + KEEP_EDGE_MAP(ListGraph);
4.365 +
4.366 + CREATE_SYM_EDGE_MAP_REGISTRY;
4.367 + CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
4.368 + IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
4.369
4.370 SymListGraph() : ListGraph() { }
4.371 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
4.372 @@ -628,11 +434,14 @@
4.373 Edge addEdge(Node u, Node v)
4.374 {
4.375 Edge e = ListGraph::addEdge(u,v);
4.376 - ListGraph::addEdge(v,u);
4.377 + Edge f = ListGraph::addEdge(v,u);
4.378 + sym_edge_maps.add(e);
4.379 + sym_edge_maps.add(f);
4.380 +
4.381 return e;
4.382 }
4.383
4.384 - void erase(Node n) { ListGraph::erase(n); }
4.385 + void erase(Node n) { ListGraph::erase(n);}
4.386 ///The oppositely directed edge.
4.387
4.388 ///Returns the oppositely directed
4.389 @@ -646,109 +455,14 @@
4.390
4.391 ///Removes a pair of oppositely directed edges to the graph.
4.392 void erase(Edge e) {
4.393 - ListGraph::erase(opposite(e));
4.394 + Edge f = opposite(e);
4.395 + sym_edge_maps.erase(e);
4.396 + sym_edge_maps.erase(f);
4.397 + ListGraph::erase(f);
4.398 ListGraph::erase(e);
4.399 - }
4.400 -
4.401 - ///Common data storage for the edge pairs.
4.402 + }
4.403 + };
4.404
4.405 - ///This map makes it possible to store data shared by the oppositely
4.406 - ///directed pairs of edges.
4.407 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
4.408 - {
4.409 - std::vector<T> container;
4.410 -
4.411 - public:
4.412 - typedef T ValueType;
4.413 - typedef Edge KeyType;
4.414 -
4.415 - SymEdgeMap(const SymListGraph &_G) :
4.416 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
4.417 - {
4.418 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
4.419 - }
4.420 - SymEdgeMap(const SymListGraph &_G,const T &t) :
4.421 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
4.422 - {
4.423 - G->dyn_edge_maps.push_back(this);
4.424 - }
4.425 -
4.426 - SymEdgeMap(const SymEdgeMap<T> &m) :
4.427 - DynMapBase<SymEdge>(*m.G), container(m.container)
4.428 - {
4.429 - G->dyn_node_maps.push_back(this);
4.430 - }
4.431 -
4.432 - // template<typename TT> friend class SymEdgeMap;
4.433 -
4.434 - ///\todo It can copy between different types.
4.435 - ///
4.436 -
4.437 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
4.438 - DynMapBase<SymEdge>(*m.G), container(m.container.size())
4.439 - {
4.440 - G->dyn_node_maps.push_back(this);
4.441 - typename std::vector<TT>::const_iterator i;
4.442 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.443 - i!=m.container.end();
4.444 - i++)
4.445 - container.push_back(*i);
4.446 - }
4.447 -
4.448 - ~SymEdgeMap()
4.449 - {
4.450 - if(G) {
4.451 - std::vector<DynMapBase<Edge>* >::iterator i;
4.452 - for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
4.453 - i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
4.454 - && *i!=this; ++i) ;
4.455 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.456 - //A better way to do that: (Is this really important?)
4.457 - if(*i==this) {
4.458 - *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
4.459 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
4.460 - }
4.461 - }
4.462 - }
4.463 -
4.464 - void add(const Edge k)
4.465 - {
4.466 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
4.467 - container.resize(k.idref()/2+1);
4.468 - }
4.469 - void erase(const Edge k) { }
4.470 -
4.471 - void set(Edge n, T a) { container[n.idref()/2]=a; }
4.472 - //T get(Edge n) const { return container[n.idref()/2]; }
4.473 - typename std::vector<T>::reference
4.474 - operator[](Edge n) { return container[n.idref()/2]; }
4.475 - typename std::vector<T>::const_reference
4.476 - operator[](Edge n) const { return container[n.idref()/2]; }
4.477 -
4.478 - ///\warning There is no safety check at all!
4.479 - ///Using operator = between maps attached to different graph may
4.480 - ///cause serious problem.
4.481 - ///\todo Is this really so?
4.482 - ///\todo It can copy between different types.
4.483 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
4.484 - {
4.485 - container = m.container;
4.486 - return *this;
4.487 - }
4.488 - template<typename TT>
4.489 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
4.490 - {
4.491 - std::copy(m.container.begin(), m.container.end(), container.begin());
4.492 - return *this;
4.493 - }
4.494 -
4.495 - void update() {} //Useless for DynMaps
4.496 - void update(T a) {} //Useless for DynMaps
4.497 -
4.498 - };
4.499 -
4.500 - };
4.501 -
4.502
4.503 ///A graph class containing only nodes.
4.504
4.505 @@ -779,35 +493,13 @@
4.506 //The first free node
4.507 int first_free_node;
4.508
4.509 - protected:
4.510 -
4.511 - template <typename Key> class DynMapBase
4.512 - {
4.513 - protected:
4.514 - const NodeSet* G;
4.515 - public:
4.516 - virtual void add(const Key k) = 0;
4.517 - virtual void erase(const Key k) = 0;
4.518 - DynMapBase(const NodeSet &_G) : G(&_G) {}
4.519 - virtual ~DynMapBase() {}
4.520 - friend class NodeSet;
4.521 - };
4.522 -
4.523 public:
4.524 - template <typename T> class EdgeMap;
4.525 - template <typename T> class NodeMap;
4.526 +
4.527 + typedef NodeSet Graph;
4.528
4.529 class Node;
4.530 class Edge;
4.531
4.532 - // protected:
4.533 - // HELPME:
4.534 - protected:
4.535 - ///\bug It must be public because of SymEdgeMap.
4.536 - ///
4.537 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.538 - //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.539 -
4.540 public:
4.541
4.542 class NodeIt;
4.543 @@ -815,26 +507,19 @@
4.544 class OutEdgeIt;
4.545 class InEdgeIt;
4.546
4.547 - template <typename T> class NodeMap;
4.548 - template <typename T> class EdgeMap;
4.549 + CREATE_MAP_REGISTRIES;
4.550 + CREATE_MAPS(ArrayMapFactory);
4.551
4.552 public:
4.553
4.554 ///Default constructor
4.555 - NodeSet() : nodes(), first_node(-1),
4.556 - first_free_node(-1) {}
4.557 + NodeSet()
4.558 + : nodes(), first_node(-1), first_free_node(-1) {}
4.559 ///Copy constructor
4.560 - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
4.561 - first_free_node(_g.first_free_node) {}
4.562 + NodeSet(const NodeSet &_g)
4.563 + : nodes(_g.nodes), first_node(_g.first_node),
4.564 + first_free_node(_g.first_free_node) {}
4.565
4.566 - ~NodeSet()
4.567 - {
4.568 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.569 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.570 - //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.571 - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.572 - }
4.573 -
4.574 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
4.575 int edgeNum() const { return 0; } //FIXME: What is this?
4.576
4.577 @@ -887,8 +572,7 @@
4.578 Node nn; nn.n=n;
4.579
4.580 //Update dynamic maps
4.581 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.582 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
4.583 + node_maps.add(nn);
4.584
4.585 return nn;
4.586 }
4.587 @@ -904,8 +588,7 @@
4.588 first_free_node = n;
4.589
4.590 //Update dynamic maps
4.591 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.592 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
4.593 + node_maps.erase(nn);
4.594 }
4.595
4.596
4.597 @@ -914,9 +597,8 @@
4.598 return INVALID;
4.599 }
4.600
4.601 - ///\bug Dynamic maps must be updated!
4.602 - ///
4.603 void clear() {
4.604 + node_maps.clear();
4.605 nodes.clear();
4.606 first_node = first_free_node = -1;
4.607 }
4.608 @@ -1012,128 +694,6 @@
4.609 InEdgeIt operator++() { return INVALID; }
4.610 };
4.611
4.612 - template <typename T> class NodeMap : public DynMapBase<Node>
4.613 - {
4.614 - std::vector<T> container;
4.615 -
4.616 - public:
4.617 - typedef T ValueType;
4.618 - typedef Node KeyType;
4.619 -
4.620 - NodeMap(const NodeSet &_G) :
4.621 - DynMapBase<Node>(_G), container(_G.maxNodeId())
4.622 - {
4.623 - G->dyn_node_maps.push_back(this);
4.624 - }
4.625 - NodeMap(const NodeSet &_G,const T &t) :
4.626 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
4.627 - {
4.628 - G->dyn_node_maps.push_back(this);
4.629 - }
4.630 -
4.631 - NodeMap(const NodeMap<T> &m) :
4.632 - DynMapBase<Node>(*m.G), container(m.container)
4.633 - {
4.634 - G->dyn_node_maps.push_back(this);
4.635 - }
4.636 -
4.637 - template<typename TT> friend class NodeMap;
4.638 -
4.639 - ///\todo It can copy between different types.
4.640 - ///
4.641 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
4.642 - DynMapBase<Node>(*m.G), container(m.container.size())
4.643 - {
4.644 - G->dyn_node_maps.push_back(this);
4.645 - typename std::vector<TT>::const_iterator i;
4.646 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.647 - i!=m.container.end();
4.648 - i++)
4.649 - container.push_back(*i);
4.650 - }
4.651 - ~NodeMap()
4.652 - {
4.653 - if(G) {
4.654 - std::vector<DynMapBase<Node>* >::iterator i;
4.655 - for(i=G->dyn_node_maps.begin();
4.656 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
4.657 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
4.658 - //A better way to do that: (Is this really important?)
4.659 - if(*i==this) {
4.660 - *i=G->dyn_node_maps.back();
4.661 - G->dyn_node_maps.pop_back();
4.662 - }
4.663 - }
4.664 - }
4.665 -
4.666 - void add(const Node k)
4.667 - {
4.668 - if(k.n>=int(container.size())) container.resize(k.n+1);
4.669 - }
4.670 -
4.671 - void erase(const Node) { }
4.672 -
4.673 - void set(Node n, T a) { container[n.n]=a; }
4.674 - //'T& operator[](Node n)' would be wrong here
4.675 - typename std::vector<T>::reference
4.676 - operator[](Node n) { return container[n.n]; }
4.677 - //'const T& operator[](Node n)' would be wrong here
4.678 - typename std::vector<T>::const_reference
4.679 - operator[](Node n) const { return container[n.n]; }
4.680 -
4.681 - ///\warning There is no safety check at all!
4.682 - ///Using operator = between maps attached to different graph may
4.683 - ///cause serious problem.
4.684 - ///\todo Is this really so?
4.685 - ///\todo It can copy between different types.
4.686 - const NodeMap<T>& operator=(const NodeMap<T> &m)
4.687 - {
4.688 - container = m.container;
4.689 - return *this;
4.690 - }
4.691 - template<typename TT>
4.692 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
4.693 - {
4.694 - std::copy(m.container.begin(), m.container.end(), container.begin());
4.695 - return *this;
4.696 - }
4.697 -
4.698 - void update() {} //Useless for Dynamic Maps
4.699 - void update(T a) {} //Useless for Dynamic Maps
4.700 - };
4.701 -
4.702 - template <typename T> class EdgeMap
4.703 - {
4.704 - public:
4.705 - typedef T ValueType;
4.706 - typedef Edge KeyType;
4.707 -
4.708 - EdgeMap(const NodeSet &) { }
4.709 - EdgeMap(const NodeSet &,const T &) { }
4.710 - EdgeMap(const EdgeMap<T> &) { }
4.711 - // template<typename TT> friend class EdgeMap;
4.712 -
4.713 - ///\todo It can copy between different types.
4.714 - ///
4.715 - template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
4.716 - ~EdgeMap() { }
4.717 -
4.718 - void add(const Edge ) { }
4.719 - void erase(const Edge) { }
4.720 -
4.721 - void set(Edge, T) { }
4.722 - //T get(Edge n) const { return container[n.n]; }
4.723 - ValueType &operator[](Edge) { return *((T*)(NULL)); }
4.724 - const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
4.725 -
4.726 - const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
4.727 -
4.728 - template<typename TT>
4.729 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
4.730 -
4.731 - void update() {}
4.732 - void update(T a) {}
4.733 - };
4.734 };
4.735
4.736
4.737 @@ -1166,11 +726,15 @@
4.738 NodeGraphType &G;
4.739
4.740 public:
4.741 +
4.742 class Node;
4.743 class Edge;
4.744 class OutEdgeIt;
4.745 class InEdgeIt;
4.746 class SymEdge;
4.747 +
4.748 + typedef EdgeSet Graph;
4.749 +
4.750 int id(Node v) const;
4.751
4.752 class Node : public NodeGraphType::Node {
4.753 @@ -1229,44 +793,21 @@
4.754 //The first free edge
4.755 int first_free_edge;
4.756
4.757 - protected:
4.758 -
4.759 - template <typename Key> class DynMapBase
4.760 - {
4.761 - protected:
4.762 - const EdgeSet* G;
4.763 - public:
4.764 - virtual void add(const Key k) = 0;
4.765 - virtual void erase(const Key k) = 0;
4.766 - DynMapBase(const EdgeSet &_G) : G(&_G) {}
4.767 - virtual ~DynMapBase() {}
4.768 - friend class EdgeSet;
4.769 - };
4.770 -
4.771 public:
4.772 - //template <typename T> class NodeMap;
4.773 - template <typename T> class EdgeMap;
4.774
4.775 class Node;
4.776 class Edge;
4.777
4.778 - // protected:
4.779 - // HELPME:
4.780 - protected:
4.781 - // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.782 - ///\bug It must be public because of SymEdgeMap.
4.783 - ///
4.784 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.785 -
4.786 - public:
4.787 -
4.788 class NodeIt;
4.789 class EdgeIt;
4.790 class OutEdgeIt;
4.791 class InEdgeIt;
4.792 +
4.793 +
4.794 + CREATE_EDGE_MAP_REGISTRY;
4.795 + CREATE_EDGE_MAP_FACTORY(ArrayMapFactory);
4.796 + IMPORT_EDGE_MAP(EdgeMapFactory);
4.797
4.798 - template <typename T> class NodeMap;
4.799 - template <typename T> class EdgeMap;
4.800
4.801 public:
4.802
4.803 @@ -1275,25 +816,17 @@
4.804 ///Construates a new graph based on the nodeset of an existing one.
4.805 ///\param _G the base graph.
4.806 ///\todo It looks like a copy constructor, but it isn't.
4.807 - EdgeSet(NodeGraphType &_G) : G(_G),
4.808 - nodes(_G), edges(),
4.809 - first_free_edge(-1) { }
4.810 + EdgeSet(NodeGraphType &_G)
4.811 + : G(_G), nodes(_G), edges(),
4.812 + first_free_edge(-1) {}
4.813 ///Copy constructor
4.814
4.815 ///Makes a copy of an EdgeSet.
4.816 ///It will be based on the same graph.
4.817 - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
4.818 - first_free_edge(_g.first_free_edge) { }
4.819 + EdgeSet(const EdgeSet &_g)
4.820 + : G(_g.G), nodes(_g.G), edges(_g.edges),
4.821 + first_free_edge(_g.first_free_edge) {}
4.822
4.823 - ~EdgeSet()
4.824 - {
4.825 - // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.826 - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.827 - for(typename std::vector<DynMapBase<Edge> * >::iterator
4.828 - i=dyn_edge_maps.begin();
4.829 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.830 - }
4.831 -
4.832 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
4.833 int edgeNum() const { return edges.size(); } //FIXME: What is this?
4.834
4.835 @@ -1347,9 +880,7 @@
4.836 Edge e; e.n=n;
4.837
4.838 //Update dynamic maps
4.839 - for(typename std::vector<DynMapBase<Edge> * >::iterator
4.840 - i=dyn_edge_maps.begin();
4.841 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
4.842 + edge_maps.add(e);
4.843
4.844 return e;
4.845 }
4.846 @@ -1389,10 +920,8 @@
4.847 first_free_edge = -1;
4.848
4.849 //Update dynamic maps
4.850 - Edge e; e.n=n;
4.851 - for(typename std::vector<DynMapBase<Edge> * >::iterator
4.852 - i=dyn_edge_maps.begin();
4.853 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
4.854 + Edge e; e.n = n;
4.855 + edge_maps.erase(e);
4.856 }
4.857
4.858 public:
4.859 @@ -1408,22 +937,12 @@
4.860
4.861 ///Clear all edges. (Doesn't clear the nodes!)
4.862 void clear() {
4.863 + edge_maps.clear();
4.864 edges.clear();
4.865 first_free_edge=-1;
4.866 }
4.867
4.868
4.869 -// //\bug Dynamic maps must be updated!
4.870 -// //
4.871 -// void clear() {
4.872 -// nodes.clear();edges.clear();
4.873 -// first_node=first_free_node=first_free_edge=-1;
4.874 -// }
4.875 -
4.876 - public:
4.877 - template <typename T> class EdgeMap;
4.878 -
4.879 - ///
4.880 class Edge {
4.881 public:
4.882 friend class EdgeSet;
4.883 @@ -1490,7 +1009,7 @@
4.884
4.885 OutEdgeIt(const EdgeSet& _G,const Node v) :
4.886 Edge(_G.nodes[v].first_out), G(&_G) { }
4.887 - OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
4.888 + OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
4.889 };
4.890
4.891 class InEdgeIt : public Edge {
4.892 @@ -1505,126 +1024,41 @@
4.893 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
4.894 };
4.895
4.896 - template <typename T> class NodeMap :
4.897 - public NodeGraphType::template NodeMap<T>
4.898 +
4.899 + template <typename V> class NodeMap
4.900 + : public NodeGraphType::template NodeMap<V>
4.901 {
4.902 //This is a must, the constructors need it.
4.903 - typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
4.904 + typedef typename NodeGraphType::template NodeMap<V> MapImpl;
4.905 + typedef V Value;
4.906 public:
4.907 - NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
4.908 - NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
4.909 - //It is unnecessary
4.910 - NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
4.911 - ParentNodeMap(m) { }
4.912 + NodeMap() : MapImpl() {}
4.913 +
4.914 + NodeMap(const EdgeSet& graph)
4.915 + : MapImpl(graph.G) { }
4.916
4.917 - ///\todo It can copy between different types.
4.918 - ///
4.919 - template<typename TT>
4.920 - NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
4.921 - : ParentNodeMap(m) { }
4.922 - };
4.923 -
4.924 - ///
4.925 - template <typename T> class EdgeMap : public DynMapBase<Edge>
4.926 - {
4.927 - protected:
4.928 - public:
4.929 - ///\bug It should be at least protected
4.930 - ///
4.931 - std::vector<T> container;
4.932 + NodeMap(const EdgeSet& graph, const Value& value)
4.933 + : MapImpl(graph.G, value) { }
4.934
4.935 - public:
4.936 - typedef T ValueType;
4.937 - typedef Edge KeyType;
4.938 + NodeMap(const NodeMap& copy)
4.939 + : MapImpl(static_cast<const MapImpl&>(copy)) {}
4.940
4.941 - EdgeMap(const EdgeSet &_G) :
4.942 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
4.943 - {
4.944 - //FIXME: What if there are empty Id's?
4.945 - //FIXME: Can I use 'this' in a constructor?
4.946 - this->G->dyn_edge_maps.push_back(this);
4.947 - }
4.948 - EdgeMap(const EdgeSet &_G,const T &t) :
4.949 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
4.950 - {
4.951 - this->G->dyn_edge_maps.push_back(this);
4.952 - }
4.953 - EdgeMap(const EdgeMap<T> &m) :
4.954 - DynMapBase<Edge>(*m.G), container(m.container)
4.955 - {
4.956 - this->G->dyn_edge_maps.push_back(this);
4.957 + template<typename CMap>
4.958 + NodeMap(const CMap& copy)
4.959 + : MapImpl(copy) { }
4.960 +
4.961 + NodeMap& operator=(const NodeMap& copy) {
4.962 + MapImpl::operator=(static_cast<const MapImpl&>(copy));
4.963 + return *this;
4.964 }
4.965
4.966 - ///\todo It can copy between different types.
4.967 - ///
4.968 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
4.969 - DynMapBase<Edge>(*m.G), container(m.container.size())
4.970 - {
4.971 - this->G->dyn_edge_maps.push_back(this);
4.972 - typename std::vector<TT>::const_iterator i;
4.973 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.974 - i!=m.container.end();
4.975 - i++)
4.976 - container.push_back(*i);
4.977 - }
4.978 - ~EdgeMap()
4.979 - {
4.980 - if(this->G) {
4.981 - typename std::vector<DynMapBase<Edge>* >::iterator i;
4.982 - for(i=this->G->dyn_edge_maps.begin();
4.983 - i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
4.984 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.985 - //A better way to do that: (Is this really important?)
4.986 - if(*i==this) {
4.987 - *i=this->G->dyn_edge_maps.back();
4.988 - this->G->dyn_edge_maps.pop_back();
4.989 - }
4.990 - }
4.991 - }
4.992 -
4.993 - void add(const Edge k)
4.994 - {
4.995 - if(k.n>=int(container.size())) container.resize(k.n+1);
4.996 - }
4.997 - void erase(const Edge) { }
4.998 -
4.999 - ///\bug This doesn't work. Why?
4.1000 - /// void set(Edge n, T a) { container[n.n]=a; }
4.1001 - void set(Edge n, T a) { container[this->G->id(n)]=a; }
4.1002 - //T get(Edge n) const { return container[n.n]; }
4.1003 - typename std::vector<T>::reference
4.1004 - ///\bug This doesn't work. Why?
4.1005 - /// operator[](Edge n) { return container[n.n]; }
4.1006 - operator[](Edge n) { return container[this->G->id(n)]; }
4.1007 - typename std::vector<T>::const_reference
4.1008 - ///\bug This doesn't work. Why?
4.1009 - /// operator[](Edge n) const { return container[n.n]; }
4.1010 - operator[](Edge n) const { return container[this->G->id(n)]; }
4.1011 -
4.1012 - ///\warning There is no safety check at all!
4.1013 - ///Using operator = between maps attached to different graph may
4.1014 - ///cause serious problem.
4.1015 - ///\todo Is this really so?
4.1016 - ///\todo It can copy between different types.
4.1017 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
4.1018 - {
4.1019 - container = m.container;
4.1020 + template <typename CMap>
4.1021 + NodeMap& operator=(const CMap& copy) {
4.1022 + MapImpl::operator=(copy);
4.1023 return *this;
4.1024 }
4.1025 -
4.1026 - template<typename TT> friend class EdgeMap;
4.1027
4.1028 - template<typename TT>
4.1029 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
4.1030 - {
4.1031 - std::copy(m.container.begin(), m.container.end(), container.begin());
4.1032 - return *this;
4.1033 - }
4.1034 -
4.1035 - void update() {} //Useless for DynMaps
4.1036 - void update(T a) {} //Useless for DynMaps
4.1037 };
4.1038 -
4.1039 };
4.1040
4.1041 template<typename GG>
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/hugo/map_defines.h Thu Sep 02 10:07:30 2004 +0000
5.3 @@ -0,0 +1,212 @@
5.4 +// -*- c++ -*-
5.5 +#ifndef MAP_DEFINES_H
5.6 +#define MAP_DEFINES_H
5.7 +
5.8 +/** Creates the EdgeMapRegistry type an declare a mutable instance
5.9 + * named edge_maps.
5.10 + */
5.11 +#define CREATE_EDGE_MAP_REGISTRY \
5.12 +typedef MapRegistry<Graph, Edge, EdgeIt> EdgeMapRegistry; \
5.13 +mutable EdgeMapRegistry edge_maps;
5.14 +
5.15 +/** Creates the NodeMapRegistry type an declare a mutable instance
5.16 + * named node_maps.
5.17 + */
5.18 +#define CREATE_NODE_MAP_REGISTRY \
5.19 +typedef MapRegistry<Graph, Node, NodeIt> NodeMapRegistry; \
5.20 +mutable NodeMapRegistry node_maps;
5.21 +
5.22 +/** Creates both map registries.
5.23 + */
5.24 +#define CREATE_MAP_REGISTRIES \
5.25 +CREATE_NODE_MAP_REGISTRY \
5.26 +CREATE_EDGE_MAP_REGISTRY
5.27 +
5.28 +/** Creates a concrete factory type from a template map
5.29 + * factory to use as node map factory.
5.30 + */
5.31 +#define CREATE_NODE_MAP_FACTORY(TemplateFactory) \
5.32 +typedef TemplateFactory<NodeMapRegistry> NodeMapFactory;
5.33 +
5.34 +/** Creates a concrete factory type from a template map
5.35 + * factory to use as edge map factory.
5.36 + */
5.37 +#define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \
5.38 +typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory;
5.39 +
5.40 +/** Creates both map factories.
5.41 + */
5.42 +#define CREATE_MAP_FACTORIES(TemplateFactory) \
5.43 +CREATE_NODE_MAP_FACTORY(TemplateFactory) \
5.44 +CREATE_EDGE_MAP_FACTORY(TemplateFactory)
5.45 +
5.46 +/** Import a map from a concrete map factory. The import method is
5.47 + * an overloading of the map type.
5.48 + * The reason to use these macro is that the c++ does not support
5.49 + * the template typedefs. If a future release of the c++
5.50 + * supports this feature it should be fixed.
5.51 + */
5.52 +#define IMPORT_NODE_MAP(Factory) \
5.53 +template <typename V> \
5.54 +class NodeMap : public Factory::template Map<V> { \
5.55 +typedef typename Factory::template Map<V> MapImpl; \
5.56 +public: \
5.57 +NodeMap() {} \
5.58 +NodeMap(const Graph& g) : MapImpl(g, g.node_maps) {} \
5.59 +NodeMap(const Graph& g, const V& v) : MapImpl(g, g.node_maps, v) {} \
5.60 +NodeMap(const NodeMap& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {} \
5.61 +template <typename CMap> NodeMap(const CMap& copy) : MapImpl(copy) {} \
5.62 +NodeMap& operator=(const NodeMap& copy) { \
5.63 + MapImpl::operator=(static_cast<const MapImpl&>(copy));\
5.64 + return *this; \
5.65 +} \
5.66 +template <typename CMap> NodeMap& operator=(const CMap& copy) { \
5.67 + MapImpl::operator=(copy);\
5.68 + return *this; \
5.69 +} \
5.70 +};
5.71 +
5.72 +/** Import a map from a concrete map factory. The import method is
5.73 + * an overloading of the map type.
5.74 + * The reason to use these macro is that the c++ does not support
5.75 + * the template typedefs. If a future release of the c++
5.76 + * supports this feature it should be fixed.
5.77 + */
5.78 +#define IMPORT_EDGE_MAP(Factory) \
5.79 +template <typename V> \
5.80 +class EdgeMap : public Factory::template Map<V> { \
5.81 +typedef typename Factory::template Map<V> MapImpl; \
5.82 +public: \
5.83 +EdgeMap() {} \
5.84 +EdgeMap(const Graph& g) : MapImpl(g, g.edge_maps) {} \
5.85 +EdgeMap(const Graph& g, const V& v) : MapImpl(g, g.edge_maps, v) {} \
5.86 +EdgeMap(const EdgeMap& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {} \
5.87 +template <typename CMap> EdgeMap(const CMap& copy) : MapImpl(copy) {} \
5.88 +EdgeMap& operator=(const EdgeMap& copy) { \
5.89 + MapImpl::operator=(static_cast<const MapImpl&>(copy));\
5.90 + return *this; \
5.91 +} \
5.92 +template <typename CMap> EdgeMap& operator=(const CMap& copy) { \
5.93 + MapImpl::operator=(copy);\
5.94 + return *this; \
5.95 +} \
5.96 +};
5.97 +
5.98 +/** This macro creates both map factories and imports both maps.
5.99 + */
5.100 +#define CREATE_MAPS(TemplateFactory) \
5.101 +CREATE_MAP_FACTORIES(TemplateFactory) \
5.102 +IMPORT_NODE_MAP(NodeMapFactory) \
5.103 +IMPORT_EDGE_MAP(EdgeMapFactory)
5.104 +
5.105 +/** This macro creates MapRegistry for Symmetric Edge Maps.
5.106 + */
5.107 +#define CREATE_SYM_EDGE_MAP_REGISTRY \
5.108 +typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
5.109 +typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
5.110 +mutable EdgeMapRegistry sym_edge_maps;
5.111 +
5.112 +/** Creates a concrete factory type from a template map
5.113 + * factory to use as edge map factory.
5.114 + */
5.115 +#define CREATE_SYM_EDGE_MAP_FACTORY(TemplateFactory) \
5.116 +typedef SymMapFactory<SymEdgeMapRegistry, TemplateFactory > \
5.117 +SymEdgeMapFactory;
5.118 +
5.119 +/** Import a map from a concrete map factory. The import method is
5.120 + * an overloading of the map type.
5.121 + * The reason to use these macro is that the c++ does not support
5.122 + * the template typedefs. If a future release of the c++
5.123 + * supports this feature it should be fixed.
5.124 + */
5.125 +#define IMPORT_SYM_EDGE_MAP(Factory) \
5.126 +template <typename V> \
5.127 +class SymEdgeMap : public Factory::template Map<V> { \
5.128 +typedef typename Factory::template Map<V> MapImpl; \
5.129 +public: \
5.130 +SymEdgeMap() {} \
5.131 +SymEdgeMap(const Graph& g) : MapImpl(g, g.sym_edge_maps) {} \
5.132 +SymEdgeMap(const Graph& g, const V& v) : MapImpl(g, g.sym_edge_maps, v) {} \
5.133 +SymEdgeMap(const SymEdgeMap& copy) \
5.134 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
5.135 +template <typename CMap> SymEdgeMap(const CMap& copy) : MapImpl(copy) {} \
5.136 +SymEdgeMap& operator=(const SymEdgeMap& copy) { \
5.137 + MapImpl::operator=(static_cast<const MapImpl&>(copy));\
5.138 + return *this; \
5.139 +} \
5.140 +template <typename CMap> SymEdgeMap& operator=(const CMap& copy) { \
5.141 + MapImpl::operator=(copy);\
5.142 + return *this; \
5.143 +} \
5.144 +};
5.145 +
5.146 +
5.147 +#define KEEP_NODE_MAP(GraphBase) \
5.148 + template <typename V> class NodeMap \
5.149 + : public GraphBase::template NodeMap<V> \
5.150 + { \
5.151 + typedef typename GraphBase::template NodeMap<V> MapImpl; \
5.152 + typedef V Value; \
5.153 + public: \
5.154 + NodeMap() : MapImpl() {} \
5.155 +\
5.156 + NodeMap(const Graph& graph) \
5.157 + : MapImpl(static_cast<const GraphBase&>(graph)) { } \
5.158 +\
5.159 + NodeMap(const Graph& graph, const Value& value) \
5.160 + : MapImpl(static_cast<const GraphBase&>(graph), value) { } \
5.161 +\
5.162 + NodeMap(const NodeMap& copy) \
5.163 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
5.164 +\
5.165 + template<typename CMap> \
5.166 + NodeMap(const CMap& copy) \
5.167 + : MapImpl(copy) {} \
5.168 +\
5.169 + NodeMap& operator=(const NodeMap& copy) { \
5.170 + MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
5.171 + return *this; \
5.172 + } \
5.173 +\
5.174 + template <typename CMap> \
5.175 + NodeMap& operator=(const CMap& copy) { \
5.176 + MapImpl::operator=(copy); \
5.177 + return *this; \
5.178 + } \
5.179 + };
5.180 +
5.181 +#define KEEP_EDGE_MAP(GraphBase) \
5.182 + template <typename V> class EdgeMap \
5.183 + : public GraphBase::template EdgeMap<V> \
5.184 + { \
5.185 + typedef typename GraphBase::template EdgeMap<V> MapImpl; \
5.186 + typedef V Value; \
5.187 + public: \
5.188 + EdgeMap() : MapImpl() {} \
5.189 +\
5.190 + EdgeMap(const Graph& graph) \
5.191 + : MapImpl(static_cast<const GraphBase&>(graph)) { } \
5.192 +\
5.193 + EdgeMap(const Graph& graph, const Value& value) \
5.194 + : MapImpl(static_cast<const GraphBase&>(graph), value) { } \
5.195 +\
5.196 + EdgeMap(const EdgeMap& copy) \
5.197 + : MapImpl(static_cast<const MapImpl&>(copy)) {} \
5.198 +\
5.199 + template<typename CMap> \
5.200 + EdgeMap(const CMap& copy) \
5.201 + : MapImpl(copy) {} \
5.202 +\
5.203 + EdgeMap& operator=(const EdgeMap& copy) { \
5.204 + MapImpl::operator=(static_cast<const MapImpl&>(copy)); \
5.205 + return *this; \
5.206 + } \
5.207 +\
5.208 + template <typename CMap> \
5.209 + EdgeMap& operator=(const CMap& copy) { \
5.210 + MapImpl::operator=(copy); \
5.211 + return *this; \
5.212 + } \
5.213 + };
5.214 +
5.215 +#endif
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/hugo/map_registry.h Thu Sep 02 10:07:30 2004 +0000
6.3 @@ -0,0 +1,265 @@
6.4 +// -*- c++ -*-
6.5 +#ifndef MAP_REGISTRY_H
6.6 +#define MAP_REGISTRY_H
6.7 +
6.8 +#include <vector>
6.9 +
6.10 +using namespace std;
6.11 +
6.12 +namespace hugo {
6.13 +
6.14 +/**
6.15 + * Registry class to register edge or node maps into the graph. The
6.16 + * registry helps you to implement an observer pattern. If you add
6.17 + * or erase an edge or node you must notify all the maps about the
6.18 + * event.
6.19 +*/
6.20 + template <typename G, typename K, typename KIt>
6.21 + class MapRegistry {
6.22 + public:
6.23 + typedef G Graph;
6.24 + typedef K Key;
6.25 + typedef KIt KeyIt;
6.26 +
6.27 +
6.28 +
6.29 + /**
6.30 + * MapBase is the base class of the registered maps.
6.31 + * It defines the core modification operations on the maps and
6.32 + * implements some helper functions.
6.33 + */
6.34 + class MapBase {
6.35 + public:
6.36 + typedef G Graph;
6.37 + typedef K Key;
6.38 + typedef KIt KeyIt;
6.39 +
6.40 + typedef MapRegistry<G, K, KIt> Registry;
6.41 +
6.42 + friend class MapRegistry<G, K, KIt>;
6.43 +
6.44 + /**
6.45 + * Default constructor for MapBase.
6.46 + */
6.47 +
6.48 + MapBase() : graph(0), registry(0) {}
6.49 +
6.50 + /**
6.51 + * Simple constructor to register into a graph registry.
6.52 + */
6.53 +
6.54 + MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
6.55 + r.attach(*this);
6.56 + }
6.57 +
6.58 + /**
6.59 + * Copy constructor to register into the registry.
6.60 + */
6.61 +
6.62 + MapBase(const MapBase& copy) : registry(0), graph(copy.graph) {
6.63 + if (copy.registry) {
6.64 + copy.registry->attach(*this);
6.65 + }
6.66 + }
6.67 +
6.68 + /**
6.69 + * Assign operator.
6.70 + */
6.71 +
6.72 + const MapBase& operator=(const MapBase& copy) {
6.73 + if (registry) {
6.74 + registry->detach(*this);
6.75 + }
6.76 + graph = copy.graph;
6.77 + if (copy.registry) {
6.78 + copy.registry->attach(*this);
6.79 + }
6.80 + }
6.81 +
6.82 +
6.83 + /**
6.84 + * Destructor.
6.85 + */
6.86 +
6.87 + virtual ~MapBase() {
6.88 + if (registry) {
6.89 + registry->detach(*this);
6.90 + }
6.91 + }
6.92 +
6.93 + /*
6.94 + * Returns the graph that the map belongs to.
6.95 + */
6.96 +
6.97 + const Graph* getGraph() const { return graph; }
6.98 +
6.99 + protected:
6.100 +
6.101 + const Graph* graph;
6.102 + Registry* registry;
6.103 +
6.104 + int registry_index;
6.105 +
6.106 + protected:
6.107 +
6.108 + /**
6.109 + Helper function to implement constructors in the subclasses.
6.110 + */
6.111 +
6.112 + virtual void init() {
6.113 + for (KeyIt it(*graph); it != INVALID; ++it) {
6.114 + add(it);
6.115 + }
6.116 + }
6.117 +
6.118 + /**
6.119 + Helper function to implement the destructor in the subclasses.
6.120 + */
6.121 +
6.122 + virtual void destroy() {
6.123 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
6.124 + erase(it);
6.125 + }
6.126 + }
6.127 +
6.128 + /**
6.129 + The add member function should be overloaded in the subclasses.
6.130 + \e Add extends the map with the new node.
6.131 + */
6.132 +
6.133 + virtual void add(const Key&) = 0;
6.134 + /**
6.135 + The erase member function should be overloaded in the subclasses.
6.136 + \e Erase removes the node from the map.
6.137 + */
6.138 +
6.139 + virtual void erase(const Key&) = 0;
6.140 +
6.141 + /**
6.142 + * The clear member function should be overloaded in the subclasses.
6.143 + * \e Clear makes empty the data structure.
6.144 + */
6.145 +
6.146 + virtual void clear() = 0;
6.147 +
6.148 + /**
6.149 + Exception class to throw at unsupported operation.
6.150 + */
6.151 +
6.152 + class NotSupportedOperationException {};
6.153 +
6.154 + };
6.155 +
6.156 + protected:
6.157 +
6.158 + /**
6.159 + * The container type of the maps.
6.160 + */
6.161 + typedef std::vector<MapBase*> Container;
6.162 +
6.163 + /**
6.164 + * The container of the registered maps.
6.165 + */
6.166 + Container container;
6.167 +
6.168 +
6.169 + public:
6.170 +
6.171 + /**
6.172 + * Default Constructor of the MapRegistry. It creates an empty registry.
6.173 + */
6.174 + MapRegistry() {}
6.175 +
6.176 + /**
6.177 + * Copy Constructor of the MapRegistry. The new registry does not steal
6.178 + * the maps from the right value. The new registry will be an empty.
6.179 + */
6.180 + MapRegistry(const MapRegistry&) {}
6.181 +
6.182 + /**
6.183 + * Assign operator. The left value does not steal the maps
6.184 + * from the right value. The left value will be an empty registry.
6.185 + */
6.186 + MapRegistry& operator=(const MapRegistry&) {
6.187 + typename Container::iterator it;
6.188 + for (it = container.begin(); it != container.end(); ++it) {
6.189 + (*it)->destroy();
6.190 + (*it)->graph = 0;
6.191 + (*it)->registry = 0;
6.192 + }
6.193 + }
6.194 +
6.195 + /**
6.196 + * Destructor of the MapRegistry.
6.197 + */
6.198 + ~MapRegistry() {
6.199 + typename Container::iterator it;
6.200 + for (it = container.begin(); it != container.end(); ++it) {
6.201 + (*it)->destroy();
6.202 + (*it)->registry = 0;
6.203 + (*it)->graph = 0;
6.204 + }
6.205 + }
6.206 +
6.207 +
6.208 + public:
6.209 +
6.210 + /**
6.211 + * Attach a map into thr registry. If the map has been attached
6.212 + * into an other registry it is detached from that automaticly.
6.213 + */
6.214 + void attach(MapBase& map) {
6.215 + if (map.registry) {
6.216 + map.registry->detach(map);
6.217 + }
6.218 + container.push_back(&map);
6.219 + map.registry = this;
6.220 + map.registry_index = container.size()-1;
6.221 + }
6.222 +
6.223 + /**
6.224 + * Detach the map from the registry.
6.225 + */
6.226 + void detach(MapBase& map) {
6.227 + container.back()->registry_index = map.registry_index;
6.228 + container[map.registry_index] = container.back();
6.229 + container.pop_back();
6.230 + map.registry = 0;
6.231 + map.graph = 0;
6.232 + }
6.233 +
6.234 +
6.235 + /**
6.236 + * Notify all the registered maps about a Key added.
6.237 + */
6.238 + virtual void add(Key& key) {
6.239 + typename Container::iterator it;
6.240 + for (it = container.begin(); it != container.end(); ++it) {
6.241 + (*it)->add(key);
6.242 + }
6.243 + }
6.244 +
6.245 + /**
6.246 + * Notify all the registered maps about a Key erased.
6.247 + */
6.248 + virtual void erase(Key& key) {
6.249 + typename Container::iterator it;
6.250 + for (it = container.begin(); it != container.end(); ++it) {
6.251 + (*it)->erase(key);
6.252 + }
6.253 + }
6.254 +
6.255 + /**
6.256 + * Notify all the registered maps about the map should be cleared.
6.257 + */
6.258 + virtual void clear() {
6.259 + typename Container::iterator it;
6.260 + for (it = container.begin(); it != container.end(); ++it) {
6.261 + (*it)->clear();
6.262 + }
6.263 + }
6.264 + };
6.265 +
6.266 +}
6.267 +
6.268 +#endif
7.1 --- a/src/hugo/smart_graph.h Wed Sep 01 15:37:36 2004 +0000
7.2 +++ b/src/hugo/smart_graph.h Thu Sep 02 10:07:30 2004 +0000
7.3 @@ -8,15 +8,21 @@
7.4 ///\brief SmartGraph and SymSmartGraph classes.
7.5
7.6 #include <vector>
7.7 -#include <limits.h>
7.8 +#include <climits>
7.9
7.10 #include <hugo/invalid.h>
7.11
7.12 +#include <hugo/array_map_factory.h>
7.13 +#include <hugo/sym_map_factory.h>
7.14 +#include <hugo/map_registry.h>
7.15 +
7.16 +#include <hugo/map_defines.h>
7.17 +
7.18 namespace hugo {
7.19
7.20 /// \addtogroup graphs
7.21 /// @{
7.22 - class SymSmartGraph;
7.23 +// class SymSmartGraph;
7.24
7.25 ///A smart graph class.
7.26
7.27 @@ -53,61 +59,27 @@
7.28
7.29 std::vector<EdgeT> edges;
7.30
7.31 - protected:
7.32 -
7.33 - template <typename Key> class DynMapBase
7.34 - {
7.35 - protected:
7.36 - const SmartGraph* G;
7.37 - public:
7.38 - virtual void add(const Key k) = 0;
7.39 - virtual void erase(const Key k) = 0;
7.40 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
7.41 - virtual ~DynMapBase() {}
7.42 - friend class SmartGraph;
7.43 - };
7.44
7.45 public:
7.46 - template <typename T> class EdgeMap;
7.47 - template <typename T> class NodeMap;
7.48 +
7.49 + typedef SmartGraph Graph;
7.50
7.51 class Node;
7.52 class Edge;
7.53
7.54 - // protected:
7.55 - // HELPME:
7.56 - protected:
7.57 - ///\bug It must be public because of SymEdgeMap.
7.58 - ///
7.59 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
7.60 - ///\bug It must be public because of SymEdgeMap.
7.61 - ///
7.62 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
7.63 -
7.64 - public:
7.65 -
7.66 -
7.67 class NodeIt;
7.68 class EdgeIt;
7.69 class OutEdgeIt;
7.70 class InEdgeIt;
7.71
7.72 - template <typename T> class NodeMap;
7.73 - template <typename T> class EdgeMap;
7.74 + CREATE_MAP_REGISTRIES;
7.75 + CREATE_MAPS(ArrayMapFactory);
7.76
7.77 public:
7.78
7.79 SmartGraph() : nodes(), edges() { }
7.80 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
7.81
7.82 - ~SmartGraph()
7.83 - {
7.84 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
7.85 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
7.86 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
7.87 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
7.88 - }
7.89 -
7.90 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
7.91 int edgeNum() const { return edges.size(); } //FIXME: What is this?
7.92
7.93 @@ -137,9 +109,8 @@
7.94 Node n; n.n=nodes.size();
7.95 nodes.push_back(NodeT()); //FIXME: Hmmm...
7.96
7.97 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
7.98 - i!=dyn_node_maps.end(); ++i) (**i).add(n);
7.99 -
7.100 +
7.101 + node_maps.add(n);
7.102 return n;
7.103 }
7.104
7.105 @@ -150,8 +121,7 @@
7.106 edges[e.n].next_in=nodes[v.n].first_in;
7.107 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
7.108
7.109 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
7.110 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
7.111 + edge_maps.add(e);
7.112
7.113 return e;
7.114 }
7.115 @@ -172,7 +142,12 @@
7.116 return prev;
7.117 }
7.118
7.119 - void clear() {nodes.clear();edges.clear();}
7.120 + void clear() {
7.121 + edge_maps.clear();
7.122 + edges.clear();
7.123 + node_maps.clear();
7.124 + nodes.clear();
7.125 + }
7.126
7.127 class Node {
7.128 friend class SmartGraph;
7.129 @@ -290,184 +265,6 @@
7.130 // operator bool() { return Edge::operator bool(); }
7.131 };
7.132
7.133 - template <typename T> class NodeMap : public DynMapBase<Node>
7.134 - {
7.135 - std::vector<T> container;
7.136 -
7.137 - public:
7.138 - typedef T ValueType;
7.139 - typedef Node KeyType;
7.140 -
7.141 - NodeMap(const SmartGraph &_G) :
7.142 - DynMapBase<Node>(_G), container(_G.maxNodeId())
7.143 - {
7.144 - G->dyn_node_maps.push_back(this);
7.145 - }
7.146 - NodeMap(const SmartGraph &_G,const T &t) :
7.147 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
7.148 - {
7.149 - G->dyn_node_maps.push_back(this);
7.150 - }
7.151 -
7.152 - NodeMap(const NodeMap<T> &m) :
7.153 - DynMapBase<Node>(*m.G), container(m.container)
7.154 - {
7.155 - G->dyn_node_maps.push_back(this);
7.156 - }
7.157 -
7.158 - template<typename TT> friend class NodeMap;
7.159 -
7.160 - ///\todo It can copy between different types.
7.161 - ///\todo We could use 'copy'
7.162 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
7.163 - DynMapBase<Node>(*m.G), container(m.container.size())
7.164 - {
7.165 - G->dyn_node_maps.push_back(this);
7.166 - typename std::vector<TT>::const_iterator i;
7.167 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.168 - i!=m.container.end();
7.169 - i++)
7.170 - container.push_back(*i);
7.171 - }
7.172 - ~NodeMap()
7.173 - {
7.174 - if(G) {
7.175 - std::vector<DynMapBase<Node>* >::iterator i;
7.176 - for(i=G->dyn_node_maps.begin();
7.177 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
7.178 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
7.179 - //A better way to do that: (Is this really important?)
7.180 - if(*i==this) {
7.181 - *i=G->dyn_node_maps.back();
7.182 - G->dyn_node_maps.pop_back();
7.183 - }
7.184 - }
7.185 - }
7.186 -
7.187 - void add(const Node k)
7.188 - {
7.189 - if(k.n>=int(container.size())) container.resize(k.n+1);
7.190 - }
7.191 -
7.192 - void erase(const Node) { }
7.193 -
7.194 - void set(Node n, T a) { container[n.n]=a; }
7.195 - //'T& operator[](Node n)' would be wrong here
7.196 - typename std::vector<T>::reference
7.197 - operator[](Node n) { return container[n.n]; }
7.198 - //'const T& operator[](Node n)' would be wrong here
7.199 - typename std::vector<T>::const_reference
7.200 - operator[](Node n) const { return container[n.n]; }
7.201 -
7.202 - ///\warning There is no safety check at all!
7.203 - ///Using operator = between maps attached to different graph may
7.204 - ///cause serious problem.
7.205 - ///\todo Is this really so?
7.206 - ///\todo It can copy between different types.
7.207 - const NodeMap<T>& operator=(const NodeMap<T> &m)
7.208 - {
7.209 - container = m.container;
7.210 - return *this;
7.211 - }
7.212 - template<typename TT>
7.213 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
7.214 - {
7.215 - std::copy(m.container.begin(), m.container.end(), container.begin());
7.216 - return *this;
7.217 - }
7.218 -
7.219 - void update() {} //Useless for Dynamic Maps
7.220 - void update(T a) {} //Useless for Dynamic Maps
7.221 - };
7.222 -
7.223 - template <typename T> class EdgeMap : public DynMapBase<Edge>
7.224 - {
7.225 - std::vector<T> container;
7.226 -
7.227 - public:
7.228 - typedef T ValueType;
7.229 - typedef Edge KeyType;
7.230 -
7.231 - EdgeMap(const SmartGraph &_G) :
7.232 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
7.233 - {
7.234 - //FIXME: What if there are empty Id's?
7.235 - //FIXME: Can I use 'this' in a constructor?
7.236 - G->dyn_edge_maps.push_back(this);
7.237 - }
7.238 - EdgeMap(const SmartGraph &_G,const T &t) :
7.239 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
7.240 - {
7.241 - G->dyn_edge_maps.push_back(this);
7.242 - }
7.243 - EdgeMap(const EdgeMap<T> &m) :
7.244 - DynMapBase<Edge>(*m.G), container(m.container)
7.245 - {
7.246 - G->dyn_edge_maps.push_back(this);
7.247 - }
7.248 -
7.249 - template<typename TT> friend class EdgeMap;
7.250 -
7.251 - ///\todo It can copy between different types.
7.252 - template<typename TT> EdgeMap(const EdgeMap<TT> &m)
7.253 - : DynMapBase<Edge>(*m.G), container(m.container.size())
7.254 - {
7.255 - G->dyn_edge_maps.push_back(this);
7.256 - typename std::vector<TT>::const_iterator i;
7.257 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.258 - i!=m.container.end();
7.259 - i++)
7.260 - container.push_back(*i);
7.261 - }
7.262 - ~EdgeMap()
7.263 - {
7.264 - if(G) {
7.265 - std::vector<DynMapBase<Edge>* >::iterator i;
7.266 - for(i=G->dyn_edge_maps.begin();
7.267 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
7.268 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
7.269 - //A better way to do that: (Is this really important?)
7.270 - if(*i==this) {
7.271 - *i=G->dyn_edge_maps.back();
7.272 - G->dyn_edge_maps.pop_back();
7.273 - }
7.274 - }
7.275 - }
7.276 -
7.277 - void add(const Edge k)
7.278 - {
7.279 - if(k.n>=int(container.size())) container.resize(k.n+1);
7.280 - }
7.281 - void erase(const Edge) { }
7.282 -
7.283 - void set(Edge n, T a) { container[n.n]=a; }
7.284 - //T get(Edge n) const { return container[n.n]; }
7.285 - typename std::vector<T>::reference
7.286 - operator[](Edge n) { return container[n.n]; }
7.287 - typename std::vector<T>::const_reference
7.288 - operator[](Edge n) const { return container[n.n]; }
7.289 -
7.290 - ///\warning There is no safety check at all!
7.291 - ///Using operator = between maps attached to different graph may
7.292 - ///cause serious problem.
7.293 - ///\todo Is this really so?
7.294 - ///\todo It can copy between different types.
7.295 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
7.296 - {
7.297 - container = m.container;
7.298 - return *this;
7.299 - }
7.300 - template<typename TT>
7.301 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
7.302 - {
7.303 - std::copy(m.container.begin(), m.container.end(), container.begin());
7.304 - return *this;
7.305 - }
7.306 -
7.307 - void update() {} //Useless for DynMaps
7.308 - void update(T a) {} //Useless for DynMaps
7.309 - };
7.310 -
7.311 };
7.312
7.313 ///Graph for bidirectional edges.
7.314 @@ -493,8 +290,14 @@
7.315 class SymSmartGraph : public SmartGraph
7.316 {
7.317 public:
7.318 - template<typename T> class SymEdgeMap;
7.319 - template<typename T> friend class SymEdgeMap;
7.320 + typedef SymSmartGraph Graph;
7.321 +
7.322 + KEEP_NODE_MAP(SmartGraph);
7.323 + KEEP_EDGE_MAP(SmartGraph);
7.324 +
7.325 + CREATE_SYM_EDGE_MAP_REGISTRY;
7.326 + CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
7.327 + IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
7.328
7.329 SymSmartGraph() : SmartGraph() { }
7.330 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
7.331 @@ -517,107 +320,10 @@
7.332 return f;
7.333 }
7.334
7.335 - ///Common data storage for the edge pairs.
7.336 -
7.337 - ///This map makes it possible to store data shared by the oppositely
7.338 - ///directed pairs of edges.
7.339 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
7.340 - {
7.341 - std::vector<T> container;
7.342 -
7.343 - public:
7.344 - typedef T ValueType;
7.345 - typedef Edge KeyType;
7.346 -
7.347 - SymEdgeMap(const SymSmartGraph &_G) :
7.348 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
7.349 - {
7.350 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
7.351 - }
7.352 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
7.353 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
7.354 - {
7.355 - G->dyn_edge_maps.push_back(this);
7.356 - }
7.357 -
7.358 - SymEdgeMap(const SymEdgeMap<T> &m) :
7.359 - DynMapBase<SymEdge>(*m.G), container(m.container)
7.360 - {
7.361 - G->dyn_node_maps.push_back(this);
7.362 - }
7.363 -
7.364 - // template<typename TT> friend class SymEdgeMap;
7.365 -
7.366 - ///\todo It can copy between different types.
7.367 - ///
7.368 -
7.369 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)
7.370 - : DynMapBase<SymEdge>(*m.G), container(m.container.size())
7.371 - {
7.372 - G->dyn_node_maps.push_back(this);
7.373 - typename std::vector<TT>::const_iterator i;
7.374 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.375 - i!=m.container.end();
7.376 - i++)
7.377 - container.push_back(*i);
7.378 - }
7.379 -
7.380 - ~SymEdgeMap()
7.381 - {
7.382 - if(G) {
7.383 - std::vector<DynMapBase<Edge>* >::iterator i;
7.384 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
7.385 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
7.386 - && *i!=this; ++i) ;
7.387 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
7.388 - //A better way to do that: (Is this really important?)
7.389 - if(*i==this) {
7.390 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
7.391 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
7.392 - }
7.393 - }
7.394 - }
7.395 -
7.396 - void add(const Edge k)
7.397 - {
7.398 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
7.399 - container.resize(k.idref()/2+1);
7.400 - }
7.401 - void erase(const Edge k) { }
7.402 -
7.403 - void set(Edge n, T a) { container[n.idref()/2]=a; }
7.404 - //T get(Edge n) const { return container[n.idref()/2]; }
7.405 - typename std::vector<T>::reference
7.406 - operator[](Edge n) { return container[n.idref()/2]; }
7.407 - typename std::vector<T>::const_reference
7.408 - operator[](Edge n) const { return container[n.idref()/2]; }
7.409 -
7.410 - ///\warning There is no safety check at all!
7.411 - ///Using operator = between maps attached to different graph may
7.412 - ///cause serious problem.
7.413 - ///\todo Is this really so?
7.414 - ///\todo It can copy between different types.
7.415 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
7.416 - {
7.417 - container = m.container;
7.418 - return *this;
7.419 - }
7.420 - template<typename TT>
7.421 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
7.422 - {
7.423 - std::copy(m.container.begin(), m.container.end(), container.begin());
7.424 - return *this;
7.425 - }
7.426 -
7.427 - void update() {} //Useless for DynMaps
7.428 - void update(T a) {} //Useless for DynMaps
7.429 -
7.430 - };
7.431
7.432 };
7.433
7.434 /// @}
7.435 -
7.436 } //namespace hugo
7.437
7.438
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/hugo/sym_map_factory.h Thu Sep 02 10:07:30 2004 +0000
8.3 @@ -0,0 +1,107 @@
8.4 +// -*- c++ -*-
8.5 +#ifndef SYM_MAP_FACTORY_H
8.6 +#define SYM_MAP_FACTORY_H
8.7 +
8.8 +namespace hugo {
8.9 +
8.10 + template <typename Graph, typename Edge, typename EdgeIt>
8.11 + class SymEdgeIt : public EdgeIt {
8.12 + public:
8.13 +
8.14 + SymEdgeIt()
8.15 + : EdgeIt() {}
8.16 +
8.17 + SymEdgeIt(const Graph& graph)
8.18 + : EdgeIt(graph) {}
8.19 +
8.20 + SymEdgeIt(Invalid invalid)
8.21 + : EdgeIt(invalid) {}
8.22 +
8.23 + SymEdgeIt(const Graph& graph, Edge edge)
8.24 + : EdgeIt(graph, edge) {}
8.25 +
8.26 + SymEdgeIt& operator++() {
8.27 + EdgeIt::operator++();
8.28 + while ( n != -1 && (n & 1)) {
8.29 + EdgeIt::operator++();
8.30 + }
8.31 + return *this;
8.32 + }
8.33 + };
8.34 +
8.35 + template <typename MapRegistry, template <typename> class MapFactory>
8.36 + class SymMapFactory {
8.37 +
8.38 + public:
8.39 +
8.40 + typedef typename MapRegistry::Graph Graph;
8.41 + typedef typename MapRegistry::Key Key;
8.42 + typedef typename MapRegistry::KeyIt KeyIt;
8.43 +
8.44 + typedef typename MapRegistry::MapBase MapBase;
8.45 +
8.46 + template <typename V>
8.47 + class Map : public MapFactory<MapRegistry>::template Map<V> {
8.48 +
8.49 + typedef typename MapFactory<MapRegistry>::template Map<V> MapImpl;
8.50 + public:
8.51 +
8.52 + typedef V Value;
8.53 +
8.54 + Map() : MapImpl() {}
8.55 +
8.56 + Map(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
8.57 +
8.58 + Map(const Graph& g, MapRegistry& r, const Value& v) : MapImpl(g, r, v) {}
8.59 +
8.60 + Map(const Map& copy) : MapImpl(static_cast<const MapImpl&>(copy)) {}
8.61 +
8.62 + template <typename CMap> Map(const CMap& copy) : MapImpl(copy) {}
8.63 +
8.64 + Map& operator=(const Map& copy) {
8.65 + MapImpl::operator=(static_cast<const MapImpl&>(copy));
8.66 + return *this;
8.67 + }
8.68 +
8.69 + template <typename CMap> Map& operator=(const CMap& copy) {
8.70 + MapImpl::operator=(copy);
8.71 + return *this;
8.72 + }
8.73 +
8.74 + Value& operator[](const Key& key) {
8.75 + int id = MapBase::getGraph()->id(key);
8.76 + return MapImpl::operator[](id >> 1);
8.77 + }
8.78 +
8.79 + const Value& operator[](const Key& key) const {
8.80 + int id = MapBase::getGraph()->id(key);
8.81 + return MapImpl::operator[](id >> 1);
8.82 + }
8.83 +
8.84 + const Value& get(const Key& key) const {
8.85 + int id = MapBase::getGraph()->id(key);
8.86 + return MapImpl::operator[](id >> 1);
8.87 + }
8.88 +
8.89 + void set(const Key& key, const Value& val) {
8.90 + int id = MapBase::getGraph()->id(key);
8.91 + MapImpl::operator[](id >> 1) = val;
8.92 + }
8.93 +
8.94 + void add(const Key& key) {
8.95 + int id = MapBase::getGraph()->id(key);
8.96 + if (id & 1) return;
8.97 + MapImpl::add(key);
8.98 + }
8.99 +
8.100 + void erase(const Key& key) {
8.101 + int id = MapBase::getGraph()->id(key);
8.102 + if (id & 1) return;
8.103 + MapImpl::add(key);
8.104 + }
8.105 +
8.106 +
8.107 + };
8.108 + };
8.109 +}
8.110 +#endif
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/src/hugo/vector_map_factory.h Thu Sep 02 10:07:30 2004 +0000
9.3 @@ -0,0 +1,338 @@
9.4 +// -*- c++ -*-
9.5 +#ifndef VECTOR_MAP_H
9.6 +#define VECTOR_MAP_H
9.7 +
9.8 +#include <vector>
9.9 +
9.10 +#include <hugo/extended_pair.h>
9.11 +
9.12 +namespace hugo {
9.13 +
9.14 + /** The VectorMapFactory template class is a factory class
9.15 + * to create maps for the edge and nodes. This map factory
9.16 + * use the std::vector to implement the container function.
9.17 + *
9.18 + * The template parameter is the MapRegistry that the maps
9.19 + * will belong to.
9.20 + */
9.21 +
9.22 + template <typename MapRegistry>
9.23 + class VectorMapFactory {
9.24 + public:
9.25 +
9.26 + /// The graph type of the maps.
9.27 + typedef typename MapRegistry::Graph Graph;
9.28 + /// The key type of the maps.
9.29 + typedef typename MapRegistry::Key Key;
9.30 + /// The iterator to iterate on the keys.
9.31 + typedef typename MapRegistry::KeyIt KeyIt;
9.32 +
9.33 + /// The MapBase of the Map which imlements the core regisitry function.
9.34 + typedef typename MapRegistry::MapBase MapBase;
9.35 +
9.36 +
9.37 + /** The template Map type.
9.38 + */
9.39 + template <typename V>
9.40 + class Map : public MapBase {
9.41 + public:
9.42 +
9.43 + /// The value type of the map.
9.44 + typedef V Value;
9.45 +
9.46 + typedef std::vector<Value> Container;
9.47 +
9.48 + /** Default constructor for the map.
9.49 + */
9.50 + Map() {}
9.51 +
9.52 + /** Graph and Registry initialized map constructor.
9.53 + */
9.54 + Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
9.55 + init();
9.56 + }
9.57 +
9.58 + /** Constructor to use default value to initialize the map.
9.59 + */
9.60 + Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
9.61 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.62 + int id = getGraph()->id(it);
9.63 + if (id >= container.size()) {
9.64 + container.resize(id + 1);
9.65 + }
9.66 + set(it, v);
9.67 + }
9.68 + }
9.69 +
9.70 + /** Constructor to copy a map of an other map type.
9.71 + */
9.72 + template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
9.73 + if (getGraph()) {
9.74 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.75 + int id = getGraph()->id(it);
9.76 + if (id >= container.size()) {
9.77 + container.resize(id + 1);
9.78 + }
9.79 + set(it, copy[it]);
9.80 + }
9.81 + }
9.82 + }
9.83 +
9.84 + /** Assign operator to copy a map an other map type.
9.85 + */
9.86 + template <typename CMap> Map& operator=(const CMap& copy) {
9.87 + if (getGraph()) {
9.88 + destroy();
9.89 + }
9.90 + this->MapBase::operator=(copy);
9.91 + if (getGraph()) {
9.92 + for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.93 + int id = getGraph()->id(it);
9.94 + if (id >= container.size()) {
9.95 + container.resize(id + 1);
9.96 + }
9.97 + set(it, copy[it]);
9.98 + }
9.99 + }
9.100 + }
9.101 +
9.102 + /** The destructor of the map.
9.103 + */
9.104 + virtual ~Map() {
9.105 + }
9.106 +
9.107 + /**
9.108 + * The subscript operator. The map can be subscripted by the
9.109 + * actual keys of the graph.
9.110 + */
9.111 + typename Container::reference operator[](const Key& key) {
9.112 + int id = getGraph()->id(key);
9.113 + return container[id];
9.114 + }
9.115 +
9.116 + /**
9.117 + * The const subscript operator. The map can be subscripted by the
9.118 + * actual keys of the graph.
9.119 + */
9.120 + typename Container::const_reference operator[](const Key& key) const {
9.121 + int id = getGraph()->id(key);
9.122 + return container[id];
9.123 + }
9.124 +
9.125 + /** Setter function of the map. Equivalent with map[key] = val.
9.126 + * This is a compatibility feature with the not dereferable maps.
9.127 + */
9.128 + void set(const Key& key, const Value& val) {
9.129 + int id = getGraph()->id(key);
9.130 + container[id] = val;
9.131 + }
9.132 +
9.133 + /** Add a new key to the map. It called by the map registry.
9.134 + */
9.135 + void add(const Key& key) {
9.136 + int id = getGraph()->id(key);
9.137 + if (id >= container.size()) {
9.138 + container.resize(id + 1);
9.139 + }
9.140 + }
9.141 +
9.142 + /** Erase a key from the map. It called by the map registry.
9.143 + */
9.144 + void erase(const Key& key) {}
9.145 +
9.146 + /** Clear the data structure.
9.147 + */
9.148 + void clear() {
9.149 + container.clear();
9.150 + }
9.151 +
9.152 + /** Compatible iterator with the stl maps' iterators.
9.153 + * It iterates on pairs of a key and a value.
9.154 + */
9.155 + class iterator {
9.156 + friend class Map;
9.157 + friend class const_iterator;
9.158 + private:
9.159 +
9.160 + /** Private constructor to initalize the the iterators returned
9.161 + * by the begin() and end().
9.162 + */
9.163 + iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
9.164 +
9.165 + public:
9.166 +
9.167 + /** Default constructor.
9.168 + */
9.169 + iterator() {}
9.170 +
9.171 + typedef extended_pair<const Key&, const Key&,
9.172 + Value&, Value&> Reference;
9.173 +
9.174 + /** Dereference operator for map.
9.175 + */
9.176 + Reference operator*() {
9.177 + return Reference(it, (*map)[it]);
9.178 + }
9.179 +
9.180 + class Pointer {
9.181 + friend class iterator;
9.182 + private:
9.183 + Reference data;
9.184 + Pointer(const Key& key, Value& val) : data(key, val) {}
9.185 + public:
9.186 + Reference* operator->() {return &data;}
9.187 + };
9.188 +
9.189 + /** Arrow operator for map.
9.190 + */
9.191 + Pointer operator->() {
9.192 + return Pointer(it, ((*map)[it]));
9.193 + }
9.194 +
9.195 + /** The pre increment operator of the map.
9.196 + */
9.197 + iterator& operator++() {
9.198 + ++it;
9.199 + return *this;
9.200 + }
9.201 +
9.202 + /** The post increment operator of the map.
9.203 + */
9.204 + iterator operator++(int) {
9.205 + iterator tmp(it);
9.206 + ++it;
9.207 + return tmp;
9.208 + }
9.209 +
9.210 + /** The equality operator of the map.
9.211 + */
9.212 + bool operator==(const_iterator p_it) {
9.213 + return p_it.it == it;
9.214 + }
9.215 +
9.216 + /** The not-equality operator of the map.
9.217 + */
9.218 + bool operator!=(const_iterator p_it) {
9.219 + return !(*this == p_it);
9.220 + }
9.221 +
9.222 +
9.223 + private:
9.224 + Map* map;
9.225 + KeyIt it;
9.226 + };
9.227 +
9.228 + /** Returns the begin iterator of the map.
9.229 + */
9.230 + iterator begin() {
9.231 + return iterator(*this, KeyIt(*getGraph()));
9.232 + }
9.233 +
9.234 + /** Returns the end iterator of the map.
9.235 + */
9.236 + iterator end() {
9.237 + return iterator(*this, INVALID);
9.238 + }
9.239 +
9.240 + class const_iterator {
9.241 + friend class Map;
9.242 + friend class iterator;
9.243 + private:
9.244 +
9.245 + /** Private constructor to initalize the the iterators returned
9.246 + * by the begin() and end().
9.247 + */
9.248 + const_iterator (const Map& pmap, const KeyIt& pit)
9.249 + : map(&pmap), it(pit) {}
9.250 +
9.251 + public:
9.252 +
9.253 + /** Default constructor.
9.254 + */
9.255 + const_iterator() {}
9.256 +
9.257 + /** Constructor to convert iterator to const_iterator.
9.258 + */
9.259 + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
9.260 +
9.261 + typedef extended_pair<const Key&, const Key&,
9.262 + const Value&, const Value&> Reference;
9.263 +
9.264 + /** Dereference operator for map.
9.265 + */
9.266 + Reference operator*() {
9.267 + return Reference(it, (*map)[it]);
9.268 + }
9.269 +
9.270 +
9.271 + class Pointer {
9.272 + friend class const_iterator;
9.273 + private:
9.274 + Reference data;
9.275 + Pointer(const Key& key, const Value& val) : data(key, val) {}
9.276 + public:
9.277 + Reference* operator->() {return &data;}
9.278 + };
9.279 +
9.280 + /** Arrow operator for map.
9.281 + */
9.282 + Pointer operator->() {
9.283 + return Pointer(it, ((*map)[it]));
9.284 + }
9.285 +
9.286 + /** The pre increment operator of the map.
9.287 + */
9.288 + const_iterator& operator++() {
9.289 + ++it;
9.290 + return *this;
9.291 + }
9.292 +
9.293 + /** The post increment operator of the map.
9.294 + */
9.295 + const_iterator operator++(int) {
9.296 + const_iterator tmp(it);
9.297 + ++it;
9.298 + return tmp;
9.299 + }
9.300 +
9.301 + /** The equality operator of the map.
9.302 + */
9.303 + bool operator==(const_iterator p_it) {
9.304 + return p_it.it == it;
9.305 + }
9.306 +
9.307 + /** The not-equality operator of the map.
9.308 + */
9.309 + bool operator!=(const_iterator p_it) {
9.310 + return !(*this == p_it);
9.311 + }
9.312 +
9.313 +
9.314 + private:
9.315 + const Map* map;
9.316 + KeyIt it;
9.317 + };
9.318 +
9.319 + /** Returns the begin const_iterator of the map.
9.320 + */
9.321 + const_iterator begin() const {
9.322 + return const_iterator(*this, KeyIt(*getGraph()));
9.323 + }
9.324 +
9.325 + /** Returns the end const_iterator of the map.
9.326 + */
9.327 + const_iterator end() const {
9.328 + return const_iterator(*this, INVALID);
9.329 + }
9.330 +
9.331 + private:
9.332 +
9.333 + Container container;
9.334 +
9.335 + };
9.336 +
9.337 + };
9.338 +
9.339 +}
9.340 +
9.341 +#endif