Author Archive: zqi

A lightweight auto-complete ActionScript example with a trie

This article was originally written in English. Text in other languages was provided by machine translation.


Auto-complete functionality is used widely over the internet and mobile apps. A lot of websites and apps try to complete your input as soon as you start typing.  In this post, I would like to introduce a simple ActionScript auto-complete solution by using trie data structure.

A trie is an ordered tree data structure that is used to store an associative array. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Starting from the root node, you can check if a word exists in the trie easily by following pointers corresponding to the letters in the target word. Trie is a well-known data structure in computer science; you can find the detailed information about trie through Wikipedia.

Here is a simple trie implementation in ActionScript:

/**
* An simple data structure to store and look up words.
* @see http://en.wikipedia.org/wiki/Trie for additional details.
*/

public class Trie {
private var _rootKeys:Array;
public function Trie():void {
_rootKeys=[];
}

/**
* Return a list of words which have the given prefix.
*/

public function get(prefix:String):Array {
var results:Array=[];
var letter:String=prefix.substr(0,1);
var root:TrieNode=_rootKeys[letter];
if (root) {
getWordList(prefix, 1, root, results);
}
return results;
}

/**
* Add a word to the object which can be matched as a prefix.
*/

public function add(word:String):void {
var letter:String=word.substr(0,1);
var root:TrieNode=_rootKeys[letter];


if (!root) {
root=createNode(letter);
_rootKeys[letter]=root;
}
insertWord(word, 1, root);
}


private function traverse(root:TrieNode, results:Array, prefix:String):void {
if(root.children) {
for each( var c:TrieNode in root.children ) {
var node:TrieNode = c as TrieNode;
if( node.word ) {
results.push( prefix + node.value);
}
traverse(node, results, prefix+node.value );
}
}
}


private function getWordList(prefix:String,
position:uint,
root:TrieNode,
results:Array):void {
var letter:String=prefix.substr(position,1);
var child:TrieNode=root.children[letter];
if (!letter || !child) {
return;
}


if ( position<(prefix.length-1) ) {
getWordList(prefix, ++position, child, results);
}else {
if (!child.word) {
traverse( child, results, prefix);
}
}

}


private function insertWord(word:String,
position:uint,
root:TrieNode):void {
var letter:String=word.substr(position,1);
if (position==word.length || !letter) {
return;
}


var child:TrieNode=root.children[letter];
if (! child) {
child=createNode(letter);
root.children[letter]=child;
}


if (position==word.length-1) {
child.word=true;
} else {
insertWord(word, ++position, child);
}
}


private function createNode(letter:String):TrieNode {
return new TrieNode(letter,false);
}
}

Sorting strings in a locale-sensitive way

This article was originally written in English. Text in other languages was provided by machine translation.

In this section, you will learn how to sort strings in a locale-sensitive way.

Before Flash Player 10.1 was released, the sorting API in AS3 was using a locale-independent way which means the APIs are not locale aware. This is not user-friendly for international users who don’t use English as their first/only language. Let’s look at the following example code for some Chinese data:

If we use the APIs in Flash Player 10.0 and earlier to sort the strings:

Actually, the output result is in simple Unicode code point order for the conventional sorting, which is not correct for Chinese users.

With Flash Player 10.1, we can easily sort strings in a locale-sensitive way with the new flash.globalization.collator class. For handling strings sorting and searching, flash.globalization.* package provides Collator class. This class performs locale-sensitive string sorting and searching, or you can say, it allows performing string sorting and searching for different languages.

In the following example, we have instantiate a Collator object with a specific locale. Then we have called the compare method of the Collator class to perform a locale-sensitive string sorting. The sort method returns a negative value if the first string argument is less than the second, a positive value if the first string argument is greater than the second and 0 if the first string argument is equal to the second one.

Now, the output result looks great for Chinese users.

If you want to learn more about Flash Player 10.1 globalization API, please check the following package:

flash.globalization