package am.aua.search;

import java.util.HashSet;

public class BreadthFirstGraphSearch implements Search{
    private Frontier frontier;

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

    public BreadthFirstGraphSearch () {
        frontier = new BreadthFirstFrontier();
        steps = 0;
    }

    @Override
    public Node search(State initialState, GoalTest goalTest) {
        frontier.clear();
        steps = 1;

        Node node = new Node(null, null, initialState);
        if (goalTest.isGoal(node.state))
            return node;
        frontier.add(node);
        HashSet<State> expanded = new HashSet<>();
        expanded.add(node.state);
        while (!frontier.isEmpty()) {
            node = frontier.remove();
            for (Action action : node.state.getApplicableActions()) {
                State newState = node.state.getActionResult(action);
                Node child = new Node(node, action, newState);
                steps++;
                if (goalTest.isGoal(newState)) return child;
                if (!expanded.contains(newState)) {
                    expanded.add(newState);
                    frontier.add(child);
                }
            }
        }
        return null;
    }

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

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

    @Override
    public String toString() {
        return "Breadth First Graph Search with Early Goal test";
    }
}