#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

#define BYTE unsigned char

// wall & visited flag vales
const BYTE CELL_TOP = 1;
const BYTE CELL_BOTTOM = 2;
const BYTE CELL_LEFT = 4;
const BYTE CELL_RIGHT = 8;
const BYTE CELL_VISITED = 16;

// maze dimensions
const int MAZE_ROWS = 3;
const int MAZE_COLS = 3;


// starting cell
const int START_CELL_ROW = 0;
const int START_CELL_COL = 0;
const int START_WALL = CELL_LEFT;

// ending cell
const int END_CELL_ROW = 2;
const int END_CELL_COL = 2;
const int END_WALL = CELL_RIGHT;

// location indexes
const int CELL_ROW_INDEX = 0;
const int CELL_COL_INDEX = 1;


// maze print characters
const char OUT_TOP_LEFT = '-';
const char OUT_TOP_MID = '-';
const char OUT_TOP_RIGHT = '-';
const char OUT_SIDE_LEFT = '|';
const char OUT_SIDE_RIGHT = '|';
const char OUT_BOT_LEFT = '-';
const char OUT_BOT_MID = '-';
const char OUT_BOT_RIGHT = '-';
const char INSIDE_MIDDLE = '+';
const char CELL_TOP_BOT = '-';
const char CELL_LEFT_RIGHT = '|';
const char CELL_OPEN_HORZ = ' ';
const char CELL_OPEN_VERT = ' ';
const char CELL_VISITIED_ON = '.';
const char CELL_VISITIED_OFF = ' ';

// function declarations
bool hasUnvisitedCells(BYTE cells[][MAZE_COLS]);
bool hasAvailableNeighbors(BYTE cells[][MAZE_COLS], int location[]);
void chooseRandomNeighbor(BYTE cells[][MAZE_COLS], int current[], int neighbor[]);
void removeWalls(BYTE cells[][MAZE_COLS], int current[], int neighbor[]);
void initMaze(BYTE cells[][MAZE_COLS]);
int pushStack(int stack[][2], int location[], int stackPoint);
void popStack(int stack[][2], int location[], int& stackPoint);
void copyOneLocTwo(int locOne[], int locTwo[]);
void printMaze(BYTE cells[][MAZE_COLS]);
void printMazeDebug(BYTE cells[][MAZE_COLS]);


int main() {
    char tmp;                           // pause program

                                        // init random generator
    srand(time(NULL));                  // stdlib; time.h

    // sotrage for the maze cells
    BYTE maze[MAZE_ROWS][MAZE_COLS] = { 0 };

    // storage for our stack of visited cells
    int stack[MAZE_ROWS * MAZE_COLS][2] = { 0 };

    int stackPointer = -1;              // empty stack value

    initMaze(maze);

    // set starting cell
    int startCell[2];
    startCell[CELL_ROW_INDEX] = START_CELL_ROW;
    startCell[CELL_COL_INDEX] = START_CELL_COL;
    // turn off starting wall
    maze[startCell[CELL_ROW_INDEX]][startCell[CELL_COL_INDEX]] ^= START_WALL;

    // turn off ending wall
    maze[END_CELL_ROW][END_CELL_COL] ^= END_WALL;

    printMaze(maze);

    cout << endl;

    printMazeDebug(maze);

    cout << endl;

    cin >> tmp;

    // 1. Make the inital cell the current cell and mark it as visited
    int currentCell[2];
    copyOneLocTwo(startCell, currentCell);
    // mark visited flag
    maze[currentCell[CELL_ROW_INDEX]][currentCell[CELL_COL_INDEX]] ^= CELL_VISITED;


    // 2. While there are unvisited cells
    while (hasUnvisitedCells(maze)) {

        // i. if the current cell has any neighbors which have not been visited
        if (hasAvailableNeighbors(maze, currentCell)) {

            // 1. Chose randomly one of the unvisited neighbors
            int neighborCell[2] = { 0 };
            chooseRandomNeighbor(maze, currentCell, neighborCell);

            // 2. Push the current cell to the stack
            stackPointer = pushStack(stack, currentCell, stackPointer);

            // 3. Remove the wall between the current cell and the chosen cell
            removeWalls(maze, currentCell, neighborCell);

            // 4. Make the chosen cell the current cell and mark it as visited
            copyOneLocTwo(neighborCell, currentCell);
            // mark visited flag
            maze[currentCell[CELL_ROW_INDEX]][currentCell[CELL_COL_INDEX]] ^= CELL_VISITED;

            // 5. Print the Maze
            printMaze(maze);
            cout << endl;

            printMazeDebug(maze);
            cout << endl;

            cin >> tmp;

        } // end has any neighbors

          // ii. Else if the stack is not empty
        else if (stackPointer > -1) {

            // Pop the last cell from the stack and make it the current cell
            popStack(stack, currentCell, stackPointer);

        }


    } // end while there are unvisitied cells


      // 3. Print the Maze
    printMaze(maze);
    cout << endl;

    printMazeDebug(maze);
    cout << endl;

    // pause program
    cin >> tmp;

    return 0;
} // end main

  /***/
