/*
 * File: SolveMaze.cpp
 * -------------------
 * This program solves a maze by recursive backtracking, and compares
 * this approach to iterative approaches using Stack (depth-first)
 * and Queue (breadth-first).
 *
 * (c) Cynthia Lee and Jerry Cain
 */

#include <fstream>
#include <iostream>
#include <string>
#include "direction.h"
#include "gwindow.h"
#include "maze.h"
#include "point.h"
#include "stack.h"
#include "queue.h"
#include "simpio.h"
using namespace std;

/* Function prototypes */

bool solveMaze(Maze & maze, Point pt);
bool solveMazeStack(Maze & maze, Point start);
bool solveMazeQueue(Maze & maze, Point start);
Point adjacentPoint(Point start, Direction dir);

/* Main program */

int main() {
    GWindow gw;
    while (true) {
        Maze maze("SampleMaze.txt", gw);
        string response = getLine("How do you want to solve the maze?\n[R]ecursive, or [S]tack, or [Q]ueue? ");
        bool foundSolution = false;
        if (response == "") break;
        else if (response == "r" || response == "R")
            foundSolution = solveMaze(maze, maze.getStartPosition());
        else if (response == "s" || response == "S")
            foundSolution = solveMazeStack(maze, maze.getStartPosition());
        else if (response == "q" || response == "Q")
            foundSolution = solveMazeQueue(maze, maze.getStartPosition());
        if (foundSolution) {
            cout << "The marked path is a solution." << endl;
            pause(800);
        } else {
            cout << "No solution exists." << endl;
        }
        cout << endl;
    }

   return 0;
}

/*
 * Function: solveMaze
 * Usage: solveMaze(maze, start);
 * ------------------------------
 * Attempts to generate a solution to the current maze from the specified
 * start point.  The solveMaze function returns true if the maze has a
 * solution and false otherwise.  The implementation uses recursion
 * to solve the submazes that result from marking the current square
 * and moving one step along each open passage.
 */
//Maze functions:
// maze.isOutSide(pt)
// maze.isMarked(pt)
// maze.markSquare(pt)
// maze.wallExists(pt,dir)
// pause(200)
// adjacentPoint(pt, dir)
// looping over directions: for (Direction dir = NORTH; dir <= WEST; dir++) {
bool solveMaze(Maze & maze, Point start) {
    if (maze.isOutside(start)) return true;
    if (maze.isMarked(start)) return false;
    pause(200);
    maze.markSquare(start);
    for (Direction dir = NORTH; dir <= WEST; dir++) {
        if (!maze.wallExists(start, dir)) {
            if (solveMaze(maze, adjacentPoint(start, dir))) {
                return true;
            }
        }
    }
    maze.unmarkSquare(start);
    return false;
}















bool solveMazeStack(Maze & maze, Point start) {
    Vector<Direction> compass;
    compass += WEST, SOUTH, EAST, NORTH;
    Stack<Point> toExplore;
    toExplore.push(start);
    while(!toExplore.isEmpty()){
        Point current = toExplore.pop();
        if (maze.isOutside(current)) return true;
        if (maze.isMarked(current)) continue;
        maze.markSquare(current);
        pause(200);
        for (Direction dir : compass) {
            if (!maze.wallExists(current, dir)) {
                toExplore.push(adjacentPoint(current,dir));
            }
        }
    }
   return false;
}


bool solveMazeQueue(Maze & maze, Point start) {
    Vector<Direction> compass;
    compass += WEST, SOUTH, EAST, NORTH;
    Queue<Point> toExplore;
    toExplore.enqueue(start);
    while(!toExplore.isEmpty()){
        Point current = toExplore.dequeue();
        if (maze.isOutside(current)) return true;
        if (maze.isMarked(current)) continue;
        maze.markSquare(current);
        pause(200);
        for (Direction dir : compass) {
            if (!maze.wallExists(current, dir)) {
                toExplore.enqueue(adjacentPoint(current,dir));
            }
        }
    }
   return false;
}


/*
 * Function: adjacentPoint
 * Usage: Point finish = adjacentPoint(start, dir);
 * ------------------------------------------------
 * Returns the point that results from moving one square from start
 * in the direction specified by dir.  For example, if pt is the
 * point (1, 1), calling adjacentPoint(pt, EAST) returns the
 * point (2, 1).  To maintain consistency with the graphics package,
 * the y coordinates increase as you move downward on the screen.  Thus,
 * moving NORTH decreases the y component, and moving SOUTH increases it.
 */

Point adjacentPoint(Point start, Direction dir) {
   switch (dir) {
    case NORTH: return Point(start.getX(), start.getY() - 1);
    case EAST:  return Point(start.getX() + 1, start.getY());
    case SOUTH: return Point(start.getX(), start.getY() + 1);
    case WEST:  return Point(start.getX() - 1, start.getY());
   }
   return start;
}
