Index of /~dpavlin/projects/bfilter

	Name	Last modified	Size	Description
	Parent Directory		-
	bfilter.js	2006-07-20 15:08	6.3K
	bfilter.html	2006-07-20 15:08	1.2K
	combo-test.js	2004-11-22 14:34	255K
	README.html	2004-11-22 14:34	4.0K
	combo2/	2004-11-22 00:30	-
	Makefile	2004-11-22 00:29	358
	hide.js	2004-11-22 00:29	2.6K
	hide.html	2004-11-22 00:29	3.3K
	down.gif	2004-11-22 00:29	850
	combo.html	2004-11-22 00:29	5.0K
	bfilter.pl	2004-11-22 00:29	2.2K
	pie.gif	2004-09-07 06:06	2.4K

JavaScript binary filter

Written by Dobrica Pavlinusic www.rot13.org/~dpavlin, 2004-11-21

I had a real-life problem: 17000 entries which I needed to filter in near-real-time to present to users just some items in unsigned list. You would probably say (as I would) that this is impossible in JavaScript.

First naive idea was to create gigantic 17000 element JavaScript array and filter through this. This took 45 minutes (no, it's not a mistake, and machine is pretty decent AMD Athlon box).

Something has to be done. First speedup was created by splitting huge 17000 element array into smaller slices (few characters) and require at least some letters before displaying result. As you will soon find out, searching array isn't the only problem: generating huge html (using DOM or innerHTML) can be very slow.
So, even if you manage to filter list fast enough, limiting filtering to begin of two or three characters will dramatically reduce about of html results that you have to create.

After initial implementation or split array, I was down from 45 minutes to just 5-7 minutes which was almost 10-fold improvement. But, it was still too slow for interactive use (which by old teletype standards should give response to users below 3 seconds).

But, I had another idea at mind: why not pre-sort all segments and use fast binary search? Of course, writing binary search in JavaScript isn't rocket science, so approach should be valid. Buy, was I wrong. I used bfilter.pl perl routine to produce my indexes. But, soon I found out that sort order in JavaScript differs from browser to browser depending on particular locale settings on machine.

While I could side-step that problem by writing localized version of sort (which I actually did), this was too slow for practical use.
So, I decided just to write unaccent in JavaScript and depend that sort order of 7-bit ASCII characters is same in all JavaScript implementations (current routines work for ISO-8859-2 encoding which is used here in Croatia and Eastern Europe).

Response time of binary search was below 3 seconds (and decent hardware again), so this problem was solved. But, Matko sow my code and said: Eh, I could write combobox using this!

JavaScript Combobox

Implementation of combobox has a little to do with me. Other than the fact that it uses bfilter described above, all the other great work is done my Matko Andjelinic. He has done initial implementation on which I hacked a bit, and that's why it's so ugly.

Matko then rewrote it in object-oriented JavaScript which produced current version of combobox.

He also did php implementation (which is nice if you have php application and want to create comboboxes on-the-fly from database). If you want to create static index file, you can use bfilter.pl script.

Installation

Depending on your usage (do you make static html for CD or dynamic web site?) you can use bfilter and checkbox in various ways. This is a toolbox. Some assembly is required to get full power of comboboxes in your web application.

There is no demo index supplied with this distribution. To create demo index file for static html examples (test.php does it for you), please type:

	make combo

License

All code is licenced under GPL v2 or later.

More restrictive licensing (if you don't want to share your changes) is available on request.