structure
Class RedBlackIterator

java.lang.Object
  |
  +--structure.AbstractIterator
        |
        +--structure.RedBlackIterator

All Implemented Interfaces:

Enumeration, Iterator

class RedBlackIterator

extends AbstractIterator

An iterator for traversing RedBlackSearchTrees constructed from RedBlackTrees. The iterator performs minimal work before traversal. Every node is considered after every left descendant, but before any right descendant. AbstractIterator finishes when all descendants of the start node have been considered.

Field Summary

protected RedBlackTree	root The root of the subtree being traversed.
protected Stack	todo Stack of nodes that maintain the state of the iterator.

Constructor Summary

RedBlackIterator(RedBlackTree root)
Construct a new inorder iterator of a tree.

Method Summary

Object	get() Return the node currently being considered.
boolean	hasNext() Returns true iff the iterator has more nodes to be considered.
Object	next() Return current node, and increment iterator.
void	reset() Reset the iterator to its initial state.

Methods inherited from class structure.AbstractIterator

hasMoreElements, nextElement, remove, value

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

root

protected RedBlackTree root

The root of the subtree being traversed.

todo

protected Stack todo

Stack of nodes that maintain the state of the iterator.

Constructor Detail

RedBlackIterator

public RedBlackIterator(RedBlackTree root)

Construct a new inorder iterator of a tree.

Parameters:

root - The root of the subtree to be traversed.

Method Detail

reset

public void reset()

Reset the iterator to its initial state.

Overrides:

reset in class AbstractIterator

Postcondition:

Resets the iterator to retraverse

hasNext

public boolean hasNext()

Returns true iff the iterator has more nodes to be considered.

Overrides:

hasNext in class AbstractIterator

Postcondition:

Returns true iff iterator is not finished

Returns:

True iff more nodes are to be considered.

get

public Object get()

Return the node currently being considered.

Overrides:

get in class AbstractIterator

Precondition:

hasNext()

Postcondition:

Returns reference to current value

Returns:

The node currently under consideration.

next

public Object next()

Return current node, and increment iterator.

Overrides:

next in class AbstractIterator

Precondition:

hasNext()

Postcondition:

Returns current value, increments iterator

Returns:

The value of the current node, before iterator iterated.