#include <iostream>
#include <vector>
#include <stack>
#include <SFML\System.hpp>
#include <SFML\Graphics.hpp>
#include "boost\smart_ptr\shared_ptr.hpp"

enum Walls {TOP, BOT, LEFT, RIGHT};

struct Cell
{
    unsigned int CoordX, CoordY;
    std::vector<Walls> WallList;
    bool Edge, Start, Exit, Visited;
};

typedef std::vector< std::vector< boost::shared_ptr <Cell> > > MazeType;

class Maze
{
    public:
        Maze(unsigned int pBoardWidth, unsigned int pBoardHeight);
        void PrintBoard(sf::RenderWindow &pApp);
        bool GenerateMaze(sf::RenderWindow &pApp);

    private:
        unsigned int mBoardWidth, mBoardHeight, mBoardSize, mVisitedCells;
        bool IsEdge(unsigned int pX, unsigned int pY);
        MazeType MazeBoard;
        MazeType InitBoard();
        std::stack<boost::shared_ptr<Cell> > PathStack;
};

bool Maze::GenerateMaze(sf::RenderWindow &pApp)
{
    boost::shared_ptr<Cell> CurrentCell (MazeBoard[1][1]);
    CurrentCell->Start = true;
    CurrentCell->Visited = true;
    MazeBoard[mBoardWidth-2][mBoardHeight-2]->Exit = true;
    while( (mVisitedCells <= mBoardSize) && pApp.IsOpened())
    {
        PrintBoard(pApp);
        sf::Event Event;
        while(pApp.GetEvent(Event))
        {
            if(Event.Type == sf::Event::Closed) pApp.Close();

            if(Event.Type == sf::Event::KeyPressed  && (Event.Key.Code == sf::Key::Escape)) pApp.Close();
        }

        CurrentCell->Visited = true;
        unsigned int x = CurrentCell->CoordX;
        unsigned int y = CurrentCell->CoordY;
        std::vector<boost::shared_ptr<Cell> > NBList;
        NBList.push_back(MazeBoard[y+1][x]);
        NBList.push_back(MazeBoard[y-1][x]);
        NBList.push_back(MazeBoard[y][x+1]);
        NBList.push_back(MazeBoard[y][x-1]);

        std::vector<boost::shared_ptr<Cell> > ValidNBList;
        for(unsigned int i = 0; i < NBList.size(); ++i)
        {
            boost::shared_ptr<Cell> TempCell (NBList[i]);
            if(TempCell->WallList.size() == 0 && !TempCell->Edge)
            {
                ValidNBList.push_back(TempCell);
            }
        }

        if(ValidNBList.size())
        {
            unsigned int n = rand()%ValidNBList.size();
            boost::shared_ptr<Cell> NewCell (ValidNBList[n]);

            if(y < NewCell->CoordY )
            {
                CurrentCell->WallList.push_back(RIGHT);
                NewCell->WallList.push_back(LEFT);
            }

            if(y > NewCell->CoordY)
            {
                CurrentCell->WallList.push_back(LEFT);
                NewCell->WallList.push_back(RIGHT);
            }

            if(x < NewCell->CoordX)
            {
                CurrentCell->WallList.push_back(BOT);
                NewCell->WallList.push_back(TOP);
            }

            if(x > NewCell->CoordX)
            {
                CurrentCell->WallList.push_back(TOP);
                NewCell->WallList.push_back(BOT);
            }
            mVisitedCells++;
            PathStack.push(CurrentCell);
            CurrentCell = NewCell;
            sf::Sleep(0.05f);
        }
        else
        {
            if(PathStack.size())
            {
                CurrentCell = PathStack.top();
                PathStack.pop();
            }
        }
    }
    return true;
}

bool Maze::IsEdge(unsigned int pX, unsigned int pY)
{
    if(pY == 0 || pY == mBoardWidth-1) return true;
    if(pX == 0 || pX == mBoardHeight-1) return true;

    return false;
}

