goldman.collection.ordered.digitized
Class Trie.SearchData

java.lang.Object
  extended by goldman.collection.ordered.digitized.Trie.SearchData
Direct Known Subclasses:
CompressedTrie.CompressedTrieSearchData, TernarySearchTrie.TernarySearchTrieSearchData
Enclosing class:
Trie<E>

protected class Trie.SearchData
extends Object


Constructor Summary
protected Trie.SearchData()
           
 
Method Summary
 boolean atLeaf()
           
 boolean atRoot()
           
protected  int childIndex(E element)
           
protected  int extendPath(E element, TrieNode<E> newChild)
           
protected  int moveDown(E element)
          Moves this SearchData instance down one level in the tree
protected  int moveDown(int childIndex)
           
 void moveToMaxDescendant()
          Moves this search data object to the descendant of its current location that is last in the iteration order among its descendants.
protected  int moveUp()
          Moves up one level in the tree
 int numMatches()
           
protected  boolean processedEndOfString(E element)
           
 void retraceToLastLeftFork(E x)
          Moves the search data position to the left fork root for x
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Trie.SearchData

protected Trie.SearchData()
Method Detail

atLeaf

public boolean atLeaf()
Returns:
true if and only if the search data object is currently at a leaf node.

atRoot

public boolean atRoot()
Returns:
true if and only if the search data object is currently at the root.

numMatches

public int numMatches()
Returns:
the number of digits of the element that have been matched so far.

childIndex

protected int childIndex(E element)
Parameters:
element - an element to be considered on this search path
Returns:
the index of the child branch that would be followed to reach the given element from the current position of this search data object.

moveDown

protected int moveDown(int childIndex)
Parameters:
childIndex - the index of the child to which to move
Returns:
the given index if the SearchData instance moves successfully or NO_CHILD if the specified child does not exist.

moveDown

protected int moveDown(E element)
Moves this SearchData instance down one level in the tree

Parameters:
element - the target
Returns:
the child index for the current search location, or NO_CHILD if the SearchData instance did not move because a null\ child was encountered.

extendPath

protected int extendPath(E element,
                         TrieNode<E> newChild)
Parameters:
element - the element that defines the search path on which the child node should be placed
newChild - the child node to be added

moveUp

protected int moveUp()
Moves up one level in the tree

Returns:
the branch position for current search location.

processedEndOfString

protected boolean processedEndOfString(E element)
Parameters:
element - the target
Returns:
true if and only if the last step of the search path processed the end of string character

retraceToLastLeftFork

public void retraceToLastLeftFork(E x)
Moves the search data position to the left fork root for x

Parameters:
x - the target
REQUIRES: this SearchData instance is set by a call to find(x)

moveToMaxDescendant

public void moveToMaxDescendant()
Moves this search data object to the descendant of its current location that is last in the iteration order among its descendants.