|
||||||||||
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.AbstractSearchTree<E>
public abstract class AbstractSearchTree<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 |
---|
protected AbstractSearchTree.TreeNode root
Constructor Detail |
---|
public AbstractSearchTree()
public AbstractSearchTree(Comparator<? super E> comp)
comp
- the element comparatorMethod Detail |
---|
protected abstract AbstractSearchTree.TreeNode find(E target)
target
- the element
to be located
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.public boolean contains(E target)
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>
target
- the element being tested for membership in the collection
public E get(int r)
r
- the desired rank
IllegalArgumentException
- r < 0 or r ≥ nprotected int getLastNodeSearchIndex()
public E getEquivalentElement(E target)
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 class AbstractCollection<E>
target
- the target element
NoSuchElementException
- there is no equivalent element in the
collection.public E min()
NoSuchElementException
- the collection is empty.public E max()
NoSuchElementException
- the collection is empty.protected void traverseForVisitor(Visitor<? super E> v) throws Exception
traverseForVisitor
in class AbstractCollection<E>
v
- the visitor
Exception
protected void writeElements(StringBuilder sb)
writeElements
in class AbstractCollection<E>
sb
- a string builderprotected abstract AbstractSearchTree.TreeNode insert(E element)
element
- the
new element
public void add(E element)
element
into the collection.
element
- the new elementprotected abstract void remove(AbstractSearchTree.TreeNode ptr)
ptr
- a pointer to
an existing tree nodepublic boolean remove(E element)
element
, if any
element
- the element to be removed
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |