jdsl.core.ref
Class InOrderIterator

java.lang.Object
  |
  +--jdsl.core.ref.InOrderIterator

All Implemented Interfaces:

ObjectIterator, PositionIterator

public class InOrderIterator

extends java.lang.Object

implements PositionIterator

The inorder iterator gives an inorder iteration of a binary tree. Creating this iterator takes O(N) where N = the number of positions in the tree, assuming that root, rightChild, leftChild, isInternal are O(1) in the tree implementation. All other methods take O(1) time

Version:

$Id: InOrderIterator.java,v 1.14 2000/12/18 16:33:30 lv Exp $

Author:

Ryan Shaun Baker, Mike Boilen (mgb)

Constructor Summary

InOrderIterator(InspectableBinaryTree tree)
Constructs a new InOrderIterator to iterate over the given container Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the container (given assumptions discussed in header)

Method Summary

java.lang.Object	element() Takes O(1) time
boolean	hasNext() Takes O(1) time
java.lang.Object	nextObject() Takes O(1) time
Position	nextPosition() Takes O(1) time
java.lang.Object	object() Takes O(1) time
Position	position() Takes O(1) time
void	reset() Takes O(1) time Sets the current node to the first node.

Methods inherited from class java.lang.Object

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

Constructor Detail

InOrderIterator

public InOrderIterator(InspectableBinaryTree tree)

Constructs a new InOrderIterator to iterate over the given container Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the container (given assumptions discussed in header)

Parameters:

tree - The tree to iterate over

Method Detail

hasNext

public boolean hasNext()

Takes O(1) time

Specified by:

hasNext in interface ObjectIterator

Following copied from interface: jdsl.core.api.ObjectIterator

Returns:

Whether there is at least one object still unseen

nextObject

public java.lang.Object nextObject()

Takes O(1) time

Specified by:

nextObject in interface ObjectIterator

Following copied from interface: jdsl.core.api.ObjectIterator

Returns:

Next object to consider

Throws:

java.util.NoSuchElementException - if iterator has moved past the last object

nextPosition

public Position nextPosition()

Takes O(1) time

Specified by:

nextPosition in interface PositionIterator

Following copied from interface: jdsl.core.api.PositionIterator

Returns:

Next position to consider

Throws:

java.util.NoSuchElementException - if iterator has moved past the last position to be seen

object

public java.lang.Object object()

Takes O(1) time

Specified by:

object in interface ObjectIterator

Following copied from interface: jdsl.core.api.ObjectIterator

Returns:

The object returned by the most recent next()

Throws:

java.util.NoSuchElementException - When the iterator is in its initial, before-the-first-object state

element

public java.lang.Object element()
                         throws java.util.NoSuchElementException

Takes O(1) time

Specified by:

element in interface PositionIterator

Following copied from interface: jdsl.core.api.PositionIterator

Returns:

Element of the position that would be returned by position()

Throws:

java.util.NoSuchElementException - When the iterator is in its initial, before-the-first-position state

position

public Position position()
                  throws java.util.NoSuchElementException

Takes O(1) time

Specified by:

position in interface PositionIterator

Following copied from interface: jdsl.core.api.PositionIterator

Returns:

The position returned by the most recent next()

Throws:

java.util.NoSuchElementException - When the iterator is in its initial, before-the-first-position state

reset

public void reset()

Takes O(1) time Sets the current node to the first node.

Specified by:

reset in interface ObjectIterator