1.1 --- a/src/hugo/list_graph.h Wed Sep 01 15:37:36 2004 +0000
1.2 +++ b/src/hugo/list_graph.h Thu Sep 02 10:07:30 2004 +0000
1.3 @@ -8,16 +8,24 @@
1.4 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
1.5
1.6 #include <vector>
1.7 -#include <limits.h>
1.8 +#include <climits>
1.9
1.10 #include <hugo/invalid.h>
1.11
1.12 +#include <hugo/map_registry.h>
1.13 +#include <hugo/array_map_factory.h>
1.14 +
1.15 +#include <hugo/sym_map_factory.h>
1.16 +
1.17 +#include <hugo/map_defines.h>
1.18 +
1.19 +
1.20 namespace hugo {
1.21
1.22 /// \addtogroup graphs
1.23 /// @{
1.24
1.25 - class SymListGraph;
1.26 +// class SymListGraph;
1.27
1.28 ///A list graph class.
1.29
1.30 @@ -56,36 +64,13 @@
1.31 //The first free edge
1.32 int first_free_edge;
1.33
1.34 - protected:
1.35 + public:
1.36
1.37 - template <typename Key> class DynMapBase
1.38 - {
1.39 - protected:
1.40 - const ListGraph* G;
1.41 - public:
1.42 - virtual void add(const Key k) = 0;
1.43 - virtual void erase(const Key k) = 0;
1.44 - DynMapBase(const ListGraph &_G) : G(&_G) {}
1.45 - virtual ~DynMapBase() {}
1.46 - friend class ListGraph;
1.47 - };
1.48 -
1.49 - public:
1.50 - template <typename T> class EdgeMap;
1.51 - template <typename T> class NodeMap;
1.52 + typedef ListGraph Graph;
1.53
1.54 class Node;
1.55 class Edge;
1.56
1.57 - // protected:
1.58 - // HELPME:
1.59 - protected:
1.60 - ///\bug It must be public because of SymEdgeMap.
1.61 - ///
1.62 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.63 - ///\bug It must be public because of SymEdgeMap.
1.64 - ///
1.65 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.66
1.67 public:
1.68
1.69 @@ -93,24 +78,21 @@
1.70 class EdgeIt;
1.71 class OutEdgeIt;
1.72 class InEdgeIt;
1.73 -
1.74 +
1.75 + CREATE_MAP_REGISTRIES;
1.76 + CREATE_MAPS(ArrayMapFactory);
1.77 +
1.78 public:
1.79
1.80 - ListGraph() : nodes(), first_node(-1),
1.81 - first_free_node(-1), edges(), first_free_edge(-1) {}
1.82 - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.83 - first_free_node(_g.first_free_node),
1.84 - edges(_g.edges),
1.85 - first_free_edge(_g.first_free_edge) {}
1.86 + ListGraph()
1.87 + : nodes(), first_node(-1),
1.88 + first_free_node(-1), edges(), first_free_edge(-1) {}
1.89 +
1.90 + ListGraph(const ListGraph &_g)
1.91 + : nodes(_g.nodes), first_node(_g.first_node),
1.92 + first_free_node(_g.first_free_node), edges(_g.edges),
1.93 + first_free_edge(_g.first_free_edge) {}
1.94
1.95 - ~ListGraph()
1.96 - {
1.97 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.98 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.99 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.100 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.101 - }
1.102 -
1.103 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.104 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.105
1.106 @@ -170,8 +152,7 @@
1.107 Node nn; nn.n=n;
1.108
1.109 //Update dynamic maps
1.110 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.111 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.112 + node_maps.add(nn);
1.113
1.114 return nn;
1.115 }
1.116 @@ -202,8 +183,7 @@
1.117 Edge e; e.n=n;
1.118
1.119 //Update dynamic maps
1.120 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.121 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.122 + edge_maps.add(e);
1.123
1.124 return e;
1.125 }
1.126 @@ -244,8 +224,8 @@
1.127
1.128 //Update dynamic maps
1.129 Edge e; e.n=n;
1.130 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.131 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.132 + edge_maps.erase(e);
1.133 +
1.134 }
1.135
1.136 public:
1.137 @@ -265,16 +245,17 @@
1.138 first_free_node = n;
1.139
1.140 //Update dynamic maps
1.141 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.142 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.143 + node_maps.erase(nn);
1.144 +
1.145 }
1.146
1.147 void erase(Edge e) { eraseEdge(e.n); }
1.148
1.149 - ///\bug Dynamic maps must be updated!
1.150 - ///
1.151 void clear() {
1.152 - nodes.clear();edges.clear();
1.153 + edge_maps.clear();
1.154 + edges.clear();
1.155 + node_maps.clear();
1.156 + nodes.clear();
1.157 first_node=first_free_node=first_free_edge=-1;
1.158 }
1.159
1.160 @@ -410,188 +391,6 @@
1.161 // ///Validity check
1.162 // operator bool() { return Edge::operator bool(); }
1.163 };
1.164 -
1.165 - template <typename T> class NodeMap : public DynMapBase<Node>
1.166 - {
1.167 - std::vector<T> container;
1.168 -
1.169 - public:
1.170 - typedef T ValueType;
1.171 - typedef Node KeyType;
1.172 -
1.173 - NodeMap(const ListGraph &_G) :
1.174 - DynMapBase<Node>(_G), container(_G.maxNodeId())
1.175 - {
1.176 - G->dyn_node_maps.push_back(this);
1.177 - }
1.178 - NodeMap(const ListGraph &_G,const T &t) :
1.179 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.180 - {
1.181 - G->dyn_node_maps.push_back(this);
1.182 - }
1.183 -
1.184 - NodeMap(const NodeMap<T> &m) :
1.185 - DynMapBase<Node>(*m.G), container(m.container)
1.186 - {
1.187 - G->dyn_node_maps.push_back(this);
1.188 - }
1.189 -
1.190 - template<typename TT> friend class NodeMap;
1.191 -
1.192 - ///\todo It can copy between different types.
1.193 - ///
1.194 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.195 - DynMapBase<Node>(*m.G), container(m.container.size())
1.196 -
1.197 - {
1.198 - G->dyn_node_maps.push_back(this);
1.199 - typename std::vector<TT>::const_iterator i;
1.200 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.201 - i!=m.container.end();
1.202 - i++)
1.203 - container.push_back(*i);
1.204 - }
1.205 - ~NodeMap()
1.206 - {
1.207 - if(G) {
1.208 - std::vector<DynMapBase<Node>* >::iterator i;
1.209 - for(i=G->dyn_node_maps.begin();
1.210 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.211 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.212 - //A better way to do that: (Is this really important?)
1.213 - if(*i==this) {
1.214 - *i=G->dyn_node_maps.back();
1.215 - G->dyn_node_maps.pop_back();
1.216 - }
1.217 - }
1.218 - }
1.219 -
1.220 - void add(const Node k)
1.221 - {
1.222 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.223 - }
1.224 -
1.225 - void erase(const Node) { }
1.226 -
1.227 - void set(Node n, T a) { container[n.n]=a; }
1.228 - //'T& operator[](Node n)' would be wrong here
1.229 - typename std::vector<T>::reference
1.230 - operator[](Node n) { return container[n.n]; }
1.231 - //'const T& operator[](Node n)' would be wrong here
1.232 - typename std::vector<T>::const_reference
1.233 - operator[](Node n) const { return container[n.n]; }
1.234 -
1.235 - ///\warning There is no safety check at all!
1.236 - ///Using operator = between maps attached to different graph may
1.237 - ///cause serious problem.
1.238 - ///\todo Is this really so?
1.239 - ///\todo It can copy between different types.
1.240 - const NodeMap<T>& operator=(const NodeMap<T> &m)
1.241 - {
1.242 - container = m.container;
1.243 - return *this;
1.244 - }
1.245 - template<typename TT>
1.246 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.247 - {
1.248 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.249 - return *this;
1.250 - }
1.251 -
1.252 - void update() {} //Useless for Dynamic Maps
1.253 - void update(T a) {} //Useless for Dynamic Maps
1.254 - };
1.255 -
1.256 - template <typename T> class EdgeMap : public DynMapBase<Edge>
1.257 - {
1.258 - protected:
1.259 - std::vector<T> container;
1.260 -
1.261 - public:
1.262 - typedef T ValueType;
1.263 - typedef Edge KeyType;
1.264 -
1.265 - EdgeMap(const ListGraph &_G) :
1.266 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.267 - {
1.268 - //FIXME: What if there are empty Id's?
1.269 - //FIXME: Can I use 'this' in a constructor?
1.270 - G->dyn_edge_maps.push_back(this);
1.271 - }
1.272 - EdgeMap(const ListGraph &_G,const T &t) :
1.273 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.274 - {
1.275 - G->dyn_edge_maps.push_back(this);
1.276 - }
1.277 - EdgeMap(const EdgeMap<T> &m) :
1.278 - DynMapBase<Edge>(*m.G), container(m.container)
1.279 - {
1.280 - G->dyn_edge_maps.push_back(this);
1.281 - }
1.282 -
1.283 - template<typename TT> friend class EdgeMap;
1.284 -
1.285 - ///\todo It can copy between different types.
1.286 - ///
1.287 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.288 - DynMapBase<Edge>(*m.G), container(m.container.size())
1.289 - {
1.290 - G->dyn_edge_maps.push_back(this);
1.291 - typename std::vector<TT>::const_iterator i;
1.292 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.293 - i!=m.container.end();
1.294 - i++)
1.295 - container.push_back(*i);
1.296 - }
1.297 - ~EdgeMap()
1.298 - {
1.299 - if(G) {
1.300 - std::vector<DynMapBase<Edge>* >::iterator i;
1.301 - for(i=G->dyn_edge_maps.begin();
1.302 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.303 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.304 - //A better way to do that: (Is this really important?)
1.305 - if(*i==this) {
1.306 - *i=G->dyn_edge_maps.back();
1.307 - G->dyn_edge_maps.pop_back();
1.308 - }
1.309 - }
1.310 - }
1.311 -
1.312 - void add(const Edge k)
1.313 - {
1.314 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.315 - }
1.316 - void erase(const Edge) { }
1.317 -
1.318 - void set(Edge n, T a) { container[n.n]=a; }
1.319 - //T get(Edge n) const { return container[n.n]; }
1.320 - typename std::vector<T>::reference
1.321 - operator[](Edge n) { return container[n.n]; }
1.322 - typename std::vector<T>::const_reference
1.323 - operator[](Edge n) const { return container[n.n]; }
1.324 -
1.325 - ///\warning There is no safety check at all!
1.326 - ///Using operator = between maps attached to different graph may
1.327 - ///cause serious problem.
1.328 - ///\todo Is this really so?
1.329 - ///\todo It can copy between different types.
1.330 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.331 - {
1.332 - container = m.container;
1.333 - return *this;
1.334 - }
1.335 - template<typename TT>
1.336 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.337 - {
1.338 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.339 - return *this;
1.340 - }
1.341 -
1.342 - void update() {} //Useless for DynMaps
1.343 - void update(T a) {} //Useless for DynMaps
1.344 - };
1.345 -
1.346 };
1.347
1.348 ///Graph for bidirectional edges.
1.349 @@ -615,12 +414,19 @@
1.350 ///
1.351 ///\todo this date structure need some reconsiderations. Maybe it
1.352 ///should be implemented independently from ListGraph.
1.353 -
1.354 +
1.355 class SymListGraph : public ListGraph
1.356 {
1.357 public:
1.358 - template<typename T> class SymEdgeMap;
1.359 - template<typename T> friend class SymEdgeMap;
1.360 +
1.361 + typedef SymListGraph Graph;
1.362 +
1.363 + KEEP_NODE_MAP(ListGraph);
1.364 + KEEP_EDGE_MAP(ListGraph);
1.365 +
1.366 + CREATE_SYM_EDGE_MAP_REGISTRY;
1.367 + CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
1.368 + IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
1.369
1.370 SymListGraph() : ListGraph() { }
1.371 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
1.372 @@ -628,11 +434,14 @@
1.373 Edge addEdge(Node u, Node v)
1.374 {
1.375 Edge e = ListGraph::addEdge(u,v);
1.376 - ListGraph::addEdge(v,u);
1.377 + Edge f = ListGraph::addEdge(v,u);
1.378 + sym_edge_maps.add(e);
1.379 + sym_edge_maps.add(f);
1.380 +
1.381 return e;
1.382 }
1.383
1.384 - void erase(Node n) { ListGraph::erase(n); }
1.385 + void erase(Node n) { ListGraph::erase(n);}
1.386 ///The oppositely directed edge.
1.387
1.388 ///Returns the oppositely directed
1.389 @@ -646,109 +455,14 @@
1.390
1.391 ///Removes a pair of oppositely directed edges to the graph.
1.392 void erase(Edge e) {
1.393 - ListGraph::erase(opposite(e));
1.394 + Edge f = opposite(e);
1.395 + sym_edge_maps.erase(e);
1.396 + sym_edge_maps.erase(f);
1.397 + ListGraph::erase(f);
1.398 ListGraph::erase(e);
1.399 - }
1.400 -
1.401 - ///Common data storage for the edge pairs.
1.402 + }
1.403 + };
1.404
1.405 - ///This map makes it possible to store data shared by the oppositely
1.406 - ///directed pairs of edges.
1.407 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
1.408 - {
1.409 - std::vector<T> container;
1.410 -
1.411 - public:
1.412 - typedef T ValueType;
1.413 - typedef Edge KeyType;
1.414 -
1.415 - SymEdgeMap(const SymListGraph &_G) :
1.416 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
1.417 - {
1.418 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
1.419 - }
1.420 - SymEdgeMap(const SymListGraph &_G,const T &t) :
1.421 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
1.422 - {
1.423 - G->dyn_edge_maps.push_back(this);
1.424 - }
1.425 -
1.426 - SymEdgeMap(const SymEdgeMap<T> &m) :
1.427 - DynMapBase<SymEdge>(*m.G), container(m.container)
1.428 - {
1.429 - G->dyn_node_maps.push_back(this);
1.430 - }
1.431 -
1.432 - // template<typename TT> friend class SymEdgeMap;
1.433 -
1.434 - ///\todo It can copy between different types.
1.435 - ///
1.436 -
1.437 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
1.438 - DynMapBase<SymEdge>(*m.G), container(m.container.size())
1.439 - {
1.440 - G->dyn_node_maps.push_back(this);
1.441 - typename std::vector<TT>::const_iterator i;
1.442 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.443 - i!=m.container.end();
1.444 - i++)
1.445 - container.push_back(*i);
1.446 - }
1.447 -
1.448 - ~SymEdgeMap()
1.449 - {
1.450 - if(G) {
1.451 - std::vector<DynMapBase<Edge>* >::iterator i;
1.452 - for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
1.453 - i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
1.454 - && *i!=this; ++i) ;
1.455 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.456 - //A better way to do that: (Is this really important?)
1.457 - if(*i==this) {
1.458 - *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
1.459 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
1.460 - }
1.461 - }
1.462 - }
1.463 -
1.464 - void add(const Edge k)
1.465 - {
1.466 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
1.467 - container.resize(k.idref()/2+1);
1.468 - }
1.469 - void erase(const Edge k) { }
1.470 -
1.471 - void set(Edge n, T a) { container[n.idref()/2]=a; }
1.472 - //T get(Edge n) const { return container[n.idref()/2]; }
1.473 - typename std::vector<T>::reference
1.474 - operator[](Edge n) { return container[n.idref()/2]; }
1.475 - typename std::vector<T>::const_reference
1.476 - operator[](Edge n) const { return container[n.idref()/2]; }
1.477 -
1.478 - ///\warning There is no safety check at all!
1.479 - ///Using operator = between maps attached to different graph may
1.480 - ///cause serious problem.
1.481 - ///\todo Is this really so?
1.482 - ///\todo It can copy between different types.
1.483 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
1.484 - {
1.485 - container = m.container;
1.486 - return *this;
1.487 - }
1.488 - template<typename TT>
1.489 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
1.490 - {
1.491 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.492 - return *this;
1.493 - }
1.494 -
1.495 - void update() {} //Useless for DynMaps
1.496 - void update(T a) {} //Useless for DynMaps
1.497 -
1.498 - };
1.499 -
1.500 - };
1.501 -
1.502
1.503 ///A graph class containing only nodes.
1.504
1.505 @@ -779,35 +493,13 @@
1.506 //The first free node
1.507 int first_free_node;
1.508
1.509 - protected:
1.510 -
1.511 - template <typename Key> class DynMapBase
1.512 - {
1.513 - protected:
1.514 - const NodeSet* G;
1.515 - public:
1.516 - virtual void add(const Key k) = 0;
1.517 - virtual void erase(const Key k) = 0;
1.518 - DynMapBase(const NodeSet &_G) : G(&_G) {}
1.519 - virtual ~DynMapBase() {}
1.520 - friend class NodeSet;
1.521 - };
1.522 -
1.523 public:
1.524 - template <typename T> class EdgeMap;
1.525 - template <typename T> class NodeMap;
1.526 +
1.527 + typedef NodeSet Graph;
1.528
1.529 class Node;
1.530 class Edge;
1.531
1.532 - // protected:
1.533 - // HELPME:
1.534 - protected:
1.535 - ///\bug It must be public because of SymEdgeMap.
1.536 - ///
1.537 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.538 - //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.539 -
1.540 public:
1.541
1.542 class NodeIt;
1.543 @@ -815,26 +507,19 @@
1.544 class OutEdgeIt;
1.545 class InEdgeIt;
1.546
1.547 - template <typename T> class NodeMap;
1.548 - template <typename T> class EdgeMap;
1.549 + CREATE_MAP_REGISTRIES;
1.550 + CREATE_MAPS(ArrayMapFactory);
1.551
1.552 public:
1.553
1.554 ///Default constructor
1.555 - NodeSet() : nodes(), first_node(-1),
1.556 - first_free_node(-1) {}
1.557 + NodeSet()
1.558 + : nodes(), first_node(-1), first_free_node(-1) {}
1.559 ///Copy constructor
1.560 - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.561 - first_free_node(_g.first_free_node) {}
1.562 + NodeSet(const NodeSet &_g)
1.563 + : nodes(_g.nodes), first_node(_g.first_node),
1.564 + first_free_node(_g.first_free_node) {}
1.565
1.566 - ~NodeSet()
1.567 - {
1.568 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.569 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.570 - //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.571 - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.572 - }
1.573 -
1.574 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.575 int edgeNum() const { return 0; } //FIXME: What is this?
1.576
1.577 @@ -887,8 +572,7 @@
1.578 Node nn; nn.n=n;
1.579
1.580 //Update dynamic maps
1.581 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.582 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.583 + node_maps.add(nn);
1.584
1.585 return nn;
1.586 }
1.587 @@ -904,8 +588,7 @@
1.588 first_free_node = n;
1.589
1.590 //Update dynamic maps
1.591 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.592 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.593 + node_maps.erase(nn);
1.594 }
1.595
1.596
1.597 @@ -914,9 +597,8 @@
1.598 return INVALID;
1.599 }
1.600
1.601 - ///\bug Dynamic maps must be updated!
1.602 - ///
1.603 void clear() {
1.604 + node_maps.clear();
1.605 nodes.clear();
1.606 first_node = first_free_node = -1;
1.607 }
1.608 @@ -1012,128 +694,6 @@
1.609 InEdgeIt operator++() { return INVALID; }
1.610 };
1.611
1.612 - template <typename T> class NodeMap : public DynMapBase<Node>
1.613 - {
1.614 - std::vector<T> container;
1.615 -
1.616 - public:
1.617 - typedef T ValueType;
1.618 - typedef Node KeyType;
1.619 -
1.620 - NodeMap(const NodeSet &_G) :
1.621 - DynMapBase<Node>(_G), container(_G.maxNodeId())
1.622 - {
1.623 - G->dyn_node_maps.push_back(this);
1.624 - }
1.625 - NodeMap(const NodeSet &_G,const T &t) :
1.626 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.627 - {
1.628 - G->dyn_node_maps.push_back(this);
1.629 - }
1.630 -
1.631 - NodeMap(const NodeMap<T> &m) :
1.632 - DynMapBase<Node>(*m.G), container(m.container)
1.633 - {
1.634 - G->dyn_node_maps.push_back(this);
1.635 - }
1.636 -
1.637 - template<typename TT> friend class NodeMap;
1.638 -
1.639 - ///\todo It can copy between different types.
1.640 - ///
1.641 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.642 - DynMapBase<Node>(*m.G), container(m.container.size())
1.643 - {
1.644 - G->dyn_node_maps.push_back(this);
1.645 - typename std::vector<TT>::const_iterator i;
1.646 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.647 - i!=m.container.end();
1.648 - i++)
1.649 - container.push_back(*i);
1.650 - }
1.651 - ~NodeMap()
1.652 - {
1.653 - if(G) {
1.654 - std::vector<DynMapBase<Node>* >::iterator i;
1.655 - for(i=G->dyn_node_maps.begin();
1.656 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.657 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.658 - //A better way to do that: (Is this really important?)
1.659 - if(*i==this) {
1.660 - *i=G->dyn_node_maps.back();
1.661 - G->dyn_node_maps.pop_back();
1.662 - }
1.663 - }
1.664 - }
1.665 -
1.666 - void add(const Node k)
1.667 - {
1.668 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.669 - }
1.670 -
1.671 - void erase(const Node) { }
1.672 -
1.673 - void set(Node n, T a) { container[n.n]=a; }
1.674 - //'T& operator[](Node n)' would be wrong here
1.675 - typename std::vector<T>::reference
1.676 - operator[](Node n) { return container[n.n]; }
1.677 - //'const T& operator[](Node n)' would be wrong here
1.678 - typename std::vector<T>::const_reference
1.679 - operator[](Node n) const { return container[n.n]; }
1.680 -
1.681 - ///\warning There is no safety check at all!
1.682 - ///Using operator = between maps attached to different graph may
1.683 - ///cause serious problem.
1.684 - ///\todo Is this really so?
1.685 - ///\todo It can copy between different types.
1.686 - const NodeMap<T>& operator=(const NodeMap<T> &m)
1.687 - {
1.688 - container = m.container;
1.689 - return *this;
1.690 - }
1.691 - template<typename TT>
1.692 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.693 - {
1.694 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.695 - return *this;
1.696 - }
1.697 -
1.698 - void update() {} //Useless for Dynamic Maps
1.699 - void update(T a) {} //Useless for Dynamic Maps
1.700 - };
1.701 -
1.702 - template <typename T> class EdgeMap
1.703 - {
1.704 - public:
1.705 - typedef T ValueType;
1.706 - typedef Edge KeyType;
1.707 -
1.708 - EdgeMap(const NodeSet &) { }
1.709 - EdgeMap(const NodeSet &,const T &) { }
1.710 - EdgeMap(const EdgeMap<T> &) { }
1.711 - // template<typename TT> friend class EdgeMap;
1.712 -
1.713 - ///\todo It can copy between different types.
1.714 - ///
1.715 - template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1.716 - ~EdgeMap() { }
1.717 -
1.718 - void add(const Edge ) { }
1.719 - void erase(const Edge) { }
1.720 -
1.721 - void set(Edge, T) { }
1.722 - //T get(Edge n) const { return container[n.n]; }
1.723 - ValueType &operator[](Edge) { return *((T*)(NULL)); }
1.724 - const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1.725 -
1.726 - const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1.727 -
1.728 - template<typename TT>
1.729 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1.730 -
1.731 - void update() {}
1.732 - void update(T a) {}
1.733 - };
1.734 };
1.735
1.736
1.737 @@ -1166,11 +726,15 @@
1.738 NodeGraphType &G;
1.739
1.740 public:
1.741 +
1.742 class Node;
1.743 class Edge;
1.744 class OutEdgeIt;
1.745 class InEdgeIt;
1.746 class SymEdge;
1.747 +
1.748 + typedef EdgeSet Graph;
1.749 +
1.750 int id(Node v) const;
1.751
1.752 class Node : public NodeGraphType::Node {
1.753 @@ -1229,44 +793,21 @@
1.754 //The first free edge
1.755 int first_free_edge;
1.756
1.757 - protected:
1.758 -
1.759 - template <typename Key> class DynMapBase
1.760 - {
1.761 - protected:
1.762 - const EdgeSet* G;
1.763 - public:
1.764 - virtual void add(const Key k) = 0;
1.765 - virtual void erase(const Key k) = 0;
1.766 - DynMapBase(const EdgeSet &_G) : G(&_G) {}
1.767 - virtual ~DynMapBase() {}
1.768 - friend class EdgeSet;
1.769 - };
1.770 -
1.771 public:
1.772 - //template <typename T> class NodeMap;
1.773 - template <typename T> class EdgeMap;
1.774
1.775 class Node;
1.776 class Edge;
1.777
1.778 - // protected:
1.779 - // HELPME:
1.780 - protected:
1.781 - // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.782 - ///\bug It must be public because of SymEdgeMap.
1.783 - ///
1.784 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.785 -
1.786 - public:
1.787 -
1.788 class NodeIt;
1.789 class EdgeIt;
1.790 class OutEdgeIt;
1.791 class InEdgeIt;
1.792 +
1.793 +
1.794 + CREATE_EDGE_MAP_REGISTRY;
1.795 + CREATE_EDGE_MAP_FACTORY(ArrayMapFactory);
1.796 + IMPORT_EDGE_MAP(EdgeMapFactory);
1.797
1.798 - template <typename T> class NodeMap;
1.799 - template <typename T> class EdgeMap;
1.800
1.801 public:
1.802
1.803 @@ -1275,25 +816,17 @@
1.804 ///Construates a new graph based on the nodeset of an existing one.
1.805 ///\param _G the base graph.
1.806 ///\todo It looks like a copy constructor, but it isn't.
1.807 - EdgeSet(NodeGraphType &_G) : G(_G),
1.808 - nodes(_G), edges(),
1.809 - first_free_edge(-1) { }
1.810 + EdgeSet(NodeGraphType &_G)
1.811 + : G(_G), nodes(_G), edges(),
1.812 + first_free_edge(-1) {}
1.813 ///Copy constructor
1.814
1.815 ///Makes a copy of an EdgeSet.
1.816 ///It will be based on the same graph.
1.817 - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1.818 - first_free_edge(_g.first_free_edge) { }
1.819 + EdgeSet(const EdgeSet &_g)
1.820 + : G(_g.G), nodes(_g.G), edges(_g.edges),
1.821 + first_free_edge(_g.first_free_edge) {}
1.822
1.823 - ~EdgeSet()
1.824 - {
1.825 - // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.826 - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.827 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.828 - i=dyn_edge_maps.begin();
1.829 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.830 - }
1.831 -
1.832 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1.833 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.834
1.835 @@ -1347,9 +880,7 @@
1.836 Edge e; e.n=n;
1.837
1.838 //Update dynamic maps
1.839 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.840 - i=dyn_edge_maps.begin();
1.841 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.842 + edge_maps.add(e);
1.843
1.844 return e;
1.845 }
1.846 @@ -1389,10 +920,8 @@
1.847 first_free_edge = -1;
1.848
1.849 //Update dynamic maps
1.850 - Edge e; e.n=n;
1.851 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.852 - i=dyn_edge_maps.begin();
1.853 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.854 + Edge e; e.n = n;
1.855 + edge_maps.erase(e);
1.856 }
1.857
1.858 public:
1.859 @@ -1408,22 +937,12 @@
1.860
1.861 ///Clear all edges. (Doesn't clear the nodes!)
1.862 void clear() {
1.863 + edge_maps.clear();
1.864 edges.clear();
1.865 first_free_edge=-1;
1.866 }
1.867
1.868
1.869 -// //\bug Dynamic maps must be updated!
1.870 -// //
1.871 -// void clear() {
1.872 -// nodes.clear();edges.clear();
1.873 -// first_node=first_free_node=first_free_edge=-1;
1.874 -// }
1.875 -
1.876 - public:
1.877 - template <typename T> class EdgeMap;
1.878 -
1.879 - ///
1.880 class Edge {
1.881 public:
1.882 friend class EdgeSet;
1.883 @@ -1490,7 +1009,7 @@
1.884
1.885 OutEdgeIt(const EdgeSet& _G,const Node v) :
1.886 Edge(_G.nodes[v].first_out), G(&_G) { }
1.887 - OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
1.888 + OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
1.889 };
1.890
1.891 class InEdgeIt : public Edge {
1.892 @@ -1505,126 +1024,41 @@
1.893 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
1.894 };
1.895
1.896 - template <typename T> class NodeMap :
1.897 - public NodeGraphType::template NodeMap<T>
1.898 +
1.899 + template <typename V> class NodeMap
1.900 + : public NodeGraphType::template NodeMap<V>
1.901 {
1.902 //This is a must, the constructors need it.
1.903 - typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
1.904 + typedef typename NodeGraphType::template NodeMap<V> MapImpl;
1.905 + typedef V Value;
1.906 public:
1.907 - NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
1.908 - NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
1.909 - //It is unnecessary
1.910 - NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
1.911 - ParentNodeMap(m) { }
1.912 + NodeMap() : MapImpl() {}
1.913 +
1.914 + NodeMap(const EdgeSet& graph)
1.915 + : MapImpl(graph.G) { }
1.916
1.917 - ///\todo It can copy between different types.
1.918 - ///
1.919 - template<typename TT>
1.920 - NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
1.921 - : ParentNodeMap(m) { }
1.922 - };
1.923 -
1.924 - ///
1.925 - template <typename T> class EdgeMap : public DynMapBase<Edge>
1.926 - {
1.927 - protected:
1.928 - public:
1.929 - ///\bug It should be at least protected
1.930 - ///
1.931 - std::vector<T> container;
1.932 + NodeMap(const EdgeSet& graph, const Value& value)
1.933 + : MapImpl(graph.G, value) { }
1.934
1.935 - public:
1.936 - typedef T ValueType;
1.937 - typedef Edge KeyType;
1.938 + NodeMap(const NodeMap& copy)
1.939 + : MapImpl(static_cast<const MapImpl&>(copy)) {}
1.940
1.941 - EdgeMap(const EdgeSet &_G) :
1.942 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.943 - {
1.944 - //FIXME: What if there are empty Id's?
1.945 - //FIXME: Can I use 'this' in a constructor?
1.946 - this->G->dyn_edge_maps.push_back(this);
1.947 - }
1.948 - EdgeMap(const EdgeSet &_G,const T &t) :
1.949 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.950 - {
1.951 - this->G->dyn_edge_maps.push_back(this);
1.952 - }
1.953 - EdgeMap(const EdgeMap<T> &m) :
1.954 - DynMapBase<Edge>(*m.G), container(m.container)
1.955 - {
1.956 - this->G->dyn_edge_maps.push_back(this);
1.957 + template<typename CMap>
1.958 + NodeMap(const CMap& copy)
1.959 + : MapImpl(copy) { }
1.960 +
1.961 + NodeMap& operator=(const NodeMap& copy) {
1.962 + MapImpl::operator=(static_cast<const MapImpl&>(copy));
1.963 + return *this;
1.964 }
1.965
1.966 - ///\todo It can copy between different types.
1.967 - ///
1.968 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.969 - DynMapBase<Edge>(*m.G), container(m.container.size())
1.970 - {
1.971 - this->G->dyn_edge_maps.push_back(this);
1.972 - typename std::vector<TT>::const_iterator i;
1.973 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.974 - i!=m.container.end();
1.975 - i++)
1.976 - container.push_back(*i);
1.977 - }
1.978 - ~EdgeMap()
1.979 - {
1.980 - if(this->G) {
1.981 - typename std::vector<DynMapBase<Edge>* >::iterator i;
1.982 - for(i=this->G->dyn_edge_maps.begin();
1.983 - i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.984 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.985 - //A better way to do that: (Is this really important?)
1.986 - if(*i==this) {
1.987 - *i=this->G->dyn_edge_maps.back();
1.988 - this->G->dyn_edge_maps.pop_back();
1.989 - }
1.990 - }
1.991 - }
1.992 -
1.993 - void add(const Edge k)
1.994 - {
1.995 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.996 - }
1.997 - void erase(const Edge) { }
1.998 -
1.999 - ///\bug This doesn't work. Why?
1.1000 - /// void set(Edge n, T a) { container[n.n]=a; }
1.1001 - void set(Edge n, T a) { container[this->G->id(n)]=a; }
1.1002 - //T get(Edge n) const { return container[n.n]; }
1.1003 - typename std::vector<T>::reference
1.1004 - ///\bug This doesn't work. Why?
1.1005 - /// operator[](Edge n) { return container[n.n]; }
1.1006 - operator[](Edge n) { return container[this->G->id(n)]; }
1.1007 - typename std::vector<T>::const_reference
1.1008 - ///\bug This doesn't work. Why?
1.1009 - /// operator[](Edge n) const { return container[n.n]; }
1.1010 - operator[](Edge n) const { return container[this->G->id(n)]; }
1.1011 -
1.1012 - ///\warning There is no safety check at all!
1.1013 - ///Using operator = between maps attached to different graph may
1.1014 - ///cause serious problem.
1.1015 - ///\todo Is this really so?
1.1016 - ///\todo It can copy between different types.
1.1017 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.1018 - {
1.1019 - container = m.container;
1.1020 + template <typename CMap>
1.1021 + NodeMap& operator=(const CMap& copy) {
1.1022 + MapImpl::operator=(copy);
1.1023 return *this;
1.1024 }
1.1025 -
1.1026 - template<typename TT> friend class EdgeMap;
1.1027
1.1028 - template<typename TT>
1.1029 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.1030 - {
1.1031 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.1032 - return *this;
1.1033 - }
1.1034 -
1.1035 - void update() {} //Useless for DynMaps
1.1036 - void update(T a) {} //Useless for DynMaps
1.1037 };
1.1038 -
1.1039 };
1.1040
1.1041 template<typename GG>