import java.util.ArrayList;
import java.util.Collections;


public class IterativeDeepeningSearch extends SearchAlgorithmBase {
    private long statesGenerated;
    private long statesGeneratedInThisRound;

    public static void main(String args[]) {
        new IterativeDeepeningSearch(args).runSearchAlgorithm();
    }

    public IterativeDeepeningSearch(String args[]) {
        super(args);
    }

    protected ArrayList<Action> run() {
        System.out.println("Running iterative deepening search...");
        ArrayList<Action> solution;
        statesGenerated = 0;
        State init = stateSpace.init();
        System.out.println("initial state: " + init);
        for (int depthLimit = 0; true; depthLimit++) {
            System.out.println("Searching to depth " + depthLimit + "...");
            statesGeneratedInThisRound = 0;
            solution = depthLimitedSearch(init, depthLimit);
            System.out.println("" + statesGeneratedInThisRound
                               + " states generated in this round");
            if (solution != null) {
                /*
                  The code builds the solution in reverse order, so we
                  have to reverse it again before returning it.
                */
                Collections.reverse(solution);
                System.out.println("" + statesGenerated + " total states generated");
                return solution;
            }
        }
    }

    private ArrayList<Action> depthLimitedSearch(State s, int depthLimit) {
        statesGeneratedInThisRound++;
        statesGenerated++;
        if (stateSpace.isGoal(s))
            return new ArrayList<Action>();

        if (depthLimit > 0) {
            for (ActionStatePair pair : stateSpace.succ(s)) {
                ArrayList<Action> solution =
                    depthLimitedSearch(pair.state, depthLimit - 1);
                if (solution != null) {
                    solution.add(pair.action);
                    return solution;
                }
            }
        }

        return null;
    }
}