goldman.collection.ordered
Class AbstractSearchTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.AbstractSearchTree<E>
All Implemented Interfaces:
Collection<E>, Iterable<E>
Direct Known Subclasses:
BinarySearchTree, BTree, QuadTree

public abstract class AbstractSearchTree<E>
extends AbstractCollection<E>

The AbstractSearchTree class is an abstract class that includes the methods that are shared by all search trees.


Nested Class Summary
protected  class AbstractSearchTree.TreeNode
           
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
protected  AbstractSearchTree.TreeNode root
           
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
AbstractSearchTree()
           
AbstractSearchTree(Comparator<? super E> comp)
           
 
Method Summary
 void add(E element)
          Inserts element into the collection.
 boolean contains(E target)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
protected abstract  AbstractSearchTree.TreeNode find(E target)
           
 E get(int r)
           
 E getEquivalentElement(E target)
          Returns an element in the collection that is equivalent to target.
protected  int getLastNodeSearchIndex()
          
REQUIRES: it is called only after a successful search
protected abstract  AbstractSearchTree.TreeNode insert(E element)
          Inserts it into the collection
 E max()
           
 E min()
           
protected abstract  void remove(AbstractSearchTree.TreeNode ptr)
          Removes the given node.
 boolean remove(E element)
          Removes an arbitrary element in the collection equivalent to element, if any
protected  void traverseForVisitor(Visitor<? super E> v)
          Applies the visitor to each element of the collection in sorted order
protected  void writeElements(StringBuilder sb)
          Appends to the string buffer a comma-separated string representation for the elements in the collection, in the iteration order.
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, clear, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
getLocator, iterator
 

Field Detail

root

protected AbstractSearchTree.TreeNode root
Constructor Detail

AbstractSearchTree

public AbstractSearchTree()

AbstractSearchTree

public AbstractSearchTree(Comparator<? super E> comp)
Parameters:
comp - the element comparator
Method Detail

find

protected abstract AbstractSearchTree.TreeNode find(E target)
Parameters:
target - the element to be located
Returns:
a reference to a tree node that contains an occurrence of the element if it is found. If target is not in the collection, then it returns the frontier node at the insert position. In that case, the parent of the returned frontier node must be the node that preceded it on the search path.

contains

public boolean contains(E target)
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:
target - the element being tested for membership in the collection
Returns:
true if and only if an equivalent value exists in the collection

get

public E get(int r)
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

getLastNodeSearchIndex

protected int getLastNodeSearchIndex()

REQUIRES: it is called only after a successful search

Returns:
the index, within its tree node, of the element returned in the most recent search.

getEquivalentElement

public E getEquivalentElement(E target)
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>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
target - the target element
Returns:
an equivalent element that is in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

min

public E min()
Returns:
a smallest element in the collection.
Throws:
NoSuchElementException - the collection is empty.

max

public E max()
Returns:
a greatest element in the collection.
Throws:
NoSuchElementException - the collection is empty.

traverseForVisitor

protected void traverseForVisitor(Visitor<? super E> v)
                           throws Exception
Applies the visitor to each element of the collection in sorted order

Overrides:
traverseForVisitor in class AbstractCollection<E>
Parameters:
v - the visitor
Throws:
Exception

writeElements

protected void writeElements(StringBuilder sb)
Appends to the string buffer a comma-separated string representation for the elements in the collection, in the iteration order.

Overrides:
writeElements in class AbstractCollection<E>
Parameters:
sb - a string builder

insert

protected abstract AbstractSearchTree.TreeNode insert(E element)
Inserts it into the collection

Parameters:
element - the new element
Returns:
a reference to the newly inserted element

add

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

Parameters:
element - the new element

remove

protected abstract void remove(AbstractSearchTree.TreeNode ptr)
Removes the given node.

Parameters:
ptr - a pointer to an existing tree node

remove

public boolean remove(E element)
Removes an arbitrary element in the collection equivalent to element, if any

Parameters:
element - the element to be removed
Returns:
true if and only if an element is removed.