1.1 --- a/lemon/path.h Thu Jan 24 11:31:19 2008 +0000
1.2 +++ b/lemon/path.h Thu Jan 24 16:49:10 2008 +0000
1.3 @@ -43,14 +43,15 @@
1.4 /// \param Digraph The digraph type in which the path is.
1.5 ///
1.6 /// In a sense, the path can be treated as a list of arcs. The
1.7 - /// lemon path type stores just this list. As a consequence it
1.8 - /// cannot enumerate the nodes in the path and the zero length paths
1.9 - /// cannot store the source.
1.10 + /// lemon path type stores just this list. As a consequence, it
1.11 + /// cannot enumerate the nodes of the path and the source node of
1.12 + /// a zero length path is undefined.
1.13 ///
1.14 /// This implementation is a back and front insertable and erasable
1.15 /// path type. It can be indexed in O(1) time. The front and back
1.16 - /// insertion and erasure is amortized O(1) time. The
1.17 - /// impelementation is based on two opposite organized vectors.
1.18 + /// insertion and erase is done in O(1) (amortized) time. The
1.19 + /// implementation uses two vectors for storing the front and back
1.20 + /// insertions.
1.21 template <typename _Digraph>
1.22 class Path {
1.23 public:
1.24 @@ -65,8 +66,8 @@
1.25
1.26 /// \brief Template copy constructor
1.27 ///
1.28 - /// This path can be initialized with any other path type. It just
1.29 - /// makes a copy of the given path.
1.30 + /// This constuctor initializes the path from any other path type.
1.31 + /// It simply makes a copy of the given path.
1.32 template <typename CPath>
1.33 Path(const CPath& cpath) {
1.34 copyPath(*this, cpath);
1.35 @@ -74,8 +75,7 @@
1.36
1.37 /// \brief Template copy assignment
1.38 ///
1.39 - /// This path can be initialized with any other path type. It just
1.40 - /// makes a copy of the given path.
1.41 + /// This operator makes a copy of a path of any other type.
1.42 template <typename CPath>
1.43 Path& operator=(const CPath& cpath) {
1.44 copyPath(*this, cpath);
1.45 @@ -92,7 +92,7 @@
1.46 ArcIt() {}
1.47 /// \brief Invalid constructor
1.48 ArcIt(Invalid) : path(0), idx(-1) {}
1.49 - /// \brief Initializate the constructor to the first arc of path
1.50 + /// \brief Initializate the iterator to the first arc of path
1.51 ArcIt(const Path &_path)
1.52 : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.53
1.54 @@ -129,13 +129,13 @@
1.55
1.56 /// \brief Length of the path.
1.57 int length() const { return head.size() + tail.size(); }
1.58 - /// \brief Returns whether the path is empty.
1.59 + /// \brief Return whether the path is empty.
1.60 bool empty() const { return head.empty() && tail.empty(); }
1.61
1.62 - /// \brief Resets the path to an empty path.
1.63 + /// \brief Reset the path to an empty one.
1.64 void clear() { head.clear(); tail.clear(); }
1.65
1.66 - /// \brief Gives back the nth arc.
1.67 + /// \brief The nth arc.
1.68 ///
1.69 /// \pre n is in the [0..length() - 1] range
1.70 const Arc& nth(int n) const {
1.71 @@ -143,14 +143,14 @@
1.72 *(tail.begin() + (n - head.size()));
1.73 }
1.74
1.75 - /// \brief Initializes arc iterator to point to the nth arc
1.76 + /// \brief Initialize arc iterator to point to the nth arc
1.77 ///
1.78 /// \pre n is in the [0..length() - 1] range
1.79 ArcIt nthIt(int n) const {
1.80 return ArcIt(*this, n);
1.81 }
1.82
1.83 - /// \brief Gives back the first arc of the path
1.84 + /// \brief The first arc of the path
1.85 const Arc& front() const {
1.86 return head.empty() ? tail.front() : head.back();
1.87 }
1.88 @@ -175,7 +175,7 @@
1.89 }
1.90 }
1.91
1.92 - /// \brief Gives back the last arc of the path
1.93 + /// \brief The last arc of the path
1.94 const Arc& back() const {
1.95 return tail.empty() ? head.front() : tail.back();
1.96 }
1.97 @@ -199,8 +199,6 @@
1.98 }
1.99 }
1.100
1.101 -
1.102 -
1.103 typedef True BuildTag;
1.104
1.105 template <typename CPath>
1.106 @@ -323,13 +321,13 @@
1.107
1.108 /// \brief Length of the path.
1.109 int length() const { return data.size(); }
1.110 - /// \brief Returns whether the path is empty.
1.111 + /// \brief Return true if the path is empty.
1.112 bool empty() const { return data.empty(); }
1.113
1.114 - /// \brief Resets the path to an empty path.
1.115 + /// \brief Reset the path to an empty one.
1.116 void clear() { data.clear(); }
1.117
1.118 - /// \brief Gives back the nth arc.
1.119 + /// \brief The nth arc.
1.120 ///
1.121 /// \pre n is in the [0..length() - 1] range
1.122 const Arc& nth(int n) const {
1.123 @@ -341,12 +339,12 @@
1.124 return ArcIt(*this, n);
1.125 }
1.126
1.127 - /// \brief Gives back the first arc of the path.
1.128 + /// \brief The first arc of the path.
1.129 const Arc& front() const {
1.130 return data.front();
1.131 }
1.132
1.133 - /// \brief Gives back the last arc of the path.
1.134 + /// \brief The last arc of the path.
1.135 const Arc& back() const {
1.136 return data.back();
1.137 }
1.138 @@ -506,9 +504,9 @@
1.139 Node *node;
1.140 };
1.141
1.142 - /// \brief Gives back the nth arc.
1.143 + /// \brief The nth arc.
1.144 ///
1.145 - /// Gives back the nth arc in O(n) time.
1.146 + /// This function looks for the nth arc in O(n) time.
1.147 /// \pre n is in the [0..length() - 1] range
1.148 const Arc& nth(int n) const {
1.149 Node *node = first;
1.150 @@ -538,10 +536,10 @@
1.151 return len;
1.152 }
1.153
1.154 - /// \brief Returns whether the path is empty.
1.155 + /// \brief Return true if the path is empty.
1.156 bool empty() const { return first == 0; }
1.157
1.158 - /// \brief Resets the path to an empty path.
1.159 + /// \brief Reset the path to an empty one.
1.160 void clear() {
1.161 while (first != 0) {
1.162 last = first->next;
1.163 @@ -551,7 +549,7 @@
1.164 }
1.165 }
1.166
1.167 - /// \brief Gives back the first arc of the path
1.168 + /// \brief The first arc of the path
1.169 const Arc& front() const {
1.170 return first->arc;
1.171 }
1.172 @@ -584,7 +582,7 @@
1.173 alloc.deallocate(node, 1);
1.174 }
1.175
1.176 - /// \brief Gives back the last arc of the path.
1.177 + /// \brief The last arc of the path.
1.178 const Arc& back() const {
1.179 return last->arc;
1.180 }
1.181 @@ -617,9 +615,9 @@
1.182 alloc.deallocate(node, 1);
1.183 }
1.184
1.185 - /// \brief Splicing the given path to the current path.
1.186 + /// \brief Splice a path to the back of the current path.
1.187 ///
1.188 - /// It splices the \c tpath to the back of the current path and \c
1.189 + /// It splices \c tpath to the back of the current path and \c
1.190 /// tpath becomes empty. The time complexity of this function is
1.191 /// O(1).
1.192 void spliceBack(ListPath& tpath) {
1.193 @@ -636,9 +634,9 @@
1.194 tpath.first = tpath.last = 0;
1.195 }
1.196
1.197 - /// \brief Splicing the given path to the current path.
1.198 + /// \brief Splice a path to the front of the current path.
1.199 ///
1.200 - /// It splices the \c tpath before the current path and \c tpath
1.201 + /// It splices \c tpath before the current path and \c tpath
1.202 /// becomes empty. The time complexity of this function
1.203 /// is O(1).
1.204 void spliceFront(ListPath& tpath) {
1.205 @@ -655,12 +653,12 @@
1.206 tpath.first = tpath.last = 0;
1.207 }
1.208
1.209 - /// \brief Splicing the given path into the current path.
1.210 + /// \brief Splice a path into the current path.
1.211 ///
1.212 /// It splices the \c tpath into the current path before the
1.213 /// position of \c it iterator and \c tpath becomes empty. The
1.214 - /// time complexity of this function is O(1). If the \c it is \c
1.215 - /// INVALID then it will splice behind the current path.
1.216 + /// time complexity of this function is O(1). If the \c it is
1.217 + /// \c INVALID then it will splice behind the current path.
1.218 void splice(ArcIt it, ListPath& tpath) {
1.219 if (it.node) {
1.220 if (tpath.first) {
1.221 @@ -688,15 +686,15 @@
1.222 tpath.first = tpath.last = 0;
1.223 }
1.224
1.225 - /// \brief Spliting the current path.
1.226 + /// \brief Split the current path.
1.227 ///
1.228 - /// It splits the current path into two parts. The part before \c
1.229 - /// it iterator will remain in the current path and the part from
1.230 - /// the it will put into the \c tpath. If the \c tpath had arcs
1.231 - /// before the operation they will be removed first. The time
1.232 - /// complexity of this function is O(1) plus the clearing of \c
1.233 - /// tpath. If the \c it is \c INVALID then it just clears \c
1.234 - /// tpath.
1.235 + /// It splits the current path into two parts. The part before
1.236 + /// the iterator \c it will remain in the current path and the part
1.237 + /// starting with
1.238 + /// \c it will put into \c tpath. If \c tpath have arcs
1.239 + /// before the operation they are removed first. The time
1.240 + /// complexity of this function is O(1) plus the the time of emtying
1.241 + /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
1.242 void split(ArcIt it, ListPath& tpath) {
1.243 tpath.clear();
1.244 if (it.node) {
1.245 @@ -738,13 +736,16 @@
1.246 ///
1.247 /// In a sense, the path can be treated as a list of arcs. The
1.248 /// lemon path type stores just this list. As a consequence it
1.249 - /// cannot enumerate the nodes in the path and the zero length paths
1.250 - /// cannot store the source.
1.251 + /// cannot enumerate the nodes in the path and the source node of
1.252 + /// a zero length path is undefined.
1.253 ///
1.254 - /// This implementation is completly static, so it cannot be
1.255 - /// modified exclude the assign an other path. It is intented to be
1.256 - /// used when you want to store a large number of paths because it is
1.257 - /// the most memory efficient path type in the lemon.
1.258 + /// This implementation is completly static, i.e. it can be copy constucted
1.259 + /// or copy assigned from another path, but otherwise it cannot be
1.260 + /// modified.
1.261 + ///
1.262 + /// Being the the most memory efficient path type in LEMON,
1.263 + /// it is intented to be
1.264 + /// used when you want to store a large number of paths.
1.265 template <typename _Digraph>
1.266 class StaticPath {
1.267 public:
1.268 @@ -759,8 +760,7 @@
1.269
1.270 /// \brief Template copy constructor
1.271 ///
1.272 - /// This path can be initialized with any other path type. It just
1.273 - /// makes a copy of the given path.
1.274 + /// This path can be initialized from any other path type.
1.275 template <typename CPath>
1.276 StaticPath(const CPath& cpath) : arcs(0) {
1.277 copyPath(*this, cpath);
1.278 @@ -775,7 +775,7 @@
1.279
1.280 /// \brief Template copy assignment
1.281 ///
1.282 - /// This path can be initialized with any other path type. It just
1.283 + /// This path can be made equal to any other path type. It simply
1.284 /// makes a copy of the given path.
1.285 template <typename CPath>
1.286 StaticPath& operator=(const CPath& cpath) {
1.287 @@ -831,37 +831,37 @@
1.288 int idx;
1.289 };
1.290
1.291 - /// \brief Gives back the nth arc.
1.292 + /// \brief The nth arc.
1.293 ///
1.294 /// \pre n is in the [0..length() - 1] range
1.295 const Arc& nth(int n) const {
1.296 return arcs[n];
1.297 }
1.298
1.299 - /// \brief Initializes arc iterator to point to the nth arc.
1.300 + /// \brief The arc iterator pointing to the nth arc.
1.301 ArcIt nthIt(int n) const {
1.302 return ArcIt(*this, n);
1.303 }
1.304
1.305 - /// \brief Gives back the length of the path.
1.306 + /// \brief The length of the path.
1.307 int length() const { return len; }
1.308
1.309 - /// \brief Returns true when the path is empty.
1.310 + /// \brief Return true when the path is empty.
1.311 int empty() const { return len == 0; }
1.312
1.313 - /// \break Erase all arc in the digraph.
1.314 + /// \break Erase all arcs in the digraph.
1.315 void clear() {
1.316 len = 0;
1.317 if (arcs) delete[] arcs;
1.318 arcs = 0;
1.319 }
1.320
1.321 - /// \brief Gives back the first arc of the path.
1.322 + /// \brief The first arc of the path.
1.323 const Arc& front() const {
1.324 return arcs[0];
1.325 }
1.326
1.327 - /// \brief Gives back the last arc of the path.
1.328 + /// \brief The last arc of the path.
1.329 const Arc& back() const {
1.330 return arcs[len - 1];
1.331 }