package hw3.puzzle;
import  edu.princeton.cs.algs4.MinPQ;
import  java.util.ArrayList;


/**
 * Created by Tim on 3/20/17.
 */
public class Solver {

    private ArrayList<WorldState> solution;
    MinPQ<SearchNode> priorityQueue;

    public Solver(WorldState initial) {
        priorityQueue = new MinPQ();
        SearchNode currentNode = new SearchNode(initial);
        solution = new ArrayList<WorldState>();
        priorityQueue.insert(currentNode);

        //ALGORITHM
        while (!priorityQueue.min().currentWorldState.isGoal()) {
            currentNode = priorityQueue.delMin();
            solution.add(currentNode.currentWorldState);
            for (WorldState x : currentNode.currentWorldState.neighbors()) {
                if (currentNode.preNode != null) { //if it's not the starting word
                    if (!x.equals(currentNode.preNode.currentWorldState)) { //making sure there's no backtracking
                        priorityQueue.insert(new SearchNode(x, currentNode.preMoves + 1, currentNode));
                    }
                } else {
                    priorityQueue.insert(new SearchNode(x, currentNode.preMoves + 1, currentNode));
                }
            }
            if (priorityQueue.min().currentWorldState.isGoal()) {
                solution.add(priorityQueue.min().currentWorldState);
            }
        }
    }

    public int moves() {
        return priorityQueue.min().preMoves;
    }

    public Iterable<WorldState> solution() {
        return solution;
    }

    private class SearchNode implements Comparable<SearchNode> {

        public WorldState currentWorldState;
        public int preMoves;
        public SearchNode preNode;

        //beginning search node
        public SearchNode(WorldState worldState1) {
            this(worldState1, 0, null);
        }

        //generic search node
        public SearchNode(WorldState worldState1, int preMoves1, SearchNode preNode1) {
            currentWorldState = worldState1;
            preMoves = preMoves1;
            preNode = preNode1;
        }

        @Override
        public int compareTo(SearchNode one) {
            if (one.currentWorldState.estimatedDistanceToGoal() + preMoves < this.currentWorldState.estimatedDistanceToGoal() + preMoves) {
                return 1;
            } else if (one.currentWorldState.estimatedDistanceToGoal() + preMoves > this.currentWorldState.estimatedDistanceToGoal() + preMoves) {
                return -1;
            } else {
                return 0;
            }
        }

    }

}