Re: Autocompletion
Re: Autocompletion
- Subject: Re: Autocompletion
- From: Wade Tregaskis <email@hidden>
- Date: Thu, 10 Jun 2004 21:09:36 +1000
Does anyone know of any good sample code for as-you-type
autocompletion? Where to place the complete as well as a quick
algorithm to throw out any non-matches since it seems a little
inefficient to check every keystroke.
Whatever you do, don't copy Apple's methods... an auto-completion
should require an explicit indication to select (e.g. pressing tab); it
shouldn't happen implicitly as in Safari et al... it makes it extremely
frustrating when you want to type a sub-section of an existing entry.
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 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 or backspaces. Building the tree initially can be
complex, which is why I think some implementations wait some amount of
time before doing it, hoping the user will enter at least the first few
characters, and they can thus avoid building the vast majority of the
tree.
Obtaining a list of potential completions is easy - just perform a
depth first ordered traversal of the hierarchy from the current point.
If the tree is static enough, you can easily cache this at various
points of the tree to aid performance.
You could do it using a series of NSDictionary's, although for
performance reasons you may end up having to move to a more manual
method. If you don't mind the use of ObjC++ you could use the STL map
class, as an intermediate step. Doing it at the basic C level will
allow you to use optimisations such as array-indexing for your "hash"
method, as well as perform aggressive caching using tricks like linked
lists through the tree... picture tinsel wrapped around a christmas
tree, if you want a pretty picture. :)
Wade Tregaskis (aim: wadetregaskis)
-- Sed quis custodiet ipsos custodes?
_______________________________________________
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.