package hw3.puzzle;

import  edu.princeton.cs.algs4.MinPQ;
import java.util.HashSet;
import java.util.LinkedList;

public class Solver {
    private int moves;
    private LinkedList<WorldState> solution = new LinkedList<>();
    private HashSet<WorldState> worldStateSet;
    /*
    Constructor which solves the puzzle, computing
                 everything necessary for moves() and solution() to
                 not have to solve the problem again. Solves the
                 puzzle using the A* algorithm. Assumes a solution exists.
     */

    public Solver(WorldState initial) {
        worldStateSet = new HashSet<>();
        Iterable<WorldState> neighbors;
        SearchNode currNode = new SearchNode(initial);
        MinPQ<SearchNode> queue = new MinPQ<>();
        queue.insert(currNode);
        queue.delMin();

        while (!currNode.getWorldState().isGoal()) {
            neighbors = currNode.getWorldState().neighbors();
            for (WorldState i: neighbors) {
                if (!worldStateSet.contains(i)) {
                    queue.insert(new SearchNode(i, moves() + 1, currNode));
                    worldStateSet.add(currNode.getWorldState());
                }
            }
            currNode = queue.delMin();
        }

        while (currNode != null) {
            solution.addFirst(currNode.getWorldState());
            currNode = currNode.getPrevNode();
        }
    }

    /*
    Returns the minimum number of moves to solve the puzzle starting
                 at the initial WorldState.
     */
    public int moves() {
        return solution.size();
    }

    /*
    Returns a sequence of WorldStates from the initial WorldState
    to the solution.
    */
    public Iterable<WorldState> solution() {
        return solution;
    }

    public class SearchNode implements Comparable<SearchNode> {
        private WorldState worldState;
        private int numMoves;
        private SearchNode prevNode;

        public SearchNode() {
            worldState = null;
            numMoves = 0;
            prevNode = null;
        }

        public SearchNode(WorldState word) {
            this.worldState = word;
            numMoves = 0;
            prevNode = null;
        }

        public SearchNode(WorldState word, int numMoves, SearchNode prevNode) {
            this.worldState = word;
            this.numMoves = numMoves;
            this.prevNode = prevNode;
        }

        public WorldState getWorldState() {
            return worldState;
        }

        public int getMoves() {
            return numMoves;
        }

        public SearchNode getPrevNode() {
            return prevNode;
        }

        public int compareTo(SearchNode n2) {
            if ((getWorldState().estimatedDistanceToGoal() + getMoves()) >
                    n2.getWorldState().estimatedDistanceToGoal() + n2.getMoves()) {
                return 1;
            } else if(getWorldState().estimatedDistanceToGoal() < n2.getWorldState().estimatedDistanceToGoal()){
                return -1;
            } else {
                return 0;
            }
        }

    }
}