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)
*/

top.__bfilter_obj = new Array();


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

        // store reference to this object for later (YAK)
        this.obj_count = top.__bfilter_obj.length;
        top.__bfilter_obj[this.obj_count] = this;

        // clear results html
        this.results_html = '';

        // show results after 0.2s
        this.timeout = 200;
        this.timeout_handle = 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 = self.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;
                this.results_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, user_filter) {
        if (!arr || typeof (user_filter) == "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,user_filter.length).toLowerCase();
                this.debug("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr);
                if (curr < user_filter) {
                        low = aTry + 1;
                        continue;
                }
                if (curr > user_filter) {
                        high = aTry - 1;
                        continue;
                }
                if (curr == user_filter) {
                        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 (user_filter) {
        this.debug("set timeout for "+this.obj_count+" to "+this.timeout);
        if (this.timeout_handle) {
                clearTimeout(this.timeout_handle);
                this.timeout_handle = null;
        }
        this.timeout_handle=setTimeout("top.__bfilter_obj["+this.obj_count+"].show_filter('"+user_filter.replace(/'/,"\\'")+"');", this.timeout);
        return true;
}

BFilter.prototype.show_filter = function (user_filter) {

        if (this.timeout_handle) {
                clearTimeout(this.timeout_handle);
                this.timeout_handle = null;
                this.debug("timeout cleared");
        }

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

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

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

        var user_filter_lc = user_filter.toLowerCase();

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

        // no part found
        if (! this.arr[part]) {
                this.show_status(" for <em>"+user_filter+"</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 (user_filter.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], user_filter_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,user_filter.length).toLowerCase() != user_filter_lc) {
                                        this.debug("loop exit at "+i);
                                        break;
                                }
                                this.result(this.arr[part][i]);
                                this.hits++;
                        }

                        this.results();
                }

        }

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