1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/deba/invalid.h Wed Jul 14 10:06:27 2004 +0000
1.3 @@ -0,0 +1,38 @@
1.4 +// -*- mode:C++ -*-
1.5 +
1.6 +#ifndef HUGO_INVALID_H
1.7 +#define HUGO_INVALID_H
1.8 +
1.9 +///\file
1.10 +///\brief Definition of INVALID.
1.11 +
1.12 +namespace hugo {
1.13 +
1.14 + /// Dummy type to make it easier to make invalid iterators.
1.15 +
1.16 + /// See \ref INVALID, how to use it.
1.17 +
1.18 + struct Invalid {
1.19 + public:
1.20 + bool operator==(Invalid) { return true; }
1.21 + bool operator!=(Invalid) { return false; }
1.22 + bool operator< (Invalid) { return false; }
1.23 + };
1.24 +
1.25 + /// Invalid iterators.
1.26 +
1.27 + /// \ref Invalid is a global type that converts to each iterator
1.28 + /// in such a way that the value of the target iterator will be invalid.
1.29 +
1.30 + // It is also used to convert the \c INVALID constant to the
1.31 + // node iterator that makes is possible to write
1.32 +
1.33 + //extern Invalid INVALID;
1.34 +
1.35 + //const Invalid &INVALID = *(Invalid *)0;
1.36 + const Invalid INVALID = Invalid();
1.37 +
1.38 +} //namespace hugo
1.39 +
1.40 +#endif
1.41 +
2.1 --- a/src/work/deba/list_graph.h Wed Jul 14 10:05:31 2004 +0000
2.2 +++ b/src/work/deba/list_graph.h Wed Jul 14 10:06:27 2004 +0000
2.3 @@ -395,911 +395,6 @@
2.4 ///\todo this date structure need some reconsiderations. Maybe it
2.5 ///should be implemented independently from ListGraph.
2.6
2.7 - };
2.8 -
2.9 -
2.10 - ///A graph class containing only nodes.
2.11 -
2.12 - ///This class implements a graph structure without edges.
2.13 - ///The most useful application of this class is to be the node set of an
2.14 - ///\ref EdgeSet class.
2.15 - ///
2.16 - ///It conforms to the graph interface documented under
2.17 - ///the description of \ref GraphSkeleton with the exception that you cannot
2.18 - ///add (or delete) edges. The usual edge iterators are exists, but they are
2.19 - ///always \ref INVALID.
2.20 - ///\sa \ref GraphSkeleton
2.21 - ///\sa \ref EdgeSet
2.22 - class NodeSet {
2.23 -
2.24 - //Nodes are double linked.
2.25 - //The free nodes are only single linked using the "next" field.
2.26 - struct NodeT
2.27 - {
2.28 - int first_in,first_out;
2.29 - int prev, next;
2.30 - // NodeT() {}
2.31 - };
2.32 -
2.33 - std::vector<NodeT> nodes;
2.34 - //The first node
2.35 - int first_node;
2.36 - //The first free node
2.37 - int first_free_node;
2.38 -
2.39 - protected:
2.40 -
2.41 - template <typename Key> class DynMapBase
2.42 - {
2.43 - protected:
2.44 - const NodeSet* G;
2.45 - public:
2.46 - virtual void add(const Key k) = 0;
2.47 - virtual void erase(const Key k) = 0;
2.48 - DynMapBase(const NodeSet &_G) : G(&_G) {}
2.49 - virtual ~DynMapBase() {}
2.50 - friend class NodeSet;
2.51 - };
2.52 -
2.53 - public:
2.54 - template <typename T> class EdgeMap;
2.55 - template <typename T> class NodeMap;
2.56 -
2.57 - class Node;
2.58 - class Edge;
2.59 -
2.60 - // protected:
2.61 - // HELPME:
2.62 - protected:
2.63 - ///\bug It must be public because of SymEdgeMap.
2.64 - ///
2.65 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
2.66 - //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
2.67 -
2.68 - public:
2.69 -
2.70 - class NodeIt;
2.71 - class EdgeIt;
2.72 - class OutEdgeIt;
2.73 - class InEdgeIt;
2.74 -
2.75 - template <typename T> class NodeMap;
2.76 - template <typename T> class EdgeMap;
2.77 -
2.78 - public:
2.79 -
2.80 - ///Default constructor
2.81 - NodeSet() : nodes(), first_node(-1),
2.82 - first_free_node(-1) {}
2.83 - ///Copy constructor
2.84 - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
2.85 - first_free_node(_g.first_free_node) {}
2.86 -
2.87 - ~NodeSet()
2.88 - {
2.89 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
2.90 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
2.91 - //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
2.92 - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
2.93 - }
2.94 -
2.95 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
2.96 - int edgeNum() const { return 0; } //FIXME: What is this?
2.97 -
2.98 - ///\bug This function does something different than
2.99 - ///its name would suggests...
2.100 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
2.101 - ///\bug This function does something different than
2.102 - ///its name would suggests...
2.103 - int maxEdgeId() const { return 0; } //FIXME: What is this?
2.104 -
2.105 - Node tail(Edge e) const { return INVALID; }
2.106 - Node head(Edge e) const { return INVALID; }
2.107 -
2.108 - Node aNode(OutEdgeIt e) const { return INVALID; }
2.109 - Node aNode(InEdgeIt e) const { return INVALID; }
2.110 -
2.111 - Node bNode(OutEdgeIt e) const { return INVALID; }
2.112 - Node bNode(InEdgeIt e) const { return INVALID; }
2.113 -
2.114 - NodeIt& first(NodeIt& v) const {
2.115 - v=NodeIt(*this); return v; }
2.116 - EdgeIt& first(EdgeIt& e) const {
2.117 - e=EdgeIt(*this); return e; }
2.118 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
2.119 - e=OutEdgeIt(*this,v); return e; }
2.120 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
2.121 - e=InEdgeIt(*this,v); return e; }
2.122 -
2.123 -// template< typename It >
2.124 -// It first() const { It e; first(e); return e; }
2.125 -
2.126 -// template< typename It >
2.127 -// It first(Node v) const { It e; first(e,v); return e; }
2.128 -
2.129 - bool valid(Edge e) const { return false; }
2.130 - bool valid(Node n) const { return n.n!=-1; }
2.131 -
2.132 - void setInvalid(Edge &e) { }
2.133 - void setInvalid(Node &n) { n.n=-1; }
2.134 -
2.135 - template <typename It> It getNext(It it) const
2.136 - { It tmp(it); return next(tmp); }
2.137 -
2.138 - NodeIt& next(NodeIt& it) const {
2.139 - it.n=nodes[it.n].next;
2.140 - return it;
2.141 - }
2.142 - OutEdgeIt& next(OutEdgeIt& it) const { return it; }
2.143 - InEdgeIt& next(InEdgeIt& it) const { return it; }
2.144 - EdgeIt& next(EdgeIt& it) const { return it; }
2.145 -
2.146 - int id(Node v) const { return v.n; }
2.147 - int id(Edge e) const { return -1; }
2.148 -
2.149 - /// Adds a new node to the graph.
2.150 -
2.151 - /// \todo It adds the nodes in a reversed order.
2.152 - /// (i.e. the lastly added node becomes the first.)
2.153 - Node addNode() {
2.154 - int n;
2.155 -
2.156 - if(first_free_node==-1)
2.157 - {
2.158 - n = nodes.size();
2.159 - nodes.push_back(NodeT());
2.160 - }
2.161 - else {
2.162 - n = first_free_node;
2.163 - first_free_node = nodes[n].next;
2.164 - }
2.165 -
2.166 - nodes[n].next = first_node;
2.167 - if(first_node != -1) nodes[first_node].prev = n;
2.168 - first_node = n;
2.169 - nodes[n].prev = -1;
2.170 -
2.171 - nodes[n].first_in = nodes[n].first_out = -1;
2.172 -
2.173 - Node nn; nn.n=n;
2.174 -
2.175 - //Update dynamic maps
2.176 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
2.177 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
2.178 -
2.179 - return nn;
2.180 - }
2.181 -
2.182 - void erase(Node nn) {
2.183 - int n=nn.n;
2.184 -
2.185 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
2.186 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
2.187 - else first_node = nodes[n].next;
2.188 -
2.189 - nodes[n].next = first_free_node;
2.190 - first_free_node = n;
2.191 -
2.192 - //Update dynamic maps
2.193 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
2.194 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
2.195 - }
2.196 -
2.197 - ///\bug Dynamic maps must be updated!
2.198 - ///
2.199 - void clear() {
2.200 - nodes.clear();
2.201 - first_node = first_free_node = -1;
2.202 - }
2.203 -
2.204 - class Node {
2.205 - friend class NodeSet;
2.206 - template <typename T> friend class NodeMap;
2.207 -
2.208 - friend class Edge;
2.209 - friend class OutEdgeIt;
2.210 - friend class InEdgeIt;
2.211 -
2.212 - protected:
2.213 - int n;
2.214 - friend int NodeSet::id(Node v) const;
2.215 - Node(int nn) {n=nn;}
2.216 - public:
2.217 - Node() {}
2.218 - Node (Invalid i) { n=-1; }
2.219 - bool operator==(const Node i) const {return n==i.n;}
2.220 - bool operator!=(const Node i) const {return n!=i.n;}
2.221 - bool operator<(const Node i) const {return n<i.n;}
2.222 - };
2.223 -
2.224 - class NodeIt : public Node {
2.225 - friend class NodeSet;
2.226 - public:
2.227 - NodeIt() : Node() { }
2.228 - NodeIt(Invalid i) : Node(i) { }
2.229 - NodeIt(const NodeSet& G) : Node(G.first_node) { }
2.230 - ///\todo Undocumented conversion Node -\> NodeIt.
2.231 - NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
2.232 -
2.233 - };
2.234 -
2.235 - class Edge {
2.236 - //friend class NodeSet;
2.237 - //template <typename T> friend class EdgeMap;
2.238 -
2.239 - //template <typename T> friend class SymNodeSet::SymEdgeMap;
2.240 - //friend Edge SymNodeSet::opposite(Edge) const;
2.241 -
2.242 - // friend class Node;
2.243 - // friend class NodeIt;
2.244 - protected:
2.245 - //friend int NodeSet::id(Edge e) const;
2.246 - // Edge(int nn) {}
2.247 - public:
2.248 - Edge() { }
2.249 - Edge (Invalid) { }
2.250 - bool operator==(const Edge i) const {return true;}
2.251 - bool operator!=(const Edge i) const {return false;}
2.252 - bool operator<(const Edge i) const {return false;}
2.253 - ///\bug This is a workaround until somebody tells me how to
2.254 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
2.255 - // int idref() {return -1;}
2.256 - // int idref() const {return -1;}
2.257 - };
2.258 -
2.259 - class EdgeIt : public Edge {
2.260 - //friend class NodeSet;
2.261 - public:
2.262 - EdgeIt(const NodeSet& G) : Edge() { }
2.263 - EdgeIt (Invalid i) : Edge(i) { }
2.264 - EdgeIt() : Edge() { }
2.265 - ///\bug This is a workaround until somebody tells me how to
2.266 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
2.267 - // int idref() {return -1;}
2.268 - };
2.269 -
2.270 - class OutEdgeIt : public Edge {
2.271 - friend class NodeSet;
2.272 - public:
2.273 - OutEdgeIt() : Edge() { }
2.274 - OutEdgeIt (Invalid i) : Edge(i) { }
2.275 - OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
2.276 - };
2.277 -
2.278 - class InEdgeIt : public Edge {
2.279 - friend class NodeSet;
2.280 - public:
2.281 - InEdgeIt() : Edge() { }
2.282 - InEdgeIt (Invalid i) : Edge(i) { }
2.283 - InEdgeIt(const NodeSet& G,Node v) :Edge() {}
2.284 - };
2.285 -
2.286 - template <typename T> class NodeMap : public DynMapBase<Node>
2.287 - {
2.288 - std::vector<T> container;
2.289 -
2.290 - public:
2.291 - typedef T ValueType;
2.292 - typedef Node KeyType;
2.293 -
2.294 - NodeMap(const NodeSet &_G) :
2.295 - DynMapBase<Node>(_G), container(_G.maxNodeId())
2.296 - {
2.297 - G->dyn_node_maps.push_back(this);
2.298 - }
2.299 - NodeMap(const NodeSet &_G,const T &t) :
2.300 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
2.301 - {
2.302 - G->dyn_node_maps.push_back(this);
2.303 - }
2.304 -
2.305 - NodeMap(const NodeMap<T> &m) :
2.306 - DynMapBase<Node>(*m.G), container(m.container)
2.307 - {
2.308 - G->dyn_node_maps.push_back(this);
2.309 - }
2.310 -
2.311 - template<typename TT> friend class NodeMap;
2.312 -
2.313 - ///\todo It can copy between different types.
2.314 - ///
2.315 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
2.316 - DynMapBase<Node>(*m.G), container(m.container.size())
2.317 - {
2.318 - G->dyn_node_maps.push_back(this);
2.319 - typename std::vector<TT>::const_iterator i;
2.320 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
2.321 - i!=m.container.end();
2.322 - i++)
2.323 - container.push_back(*i);
2.324 - }
2.325 - ~NodeMap()
2.326 - {
2.327 - if(G) {
2.328 - std::vector<DynMapBase<Node>* >::iterator i;
2.329 - for(i=G->dyn_node_maps.begin();
2.330 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
2.331 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
2.332 - //A better way to do that: (Is this really important?)
2.333 - if(*i==this) {
2.334 - *i=G->dyn_node_maps.back();
2.335 - G->dyn_node_maps.pop_back();
2.336 - }
2.337 - }
2.338 - }
2.339 -
2.340 - void add(const Node k)
2.341 - {
2.342 - if(k.n>=int(container.size())) container.resize(k.n+1);
2.343 - }
2.344 -
2.345 - void erase(const Node) { }
2.346 -
2.347 - void set(Node n, T a) { container[n.n]=a; }
2.348 - //'T& operator[](Node n)' would be wrong here
2.349 - typename std::vector<T>::reference
2.350 - operator[](Node n) { return container[n.n]; }
2.351 - //'const T& operator[](Node n)' would be wrong here
2.352 - typename std::vector<T>::const_reference
2.353 - operator[](Node n) const { return container[n.n]; }
2.354 -
2.355 - ///\warning There is no safety check at all!
2.356 - ///Using operator = between maps attached to different graph may
2.357 - ///cause serious problem.
2.358 - ///\todo Is this really so?
2.359 - ///\todo It can copy between different types.
2.360 - const NodeMap<T>& operator=(const NodeMap<T> &m)
2.361 - {
2.362 - container = m.container;
2.363 - return *this;
2.364 - }
2.365 - template<typename TT>
2.366 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
2.367 - {
2.368 - std::copy(m.container.begin(), m.container.end(), container.begin());
2.369 - return *this;
2.370 - }
2.371 -
2.372 - void update() {} //Useless for Dynamic Maps
2.373 - void update(T a) {} //Useless for Dynamic Maps
2.374 - };
2.375 -
2.376 - template <typename T> class EdgeMap
2.377 - {
2.378 - public:
2.379 - typedef T ValueType;
2.380 - typedef Edge KeyType;
2.381 -
2.382 - EdgeMap(const NodeSet &) { }
2.383 - EdgeMap(const NodeSet &,const T &) { }
2.384 - EdgeMap(const EdgeMap<T> &) { }
2.385 - // template<typename TT> friend class EdgeMap;
2.386 -
2.387 - ///\todo It can copy between different types.
2.388 - ///
2.389 - template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
2.390 - ~EdgeMap() { }
2.391 -
2.392 - void add(const Edge ) { }
2.393 - void erase(const Edge) { }
2.394 -
2.395 - void set(Edge, T) { }
2.396 - //T get(Edge n) const { return container[n.n]; }
2.397 - ValueType &operator[](Edge) { return *((T*)(NULL)); }
2.398 - const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
2.399 -
2.400 - const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
2.401 -
2.402 - template<typename TT>
2.403 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
2.404 -
2.405 - void update() {}
2.406 - void update(T a) {}
2.407 - };
2.408 - };
2.409 -
2.410 -
2.411 -
2.412 - ///Graph structure using a node set of another graph.
2.413 -
2.414 - ///This structure can be used to establish another graph over a node set
2.415 - /// of an existing one. The node iterator will go through the nodes of the
2.416 - /// original graph, and the NodeMap's of both graphs will convert to
2.417 - /// each other.
2.418 - ///
2.419 - ///\warning Adding or deleting nodes from the graph is not safe if an
2.420 - ///\ref EdgeSet is currently attached to it!
2.421 - ///
2.422 - ///\todo Make it possible to add/delete edges from the base graph
2.423 - ///(and from \ref EdgeSet, as well)
2.424 - ///
2.425 - ///\param GG The type of the graph which shares its node set with this class.
2.426 - ///Its interface must conform with \ref GraphSkeleton.
2.427 - ///
2.428 - ///It conforms to the graph interface documented under
2.429 - ///the description of \ref GraphSkeleton.
2.430 - ///\sa \ref GraphSkeleton.
2.431 - ///\sa \ref NodeSet.
2.432 - template<typename GG>
2.433 - class EdgeSet {
2.434 -
2.435 - typedef GG NodeGraphType;
2.436 -
2.437 - NodeGraphType &G;
2.438 -
2.439 - public:
2.440 - class Node;
2.441 - int id(Node v) const;
2.442 -
2.443 - class Node : public NodeGraphType::Node {
2.444 - friend class EdgeSet;
2.445 - // template <typename T> friend class NodeMap;
2.446 -
2.447 - friend class Edge;
2.448 - friend class OutEdgeIt;
2.449 - friend class InEdgeIt;
2.450 - friend class SymEdge;
2.451 -
2.452 - public:
2.453 - friend int EdgeSet::id(Node v) const;
2.454 - // Node(int nn) {n=nn;}
2.455 - public:
2.456 - Node() : NodeGraphType::Node() {}
2.457 - Node (Invalid i) : NodeGraphType::Node(i) {}
2.458 - Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
2.459 - };
2.460 -
2.461 - class NodeIt : public NodeGraphType::NodeIt {
2.462 - friend class EdgeSet;
2.463 - public:
2.464 - NodeIt() : NodeGraphType::NodeIt() { }
2.465 - NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
2.466 - NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
2.467 - NodeIt(const typename NodeGraphType::NodeIt &n)
2.468 - : NodeGraphType::NodeIt(n) {}
2.469 - ///\todo Undocumented conversion Node -\> NodeIt.
2.470 - NodeIt(const EdgeSet& _G, const Node &n)
2.471 - : NodeGraphType::NodeIt(_G.G,n) { }
2.472 -
2.473 - operator Node() { return Node(*this);}
2.474 - };
2.475 -
2.476 - private:
2.477 - //Edges are double linked.
2.478 - //The free edges are only single linked using the "next_in" field.
2.479 - struct NodeT
2.480 - {
2.481 - int first_in,first_out;
2.482 - NodeT() : first_in(-1), first_out(-1) { }
2.483 - };
2.484 -
2.485 - struct EdgeT
2.486 - {
2.487 - Node head, tail;
2.488 - int prev_in, prev_out;
2.489 - int next_in, next_out;
2.490 - };
2.491 -
2.492 -
2.493 - typename NodeGraphType::template NodeMap<NodeT> nodes;
2.494 -
2.495 - std::vector<EdgeT> edges;
2.496 - //The first free edge
2.497 - int first_free_edge;
2.498 -
2.499 - protected:
2.500 -
2.501 - template <typename Key> class DynMapBase
2.502 - {
2.503 - protected:
2.504 - const EdgeSet* G;
2.505 - public:
2.506 - virtual void add(const Key k) = 0;
2.507 - virtual void erase(const Key k) = 0;
2.508 - DynMapBase(const EdgeSet &_G) : G(&_G) {}
2.509 - virtual ~DynMapBase() {}
2.510 - friend class EdgeSet;
2.511 - };
2.512 -
2.513 - public:
2.514 - //template <typename T> class NodeMap;
2.515 - template <typename T> class EdgeMap;
2.516 -
2.517 - class Node;
2.518 - class Edge;
2.519 -
2.520 - // protected:
2.521 - // HELPME:
2.522 - protected:
2.523 - // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
2.524 - ///\bug It must be public because of SymEdgeMap.
2.525 - ///
2.526 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
2.527 -
2.528 - public:
2.529 -
2.530 - class NodeIt;
2.531 - class EdgeIt;
2.532 - class OutEdgeIt;
2.533 - class InEdgeIt;
2.534 -
2.535 - template <typename T> class NodeMap;
2.536 - template <typename T> class EdgeMap;
2.537 -
2.538 - public:
2.539 -
2.540 - ///Constructor
2.541 -
2.542 - ///Construates a new graph based on the nodeset of an existing one.
2.543 - ///\param _G the base graph.
2.544 - ///\todo It looks like a copy constructor, but it isn't.
2.545 - EdgeSet(NodeGraphType &_G) : G(_G),
2.546 - nodes(_G), edges(),
2.547 - first_free_edge(-1) { }
2.548 - ///Copy constructor
2.549 -
2.550 - ///Makes a copy of an EdgeSet.
2.551 - ///It will be based on the same graph.
2.552 - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
2.553 - first_free_edge(_g.first_free_edge) { }
2.554 -
2.555 - ~EdgeSet()
2.556 - {
2.557 - // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
2.558 - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
2.559 - for(typename std::vector<DynMapBase<Edge> * >::iterator
2.560 - i=dyn_edge_maps.begin();
2.561 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
2.562 - }
2.563 -
2.564 - int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
2.565 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
2.566 -
2.567 - ///\bug This function does something different than
2.568 - ///its name would suggests...
2.569 - int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
2.570 - ///\bug This function does something different than
2.571 - ///its name would suggests...
2.572 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
2.573 -
2.574 - Node tail(Edge e) const { return edges[e.n].tail; }
2.575 - Node head(Edge e) const { return edges[e.n].head; }
2.576 -
2.577 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
2.578 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
2.579 -
2.580 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
2.581 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
2.582 -
2.583 - NodeIt& first(NodeIt& v) const {
2.584 - v=NodeIt(*this); return v; }
2.585 - EdgeIt& first(EdgeIt& e) const {
2.586 - e=EdgeIt(*this); return e; }
2.587 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
2.588 - e=OutEdgeIt(*this,v); return e; }
2.589 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
2.590 - e=InEdgeIt(*this,v); return e; }
2.591 -
2.592 -// template< typename It >
2.593 -// It first() const { It e; first(e); return e; }
2.594 -
2.595 -// template< typename It >
2.596 -// It first(Node v) const { It e; first(e,v); return e; }
2.597 -
2.598 - bool valid(Edge e) const { return e.n!=-1; }
2.599 - bool valid(Node n) const { return G.valid(n); }
2.600 -
2.601 - void setInvalid(Edge &e) { e.n=-1; }
2.602 - void setInvalid(Node &n) { G.setInvalid(n); }
2.603 -
2.604 - template <typename It> It getNext(It it) const
2.605 - { It tmp(it); return next(tmp); }
2.606 -
2.607 - NodeIt& next(NodeIt& it) const { G.next(it); return it; }
2.608 - OutEdgeIt& next(OutEdgeIt& it) const
2.609 - { it.n=edges[it.n].next_out; return it; }
2.610 - InEdgeIt& next(InEdgeIt& it) const
2.611 - { it.n=edges[it.n].next_in; return it; }
2.612 - EdgeIt& next(EdgeIt& it) const {
2.613 - if(edges[it.n].next_in!=-1) {
2.614 - it.n=edges[it.n].next_in;
2.615 - }
2.616 - else {
2.617 - NodeIt n(*this,edges[it.n].head);
2.618 - for(n=next(n);
2.619 - valid(n) && nodes[n].first_in == -1;
2.620 - next(n)) ;
2.621 - it.n = (valid(n))?-1:nodes[n].first_in;
2.622 - }
2.623 - return it;
2.624 - }
2.625 -
2.626 - int id(Edge e) const { return e.n; }
2.627 -
2.628 - /// Adds a new node to the graph.
2.629 - Node addNode() { return G.addNode(); }
2.630 -
2.631 - Edge addEdge(Node u, Node v) {
2.632 - int n;
2.633 -
2.634 - if(first_free_edge==-1)
2.635 - {
2.636 - n = edges.size();
2.637 - edges.push_back(EdgeT());
2.638 - }
2.639 - else {
2.640 - n = first_free_edge;
2.641 - first_free_edge = edges[n].next_in;
2.642 - }
2.643 -
2.644 - edges[n].tail = u; edges[n].head = v;
2.645 -
2.646 - edges[n].next_out = nodes[u].first_out;
2.647 - if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
2.648 - edges[n].next_in = nodes[v].first_in;
2.649 - if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
2.650 - edges[n].prev_in = edges[n].prev_out = -1;
2.651 -
2.652 - nodes[u].first_out = nodes[v].first_in = n;
2.653 -
2.654 - Edge e; e.n=n;
2.655 -
2.656 - //Update dynamic maps
2.657 - for(typename std::vector<DynMapBase<Edge> * >::iterator
2.658 - i=dyn_edge_maps.begin();
2.659 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
2.660 -
2.661 - return e;
2.662 - }
2.663 -
2.664 - private:
2.665 - void eraseEdge(int n) {
2.666 -
2.667 - if(edges[n].next_in!=-1)
2.668 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
2.669 - if(edges[n].prev_in!=-1)
2.670 - edges[edges[n].prev_in].next_in = edges[n].next_in;
2.671 - else nodes[edges[n].head].first_in = edges[n].next_in;
2.672 -
2.673 - if(edges[n].next_out!=-1)
2.674 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
2.675 - if(edges[n].prev_out!=-1)
2.676 - edges[edges[n].prev_out].next_out = edges[n].next_out;
2.677 - else nodes[edges[n].tail].first_out = edges[n].next_out;
2.678 -
2.679 - edges[n].next_in = first_free_edge;
2.680 - first_free_edge = -1;
2.681 -
2.682 - //Update dynamic maps
2.683 - Edge e; e.n=n;
2.684 - for(typename std::vector<DynMapBase<Edge> * >::iterator
2.685 - i=dyn_edge_maps.begin();
2.686 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
2.687 - }
2.688 -
2.689 - public:
2.690 -
2.691 -// void erase(Node nn) {
2.692 -// int n=nn.n;
2.693 -// int m;
2.694 -// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
2.695 -// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
2.696 -// }
2.697 -
2.698 - void erase(Edge e) { eraseEdge(e.n); }
2.699 -
2.700 - ///Clear all edges. (Doesn't clear the nodes!)
2.701 - void clear() {
2.702 - edges.clear();
2.703 - first_free_edge=-1;
2.704 - }
2.705 -
2.706 -
2.707 -// //\bug Dynamic maps must be updated!
2.708 -// //
2.709 -// void clear() {
2.710 -// nodes.clear();edges.clear();
2.711 -// first_node=first_free_node=first_free_edge=-1;
2.712 -// }
2.713 -
2.714 - public:
2.715 - template <typename T> class EdgeMap;
2.716 -
2.717 - ///
2.718 - class Edge {
2.719 - public:
2.720 - friend class EdgeSet;
2.721 - template <typename T> friend class EdgeMap;
2.722 -
2.723 - friend class Node;
2.724 - friend class NodeIt;
2.725 - public:
2.726 - ///\bug It shoud be at least protected
2.727 - ///
2.728 - int n;
2.729 - protected:
2.730 - friend int EdgeSet::id(Edge e) const;
2.731 -
2.732 - Edge(int nn) {n=nn;}
2.733 - public:
2.734 - Edge() { }
2.735 - Edge (Invalid) { n=-1; }
2.736 - bool operator==(const Edge i) const {return n==i.n;}
2.737 - bool operator!=(const Edge i) const {return n!=i.n;}
2.738 - bool operator<(const Edge i) const {return n<i.n;}
2.739 - ///\bug This is a workaround until somebody tells me how to
2.740 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
2.741 - int &idref() {return n;}
2.742 - const int &idref() const {return n;}
2.743 - };
2.744 -
2.745 - class EdgeIt : public Edge {
2.746 - friend class EdgeSet;
2.747 - template <typename T> friend class EdgeMap;
2.748 -
2.749 -
2.750 - public:
2.751 - EdgeIt(const EdgeSet& G) : Edge() {
2.752 - // typename NodeGraphType::Node m;
2.753 - NodeIt m;
2.754 - for(G.first(m);
2.755 - G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
2.756 - //AJJAJ! This is a non sense!!!!!!!
2.757 - this->n = G.valid(m)?-1:G.nodes[m].first_in;
2.758 - }
2.759 - EdgeIt (Invalid i) : Edge(i) { }
2.760 - EdgeIt() : Edge() { }
2.761 - ///\bug This is a workaround until somebody tells me how to
2.762 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
2.763 - int &idref() {return this->n;}
2.764 - };
2.765 -
2.766 - class OutEdgeIt : public Edge {
2.767 - friend class EdgeSet;
2.768 - public:
2.769 - OutEdgeIt() : Edge() { }
2.770 - OutEdgeIt (Invalid i) : Edge(i) { }
2.771 -
2.772 - OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
2.773 - };
2.774 -
2.775 - class InEdgeIt : public Edge {
2.776 - friend class EdgeSet;
2.777 - public:
2.778 - InEdgeIt() : Edge() { }
2.779 - InEdgeIt (Invalid i) : Edge(i) { }
2.780 - InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
2.781 - };
2.782 -
2.783 - template <typename T> class NodeMap :
2.784 - public NodeGraphType::template NodeMap<T>
2.785 - {
2.786 - //This is a must, the constructors need it.
2.787 - typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
2.788 - public:
2.789 - NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
2.790 - NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
2.791 - //It is unnecessary
2.792 - NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
2.793 - ParentNodeMap(m) { }
2.794 -
2.795 - ///\todo It can copy between different types.
2.796 - ///
2.797 - template<typename TT>
2.798 - NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
2.799 - : ParentNodeMap(m) { }
2.800 - };
2.801 -
2.802 - ///
2.803 - template <typename T> class EdgeMap : public DynMapBase<Edge>
2.804 - {
2.805 - protected:
2.806 - public:
2.807 - ///\bug It should be at least protected
2.808 - ///
2.809 - std::vector<T> container;
2.810 -
2.811 - public:
2.812 - typedef T ValueType;
2.813 - typedef Edge KeyType;
2.814 -
2.815 - EdgeMap(const EdgeSet &_G) :
2.816 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
2.817 - {
2.818 - //FIXME: What if there are empty Id's?
2.819 - //FIXME: Can I use 'this' in a constructor?
2.820 - G->dyn_edge_maps.push_back(this);
2.821 - }
2.822 - EdgeMap(const EdgeSet &_G,const T &t) :
2.823 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
2.824 - {
2.825 - G->dyn_edge_maps.push_back(this);
2.826 - }
2.827 - EdgeMap(const EdgeMap<T> &m) :
2.828 - DynMapBase<Edge>(*m.G), container(m.container)
2.829 - {
2.830 - G->dyn_edge_maps.push_back(this);
2.831 - }
2.832 -
2.833 - template<typename TT> friend class EdgeMap;
2.834 -
2.835 - ///\todo It can copy between different types.
2.836 - ///
2.837 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
2.838 - DynMapBase<Edge>(*m.G), container(m.container.size())
2.839 - {
2.840 - G->dyn_edge_maps.push_back(this);
2.841 - typename std::vector<TT>::const_iterator i;
2.842 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
2.843 - i!=m.container.end();
2.844 - i++)
2.845 - container.push_back(*i);
2.846 - }
2.847 - ~EdgeMap()
2.848 - {
2.849 - if(G) {
2.850 - typename std::vector<DynMapBase<Edge>* >::iterator i;
2.851 - for(i=G->dyn_edge_maps.begin();
2.852 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
2.853 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
2.854 - //A better way to do that: (Is this really important?)
2.855 - if(*i==this) {
2.856 - *i=G->dyn_edge_maps.back();
2.857 - G->dyn_edge_maps.pop_back();
2.858 - }
2.859 - }
2.860 - }
2.861 -
2.862 - void add(const Edge k)
2.863 - {
2.864 - if(k.n>=int(container.size())) container.resize(k.n+1);
2.865 - }
2.866 - void erase(const Edge) { }
2.867 -
2.868 - ///\bug This doesn't work. Why?
2.869 - /// void set(Edge n, T a) { container[n.n]=a; }
2.870 - void set(Edge n, T a) { container[G->id(n)]=a; }
2.871 - //T get(Edge n) const { return container[n.n]; }
2.872 - typename std::vector<T>::reference
2.873 - ///\bug This doesn't work. Why?
2.874 - /// operator[](Edge n) { return container[n.n]; }
2.875 - operator[](Edge n) { return container[G->id(n)]; }
2.876 - typename std::vector<T>::const_reference
2.877 - ///\bug This doesn't work. Why?
2.878 - /// operator[](Edge n) const { return container[n.n]; }
2.879 - operator[](Edge n) const { return container[G->id(n)]; }
2.880 -
2.881 - ///\warning There is no safety check at all!
2.882 - ///Using operator = between maps attached to different graph may
2.883 - ///cause serious problem.
2.884 - ///\todo Is this really so?
2.885 - ///\todo It can copy between different types.
2.886 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
2.887 - {
2.888 - container = m.container;
2.889 - return *this;
2.890 - }
2.891 -
2.892 - template<typename TT> friend class EdgeMap;
2.893 -
2.894 - template<typename TT>
2.895 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
2.896 - {
2.897 - std::copy(m.container.begin(), m.container.end(), container.begin());
2.898 - return *this;
2.899 - }
2.900 -
2.901 - void update() {} //Useless for DynMaps
2.902 - void update(T a) {} //Useless for DynMaps
2.903 - };
2.904 -
2.905 - };
2.906 -
2.907 - template<typename GG>
2.908 - inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
2.909 -
2.910 -/// @}
2.911 -
2.912 -} //namespace hugo
2.913 +}
2.914
2.915 #endif //HUGO_LIST_GRAPH_H
3.1 --- a/src/work/deba/main.cpp Wed Jul 14 10:05:31 2004 +0000
3.2 +++ b/src/work/deba/main.cpp Wed Jul 14 10:06:27 2004 +0000
3.3 @@ -11,7 +11,7 @@
3.4 for (int i = 0; i < 10; ++i) {
3.5 ListGraph::Node node = g.addNode();
3.6 }
3.7 - ListGraph::NodeMap<int> map(g);
3.8 + ListGraph::NodeMap<int> map(g, 10);
3.9 for (int i = 0; i < 10; ++i) {
3.10 ListGraph::Node node = g.addNode();
3.11 map[node] = rand()%100;
3.12 @@ -19,6 +19,20 @@
3.13 for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
3.14 cout << map[it] << endl;
3.15 }
3.16 + ListGraph::NodeMap<int>::iterator pit;
3.17 + for (pit = map.begin(); pit != map.end(); ++pit) {
3.18 + cout << g.id(pit->first) << ' ' << pit->second << endl;
3.19 + }
3.20 + ListGraph::NodeMap<double> ot_map = map;
3.21 + for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
3.22 + ot_map[it] *= 2.1;
3.23 + cout << ot_map[it] << endl;
3.24 + }
3.25 + ot_map = map;
3.26 + for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
3.27 + ot_map[it] *= 3.1;
3.28 + cout << ot_map[it] << endl;
3.29 + }
3.30 return 0;
3.31 }
3.32
4.1 --- a/src/work/deba/map_defines.h Wed Jul 14 10:05:31 2004 +0000
4.2 +++ b/src/work/deba/map_defines.h Wed Jul 14 10:06:27 2004 +0000
4.3 @@ -2,44 +2,96 @@
4.4 #ifndef MAP_DEFINES_H
4.5 #define MAP_DEFINES_H
4.6
4.7 +/** Creates the EdgeMapRegistry type an declare a mutable instance
4.8 + * named edge_maps.
4.9 + */
4.10 #define CREATE_EDGE_MAP_REGISTRY \
4.11 typedef MapRegistry<Graph, Edge, EdgeIt> EdgeMapRegistry; \
4.12 -EdgeMapRegistry edge_maps;
4.13 +mutable EdgeMapRegistry edge_maps;
4.14
4.15 +/** Creates the NodeMapRegistry type an declare a mutable instance
4.16 + * named node_maps.
4.17 + */
4.18 #define CREATE_NODE_MAP_REGISTRY \
4.19 typedef MapRegistry<Graph, Node, NodeIt> NodeMapRegistry; \
4.20 -NodeMapRegistry node_maps;
4.21 +mutable NodeMapRegistry node_maps;
4.22
4.23 +/** Creates both map registries.
4.24 + */
4.25 #define CREATE_MAP_REGISTRIES \
4.26 CREATE_NODE_MAP_REGISTRY \
4.27 CREATE_EDGE_MAP_REGISTRY
4.28
4.29 +/** Creates a map a concrete factory type from a template map
4.30 + * factory to use as node map factory.
4.31 + */
4.32 #define CREATE_NODE_MAP_FACTORY(TemplateFactory) \
4.33 typedef TemplateFactory<NodeMapRegistry> NodeMapFactory;
4.34
4.35 +/** Creates a map a concrete factory type from a template map
4.36 + * factory to use as edge map factory.
4.37 + */
4.38 #define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \
4.39 typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory;
4.40
4.41 +/** Creates both map factories.
4.42 + */
4.43 #define CREATE_MAP_FACTORIES(TemplateFactory) \
4.44 CREATE_NODE_MAP_FACTORY(TemplateFactory) \
4.45 CREATE_EDGE_MAP_FACTORY(TemplateFactory)
4.46
4.47 +/** Import a map from a concrete map factory. The import method is
4.48 + * an overloading of the map type.
4.49 + * The reason to use these macro is that the c++ does not support
4.50 + * the template typedefs. If a future release of the c++
4.51 + * supports this feature it should be fixed.
4.52 + */
4.53 #define IMPORT_NODE_MAP(Factory) \
4.54 template <typename V> \
4.55 class NodeMap : public Factory::Map<V> { \
4.56 public: \
4.57 NodeMap() {} \
4.58 -NodeMap(Graph& g) : Factory::Map<V>(g, g.node_maps) {} \
4.59 +NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
4.60 +NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
4.61 +NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
4.62 +template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
4.63 +NodeMap& operator=(const NodeMap& copy) { \
4.64 + this->Factory::Map<V>::operator=(copy); \
4.65 + return *this; \
4.66 +} \
4.67 +template <typename CMap>NodeMap& operator=(const CMap& copy) { \
4.68 + this->Factory::Map<V>::operator=<CMap>(copy); \
4.69 + return *this; \
4.70 +} \
4.71 };
4.72
4.73 +/** Import a map from a concrete map factory. The import method is
4.74 + * an overloading of the map type.
4.75 + * The reason to use these macro is that the c++ does not support
4.76 + * the template typedefs. If a future release of the c++
4.77 + * supports this feature it should be fixed.
4.78 + */
4.79 #define IMPORT_EDGE_MAP(Factory) \
4.80 template <typename V> \
4.81 class EdgeMap : public Factory::Map<V> { \
4.82 public: \
4.83 EdgeMap() {} \
4.84 -EdgeMap(Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
4.85 +EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
4.86 +EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
4.87 +EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
4.88 +template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
4.89 +EdgeMap& operator=(const EdgeMap& copy) { \
4.90 + this->Factory::Map<V>::operator=(copy); \
4.91 + return *this; \
4.92 +} \
4.93 +template <typename CMap>EdgeMap& operator=(const CMap& copy) { \
4.94 + this->Factory::Map<V>::operator=<CMap>(copy); \
4.95 + return *this; \
4.96 +} \
4.97 };
4.98
4.99 +/** This macro creates both map factories and imports both maps.
4.100 + */
4.101 #define CREATE_MAPS(TemplateFactory) \
4.102 CREATE_MAP_FACTORIES(TemplateFactory) \
4.103 IMPORT_NODE_MAP(NodeMapFactory) \
5.1 --- a/src/work/deba/map_registry.h Wed Jul 14 10:05:31 2004 +0000
5.2 +++ b/src/work/deba/map_registry.h Wed Jul 14 10:06:27 2004 +0000
5.3 @@ -8,10 +8,10 @@
5.4 namespace hugo {
5.5
5.6 /**
5.7 - Registry class to register edge or node maps in the graph. The
5.8 - registry helps you to implement an observer pattern. If you add
5.9 - or erase an edge or node you must notify all the maps about the
5.10 - event.
5.11 + * Registry class to register edge or node maps into the graph. The
5.12 + * registry helps you to implement an observer pattern. If you add
5.13 + * or erase an edge or node you must notify all the maps about the
5.14 + * event.
5.15 */
5.16 template <typename G, typename K, typename KIt>
5.17 class MapRegistry {
5.18 @@ -22,10 +22,11 @@
5.19
5.20
5.21
5.22 - ///.
5.23 -
5.24 - ///.
5.25 - ///
5.26 + /**
5.27 + * MapBase is the base class of the registered maps.
5.28 + * It defines the core modification operations on the maps and
5.29 + * implements some helper functions.
5.30 + */
5.31 class MapBase {
5.32 public:
5.33 typedef G Graph;
5.34 @@ -34,23 +35,23 @@
5.35 typedef KIt KeyIt;
5.36
5.37 friend class Registry;
5.38 +
5.39 + /**
5.40 + * Default constructor for MapBase.
5.41 + */
5.42 +
5.43 + MapBase() : graph(0), registry(0) {}
5.44
5.45 /**
5.46 - Default constructor.
5.47 - */
5.48 -
5.49 - MapBase() : graph(0), registry(0) {}
5.50 -
5.51 - /**
5.52 - Simple constructor to register into a graph registry.
5.53 + * Simple constructor to register into a graph registry.
5.54 */
5.55
5.56 - MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
5.57 + MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
5.58 r.attach(*this);
5.59 }
5.60
5.61 /**
5.62 - Copy constructor with registering into the map.
5.63 + * Copy constructor to register into the registry.
5.64 */
5.65
5.66 MapBase(const MapBase& copy) : registry(0), graph(copy.graph) {
5.67 @@ -60,7 +61,7 @@
5.68 }
5.69
5.70 /**
5.71 - Assign operator.
5.72 + * Assign operator.
5.73 */
5.74
5.75 const MapBase& operator=(const MapBase& copy) {
5.76 @@ -75,7 +76,7 @@
5.77
5.78
5.79 /**
5.80 - Destructor.
5.81 + * Destructor.
5.82 */
5.83
5.84 virtual ~MapBase() {
5.85 @@ -83,13 +84,21 @@
5.86 registry->detach(*this);
5.87 }
5.88 }
5.89 +
5.90 + /*
5.91 + * Returns the graph that the map belongs to.
5.92 + */
5.93 +
5.94 + const Graph* getGraph() const { return graph; }
5.95
5.96 - protected:
5.97 + private:
5.98
5.99 - Graph* graph;
5.100 + const Graph* graph;
5.101 Registry* registry;
5.102
5.103 int registry_index;
5.104 +
5.105 + protected:
5.106
5.107 /**
5.108 Helper function to implement constructors in the subclasses.
5.109 @@ -106,7 +115,7 @@
5.110 */
5.111
5.112 virtual void destroy() {
5.113 - for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
5.114 + for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
5.115 erase(it);
5.116 }
5.117 }
5.118 @@ -134,19 +143,34 @@
5.119
5.120 protected:
5.121
5.122 + /**
5.123 + * The container type of the maps.
5.124 + */
5.125 typedef std::vector<MapBase*> Container;
5.126 +
5.127 + /**
5.128 + * The container of the registered maps.
5.129 + */
5.130 Container container;
5.131
5.132
5.133 - public:
5.134 + public:
5.135
5.136 - ///.
5.137 + /**
5.138 + * Default Constructor of the MapRegistry. It creates an empty registry.
5.139 + */
5.140 MapRegistry() {}
5.141
5.142 - ///.
5.143 + /**
5.144 + * Copy Constructor of the MapRegistry. The new registry does not steal
5.145 + * the maps from the right value. The new registry will be an empty.
5.146 + */
5.147 MapRegistry(const MapRegistry&) {}
5.148
5.149 - ///.
5.150 + /**
5.151 + * Assign operator. The left value does not steal the maps
5.152 + * from the right value. The left value will be an empty registry.
5.153 + */
5.154 MapRegistry& operator=(const MapRegistry&) {
5.155 for (it = container.begin(); it != container.end(); ++it) {
5.156 (*it)->destroy();
5.157 @@ -155,7 +179,9 @@
5.158 }
5.159 }
5.160
5.161 - ///.
5.162 + /**
5.163 + * Destructor of the MapRegistry.
5.164 + */
5.165 ~MapRegistry() {
5.166 typename Container::iterator it;
5.167 for (it = container.begin(); it != container.end(); ++it) {
5.168 @@ -168,7 +194,10 @@
5.169
5.170 public:
5.171
5.172 - ///.
5.173 + /**
5.174 + * Attach a map into thr registry. If the map has been attached
5.175 + * into an other registry it is detached from that automaticly.
5.176 + */
5.177 void attach(MapBase& map) {
5.178 if (map.registry) {
5.179 map.registry->detach(map);
5.180 @@ -178,7 +207,9 @@
5.181 map.registry_index = container.size()-1;
5.182 }
5.183
5.184 - ///.
5.185 + /**
5.186 + * Detach the map from the registry.
5.187 + */
5.188 void detach(MapBase& map) {
5.189 container.back()->registry_index = map.registry_index;
5.190 container[map.registry_index] = container.back();
5.191 @@ -188,7 +219,9 @@
5.192 }
5.193
5.194
5.195 - ///.
5.196 + /**
5.197 + * Notify all the registered maps about a Key added.
5.198 + */
5.199 virtual void add(Key& key) {
5.200 typename Container::iterator it;
5.201 for (it = container.begin(); it != container.end(); ++it) {
5.202 @@ -196,7 +229,9 @@
5.203 }
5.204 }
5.205
5.206 - ///.
5.207 + /**
5.208 + * Notify all the registered maps about a Key erased.
5.209 + */
5.210 virtual void erase(Key& key) {
5.211 typename Container::iterator it;
5.212 for (it = container.begin(); it != container.end(); ++it) {