void Maze::PrintBoard(sf::RenderWindow &pApp)
{
    pApp.Clear();
    for(unsigned int i = 0; i < mBoardHeight; ++i)
    {
        for(unsigned int j = 0; j < mBoardWidth; ++j)
        {
            int x = i * 12;
            int y = j * 12;

            if (MazeBoard[i][j]->Visited)
            {
                pApp.Draw(sf::Shape::Rectangle(x+3, y+3, x+9, y+9, sf::Color(255, 255, 255)));
                for(unsigned int k = 0; k < MazeBoard[i][j]->WallList.size(); ++k)
                {
                    switch (MazeBoard[i][j]->WallList.at(k))
                    {
                        case TOP:
                            pApp.Draw(sf::Shape::Rectangle(x+3, y, x+9, y+3, sf::Color(255, 255, 255)));
                        break;

                        case BOT:
                            pApp.Draw(sf::Shape::Rectangle(x+3, y+9, x+9, y+12, sf::Color(255, 255, 255)));
                        break;

                        case LEFT:
                            pApp.Draw(sf::Shape::Rectangle(x, y+3, x+3, y+9, sf::Color(255, 255, 255)));
                        break;

                        case RIGHT:
                            pApp.Draw(sf::Shape::Rectangle(x+9, y+3, x+12, y+9, sf::Color(255, 255, 255)));
                        break;
                    }
                }
            }
            if(MazeBoard[i][j]->Edge) pApp.Draw(sf::Shape::Rectangle(x, y, x+12, y+12, sf::Color(139, 137, 137)));

            if(MazeBoard[i][j]->Exit) pApp.Draw(sf::Shape::Rectangle(x, y, x+12, y+12, sf::Color(0, 0, 255)));

            if(MazeBoard[i][j]->Start) pApp.Draw(sf::Shape::Rectangle(x, y, x+12, y+12, sf::Color(0, 255, 0)));
        }
    }
    pApp.Display();
    return;
}

MazeType Maze::InitBoard()
{
    for(unsigned int i = 0; i < mBoardHeight; ++i)
    {
        std::vector<boost::shared_ptr<Cell> > TempVector;
        for(unsigned int j = 0; j < mBoardWidth; ++j)
        {
            boost::shared_ptr<Cell> TempPointer (new Cell);
            TempPointer->CoordX = j;
            TempPointer->CoordY = i;
            TempPointer->Edge = IsEdge(i,j);
            TempPointer->Start = false;
            TempPointer->Exit = false;
            TempPointer->Visited = false;
            if(TempPointer->Edge) mVisitedCells++;
            TempVector.push_back(TempPointer);
        }
        MazeBoard.push_back(TempVector);
    }
    return MazeBoard;
}

Maze::Maze(unsigned int pBoardWidth, unsigned int pBoardHeight)
{
    mBoardWidth = pBoardWidth;
    mBoardHeight = pBoardHeight;
    mBoardSize = mBoardWidth * mBoardHeight;
    mVisitedCells = 0;
    srand( time(NULL) );
    InitBoard();
}

int main(int argc, char *argv[])
{
    if(argc != 3)
    {
        std::cerr << "Incorrect parameter pattern." << std::endl;
        return 1;
    }

    unsigned int MazeWidth = atoi(argv[1]);
    unsigned int MazeHeight = atoi(argv[2]);

    if(MazeWidth < 4 || MazeHeight < 4)
    {
        std::cerr << "Smallest possible maze is 4x4." << std::endl;
        return 1;
    }

    unsigned int CellWidth = 12, CellHeight = 12;

    sf::RenderWindow App(sf::VideoMode(CellWidth * MazeWidth, CellHeight * MazeHeight, 32), "MazeGen", sf::Style::Close);

    Maze MyMaze (MazeWidth, MazeHeight);
    MyMaze.GenerateMaze(App);
    return 0;
}