bfilter/trunk/bfilter.js

/*
   Fast filtering function using pre-sorted list elements
   Dobrica Pavlinusic, dpavlin@rot13.org 2004-09-06
   Matko Andjelinic, matko.andjelinic@gmail.com 2004-09-09 (contributed OO implementation)
*/


function BFilter(arr) {
        this.id_cache = Array();
        // total number of hits
        this.hits = 0;

        this.results_html = null;

        // this function is called for each result
        this.result = function (arr) {
                this.results_html += '<li><a href="'+arr[1]+'">'+
                        (this.hits % 2 == 0 ? '<span style="background: #e0e0e0;">' : '') +
                        arr[0] +
                        (this.hits % 2 == 0 ? '</span>' : '') +
                        '</a></li>';
                return true;
        }

        // this function is called when updating innerHTML with results
        this.display = function () {
                if (this.results_html) {
                        return '<ul>'+this.results_html+'</ul>';
                } else {
                        return null;
                }
        }


        if (! arr) {
                this.debug("ERROR: can't search empty array");
                return;
        }

        this.arr = arr;
        this.debug("index has "+this.arr.length+" parts");

        if (! arr.min_len) {
                this.results("ERROR: index structure problem");
                return;
        } else {
                this.min_len = arr.min_len;
        }

        this.debug("index part has "+this.min_len+" parts");

        this.show_status();

}

BFilter.prototype.element_id = function (id,no_alert) {
        if (this.id_cache[id]) {
                return this.id_cache[id];
        } else {
                var el = document.getElementById(id);
                if (el) {
                        this.id_cache[id] = el;
                        return el;
                } else {
                        if (! no_alert) {
                                alert("can't find element id: "+id);
                        } else {
                                // don't look it up again
                                this.id_cache[id] = null;
                        }
                }
        }
        return null;
}


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

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

BFilter.prototype.results = function (html,clean) {

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

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


BFilter.prototype.debug = function (html) {

        //return;

        // check if debugging is on
        if (! html) { return 1; }

        var debug_div = this.element_id("debug",1);
        if (! debug_div) { return null; }

        debug_div.innerHTML += html + "<br>\n";

        return null;
}


// modified binary search to find first element with substring
BFilter.prototype.binarySearch = function (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][0].substr(0,find.length).toLowerCase();
                this.debug("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr);
                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;
        }
        this.debug("lastTry="+lastTry);

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

BFilter.prototype.filter = function (document, find) {

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

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

        this.debug("filter: '"+find+"'");

        var find_lc = find.toLowerCase();

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

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

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

        var i;

        // full part? (optimization)
        if (find.length == this.min_len) {
                for (i = 0; i < this.arr[part].length; i++) {
                        this.result(this.arr[part][i]);
                        this.hits++;
                }
                this.results();
        } else {

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

                if (from != null) {
                
                        this.debug("loop "+from+" ... "+this.arr[part].length);

                        for(i = from ; i < this.arr[part].length ; i++) {
                                if (this.arr[part][i][0].substring(0,find.length).toLowerCase() != find_lc) {
                                        this.debug("loop exit at "+i);
                                        break;
                                }
                                this.result(this.arr[part][i]);
                                this.hits++;
                        }

                        this.results();
                }

        }

        this.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	Matko Andjelinic, matko.andjelinic@gmail.com 2004-09-09 (contributed OO implementation)
5	*/
6
7
8	function BFilter(arr) {
9	this.id_cache = Array();
10	// total number of hits
11	this.hits = 0;
12
13	this.results_html = null;
14
15	// this function is called for each result
16	this.result = function (arr) {
17	this.results_html += '<li><a href="'+arr[1]+'">'+
18	(this.hits % 2 == 0 ? '<span style="background: #e0e0e0;">' : '') +
19	arr[0] +
20	(this.hits % 2 == 0 ? '</span>' : '') +
21	'</a></li>';
22	return true;
23	}
24
25	// this function is called when updating innerHTML with results
26	this.display = function () {
27	if (this.results_html) {
28	return '<ul>'+this.results_html+'</ul>';
29	} else {
30	return null;
31	}
32	}
33
34
35	if (! arr) {
36	this.debug("ERROR: can't search empty array");
37	return;
38	}
39
40	this.arr = arr;
41	this.debug("index has "+this.arr.length+" parts");
42
43	if (! arr.min_len) {
44	this.results("ERROR: index structure problem");
45	return;
46	} else {
47	this.min_len = arr.min_len;
48	}
49
50	this.debug("index part has "+this.min_len+" parts");
51
52	this.show_status();
53
54	}
55
56	BFilter.prototype.element_id = function (id,no_alert) {
57	if (this.id_cache[id]) {
58	return this.id_cache[id];
59	} else {
60	var el = document.getElementById(id);
61	if (el) {
62	this.id_cache[id] = el;
63	return el;
64	} else {
65	if (! no_alert) {
66	alert("can't find element id: "+id);
67	} else {
68	// don't look it up again
69	this.id_cache[id] = null;
70	}
71	}
72	}
73	return null;
74	}
75
76
77	BFilter.prototype.show_status = function (status) {
78	var html;
79	if (this.hits > 0) {
80	html = "shown "+this.hits+" entries";
81	} else {
82	html = "no results";
83	}
84	if (! status) {
85	html = "Enter "+this.min_len+" letter"+(this.min_len == 1 ? '' : 's')+" to filter entries";
86	status = "";
87	}
88
89	var el = this.element_id("status");
90	el.innerHTML = html+status+"\n";
91	}
92
93	BFilter.prototype.results = function (html,clean) {
94
95	if (! html) { html = ""; }
96
97	// results_div.style.cursor = 'wait'; // 'auto'
98	var results_div = this.element_id("results");
99	if (clean) {
100	results_div.innerHTML = html;
101	} else {
102	html = this.display();
103	if (html) results_div.innerHTML += html;
104	}
105	}
106
107
108	BFilter.prototype.debug = function (html) {
109
110	//return;
111
112	// check if debugging is on
113	if (! html) { return 1; }
114
115	var debug_div = this.element_id("debug",1);
116	if (! debug_div) { return null; }
117
118	debug_div.innerHTML += html + "<br>\n";
119
120	return null;
121	}
122
123
124	// modified binary search to find first element with substring
125	BFilter.prototype.binarySearch = function (arr, find) {
126	if (!arr \|\| typeof (find) == "undefined" \|\| !arr.length) {
127	return null;
128	}
129	var low = 0;
130	var high = arr.length - 1;
131	var middlearr = parseInt(arr.length / 2);
132	var lastTry;
133	while (low <= high) {
134	var mid = (low + high) / 2;
135	var aTry = (mid < 1) ? 0 : parseInt(mid);
136
137	var curr = arr[aTry][0].substr(0,find.length).toLowerCase();
138	this.debug("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr);
139	if (curr < find) {
140	low = aTry + 1;
141	continue;
142	}
143	if (curr > find) {
144	high = aTry - 1;
145	continue;
146	}
147	if (curr == find) {
148	high = aTry - 1;
149	lastTry = aTry;
150	continue;
151	}
152	return aTry;
153	}
154	this.debug("lastTry="+lastTry);
155
156	if (typeof (lastTry) != "undefined") {
157	return lastTry;
158	} else {
159	return null;
160	}
161	}
162
163	BFilter.prototype.filter = function (document, find) {
164
165	this.results('',1);
166	this.hits = 0;
167
168	if (find.length < this.min_len) {
169	this.show_status();
170	return;
171	}
172
173	this.debug("filter: '"+find+"'");
174
175	var find_lc = find.toLowerCase();
176
177	var part = find_lc.substr(0,this.min_len);
178
179	// no part found
180	if (! this.arr[part]) {
181	this.show_status(" for <em>"+find+"</em><br>");
182	this.debug("no part "+part);
183	return;
184	}
185
186	// start anim icon
187	//results("<img src=\"pie.gif\"> Please wait, filtering...\n",1);
188
189	var i;
190
191	// full part? (optimization)
192	if (find.length == this.min_len) {
193	for (i = 0; i < this.arr[part].length; i++) {
194	this.result(this.arr[part][i]);
195	this.hits++;
196	}
197	this.results();
198	} else {
199
200	var from = this.binarySearch(this.arr[part], find_lc);
201
202	if (from != null) {
203
204	this.debug("loop "+from+" ... "+this.arr[part].length);
205
206	for(i = from ; i < this.arr[part].length ; i++) {
207	if (this.arr[part][i][0].substring(0,find.length).toLowerCase() != find_lc) {
208	this.debug("loop exit at "+i);
209	break;
210	}
211	this.result(this.arr[part][i]);
212	this.hits++;
213	}
214
215	this.results();
216	}
217
218	}
219
220	this.show_status(" for <em>"+find+"</em>");
221
222	}
223