goldman.collection.ordered.digitized
Class TernarySearchTrie<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.digitized.Trie<E>
          extended by goldman.collection.ordered.digitized.CompactTrie<E>
              extended by goldman.collection.ordered.digitized.TernarySearchTrie<E>
All Implemented Interfaces:
Collection<E>, DigitizedOrderedCollection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>

public class TernarySearchTrie<E>
extends CompactTrie<E>
implements DigitizedOrderedCollection<E>, Tracked<E>

The ternary search trie (often referred to as a TST) is a hybrid between a trie and a binary search tree that combines the time efficiency of a trie with the space efficiency of a binary search tree. In a ternary search trie, each node has three children. The branch to take during search is determined by both a branch position and the digit in that position for a distinguished descendant leaf node. Elements with a smaller digit use the left branch, elements with a equal digit use the middle branch, and elements with a larger digit use the right branch.


Nested Class Summary
protected  class TernarySearchTrie.InternalNode
           
protected  class TernarySearchTrie.TernarySearchTrieSearchData
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.digitized.Trie
Trie.FindResult, Trie.LeafNode, Trie.SearchData, Trie.Tracker
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version
 
Constructor Summary
TernarySearchTrie(Digitizer<? super E> digitizer)
          Creates an empty ternary search trie that uses the given digitizer.
 
Method Summary
protected  Trie.SearchData createSearchData()
           
protected  void moveToLowestCommonAncestor(E prefix, Trie.SearchData sd, Trie.FindResult found)
          This method has the side affect of moving sd so that it is at the lowest common ancestor for which the associated data is an extension of prefix.
protected  TrieNode<E> newInternalNode(Object o)
           
protected  TrieLeafNode<E> newLeafNode(E element, int level)
           
 
Methods inherited from class goldman.collection.ordered.digitized.CompactTrie
addNewNode
 
Methods inherited from class goldman.collection.ordered.digitized.Trie
add, addTracked, completions, contains, get, getEquivalentElement, getLocator, insert, iterator, iteratorAtEnd, longestCommonPrefix, max, min, moveToPred, predecessor, remove, removeImpl, successor
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, clear, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.ordered.digitized.DigitizedOrderedCollection
completions, longestCommonPrefix
 
Methods inherited from interface goldman.collection.ordered.OrderedCollection
get, getEquivalentElement, iteratorAtEnd, max, min, predecessor, successor
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from interface goldman.collection.Tracked
addTracked
 

Constructor Detail

TernarySearchTrie

public TernarySearchTrie(Digitizer<? super E> digitizer)
Creates an empty ternary search trie that uses the given digitizer.

Parameters:
digitizer - the digitizer to extract digits from elements
Method Detail

createSearchData

protected Trie.SearchData createSearchData()
Overrides:
createSearchData in class Trie<E>
Returns:
a newly created and initialized ternary search trie search data instance

newLeafNode

protected TrieLeafNode<E> newLeafNode(E element,
                                      int level)
Parameters:
element - the data element
Returns:
a newly created ternary search trie leaf node holding the given element.

newInternalNode

protected TrieNode<E> newInternalNode(Object o)
Overrides:
newInternalNode in class CompactTrie<E>
Parameters:
o - an object to initialize the data value for the new node
Returns:
a new ternary search trie node holding o

moveToLowestCommonAncestor

protected void moveToLowestCommonAncestor(E prefix,
                                          Trie.SearchData sd,
                                          Trie.FindResult found)
This method has the side affect of moving sd so that it is at the lowest common ancestor for which the associated data is an extension of prefix.

Overrides:
moveToLowestCommonAncestor in class Trie<E>
Parameters:
prefix - a digitized element
sd - a SearchData instance that has been set by a search for prefix
found - the FindResult value returned by the search that was used to set sd