#include <iostream.h>

#include "bot.h"
#include "collections.h"
#include "maze.h"

Bot::Bot( Maze& m )
    : maze( m )
{}

bool Bot::solve()
{
    maze.reset();
    maze.start();

    DirStack ds;
    ds.push( EAST );

    if( findSolution( ds ) ) {
        return true;
    } 

    ds.push( SOUTH );

    if( findSolution( ds ) ) {
        return true;
    }

    return false;
}

bool Bot::findSolution( DirStack& stack )
{
    bool solved = false;

    while( !stack.isEmpty() ) {
        if( solved ) {
			// If the maze has been solved, then all
			// we want to do is walk backwards along
			// the solution path, marking cells as we go.
            maze.getCell().setMark( true );
            Dir d = opposite( stack.pop() );
            maze.move( d );
        } else if( maze.isGoal() ) {
			// If this is the goal cell, then stop trying
			// to explore the maze and just start backing up.
            stack.pop();
            solved = true;
        } else {
			// We still have some work to do.  If we can move 
			// in the proposed direction, then do so, and start
			// exploring from there.  If not, either pick the
			// next direction clockwise or back up if we've 
			// run out of directions.

            if( maze.isClear( stack.top() ) ) {
                maze.move( stack.top() );
                stack.push( nextCCW( stack.top() ) );
            } else {
                while( true ) {
                    Dir next = nextCW( stack.pop() );
                    if( stack.isEmpty() ) {
						// Whoops, backed up too much.  Better stop.
                        return false;
                    }
                    if( next != opposite( stack.top() ) ) {
                        stack.push( next );
                        break;
                    } else {
						// We're trying to retrace our steps.  Back
						// out instead.
                        maze.move( opposite( stack.top() ) );
                    }
                }
            }
        }
    }

    if( solved ) {
        maze.getCell().setMark( true );
    }

    return solved;
}