import java.util.NoSuchElementException;

import weiss.nonstandard.Stack;
import weiss.nonstandard.Queue;
import weiss.nonstandard.ArrayStack;
import weiss.nonstandard.ArrayQueue;

// TreeIterator class; maintains "current position"
//
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
//     first and advance are abstract; others are final
// boolean isValid( )   --> True if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Tree iterator class.
 * @author Mark Allen Weiss
 */
abstract class TreeIterator<AnyType>
{
    /**
     * Construct the iterator.
     * The current position is set to null.
     * @param theTree the tree to which the iterator is
     *     permanently bound.
     */
    public TreeIterator( BinaryTree<AnyType> theTree )
    {
        t = theTree;
        current = null;
    }

    /**
     * Set the current position to the first item, according
     * to the traversal scheme.
     */
    abstract public void first( );

    /**
     * Test if current position references a valid tree item.
     * @return true if the current position is not null; false otherwise.
     */
    final public boolean isValid( )
    {
        return current != null;
    }

    /**
     * Return the item stored in the current position.
     * @return the stored item.
     * @throws NoSuchElementException if the current position is invalid.
     */
    final public AnyType retrieve( )
    {
        if( current == null )
            throw new NoSuchElementException( "TreeIterator retrieve" );
        return current.getElement( );
    }

    /**
     * Advance the current position to the next node in the tree,
     *     according to the traversal scheme.
     * If the current position is null, then throw an exception.
     * This is the alternate strategy, that we did not use for lists.
     * @throws NoSuchElementException if the current position is null.
     */
    abstract public void advance( );

        /** The tree. */
    protected BinaryTree<AnyType> t;        // Tree
        /** Current position. */
    protected BinaryNode<AnyType> current;  // Current position
}


// PostOrder class; maintains "current position"
//     according to a postorder traversal
// 
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( )   --> True if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Postorder iterator class.
 * @author Mark Allen Weiss
 */
class PostOrder<AnyType> extends TreeIterator<AnyType>
{
    /**
     * Construct the iterator.
     * The current position is set to null.
     * @param theTree the tree to which the iterator is
     *     permanently bound.
     */
    public PostOrder( BinaryTree<AnyType> theTree )
    {
        super( theTree );
        s = new ArrayStack<StNode<AnyType>>( );
        s.push( new StNode<AnyType>( t.getRoot( ) ) );
    }

    /**
     * Set the current position to the first item, according
     * to the postorder traversal scheme.
     */
    public void first( )
    {
        s.makeEmpty( );
        if( t.getRoot( ) != null )
        {
            s.push( new StNode<AnyType>( t.getRoot( ) ) );
            advance( );
        }
    }

    /**
     * Advance the current position to the next node in the tree,
     *     according to the postorder traversal scheme.
     * @throws NoSuchElementException if iteration has
     *     been exhausted prior to the call.
     */
    public void advance( )
    {
        if( s.isEmpty( ) )
        {
            if( current == null )
                throw new NoSuchElementException( "PostOrder Advance" );
            current = null;
            return;
        }

        StNode<AnyType> cnode;

        for( ; ; )
        {
            cnode = s.topAndPop( );

            if( ++cnode.timesPopped == 3 )
            {
                current = cnode.node;
                return;
            }

            s.push( cnode );
            if( cnode.timesPopped == 1 )
            {
                if( cnode.node.getLeft( ) != null )
                    s.push( new StNode<AnyType>( cnode.node.getLeft( ) ) );
            }
            else  // cnode.timesPopped == 2
            {
                if( cnode.node.getRight( ) != null )
                    s.push( new StNode<AnyType>( cnode.node.getRight( ) ) );
            }
        }
    }

      // An internal class for tree iterators
    protected static class StNode<AnyType>
    {
        BinaryNode<AnyType> node;
        int timesPopped;

        StNode( BinaryNode<AnyType> n )
        {
           node = n;
           timesPopped = 0;
        }
    }
        /** An internal stack if visited nodes. */
    protected Stack<StNode<AnyType>> s;    // The stack of StNode objects
}


// InOrder class; maintains "current position"
//     according to an inorder traversal
// 
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( )   --> True if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Inorder iterator class.
 * @author Mark Allen Weiss
 */
class InOrder<AnyType> extends PostOrder<AnyType>
{
    /**
     * Construct the iterator.
     * The current position is set to null.
     * @param theTree the tree to which the iterator is
     *     permanently bound.
     */
    public InOrder( BinaryTree<AnyType> theTree )
    {
        super( theTree );
    }

    /**
     * Advance the current position to the next node in the tree,
     *     according to the inorder traversal scheme.
     * @throws NoSuchElementException if iteration has
     *     been exhausted prior to the call.
     */
    public void advance( )
    {
        if( s.isEmpty( ) )
        {
            if( current == null )
                throw new NoSuchElementException( "InOrder advance" );
            current = null;
            return;
        }

        StNode<AnyType> cnode;

        for( ; ; )
        {
            cnode = s.topAndPop( );

            if( ++cnode.timesPopped == 2 )
            {
                current = cnode.node;
                if( cnode.node.getRight( ) != null )
                    s.push( new StNode<AnyType>( cnode.node.getRight( ) ) );
                return;
            }

                // First time through
            s.push( cnode );
            if( cnode.node.getLeft( ) != null )
                s.push( new StNode<AnyType>( cnode.node.getLeft( ) ) );
        }
    }
}


