goldman.collection.ordered.digitized
Class CompressedTrie<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>
- 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.
Constructor Summary |
CompressedTrie(Digitizer<? super E> digitizer)
Creates an empty compressed trie that uses
the given digitizer. |
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 interface goldman.collection.Collection |
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
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
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 elementsd
- 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