Re: Autocompletion
Re: Autocompletion
- Subject: Re: Autocompletion
- From: Greg Titus <email@hidden>
- Date: Thu, 10 Jun 2004 15:44:56 -0700
On Jun 10, 2004, at 11:06 AM, Jim Witte wrote:
FWIW, auto-completion is very simple algorithmically. You might find
some useful information by looking at what's sometimes called "radix"
sorting. In your particular case, what you'll want to do
is sort all your potentials into groups based on their first letter,
then into further groups based on
This sounds like a Trie structure, or a Patricia tree.
their second, etc... forming a sparse hierarchal tree. You can then
maintain a pointer to the current branch position in the tree, which
you can adjust appropriately upon entry of further keys
caching using tricks like linked lists through the tree... picture
tinsel wrapped around a christmas tree, if you want a pretty picture.
:)
Standard tree threading (I know how it works for binary tree's, bit
sure about real k-arry tree that haven't been turned back into binary
trees).
I'm surprise someone hasn't written a specialized Cocoa class to do
this, possibly using the interface of NSDictionary..
OFTrie in OmniFoundation has an implementation of Tries for Cocoa.
Hope this helps,
- Greg
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.