package assignment9;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;

import assignment6.MyLinkedList;

public class PathFinder {

    public static int row;
    public static int column;
    public static int sRow;
    public static int sColumn;
    public static int gRow;
    public static int gColumn;
    public static ArrayList<node> path = new ArrayList<node>();
    public static MyQueue<node> queue = new MyQueue<node>();

    // subclass called node
    public static class node {
        boolean visited;
        char data;
        node left;
        node right;
        node up;
        node down;
        node from;
        int nRow;
        int nColumn;

        // node constructor
        public node(char data, node left, node right, node up, node down,
                int nRow, int nColumn) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.up = up;
            this.down = down;
            // marking the node as false when created
            this.visited = false;
            // takes down the node it came from in the bfs
            this.from = null;
            // node position
            this.nRow = nRow;
            this.nColumn = nColumn;
        }
    }

    // queue class based off linked list
    public static class MyQueue<E> {

        private MyLinkedList<E> queue;

        public MyQueue() {
            queue = new MyLinkedList<E>();
        }

        /**
         * Removes all of the elements from the stack.
         */
        public void clear() {
            // FILL IN
            queue.clear();
        }

        /**
         * Returns true if the stack contains no elements.
         */
        public boolean isEmpty() {
            // FILL IN
            return queue.isEmpty();
        }

        /**
         * Returns the item at the top of the stack without removing it from the
         * stack. Throws NoSuchElementException if the stack is empty.
         */
        public E peek() throws NoSuchElementException {
            // FILL IN
            return (E) queue.getLast();
        }

        /**
         * Returns and removes the item at the bottom of the queue. Throws
         * NoSuchElementException if the stack is empty.
         */
        public E pop() throws NoSuchElementException {
            // FILL IN
            return (E) queue.removeFirst();
        }

        /**
         * Pushes the input item onto the top of the stack.
         */
        public void push(E item) {
            // FILL IN
            queue.addLast(item);
        }

        /**
         * Returns the number of items in the stack.
         */
        public int size() {
            return queue.size();
        }
    }

    public static void solveMaze(String inputFile) {
        node[][] map;
        ArrayList<node> path;
        try {
            map = translate(inputFile);
            // connects adjacent nodes
            pointNodes(map);
            // makes a path from g to s and storing the path in an array list
            path = reconstructPath(map, map[gRow][gColumn]);
            // go back from the array list path
            map = drawPath(map, path);
            // print out path
            for(int r = 0; r < row; r++) {
                for(int c = 0; c < column; c++) {
                    System.out.print(map[r][c].data);
                }
                System.out.print('\n');
            }
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            System.out.println("solveMaze error");
            e.printStackTrace();
        }
    }

    /**
     * translates the maze into an array of arrays of nodes called map
     *
     * @param inputFile
     * @throws FileNotFoundException
     */
    public static node[][] translate(String inputFile)
            throws FileNotFoundException {
        String rowString = null;
        String dimensions = null;
        char ch;
        Scanner s = new Scanner(new FileReader(inputFile));
        dimensions = s.nextLine();
        Scanner d = new Scanner(dimensions);
        row = Integer.parseInt(d.next());
        column = Integer.parseInt(d.next());
        System.out.println(row + " " + column);
        node[][] map = new node[row][column];
        for (int r = 0; r < row; r++) {
            if (s.hasNextLine()) {
                rowString = s.nextLine();
                System.out.println(rowString);
            }
            for (int c = 0; c < column; c++) {
                ch = rowString.charAt(c);
                if (ch == 'X') {
                    // create node
                    map[r][c] = new node(ch, null, null, null, null, r, c);
                }
                // check for 'S'
                else if (ch == 'S') {
                    sRow = r;
                    sColumn = c;
                    // create node
                    map[r][c] = new node(ch, null, null, null, null, r, c);
                } else if (ch == 'G') {
                    gRow = r;
                    gColumn = c;
                    // create node
                    map[r][c] = new node(ch, null, null, null, null, r, c);
                } else {
                    // create node
                    map[r][c] = new node(ch, null, null, null, null, r, c);
                }
            }
        }
        s.close();
        return map;
    }

    /**
     * points all the nodes in the array of arrays to their correct neighbors
     *
     * @param map
     */
    public static void pointNodes(node[][] map) {
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < column; c++) {

                // top row
                // first row first column
                if (r == 0 && c == 0) {
                    map[r][c].right = map[r][c + 1];
                    map[r][c].down = map[r + 1][c];
                }
                // first row last column
                else if (r == 0 && c == column - 1) {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].down = map[r + 1][c];
                }
                // first row in between
                else if (r == 0 && c > 0 && c < column - 1) {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].right = map[r][c + 1];
                    map[r][c].down = map[r + 1][c];
                }

                // bottom row
                // last row first column
                else if (r == row - 1 && c == 0) {
                    map[r][c].right = map[r][c + 1];
                    map[r][c].up = map[r - 1][c];
                }
                // last row last column
                else if (r == row - 1 && c == column - 1) {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].up = map[r - 1][c];
                }
                // last row in between
                else if (r == row - 1 && c > 0 && c < column - 1) {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].right = map[r][c + 1];
                    map[r][c].up = map[r - 1][c];
                }

                // first column in between
                else if (r > 0 && r < row - 1 && c == 0) {
                    map[r][c].right = map[r][c + 1];
                    map[r][c].up = map[r - 1][c];
                    map[r][c].down = map[r + 1][c];
                }

                // last column in between
                else if (r > 0 && r < row - 1 && c == column - 1) {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].up = map[r - 1][c];
                    map[r][c].down = map[r + 1][c];
                }

                // everything else
                else {
                    map[r][c].left = map[r][c - 1];
                    map[r][c].right = map[r][c + 1];
                    map[r][c].up = map[r - 1][c];
                    map[r][c].down = map[r + 1][c];
                }
            }
        }
    }

    /**
     * returns true if you can get from 'S' to 'G', false otherwise
     *
     * @param map
     * @return
     */
    public boolean bfs(node[][] map, node n) {
        if (n.data == 'G') {
            return true;
        } else {
            if (n.left.data != 'X' && n.left.visited == false) {
                queue.push(map[sRow][sColumn].left);
                n.left.visited = true;
                n.left.from = n;
            }
            if (n.right.data != 'X' && n.right.visited == false) {
                queue.push(map[sRow][sColumn].right);
                n.right.visited = true;
                n.right.from = n;
            }
            if (n.up.data != 'X' && n.up.visited == false) {
                queue.push(map[sRow][sColumn].up);
                n.up.visited = true;
                n.up.from = n;
            }
            if (n.down.data != 'X' && n.down.visited == false) {
                queue.push(map[sRow][sColumn].down);
                n.down.visited = true;
                n.down.from = n;
            }
            if (queue.isEmpty()) {
                return false;
            } else {
                return bfs(map, queue.pop());
            }
        }
    }

    /**
     * reconstructs the path back from 'G' to the node containing 'S'
     *
     * @param map
     * @param n
     * @return
     */
    public static ArrayList<node> reconstructPath(node[][] map, node n) {
        if (n.from.data == 'S') {
            path.add(n);
            path.add(n.from);
            return path;
        } else {
            path.add(n.from);
            return reconstructPath(map, n.from);
        }
    }

    /**
     * puts a '.' instead of ' ' through the path
     *
     * @param map
     * @param path
     * @return
     */
    public static node[][] drawPath(node[][] map, ArrayList<node> path) {
        for (int i = 0; i < path.size(); i++) {
            if (path.get(i).data == ' ') {
                map[path.get(i).nRow][path.get(i).nColumn].data = '.';
            }
        }
        return map;
    }

    public static void main(String[] args) {
        solveMaze("tinyMaze.txt");
    }
}