Class Trie

Class Summary
Constructor Attributes	Constructor Name and Description
	Trie(stem, sorting) Trie is a kind of digital search tree.

Field Summary
Field Attributes	Field Name and Description
<static>	Trie.SORT_ASC sort the trie in ascending lexical order
<static>	Trie.SORT_DESC sort the trie in descending lexical order
<static>	Trie.SORT_NONE sort the trie in no particular order

Method Summary
Method Attributes	Method Name and Description
	add(word) Add a word to the existing dictionary.
	find(prefix) Find a trie node that is paired with a word or prefix 's'.
	findPrefix(prefix)
	getChild(prefix) Retrieve a direct child node of this dictionary with 'prefix'.
	getPrefixCount(word) Retrieve the prefix count of the applied argument
	getWordCount(word) Retrieve the word count of the applied argument
	getWords(s) Retrieve the Array of words that originate from this trie.
	hasChild(prefix) A version of getChild with a Boolean return type.
	remove(word) Remove a word from the dictionary.
	sort(direction) Resort this dictionary in lexical order, either in an ascending or descending direction.
<inner> <static>	Trie.sortAsc(a, b) Sorting helper function that can be passed to Array.sort().
<inner> <static>	Trie.sortDesc(a, b) Sorting helper function that can be passed to Array.sort().
	toString() Overrides Object.prototype.toString to deliver a more context sensitive String representation of a Trie.
	update(sOld, sNew) Update a word in the dictionary.
<inner> <static>	Trie.walker(word, trie, method) NOT named after Johnny, but merely after the verb 'to walk'.

Class Detail

Trie(stem, sorting)

Trie is a kind of digital search tree. (See [Knuth1972] for more details on digital search trees.) [Fredkin1960] introduced the trie terminology, which is abbreviated from "Retrieval". [Knuth1972] Knuth, D. E. The Art of Computer Programming Vol. 3, Sorting and Searching. Addison-Wesley. 1972. [Fredkin1960] Fredkin, E. Trie Memory. Communication of the ACM. Vol. 3:9 (Sep 1960). pp. 490-499. source
Author: Mike de Boer .

Parameters:
{String} stem: One character long representation of the trie node instance
{Number} sorting: Sort method. May be SORT_ASC or SORT_DESC.

See:: Wikipedia article The trie implementation of Dennis Byrne served as a starting point and inspiration:; http://notdennisbyrne.blogspot.com/2008/12/javascript-trie-implementation.html

Field Detail

<static> {Number} Trie.SORT_ASC

sort the trie in ascending lexical order

<static> {Number} Trie.SORT_DESC

sort the trie in descending lexical order

<static> {Number} Trie.SORT_NONE

sort the trie in no particular order

Method Detail

add(word)

Add a word to the existing dictionary. If a trie node doesn't exist yet, it is created with that character as its stem. Since an add already an expensive action, compared to adding nodes to native Javascript containers like Array or Object, inserting a trie node in lexical order is relatively cheap. Please refer to the test suite to compare performance in your browser(s).

Parameters:
{String} word: Remainder of the word that is added to the root trie

find(prefix)

Find a trie node that is paired with a word or prefix 's'. Like the remove function, this function also uses the walker.

Parameters:
{String} prefix: the word or prefix to search for in the dictionary

findPrefix(prefix)

Parameters:
{String} prefix: the word or prefix to search for in the dictionary

getChild(prefix)

Retrieve a direct child node of this dictionary with 'prefix'.

Parameters:
{String} prefix: s the word or prefix to search for in the children of this dictionary

getPrefixCount(word)

Retrieve the prefix count of the applied argument

Parameters:
{String} word: the prefix or word-completing stem

getWordCount(word)

Retrieve the word count of the applied argument

Parameters:
{String} word: the prefix or word-completing stem

getWords(s)

Retrieve the Array of words that originate from this trie. The main use-case for this function is for implementations of the type-ahead user experience pattern, but can be used to other ends as well, of course. The performance of this function still needs to be profiled against alternatives, like pre-caching the words Array per Trie when it's instantiated.

Parameters:
{String} s Optional: prefix to prepend to a stem character to make it a word

hasChild(prefix)

A version of getChild with a Boolean return type.

Parameters:
{String} prefix: s the word or prefix to search for in the children of this dictionary

remove(word)

Remove a word from the dictionary. This function uses the walker, which is a generic implementation of a tree walker.

Parameters:
{String} word: the word to remove

sort(direction)

Resort this dictionary in lexical order, either in an ascending or descending direction. Since it uses the native Array#sort method, sorting speed can be considered linear O(n) to the size of the trie, i.e. the word count. Please refer to the test suite to compare performance in your browser(s).

Parameters:
{Number} direction: sorting direction. Possible values: Trie#SORT_ASC Trie#SORT_DESC

<inner> <static> Trie.sortAsc(a, b)

Sorting helper function that can be passed to Array.sort(). The result of this helper will be that all nodes will be sorted in ascending lexical order.

Parameters:
{Trie} a: first element for comparison
{Trie} b: second element for comparison

<inner> <static> Trie.sortDesc(a, b)

Sorting helper function that can be passed to Array.sort(). The result of this helper will be that all nodes will be sorted in descending lexical order.

Parameters:
{Trie} a: first element for comparison
{Trie} b: second element for comparison

toString()

Overrides Object.prototype.toString to deliver a more context sensitive String representation of a Trie.

update(sOld, sNew)

Update a word in the dictionary. This update implementation is implemented like a file rename action as on a filesystem: add a node with the new name and remove the outdated, 'old' version.

Parameters:
{String} sOld: the old word to be replaced by the word provided by 'sNew'
{String} sNew: the new word to be added to the dictionary

<inner> <static> Trie.walker(word, trie, method)

NOT named after Johnny, but merely after the verb 'to walk'. This function walks along a Trie top-down until it finds the node which fully represents the term/ prefix/ word that was searched for. It passes the parent node of the found Trie and its index to a callback function. It passes the parent node, because otherwise Trie mutation would become increasingly more difficult. An earlier implementation of this function used a naive recursive algorithm, but my friend - @ejpbruel - has shown me that you can simply rewrite any form of tail-recursion to an inner loop.

Parameters:
{String} word: the word or prefix to search for
{Trie} trie: the root trie node to walk through
{Function} method: callback function to which the results of the walker are passed