Changes in / [1047:f7247b5c04bf:1048:dbaf21739390] in lemon-main

Files:

• lemon/path.h (modified) (1 diff)
• test/path_test.cc (modified) (2 diffs)

lemon/path.h

@@ -318 +318 @@
       /// Constructor with starting point
       ArcIt(const SimplePath &_path, int _idx)
-        : idx(_idx), path(&_path) {}
+        : path(&_path), idx(_idx) {}
 
     public:

test/path_test.cc

@@ -22 +22 @@
 #include <lemon/concepts/path.h>
 #include <lemon/concepts/digraph.h>
+#include <lemon/concept_check.h>
 
 #include <lemon/path.h>
@@ -31 +32 @@
 using namespace lemon;
 
-void check_concepts() {
-  checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
-  checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
-  checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
-  checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
-  checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
+template <typename GR>
+void checkConcepts() {
+  checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
+  checkConcept<concepts::Path<GR>, Path<GR> >();
+  checkConcept<concepts::Path<GR>, SimplePath<GR> >();
+  checkConcept<concepts::Path<GR>, StaticPath<GR> >();
+  checkConcept<concepts::Path<GR>, ListPath<GR> >();
+}
+
+// Conecpt checking for path structures
+void checkPathConcepts() {
+  checkConcepts<concepts::Digraph>();
+  checkConcepts<ListDigraph>();
 }
 
 // Check if proper copy consructor is called (use valgrind for testing)
-template<class _Path>
-void checkCopy()
-{
+template <typename GR, typename P1, typename P2>
+void checkCopy(typename GR::Arc a) {
+  P1 p;
+  p.addBack(a);
+  P1 q;
+  q = p;
+  P1 r(p);
+  P2 q2;
+  q2 = p;
+  P2 r2(p);
+}
+
+// Tests for copy constructors and assignment operators of paths
+void checkPathCopy() {
   ListDigraph g;
-  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
-  
-  _Path p,q;
-  p.addBack(a);
-  q=p;
-  _Path r(p);
-  StaticPath<ListDigraph> s(r);
-}
-  
+  ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
+
+  typedef Path<ListDigraph> Path1;
+  typedef SimplePath<ListDigraph> Path2;
+  typedef ListPath<ListDigraph> Path3;
+  typedef StaticPath<ListDigraph> Path4;
+  checkCopy<ListDigraph, Path1, Path2>(a);
+  checkCopy<ListDigraph, Path1, Path3>(a);
+  checkCopy<ListDigraph, Path1, Path4>(a);
+  checkCopy<ListDigraph, Path2, Path1>(a);
+  checkCopy<ListDigraph, Path2, Path3>(a);
+  checkCopy<ListDigraph, Path2, Path4>(a);
+  checkCopy<ListDigraph, Path3, Path1>(a);
+  checkCopy<ListDigraph, Path3, Path2>(a);
+  checkCopy<ListDigraph, Path3, Path4>(a);
+}
+
+// Class for testing path functions
+class CheckPathFunctions {
+  typedef ListDigraph GR;
+  DIGRAPH_TYPEDEFS(GR);
+  GR gr;
+  const GR& cgr;
+  Node n1, n2, n3, n4;
+  Node tmp_n;
+  Arc a1, a2, a3, a4;
+  Arc tmp_a;
+
+public:
+
+  CheckPathFunctions() : cgr(gr) {
+    n1 = gr.addNode();
+    n2 = gr.addNode();
+    n3 = gr.addNode();
+    n4 = gr.addNode();
+    a1 = gr.addArc(n1, n2);
+    a2 = gr.addArc(n2, n3);
+    a3 = gr.addArc(n3, n4);
+    a4 = gr.addArc(n4, n1);
+  }
+
+  void run() {
+    checkBackAndFrontInsertablePath<Path<GR> >();
+    checkBackAndFrontInsertablePath<ListPath<GR> >();
+    checkBackInsertablePath<SimplePath<GR> >();
+
+    checkListPathSplitAndSplice();
+  }
+
+private:
+
+  template <typename P>
+  void checkBackInsertablePath() {
+
+    // Create and check empty path
+    P p;
+    const P& cp = p;
+    check(cp.empty(), "The path is not empty");
+    check(cp.length() == 0, "The path is not empty");
+//    check(cp.front() == INVALID, "Wrong front()");
+//    check(cp.back() == INVALID, "Wrong back()");
+    typename P::ArcIt ai(cp);
+    check(ai == INVALID, "Wrong ArcIt");
+    check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni(cgr, cp);
+    check(ni == INVALID, "Wrong PathNodeIt");
+
+    // Check single-arc path
+    p.addBack(a1);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 1, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(cp.nth(0) == a1, "Wrong nth()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    typename P::ArcIt ai2(cp);
+    check((tmp_a = ai2) == a1, "Wrong ArcIt");
+    check(++ai2 == INVALID, "Wrong ArcIt");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni2(cgr, cp);
+    check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
+    check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
+    check(++ni2 == INVALID, "Wrong PathNodeIt");
+
+    // Check adding more arcs
+    p.addBack(a2);
+    p.addBack(a3);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a3, "Wrong back()");
+    check(cp.nth(0) == a1, "Wrong nth()");
+    check(cp.nth(1) == a2, "Wrong nth()");
+    check(cp.nth(2) == a3, "Wrong nth()");
+    typename P::ArcIt ai3(cp);
+    check((tmp_a = ai3) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
+    check(++ai3 == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a3, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni3(cgr, cp);
+    check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
+    check(++ni3 == INVALID, "Wrong PathNodeIt");
+
+    // Check arc removal and addition
+    p.eraseBack();
+    p.eraseBack();
+    p.addBack(a2);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 2, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a2, "Wrong back()");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+
+    // Check clear()
+    p.clear();
+    check(cp.empty(), "The path is not empty");
+    check(cp.length() == 0, "The path is not empty");
+
+    // Check inconsistent path
+    p.addBack(a4);
+    p.addBack(a2);
+    p.addBack(a1);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a4, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(!checkPath(cgr, cp), "Wrong checkPath()");
+  }
+
+  template <typename P>
+  void checkBackAndFrontInsertablePath() {
+
+    // Include back insertable test cases
+    checkBackInsertablePath<P>();
+
+    // Check front and back insertion
+    P p;
+    const P& cp = p;
+    p.addFront(a4);
+    p.addBack(a1);
+    p.addFront(a3);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a3, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(cp.nth(0) == a3, "Wrong nth()");
+    check(cp.nth(1) == a4, "Wrong nth()");
+    check(cp.nth(2) == a1, "Wrong nth()");
+    typename P::ArcIt ai(cp);
+    check((tmp_a = ai) == a3, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+
+    // Check eraseFront()
+    p.eraseFront();
+    p.addBack(a2);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a4, "Wrong front()");
+    check(cp.back() == a2, "Wrong back()");
+    check(cp.nth(0) == a4, "Wrong nth()");
+    check(cp.nth(1) == a1, "Wrong nth()");
+    check(cp.nth(2) == a2, "Wrong nth()");
+    typename P::ArcIt ai2(cp);
+    check((tmp_a = ai2) == a4, "Wrong ArcIt");
+    check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
+    check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
+    check(++ai2 == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a4, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a2, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+  }
+
+  void checkListPathSplitAndSplice() {
+
+    // Build a path with spliceFront() and spliceBack()
+    ListPath<GR> p1, p2, p3, p4;
+    p1.addBack(a3);
+    p1.addFront(a2);
+    p2.addBack(a1);
+    p1.spliceFront(p2);
+    p3.addFront(a4);
+    p1.spliceBack(p3);
+    check(p1.length() == 4, "Wrong length");
+    check(p1.front() == a1, "Wrong front()");
+    check(p1.back() == a4, "Wrong back()");
+    ListPath<GR>::ArcIt ai(p1);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p1), "Wrong checkPath()");
+
+    // Check split()
+    p1.split(p1.nthIt(2), p2);
+    check(p1.length() == 2, "Wrong length");
+    ai = p1.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p1), "Wrong checkPath()");
+    check(p2.length() == 2, "Wrong length");
+    ai = p2.nthIt(0);
+    check((tmp_a = ai) == a3, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p2), "Wrong checkPath()");
+
+    // Check split() and splice()
+    p1.spliceFront(p2);
+    p1.split(p1.nthIt(2), p2);
+    p2.split(p2.nthIt(1), p3);
+    p2.spliceBack(p1);
+    p2.splice(p2.nthIt(1), p3);
+    check(p2.length() == 4, "Wrong length");
+    check(p2.front() == a1, "Wrong front()");
+    check(p2.back() == a4, "Wrong back()");
+    ai = p2.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p2), "Wrong checkPath()");
+  }
+
+};
+
 int main() {
-  check_concepts();
-
-  checkCopy<Path<ListDigraph> >();
-  checkCopy<SimplePath<ListDigraph> >();
-  checkCopy<ListPath<ListDigraph> >();
-
-  ListDigraph g;
-  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
-  
-  Path<ListDigraph> p;
-  StaticPath<ListDigraph> q,r;
-  p.addBack(a);
-  q=p;
-  r=q;
-  StaticPath<ListDigraph> s(q);
+  checkPathConcepts();
+  checkPathCopy();
+  CheckPathFunctions cpf;
+  cpf.run();
 
   return 0;