1.1 --- a/src/work/klao/path.h Tue May 11 22:49:13 2004 +0000
1.2 +++ b/src/work/klao/path.h Tue May 11 22:50:09 2004 +0000
1.3 @@ -23,6 +23,7 @@
1.4
1.5 //! \brief A structure for representing directed path in a graph.
1.6 //!
1.7 + //! A structure for representing directed path in a graph.
1.8 //! \param Graph The graph type in which the path is.
1.9 //! \param DM DebugMode, defaults to DefaultDebugMode.
1.10 //!
1.11 @@ -54,14 +55,27 @@
1.12 ///
1.13 /// Subpath defined by two nodes.
1.14 /// \warning It is an error if the two edges are not in order!
1.15 - /// \todo Implement!
1.16 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
1.17 + DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.18 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.19 + // FIXME: this check should be more elaborate...
1.20 + fault("DirPath, subpath ctor: invalid bounding nodes");
1.21 + }
1.22 + gr = P.gr;
1.23 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.24 + }
1.25 +
1.26 /// \brief Subpath constructor.
1.27 ///
1.28 /// Subpath defined by two edges. Contains edges in [a,b)
1.29 /// \warning It is an error if the two edges are not in order!
1.30 - /// \todo Implement!
1.31 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
1.32 + DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.33 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.34 + // FIXME: this check should be more elaborate...
1.35 + fault("DirPath, subpath ctor: invalid bounding nodes");
1.36 + }
1.37 + gr = P.gr;
1.38 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.39 + }
1.40
1.41 /// Length of the path.
1.42 size_t length() const { return edges.size(); }
1.43 @@ -93,23 +107,29 @@
1.44 template<typename It>
1.45 It& first(It &i) const { return i=It(*this); }
1.46
1.47 - /// \brief Initializes node or edge iterator to point to the node or edge
1.48 - /// of a given index.
1.49 - template<typename It>
1.50 - It& nth(It &i, int n) const {
1.51 - // FIXME: this test should be different for NodeIt and EdgeIt:
1.52 + /// \brief Initializes node iterator to point to the node of a given index.
1.53 + NodeIt& nth(NodeIt &i, int n) const {
1.54 if( DM::range_check && (n<0 || n>int(length())) )
1.55 fault("DirPath::nth: index out of range");
1.56 - return i=It(*this, n);
1.57 + return i=NodeIt(*this, n);
1.58 + }
1.59 +
1.60 + /// \brief Initializes edge iterator to point to the edge of a given index.
1.61 + EdgeIt& nth(EdgeIt &i, int n) const {
1.62 + if( DM::range_check && (n<0 || n>=int(length())) )
1.63 + fault("DirPath::nth: index out of range");
1.64 + return i=EdgeIt(*this, n);
1.65 }
1.66
1.67 /// Checks validity of a node or edge iterator.
1.68 template<typename It>
1.69 - bool valid(const It &i) const { return i.valid(); }
1.70 + static
1.71 + bool valid(const It &i) { return i.valid(); }
1.72
1.73 /// Steps the given node or edge iterator.
1.74 template<typename It>
1.75 - It& next(It &e) const {
1.76 + static
1.77 + It& next(It &e) {
1.78 if( DM::range_check && !e.valid() )
1.79 fault("DirPath::next() on invalid iterator");
1.80 return ++e;
1.81 @@ -118,12 +138,16 @@
1.82 /// \brief Returns node iterator pointing to the head node of the
1.83 /// given edge iterator.
1.84 NodeIt head(const EdgeIt& e) const {
1.85 + if( DM::range_check && !e.valid() )
1.86 + fault("DirPath::head() on invalid iterator");
1.87 return NodeIt(*this, e.idx+1);
1.88 }
1.89
1.90 /// \brief Returns node iterator pointing to the tail node of the
1.91 /// given edge iterator.
1.92 NodeIt tail(const EdgeIt& e) const {
1.93 + if( DM::range_check && !e.valid() )
1.94 + fault("DirPath::tail() on invalid iterator");
1.95 return NodeIt(*this, e.idx);
1.96 }
1.97
1.98 @@ -170,7 +194,7 @@
1.99
1.100 bool valid() const { return idx!=-1; }
1.101
1.102 - operator const GraphEdge& () const {
1.103 + operator const GraphNode& () const {
1.104 if(idx >= p->length())
1.105 return p->to();
1.106 else if(idx >= 0)
1.107 @@ -197,7 +221,7 @@
1.108 * This class is used to fill a path with edges.
1.109 *
1.110 * You can push new edges to the front and to the back of the path in
1.111 - * arbitrary order the you can commit these changes to the graph.
1.112 + * arbitrary order then you should commit these changes to the graph.
1.113 *
1.114 * Fundamentally, for most "Paths" (classes fulfilling the
1.115 * PathConcept) while the builder is active (after the first modifying
1.116 @@ -215,24 +239,18 @@
1.117 ///
1.118 Builder(DirPath &_P) : P(_P) {}
1.119
1.120 - ///Sets the first node of the path.
1.121 + /// Sets the starting node of the path.
1.122
1.123 - ///Sets the first node of the path. If the path is empty, this
1.124 - ///function or setTo() have to be called before any call to \ref
1.125 - ///pushFront() or \ref pushBack()
1.126 - void setFrom(const GraphNode &) {}
1.127 -
1.128 - ///Sets the last node of the path.
1.129 -
1.130 - ///Sets the last node of the path. If the path is empty, this
1.131 - ///function or setFrom() have to be called before any call of \ref
1.132 - ///pushFront() or \ref pushBack()
1.133 - void setTo(const GraphNode &) {}
1.134 -
1.135 + /// Sets the starting node of the path. Edge added to the path
1.136 + /// afterwards have to be incident to this node.
1.137 + /// It should be called iff the path is empty and before any call to
1.138 + /// \ref pushFront() or \ref pushBack()
1.139 + void setStart(const GraphNode &) {}
1.140 +
1.141 ///Push a new edge to the front of the path
1.142
1.143 ///Push a new edge to the front of the path.
1.144 - ///\sa setTo
1.145 + ///\sa setStart
1.146 void pushFront(const GraphEdge& e) {
1.147 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.148 fault("DirPath::Builder::pushFront: nonincident edge");
1.149 @@ -243,7 +261,7 @@
1.150 ///Push a new edge to the back of the path
1.151
1.152 ///Push a new edge to the back of the path.
1.153 - ///\sa setFrom
1.154 + ///\sa setStart
1.155 void pushBack(const GraphEdge& e) {
1.156 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.157 fault("DirPath::Builder::pushBack: nonincident edge");
1.158 @@ -265,13 +283,319 @@
1.159 }
1.160 }
1.161
1.162 -// ///Desctuctor
1.163 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.164 + // Hogy kenyelmes egy ilyet hasznalni?
1.165 + void reserve(size_t r) {
1.166 + front.reserve(r);
1.167 + back.reserve(r);
1.168 + }
1.169
1.170 -// ///The desctuctor.
1.171 -// ///It commit also commit the changes.
1.172 -// ///\todo Is this what we want?
1.173 -// Nope. Let's use commit() explicitly.
1.174 -// ~Builder() { commit(); }
1.175 + private:
1.176 + bool empty() {
1.177 + return front.empty() && back.empty() && P.empty();
1.178 + }
1.179 +
1.180 + GraphNode from() const {
1.181 + if( ! front.empty() )
1.182 + return P.gr->tail(front[front.size()-1]);
1.183 + else if( ! P.empty() )
1.184 + return P.gr->tail(P.edges[0]);
1.185 + else if( ! back.empty() )
1.186 + return P.gr->tail(back[0]);
1.187 + else
1.188 + return INVALID;
1.189 + }
1.190 + GraphNode to() const {
1.191 + if( ! back.empty() )
1.192 + return P.gr->head(back[back.size()-1]);
1.193 + else if( ! P.empty() )
1.194 + return P.gr->head(P.edges[P.length()-1]);
1.195 + else if( ! front.empty() )
1.196 + return P.gr->head(front[0]);
1.197 + else
1.198 + return INVALID;
1.199 + }
1.200 +
1.201 + };
1.202 +
1.203 + };
1.204 +
1.205 +
1.206 +
1.207 +
1.208 +
1.209 +
1.210 +
1.211 +
1.212 +
1.213 +
1.214 + /**********************************************************************/
1.215 +
1.216 +
1.217 + //! \brief A structure for representing undirected path in a graph.
1.218 + //!
1.219 + //! A structure for representing undirected path in a graph. Ie. this is
1.220 + //! a path in a \e directed graph but the edges should not be directed
1.221 + //! forward.
1.222 + //!
1.223 + //! \param Graph The graph type in which the path is.
1.224 + //! \param DM DebugMode, defaults to DefaultDebugMode.
1.225 + //!
1.226 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.227 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.228 + //! and \c Edge of the original graph.
1.229 + //!
1.230 + //! \todo Thoroughfully check all the range and consistency tests.
1.231 + template<typename Graph, typename DM = DefaultDebugMode>
1.232 + class UndirPath {
1.233 + public:
1.234 + typedef typename Graph::Edge GraphEdge;
1.235 + typedef typename Graph::Node GraphNode;
1.236 + class NodeIt;
1.237 + class EdgeIt;
1.238 +
1.239 + protected:
1.240 + const Graph *gr;
1.241 + typedef std::vector<GraphEdge> Container;
1.242 + Container edges;
1.243 +
1.244 + public:
1.245 +
1.246 + /// \param _G The graph in which the path is.
1.247 + ///
1.248 + UndirPath(const Graph &_G) : gr(&_G) {}
1.249 +
1.250 + /// \brief Subpath constructor.
1.251 + ///
1.252 + /// Subpath defined by two nodes.
1.253 + /// \warning It is an error if the two edges are not in order!
1.254 + UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.255 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.256 + // FIXME: this check should be more elaborate...
1.257 + fault("UndirPath, subpath ctor: invalid bounding nodes");
1.258 + }
1.259 + gr = P.gr;
1.260 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.261 + }
1.262 +
1.263 + /// \brief Subpath constructor.
1.264 + ///
1.265 + /// Subpath defined by two edges. Contains edges in [a,b)
1.266 + /// \warning It is an error if the two edges are not in order!
1.267 + UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.268 + if( DM::range_check && (!a.valid() || !b.valid) ) {
1.269 + // FIXME: this check should be more elaborate...
1.270 + fault("UndirPath, subpath ctor: invalid bounding nodes");
1.271 + }
1.272 + gr = P.gr;
1.273 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.274 + }
1.275 +
1.276 + /// Length of the path.
1.277 + size_t length() const { return edges.size(); }
1.278 + /// Returns whether the path is empty.
1.279 + bool empty() const { return edges.empty(); }
1.280 +
1.281 + /// Resets the path to an empty path.
1.282 + void clear() { edges.clear(); }
1.283 +
1.284 + /// \brief Starting point of the path.
1.285 + ///
1.286 + /// Starting point of the path.
1.287 + /// Returns INVALID if the path is empty.
1.288 + GraphNode from() const {
1.289 + return empty() ? INVALID : gr->tail(edges[0]);
1.290 + }
1.291 + /// \brief End point of the path.
1.292 + ///
1.293 + /// End point of the path.
1.294 + /// Returns INVALID if the path is empty.
1.295 + GraphNode to() const {
1.296 + return empty() ? INVALID : gr->head(edges[length()-1]);
1.297 + }
1.298 +
1.299 + /// \brief Initializes node or edge iterator to point to the first
1.300 + /// node or edge.
1.301 + ///
1.302 + /// \sa nth
1.303 + template<typename It>
1.304 + It& first(It &i) const { return i=It(*this); }
1.305 +
1.306 + /// \brief Initializes node iterator to point to the node of a given index.
1.307 + NodeIt& nth(NodeIt &i, int n) const {
1.308 + if( DM::range_check && (n<0 || n>int(length())) )
1.309 + fault("UndirPath::nth: index out of range");
1.310 + return i=NodeIt(*this, n);
1.311 + }
1.312 +
1.313 + /// \brief Initializes edge iterator to point to the edge of a given index.
1.314 + EdgeIt& nth(EdgeIt &i, int n) const {
1.315 + if( DM::range_check && (n<0 || n>=int(length())) )
1.316 + fault("UndirPath::nth: index out of range");
1.317 + return i=EdgeIt(*this, n);
1.318 + }
1.319 +
1.320 + /// Checks validity of a node or edge iterator.
1.321 + template<typename It>
1.322 + static
1.323 + bool valid(const It &i) { return i.valid(); }
1.324 +
1.325 + /// Steps the given node or edge iterator.
1.326 + template<typename It>
1.327 + static
1.328 + It& next(It &e) {
1.329 + if( DM::range_check && !e.valid() )
1.330 + fault("UndirPath::next() on invalid iterator");
1.331 + return ++e;
1.332 + }
1.333 +
1.334 + /// \brief Returns node iterator pointing to the head node of the
1.335 + /// given edge iterator.
1.336 + NodeIt head(const EdgeIt& e) const {
1.337 + if( DM::range_check && !e.valid() )
1.338 + fault("UndirPath::head() on invalid iterator");
1.339 + return NodeIt(*this, e.idx+1);
1.340 + }
1.341 +
1.342 + /// \brief Returns node iterator pointing to the tail node of the
1.343 + /// given edge iterator.
1.344 + NodeIt tail(const EdgeIt& e) const {
1.345 + if( DM::range_check && !e.valid() )
1.346 + fault("UndirPath::tail() on invalid iterator");
1.347 + return NodeIt(*this, e.idx);
1.348 + }
1.349 +
1.350 +
1.351 + /*** Iterator classes ***/
1.352 + class EdgeIt {
1.353 + friend class UndirPath;
1.354 +
1.355 + int idx;
1.356 + const UndirPath *p;
1.357 + public:
1.358 + EdgeIt() {}
1.359 + EdgeIt(Invalid) : idx(-1), p(0) {}
1.360 + EdgeIt(const UndirPath &_p, int _idx = 0) :
1.361 + idx(_idx), p(&_p) { validate(); }
1.362 +
1.363 + bool valid() const { return idx!=-1; }
1.364 +
1.365 + operator GraphEdge () const {
1.366 + return valid() ? p->edges[idx] : INVALID;
1.367 + }
1.368 + EdgeIt& operator++() { ++idx; validate(); return *this; }
1.369 +
1.370 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.371 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.372 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.373 +
1.374 + private:
1.375 + // FIXME: comparison between signed and unsigned...
1.376 + // Jo ez igy? Vagy esetleg legyen a length() int?
1.377 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.378 + };
1.379 +
1.380 + class NodeIt {
1.381 + friend class UndirPath;
1.382 +
1.383 + int idx;
1.384 + const UndirPath *p;
1.385 + public:
1.386 + NodeIt() {}
1.387 + NodeIt(Invalid) : idx(-1), p(0) {}
1.388 + NodeIt(const UndirPath &_p, int _idx = 0) :
1.389 + idx(_idx), p(&_p) { validate(); }
1.390 +
1.391 + bool valid() const { return idx!=-1; }
1.392 +
1.393 + operator const GraphNode& () const {
1.394 + if(idx >= p->length())
1.395 + return p->to();
1.396 + else if(idx >= 0)
1.397 + return p->gr->tail(p->edges[idx]);
1.398 + else
1.399 + return INVALID;
1.400 + }
1.401 + NodeIt& operator++() { ++idx; validate(); return *this; }
1.402 +
1.403 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.404 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.405 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.406 +
1.407 + private:
1.408 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.409 + };
1.410 +
1.411 + friend class Builder;
1.412 +
1.413 + /**
1.414 + * \brief Class to build paths
1.415 + *
1.416 + * \ingroup datas
1.417 + * This class is used to fill a path with edges.
1.418 + *
1.419 + * You can push new edges to the front and to the back of the path in
1.420 + * arbitrary order then you should commit these changes to the graph.
1.421 + *
1.422 + * Fundamentally, for most "Paths" (classes fulfilling the
1.423 + * PathConcept) while the builder is active (after the first modifying
1.424 + * operation and until the commit()) the original Path is in a
1.425 + * "transitional" state (operations ot it have undefined result). But
1.426 + * in the case of UndirPath the original path is unchanged until the
1.427 + * commit. However we don't recomend that you use this feature.
1.428 + */
1.429 + class Builder {
1.430 + UndirPath &P;
1.431 + Container front, back;
1.432 +
1.433 + public:
1.434 + ///\param _P the path you want to fill in.
1.435 + ///
1.436 + Builder(UndirPath &_P) : P(_P) {}
1.437 +
1.438 + /// Sets the starting node of the path.
1.439 +
1.440 + /// Sets the starting node of the path. Edge added to the path
1.441 + /// afterwards have to be incident to this node.
1.442 + /// It should be called iff the path is empty and before any call to
1.443 + /// \ref pushFront() or \ref pushBack()
1.444 + void setStart(const GraphNode &) {}
1.445 +
1.446 + ///Push a new edge to the front of the path
1.447 +
1.448 + ///Push a new edge to the front of the path.
1.449 + ///\sa setStart
1.450 + void pushFront(const GraphEdge& e) {
1.451 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.452 + fault("UndirPath::Builder::pushFront: nonincident edge");
1.453 + }
1.454 + front.push_back(e);
1.455 + }
1.456 +
1.457 + ///Push a new edge to the back of the path
1.458 +
1.459 + ///Push a new edge to the back of the path.
1.460 + ///\sa setStart
1.461 + void pushBack(const GraphEdge& e) {
1.462 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.463 + fault("UndirPath::Builder::pushBack: nonincident edge");
1.464 + }
1.465 + back.push_back(e);
1.466 + }
1.467 +
1.468 + ///Commit the changes to the path.
1.469 + void commit() {
1.470 + if( !(front.empty() && back.empty()) ) {
1.471 + Container tmp;
1.472 + tmp.reserve(front.size()+back.size()+P.length());
1.473 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.474 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.475 + tmp.insert(tmp.end(), back.begin(), back.end());
1.476 + P.edges.swap(tmp);
1.477 + front.clear();
1.478 + back.clear();
1.479 + }
1.480 + }
1.481
1.482 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.483 // Hogy kenyelmes egy ilyet hasznalni?