--- trunk/bfilter.js	2004/09/07 08:33:53	1
+++ trunk/bfilter.js	2004/09/07 08:37:14	2
@@ -3,6 +3,8 @@
    Dobrica Pavlinusic, dpavlin@rot13.org 2004-09-06
 */
 
+var debug = 1;
+
 function bfilter_init() {
 	show_status();
 }
@@ -57,10 +59,48 @@
 	}
 }
 
+// modified binary search to find first element with substring
+function binarySearch(arr, find) {
+	if (!arr ||
+		typeof (arr) != "object" ||
+		typeof (find) == "undefined" || !arr.length) {
+		return null;
+	}
+	var low = 0;
+	var high = arr.length - 1;
+	var middlearr = parseInt(arr.length / 2);
+	var lastTry;
+	while (low <= high) {
+		var mid = (low + high) / 2;
+		var aTry = (mid < 1) ? 0 : parseInt(mid);
+	
+		var curr = arr[aTry].substr(0,find.length).toLowerCase();
+		if (debug) { results("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr+"<br>"); }
+		if (curr < find) {
+			low = aTry + 1;
+			continue;
+		}
+		if (curr > find) {
+			high = aTry - 1;
+			continue;
+		}
+		if (curr == find) {
+			high = aTry - 1;
+			lastTry = aTry;
+			continue;
+		}
+		return aTry;
+	}
+	if (debug) { results("lastTry="+lastTry+"<br>"); }
 
-function bfilter(document, id, find, arr) {
+	if (typeof (lastTry) != "undefined") {
+		return lastTry;
+	} else {
+		return null;
+	}
+}
 
-	var debug = 0;
+function bfilter(document, id, find, arr) {
 
 	results('',1);
 	hits = 0;
@@ -89,33 +129,31 @@
 	if (find.length == min_len) {
 		var html = '';
 		for (var i = 0; i < arr[part].length; i++) {
-			html += "<li>"+arr[part][i]+"</li>\n";
+			html += "<li>"+i+": "+arr[part][i]+"</li>\n";
 			hits++;
 		}
 		results(html);
 	} else {
 
-		for (var i = 0; i < arr[part].length; i++) {
-
-			var text = arr[part][i].toLowerCase();
-
-			if (debug) { results(part+" "+i+": "+text); }
+		var from = binarySearch(arr[part], find_lc);
 
-			// get li element by ID
-
-			if (debug) { results("cmp: "+text.substring(0,find.length)+" "+find+" ["+text+"]<br>\n"); }
-
-			if (text.substring(0,find.length) == find_lc) {
-				results("<li>"+text+"</li>\n");
+		if (from != null) {
+		
+			if (debug) { results("loop "+from+" ... "+arr[part].length)+"<br>\n"; }
+			for(var i = from ; i < arr[part].length ; i++) {
+				if (arr[part][i].substring(0,find.length).toLowerCase() != find_lc) {
+					break;
+				}
+				results(i+": "+arr[part][i]+"<br>\n");
 				hits++;
 			}
-
+		} else {
+			// clean results list
+//			results("",1);
 		}
 
 	}
 
-	// clean clock if no results
-	if (hits == 0) { results("",1); }
 	show_status(" for <em>"+find+"</em>");
 
 }