From 0ab5dc19d2a874aeda2b277f8f322db0cccc1d03 Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Wed, 20 Jun 2007 07:32:11 +0000
Subject: [PATCH] findIntervalsAtPoitns is now O(n)

---
 src/genealgorithms.cpp | 41 +++++++++++++----------------------------
 1 file changed, 13 insertions(+), 28 deletions(-)

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 4315cb3..d85cd8d 100644
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -116,34 +116,19 @@ std::vector<Interval> findIntervals(const GeneOrder& go){
  * Possibly move to cache result
  */
 std::vector<Interval> findIntervalsAtPoints(const vector<Interval>& intervals){
-	vector<Interval> points;
-	points.push_back(Interval(intervals.size(),intervals.size())); //Dummy interval to match point and index
-	for (size_t p = 1; p <= intervals.size(); ++p){
-		size_t f = 0;
-		size_t s = 0;
-		bool found = false;
-		size_t n = 0;
-		for (vector<Interval>::const_iterator i = intervals.begin(); i != intervals.end(); ++i, ++n){
-			if (i->first == p){
-				if (!found){
-					f = n;
-					found = true;
-				}else{
-					s = n;
-					break;
-				}
-			}
-			if (i->second == p){
-				if (!found){
-					f = n;
-					found = true;
-				}else{
-					s = n;
-					break;
-				}
-			}
-		}
-		points.push_back(Interval(f,s));
+	size_t max = intervals.size()+1;
+	vector<Interval> points(max,Interval(max,max));
+	size_t n = 0;
+	for (vector<Interval>::const_iterator i = intervals.begin(); i != intervals.end(); ++i, ++n){
+		if (points[i->first].first == max){
+			points[i->first].first = n;
+		}else
+			points[i->first].second = n;
+			
+		if (points[i->second].first == max){
+			points[i->second].first = n;
+		}else
+			points[i->second].second = n;
 	}
 	return points;
 
-- 
2.39.2