package IDAStarSearch;

import java.util.*;
import IDAStarSearch.*;


public class StateNode{

   /*
      Goal will look like:
      0 1 2
      3 4 5
      6 7
   */

   private static Random _rndGen = new Random();

   int[] _squares;
   private int _freePos;

   private StateNode _parent;
   private Vector _kids = null;

   private StateNode( int[] squares, int freePos, StateNode parent ){
      _squares = squares;
      _freePos = freePos;
      _parent = parent;
   }

   public boolean isGoal(){
      if( _freePos != 8 ){
	 return false;
      }

      for( int i = 0 ; i < 8 ; i++ ){
	 if( _squares[i] != i ){
	    return false;
	 }
      }
      return true;
   }

   int costSoFar = -1;

   public int getCost(){
      if( costSoFar != -1 ){
	 return costSoFar;
      }

      int tXpos;
      int tYpos;
      int sXpos;
      int sYpos;

      int cost = 0;

      for(int i = 0 ; i < 9 ; i++ ){
	 if( _squares[i] == -1 ){
	    continue;
	 }
   
	 tXpos = getXcoord( i );
	 tYpos = getYcoord( i );

	 sXpos = getXcoord( _squares[i] );
	 sYpos = getYcoord( _squares[i] );

	 cost += (Math.abs( tXpos - sXpos ));
	 cost += (Math.abs( tYpos - sYpos ));
      }

      if( _parent == null ){
	 costSoFar = cost;
	 return cost;
      }else{
	 costSoFar = _parent.getCost() + cost;
	 return costSoFar;
      }

   }

   private int getPathCost(){
      if( _parent != null ){
	 return 1 + _parent.getPathCost();
      }else{
	 return 1;
      }
   }

   public int getXcoord(int a ){
      return (a % 3);
   }
   
   public int getYcoord(int a){
      return ( a / 3 );
   }

   public Vector getSuccessors(){
      if( _kids != null ){
	 return _kids;
      }

      Vector succ = new Vector();

      int top = _freePos - 3;
      int bottom = _freePos + 3;
      int left = _freePos - 1 ;
      int right = _freePos + 1;

      if( top >= 0 ){
	 int[] tSquares = new int[9];
	 System.arraycopy( _squares, 0, tSquares, 0, 9 );
	 tSquares[_freePos] = tSquares[top];
	 tSquares[top] = -1;
	 succ.add( new StateNode( tSquares, top , this) );
      }

      if( bottom <= 8 ){
	 int[] tSquares = new int[9];
	 System.arraycopy( _squares, 0, tSquares, 0, 9 );
	 tSquares[_freePos] = tSquares[bottom];
	 tSquares[bottom] = -1;
	 succ.add( new StateNode( tSquares, bottom , this) );
      }

      if( left % 3 != 2 && left > 0 ){
	 int[] tSquares = new int[9];
	 System.arraycopy( _squares, 0, tSquares, 0, 9 );
	 tSquares[_freePos] = tSquares[left];
	 tSquares[left] = -1;
	 succ.add( new StateNode( tSquares, left, this  ) );
      }

      if( right % 3 != 0 ){
	 int[] tSquares = new int[9];
	 System.arraycopy( _squares, 0, tSquares, 0, 9 );
	 tSquares[_freePos] = tSquares[right];
	 tSquares[right] = -1;
	 succ.add( new StateNode( tSquares, right, this ) );
      }

      _kids = succ;

      return succ;

   }

   public static StateNode getStartNode(){

      int[] squares = new int[9];

      for(int i = 0 ; i < 9 ; i++ ){
	 squares[i] = (_rndGen.nextInt(10)) * 10 + (i);
      }

      java.util.Arrays.sort( squares );

      int fp = -999;

      for(int i = 0 ; i < 9 ; i++ ){
	 if( squares[i] % 10 == 8 ){
	    squares[i] = -1;
	    fp = i;
	 }else{
	    squares[i] = squares[i] % 10;
	 }
      }

      return new StateNode( squares, fp, null );

   }

/*----------------------------------------------------------------------------*/
   public StateNode getParent(){
      return _parent;
   }

   public Vector getKids(){
      return _kids;
   }

   long _w; /* Holder for this nodes graphical 'width' */

   public void setWidth( long w ){
      _w = w;
   }

   public long getWidth(){
      return _w;
   }

}