bool hasUnvisitedCells(BYTE cells[][MAZE_COLS]) {

    bool isVisited = true;

    int row = 0;


    while (isVisited && row < MAZE_ROWS) {

        int col = 0;
        while (isVisited && col < MAZE_COLS) {

            isVisited = cells[row][col] & CELL_VISITED;
            col++;
        }

        row++;
    }

    return !isVisited;
}


/**
* Checks to see if there are any available neigbors
* @param cells - the maze
* @param location - the position of the cells
*/
bool hasAvailableNeighbors(BYTE cells[][MAZE_COLS], int location[]) {
    // check if has neighbor above

    if (location[CELL_ROW_INDEX] > 0) {
        // check if not visited
        if (!(cells[location[CELL_ROW_INDEX] - 1][location[CELL_COL_INDEX]] & CELL_VISITED)) {
            return true;
        }
    }

    // check if has neighbor below

    if (location[CELL_ROW_INDEX] < MAZE_ROWS - 1) {
        // check if not visited
        if (!(cells[location[CELL_ROW_INDEX] + 1][location[CELL_COL_INDEX]] & CELL_VISITED)) {
            return true;
        }
    }

    // check if has left neighbor

    if (location[CELL_COL_INDEX] > 0) {
        // check if not visited
        if (!(cells[location[CELL_ROW_INDEX]][location[CELL_COL_INDEX] - 1] & CELL_VISITED)) {
            return true;
        }
    }

    // check if has right neighbor

    if (location[CELL_COL_INDEX] < MAZE_COLS - 1) {
        // check if not visited
        if (!(cells[location[CELL_ROW_INDEX]][location[CELL_COL_INDEX] + 1] & CELL_VISITED)) {
            return true;
        }
    }

    return false;

} // end hasAvailableNeighbors


  /**
  * Chooses a random neighbor in the maze
  * @param cells - the maze
  * @param current - the current position of the maze
  * @param neighbor - the position of the neighbor
  */
void chooseRandomNeighbor(BYTE cells[][MAZE_COLS], int current[], int neighbor[]) {

    bool done = false;

    while (!done) {
        int randNeighbor = rand() % 4;      // random 0 through 3

        switch (randNeighbor) {

        case 0:                     // TOP
            if (current[CELL_ROW_INDEX] > 0) {
                if (!(cells[current[CELL_ROW_INDEX] - 1][current[CELL_COL_INDEX]] & CELL_VISITED)) {

                    neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX] - 1;
                    neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX];

                    done = true;

                }
            }
            break;

        case 1:                     // BOTTOM
            if (current[CELL_ROW_INDEX] < MAZE_ROWS - 1) {
                if (!(cells[current[CELL_ROW_INDEX] + 1][current[CELL_COL_INDEX]] & CELL_VISITED)) {

                    neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX] + 1;
                    neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX];

                    done = true;

                }
            }
            break;

        case 2:                     // LEFT
            if (current[CELL_COL_INDEX] > 0) {
                if (!(cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX] - 1] & CELL_VISITED)) {

                    neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX];
                    neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX] - 1;

                    done = true;
                }
            }
            break;

        case 3:                     // RIGHT
            if (current[CELL_COL_INDEX] < MAZE_COLS - 1) {
                if (!(cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX] + 1] & CELL_VISITED)) {

                    neighbor[CELL_ROW_INDEX] = current[CELL_ROW_INDEX];
                    neighbor[CELL_COL_INDEX] = current[CELL_COL_INDEX] + 1;

                    done = true;

                }
            }
            break;

        } // end switch


    }

} //end chooseRandomNeighbor


  /**
  * Remove the wall between the current cell and the chosen cell
  * @param cells - the maze
  * @param current - the current position of the maze
  * @param neighbor - the position of the neighbor
  */
void removeWalls(BYTE cells[][MAZE_COLS], int current[], int neighbor[]) {

    // test for the location of current and neighbor

    // test for neighbor above
    if (neighbor[CELL_ROW_INDEX] < current[CELL_ROW_INDEX]) {

        cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_BOTTOM;   // toggle wall off
        cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_TOP;
    }


    // test for neighbor below

    else if (neighbor[CELL_ROW_INDEX] > current[CELL_ROW_INDEX]) {

        cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_TOP;      // toggle wall off
        cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_BOTTOM;
    }

    // test for neighbor left

    else if (neighbor[CELL_COL_INDEX] < current[CELL_COL_INDEX]) {

        cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_RIGHT;    // toggle wall off
        cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_LEFT;
    }

    // neighbor must be right

    else {

        cells[neighbor[CELL_ROW_INDEX]][neighbor[CELL_COL_INDEX]] ^= CELL_LEFT;     // toggle wall off
        cells[current[CELL_ROW_INDEX]][current[CELL_COL_INDEX]] ^= CELL_RIGHT;

    }
} // end removeWalls


  /**
  * Initialize maze array elements to turn all
  * walls on and visited off
  * @param cells - the grid of cells in the maze
  */
