/*
	Search.java - abstract class specialising to Map_Search etc
*/

import java.util.*;
import Search_Node;
import Search_State;
import sheffield.*;

public abstract class Search {

  protected Search_Node init_node; //initial node
  protected Search_Node current_node; // current node
  protected Search_Node old_node; //node found on open with same state as new one
  protected ArrayList open;  //open - list of Search_Nodes
  protected ArrayList closed; //closed - .......
  
  protected EasyWriter scr;

  protected ArrayList successor_nodes; //used in expand & vet_successors

      	
  /** 
  * run a search 
  * @param init_state initial state
  * @param strat - String specifying strategy
  * @return indication of success or failure
  */
	
  public  String run_Search (Search_State init_state, String strat) {

    init_node= new Search_Node(init_state,0); // create initial node
    init_node.setglobalCost(0); //change from search2
    
    scr=new EasyWriter();
	
	//change from search1 - print strategy
	scr.println("Starting "+strat+" Search");
	
	open=new ArrayList(); // initial open, closed
	open.add(init_node);
	closed=new ArrayList();
	
	int cnum = 1;
	
	while (!open.isEmpty()) {
		    
	    // print contents of open
	    scr.println("-------------------------");
	    scr.println("iteration no "+cnum);
	    scr.println("open is");
	    for (Iterator it = open.iterator();it.hasNext(); ){
		
		Search_Node nn = (Search_Node) it.next();
		
		String nodestr=nn.toString();
		
		scr.println(nodestr);
	    }
	    
	    select_Node(strat); // change from search1 -select_Node selects next node given strategy, 
	    // makes it current_node & removes it from open
	    scr.println("Current node: "+current_node.toString());
	    
	    if (current_node.goalP(this)) return report_Success();  //success
	    //change from search1 - call Report_Success 
	                                              
	    expand(); // go again
	    closed.add(current_node); // put current node on closed
	    cnum=cnum+1;
	};

	return "Search Fails";  // out of the while loop - failure

	}
	
    // expand current node
			
    private void expand () {
	// get all successor nodes - as ArrayList of Objects
	
	successor_nodes = current_node.get_Successors(this); //pass search instance
	// change from search2
    // set global costs and parents for successors
    for (Iterator i = successor_nodes.iterator(); i.hasNext();){
              Search_Node snode = (Search_Node) i.next();
              snode.setglobalCost(current_node.getglobalCost()+ snode.getlocalCost());
              snode.set_Parent(current_node);
    }
              
	vet_Successors(); //filter out unwanted - DP check

	//add surviving nodes to open   
	    for (Iterator i = successor_nodes.iterator(); i.hasNext();){
	          open.add(i.next());	
	    }
    }

  // vet the successors - reject any whose states are on open or closed
  // change from search2 to do DP check	

	private void vet_Successors() {
	    ArrayList vslis = new ArrayList();
	    
	    for (Iterator i = successor_nodes.iterator(); i.hasNext();){
          Search_Node snode = (Search_Node) i.next();
          if (!(on_Closed(snode))) {  //if on closed, ignore
            if (!(on_Open(snode))) {
              vslis.add(snode);  //if not on open, add it
            }
            else {  //DPcheck - node found on open is in old_node
              if (snode.getglobalCost()<=old_node.getglobalCost()){ //compare global costs
                old_node.set_Parent(snode.get_Parent()); //better route, modify node
                old_node.setglobalCost(snode.getglobalCost());
              };
            };
          };
        };
        
        successor_nodes=vslis;
    }    
           

    //on_Closed - is the state for a node the same as one on closed?

    private boolean on_Closed(Search_Node new_node){
	boolean ans = false;
	for (Iterator ic = closed.iterator(); ic.hasNext();){ 
	    Search_Node closed_node = (Search_Node) ic.next();
	    if (new_node.same_State(closed_node)) ans=true;
	}
	return ans;
    }
  //on_Open - is the state for a node the same as one on open?
  // if node found, remember it in old_node

  private boolean on_Open(Search_Node new_node){
	boolean ans = false;
    Iterator ic = open.iterator();
    while ((ic.hasNext())&& !ans){ //there can only be one node on open with same state
      Search_Node open_node = (Search_Node) ic.next();
      if (new_node.same_State(open_node)) {
        ans=true;
        old_node=open_node;
      }
    }
	return ans;
  }  
	
             
    // select the next node - depth-first for now - remove it from open
	
	//change from search1
	// call depth_first or breadth_first dependent on strat - clumsy!
	//default is breadth_first
	
  
    private void select_Node(String strat) {
	if (strat== "depth_first") 
      depth_first();
    else 
      if(strat=="breadth_first") 
        breadth_first();
      else 
        branch_and_bound();
    }
  	
    private void depth_first () {
    	int osize=open.size();
		current_node= (Search_Node) open.get(osize-1); // last node added to open
		open.remove(osize-1); //remove it
	}
	
	private void breadth_first(){
		current_node= (Search_Node) open.get(0); //first node on open
		open.remove(0);
	}

    //change from search2
    private void branch_and_bound(){
      
      Iterator i = open.iterator();
      Search_Node min_cost_node=(Search_Node) i.next();
      for (;i.hasNext();){
        Search_Node n=(Search_Node) i.next();
        if (n.getglobalCost()<min_cost_node.getglobalCost()){
          min_cost_node=n;};
      };
      
      current_node=min_cost_node;
      open.remove(min_cost_node); 
    }
      
	
		//change from search1
	
	// report success - reconstruct path, convert to string & return
		
    private String report_Success(){

	Search_Node n = current_node;
	StringBuffer buf = new StringBuffer(n.toString());
	int plen=1;
	
	while (n.get_Parent() != null){
	    buf.insert(0,"\n");
	    n=n.get_Parent();
	    buf.insert(0,n.toString());
	    plen=plen+1;	    
		}
	
	scr.println("=========================== \n");
	scr.println("Search Succeeds");

	scr.println("Efficiency "+ ((float) plen/(closed.size()+1)));
	scr.println("Solution Path\n");
	return buf.toString();
    }    
}