1.1 --- a/src/work/klao/path.h Fri Apr 30 01:10:13 2004 +0000
1.2 +++ b/src/work/klao/path.h Fri Apr 30 01:59:15 2004 +0000
1.3 @@ -1,8 +1,8 @@
1.4 // -*- c++ -*- //
1.5
1.6 -///ingroup datas
1.7 +///\ingroup datas
1.8 ///\file
1.9 -///\brief Class for representing paths in graphs.
1.10 +///\brief Classes for representing paths in graphs.
1.11
1.12 #ifndef HUGO_PATH_H
1.13 #define HUGO_PATH_H
1.14 @@ -12,22 +12,26 @@
1.15 #include <algorithm>
1.16
1.17 #include <invalid.h>
1.18 +#include <error.h>
1.19 +#include <debug.h>
1.20
1.21 namespace hugo {
1.22
1.23 /// \addtogroup datas
1.24 /// @{
1.25
1.26 - ///A container for directed paths
1.27
1.28 - ///\param Graph The graph type in which the path is.
1.29 - ///
1.30 - ///In a sense, the path can be treated as a graph, for is has \c NodeIt
1.31 - ///and \c EdgeIt with the same usage. These types converts to the \c Node
1.32 - ///and \c Edge of the original graph.
1.33 - ///\todo How to clear a path?
1.34 - ///\todo Clarify the consistency checks to do.
1.35 - template<typename Graph>
1.36 + //! \brief A structure for representing directed path in a graph.
1.37 + //!
1.38 + //! \param Graph The graph type in which the path is.
1.39 + //! \param DM DebugMode, defaults to DefaultDebugMode.
1.40 + //!
1.41 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.42 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.43 + //! and \c Edge of the original graph.
1.44 + //!
1.45 + //! \todo Thoroughfully check all the range and consistency tests.
1.46 + template<typename Graph, typename DM = DefaultDebugMode>
1.47 class DirPath {
1.48 public:
1.49 typedef typename Graph::Edge GraphEdge;
1.50 @@ -42,43 +46,86 @@
1.51
1.52 public:
1.53
1.54 - /// Constructor
1.55 -
1.56 /// \param _G The graph in which the path is.
1.57 ///
1.58 DirPath(const Graph &_G) : gr(&_G) {}
1.59
1.60 + /// \brief Subpath constructor.
1.61 + ///
1.62 /// Subpath defined by two nodes.
1.63 /// \warning It is an error if the two edges are not in order!
1.64 + /// \todo Implement!
1.65 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
1.66 + /// \brief Subpath constructor.
1.67 + ///
1.68 /// Subpath defined by two edges. Contains edges in [a,b)
1.69 /// \warning It is an error if the two edges are not in order!
1.70 + /// \todo Implement!
1.71 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
1.72
1.73 + /// Length of the path.
1.74 size_t length() const { return edges.size(); }
1.75 + /// Returns whether the path is empty.
1.76 bool empty() const { return edges.empty(); }
1.77 +
1.78 + /// Resets the path to an empty path.
1.79 + void clear() { edges.clear(); }
1.80 +
1.81 + /// \brief Starting point of the path.
1.82 + ///
1.83 + /// Starting point of the path.
1.84 + /// Returns INVALID if the path is empty.
1.85 GraphNode from() const {
1.86 return empty() ? INVALID : gr->tail(edges[0]);
1.87 }
1.88 + /// \brief End point of the path.
1.89 + ///
1.90 + /// End point of the path.
1.91 + /// Returns INVALID if the path is empty.
1.92 GraphNode to() const {
1.93 return empty() ? INVALID : gr->head(edges[length()-1]);
1.94 }
1.95
1.96 + /// \brief Initializes node or edge iterator to point to the first
1.97 + /// node or edge.
1.98 + ///
1.99 + /// \sa nth
1.100 template<typename It>
1.101 It& first(It &i) const { return i=It(*this); }
1.102
1.103 + /// \brief Initializes node or edge iterator to point to the node or edge
1.104 + /// of a given index.
1.105 template<typename It>
1.106 - It& nth(It &i, int n) const { return i=It(*this, n); }
1.107 + It& nth(It &i, int n) const {
1.108 + // FIXME: this test should be different for NodeIt and EdgeIt:
1.109 + if( DM::range_check && (n<0 || n>int(length())) )
1.110 + fault("DirPath::nth: index out of range");
1.111 + return i=It(*this, n);
1.112 + }
1.113
1.114 + /// Checks validity of a node or edge iterator.
1.115 template<typename It>
1.116 bool valid(const It &i) const { return i.valid(); }
1.117
1.118 + /// Steps the given node or edge iterator.
1.119 template<typename It>
1.120 - It& next(It &e) const { return ++e; }
1.121 + It& next(It &e) const {
1.122 + if( DM::range_check && !e.valid() )
1.123 + fault("DirPath::next() on invalid iterator");
1.124 + return ++e;
1.125 + }
1.126
1.127 - /// \todo !
1.128 - NodeIt head(const EdgeIt& e) const;
1.129 - NodeIt tail(const EdgeIt& e) const;
1.130 + /// \brief Returns node iterator pointing to the head node of the
1.131 + /// given edge iterator.
1.132 + NodeIt head(const EdgeIt& e) const {
1.133 + return NodeIt(*this, e.idx+1);
1.134 + }
1.135 +
1.136 + /// \brief Returns node iterator pointing to the tail node of the
1.137 + /// given edge iterator.
1.138 + NodeIt tail(const EdgeIt& e) const {
1.139 + return NodeIt(*this, e.idx);
1.140 + }
1.141
1.142
1.143 /*** Iterator classes ***/
1.144 @@ -143,92 +190,118 @@
1.145
1.146 friend class Builder;
1.147
1.148 - ///Class to build paths
1.149 -
1.150 - ///\ingroup datas
1.151 - ///This class is used to build new paths.
1.152 - ///You can push new edges to the front and to the back of the path in
1.153 - ///arbitrary order the you can commit these changes to the graph.
1.154 - ///\todo We must clarify when the path will be in "transitional" state.
1.155 + /**
1.156 + * \brief Class to build paths
1.157 + *
1.158 + * \ingroup datas
1.159 + * This class is used to fill a path with edges.
1.160 + *
1.161 + * You can push new edges to the front and to the back of the path in
1.162 + * arbitrary order the you can commit these changes to the graph.
1.163 + *
1.164 + * Fundamentally, for most "Paths" (classes fulfilling the
1.165 + * PathConcept) while the builder is active (after the first modifying
1.166 + * operation and until the commit()) the original Path is in a
1.167 + * "transitional" state (operations ot it have undefined result). But
1.168 + * in the case of DirPath the original path is unchanged until the
1.169 + * commit. However we don't recomend that you use this feature.
1.170 + */
1.171 class Builder {
1.172 DirPath &P;
1.173 - Container d;
1.174 + Container front, back;
1.175
1.176 public:
1.177 - ///Constructor
1.178 -
1.179 - ///\param _P the path you want to build.
1.180 + ///\param _P the path you want to fill in.
1.181 ///
1.182 Builder(DirPath &_P) : P(_P) {}
1.183
1.184 - ///Set the first node of the path.
1.185 + ///Sets the first node of the path.
1.186
1.187 - ///Set the first node of the path.
1.188 - ///If the path is empty, this must be call before any call of
1.189 - ///\ref pushFront() or \ref pushBack()
1.190 - void setFirst(const GraphNode &) { }
1.191 + ///Sets the first node of the path. If the path is empty, this
1.192 + ///function or setTo() have to be called before any call to \ref
1.193 + ///pushFront() or \ref pushBack()
1.194 + void setFrom(const GraphNode &) {}
1.195 +
1.196 + ///Sets the last node of the path.
1.197 +
1.198 + ///Sets the last node of the path. If the path is empty, this
1.199 + ///function or setFrom() have to be called before any call of \ref
1.200 + ///pushFront() or \ref pushBack()
1.201 + void setTo(const GraphNode &) {}
1.202
1.203 ///Push a new edge to the front of the path
1.204
1.205 ///Push a new edge to the front of the path.
1.206 - ///\sa setFirst()
1.207 - bool pushFront(const GraphEdge& e) {
1.208 - if( empty() || P.gr->head(e)==from() ) {
1.209 - d.push_back(e);
1.210 - return true;
1.211 + ///\sa setTo
1.212 + void pushFront(const GraphEdge& e) {
1.213 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.214 + fault("DirPath::Builder::pushFront: nonincident edge");
1.215 }
1.216 - return false;
1.217 + front.push_back(e);
1.218 }
1.219 +
1.220 ///Push a new edge to the back of the path
1.221
1.222 ///Push a new edge to the back of the path.
1.223 - ///\sa setFirst()
1.224 - bool pushBack(const GraphEdge& e) {
1.225 - if( empty() || P.gr->tail(e)==to() ) {
1.226 - P.edges.push_back(e);
1.227 - return true;
1.228 + ///\sa setFrom
1.229 + void pushBack(const GraphEdge& e) {
1.230 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.231 + fault("DirPath::Builder::pushBack: nonincident edge");
1.232 }
1.233 - return false;
1.234 + back.push_back(e);
1.235 }
1.236
1.237 ///Commit the changes to the path.
1.238 void commit() {
1.239 - if( !d.empty() ) {
1.240 - P.edges.insert(P.edges.begin(), d.rbegin(), d.rend());
1.241 - d.clear();
1.242 + if( !(front.empty() && back.empty()) ) {
1.243 + Container tmp;
1.244 + tmp.reserve(front.size()+back.size()+P.length());
1.245 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.246 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.247 + tmp.insert(tmp.end(), back.begin(), back.end());
1.248 + P.edges.swap(tmp);
1.249 + front.clear();
1.250 + back.clear();
1.251 }
1.252 }
1.253
1.254 - ///Desctuctor
1.255 +// ///Desctuctor
1.256
1.257 - ///The desctuctor.
1.258 - ///It commit also commit the changes.
1.259 - ///\todo Is this what we want?
1.260 - ~Builder() { commit(); }
1.261 +// ///The desctuctor.
1.262 +// ///It commit also commit the changes.
1.263 +// ///\todo Is this what we want?
1.264 +// Nope. Let's use commit() explicitly.
1.265 +// ~Builder() { commit(); }
1.266
1.267 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.268 // Hogy kenyelmes egy ilyet hasznalni?
1.269 void reserve(size_t r) {
1.270 - d.reserve(r);
1.271 - P.edges.reserve(P.length()+r);
1.272 + front.reserve(r);
1.273 + back.reserve(r);
1.274 }
1.275
1.276 private:
1.277 - bool empty() { return d.empty() && P.empty(); }
1.278 + bool empty() {
1.279 + return front.empty() && back.empty() && P.empty();
1.280 + }
1.281
1.282 GraphNode from() const {
1.283 - if( ! d.empty() )
1.284 - return P.gr->tail(d[d.size()-1]);
1.285 + if( ! front.empty() )
1.286 + return P.gr->tail(front[front.size()-1]);
1.287 else if( ! P.empty() )
1.288 return P.gr->tail(P.edges[0]);
1.289 + else if( ! back.empty() )
1.290 + return P.gr->tail(back[0]);
1.291 else
1.292 return INVALID;
1.293 }
1.294 GraphNode to() const {
1.295 - if( ! P.empty() )
1.296 + if( ! back.empty() )
1.297 + return P.gr->head(back[back.size()-1]);
1.298 + else if( ! P.empty() )
1.299 return P.gr->head(P.edges[P.length()-1]);
1.300 - else if( ! d.empty() )
1.301 - return P.gr->head(d[0]);
1.302 + else if( ! front.empty() )
1.303 + return P.gr->head(front[0]);
1.304 else
1.305 return INVALID;
1.306 }