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;
        // before all results
        this.html_full_pre = '<ul>';
        // before result
        this.html_pre = '<li><a href="';
        // id from result
        this.html_mid = '">';
        // title from result (which was searched also)
        this.html_post = '</a></li>';
        // after all results
        this.html_full_post = '</ul>';
        // highlight for every second row in results
        //this.html_hl_start = '<span style="background: #e0e0e0;">';
        //this.html_hl_end = '</span>';
        this.html_hl_start = '';
        this.html_hl_end = '';

        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 + "\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 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][1].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) {
                var html = '';
                for (i = 0; i < this.arr[part].length; i++) {
                        html += this.html_pre +
                                this.arr[part][i][0] +
                                this.html_mid +
                                (this.hits % 2 == 0 ? this.html_hl_start : '');
                        //if (this.debug()) { html += i+": "; }
                        html += this.arr[part][i][1] + 
                                (this.hits % 2 == 0 ? this.html_hl_end : '') +
                                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);

                        html = '';

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