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 = null;

        // show results after 0.2s
        this.timeout = 200;
        this.timeout_handle = 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) {
                alert("ERROR: index structure problem");
                return;
        } else {
                this.min_len = arr.min_len;
        }

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

        this.show_status();

        // show alert for non-existent elements?
        this.show_alert = 1;

}

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 && this.show_alert) {
                                this.show_alert = confirm("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 (query,no_hits) {
        var html = "";
        if (! no_hits) {
                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 = "";
                }
        }
        if (! query) {
                html = "Enter "+this.min_len+" letter"+(this.min_len == 1 ? '' : 's')+" to filter entries";
                query = "";
        } else {
                query = " for <em>"+query+"</em>";
        }

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

        return true;
}

// this function is called to clean old results list
BFilter.prototype.clear_results = function () {
        var results_div = this.element_id("results");
        results_div.innerHTML = '';
        this.results_html = '';
        return true;
}

// this function is called for each result
BFilter.prototype.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
BFilter.prototype.show_results = function () {
        var results_div = this.element_id("results");
        if (this.results_html) {
                results_div.innerHTML = '<ul>'+this.results_html+'</ul>';
        }
        return true;
}

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);
        this.debug("binarySearch: "+low+"-("+middlearr+")-"+high+" for "+user_filter);
        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+"-"+high+", "+aTry+"="+curr+" last="+lastTry);
                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) {

        this.show_status("Showing entries with <em>"+user_filter+"</em>\n");

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

        this.clear_results();
        this.hits = 0;

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

        var user_filter_lc = user_filter.toLowerCase();
        
        this.debug("filter: '"+user_filter_lc+"'");

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

        // no part found
        if (! this.arr[part]) {
                this.show_status(user_filter);
                this.debug("no part "+part);
                return;
        }

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

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

        }

        this.show_status(user_filter);

}

BFilter.prototype.show_all = function (user_filter) {

        this.show_status("Showing all entries\n");

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

        this.clear_results();
        this.hits = 0;

        for (part in this.arr) {
                // skip elements which are not really parts
                if (part == 'length' || part == 'min_len') continue;

                this.debug("part: "+part);
                for(var i = 0 ; i < this.arr[part].length ; i++) {
                        this.result(this.arr[part][i]);
                        this.hits++;
                }

                this.show_results();
        }

        this.show_status(user_filter);

}

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