// Node.java

public class Node
{
   private int PUZZLESIZE, dim;
   private String path = "";
   protected int[] state;
   protected int cost = 0;
   public Node next = null, parent, child, right, left;
   public int degree, level;
   public boolean mark;

   public Node(int _PUZZLESIZE, int _state[])
   {
      PUZZLESIZE = _PUZZLESIZE;
      state = new int[PUZZLESIZE];
      for(int i = 0; i < PUZZLESIZE; i++)
         state[i] = _state[i];
      dim = (int)Math.sqrt(PUZZLESIZE);
      right = this;
      left = this;
   }

   public String displayCost()
   {
      return Integer.toString(cost);
   }

   public void setCost(int _cost)
   {
      cost = _cost;
   }

   public int getCost()
   {
      return cost;
   }

   public int[] getState()
   {
      return state;
   }

   public String getPath()
   {
      return path;
   }

   private int getXPos(int tileNum, int board[])
   {
      int pos = 0;
      for(int y = 0; y < dim; y++)
        for(int x = 0; x < dim; x++)
        {
           if (board[pos] == tileNum)
             return x;
           pos++;
        }
      return -1;
   }

   private int getYPos(int tileNum, int board[])
   {
      int pos = 0;
      for(int y = 0; y < dim; y++)
        for(int x = 0; x < dim; x++)
        {
           if (board[pos] == tileNum)
             return y;
           pos++;
        }
      return -1;
   }

   public int f()
   {
      return g() + h();
   }

   private int g()
   {
      return path.length();
   }

   private int h()
   {
      // Implements the Manhattan Distance fitness function
      int distance = 0;
      for(int pos = 0; pos < PUZZLESIZE; pos++)
        if ((PuzzleApp.goalState[pos] != 0) && 
            (state[pos] != PuzzleApp.goalState[pos]))
          distance += (Math.abs(getXPos(PuzzleApp.goalState[pos], state) - 
                                getXPos(PuzzleApp.goalState[pos],
                                        PuzzleApp.goalState)) +
                       Math.abs(getYPos(PuzzleApp.goalState[pos], state) - 
                                getYPos(PuzzleApp.goalState[pos],
                                        PuzzleApp.goalState)));
      return distance;                     
   }

   public Node copyOfNode()
   {
      Node n = new Node(PUZZLESIZE, this.state);
      n.cost = this.cost;
      n.path = this.path;
      return n;
   }

   public boolean isGoalState()
   {
      for(int i = 0; i < PUZZLESIZE; i++)
        if (state[i] != PuzzleApp.goalState[i])
          return false;
      return true;
   }

   public int compareTo(int[] state)
   {
      for(int i = 0; i < PUZZLESIZE; i++)
         if (this.state[i] > state[i])
            return 1;
         else if (this.state[i] < state[i])
            return -1;
      return 0;
   }

   public Node moveLeft()
   {
      int pos = Utility.posOfElement(0, state, PUZZLESIZE);
      if (pos % dim == 0)
         return null;
      else
      {
         Node copy = copyOfNode();
         Utility.swap(pos, pos - 1, copy.state);
         copy.path += "L";
         copy.setCost(copy.f());
         return copy;
      }
   }

   public Node moveRight()
   {
      int pos = Utility.posOfElement(0, state, PUZZLESIZE);
      if ((pos + 1) % dim == 0)
         return null;
      else
      {
         Node copy = copyOfNode();
         Utility.swap(pos, pos + 1, copy.state);
         copy.path += "R";
         copy.setCost(copy.f());
         return copy;
      }
   }

   public Node moveUp()
   {
      int pos = Utility.posOfElement(0, state, PUZZLESIZE);
      if (pos < dim)
         return null;
      else
      {
         Node copy = copyOfNode();
         Utility.swap(pos, pos - dim, copy.state);
         copy.path += "U";
         copy.setCost(copy.f());
         return copy;
      }
   }

   public Node moveDown()
   {
      int pos = Utility.posOfElement(0, state, PUZZLESIZE);
      if (pos >= PUZZLESIZE - dim)
         return null;
      else
      {
         Node copy = copyOfNode();
         Utility.swap(pos, pos + dim, copy.state);
         copy.path += "D";
         copy.setCost(copy.f());
         return copy;
      }
   }

}