package am.aua.search;

public class BreadthFirstTreeSearch implements Search{
	private Frontier frontier;

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

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

	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);
		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;
				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 Tree Search with Early Goal test";
	}
}