longest increasing and decreasing subsequences

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 154df354bc346592f53a1373b49bbc1c72a0b79d..b2d7fa6132b0463ee9a1b1cdf8f240bddf1204f9 100644 (file)
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -26,27 +26,10 @@
 using namespace std;
 
 std::pair<int,int> longestSequences(const GeneOrder& go){
 using namespace std;
 
 std::pair<int,int> longestSequences(const GeneOrder& go){

+       vector<vector<int> > v = robinsonSchensted(go);
+       return pair<int,int>(v[0].size(),v.size());

 }
 
 }
 

-
-/*
-robSche2 :: [Int] -> [[Int]] -> [[Int]]
-robSche2 [] ys = ys
-robSche2 (x:xs) ys = robSche2 xs $ robSche4 x ys
-
-robSche3 :: Int -> [Int] -> (Maybe Int,[Int])
-robSche3 x ys = let yless = [y | y <- ys, y < x] in
-       let ymore = [y | y <- ys, y > x] in
-               case ymore of
-                       [] -> (Nothing, yless++[x])
-                       (y:ys) -> (Just y, yless++(x:ys))
-
-robSche4 :: Int -> [[Int]] -> [[Int]]
-robSche4 x [] = [[x]]
-robSche4 x (y:ys) = case robSche3 x y of
-       (Nothing, y) -> y:ys
-       (Just x, y) -> y:robSche4 x ys
-*/

 std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go){
        vector<vector<int> > v;
        for (GeneOrder::iterator i = go.begin(); i != go.end(); ++i){
 std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go){
        vector<vector<int> > v;
        for (GeneOrder::iterator i = go.begin(); i != go.end(); ++i){

diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
index f7bd2fc13bf3d0c7551536f03db2c348c442b127..55ebb58db7085ff5cbeb242d7ce7b3057d97659c 100644 (file)
--- a/src/test/genealgorithmstest.cpp
+++ b/src/test/genealgorithmstest.cpp
@@ -21,6 +21,7 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
 {
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testRobinsonSchensted );
 {
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testRobinsonSchensted );

+  CPPUNIT_TEST( testLongestSequences );

   CPPUNIT_TEST_SUITE_END();
 
 protected:
   CPPUNIT_TEST_SUITE_END();
 
 protected:


@@ -65,6 +66,20 @@ protected:
                CPPUNIT_ASSERT(equal(v[1].begin(),v[1].end(),second));
        }
 
                CPPUNIT_ASSERT(equal(v[1].begin(),v[1].end(),second));
        }
 

+       void testLongestSequences (){
+               GeneOrder go(_validPerm.begin(),_validPerm.end());
+               pair<int,int> p = longestSequences(go);
+               CPPUNIT_ASSERT_EQUAL(5,p.first);
+               CPPUNIT_ASSERT_EQUAL(1,p.second);
+               
+               GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
+               p = longestSequences(go2);
+               int first[] = {0,1,3,5,6,7,9};
+               int second[] = {2,4,8};
+               CPPUNIT_ASSERT_EQUAL(7,p.first);
+               CPPUNIT_ASSERT_EQUAL(2,p.second);
+       }
+

 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );
 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );