package Search;

import java.io.*;
import java.util.*;

public class USearcher {

  public USearcher(SearchState initState) {
    open = new SearchNode(initState);
    initNode = open;
    lastOpen = open;
    nrOfNodes = 1;
  }

  public boolean search() {
    while ((open != null) && (nrOfNodes <= searchLimit)) {
      SearchNode currentNode = moveFirst();
      printTrace("Current state:\n" + currentNode.state.toString());

      // test whether this is a goal state:
      if (currentNode.state.isGoalState()) {
	goalNode = currentNode;
	return true;
      }

      // add the successor nodes to open:
      Vector succs = currentNode.state.getSuccessors();
      printTrace("Successor states:\n");
      for (Enumeration se=succs.elements(); se.hasMoreElements(); )
	addOpenNode((SearchState)se.nextElement(), currentNode);
    }
    return false;
  }

  private SearchNode moveFirst() {
    SearchNode currentNode = open;
    // take current node out of open:
    open = currentNode.rest;
    if (open == null)
      lastOpen = null;
    // append current node to closed:
    if (closed == null)
      closed = currentNode;
    else 
      lastClosed.rest = currentNode;
    lastClosed = currentNode;
    // return the current node:
    return currentNode;
  }

  private void printTrace(String str) {
    if (traceStream == null)
      return;
    try {
      traceStream.write(str.getBytes());
      traceStream.write((int)'\n');
    } catch (IOException ioe) {
      System.out.println("Problem: Failed to write to trace stream!");
    }
  }

  private void addOpenNode(SearchState newState, SearchNode parentNode) {
    if ((rptTestLev > 0) && (rptNode(newState, parentNode)))
      return;
    nrOfNodes++;
    printTrace(newState.toString());
    SearchNode newNode = new SearchNode(newState);
    parentNode.children.addElement(newNode);
    newNode.parent = parentNode;
    if (searchDF) {
      if (open == null)
	lastOpen = newNode;
      else
	newNode.rest = open;
      open = newNode;
    }
    else {
      if (open == null)
	open = newNode;
      else 
	lastOpen.rest = newNode;
      lastOpen = newNode;
    }
  }

  private boolean rptNode(SearchState newState, SearchNode parentNode) {
    // level 1: test all parent nodes:
    for (SearchNode cn=parentNode; (cn != null); cn=cn.parent )
      if (newState.equals(cn.state))
	return true;
    if (rptTestLev == 1)
      return false;

    // level 2: test all closed nodes:
    for (SearchNode cn=closed; (cn != null); cn=cn.rest )
      if (newState.equals(cn.state))
	return true;
    if (rptTestLev == 2)
      return false;
    
    // level 3: also test all open nodes:
    for (SearchNode cn=open; (cn != null); cn=cn.rest )
      if (newState.equals(cn.state))
	return true;
    
    return false;
  }

  public SearchState getSolutionState() {
    return goalNode.state;
  }

  public void setSearchLimit(int limit) {
    searchLimit = limit;
  }

  public void setTraceStream(OutputStream ost) {
    traceStream = ost;
  }

  public void searchBreadthFirst() {
    searchDF = false;
  }

  public void searchDepthFirst() {
    searchDF = true;
  }

  public void setRepeatTestLevel(int n) {
    rptTestLev = n;
  }

  private SearchNode initNode = null;
  private SearchNode goalNode = null;
  private SearchNode open = null;
  private SearchNode lastOpen = null;
  private SearchNode closed = null;
  private SearchNode lastClosed = null;

  private boolean searchDF = false;
  private int nrOfNodes = 0;
  private int searchLimit = 1000;
  private int rptTestLev = 0;
  private OutputStream traceStream = null;
}

class SearchNode {
  SearchNode(SearchState f) {
    state = f; 
    rest = null;
    parent = null;
    children = new Vector();
  }
  SearchState state;
  SearchNode rest, parent;
  Vector children;
}
