1.1 --- a/src/hugo/path.h Mon Sep 13 13:57:13 2004 +0000
1.2 +++ b/src/hugo/path.h Mon Sep 13 15:30:01 2004 +0000
1.3 @@ -40,7 +40,7 @@
1.4 //! A structure for representing directed path in a graph.
1.5 //! \param Graph The graph type in which the path is.
1.6 //! \param DM DebugMode, defaults to DefaultDebugMode.
1.7 - //!
1.8 + //!
1.9 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.10 //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.11 //! and \c Edge of the original graph.
1.12 @@ -50,7 +50,7 @@
1.13 class DirPath {
1.14 public:
1.15 /// Edge type of the underlying graph.
1.16 - typedef typename Graph::Edge GraphEdge;
1.17 + typedef typename Graph::Edge GraphEdge;
1.18 /// Node type of the underlying graph.
1.19 typedef typename Graph::Node GraphNode;
1.20 class NodeIt;
1.21 @@ -154,12 +154,12 @@
1.22
1.23 /**
1.24 * \brief Iterator class to iterate on the edges of the paths
1.25 - *
1.26 + *
1.27 * \ingroup paths
1.28 * This class is used to iterate on the edges of the paths
1.29 *
1.30 * Of course it converts to Graph::Edge
1.31 - *
1.32 + *
1.33 * \todo Its interface differs from the standard edge iterator.
1.34 * Yes, it shouldn't.
1.35 */
1.36 @@ -203,12 +203,12 @@
1.37
1.38 /**
1.39 * \brief Iterator class to iterate on the nodes of the paths
1.40 - *
1.41 + *
1.42 * \ingroup paths
1.43 * This class is used to iterate on the nodes of the paths
1.44 *
1.45 * Of course it converts to Graph::Node
1.46 - *
1.47 + *
1.48 * \todo Its interface differs from the standard node iterator.
1.49 * Yes, it shouldn't.
1.50 */
1.51 @@ -252,11 +252,11 @@
1.52 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.53 };
1.54
1.55 - friend class Builder;
1.56 + friend class Builder;
1.57
1.58 /**
1.59 * \brief Class to build paths
1.60 - *
1.61 + *
1.62 * \ingroup paths
1.63 * This class is used to fill a path with edges.
1.64 *
1.65 @@ -280,7 +280,7 @@
1.66 Builder(DirPath &_P) : P(_P) {}
1.67
1.68 /// Sets the starting node of the path.
1.69 -
1.70 +
1.71 /// Sets the starting node of the path. Edge added to the path
1.72 /// afterwards have to be incident to this node.
1.73 /// It should be called iff the path is empty and before any call to
1.74 @@ -305,7 +305,7 @@
1.75
1.76 ///Commit the changes to the path.
1.77 void commit() {
1.78 - if( !(front.empty() && back.empty()) ) {
1.79 + if( !front.empty() || !back.empty() ) {
1.80 Container tmp;
1.81 tmp.reserve(front.size()+back.size()+P.length());
1.82 tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.83 @@ -317,20 +317,19 @@
1.84 }
1.85 }
1.86
1.87 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.88 - // Hogy kenyelmes egy ilyet hasznalni?
1.89 -
1.90 ///Reserve storage for the builder in advance.
1.91
1.92 - ///If you know an reasonable upper bound of the number of the edges
1.93 - ///to add, using this function you can speed up the building.
1.94 - void reserve(size_t r) {
1.95 - front.reserve(r);
1.96 - back.reserve(r);
1.97 - }
1.98 + ///If you know a reasonable upper bound of the number of the edges
1.99 + ///to add to the front, using this function you can speed up the building.
1.100
1.101 - void reserveFront(size_t r) {}
1.102 - void reserveBack(size_t r) {}
1.103 + void reserveFront(size_t r) {front.reserve(r);}
1.104 +
1.105 + ///Reserve storage for the builder in advance.
1.106 +
1.107 + ///If you know a reasonable upper bound of the number of the edges
1.108 + ///to add to the back, using this function you can speed up the building.
1.109 +
1.110 + void reserveBack(size_t r) {back.reserve(r);}
1.111
1.112 private:
1.113 bool empty() {
1.114 @@ -382,7 +381,7 @@
1.115 //!
1.116 //! \param Graph The graph type in which the path is.
1.117 //! \param DM DebugMode, defaults to DefaultDebugMode.
1.118 - //!
1.119 + //!
1.120 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.121 //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.122 //! and \c Edge of the original graph.
1.123 @@ -495,12 +494,12 @@
1.124
1.125 /**
1.126 * \brief Iterator class to iterate on the edges of the paths
1.127 - *
1.128 + *
1.129 * \ingroup paths
1.130 * This class is used to iterate on the edges of the paths
1.131 *
1.132 * Of course it converts to Graph::Edge
1.133 - *
1.134 + *
1.135 * \todo Its interface differs from the standard edge iterator.
1.136 * Yes, it shouldn't.
1.137 */
1.138 @@ -543,12 +542,12 @@
1.139
1.140 /**
1.141 * \brief Iterator class to iterate on the nodes of the paths
1.142 - *
1.143 + *
1.144 * \ingroup paths
1.145 * This class is used to iterate on the nodes of the paths
1.146 *
1.147 * Of course it converts to Graph::Node
1.148 - *
1.149 + *
1.150 * \todo Its interface differs from the standard node iterator.
1.151 * Yes, it shouldn't.
1.152 */
1.153 @@ -592,11 +591,11 @@
1.154 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.155 };
1.156
1.157 - friend class Builder;
1.158 + friend class Builder;
1.159
1.160 /**
1.161 * \brief Class to build paths
1.162 - *
1.163 + *
1.164 * \ingroup paths
1.165 * This class is used to fill a path with edges.
1.166 *
1.167 @@ -620,7 +619,7 @@
1.168 Builder(UndirPath &_P) : P(_P) {}
1.169
1.170 /// Sets the starting node of the path.
1.171 -
1.172 +
1.173 /// Sets the starting node of the path. Edge added to the path
1.174 /// afterwards have to be incident to this node.
1.175 /// It should be called iff the path is empty and before any call to
1.176 @@ -657,20 +656,20 @@
1.177 }
1.178 }
1.179
1.180 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.181 - // Hogy kenyelmes egy ilyet hasznalni?
1.182
1.183 ///Reserve storage for the builder in advance.
1.184
1.185 - ///If you know an reasonable upper bound of the number of the edges
1.186 - ///to add, using this function you can speed up the building.
1.187 - void reserve(size_t r) {
1.188 - front.reserve(r);
1.189 - back.reserve(r);
1.190 - }
1.191 + ///If you know a reasonable upper bound of the number of the edges
1.192 + ///to add to the front, using this function you can speed up the building.
1.193
1.194 - void reserveFront(size_t r) {}
1.195 - void reserveBack(size_t r) {}
1.196 + void reserveFront(size_t r) {front.reserve(r);}
1.197 +
1.198 + ///Reserve storage for the builder in advance.
1.199 +
1.200 + ///If you know a reasonable upper bound of the number of the edges
1.201 + ///to add to the back, using this function you can speed up the building.
1.202 +
1.203 + void reserveBack(size_t r) {back.reserve(r);}
1.204
1.205 private:
1.206 bool empty() {
1.207 @@ -703,426 +702,6 @@
1.208 };
1.209
1.210
1.211 -
1.212 -
1.213 -
1.214 -
1.215 -
1.216 -
1.217 -
1.218 -
1.219 - /**********************************************************************/
1.220 -
1.221 -
1.222 - /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
1.223 - elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
1.224 -
1.225 - template<typename Graph>
1.226 - class DynamicPath {
1.227 -
1.228 - public:
1.229 - typedef typename Graph::Edge GraphEdge;
1.230 - typedef typename Graph::Node GraphNode;
1.231 - class NodeIt;
1.232 - class EdgeIt;
1.233 -
1.234 - protected:
1.235 - Graph& G;
1.236 - // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
1.237 - // iranyitasat:
1.238 - GraphNode _first, _last;
1.239 - typedef std::deque<GraphEdge> Container;
1.240 - Container edges;
1.241 -
1.242 - public:
1.243 -
1.244 - DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
1.245 -
1.246 - /// Subpath defined by two nodes.
1.247 - /// Nodes may be in reversed order, then
1.248 - /// we contstruct the reversed path.
1.249 - DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
1.250 - /// Subpath defined by two edges. Contains edges in [a,b)
1.251 - /// It is an error if the two edges are not in order!
1.252 - DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
1.253 -
1.254 - size_t length() const { return edges.size(); }
1.255 - GraphNode tail() const { return _first; }
1.256 - GraphNode head() const { return _last; }
1.257 -
1.258 - NodeIt& first(NodeIt &n) const { return nth(n, 0); }
1.259 - EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
1.260 - template<typename It>
1.261 - It first() const {
1.262 - It e;
1.263 - first(e);
1.264 - return e;
1.265 - }
1.266 -
1.267 - NodeIt& nth(NodeIt &, size_t) const;
1.268 - EdgeIt& nth(EdgeIt &, size_t) const;
1.269 - template<typename It>
1.270 - It nth(size_t n) const {
1.271 - It e;
1.272 - nth(e, n);
1.273 - return e;
1.274 - }
1.275 -
1.276 - bool valid(const NodeIt &n) const { return n.idx <= length(); }
1.277 - bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
1.278 -
1.279 - bool isForward(const EdgeIt &e) const { return e.forw; }
1.280 -
1.281 - /// index of a node on the path. Returns length+2 for the invalid NodeIt
1.282 - int index(const NodeIt &n) const { return n.idx; }
1.283 - /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
1.284 - int index(const EdgeIt &e) const { return e.it - edges.begin(); }
1.285 -
1.286 - EdgeIt& next(EdgeIt &e) const;
1.287 - NodeIt& next(NodeIt &n) const;
1.288 - template <typename It>
1.289 - It getNext(It it) const {
1.290 - It tmp(it); return next(tmp);
1.291 - }
1.292 -
1.293 - // A path is constructed using the following four functions.
1.294 - // They return false if the requested operation is inconsistent
1.295 - // with the path constructed so far.
1.296 - // If your path has only one edge you MUST set either "from" or "to"!
1.297 - // So you probably SHOULD call it in any case to be safe (and check the
1.298 - // returned value to check if your path is consistent with your idea).
1.299 - bool pushFront(const GraphEdge &e);
1.300 - bool pushBack(const GraphEdge &e);
1.301 - bool setFrom(const GraphNode &n);
1.302 - bool setTo(const GraphNode &n);
1.303 -
1.304 - // WARNING: these two functions return the head/tail of an edge with
1.305 - // respect to the direction of the path!
1.306 - // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
1.307 - // P.forward(e) is true (or the edge is a loop)!
1.308 - NodeIt head(const EdgeIt& e) const;
1.309 - NodeIt tail(const EdgeIt& e) const;
1.310 -
1.311 - // FIXME: ezeknek valami jobb nev kellene!!!
1.312 - GraphEdge graphEdge(const EdgeIt& e) const;
1.313 - GraphNode graphNode(const NodeIt& n) const;
1.314 -
1.315 -
1.316 - /*** Iterator classes ***/
1.317 - class EdgeIt {
1.318 - friend class DynamicPath;
1.319 -
1.320 - typename Container::const_iterator it;
1.321 - bool forw;
1.322 - public:
1.323 - // FIXME: jarna neki ilyen is...
1.324 - // EdgeIt(Invalid);
1.325 -
1.326 - bool forward() const { return forw; }
1.327 -
1.328 - bool operator==(const EdgeIt& e) const { return it==e.it; }
1.329 - bool operator!=(const EdgeIt& e) const { return it!=e.it; }
1.330 - bool operator<(const EdgeIt& e) const { return it<e.it; }
1.331 - };
1.332 -
1.333 - class NodeIt {
1.334 - friend class DynamicPath;
1.335 -
1.336 - size_t idx;
1.337 - bool tail; // Is this node the tail of the edge with same idx?
1.338 -
1.339 - public:
1.340 - // FIXME: jarna neki ilyen is...
1.341 - // NodeIt(Invalid);
1.342 -
1.343 - bool operator==(const NodeIt& n) const { return idx==n.idx; }
1.344 - bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
1.345 - bool operator<(const NodeIt& n) const { return idx<n.idx; }
1.346 - };
1.347 -
1.348 - private:
1.349 - bool edgeIncident(const GraphEdge &e, const GraphNode &a,
1.350 - GraphNode &b);
1.351 - bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
1.352 - };
1.353 -
1.354 - template<typename Gr>
1.355 - typename DynamicPath<Gr>::EdgeIt&
1.356 - DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
1.357 - if( e.it == edges.end() )
1.358 - return e;
1.359 -
1.360 - GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
1.361 - ++e.it;
1.362 -
1.363 - // Invalid edgeit is always forward :)
1.364 - if( e.it == edges.end() ) {
1.365 - e.forw = true;
1.366 - return e;
1.367 - }
1.368 -
1.369 - e.forw = ( G.tail(*e.it) == common_node );
1.370 - return e;
1.371 - }
1.372 -
1.373 - template<typename Gr>
1.374 - typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
1.375 - if( n.idx >= length() ) {
1.376 - // FIXME: invalid
1.377 - n.idx = length()+1;
1.378 - return n;
1.379 - }
1.380 -
1.381 -
1.382 - GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
1.383 - G.tail(edges[n.idx]) );
1.384 - ++n.idx;
1.385 - if( n.idx < length() ) {
1.386 - n.tail = ( next_node == G.tail(edges[n.idx]) );
1.387 - }
1.388 - else {
1.389 - n.tail = true;
1.390 - }
1.391 -
1.392 - return n;
1.393 - }
1.394 -
1.395 - template<typename Gr>
1.396 - bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
1.397 - GraphNode &b) {
1.398 - if( G.tail(e) == a ) {
1.399 - b=G.head(e);
1.400 - return true;
1.401 - }
1.402 - if( G.head(e) == a ) {
1.403 - b=G.tail(e);
1.404 - return true;
1.405 - }
1.406 - return false;
1.407 - }
1.408 -
1.409 - template<typename Gr>
1.410 - bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
1.411 - const GraphEdge &f) {
1.412 - if( edgeIncident(f, G.tail(e), _last) ) {
1.413 - _first = G.head(e);
1.414 - return true;
1.415 - }
1.416 - if( edgeIncident(f, G.head(e), _last) ) {
1.417 - _first = G.tail(e);
1.418 - return true;
1.419 - }
1.420 - return false;
1.421 - }
1.422 -
1.423 - template<typename Gr>
1.424 - bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
1.425 - if( G.valid(_first) ) {
1.426 - if( edgeIncident(e, _first, _first) ) {
1.427 - edges.push_front(e);
1.428 - return true;
1.429 - }
1.430 - else
1.431 - return false;
1.432 - }
1.433 - else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
1.434 - edges.push_front(e);
1.435 - return true;
1.436 - }
1.437 - else
1.438 - return false;
1.439 - }
1.440 -
1.441 - template<typename Gr>
1.442 - bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
1.443 - if( G.valid(_last) ) {
1.444 - if( edgeIncident(e, _last, _last) ) {
1.445 - edges.push_back(e);
1.446 - return true;
1.447 - }
1.448 - else
1.449 - return false;
1.450 - }
1.451 - else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
1.452 - edges.push_back(e);
1.453 - return true;
1.454 - }
1.455 - else
1.456 - return false;
1.457 - }
1.458 -
1.459 -
1.460 - template<typename Gr>
1.461 - bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1.462 - if( G.valid(_first) ) {
1.463 - return _first == n;
1.464 - }
1.465 - else {
1.466 - if( length() > 0) {
1.467 - if( edgeIncident(edges[0], n, _last) ) {
1.468 - _first = n;
1.469 - return true;
1.470 - }
1.471 - else return false;
1.472 - }
1.473 - else {
1.474 - _first = _last = n;
1.475 - return true;
1.476 - }
1.477 - }
1.478 - }
1.479 -
1.480 - template<typename Gr>
1.481 - bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1.482 - if( G.valid(_last) ) {
1.483 - return _last == n;
1.484 - }
1.485 - else {
1.486 - if( length() > 0) {
1.487 - if( edgeIncident(edges[0], n, _first) ) {
1.488 - _last = n;
1.489 - return true;
1.490 - }
1.491 - else return false;
1.492 - }
1.493 - else {
1.494 - _first = _last = n;
1.495 - return true;
1.496 - }
1.497 - }
1.498 - }
1.499 -
1.500 -
1.501 - template<typename Gr>
1.502 - typename DynamicPath<Gr>::NodeIt
1.503 - DynamicPath<Gr>::tail(const EdgeIt& e) const {
1.504 - NodeIt n;
1.505 -
1.506 - if( e.it == edges.end() ) {
1.507 - // FIXME: invalid-> invalid
1.508 - n.idx = length() + 1;
1.509 - n.tail = true;
1.510 - return n;
1.511 - }
1.512 -
1.513 - n.idx = e.it-edges.begin();
1.514 - n.tail = e.forw;
1.515 - return n;
1.516 - }
1.517 -
1.518 - template<typename Gr>
1.519 - typename DynamicPath<Gr>::NodeIt
1.520 - DynamicPath<Gr>::head(const EdgeIt& e) const {
1.521 - if( e.it == edges.end()-1 ) {
1.522 - return _last;
1.523 - }
1.524 -
1.525 - EdgeIt next_edge = e;
1.526 - next(next_edge);
1.527 - return tail(next_edge);
1.528 - }
1.529 -
1.530 - template<typename Gr>
1.531 - typename DynamicPath<Gr>::GraphEdge
1.532 - DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1.533 - if( e.it != edges.end() ) {
1.534 - return *e.it;
1.535 - }
1.536 - else {
1.537 - return INVALID;
1.538 - }
1.539 - }
1.540 -
1.541 - template<typename Gr>
1.542 - typename DynamicPath<Gr>::GraphNode
1.543 - DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1.544 - if( n.idx < length() ) {
1.545 - return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1.546 - }
1.547 - else if( n.idx == length() ) {
1.548 - return _last;
1.549 - }
1.550 - else {
1.551 - return INVALID;
1.552 - }
1.553 - }
1.554 -
1.555 - template<typename Gr>
1.556 - typename DynamicPath<Gr>::EdgeIt&
1.557 - DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1.558 - if( k>=length() ) {
1.559 - // FIXME: invalid EdgeIt
1.560 - e.it = edges.end();
1.561 - e.forw = true;
1.562 - return e;
1.563 - }
1.564 -
1.565 - e.it = edges.begin()+k;
1.566 - if(k==0) {
1.567 - e.forw = ( G.tail(*e.it) == _first );
1.568 - }
1.569 - else {
1.570 - e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1.571 - G.tail(*e.it) == G.head(edges[k-1]) );
1.572 - }
1.573 - return e;
1.574 - }
1.575 -
1.576 - template<typename Gr>
1.577 - typename DynamicPath<Gr>::NodeIt&
1.578 - DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1.579 - if( k>length() ) {
1.580 - // FIXME: invalid NodeIt
1.581 - n.idx = length()+1;
1.582 - n.tail = true;
1.583 - return n;
1.584 - }
1.585 - if( k==length() ) {
1.586 - n.idx = length();
1.587 - n.tail = true;
1.588 - return n;
1.589 - }
1.590 - n = tail(nth<EdgeIt>(k));
1.591 - return n;
1.592 - }
1.593 -
1.594 - // Reszut konstruktorok:
1.595 -
1.596 -
1.597 - template<typename Gr>
1.598 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1.599 - const EdgeIt &b) :
1.600 - G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1.601 - {
1.602 - if( G.valid(P._first) && a.it < P.edges.end() ) {
1.603 - _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1.604 - if( b.it < P.edges.end() ) {
1.605 - _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1.606 - }
1.607 - else {
1.608 - _last = P._last;
1.609 - }
1.610 - }
1.611 - }
1.612 -
1.613 - template<typename Gr>
1.614 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1.615 - const NodeIt &b) : G(P.G)
1.616 - {
1.617 - if( !P.valid(a) || !P.valid(b) )
1.618 - return;
1.619 -
1.620 - int ai = a.idx, bi = b.idx;
1.621 - if( bi<ai )
1.622 - std::swap(ai,bi);
1.623 -
1.624 - edges.resize(bi-ai);
1.625 - copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1.626 -
1.627 - _first = P.graphNode(a);
1.628 - _last = P.graphNode(b);
1.629 - }
1.630 -
1.631 ///@}
1.632
1.633 } // namespace hugo