#include <iostream.h>
#include <math.h>
#include <stdlib.h>

#include "maze.h"

Maze::Maze( int w, int h )
    : width( w )
    , height( h )
    , cursor_row( 0 )
    , cursor_col( 0 )
{
    cells = new Cell[ width * height ];
    generate();
}

bool Maze::open( int x, int y, Dir dir )
{
    int nx, ny;

    Cell& c1 = fetch( x, y );
    if( nudge( x, y, dir, nx, ny ) ) {
        Cell& c2 = fetch( nx, ny );
        c1.setOpen( dir, true );
        c2.setOpen( opposite( dir ), true );
        return true;
    }
    return false;
}

bool Maze::nudge( int x, int y, Dir dir, int& nx, int& ny )
{
    nx = x;
    ny = y;

    switch( dir ) {
    case NORTH:
        ny--;
        break;
    case WEST:
        nx--;
        break;
    case SOUTH:
        ny++;
        break;
    case EAST:
        nx++;
        break;
    }

    if( nx < 0 || nx >= width ) {
        return false;
    }

    if( ny < 0 || ny >= height ) {
        return false;
    }

    return true;
}

ostream& Maze::print( ostream& os )
{
    os << "+";
    for( int idx = 0; idx < width; idx++ ) {
        os << "-+";
    }
    os << endl;

    for( int row = 0; row < height; row++ ) {
        int col;
        os << "|";
        for( col = 0; col < width; col++ ) {
            if( fetch( col, row ).isMarked() ) {
                os << "#";
            } else {
                os << " ";
            }

            if( fetch( col, row ).isOpen( EAST ) ) {
                os << " ";
            } else {
                os << "|";
            }
        }
        os << endl;
        os << "+";

        for( col = 0; col < width; col++ ) {
            if( fetch( col, row ).isOpen( SOUTH ) ) {
                os << " ";
            } else {
                os << "-";
            } 
            os << "+";
        }

        os << endl;
    }

    return os;
}

void Maze::reset()
{
    for( int col = 0; col < width; col++ ) {
        for( int row = 0; row < height; row++ ) {
            fetch( col, row ).setMark( false );
        }
    }
}

void Maze::start()
{
    cursor_row = 0;
    cursor_col = 0;
}

bool Maze::move( Dir dir )
{
    if( fetch( cursor_col, cursor_row ).isOpen( dir ) ) {
        int nx;
        int ny;

        nudge( cursor_col, cursor_row, dir, nx, ny );
        cursor_col = nx;
        cursor_row = ny;
        return true;
    }

    return false;
}

Cell& Maze::getCell()
{
    return fetch( cursor_col, cursor_row );
}

bool Maze::isClear( Dir dir )
{
    return fetch( cursor_col, cursor_row ).isOpen( dir );
}

bool Maze::isGoal()
{
    return (cursor_col == width - 1) && (cursor_row == height - 1);
}

void Maze::generate()
{
    struct GenInfo {
        GenInfo()
            : col( -1 )
            , row( -1 )
            , dir( NORTH )
        {}

        GenInfo( int c, int r, Dir d )
            : col( c )
            , row( r )
            , dir( d )
        {}

        int col;
        int row;

        Dir dir;
    };

    // First, create a big array of all possible GenInfos.
    int size = 2*width*height - (width+height);
    GenInfo *gi1 = new GenInfo[ size ];
    GenInfo *gi2 = new GenInfo[ size ];

    int index = 0;
    int col;
    for( col = 0; col < width; col++ ) {
        for( int row = 0; row < (height-1); row++ ) {
            gi1[ index ] = GenInfo( col, row, SOUTH );
            index++;
        }
    }

    for( col = 0; col < (width-1); col++ ) {
        for( int row = 0; row < height; row++ ) {
            gi1[ index ] = GenInfo( col, row, EAST );
            index++;
        }
    }

    // Next, create a second array which is the first one randomized.
    index = 0;
    int cursz = size;
    int idx;
    for( idx = 0; idx < size; ++idx ) {
        index = (rand() * (RAND_MAX + 1) + rand()) % cursz;
        gi2[ idx ] = gi1[ index ];
        if( index != (cursz - 1) ) {
            gi1[ index ] = gi1[ cursz - 1 ];
        }
        cursz--;
    }

    // Now do the algorithm.
    for( idx = 0; idx < size; idx++ ) {
        int col = gi2[ idx ].col;
        int row = gi2[ idx ].row;
        Dir dir = gi2[ idx ].dir;
        int tcol;
        int trow;

        Cell& here = fetch( col, row );
        nudge( col, row, dir, tcol, trow );
        Cell& there = fetch( tcol, trow );
        if( !here.inSameGroup( there ) ) {
            open( col, row, dir );
            here.combineGroups( there );
        }

    }

    delete [] gi1;
    delete [] gi2;
}