#include "Iterate.h"
#include <stdlib.h>
template <class Object>
const Object & TreeIterator<Object>::retrieve( ) const
{
if( !isValid( ) )
throw BadIterator( "Illegal retrieve" );
return current->element;
}
template <class Object>
PreOrder<Object>::PreOrder( const BinaryTree<Object> & theTree )
: TreeIterator<Object>( theTree )
{
s.push( root );
}
template <class Object>
void PreOrder<Object>::first( )
{
s.makeEmpty( );
if( root != NULL )
{
s.push( root );
advance( );
}
}
template <class Object>
void PreOrder<Object>::advance( )
{
if( s.isEmpty( ) )
{
if( current == NULL )
throw BadIterator( "Advance past end" );
current = NULL;
return;
}
current = s.topAndPop( );
if( current->right != NULL )
s.push( current->right );
if( current->left != NULL )
s.push( current->left );
}
template <class Object>
PostOrder<Object>::PostOrder( const BinaryTree<Object> & theTree )
: TreeIterator<Object>( theTree )
{
s.push( StNode<Object>( root ) );
}
template <class Object>
void PostOrder<Object>::first( )
{
s.makeEmpty( );
if( root != NULL )
{
s.push( StNode<Object>( root ) );
advance( );
}
}
template <class Object>
void PostOrder<Object>::advance( )
{
if( s.isEmpty( ) )
{
if( current == NULL )
throw BadIterator( "Advance past end" );
current = NULL;
return;
}
StNode <Object> cnode;
for( ; ; )
{
cnode = s.topAndPop( );
if( ++cnode.timesPopped == 3 )
{
current = cnode.node;
return;
}
s.push( cnode );
if( cnode.timesPopped == 1 )
{
if( cnode.node->left != NULL )
s.push( StNode<Object>( cnode.node->left ) );
}
else {
if( cnode.node->right != NULL )
s.push( StNode<Object>( cnode.node->right ) );
}
}
}
template <class Object>
void InOrder<Object>::advance( )
{
if( s.isEmpty( ) )
{
if( current == NULL )
throw BadIterator( "Advance past end" );
current = NULL;
return;
}
StNode<Object> cnode;
for( ; ; )
{
cnode = s.topAndPop( );
if( ++cnode.timesPopped == 2 )
{
current = cnode.node;
if( cnode.node->right != NULL )
s.push( StNode<Object>( cnode.node->right ) );
return;
}
s.push( cnode );
if( cnode.node->left != NULL )
s.push( StNode<Object>( cnode.node->left ) );
}
}
template <class Object>
LevelOrder<Object>::LevelOrder( const BinaryTree<Object> & theTree )
: TreeIterator<Object>( theTree )
{
q.enqueue( root );
}
template <class Object>
void LevelOrder<Object>::first( )
{
q.makeEmpty( );
if( root != NULL )
{
q.enqueue( root );
advance( );
}
}
template <class Object>
void LevelOrder<Object>::advance( )
{
if( q.isEmpty( ) )
{
if( current == NULL )
throw BadIterator( "Advance past end" );
current = NULL;
return;
}
current = q.getFront( );
q.dequeue( );
if( current->left != NULL )
q.enqueue( current->left );
if( current->right != NULL )
q.enqueue( current->right );
}