robinson schensted algorithm implemented

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 57f719813a3c5b67e16199e4b20b6a774dc66add..fed42f37f1da57c3b0aeddd9e92f609b902ae090 100644 (file)
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -5,7 +5,7 @@ SET(CMAKE_VERBOSE_MAKEFILE OFF)
 ADD_DEFINITIONS(-Wall -O2)
 
 INCLUDE_DIRECTORIES(.)
-ADD_LIBRARY(GeneSort geneorder)
+ADD_LIBRARY(GeneSort geneorder genealgorithms)
 ADD_EXECUTABLE(genesort main.cpp)
 
 TARGET_LINK_LIBRARIES(genesort doublefann GeneSort)

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
new file mode 100644 (file)
index 0000000..154df35
--- /dev/null
+++ b/src/genealgorithms.cpp
@@ -0,0 +1,72 @@
+/***************************************************************************
+ *   Copyright (C) 2006 by Michael Andreen                                 *
+ *   andreen@student.chalmers.se                                           *
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ *   This program is distributed in the hope that it will be useful,       *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
+ *   GNU General Public License for more details.                          *
+ *                                                                         *
+ *   You should have received a copy of the GNU General Public License     *
+ *   along with this program; if not, write to the                         *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA          *
+ ***************************************************************************/
+
+#include "genealgorithms.h"
+#include "geneorder.h"
+
+#include <algorithm>
+#include <cstdlib>
+using namespace std;
+
+std::pair<int,int> longestSequences(const GeneOrder& go){
+}
+
+
+/*
+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){
+               int n = abs(*i);
+               bool added = false;
+               for (vector<vector<int> >::iterator vs = v.begin();
+                               vs != v.end(); ++vs){
+                       vector<int>::iterator bigger = upper_bound(vs->begin(),vs->end(),n);
+                       if ( bigger == vs->end()){
+                               vs->push_back(n);
+                               added = true;
+                               break;
+                       }else{
+                               swap(n,*bigger);
+                       }
+               }
+               if (!added){
+                       v.push_back(vector<int>());
+                       v.back().push_back(n);
+               }
+       }
+       return v;
+}

diff --git a/src/genealgorithms.h b/src/genealgorithms.h
new file mode 100644 (file)
index 0000000..4c519a7
--- /dev/null
+++ b/src/genealgorithms.h
@@ -0,0 +1,39 @@
+/***************************************************************************
+ *   Copyright (C) 2006 by Michael Andreen                                 *
+ *   andreen@student.chalmers.se                                           *
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ *   This program is distributed in the hope that it will be useful,       *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
+ *   GNU General Public License for more details.                          *
+ *                                                                         *
+ *   You should have received a copy of the GNU General Public License     *
+ *   along with this program; if not, write to the                         *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA          *
+ ***************************************************************************/
+
+#ifndef __GENEALGORITHMS_H__
+#define __GENEALGORITHMS_H__
+
+#include <vector>
+
+class GeneOrder;
+
+/**
+ * Returns the length of the longest increasing sequence and the longest
+ * decreasing sequence.
+ */
+std::pair<int,int> longestSequences(const GeneOrder& go);
+
+/**
+ */
+std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go);
+
+#endif
+

diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt
index c6f82f75e3518c057e139d4deeff017f60437b56..5540c09b9bcc5c5aaecaa09b8d51109e642a2a43 100644 (file)
--- a/src/test/CMakeLists.txt
+++ b/src/test/CMakeLists.txt
@@ -5,7 +5,7 @@ SET(CMAKE_VERBOSE_MAKEFILE OFF)
 ADD_DEFINITIONS(-Wall -O2)
 
 
-SET(TESTSRC geneordertest)
+SET(TESTSRC geneordertest genealgorithmstest)
 
 ADD_EXECUTABLE(tester main ${TESTSRC})
 TARGET_LINK_LIBRARIES(tester GeneSort cppunit)

diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
new file mode 100644 (file)
index 0000000..f7bd2fc
--- /dev/null
+++ b/src/test/genealgorithmstest.cpp
@@ -0,0 +1,72 @@
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+#include <geneorder.h>
+#include <genealgorithms.h>
+
+#include <algorithm>
+#include <iterator>
+using namespace std;
+
+/* 
+ * A test case that is designed to produce
+ * example errors and failures.
+ *
+ */
+
+#define TESTNAME GeneAlgorithmsTest
+
+
+class TESTNAME : public CPPUNIT_NS::TestFixture
+{
+  CPPUNIT_TEST_SUITE( TESTNAME );
+  CPPUNIT_TEST( testRobinsonSchensted );
+  CPPUNIT_TEST_SUITE_END();
+
+protected:
+               vector<int> _validPerm;
+               vector<int> _validPerm2;
+               vector<int> _validPerm3;
+               vector<int> _bigvalidPerm;
+               vector<int> _invalidPerm;
+
+public:
+
+       void setUp (){
+               int validPerm[] = {1,2,3,4};
+               _validPerm.assign(validPerm,validPerm+4);
+               int validPerm2[] = {0,-2,-1,4,3,5,-8,6,7,9};
+               _validPerm2.assign(validPerm2,validPerm2+10);
+               int validPerm3[] = {-3,1,2,4,6,5,7,-15,-13,-14,-12,-10,-11,-9,8};
+               _validPerm3.assign(validPerm3,validPerm3+15);
+               int invalidPerm[] = {1,3,4,5};
+               _invalidPerm.assign(invalidPerm,validPerm+4);
+               int test[] = {0,493,494,495,299,336,-490,-489,-488,-487,-486,-484,481,-482,503,-140,504,292,-507,97,-506,-505,154,157,509,510,511,512,513,514,515,-235,516,517,132,518,-308,519,520,521,523,525,526,383,384,-116,-119,529,530,531,532,533,433,-432,-431,-430,-429,-428,-426,-425,-424,-423,-422,-421,185,-420,-419,-418,-417,-416,-415,-414,-413,-412,-411,-410,-409,-408,-407,-406,-405,-404,-403,-402,-401,-400,-399,-398,-397,-396,-395,-394,-393,-63,-392,-391,-390,-238,-389,-388,-387,-386,385,-382,162,-381,-380,-379,-378,-377,-376,-375,-374,-58,-373,-372,-371,-370,-369,-368,-366,-365,-364,-363,-362,-359,-358,-357,-356,-355,-354,-353,-352,-351,-350,-349,-348,-347,-346,-84,-345,-344,-343,-329,-328,-67,146,-321,596,-316,-315,-314,-313,-311,-310,175,51,-309,-134,-342,-340,-339,-338,-337,-334,-333,-331,-194,-330,-306,-305,-302,-301,-300,-298,297,-296,-295,293,-291,294,-290,632,-40,-273,633,634,322,-323,-324,-327,-325,5,6,-7,-106,-216,-75,-215,-214,-213,-212,-211,188,-209,-208,-207,-206,-203,-202,-201,-200,141,-199,-198,-197,-92,93,94,95,98,-192,-191,-190,-196,-195,-193,36,37,39,-41,42,43,44,46,47,50,52,53,56,54,59,61,62,65,66,68,69,70,71,72,73,74,76,77,78,-60,79,80,81,82,85,86,88,-90,91,-189,-187,-186,-48,-184,-16,-182,-181,-180,-179,-178,64,-177,-176,-174,-159,-158,-170,-169,-156,-153,-152,-121,122,172,-617,128,130,127,129,137,138,139,113,114,-151,-150,-149,-148,-147,118,-145,-144,173,183,-163,-117,-161,124,123,126,125,-160,115,120,485,108,110,111,142,143,164,-19,-136,-135,-133,-131,-107,-168,-167,165,100,-105,-104,-102,-101,-35,-34,-33,-32,-20,-31,-30,-29,-28,-26,-25,-24,-23,-22,-21,-17,-55,13,14,15,-12,-11,-10,-252,-18,231,232,233,234,237,239,240,241,242,243,244,245,246,247,83,248,-219,220,221,222,223,224,225,227,228,229,230,38,254,255,256,257,258,-49,259,260,261,263,265,266,57,-361,-4,-3,-2,-1,-280,-281,96,-9,-8,267,-249,250,251,268,269,-360,270,271,272,528,166,274,275,276,277,278,279,282,283,171,284,285,286,287,264,253,452,-631,-630,-629,-628,-627,-626,-625,-451,-624,-623,-622,-621,-620,-619,-618,-87,-218,-616,-615,-614,-613,-612,-611,-610,-609,-608,-607,-606,-605,-604,-603,591,-602,27,-601,-600,-598,-599,-597,226,318,320,-326,-595,-594,-593,-592,-155,590,-589,-588,-587,-586,-585,-584,-583,-582,-581,-580,-579,-578,427,-577,-540,-560,-576,-575,-574,-573,-572,-571,-570,-569,-568,335,-567,-332,508,-112,-566,545,-565,204,-564,205,-103,563,-109,-562,-559,-558,-45,-557,-556,-312,-555,-554,-553,262,-552,-551,-317,-550,-549,-548,-547,-546,304,544,543,-542,-541,527,-236,-539,-538,-537,-522,483,-536,-436,-341,217,319,-289,-535,-534,-524,-288,99,434,435,-437,89,438,439,440,441,442,443,444,445,446,447,448,449,450,210,453,454,455,303,456,457,458,-561,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,367,496,497,498,499,500,501,502,476,477,478,-307,479,480,-491,492,635};
+
+               _bigvalidPerm.assign(test,test+636);
+       }
+
+protected:
+
+       void testRobinsonSchensted (){
+               GeneOrder go(_validPerm.begin(),_validPerm.end());
+               vector<vector<int> > v = robinsonSchensted(go);
+               CPPUNIT_ASSERT_EQUAL(1ul,v.size());
+               
+               int go11[] = {0,1,2,3,4};
+               CPPUNIT_ASSERT(equal(v[0].begin(),v[0].end(),go11));
+
+               GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
+               v = robinsonSchensted(go2);
+               int first[] = {0,1,3,5,6,7,9};
+               int second[] = {2,4,8};
+               CPPUNIT_ASSERT_EQUAL(2ul,v.size());
+               CPPUNIT_ASSERT(equal(v[0].begin(),v[0].end(),first));
+               CPPUNIT_ASSERT(equal(v[1].begin(),v[1].end(),second));
+       }
+
+};
+
+CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );
+
+#undef TESTNAME