--- trunk/bfilter.js 2004/09/07 19:03:11 8 +++ trunk/bfilter.js 2004/09/10 12:42:58 11 @@ -1,66 +1,111 @@ /* 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) */ -var debug = 0; -function bfilter_init() { - show_status(); -} +function BFilter(arr) { + this.id_cache = Array(); + // total number of hits + this.hits = 0; + this.html_pre = ''; + this.html_post = '
'; + this.html_full_pre = ''; + this.html_full_post = ''; + + if (! arr) { + this.debug("ERROR: can't search empty array"); + return; + } -var id_cache = Array(); + this.arr = arr; + this.debug("index has "+this.arr.length+" parts"); -function element_id(id) { - if (id_cache[id]) { - return id_cache[id]; + 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) { - id_cache[id] = el; + this.id_cache[id] = el; return el; } else { - alert("can't find element id: "+id); + if (! no_alert) { + alert("can't find element id: "+id); + } else { + // don't look it up again + this.id_cache[id] = null; + } } } } -// total number of hits -var hits = 0; -function show_status(status) { +BFilter.prototype.show_status = function (status) { var html; - if (hits > 0) { - html = "shown "+hits+" entries"; + if (this.hits > 0) { + html = "shown "+this.hits+" entries"; } else { html = "no results"; } if (! status) { - html = "Enter "+min_len+" letter"+(min_len == 1 ? '' : 's')+" to filter entries"; + html = "Enter "+this.min_len+" letter"+(this.min_len == 1 ? '' : 's')+" to filter entries"; status = ""; } - var el = element_id("status"); + var el = this.element_id("status"); el.innerHTML = html+status+"\n"; } -var wait = 0; - -function results(html,clean) { +BFilter.prototype.results = function (html,clean) { if (! html) { html = ""; } // results_div.style.cursor = 'wait'; // 'auto' - var results_div = element_id("results"); + var results_div = this.element_id("results"); if (clean) { - results_div.innerHTML = html+"\n"; + 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
\n"; } else { - results_div.innerHTML += html+"\n"; + debug_div.innerHTML = html + "y
\n"; } } + // modified binary search to find first element with substring -function binarySearch(arr, find) { +BFilter.prototype.binarySearch = function (arr, find) { if (!arr || typeof (find) == "undefined" || !arr.length) { return null; } @@ -73,7 +118,7 @@ var aTry = (mid < 1) ? 0 : parseInt(mid); var curr = arr[aTry][1].substr(0,find.length).toLowerCase(); - if (debug) { results("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr+"
"); } + this.debug("low="+low+" high="+high+" lastTry="+lastTry+" "+aTry+": "+curr+"
"); if (curr < find) { low = aTry + 1; continue; @@ -89,7 +134,7 @@ } return aTry; } - if (debug) { results("lastTry="+lastTry+"
"); } + this.debug("lastTry="+lastTry+"
"); if (typeof (lastTry) != "undefined") { return lastTry; @@ -98,25 +143,26 @@ } } -function bfilter(document, id, find, arr) { +BFilter.prototype.filter = function (document, find) { - results('',1); - hits = 0; + this.results('',1); + this.hits = 0; - if (find.length < min_len) { - show_status(); + if (find.length < this.min_len) { + this.show_status(); return; } - if (debug) { results("filter: '"+find+"'
"); } + this.debug("filter: '"+find+"'
"); var find_lc = find.toLowerCase(); - var part = find_lc.substr(0,min_len); + var part = find_lc.substr(0,this.min_len); // no part found - if (! arr[part]) { - show_status(" for "+find+"
"); + if (! this.arr[part]) { + this.show_status(" for "+find+"
"); + this.debug("no part "+part); return; } @@ -124,51 +170,53 @@ //results(" Please wait, filtering...\n",1); // full part? (optimization) - if (find.length == min_len) { + if (find.length == this.min_len) { var html = ''; - for (var i = 0; i < arr[part].length; i++) { - html += html_pre + - arr[part][i][0] + - html_mid + - (hits % 2 == 0 ? '' : ''); - if (debug) { $html += i+": "; } - html += arr[part][i][1] + - (hits % 2 == 0 ? '' : '') + - html_post + "\n"; - hits++; + 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 ? '' : ''); + //if (this.debug()) { html += i+": "; } + html += this.arr[part][i][1] + + (this.hits % 2 == 0 ? '' : '') + + this.html_post + "\n"; + this.hits++; } - results(html); + this.results(html); } else { - var from = binarySearch(arr[part], find_lc); + var from = this.binarySearch(this.arr[part], find_lc); if (from != null) { - if (debug) { results("loop "+from+" ... "+arr[part].length)+"
\n"; } + this.debug("loop "+from+" ... "+this.arr[part].length)+"
\n"; var html = ''; - for(var i = from ; i < arr[part].length ; i++) { - if (arr[part][i][1].substring(0,find.length).toLowerCase() != find_lc) { + 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 += html_pre + - arr[part][i][0] + - html_mid + - (hits % 2 == 0 ? '' : ''); - if (debug) { html += i+": "; } - html += arr[part][i][1] + - (hits % 2 == 0 ? '' : '') + - html_post + "\n"; - hits++; + html += this.html_pre + + this.arr[part][i][0] + + this.html_mid + + (this.hits % 2 == 0 ? '' : ''); + //if (this.debug()) { html += i+": "; } + html += this.arr[part][i][1] + + (this.hits % 2 == 0 ? '' : '') + + this.html_post + "\n"; + this.hits++; } - results(html); + this.results(html); } } - show_status(" for "+find+""); + this.show_status(" for "+find+""); } +