void initMaze(BYTE cells[][MAZE_COLS]) {

    for (int row = 0; row < MAZE_ROWS; row++) {

        for (int col = 0; col < MAZE_COLS; col++) {
            cells[row][col] = CELL_TOP | CELL_BOTTOM | CELL_LEFT | CELL_RIGHT;
        }
    }

}


/*
* Adds a cell location onto the stack
* @param stack - the location stack
* @param location - row and col of a maze cell
* @param stackPoint - last location added to the stack
* @return int - new stack pointer
*/
int pushStack(int stack[][2], int location[], int stackPoint) {
    int spNew = stackPoint;

    spNew++;                    // move sp up the stack
    copyOneLocTwo(location, stack[spNew]);

    return spNew;

}


/*
* Pull a cell location off the stack
* @param stack - the location stack
* @param location - row and col of a maze cell
* @param stackPoint - last location added to the stack and return new
*/
void popStack(int stack[][2], int location[], int& stackPoint) {

    copyOneLocTwo(stack[stackPoint], location);
    stackPoint--;


}


/*
* Copies the contents of one location to another
* @param locOne - one location
* @param locTwo - another location
*/
void copyOneLocTwo(int locOne[], int locTwo[]) {

    locTwo[CELL_ROW_INDEX] = locOne[CELL_ROW_INDEX];
    locTwo[CELL_COL_INDEX] = locOne[CELL_COL_INDEX];
}


/**
* Printing the maze to the console
* @param cells - the grid of cells in the maze
*/
void printMaze(BYTE cells[][MAZE_COLS]) {

    for (int row = 0; row < MAZE_ROWS; row++) {

        // print the top row of the cells
        for (int col = 0; col < MAZE_COLS; col++) {

            /*** print left spacer ***/

            // are we on the top row
            if (row == 0) {

                // are we on the left wall
                if (col == 0) {



                    cout << OUT_TOP_LEFT;
                }
                else {
                    cout << OUT_TOP_MID;
                }

            }

            else { // not on top row

                   // are we on the left wall
                if (col == 0) {



                    cout << OUT_SIDE_LEFT;
                }
                else {
                    cout << INSIDE_MIDDLE;
                }

            }

            // print top left spacer

            /*** print cell top ***/

            if (cells[row][col] & CELL_TOP) {
                cout << CELL_TOP_BOT;
            }
            else {
                cout << CELL_OPEN_HORZ;
            }

            // print last right spacer
            if (col == MAZE_COLS - 1) {

                //top row
                if (row == 0) {
                    cout << OUT_TOP_RIGHT;
                }
                else { // not top row
                    cout << OUT_SIDE_RIGHT;
                }
            }


        } //print top row

          // move down to start printing side walls
        cout << endl;

        // print side walls of the cells
        for (int col = 0; col < MAZE_COLS; col++) {

            // prints cell left side wall
            if (cells[row][col] & CELL_LEFT) {
                cout << CELL_LEFT_RIGHT;

            }
            else {
                cout << CELL_OPEN_VERT;
            }

            // print cell visited
            if (cells[row][col] & CELL_VISITED) {
                cout << CELL_VISITIED_ON;

            }
            else {
                cout << CELL_VISITIED_OFF;
            }

            // print right wall
            if (col == MAZE_COLS - 1) {

                // prints cell right side wall
                if (cells[row][col] & CELL_RIGHT) {
                    cout << CELL_LEFT_RIGHT;

                }
                else {
                    cout << CELL_OPEN_VERT;
                }
            }


        } // print side walls

          // move down to start printing next top walls
        cout << endl;

        // print bottom row
        if (row == MAZE_ROWS - 1) {

            // print the bottom row of the cell walls
            for (int col = 0; col < MAZE_COLS; col++) {

                // print spacer
                if (col == 0) {
                    cout << OUT_BOT_LEFT;
                }
                else {
                    cout << OUT_BOT_MID;
                }

                // print cell bottom wall
                if (cells[row][col] & CELL_BOTTOM) {
                    cout << CELL_TOP_BOT;
                }
                else {
                    cout << CELL_OPEN_HORZ;
                }

                // print right corner
                if (col == MAZE_COLS - 1) {
                    cout << OUT_BOT_RIGHT;
                }

            } // bottom walls


              // end the cells
            cout << endl;

        } // bottom row


    } // end row loop

} // end printMaze



  /**
  * Printing the maze call values to the console
  * @param cells - the grid of cells in the maze
  */
void printMazeDebug(BYTE cells[][MAZE_COLS]) {

    for (int row = 0; row < MAZE_ROWS; row++) {

        for (int col = 0; col < MAZE_COLS; col++) {

            cout << to_string(int(cells[row][col])) << " ";
        }

        cout << endl;
    }

}