/**
 */


import java.util.Set;
import java.util.HashSet;
import java.util.ArrayDeque;


class SimpleStateSpaceSearch 
implements StateSpaceSearch


  /**

   */

  private Set<Path>
  initialPaths(Problem problem)

    final Set<Path> paths = new HashSet<Path>()

    for (Problem.State s : problem.initialStates())
      paths.add(new Path(s))

    return paths


  /**

   */

  private Path
  pick(Set<Path> paths)

    for (Path path : paths)
      paths.remove(path)
      return path

    assert false

    return null


  /**

   */

  public SolutionPath
  search(Problem problem)

    final Set<Path> pendingPaths = initialPaths(problem)

    while (!pendingPaths.isEmpty())

      final Path path = pick(pendingPaths)

      for (Problem.State neighbor : problem.moveResults(path.lastState()))

	final Path newPath = path.addStep(neighbor)

	if (problem.isGoalState(neighbor))
	  return newPath

	pendingPaths.add(newPath)

    return new Path()


  /**
   */

  private static class
  Path 
  extends ArrayDeque<Problem.State> 
  implements SolutionPath

    /**
     */

    Path
    addStep(Problem.State state)

      final Path newPath = new Path(this)

      newPath.addLast(state)

      return newPath


    /**
     */

    Problem.State
    lastState()
      return peekLast()


    /**
       Create a new state path.

       @param state The initial state in the path.

       @return A new path containing only the given state.
     */

    Path(Problem.State state)
      add(state)


    /**
       Create a new empty state path.

       @return A new path containing no states at all.
     */

    Path()


    /**
       Create a new state path.

       @param state The initial state in the path.

       @return A new path containing only the given state.
     */

    private 
    Path(Path path)
      addAll(path)


// $Log:$