bfilter/trunk/bfilter.js

/*
   Fast filtering function using pre-sorted list elements
   Dobrica Pavlinusic, dpavlin@rot13.org 2004-09-06
*/

var debug = 0;

function bfilter_init() {
        show_status();
}

var id_cache = Array();

function element_id(id) {
        if (id_cache[id]) {
                return id_cache[id];
        } else {
                var el = document.getElementById(id);
                if (el) {
                        id_cache[id] = el;
                        return el;
                } else {
                        alert("can't find element id: "+id);
                }
        }
}

// total number of hits
var hits = 0;

function show_status(status) {
        var html;
        if (hits > 0) {
                html = "shown "+hits+" entries";
        } else {
                html = "no results";
        }
        if (! status) {
                html = "Enter "+min_len+" letter"+(min_len == 1 ? '' : 's')+" to filter entries";
                status = "";
        }

        var el = element_id("status");
        el.innerHTML = html+status+"\n";
}

var wait = 0;

function results(html,clean) {

        if (! html) { html = ""; }

        // results_div.style.cursor = 'wait'; // 'auto'
        var results_div = element_id("results");
        if (clean) {
                results_div.innerHTML = html+"\n";
        } else {
                results_div.innerHTML += html+"\n";
        }
}

// 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>"); }

        if (typeof (lastTry) != "undefined") {
                return lastTry;
        } else {
                return null;
        }
}

function bfilter(document, id, find, arr) {

        results('',1);
        hits = 0;

        if (find.length < min_len) {
                show_status();
                return;
        }

        if (debug) { results("filter: '"+find+"'<br>"); }

        var find_lc = find.toLowerCase();

        var part = find_lc.substr(0,min_len);

        // no part found
        if (! arr[part]) {
                show_status(" for <em>"+find+"</em><br>");
                return;
        }

        // start anim icon
        //results("<img  src=\"pie.gif\">&nbsp;Please wait, filtering...\n",1);

        // full part? (optimization)
        if (find.length == min_len) {
                var html = '';
                for (var i = 0; i < arr[part].length; i++) {
                        html += "<li>";
                        if (debug) { $html += i+": "; }
                        html += arr[part][i]+"</li>\n";
                        hits++;
                }
                results(html);
        } else {

                var from = binarySearch(arr[part], find_lc);

                if (from != null) {
                
                        if (debug) { results("loop "+from+" ... "+arr[part].length)+"<br>\n"; }

                        var html = '';

                        for(var i = from ; i < arr[part].length ; i++) {
                                if (arr[part][i].substring(0,find.length).toLowerCase() != find_lc) {
                                        break;
                                }
                                if (debug) { html += i+": "; }
                                html += arr[part][i]+"<br>\n";
                                hits++;
                        }

                        results(html);
                } else {
                        // clean results list
//                      results("",1);
                }

        }

        show_status(" for <em>"+find+"</em>");

}

1	/*
2	Fast filtering function using pre-sorted list elements
3	Dobrica Pavlinusic, dpavlin@rot13.org 2004-09-06
4	*/
5
6	var debug = 0;
7
8	function bfilter_init() {
9	show_status();
10	}
11
12	var id_cache = Array();
13
14	function element_id(id) {
15	if (id_cache[id]) {
16	return id_cache[id];
17	} else {
18	var el = document.getElementById(id);
19	if (el) {
20	id_cache[id] = el;
21	return el;
22	} else {
23	alert("can't find element id: "+id);
24	}
25	}
26	}
27
28	// total number of hits
29	var hits = 0;
30
31	function show_status(status) {
32	var html;
33	if (hits > 0) {
34	html = "shown "+hits+" entries";
35	} else {
36	html = "no results";
37	}
38	if (! status) {
39	html = "Enter "+min_len+" letter"+(min_len == 1 ? '' : 's')+" to filter entries";
40	status = "";
41	}
42
43	var el = element_id("status");
44	el.innerHTML = html+status+"\n";
45	}
46
47	var wait = 0;
48
49	function results(html,clean) {
50
51	if (! html) { html = ""; }
52
53	// results_div.style.cursor = 'wait'; // 'auto'
54	var results_div = element_id("results");
55	if (clean) {
56	results_div.innerHTML = html+"\n";
57	} else {
58	results_div.innerHTML += html+"\n";
59	}
60	}
61
62	// modified binary search to find first element with substring
63	function binarySearch(arr, find) {
64	if (!arr \|\|
65	typeof (arr) != "object" \|\|
66	typeof (find) == "undefined" \|\| !arr.length) {
67	return null;
68	}
69	var low = 0;
70	var high = arr.length - 1;
71	var middlearr = parseInt(arr.length / 2);
72	var lastTry;
73	while (low <= high) {
74	var mid = (low + high) / 2;
75	var aTry = (mid < 1) ? 0 : parseInt(mid);
76
77	var curr = arr[aTry].substr(0,find.length).toLowerCase();
78	if (debug) { results("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr+"<br>"); }
79	if (curr < find) {
80	low = aTry + 1;
81	continue;
82	}
83	if (curr > find) {
84	high = aTry - 1;
85	continue;
86	}
87	if (curr == find) {
88	high = aTry - 1;
89	lastTry = aTry;
90	continue;
91	}
92	return aTry;
93	}
94	if (debug) { results("lastTry="+lastTry+"<br>"); }
95
96	if (typeof (lastTry) != "undefined") {
97	return lastTry;
98	} else {
99	return null;
100	}
101	}
102
103	function bfilter(document, id, find, arr) {
104
105	results('',1);
106	hits = 0;
107
108	if (find.length < min_len) {
109	show_status();
110	return;
111	}
112
113	if (debug) { results("filter: '"+find+"'<br>"); }
114
115	var find_lc = find.toLowerCase();
116
117	var part = find_lc.substr(0,min_len);
118
119	// no part found
120	if (! arr[part]) {
121	show_status(" for <em>"+find+"</em><br>");
122	return;
123	}
124
125	// start anim icon
126	//results("<img src=\"pie.gif\"> Please wait, filtering...\n",1);
127
128	// full part? (optimization)
129	if (find.length == min_len) {
130	var html = '';
131	for (var i = 0; i < arr[part].length; i++) {
132	html += "<li>";
133	if (debug) { $html += i+": "; }
134	html += arr[part][i]+"</li>\n";
135	hits++;
136	}
137	results(html);
138	} else {
139
140	var from = binarySearch(arr[part], find_lc);
141
142	if (from != null) {
143
144	if (debug) { results("loop "+from+" ... "+arr[part].length)+"<br>\n"; }
145
146	var html = '';
147
148	for(var i = from ; i < arr[part].length ; i++) {
149	if (arr[part][i].substring(0,find.length).toLowerCase() != find_lc) {
150	break;
151	}
152	if (debug) { html += i+": "; }
153	html += arr[part][i]+"<br>\n";
154	hits++;
155	}
156
157	results(html);
158	} else {
159	// clean results list
160	// results("",1);
161	}
162
163	}
164
165	show_status(" for <em>"+find+"</em>");
166
167	}
168