Filter list as you type interface like on an iPod

[BCSWebStudio]

I'm working on a filter-as-you-type list like on an iPod: partial matches show below the text field, and as you type, your search gets more specific and less strings show in the list below. This is to be implemented in a name-lookup. My problem is both with algorithm and speed.

Current setup is this:
-One text field, one ListBox. This is the search setup.
-One hidden text field, one ListBox. This is the "last search string" and original, complete list of names. On init, this list populates the filtered search ListBox 1:1.

As the user proceeds to type a name in the search box, the list below gets filtered like this:
- first check that the previously typed text is contained in the current/new search string. If it is, we know to simply filter out the mismatches and trim the list. If it is not, then this is a new search (or backed-up a character), and the entire list is recreated based on the hidden, original list.
- To recreate the list: Clear the ListBox and copy 1:1 from the hidden original.
- To remove mismatches: Loop the entire ListBox and remove items that don't match with .removeItemAt().

This is incredibly slow on my 1.6GHz machine, and on my 700MHz production kiosk, it is impossible. In addition to that, something in my implementation is buggy, and it seems to miss every other name upon filtering...

Would someone please take a crack at it and advise me where I'm going wrong or even offer a better way? Oh, and I have commented out removeItemAt in order to verify that that's a slow-down: the thing is quick as lightening when not having to alter the ListBox items...

function onSearchChange(str) {
	// if search text contains previously searched text, remove items that do not contain search text,
	//	otherwise, rebuild list based on search
	var stxt:String = txtSearch.text.toLowerCase();
	var prevstxt:String = txtPrevSearch.text;
	var arrstxt:Array = stxt.split(" ");
	//trace("\"" + stxt + "\"" + "\t" + "\"" + prevstxt + "\"");
	if (stxt.indexOf(prevstxt) > -1) {
		// search text contains previous search-- remove filtered
		var curnam:String = "";
		// loop thru entire current list
		var numitems:Number = liNames.length;
		for (var i=0; i < numitems; i++) {
			curnam = liNames.getItemAt(i).label.toLowerCase();
			// loop thru all space-delimited individual search words; compare against current item in list
			if (curnam.indexOf(stxt) < 0) {
				//trace("removed " + curnam + " for " + stxt);
				liNames.removeItemAt(i);
				numitems--; i--;	// reset counters: number of items and current, b/c removeItemAt is immediate
			}
		}
//		trace("Removed item(s)");
	} else {
		// search text does not contain prev search (backspace, replace, etc)-- rebuild list based on current search
		liNames.removeAll();
		var curnam:String = "";
		var curitem;
		for (var i=0; i < liNamesSrc.length; i++) {
			curitem = liNamesSrc.getItemAt(i);
			curnam = curitem.label.toLowerCase();
			var blninc:Boolean = false;
			// loop thru all space-delimited individual search words; compare against current item in list
			// - only add item if all search terms are contained within current item (like an iterative AND)
			for (stxti in arrstxt) {
				if (curnam.indexOf(arrstxt[stxti]) > -1) {
					blninc = true;
					continue;
				} else {
					blninc = false;
					break
				}
			}
			if (blninc) {
				liNames.addItem(curitem);
			}
		}
		trace("rebuilt list.");

	}
	txtPrevSearch.text = stxt;
	txtCnt.text = liNames.length;
}

[random]

i am pretty sure the reason it is so slow is because of indexOf.

instead try using something like:

if(substring(curnam,0,length(stxt)) == stxt){
blninc = true;
continue;
} else {
blninc = false;
break
}
if (blninc) {
liNames.addItem(curitem);
}

Plus this method gives you true results, as apposed to before you might get elephant if you typed in ph. In the exapmple above it matches the begining of the string.

[BCSWebStudio]

Thanks for the quick response-- Goodness!
I am actually wanting to allow partial matches: "atr" should keep "patrick". In order for sub(0..) to work, I would need to further split both needle and haystack strings on spaces and search them individually, I think. I am about ready to just do a basic "type-then-click-search" iterative solution...

[random]

It would be alot more practical and efficient... But either way it is going to have some lag time.

[BCSWebStudio]

Just an update on this ill quest: I am certain that the lag is the removeItemAt method-- again, commenting it out is like lightning. Also, I have tried converting the ListBox to use setDataProvider with an array of data and using Array.splice to pluck the values-- just as slow.

I guess this means only one thing: implement the iterative "type and click search" way. Grr..