package am.aua.search;

public class IterativeDeepeningTreeSearch implements Search {
    private Frontier frontier;
    private Node solution;

    // statistics
    // keeps track of how many nodes where generated during last search
    private int steps;

    public IterativeDeepeningTreeSearch() {
        frontier = new DepthFirstFrontier();
    }

    @Override
    public Node search(State initialState, GoalTest test) {
        steps = 0;
        int depth = 30;
        while (true) {
            Result result = depthLimitedSearch(initialState, test, depth);
            if (result != Result.CUTOFF) return solution;
        }
    }

    private Result depthLimitedSearch(State initialState, GoalTest test, int limit) {
        frontier.clear();

        Node node = new Node(null, null, initialState, 0);
        steps++;
        frontier.add(node);
        Result result = Result.FAILURE;
        while (!frontier.isEmpty()) {
            node = frontier.remove();
            if (test.isGoal(node.state)) {
                solution = node;
                return Result.SOLUTION;
            }
            if (node.depth > limit) {
                result = Result.CUTOFF;
            }
            else if (!isCycle(node)) {
                for (Action action : node.state.getApplicableActions()) {
                    State newState = node.state.getActionResult(action);
                    Node child = new Node(node, action, newState, node.depth + 1);
                    steps++;
                    frontier.add(child);
                }
            }
        }
        return result;
    }

    private boolean isCycle (Node node) {
        Node prev = node.parent;
        while (prev != null) {
            if (prev.state.equals(node.state))
                return true;
            prev = prev.parent;
        }
        return false;
    }

    @Override
    public int steps() {
        return steps;
    }

    @Override
    public int stretchFactor() {
        return frontier.stretchFactor();
    }

    @Override
    public String toString() {
        return "Iterative Deepening Tree Search";
    }

    private enum Result {
        SOLUTION,
        FAILURE,
        CUTOFF
    }
}