|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.ordered.digitized.Trie<E>
public class Trie<E>
The trie data structure is the simplest DigitizedOrderedCollection
implementation. However,
it typically requires significantly more space than the other
data structures. It should be used only when most prefixes p
that occur have at least two distinct elements
with that prefix. The search path to any element is exactly
the number of digits (including the end of string character) in
the element.
Nested Class Summary | |
---|---|
protected static class |
Trie.FindResult
|
protected class |
Trie.InternalNode
|
protected class |
Trie.LeafNode
|
protected class |
Trie.SearchData
|
protected class |
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 | |
---|---|
Trie(Digitizer<? super E> digitizer)
Creates an empty trie that uses the given digitizer. |
Method Summary | |
---|---|
void |
add(E element)
Inserts element into the collection. |
protected void |
addNewNode(TrieNode<E> newNode,
Trie.SearchData sd)
Modifies the trie (excluding the ordered leaf chain) to include newNode |
Locator<E> |
addTracked(E element)
Inserts element into the collection. |
void |
completions(E prefix,
Collection<? super E> c)
Appends all elements in this collection that have the given prefix to the given collection c. |
boolean |
contains(E element)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
protected Trie.SearchData |
createSearchData()
|
E |
get(int r)
Returns the rth element in the sorted order, where r=0 is the minimum element. |
E |
getEquivalentElement(E element)
Returns an element in the collection that is equivalent to target . |
Locator<E> |
getLocator(E x)
Returns a locator that has been initialized to an element equivalent to target . |
protected TrieLeafNode<E> |
insert(E element)
|
Locator<E> |
iterator()
Creates a new tracker that is at FORE. |
Locator<E> |
iteratorAtEnd()
Creates a new tracker that is at AFT. |
void |
longestCommonPrefix(E prefix,
Collection<? super E> c)
Appends to the provided collection c all elements in this collection that have a longest common prefix with element . |
E |
max()
Returns a greatest element in the collection (according to the comparator). |
E |
min()
Returns a least element in the collection (according to the comparator). |
protected void |
moveToLowestCommonAncestor(E prefix,
Trie.SearchData sd,
Trie.FindResult findStatus)
This method has the side affect of moving sd to its lowest ancestor for which the associated data is an extension of
prefix . |
protected boolean |
moveToPred(E element,
Trie.SearchData sd,
Trie.FindResult findStatus)
If there is some element in the collection less than element
then sd is moved to the predecessor. |
E |
predecessor(E element)
This method does not require that element
be in the collection. |
boolean |
remove(E element)
Removes from the collection the element (if any) equivalent to element . |
protected void |
removeImpl(Trie.SearchData sd)
It calls an internal method that removes sd.ptr from the trie. |
E |
successor(E element)
This method does not require that element
be in the collection. |
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.Collection |
---|
accept, addAll, checkRep, clear, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public Trie(Digitizer<? super E> digitizer)
digitizer
- the digitizer to be
usedMethod Detail |
---|
protected Trie.SearchData createSearchData()
public boolean contains(E element)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
element
- the element being tested for membership in the collection
public E get(int r)
OrderedCollection
IllegalArgumentException
when r < 0 or r ≥ n.
get
in interface OrderedCollection<E>
r
- the desired rank
IllegalArgumentException
- r < 0 or r ≥ npublic E getEquivalentElement(E element)
Collection
target
. It
throws a NoSuchElementException
when there is no equivalent
element. The contains
method should be used to
determine if an element is in the collection.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in interface OrderedCollection<E>
getEquivalentElement
in class AbstractCollection<E>
element
- the target
NoSuchElementException
- there is no equivalent element in the
collection.public E min()
OrderedCollection
NoSuchElementException
when the collection is empty.
min
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.public E max()
OrderedCollection
NoSuchElementException
when the collection is empty.
max
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.protected boolean moveToPred(E element, Trie.SearchData sd, Trie.FindResult findStatus)
element
then sd
is moved to the predecessor. Otherwise, sd
is not changed.
element
- the targetsd
- a SearchData instance that has already been set by find(element)
findStatus
- the return value from find(element)
element
and otherwise returns falsepublic E predecessor(E element)
element
be in the collection.
predecessor
in interface OrderedCollection<E>
element
- the element for which to find
the predecessor
x
.
NoSuchElementException
- no element in the collection
is less than element
public E successor(E element)
element
be in the collection.
successor
in interface OrderedCollection<E>
element
- the element for which to find
the successor
element
NoSuchElementException
- no element in the collection
is greater than element
protected void moveToLowestCommonAncestor(E prefix, Trie.SearchData sd, Trie.FindResult findStatus)
sd
to its lowest ancestor for which the associated data is an extension of
prefix
.
prefix
- the desired prefixsd
- a SearchData
instance that has been set by find(prefix)
findStatus
- the FindResult value returned by the search used to
set sd
public void completions(E prefix, Collection<? super E> c)
DigitizedOrderedCollection
completions
in interface DigitizedOrderedCollection<E>
prefix
- the desired
element for which all completions are soughtc
- a collection
to which all elements in the collection that consists of prefix
followed by any number of
(possibly zero) additional digits are added.public void longestCommonPrefix(E prefix, Collection<? super E> c)
DigitizedOrderedCollection
element
.
longestCommonPrefix
in interface DigitizedOrderedCollection<E>
prefix
- the desired prefixc
- a collection to which all
elements in the collection that have a longest common
prefix with element
are added.protected void addNewNode(TrieNode<E> newNode, Trie.SearchData sd)
newNode
newNode
- a trie node to add that
already holds the new elementsd
- a SearchData instance
set by a call to find(newNode.data())
protected TrieLeafNode<E> insert(E element)
element
- the element to be added to
the collection
IllegalArgumentException
- adding
element
to the collection would violate the requirement that no element in the
collection is a prefix of any other element in the collection. Recall that two equal elements
are considered to be prefixes of each other.public void add(E element)
element
into the collection.
add
in interface Collection<E>
element
- the new elementpublic Locator<E> addTracked(E element)
element
into the collection.
addTracked
in interface Tracked<E>
element
- the new element
protected void removeImpl(Trie.SearchData sd)
sd.ptr
from the trie.
sd
- a search data instance that has
been set by a search for the element to be removed
find
was called with sd.ptr.data
public boolean remove(E element)
element
.
remove
in interface Collection<E>
element
- the element to remove
true
if an element was removed, and false
otherwise.public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> iteratorAtEnd()
iteratorAtEnd
in interface OrderedCollection<E>
public Locator<E> getLocator(E x)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
x
- the element to track
x
.
NoSuchElementException
- x
is not in the collection.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |