From e7953f0050007cd1999d64d985d0a063b9ddc99b Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Tue, 19 Jun 2007 08:27:42 +0000
Subject: [PATCH] adding countCycles, findComponents, findIntervals
 declaration, with initial tests

---
 src/genealgorithms.cpp          | 19 +++++++++++++++++++
 src/genealgorithms.h            | 23 +++++++++++++++++++++++
 src/test/genealgorithmstest.cpp | 30 ++++++++++++++++++++++++++++--
 3 files changed, 70 insertions(+), 2 deletions(-)

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index b2d7fa6..7dc832f 100644
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -22,6 +22,7 @@
 #include "geneorder.h"
 
 #include <algorithm>
+#include <set>
 #include <cstdlib>
 using namespace std;
 
@@ -53,3 +54,21 @@ std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go){
 	}
 	return v;
 }
+
+int countCycles(const GeneOrder& go){
+	int cycles = 0;
+	set<size_t> marked;
+	for (size_t p = 1; p < go.size() - 1; ++p){
+		if (marked.find(p) != marked.end())
+			continue;
+	}
+	return cycles;
+}
+
+std::vector<Component> findComponents(const GeneOrder& go){
+	return vector<Component>();
+}
+
+std::vector<Interval> findIntervals(const GeneOrder& go){
+	return vector<Interval>();
+}
diff --git a/src/genealgorithms.h b/src/genealgorithms.h
index 4c519a7..4c938e3 100644
--- a/src/genealgorithms.h
+++ b/src/genealgorithms.h
@@ -25,6 +25,14 @@
 
 class GeneOrder;
 
+struct Component{
+	Component(int b,int e,int s):begin(b),end(e),sign(s){}
+	int begin;
+	int end;
+	int sign;
+};
+typedef std::pair<size_t,size_t> Interval;
+
 /**
  * Returns the length of the longest increasing sequence and the longest
  * decreasing sequence.
@@ -35,5 +43,20 @@ std::pair<int,int> longestSequences(const GeneOrder& go);
  */
 std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go);
 
+/**
+ * Counts the number of cycles in the gene order.
+ */
+int countCycles(const GeneOrder& go);
+
+/**
+ * Finds the components in the gene order.
+ */
+std::vector<Component> findComponents(const GeneOrder& go);
+
+/**
+ * Find intervals.
+ */
+std::vector<Interval> findIntervals(const GeneOrder& go);
+
 #endif
 
diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
index 55ebb58..50a5c73 100644
--- a/src/test/genealgorithmstest.cpp
+++ b/src/test/genealgorithmstest.cpp
@@ -22,6 +22,8 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testRobinsonSchensted );
   CPPUNIT_TEST( testLongestSequences );
+  CPPUNIT_TEST( testFindIntervals );
+  CPPUNIT_TEST( testCountCycles );
   CPPUNIT_TEST_SUITE_END();
 
 protected:
@@ -74,11 +76,35 @@ protected:
 		
 		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);
 	}
+	void testFindIntervals (){
+		GeneOrder go(_validPerm.begin(),_validPerm.end());
+		vector<pair<size_t,size_t> > v = findIntervals(go);
+		CPPUNIT_ASSERT_EQUAL(4ul,v.size());
+		Interval go10(1,1);
+		Interval go12(3,3);
+		CPPUNIT_ASSERT(go10 == v[0]);
+		CPPUNIT_ASSERT(go12 == v[2]);
+		
+		GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
+		v = findIntervals(go);
+		CPPUNIT_ASSERT_EQUAL(9ul,v.size());
+		Interval go20(1,3);
+		Interval go22(1,4);
+		CPPUNIT_ASSERT(go20 == v[0]);
+		CPPUNIT_ASSERT(go22 == v[2]);
+	}
+	void testCountCycles (){
+		GeneOrder go(_validPerm.begin(),_validPerm.end());
+		int c = countCycles(go);
+		CPPUNIT_ASSERT_EQUAL(4,c);
+		
+		GeneOrder go2(_validPerm3.begin(),_validPerm3.end());
+		c = countCycles(go2);
+		CPPUNIT_ASSERT_EQUAL(6,c);
+	}
 
 };
 
-- 
2.39.2