add operator< to ConservedPath

So I could sort a list of ConservedPaths it was hopefully going to
let me make simple_refine a little bit better by grouping paths
that were next to each other closer than those that were almost
next to each other execpt one match far away. Unfortunately
I didn't think it all the way through and the lists are already
sorted by that criteria. e.g.

1,1,1 < 1,1,70 < 2,2,2

when what simple refine needis is something more like

1,1,1 < 2,2,2 < 1,1,70

diff --git a/alg/conserved_path.cpp b/alg/conserved_path.cpp
index 52e0c39b5a3fc8d5c686a651ddd278e0bd5af173..1edb374065c2027d3cf1a4e37dec80b17ebea9c6 100644 (file)
--- a/alg/conserved_path.cpp
+++ b/alg/conserved_path.cpp
@@ -54,6 +54,32 @@ bool operator!=(const ConservedPath::ConservedPath& a,
   return not (a == b);
 }
 
+bool operator<(const ConservedPath& a, const ConservedPath &b)
+{
+  ConservedPath::const_iterator a_i = a.begin();
+  ConservedPath::const_iterator b_i = b.begin();
+  for(; a_i != a.end() and b_i != b.end(); ++a_i, ++b_i)
+  {
+    if (*a_i < *b_i) {
+      return true;
+    } else if (*a_i > *b_i) {
+      return false;
+    }
+    // else they're equal and we continue to loop
+  }
+  // now handle mismatched lengths
+  if (a_i == a.end() and b_i == b.end()) {
+    return false; // since the two paths are equal
+  } else if (a_i == a.end()) {
+    return true; // a is shorter than b
+  } else if (b_i == b.end()) {
+    return false; // b is shorter than a
+  } else {
+    // something went horribly wrong
+    throw std::runtime_error("ConservedPath operator< had a fatal logic error");
+  }
+}
+
 std::ostream& operator<<(std::ostream& out, const ConservedPath& path)
 {
   out << "<path win_size" << path.window_size 

diff --git a/alg/conserved_path.hpp b/alg/conserved_path.hpp
index 5f7e0033ce208fc6addfcc7e53872cd05bc6e458..7ff26613ab23ae2ea5ce16998348a022dfaaeccc 100644 (file)
--- a/alg/conserved_path.hpp
+++ b/alg/conserved_path.hpp
@@ -29,6 +29,7 @@ struct ConservedPath
 
   friend bool operator==(const ConservedPath& a, const ConservedPath &b);
   friend bool operator!=(const ConservedPath& a, const ConservedPath &b);
+  friend bool operator<(const ConservedPath& a, const ConservedPath &b);
   friend std::ostream& operator<<(std::ostream&, const ConservedPath&);
 
   //! return true if all elements of the path are "next to" our current path.

diff --git a/alg/test/test_conserved_path.cpp b/alg/test/test_conserved_path.cpp
index f8d670c31fd62a81faf084bc997709e110c2701c..e467c721dd635a9656ecd9a7c4e858ce1485aa13 100644 (file)
--- a/alg/test/test_conserved_path.cpp
+++ b/alg/test/test_conserved_path.cpp
@@ -159,3 +159,61 @@ BOOST_AUTO_TEST_CASE ( extended_conserved_normalized )
   }
 }
 
+BOOST_AUTO_TEST_CASE( conserved_path_less_than )
+{
+  vector<int> p111;
+  p111 += 1,1,1;
+  vector<int> p112;
+  p112 += 1,1,2;
+  vector<int> p115;
+  p115 += 1,1,5; 
+  vector<int> p112a;
+  p112a += 1,1,1;
+  vector<int> p1111;
+  p1111 += 1,1,1,1; 
+  
+  ConservedPath cp111(10, 1.0, p111);
+  ConservedPath cp112(10, 1.0, p112);
+  ConservedPath cp112a(10, 1.0, p112a);
+  ConservedPath cp115(10, 1.0, p115);
+  ConservedPath cp1111(10, 1.0, p1111);
+  
+  BOOST_CHECK_EQUAL( cp111 < cp112, true );
+  BOOST_CHECK_EQUAL( cp111 < cp1111, true );
+  BOOST_CHECK_EQUAL( cp1111 < cp111, false );
+  BOOST_CHECK_EQUAL( cp112 < cp112, false );
+  BOOST_CHECK_EQUAL( cp112 == cp112, true );
+  BOOST_CHECK_EQUAL( cp112 < cp115, true );
+}
+
+BOOST_AUTO_TEST_CASE( conserved_path_sort )
+{
+  vector<int> p111;
+  p111 += 1,1,1;
+  vector<int> p112;
+  p112 += 1,1,2;
+  vector<int> p115;
+  p115 += 1,1,5;
+  vector<int> p121;
+  p121 += 1,2,1; 
+
+  ConservedPath cp111(10, 1.0, p111);
+  ConservedPath cp112(10, 1.0, p112);
+  ConservedPath cp115(10, 1.0, p115);
+  ConservedPath cp121(10, 1.0, p121);
+  
+  list<ConservedPath> paths;
+  paths.push_back(cp115);
+  paths.push_back(cp121);
+  paths.push_back(cp112);
+  paths.push_back(cp111);
+  
+  paths.sort();
+  BOOST_REQUIRE_EQUAL( paths.size(), 4 );
+  list<ConservedPath>::const_iterator path_i = paths.begin();
+  
+  BOOST_CHECK_EQUAL( *path_i, cp111 ); ++path_i;
+  BOOST_CHECK_EQUAL( *path_i, cp112 ); ++path_i;
+  BOOST_CHECK_EQUAL( *path_i, cp115 ); ++path_i;
+  BOOST_CHECK_EQUAL( *path_i, cp121 );
+}
\ No newline at end of file

diff --git a/alg/test/test_mussa.cpp b/alg/test/test_mussa.cpp
index 74f8a9c658e55047f7a8b2e24e4502eafd99e423..7eb301572777dc2e9037cfbe4410c3fe6ea416e9 100644 (file)
--- a/alg/test/test_mussa.cpp
+++ b/alg/test/test_mussa.cpp
@@ -462,7 +462,6 @@ BOOST_AUTO_TEST_CASE( three_way_local_alignment )
       result_i != result.end();
       ++result_i)
   {
-    std::cout << "path ";
     ConservedPath::path_element first_element = *(result_i->begin());
     for (ConservedPath::path_type::iterator element_i = result_i->begin();
          element_i != result_i->end();
@@ -472,9 +471,7 @@ BOOST_AUTO_TEST_CASE( three_way_local_alignment )
       BOOST_CHECK_EQUAL( s0[*element_i], s1[*element_i] );
       BOOST_CHECK_EQUAL( s1[*element_i], s2[*element_i] );
       BOOST_CHECK_EQUAL( s0[*element_i], s2[*element_i] );
-      std::cout << *element_i << " " << s0[*element_i];
     }
-    std::cout << std::endl;
   }   
 }