goldman.collection.ordered.digitized
Class Trie<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.digitized.Trie<E>
All Implemented Interfaces:
Collection<E>, DigitizedOrderedCollection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>
Direct Known Subclasses:
CompactTrie

public class Trie<E>
extends AbstractCollection<E>
implements DigitizedOrderedCollection<E>, Tracked<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

Trie

public Trie(Digitizer<? super E> digitizer)
Creates an empty trie that uses the given digitizer.

Parameters:
digitizer - the digitizer to be used
Method Detail

createSearchData

protected Trie.SearchData createSearchData()
Returns:
a newly created and initialized search data instance

contains

public boolean contains(E element)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
element - the element being tested for membership in the collection
Returns:
true if and only if an equivalent element exists in the collection

get

public E get(int r)
Description copied from interface: OrderedCollection
Returns the rth element in the sorted order, where r=0 is the minimum element. It throws an IllegalArgumentException when r < 0 or r ≥ n.

Specified by:
get in interface OrderedCollection<E>
Parameters:
r - the desired rank
Returns:
the rth element in the sorted order, where r = 0 is the minimum.
Throws:
IllegalArgumentException - r < 0 or r ≥ n

getEquivalentElement

public E getEquivalentElement(E element)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to 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.

Specified by:
getEquivalentElement in interface Collection<E>
Specified by:
getEquivalentElement in interface OrderedCollection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
element - the target
Returns:
an equivalent element in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

min

public E min()
Description copied from interface: OrderedCollection
Returns a least element in the collection (according to the comparator). More specifically, the first element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
min in interface OrderedCollection<E>
Returns:
the least element in the collection, as defined by the digitizer.
Throws:
NoSuchElementException - the collection is empty.

max

public E max()
Description copied from interface: OrderedCollection
Returns a greatest element in the collection (according to the comparator). More specifically, the last element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
max in interface OrderedCollection<E>
Returns:
the greatest element in the collection, as defined by the digitizer.
Throws:
NoSuchElementException - the collection is empty.

moveToPred

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. Otherwise, sd is not changed.

Parameters:
element - the target
sd - a SearchData instance that has already been set by find(element)
findStatus - the return value from find(element)
Returns:
true if there is some element in the collection less than element and otherwise returns false

predecessor

public E predecessor(E element)
This method does not require that element be in the collection.

Specified by:
predecessor in interface OrderedCollection<E>
Parameters:
element - the element for which to find the predecessor
Returns:
the maximum element in the ordered collection that is less than x.
Throws:
NoSuchElementException - no element in the collection is less than element

successor

public E successor(E element)
This method does not require that element be in the collection.

Specified by:
successor in interface OrderedCollection<E>
Parameters:
element - the element for which to find the successor
Returns:
the least element in the collection that is greater than element
Throws:
NoSuchElementException - no element in the collection is greater than element

moveToLowestCommonAncestor

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.

Parameters:
prefix - the desired prefix
sd - a SearchData instance that has been set by find(prefix)
findStatus - the FindResult value returned by the search used to set sd

completions

public void completions(E prefix,
                        Collection<? super E> c)
Description copied from interface: DigitizedOrderedCollection
Appends all elements in this collection that have the given prefix to the given collection c. We consider an element to be a prefix of itself.

Specified by:
completions in interface DigitizedOrderedCollection<E>
Parameters:
prefix - the desired element for which all completions are sought
c - a collection to which all elements in the collection that consists of prefix followed by any number of (possibly zero) additional digits are added.

longestCommonPrefix

public void longestCommonPrefix(E prefix,
                                Collection<? super E> c)
Description copied from interface: DigitizedOrderedCollection
Appends to the provided collection c all elements in this collection that have a longest common prefix with element.

Specified by:
longestCommonPrefix in interface DigitizedOrderedCollection<E>
Parameters:
prefix - the desired prefix
c - a collection to which all elements in the collection that have a longest common prefix with element are added.

addNewNode

protected void addNewNode(TrieNode<E> newNode,
                          Trie.SearchData sd)
Modifies the trie (excluding the ordered leaf chain) to include newNode

Parameters:
newNode - a trie node to add that already holds the new element
sd - a SearchData instance set by a call to find(newNode.data())
REQUIRES: adding the new element will preserve the property that the collection is prefix free

insert

protected TrieLeafNode<E> insert(E element)
Parameters:
element - the element to be added to the collection
Returns:
a reference to the newly inserted leaf node.
Throws:
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.

add

public void add(E element)
Inserts element into the collection.

Specified by:
add in interface Collection<E>
Parameters:
element - the new element

addTracked

public Locator<E> addTracked(E element)
Inserts element into the collection.

Specified by:
addTracked in interface Tracked<E>
Parameters:
element - the new element
Returns:
a locator that tracks the newly added element

removeImpl

protected void removeImpl(Trie.SearchData sd)
It calls an internal method that removes sd.ptr from the trie.

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

public boolean remove(E element)
Removes from the collection the element (if any) equivalent to element.

Specified by:
remove in interface Collection<E>
Parameters:
element - the element to remove
Returns:
true if an element was removed, and false otherwise.

iterator

public Locator<E> iterator()
Creates a new tracker that is at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public Locator<E> iteratorAtEnd()
Creates a new tracker that is at AFT.

Specified by:
iteratorAtEnd in interface OrderedCollection<E>

getLocator

public Locator<E> getLocator(E x)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to 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.

Specified by:
getLocator in interface Collection<E>
Parameters:
x - the element to track
Returns:
a new tracker that is initialized to track x.
Throws:
NoSuchElementException - x is not in the collection.