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.html_pre = '<a href="';
        this.html_mid = '">';
        this.html_post = '</a><br/>';
        this.html_full_pre = '';
        this.html_full_post = '';

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


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 + "\n";
        } else {
                results_div.innerHTML += this.html_full_pre + html +"\n" + this.html_full_post;
        }
}


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

        if (debug_div.innerHTML) {
                debug_div.innerHTML =+ html + "x<br>\n";
        } else {
                debug_div.innerHTML = html + "y<br>\n";
        }
}


// 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][1].substr(0,find.length).toLowerCase();
                this.debug("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;
        }
        this.debug("lastTry="+lastTry+"<br>");

        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+"'<br>");

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

        // full part? (optimization)
        if (find.length == this.min_len) {
                var html = '';
                for (var i = 0; i < this.arr[part].length; i++) {
                        html += this.html_pre +
                                this.arr[part][i][0] +
                                this.html_mid +
                                (this.hits % 2 == 0 ? '<span style="background: #e0e0e0">' : '');
                        //if (this.debug()) { html += i+": "; }
                        html += this.arr[part][i][1] + 
                                (this.hits % 2 == 0 ? '</span>' : '') +
                                this.html_post + "\n";
                        this.hits++;
                }
                this.results(html);
        } else {

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

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

                        var html = '';

                        for(var i = from ; i < this.arr[part].length ; i++) {
                                if (this.arr[part][i][1].substring(0,find.length).toLowerCase() != find_lc) {
                                        this.debug("loop exit at "+i);
                                        break;
                                }
                                html += this.html_pre +
                                        this.arr[part][i][0] +
                                        this.html_mid +
                                        (this.hits % 2 == 0 ? '<span style="background: #e0e0e0">' : '');
                                //if (this.debug()) { html += i+": "; }
                                html += this.arr[part][i][1] +
                                        (this.hits % 2 == 0 ? '</span>' : '') +
                                        this.html_post + "\n";
                                this.hits++;
                        }

                        this.results(html);
                }

        }

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

}


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