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

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

The Patricia trie is a variation of a compressed trie that can be used when the digitizer has base 2 and the collection is naturally prefix-free (without adding an end of string character). The most common application is for fixed-length binary strings (such as ASCII codes or IP addresses). A Patricia trie reduces the space usage of the compressed trie by letting each node serve the role of both an internal node and leaf node.


Nested Class Summary
protected  class PatriciaTrie.Node
           
protected  class PatriciaTrie.PatriciaSearchData
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.digitized.CompressedTrie
CompressedTrie.CompressedTrieSearchData, CompressedTrie.InternalNode, 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
PatriciaTrie(Digitizer<? super E> digitizer)
          Creates an empty Patricia 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  PatriciaTrie.PatriciaSearchData createSearchData()
           
protected  TrieLeafNode<E> insert(E element)
           
protected  void remove(TrieNode<E> x)
           
protected  void remove(TrieNode<E> x, PatriciaTrie.Node leafParent)
           
protected  void removeImpl(Trie.SearchData sd)
          Call an internal remove method that takes a reference to the node to remove and its leaf parent
 
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, iterator, iteratorAtEnd, longestCommonPrefix, max, min, moveToLowestCommonAncestor, moveToPred, predecessor, remove, 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

PatriciaTrie

public PatriciaTrie(Digitizer<? super E> digitizer)
             throws Exception
Creates an empty Patricia trie that uses the given digitizer

Parameters:
digitizer - the digitizer for extracting digits from elements at each branch position
Throws:
Exception - the base for the provided digitizer is not 2.
Method Detail

createSearchData

protected PatriciaTrie.PatriciaSearchData createSearchData()
Overrides:
createSearchData in class CompressedTrie<E>
Returns:
a newly created and initialized PatriciaSearchData 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 CompressedTrie<E>
Parameters:
newNode - a trie node that already holds the new element
sd - a search data object positioned by a call to find using the element held in newNode
REQUIRES: the new node's branch position has been set to the number of matches that occurred during the search

insert

protected TrieLeafNode<E> insert(E element)
Overrides:
insert in class Trie<E>
Parameters:
element - the element to be added to the collection
Returns:
a reference to the new Patricia trie node that was inserted.
Throws:
IllegalArgumentException - adding element to the collection would violate the requirement that collection is prefix free.

removeImpl

protected void removeImpl(Trie.SearchData sd)
Call an internal remove method that takes a reference to the node to remove and its leaf parent

Overrides:
removeImpl in class Trie<E>
Parameters:
sd - a search data instance that has been set by a search for the element to be removed
REQUIRES: the structure of the Patricia trie has not changed since find was called with sd.ptr.data

remove

protected void remove(TrieNode<E> x)
Overrides:
remove in class CompressedTrie<E>
Parameters:
x - a reference to the trie node to remove

remove

protected void remove(TrieNode<E> x,
                      PatriciaTrie.Node leafParent)
Parameters:
x - a reference to the node to remove
leafParent - a reference to the leaf parent of x