From CSULA CS Wiki
< Courses‎ | CS 460‎ | Fall 2006‎ | Search
Jump to: navigation, search
m
m
Line 1: Line 1:
 
<java>
 
<java>
 +
<pre>
 
package searchExample;
 
package searchExample;
  
Line 99: Line 100:
  
 
}  
 
}  
 +
</pre>
 
</java>
 
</java>

Revision as of 15:36, 24 October 2006

<java>

package searchExample;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.TreeSet;

public class Searcher {

  public ExtendableState search(SearchType searchType, 
                                ExtendableState startState, 
                                ExtendableState goalState, 
                                boolean verbose) {
    if (startState.equals(goalState)) return startState;

    // These are the states currently on the "frontier," i.e., the current leaves 
    // of the current tree. We have to examine their successors (children) if any.
    AbstractList<ExtendableState> frontier = new ArrayList<ExtendableState>();
    frontier.add(startState);

    // These are the states which have ever been on the frontier, i.e., the current
    // leaves plus all current interior nodes of the current tree.
    // Since we have seen them once, don't want to look at them again.
    TreeSet<ExtendableState> seenStates = new TreeSet<ExtendableState>();
    seenStates.add(startState);

    if (verbose) {
      System.out.println("Start state: " + startState);
      System.out.println("Using " + searchType + " search.");
      System.out.println("Frontier lists");
    }

    while (!frontier.isEmpty()) {
      if (verbose) System.out.println(frontier);
      ExtendableState currentState = frontier.get(0);
      // This is a successor of CurrentState. Add it to the frontier.
      ExtendableState nextState = currentState.next();
      if (verbose) System.out.println("  " + currentState + " --> " + nextState + ".");
      if (nextState.equals(goalState)) {
        if (verbose) System.out.println("\tReached goal.");
        return nextState;
      }
      if (!currentState.hasNext()) {
        // We have seen all the successors of currentState.
        // Remove it from the frontier.
        frontier.remove(0);
        if (verbose) {
          System.out.println("\tNo more children of " + currentState +
          ". Removing it from the frontier list.");
          //System.out.println(frontier);
        }
      }
      if (seenStates.contains(nextState)) {
        if (verbose) System.out.println("\tHave already seen " + nextState + 
        ". Ignoring it.");
      } else {
        seenStates.add(nextState);

        // Let the searchType determime where to add nextState in the frontier list.
        searchType.addState(frontier, nextState, verbose);
      }
    }

    // No more frontier states, and we didn't reach the goal.
    return null;
  }

  public int printPathTo(ExtendableState state) {
    ExtendableState predecessor = state.getPredecessor();
    // If this is the first state (on first line). 
    //   Print the state but don't terminate line.
    //   Return the length of the first state as an indent for subsequent lines.
    if (predecessor == null) {
      System.out.println("Path from start state to goal.");
      String stateString = state.toString();
      System.out.print(stateString);
      return stateString.length();
    }
    // If this is not the first state, print the first (and other previous) states.
    // Capture the indent length.
    int indent = printPathTo(predecessor);
    // If this is not the second state (on the first line) we are printing an entirely
    // new line. 
    //  Print indent number of spaces. 
    // On the other hand, if this is the second state (which is on the first line), 
    // don't print the extra spaces.
    if (predecessor.getPredecessor() != null) System.out.print(spaces(indent));
    // In either case, print " --> ", the state, and "\n". 
    // Return the indent for subsequent lines.
    System.out.println(" --> " + state.toString());
    return indent;
  }

  private String spaces(int indent) {
    StringBuffer spaces = new StringBuffer();
    for (int i = 0; i < indent; i++) spaces.append(' ');
    return spaces.toString();
  }

} 

</java>