goldman.collection.ordered.digitized
Class CompactTrie<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>
All Implemented Interfaces:
Collection<E>, DigitizedOrderedCollection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>
Direct Known Subclasses:
CompressedTrie, TernarySearchTrie

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

The compact trie data structure modifies the trie by replacing any leaf that has no siblings by its parent. A compact trie reduces the space complexity of a trie without any additional cost except that the search, insert, and remove methods are slightly more complicated. The length of the search path in a compact trie is at most the number of digits in the elements. More specifically, it is the length of the prefix needed to distinguish the given element from all other elements in the collection.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.ordered.digitized.Trie
Trie.FindResult, Trie.InternalNode, 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
CompactTrie(Digitizer<? super E> digitizer)
          Creates an empty compact trie that uses the given digitizer.
 
Method Summary
protected  void addNewNode(TrieNode<E> newNode, Trie.SearchData sd)
          Modifies the trie (excluding the ordered leaf chain) to include newNode
protected  TrieNode<E> newInternalNode(Object o)
           
 
Methods inherited from class goldman.collection.ordered.digitized.Trie
add, addTracked, completions, contains, createSearchData, get, getEquivalentElement, getLocator, insert, iterator, iteratorAtEnd, longestCommonPrefix, max, min, moveToLowestCommonAncestor, 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

CompactTrie

public CompactTrie(Digitizer<? super E> digitizer)
Creates an empty compact trie that uses the given digitizer.

Parameters:
digitizer - the digitizer to be used to define the digits for any element
Method Detail

newInternalNode

protected TrieNode<E> newInternalNode(Object o)
Parameters:
o - the data value for the new node
Returns:
a new internal trie node holding o

addNewNode

protected void addNewNode(TrieNode<E> newNode,
                          Trie.SearchData sd)
Description copied from class: Trie
Modifies the trie (excluding the ordered leaf chain) to include newNode

Overrides:
addNewNode in class Trie<E>
Parameters:
newNode - a new trie node holding the element to be added
sd - a SearchData instance
REQUIRES: sd has been positioned by a call to find using the element associated with newNode, and that the new element will preserve the prefix free requirement for the collection