goldman.collection.ordered.digitized
Class Trie.Tracker

java.lang.Object
  extended by goldman.collection.AbstractCollection.AbstractLocator<E>
      extended by goldman.collection.ordered.digitized.Trie.Tracker
All Implemented Interfaces:
Locator<E>, Cloneable, Iterator<E>
Enclosing class:
Trie<E>

protected class Trie.Tracker
extends AbstractCollection.AbstractLocator<E>


Field Summary
 
Fields inherited from class goldman.collection.AbstractCollection.AbstractLocator
versionNumber
 
Method Summary
 boolean advance()
          Moves this tracker to the next element in the iteration order (or {\texttt AFT} if the tracker is currently at the last element).
 E get()
          Returns the element associated with this locator.
 boolean hasNext()
           
 boolean inCollection()
          Returns true if and only if the locator is at an element of the collection.
 void remove()
          Removes the tracked element, leaving the tracker logically between the elements in the iteration order that preceded and followed the one removed.
 boolean retreat()
          Moves this tracker to the previous element in the iteration order (or FORE if the tracker is currently at the first element).
protected  TrieLeafNode<E> skipRemovedElements(TrieLeafNode<E> ptr)
          Similar to the path compression performed by the union-find data structure (Section~\ref{sec:union-find}), this method performs the optimization of compressing the path of the redirect chain by updating all next pointers to refer directly to the returned element.
 
Methods inherited from class goldman.collection.AbstractCollection.AbstractLocator
checkValidity, ignoreConcurrentModifications, ignorePriorConcurrentModifications, next, updateVersion
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

inCollection

public boolean inCollection()
Description copied from interface: Locator
Returns true if and only if the locator is at an element of the collection.

Returns:
true if and only if the tracked element is currently in the collection.

get

public E get()
Description copied from interface: Locator
Returns the element associated with this locator. When a tracker is used, the element associated with the locator might no longer be in the collection. If desired, the inCollection method can be used to determine if a tracked element is currently in the collection. If the locator is at FORE or AFT then a NoSuchElementException is thrown.

Returns:
the tracked element
Throws:
NoSuchElementException - this tracker is not at an element in the collection.

skipRemovedElements

protected TrieLeafNode<E> skipRemovedElements(TrieLeafNode<E> ptr)
Similar to the path compression performed by the union-find data structure (Section~\ref{sec:union-find}), this method performs the optimization of compressing the path of the redirect chain by updating all next pointers to refer directly to the returned element.

Parameters:
ptr - reference to a trie node that is no longer in the collection
Returns:
a reference to the element in the collection that follows the element referenced by ptr in the iteration order. If there is no such element AFT is returned.

advance

public boolean advance()
Moves this tracker to the next element in the iteration order (or {\texttt AFT} if the tracker is currently at the last element).

Returns:
true if and only if, after the update, the tracker is at an element of the collection.
Throws:
AtBoundaryException - this tracker is already at AFT since there is no place to advance.

retreat

public boolean retreat()
Moves this tracker to the previous element in the iteration order (or FORE if the tracker is currently at the first element).

Returns:
true if and only if, after the update, the tracker is at an element of the collection.
Throws:
AtBoundaryException - this tracker is already at FORE since there is no place to retreat.

hasNext

public boolean hasNext()
Returns:
true if there is some element in the collection after the currently tracked element.

remove

public void remove()
Removes the tracked element, leaving the tracker logically between the elements in the iteration order that preceded and followed the one removed.

Throws:
NoSuchElementException - the tracker is at FORE or AFT