1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/path.h Tue Jun 15 06:29:27 2004 +0000
1.3 @@ -0,0 +1,748 @@
1.4 +// -*- c++ -*- //
1.5 +
1.6 +/**
1.7 +@defgroup paths Path Structures
1.8 +@ingroup datas
1.9 +\brief Path structures implemented in Hugo.
1.10 +
1.11 +Hugolib provides flexible data structures
1.12 +to work with paths.
1.13 +
1.14 +All of them have the same interface, especially they can be built or extended
1.15 +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
1.16 +algorithm to store its result in any kind of path structure.
1.17 +
1.18 +*/
1.19 +
1.20 +///\ingroup paths
1.21 +///\file
1.22 +///\brief Classes for representing paths in graphs.
1.23 +
1.24 +#ifndef HUGO_PATH_H
1.25 +#define HUGO_PATH_H
1.26 +
1.27 +#include <deque>
1.28 +#include <vector>
1.29 +#include <algorithm>
1.30 +
1.31 +#include <hugo/invalid.h>
1.32 +#include <hugo/error.h>
1.33 +#include <debug.h>
1.34 +
1.35 +namespace hugo {
1.36 +
1.37 + /// \addtogroup paths
1.38 + /// @{
1.39 +
1.40 +
1.41 + //! \brief A structure for representing directed path in a graph.
1.42 + //!
1.43 + //! A structure for representing directed path in a graph.
1.44 + //! \param Graph The graph type in which the path is.
1.45 + //! \param DM DebugMode, defaults to DefaultDebugMode.
1.46 + //!
1.47 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.48 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.49 + //! and \c Edge of the original graph.
1.50 + //!
1.51 + //! \todo Thoroughfully check all the range and consistency tests.
1.52 + template<typename Graph, typename DM = DefaultDebugMode>
1.53 + class DirPath {
1.54 + public:
1.55 + /// Edge type of the underlying graph.
1.56 + typedef typename Graph::Edge GraphEdge;
1.57 + /// Node type of the underlying graph.
1.58 + typedef typename Graph::Node GraphNode;
1.59 + class NodeIt;
1.60 + class EdgeIt;
1.61 +
1.62 + protected:
1.63 + const Graph *gr;
1.64 + typedef std::vector<GraphEdge> Container;
1.65 + Container edges;
1.66 +
1.67 + public:
1.68 +
1.69 + /// \param _G The graph in which the path is.
1.70 + ///
1.71 + DirPath(const Graph &_G) : gr(&_G) {}
1.72 +
1.73 + /// \brief Subpath constructor.
1.74 + ///
1.75 + /// Subpath defined by two nodes.
1.76 + /// \warning It is an error if the two edges are not in order!
1.77 + DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.78 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.79 + // FIXME: this check should be more elaborate...
1.80 + fault("DirPath, subpath ctor: invalid bounding nodes");
1.81 + }
1.82 + gr = P.gr;
1.83 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.84 + }
1.85 +
1.86 + /// \brief Subpath constructor.
1.87 + ///
1.88 + /// Subpath defined by two edges. Contains edges in [a,b)
1.89 + /// \warning It is an error if the two edges are not in order!
1.90 + DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.91 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.92 + // FIXME: this check should be more elaborate...
1.93 + fault("DirPath, subpath ctor: invalid bounding nodes");
1.94 + }
1.95 + gr = P.gr;
1.96 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.97 + }
1.98 +
1.99 + /// Length of the path.
1.100 + size_t length() const { return edges.size(); }
1.101 + /// Returns whether the path is empty.
1.102 + bool empty() const { return edges.empty(); }
1.103 +
1.104 + /// Resets the path to an empty path.
1.105 + void clear() { edges.clear(); }
1.106 +
1.107 + /// \brief Starting point of the path.
1.108 + ///
1.109 + /// Starting point of the path.
1.110 + /// Returns INVALID if the path is empty.
1.111 + GraphNode from() const {
1.112 + return empty() ? INVALID : gr->tail(edges[0]);
1.113 + }
1.114 + /// \brief End point of the path.
1.115 + ///
1.116 + /// End point of the path.
1.117 + /// Returns INVALID if the path is empty.
1.118 + GraphNode to() const {
1.119 + return empty() ? INVALID : gr->head(edges[length()-1]);
1.120 + }
1.121 +
1.122 + /// \brief Initializes node or edge iterator to point to the first
1.123 + /// node or edge.
1.124 + ///
1.125 + /// \sa nth
1.126 + template<typename It>
1.127 + It& first(It &i) const { return i=It(*this); }
1.128 +
1.129 + /// \brief Initializes node iterator to point to the node of a given index.
1.130 + NodeIt& nth(NodeIt &i, int n) const {
1.131 + if( DM::range_check && (n<0 || n>int(length())) )
1.132 + fault("DirPath::nth: index out of range");
1.133 + return i=NodeIt(*this, n);
1.134 + }
1.135 +
1.136 + /// \brief Initializes edge iterator to point to the edge of a given index.
1.137 + EdgeIt& nth(EdgeIt &i, int n) const {
1.138 + if( DM::range_check && (n<0 || n>=int(length())) )
1.139 + fault("DirPath::nth: index out of range");
1.140 + return i=EdgeIt(*this, n);
1.141 + }
1.142 +
1.143 + /// Checks validity of a node or edge iterator.
1.144 + template<typename It>
1.145 + static
1.146 + bool valid(const It &i) { return i.valid(); }
1.147 +
1.148 + /// Steps the given node or edge iterator.
1.149 + template<typename It>
1.150 + static
1.151 + It& next(It &e) {
1.152 + if( DM::range_check && !e.valid() )
1.153 + fault("DirPath::next() on invalid iterator");
1.154 + return ++e;
1.155 + }
1.156 +
1.157 + /// \brief Returns node iterator pointing to the head node of the
1.158 + /// given edge iterator.
1.159 + NodeIt head(const EdgeIt& e) const {
1.160 + if( DM::range_check && !e.valid() )
1.161 + fault("DirPath::head() on invalid iterator");
1.162 + return NodeIt(*this, e.idx+1);
1.163 + }
1.164 +
1.165 + /// \brief Returns node iterator pointing to the tail node of the
1.166 + /// given edge iterator.
1.167 + NodeIt tail(const EdgeIt& e) const {
1.168 + if( DM::range_check && !e.valid() )
1.169 + fault("DirPath::tail() on invalid iterator");
1.170 + return NodeIt(*this, e.idx);
1.171 + }
1.172 +
1.173 +
1.174 + /* Iterator classes */
1.175 +
1.176 + /**
1.177 + * \brief Iterator class to iterate on the edges of the paths
1.178 + *
1.179 + * \ingroup paths
1.180 + * This class is used to iterate on the edges of the paths
1.181 + *
1.182 + * Of course it converts to Graph::Edge
1.183 + *
1.184 + * \todo Its interface differs from the standard edge iterator.
1.185 + * Yes, it shouldn't.
1.186 + */
1.187 + class EdgeIt {
1.188 + friend class DirPath;
1.189 +
1.190 + int idx;
1.191 + const DirPath *p;
1.192 + public:
1.193 + /// Default constructor
1.194 + EdgeIt() {}
1.195 + /// Invalid constructor
1.196 + EdgeIt(Invalid) : idx(-1), p(0) {}
1.197 + /// Constructor with starting point
1.198 + EdgeIt(const DirPath &_p, int _idx = 0) :
1.199 + idx(_idx), p(&_p) { validate(); }
1.200 +
1.201 + ///Validity check
1.202 + bool valid() const { return idx!=-1; }
1.203 +
1.204 + ///Conversion to Graph::Edge
1.205 + operator GraphEdge () const {
1.206 + return valid() ? p->edges[idx] : INVALID;
1.207 + }
1.208 +
1.209 + /// Next edge
1.210 + EdgeIt& operator++() { ++idx; validate(); return *this; }
1.211 +
1.212 + /// Comparison operator
1.213 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.214 + /// Comparison operator
1.215 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.216 + /// Comparison operator
1.217 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.218 +
1.219 + private:
1.220 + // FIXME: comparison between signed and unsigned...
1.221 + // Jo ez igy? Vagy esetleg legyen a length() int?
1.222 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.223 + };
1.224 +
1.225 + /**
1.226 + * \brief Iterator class to iterate on the nodes of the paths
1.227 + *
1.228 + * \ingroup paths
1.229 + * This class is used to iterate on the nodes of the paths
1.230 + *
1.231 + * Of course it converts to Graph::Node
1.232 + *
1.233 + * \todo Its interface differs from the standard node iterator.
1.234 + * Yes, it shouldn't.
1.235 + */
1.236 + class NodeIt {
1.237 + friend class DirPath;
1.238 +
1.239 + int idx;
1.240 + const DirPath *p;
1.241 + public:
1.242 + /// Default constructor
1.243 + NodeIt() {}
1.244 + /// Invalid constructor
1.245 + NodeIt(Invalid) : idx(-1), p(0) {}
1.246 + /// Constructor with starting point
1.247 + NodeIt(const DirPath &_p, int _idx = 0) :
1.248 + idx(_idx), p(&_p) { validate(); }
1.249 +
1.250 + ///Validity check
1.251 + bool valid() const { return idx!=-1; }
1.252 +
1.253 + ///Conversion to Graph::Node
1.254 + operator const GraphNode& () const {
1.255 + if(idx >= p->length())
1.256 + return p->to();
1.257 + else if(idx >= 0)
1.258 + return p->gr->tail(p->edges[idx]);
1.259 + else
1.260 + return INVALID;
1.261 + }
1.262 + /// Next node
1.263 + NodeIt& operator++() { ++idx; validate(); return *this; }
1.264 +
1.265 + /// Comparison operator
1.266 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.267 + /// Comparison operator
1.268 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.269 + /// Comparison operator
1.270 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.271 +
1.272 + private:
1.273 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.274 + };
1.275 +
1.276 + friend class Builder;
1.277 +
1.278 + /**
1.279 + * \brief Class to build paths
1.280 + *
1.281 + * \ingroup paths
1.282 + * This class is used to fill a path with edges.
1.283 + *
1.284 + * You can push new edges to the front and to the back of the path in
1.285 + * arbitrary order then you should commit these changes to the graph.
1.286 + *
1.287 + * Fundamentally, for most "Paths" (classes fulfilling the
1.288 + * PathConcept) while the builder is active (after the first modifying
1.289 + * operation and until the commit()) the original Path is in a
1.290 + * "transitional" state (operations on it have undefined result). But
1.291 + * in the case of DirPath the original path remains unchanged until the
1.292 + * commit. However we don't recomend that you use this feature.
1.293 + */
1.294 + class Builder {
1.295 + DirPath &P;
1.296 + Container front, back;
1.297 +
1.298 + public:
1.299 + ///\param _P the path you want to fill in.
1.300 + ///
1.301 + Builder(DirPath &_P) : P(_P) {}
1.302 +
1.303 + /// Sets the starting node of the path.
1.304 +
1.305 + /// Sets the starting node of the path. Edge added to the path
1.306 + /// afterwards have to be incident to this node.
1.307 + /// It should be called iff the path is empty and before any call to
1.308 + /// \ref pushFront() or \ref pushBack()
1.309 + void setStart(const GraphNode &) {}
1.310 +
1.311 + ///Push a new edge to the front of the path
1.312 +
1.313 + ///Push a new edge to the front of the path.
1.314 + ///\sa setStart
1.315 + void pushFront(const GraphEdge& e) {
1.316 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.317 + fault("DirPath::Builder::pushFront: nonincident edge");
1.318 + }
1.319 + front.push_back(e);
1.320 + }
1.321 +
1.322 + ///Push a new edge to the back of the path
1.323 +
1.324 + ///Push a new edge to the back of the path.
1.325 + ///\sa setStart
1.326 + void pushBack(const GraphEdge& e) {
1.327 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.328 + fault("DirPath::Builder::pushBack: nonincident edge");
1.329 + }
1.330 + back.push_back(e);
1.331 + }
1.332 +
1.333 + ///Commit the changes to the path.
1.334 + void commit() {
1.335 + if( !(front.empty() && back.empty()) ) {
1.336 + Container tmp;
1.337 + tmp.reserve(front.size()+back.size()+P.length());
1.338 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.339 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.340 + tmp.insert(tmp.end(), back.begin(), back.end());
1.341 + P.edges.swap(tmp);
1.342 + front.clear();
1.343 + back.clear();
1.344 + }
1.345 + }
1.346 +
1.347 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.348 + // Hogy kenyelmes egy ilyet hasznalni?
1.349 +
1.350 + ///Reserve storage in advance for the builder
1.351 +
1.352 + ///If you know an reasonable upper bound of the number of the edges
1.353 + ///to add, using this function you can speed up the building.
1.354 + void reserve(size_t r) {
1.355 + front.reserve(r);
1.356 + back.reserve(r);
1.357 + }
1.358 +
1.359 + private:
1.360 + bool empty() {
1.361 + return front.empty() && back.empty() && P.empty();
1.362 + }
1.363 +
1.364 + GraphNode from() const {
1.365 + if( ! front.empty() )
1.366 + return P.gr->tail(front[front.size()-1]);
1.367 + else if( ! P.empty() )
1.368 + return P.gr->tail(P.edges[0]);
1.369 + else if( ! back.empty() )
1.370 + return P.gr->tail(back[0]);
1.371 + else
1.372 + return INVALID;
1.373 + }
1.374 + GraphNode to() const {
1.375 + if( ! back.empty() )
1.376 + return P.gr->head(back[back.size()-1]);
1.377 + else if( ! P.empty() )
1.378 + return P.gr->head(P.edges[P.length()-1]);
1.379 + else if( ! front.empty() )
1.380 + return P.gr->head(front[0]);
1.381 + else
1.382 + return INVALID;
1.383 + }
1.384 +
1.385 + };
1.386 +
1.387 + };
1.388 +
1.389 +
1.390 +
1.391 +
1.392 +
1.393 +
1.394 + /**********************************************************************/
1.395 +
1.396 +
1.397 + //! \brief A structure for representing undirected path in a graph.
1.398 + //!
1.399 + //! A structure for representing undirected path in a graph. Ie. this is
1.400 + //! a path in a \e directed graph but the edges should not be directed
1.401 + //! forward.
1.402 + //!
1.403 + //! \param Graph The graph type in which the path is.
1.404 + //! \param DM DebugMode, defaults to DefaultDebugMode.
1.405 + //!
1.406 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.407 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.408 + //! and \c Edge of the original graph.
1.409 + //!
1.410 + //! \todo Thoroughfully check all the range and consistency tests.
1.411 + template<typename Graph, typename DM = DefaultDebugMode>
1.412 + class UndirPath {
1.413 + public:
1.414 + /// Edge type of the underlying graph.
1.415 + typedef typename Graph::Edge GraphEdge;
1.416 + /// Node type of the underlying graph.
1.417 + typedef typename Graph::Node GraphNode;
1.418 + class NodeIt;
1.419 + class EdgeIt;
1.420 +
1.421 + protected:
1.422 + const Graph *gr;
1.423 + typedef std::vector<GraphEdge> Container;
1.424 + Container edges;
1.425 +
1.426 + public:
1.427 +
1.428 + /// \param _G The graph in which the path is.
1.429 + ///
1.430 + UndirPath(const Graph &_G) : gr(&_G) {}
1.431 +
1.432 + /// \brief Subpath constructor.
1.433 + ///
1.434 + /// Subpath defined by two nodes.
1.435 + /// \warning It is an error if the two edges are not in order!
1.436 + UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.437 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.438 + // FIXME: this check should be more elaborate...
1.439 + fault("UndirPath, subpath ctor: invalid bounding nodes");
1.440 + }
1.441 + gr = P.gr;
1.442 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.443 + }
1.444 +
1.445 + /// \brief Subpath constructor.
1.446 + ///
1.447 + /// Subpath defined by two edges. Contains edges in [a,b)
1.448 + /// \warning It is an error if the two edges are not in order!
1.449 + UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.450 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.451 + // FIXME: this check should be more elaborate...
1.452 + fault("UndirPath, subpath ctor: invalid bounding nodes");
1.453 + }
1.454 + gr = P.gr;
1.455 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.456 + }
1.457 +
1.458 + /// Length of the path.
1.459 + size_t length() const { return edges.size(); }
1.460 + /// Returns whether the path is empty.
1.461 + bool empty() const { return edges.empty(); }
1.462 +
1.463 + /// Resets the path to an empty path.
1.464 + void clear() { edges.clear(); }
1.465 +
1.466 + /// \brief Starting point of the path.
1.467 + ///
1.468 + /// Starting point of the path.
1.469 + /// Returns INVALID if the path is empty.
1.470 + GraphNode from() const {
1.471 + return empty() ? INVALID : gr->tail(edges[0]);
1.472 + }
1.473 + /// \brief End point of the path.
1.474 + ///
1.475 + /// End point of the path.
1.476 + /// Returns INVALID if the path is empty.
1.477 + GraphNode to() const {
1.478 + return empty() ? INVALID : gr->head(edges[length()-1]);
1.479 + }
1.480 +
1.481 + /// \brief Initializes node or edge iterator to point to the first
1.482 + /// node or edge.
1.483 + ///
1.484 + /// \sa nth
1.485 + template<typename It>
1.486 + It& first(It &i) const { return i=It(*this); }
1.487 +
1.488 + /// \brief Initializes node iterator to point to the node of a given index.
1.489 + NodeIt& nth(NodeIt &i, int n) const {
1.490 + if( DM::range_check && (n<0 || n>int(length())) )
1.491 + fault("UndirPath::nth: index out of range");
1.492 + return i=NodeIt(*this, n);
1.493 + }
1.494 +
1.495 + /// \brief Initializes edge iterator to point to the edge of a given index.
1.496 + EdgeIt& nth(EdgeIt &i, int n) const {
1.497 + if( DM::range_check && (n<0 || n>=int(length())) )
1.498 + fault("UndirPath::nth: index out of range");
1.499 + return i=EdgeIt(*this, n);
1.500 + }
1.501 +
1.502 + /// Checks validity of a node or edge iterator.
1.503 + template<typename It>
1.504 + static
1.505 + bool valid(const It &i) { return i.valid(); }
1.506 +
1.507 + /// Steps the given node or edge iterator.
1.508 + template<typename It>
1.509 + static
1.510 + It& next(It &e) {
1.511 + if( DM::range_check && !e.valid() )
1.512 + fault("UndirPath::next() on invalid iterator");
1.513 + return ++e;
1.514 + }
1.515 +
1.516 + /// \brief Returns node iterator pointing to the head node of the
1.517 + /// given edge iterator.
1.518 + NodeIt head(const EdgeIt& e) const {
1.519 + if( DM::range_check && !e.valid() )
1.520 + fault("UndirPath::head() on invalid iterator");
1.521 + return NodeIt(*this, e.idx+1);
1.522 + }
1.523 +
1.524 + /// \brief Returns node iterator pointing to the tail node of the
1.525 + /// given edge iterator.
1.526 + NodeIt tail(const EdgeIt& e) const {
1.527 + if( DM::range_check && !e.valid() )
1.528 + fault("UndirPath::tail() on invalid iterator");
1.529 + return NodeIt(*this, e.idx);
1.530 + }
1.531 +
1.532 +
1.533 +
1.534 + /**
1.535 + * \brief Iterator class to iterate on the edges of the paths
1.536 + *
1.537 + * \ingroup paths
1.538 + * This class is used to iterate on the edges of the paths
1.539 + *
1.540 + * Of course it converts to Graph::Edge
1.541 + *
1.542 + * \todo Its interface differs from the standard edge iterator.
1.543 + * Yes, it shouldn't.
1.544 + */
1.545 + class EdgeIt {
1.546 + friend class UndirPath;
1.547 +
1.548 + int idx;
1.549 + const UndirPath *p;
1.550 + public:
1.551 + /// Default constructor
1.552 + EdgeIt() {}
1.553 + /// Invalid constructor
1.554 + EdgeIt(Invalid) : idx(-1), p(0) {}
1.555 + /// Constructor with starting point
1.556 + EdgeIt(const UndirPath &_p, int _idx = 0) :
1.557 + idx(_idx), p(&_p) { validate(); }
1.558 +
1.559 + ///Validity check
1.560 + bool valid() const { return idx!=-1; }
1.561 +
1.562 + ///Conversion to Graph::Edge
1.563 + operator GraphEdge () const {
1.564 + return valid() ? p->edges[idx] : INVALID;
1.565 + }
1.566 + /// Next edge
1.567 + EdgeIt& operator++() { ++idx; validate(); return *this; }
1.568 +
1.569 + /// Comparison operator
1.570 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.571 + /// Comparison operator
1.572 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.573 + /// Comparison operator
1.574 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.575 +
1.576 + private:
1.577 + // FIXME: comparison between signed and unsigned...
1.578 + // Jo ez igy? Vagy esetleg legyen a length() int?
1.579 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.580 + };
1.581 +
1.582 + /**
1.583 + * \brief Iterator class to iterate on the nodes of the paths
1.584 + *
1.585 + * \ingroup paths
1.586 + * This class is used to iterate on the nodes of the paths
1.587 + *
1.588 + * Of course it converts to Graph::Node
1.589 + *
1.590 + * \todo Its interface differs from the standard node iterator.
1.591 + * Yes, it shouldn't.
1.592 + */
1.593 + class NodeIt {
1.594 + friend class UndirPath;
1.595 +
1.596 + int idx;
1.597 + const UndirPath *p;
1.598 + public:
1.599 + /// Default constructor
1.600 + NodeIt() {}
1.601 + /// Invalid constructor
1.602 + NodeIt(Invalid) : idx(-1), p(0) {}
1.603 + /// Constructor with starting point
1.604 + NodeIt(const UndirPath &_p, int _idx = 0) :
1.605 + idx(_idx), p(&_p) { validate(); }
1.606 +
1.607 + ///Validity check
1.608 + bool valid() const { return idx!=-1; }
1.609 +
1.610 + ///Conversion to Graph::Node
1.611 + operator const GraphNode& () const {
1.612 + if(idx >= p->length())
1.613 + return p->to();
1.614 + else if(idx >= 0)
1.615 + return p->gr->tail(p->edges[idx]);
1.616 + else
1.617 + return INVALID;
1.618 + }
1.619 + /// Next node
1.620 + NodeIt& operator++() { ++idx; validate(); return *this; }
1.621 +
1.622 + /// Comparison operator
1.623 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.624 + /// Comparison operator
1.625 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.626 + /// Comparison operator
1.627 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.628 +
1.629 + private:
1.630 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.631 + };
1.632 +
1.633 + friend class Builder;
1.634 +
1.635 + /**
1.636 + * \brief Class to build paths
1.637 + *
1.638 + * \ingroup paths
1.639 + * This class is used to fill a path with edges.
1.640 + *
1.641 + * You can push new edges to the front and to the back of the path in
1.642 + * arbitrary order then you should commit these changes to the graph.
1.643 + *
1.644 + * Fundamentally, for most "Paths" (classes fulfilling the
1.645 + * PathConcept) while the builder is active (after the first modifying
1.646 + * operation and until the commit()) the original Path is in a
1.647 + * "transitional" state (operations ot it have undefined result). But
1.648 + * in the case of UndirPath the original path is unchanged until the
1.649 + * commit. However we don't recomend that you use this feature.
1.650 + */
1.651 + class Builder {
1.652 + UndirPath &P;
1.653 + Container front, back;
1.654 +
1.655 + public:
1.656 + ///\param _P the path you want to fill in.
1.657 + ///
1.658 + Builder(UndirPath &_P) : P(_P) {}
1.659 +
1.660 + /// Sets the starting node of the path.
1.661 +
1.662 + /// Sets the starting node of the path. Edge added to the path
1.663 + /// afterwards have to be incident to this node.
1.664 + /// It should be called iff the path is empty and before any call to
1.665 + /// \ref pushFront() or \ref pushBack()
1.666 + void setStart(const GraphNode &) {}
1.667 +
1.668 + ///Push a new edge to the front of the path
1.669 +
1.670 + ///Push a new edge to the front of the path.
1.671 + ///\sa setStart
1.672 + void pushFront(const GraphEdge& e) {
1.673 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.674 + fault("UndirPath::Builder::pushFront: nonincident edge");
1.675 + }
1.676 + front.push_back(e);
1.677 + }
1.678 +
1.679 + ///Push a new edge to the back of the path
1.680 +
1.681 + ///Push a new edge to the back of the path.
1.682 + ///\sa setStart
1.683 + void pushBack(const GraphEdge& e) {
1.684 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.685 + fault("UndirPath::Builder::pushBack: nonincident edge");
1.686 + }
1.687 + back.push_back(e);
1.688 + }
1.689 +
1.690 + ///Commit the changes to the path.
1.691 + void commit() {
1.692 + if( !(front.empty() && back.empty()) ) {
1.693 + Container tmp;
1.694 + tmp.reserve(front.size()+back.size()+P.length());
1.695 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.696 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.697 + tmp.insert(tmp.end(), back.begin(), back.end());
1.698 + P.edges.swap(tmp);
1.699 + front.clear();
1.700 + back.clear();
1.701 + }
1.702 + }
1.703 +
1.704 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.705 + // Hogy kenyelmes egy ilyet hasznalni?
1.706 +
1.707 + ///Reserve storage in advance for the builder
1.708 +
1.709 + ///If you know an reasonable upper bound of the number of the edges
1.710 + ///to add, using this function you can speed up the building.
1.711 + void reserve(size_t r) {
1.712 + front.reserve(r);
1.713 + back.reserve(r);
1.714 + }
1.715 +
1.716 + private:
1.717 + bool empty() {
1.718 + return front.empty() && back.empty() && P.empty();
1.719 + }
1.720 +
1.721 + GraphNode from() const {
1.722 + if( ! front.empty() )
1.723 + return P.gr->tail(front[front.size()-1]);
1.724 + else if( ! P.empty() )
1.725 + return P.gr->tail(P.edges[0]);
1.726 + else if( ! back.empty() )
1.727 + return P.gr->tail(back[0]);
1.728 + else
1.729 + return INVALID;
1.730 + }
1.731 + GraphNode to() const {
1.732 + if( ! back.empty() )
1.733 + return P.gr->head(back[back.size()-1]);
1.734 + else if( ! P.empty() )
1.735 + return P.gr->head(P.edges[P.length()-1]);
1.736 + else if( ! front.empty() )
1.737 + return P.gr->head(front[0]);
1.738 + else
1.739 + return INVALID;
1.740 + }
1.741 +
1.742 + };
1.743 +
1.744 + };
1.745 +
1.746 +
1.747 + ///@}
1.748 +
1.749 +} // namespace hugo
1.750 +
1.751 +#endif // HUGO_PATH_H