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