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 (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);
                }

        }

        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 \|\| typeof (find) == "undefined" \|\| !arr.length) {
65	return null;
66	}
67	var low = 0;
68	var high = arr.length - 1;
69	var middlearr = parseInt(arr.length / 2);
70	var lastTry;
71	while (low <= high) {
72	var mid = (low + high) / 2;
73	var aTry = (mid < 1) ? 0 : parseInt(mid);
74
75	var curr = arr[aTry].substr(0,find.length).toLowerCase();
76	if (debug) { results("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr+"<br>"); }
77	if (curr < find) {
78	low = aTry + 1;
79	continue;
80	}
81	if (curr > find) {
82	high = aTry - 1;
83	continue;
84	}
85	if (curr == find) {
86	high = aTry - 1;
87	lastTry = aTry;
88	continue;
89	}
90	return aTry;
91	}
92	if (debug) { results("lastTry="+lastTry+"<br>"); }
93
94	if (typeof (lastTry) != "undefined") {
95	return lastTry;
96	} else {
97	return null;
98	}
99	}
100
101	function bfilter(document, id, find, arr) {
102
103	results('',1);
104	hits = 0;
105
106	if (find.length < min_len) {
107	show_status();
108	return;
109	}
110
111	if (debug) { results("filter: '"+find+"'<br>"); }
112
113	var find_lc = find.toLowerCase();
114
115	var part = find_lc.substr(0,min_len);
116
117	// no part found
118	if (! arr[part]) {
119	show_status(" for <em>"+find+"</em><br>");
120	return;
121	}
122
123	// start anim icon
124	//results("<img src=\"pie.gif\"> Please wait, filtering...\n",1);
125
126	// full part? (optimization)
127	if (find.length == min_len) {
128	var html = '';
129	for (var i = 0; i < arr[part].length; i++) {
130	html += "<li>";
131	if (debug) { $html += i+": "; }
132	html += arr[part][i]+"</li>\n";
133	hits++;
134	}
135	results(html);
136	} else {
137
138	var from = binarySearch(arr[part], find_lc);
139
140	if (from != null) {
141
142	if (debug) { results("loop "+from+" ... "+arr[part].length)+"<br>\n"; }
143
144	var html = '';
145
146	for(var i = from ; i < arr[part].length ; i++) {
147	if (arr[part][i].substring(0,find.length).toLowerCase() != find_lc) {
148	break;
149	}
150	if (debug) { html += i+": "; }
151	html += arr[part][i]+"<br>\n";
152	hits++;
153	}
154
155	results(html);
156	}
157
158	}
159
160	show_status(" for <em>"+find+"</em>");
161
162	}
163