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

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

The compressed trie performs additional compression on a compact trie. While the compact trie ensures that all leaves have at least one sibling, there can be an internal node with a single child. A compressed trie ensures that all nodes have at least two children by replacing any node with a single child by that child.


Nested Class Summary
protected  class CompressedTrie.CompressedTrieSearchData
           
protected  class CompressedTrie.InternalNode
           
protected  class CompressedTrie.LeafNode
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.digitized.Trie
Trie.FindResult, 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
CompressedTrie(Digitizer<? super E> digitizer)
          Creates an empty compressed 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  CompressedTrie.CompressedTrieSearchData createSearchData()
           
protected  void remove(TrieNode<E> node)
           
 
Methods inherited from class goldman.collection.ordered.digitized.CompactTrie
newInternalNode
 
Methods inherited from class goldman.collection.ordered.digitized.Trie
add, addTracked, completions, contains, 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

CompressedTrie

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

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

createSearchData

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

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 CompactTrie<E>
Parameters:
newNode - a trie node to add that already holds the new element
sd - a SearchData instance
REQUIRES: sd has been set 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

remove

protected void remove(TrieNode<E> node)
Parameters:
node - a reference to the trie node to remove