Changeset 226:616bc397c83a in lemon-0.x for src/work/klao/path.h

Timestamp:

03/21/04 18:09:16 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@323

Message:

Reszutas konstruktorok

File:

• src/work/klao/path.h (modified) (6 diffs)

src/work/klao/path.h

@@ -11 +11 @@
 
 #include <deque>
+#include <algorithm>
 
 #include <invalid.h>
@@ -40 +41 @@
     Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
 
-    /// Subpath defined by two nodes
-    Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
-    /// Subpath defined by tow edges. Contains edges in [a,b)
-    Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
+    /// Subpath defined by two nodes.
+    /// Nodes may be in reversed order, then
+    /// we contstruct the reversed path.
+    Path(const Path &P, const NodeIt &a, const NodeIt &b);
+    /// Subpath defined by two edges. Contains edges in [a,b)
+    /// It is an error if the two edges are not in order!
+    Path(const Path &P, const EdgeIt &a, const EdgeIt &b);
     
     size_t length() const { return edges.size(); }
@@ -71 +75 @@
 
     bool isForward(const EdgeIt &e) const { return e.forw; }
+
+    /// index of a node on the path. Returns length+2 for the invalid NodeIt
+    int index(const NodeIt &n) const { return n.idx; }
+    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
+    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
 
     EdgeIt& next(EdgeIt &e) const;
@@ -123 +132 @@
       friend class EdgeIt;
 
-      int idx;
+      size_t idx;
       bool tail;  // Is this node the tail of the edge with same idx?
 
@@ -302 +311 @@
     n.idx = e.it-edges.begin();
     n.tail = e.forw;
+    return n;
   }
 
@@ -378 +388 @@
   }
 
+  // Reszut konstruktorok:
+
+
+  template<typename Gr>
+  Path<Gr>::Path(const Path &P, const EdgeIt &a, const EdgeIt &b) :
+    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up! 
+  {
+    if( G.valid(P._first) && a.it < P.edges.end() ) {
+      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
+      if( b.it < P.edges.end() ) {
+        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
+      }
+      else {
+        _last = P._last;
+      }
+    }
+  }
+
+
+  template<typename Gr>
+  Path<Gr>::Path(const Path &P, const NodeIt &a, const NodeIt &b) :
+    G(P.G)
+  {
+    if( !P.valid(a) || !P.valid(b) )
+      return;
+
+    int ai = a.idx, bi = b.idx;
+    if( bi<ai )
+      swap(ai,bi);
+    
+    edges.resize(bi-ai);
+    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
+
+    _first = P.graphNode(a);
+    _last = P.graphNode(b);
+  }
+
 
 } // namespace hugo