| home / programming / javascript / gr / column5 / 1 |    [previous][next] |
|
|
|
When the user types a character, the AutoComplete object gets a count of the number of strings that match the current value of the text box. If the count falls within acceptable bounds, the list of matching words is retrieved and added to the <div> element supplied in the constructor. Each word is enclosed within its own <div> element which offers two benefits: the list of words is displayed vertically (which is easy to read) and also it allows the code to trap the mousedown event (which is necessary for selecting the text to be inserted back into the text-box). As an aid to the user we can handle the mouseover and mouseout events to highlight the word under the mouse.
The code for the event handlers for the word-divs is as follows…
AutoComplete.prototype.onDivMouseDown = function()
{
// set the text-box value to
the word
this.AutoComplete.oText.value
= this.innerHTML;
}
AutoComplete.prototype.onDivMouseOver = function()
{
// assumes the existence of
a CSS style called AutoCompleteHighlight
this.className = "AutoCompleteHighlight";
}
AutoComplete.prototype.onDivMouseOut = function()
{
// assumes the existence of
a CSS style called AutoCompleteBackground
this.className = "AutoCompleteBackground";
}
A subtle effect happens when the user selects a word from the list. As the user clicks the mouse on a word, the mousedown event is handled and the text-box value is changed. When the user lifts the mouse button, the onblur event on the text-box is raised, causing the popup-div to then be hidden.
As mentioned earlier, the list of available words is stored in a data structure managed by the AutoCompleteDB class. The main purpose of this class is to optimize the generation of matching strings. If we were to keep the strings in an array, each time we need to generate a list of matches (i.e. every time the user types a character), each string in the array would need to be processed. While this might be fine for small arrays of a hundred or so strings, it would soon become cumbersome for larger amounts.
The AutoCompleteDB class is nothing more than a simple tree. The root node of the tree represents the start of the string and the rest represent single characters in each string. Storing a word in this tree is done by starting at the root, adding a node represents the first letter, then adding a node to that represents the second letter and so on. The last or deepest node in the sequence records that it is the end of a string. If a letter is already a child of a node when adding a new word, it is reused.
For example, if we wanted to store the names Aaron, Abe and Able we would end up with a tree that would look something like this:
Fig.3: Tree structure containing three names. The * symbol
denotes the end of a string and the numbers represent the number of strings
that terminate on that node or below.
The advantage of this tree structure can be shown in the above example by finding the number of strings that match the string “A”. Starting from the root node, move down to the ‘A’ node and we can see immediately that there are three matches. To match the string “Abe”, we follow the tree nodes down through ‘A’, ‘b’ and ‘e’ and see that there are two that match.
When many strings are added to the tree the benefits are considerable. Even when there are many thousands of strings in the tree, the number of nodes visited to count the number of matches is proportional to the size of the search string.
The AutoCompleteDB class implements this tree behavior…
{
// set initial values.
this.bEnd = false;
this.nCount = 0;
this.aStr = new Object;
}
Adding new strings is done using the following function…
AutoCompleteDB.prototype.add = function(str)
{
// increment the count value.
this.nCount++;
// if at the end of the string, flag this
node as an end point.
if ( str == "" )
this.bEnd = true;
else
{
// otherwise, pull
the first letter off the string
var letter = str.substring(0,1);
var rest = str.substring(1,str.length);
// and either create
a child node for it or reuse an old one.
if ( !this.aStr[letter]
) this.aStr[letter] = new AutoCompleteDB();
this.aStr[letter].add(rest);
}
}
Counting matches is handled with the getCount method…
AutoCompleteDB.prototype.getCount = function(str, bExact)
{
// if end of search string, return number
if ( str == "" )
if ( this.bEnd &&
bExact && (this.nCount == 1) ) return 0;
else return this.nCount;
// otherwise, pull the first letter off
the string
var letter = str.substring(0,1);
var rest = str.substring(1,str.length);
// and look for case-insensitive matches
var nCount = 0;
var lLetter = letter.toLowerCase();
if ( this.aStr[lLetter] )
nCount += this.aStr[lLetter].getCount(rest,
bExact && (letter == lLetter));
var uLetter = letter.toUpperCase();
if ( this.aStr[uLetter] )
nCount += this.aStr[uLetter].getCount(rest,
bExact && (letter == uLetter));
return nCount;
}
| home / programming / javascript / gr / column5 / 1 | [previous][next] |
Legal Notices, Licensing, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs 
Created: March 27, 2003
Revised: April 6, 2004
URL: URL: http://webreference.com/programming/javascript/gr/column5/1
