goldman.collection.ordered.digitized
Class PatriciaTrie<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.ordered.digitized.Trie<E>
goldman.collection.ordered.digitized.CompactTrie<E>
goldman.collection.ordered.digitized.CompressedTrie<E>
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.
Constructor Summary |
PatriciaTrie(Digitizer<? super E> digitizer)
Creates an empty Patricia trie that uses
the given digitizer |
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 interface goldman.collection.Collection |
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
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.
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 elementsd
- 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 removeleafParent
- a reference to the leaf parent of x