From 778905d507474784ec6be37fe8f2e5d9c179ae59 Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Wed, 20 Jun 2007 07:19:02 +0000
Subject: [PATCH] findIntervals is now O(n)

---
 src/genealgorithms.cpp          | 36 +++++++++------------------------
 src/test/genealgorithmstest.cpp |  2 ++
 2 files changed, 11 insertions(+), 27 deletions(-)

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 24e7b43..4315cb3 100644
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -96,35 +96,17 @@ std::vector<Component> findComponents(const GeneOrder& go){
 }
 
 /**
- * TODO: Think of a better than O(n^2) implementation
- * Possibly move it to GeneOrder too
+ * 
  */
 std::vector<Interval> findIntervals(const GeneOrder& go){
-	vector<Interval> intervals;
-	for (size_t i = 0; i < go.size() - 1; ++i){
-		size_t f = 0;
-		size_t s = 0;
-		bool found = false;
-		size_t n = 0;
-		for (GeneOrder::iterator g = go.begin(); g != go.end(); ++g, ++n){
-			if (static_cast<size_t>(abs(*g)) == i){
-				f = n;
-				if (*g >= 0)
-					++f;
-				if (found)
-					break;
-				found = true;
-			}
-			if(static_cast<size_t>(abs(*g)) == i+1){
-				s = n;
-				if (*g < 0)
-					++s;
-				if (found)
-					break;
-				found = true;
-			}
-		}
-		intervals.push_back(Interval(f,s));
+	vector<Interval> intervals(go.size()-1,Interval(go.size(),go.size()));
+	size_t n = 0;
+	for (GeneOrder::iterator g = go.begin(); g != go.end(); ++g, ++n){
+			size_t i = abs(*g);
+			if (i < go.size() - 1)
+				intervals[i].first = n + (*g >= 0 ? 1 : 0);
+			if (i > 0)
+				intervals[i-1].second = n + (*g < 0 ? 1 : 0);
 	}
 	return intervals;
 }
diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
index b06f416..1d7f2d0 100644
--- a/src/test/genealgorithmstest.cpp
+++ b/src/test/genealgorithmstest.cpp
@@ -94,8 +94,10 @@ protected:
 		CPPUNIT_ASSERT_EQUAL(16ul,v.size());
 		Interval go20(1,2);
 		Interval go22(4,2);
+		Interval go215(8,16);
 		CPPUNIT_ASSERT(go20 == v[0]);
 		CPPUNIT_ASSERT(go22 == v[2]);
+		CPPUNIT_ASSERT(go215 == v[15]);
 	}
 	void testFindIntervalsAtPoints (){
 		GeneOrder go(_validPerm.begin(),_validPerm.end());
-- 
2.39.2