// PreOrder class; maintains "current position"
//     according to a preorder traversal
// 
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( )   --> True if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Preorder iterator class.
 * @author Mark Allen Weiss
 */
class PreOrder<AnyType> extends TreeIterator<AnyType>
{
    /**
     * Construct the iterator.
     * The current position is set to null.
     * @param theTree the tree to which the iterator is
     *     permanently bound.
     */
    public PreOrder( BinaryTree<AnyType> theTree )
    {
        super( theTree );
        s = new ArrayStack<BinaryNode<AnyType>>( );
        s.push( t.getRoot( ) );
    }

    /**
     * Set the current position to the first item, according
     * to the preorder traversal scheme.
     */
    public void first( )
    {
        s.makeEmpty( );
        if( t.getRoot( ) != null )
        {
            s.push( t.getRoot( ) );
            advance( );
        }
    }

    /**
     * Advance the current position to the next node in the tree,
     *     according to the preorder traversal scheme.
     * @throws NoSuchElementException if iteration has
     *     been exhausted prior to the call.
     */
    public void advance( )
    {
        if( s.isEmpty( ) )
        {
            if( current == null )
                throw new NoSuchElementException( "PreOrder Advance" );
            current = null;
            return;
        }

        current = s.topAndPop( );

        if( current.getRight( ) != null )
            s.push( current.getRight( ) );
        if( current.getLeft( ) != null )
            s.push( current.getLeft( ) );
    }

        /** An internal stack of visited nodes */
    private Stack<BinaryNode<AnyType>> s;    // Stack of BinaryNode objects
}


// LevelOrder class; maintains "current position"
//     according to a level-order traversal
// 
// CONSTRUCTION: with tree to which iterator is bound
//
// ******************PUBLIC OPERATIONS**********************
// boolean isValid( )   --> True if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)
// ******************ERRORS*********************************
// Exceptions thrown for illegal access or advance

/**
 * Level-order iterator class.
 * @author Mark Allen Weiss
 */
class LevelOrder<AnyType> extends TreeIterator<AnyType>
{
    /**
     * Construct the iterator.
     * The current position is set to null.
     * @param theTree the tree to which the iterator is
     *     permanently bound.
     */
    public LevelOrder( BinaryTree<AnyType> theTree )
    {
        super( theTree );
        q = new ArrayQueue<BinaryNode<AnyType>>( );
        q.enqueue( t.getRoot( ) );
    }

    /**
     * Set the current position to the first item, according
     * to the level-order traversal scheme.
     */
    public void first( )
    {
        q.makeEmpty( );
        if( t.getRoot( ) != null )
        {
            q.enqueue( t.getRoot( ) );
            advance( );
        }
    }

    /**
     * Advance the current position to the next node in the tree,
     *     according to the level-order traversal scheme.
     * @throws NoSuchElementException if iteration has
     *     been exhausted prior to the call.
     */
    public void advance( )
    {
        if( q.isEmpty( ) )
        {
            if( current == null )
                throw new NoSuchElementException( "LevelOrder advance" );
            current = null;
            return;
        }

        current = q.dequeue( );

        if( current.getLeft( ) != null )
            q.enqueue( current.getLeft( ) );
        if( current.getRight( ) != null )
            q.enqueue( current.getRight( ) );
    }

        /** An internal queue of visited nodes */
    private Queue<BinaryNode<AnyType>> q;  // Queue of BinaryNode objects
}

public class TestTreeIterators
{
        // Test program
    public static void main( String[ ] args )
    {
        BinaryTree<Integer> t = new BinaryTree<Integer>( );

        testItr( "PreOrder", new PreOrder<Integer>( t ) ); // Test empty tree

        BinaryTree<Integer> t1 = new BinaryTree<Integer>( 1 );
        BinaryTree<Integer> t3 = new BinaryTree<Integer>( 3 );
        BinaryTree<Integer> t5 = new BinaryTree<Integer>( 5 );
        BinaryTree<Integer> t7 = new BinaryTree<Integer>( 7 );
        BinaryTree<Integer> t2 = new BinaryTree<Integer>( );
        BinaryTree<Integer> t4 = new BinaryTree<Integer>( );
        BinaryTree<Integer> t6 = new BinaryTree<Integer>( );

        t2.merge( 2, t1, t3 );
        t6.merge( 6, t5, t7 );
        t4.merge( 4, t2, t6 );
        
        t = t4;

        testItr( "Preorder", new PreOrder<Integer>( t ) );
        testItr( "Postorder", new PostOrder<Integer>( t ) );
        testItr( "Inorder", new InOrder<Integer>( t ) );
        testItr( "Level order", new LevelOrder<Integer>( t ) );
    }

    public static <AnyType> void testItr( String type, TreeIterator<AnyType> itr )
    {
        try
        {
            System.out.print( type + ":" );
            for( itr.first( ); itr.isValid( ); itr.advance( ) )
                System.out.print( " " + itr.retrieve( ) );
            System.out.println( );
            itr.advance( );
        }
        catch( NoSuchElementException e )
          { System.out.println( e + " (as expected)" ); }
    }
}