import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * A class that implements a breadth-first search algorithm
 * for finding the Configurations for which the isSolution predicate holds
 * 
 * @author Pieter Koopman, Sjaak Smetsers
 * @author Camil Staps, s4498062
 */
@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.
public class Solver
{
    // A queue for maintaining graphs that are not visited yet.
    private final Queue<Node<Configuration>> toExamine = new PriorityQueue<Node<Configuration>>();
    private final HashSet<Configuration> examined = new HashSet<Configuration>();
    
    private Node winner = null;

    public Solver(Configuration g) {
        toExamine.add(new Node(null, g));
    }
    
    /* A skeleton implementation of the solver
     * @return a string representation of the solution
     */
    public boolean solve () {
        while (!toExamine.isEmpty()) {
            Node next = toExamine.remove();
            Configuration nextConfiguration = (Configuration) next.getItem();
            examined.add(nextConfiguration);
            if (nextConfiguration.isSolution()) {
                winner = next;
                return true;
            } else {
                for (Configuration succ: nextConfiguration.successors()) {
                    if (!examined.contains(succ)) {
                        toExamine.add(new Node(next, succ));
                    }
                }
            }
        }
        return false;
    }
    
    /**
     * Return the winning Node (from which the path can be reconstructed)
     * @return the node in which we found a solution
     */
    public Node getWinner() {
        return winner;
    }
    
}