From 5645153bf9f986331307c548b284188a64b04bf5 Mon Sep 17 00:00:00 2001
From: Diane Trout <diane@caltech.edu>
Date: Sat, 14 Oct 2006 00:05:43 +0000
Subject: [PATCH] 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
---
 alg/conserved_path.cpp           | 26 ++++++++++++++
 alg/conserved_path.hpp           |  1 +
 alg/test/test_conserved_path.cpp | 58 ++++++++++++++++++++++++++++++++
 alg/test/test_mussa.cpp          |  3 --
 4 files changed, 85 insertions(+), 3 deletions(-)

diff --git a/alg/conserved_path.cpp b/alg/conserved_path.cpp
index 52e0c39..1edb374 100644
--- 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 5f7e003..7ff2661 100644
--- 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 f8d670c..e467c72 100644
--- 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 74f8a9c..7eb3015 100644
--- 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;
   }   
 }
 
-- 
2.30.2