import java.util.*;
import java.util.List;

/**
  The AStarNode class, along with the AStarSearch class,
  implements a generic A* search algorithm. The AStarNode
  class should be subclassed to provide searching capability.
*/

/*
 * Deze code komt van http://www.peachpit.com/articles/article.asp?p=101142&seqNum=2&rl=1 en hebben we
 * teogespitst op ons probleem door een aantal componenten te veranderen of helemaal te schrijven.
 */
	
public  class AStarNode extends Vector implements Comparable  {
int x,y;
int[][] maze;
AStarNode pathParent, goalNode;	
float costFromStart;
float estimatedCostToGoal;	
/*
 * Deze twee constructors bevatten alle informatie die het algoritme nodig heeft om een pad te creeeren.
 * Ze bestaan uit een x- en y-coordinaat die de plaats in het doolhof aangeven; het doolhof zelf; de koste vanaf de start;
 * de geschatte afstand naar het doel; de node waar de node van afstamt en de goalNode.
 *
 * Het zijn twee constructors omdat verderop in het programma er informatie gevonden moet worden die de uiteindelijke nieuwe node
 * nodig heeft.  
 */
  AStarNode(int x, int y, int[][] maze) {
  	this.x=x;
  	this.y=y;
  	this.maze=maze;
  		}
		
  AStarNode(int x, int y, int[][] maze, float costFromStart, float estimatedCostToGoal, AStarNode pathParent, AStarNode goalNode) {
	this.x = x;
	this.y = y;
	this.maze = maze;
	this.costFromStart = costFromStart;
	this.estimatedCostToGoal = estimatedCostToGoal;
	this.pathParent = pathParent;
	this.goalNode = goalNode;	
	}
	
public String toString() {
	String s = new String(x + " " + y);
	//System.out.println(x + " " + y);
	//for(int i = 0; i <maze.length; i++){
	//	for(int j = 0; j < maze[i].length;j++){
//			System.out.print(maze[i][j]);
		//}
		//System.out.println("");
	//}
	return s;
}


    public float getCost() {
    return costFromStart + estimatedCostToGoal;
  }


  public int compareTo(Object other) {
    float thisValue = this.getCost();
    float otherValue = ((AStarNode)other).getCost();

    float v = thisValue - otherValue;
    return (v>0)?1:(v<0)?-1:0; // sign function
  }


  /**
    Gets the cost between this node and the specified
    adjacent (AKA "neighbor" or "child") node.
  */

   /*
    * Deze functie haalt de kosten uit de node
    * Node bestaat uit een x-coordinaat een y-coordinaat en een waarde 
    * welke gespecificeerd is in een array.
    * 
    * We hebben het doolhof beschreven als een matrix met op alle coordinaten
    * de bijbehorende kosten van de stap die de robot zou moeten maken om
    * naar die node te komen.  		 
    */ 	

  public float getCost(AStarNode node){
	int xbegin, ybegin;
	int x = node.x;
	int y = node.y;
	xbegin = this.x;
	ybegin = this.y;
	int[][] maze = node.maze;

	float cost2 = (float) maze[xbegin][ybegin];
	float cost1 = (float) maze[x][y];
	float cost = (cost1 + cost2) / 2;
	//System.out.println("Cost:" +cost);
	return cost;
	}

  /**
    Gets the estimated cost between this node and the
    specified node. The estimated cost should never exceed
    the true cost. The better the estimate, the more
    effecient the search.
  */

   /*
    * Hier voor gebruiken we de Manhattan distance tussen het begin
    * en eindpunt van het doolhof.
    */			
  public float getEstimatedCost(AStarNode goalNode){
	int xbegin, ybegin, xeind, yeind;
	float manDistance;
	xbegin = this.x;
	ybegin = this.y;	
	xeind = goalNode.x;
	yeind = goalNode.y;
	float som1 = Math.abs(xeind - xbegin);
	float som2 = Math.abs(yeind - ybegin);	

	manDistance = (float) som1 + som2;	
	return manDistance;
	}


  /**
    Gets the children (AKA "neighbors" or "adjacent nodes")
    of this node.
  */

   /*
    * Deze functie bekijkt welke kanten de robot op kan vanuit een
    * bepaalde node en genereert deze
    */				
  public List getNeighbors(){
	int x = this.x;
	int y = this.y;
	int[][] maze = this.maze;
	float costFromStart = this.costFromStart;
	float estimatedCostToGoal = this.estimatedCostToGoal;
	AStarNode pathParent = this.pathParent;
	AStarNode goalNode = this.goalNode;
	
	Vector neighbours = new Vector();
	
	AStarNode expandNode = new AStarNode(x,y,maze,costFromStart, estimatedCostToGoal, pathParent, goalNode);

	if(!(expandLeftPos(expandNode) == null))
	neighbours.add(expandLeftPos(expandNode));
	if(!(expandRightPos(expandNode) == null))
	neighbours.add(expandRightPos(expandNode));
	if(!(expandUpPos(expandNode) == null))
	neighbours.add(expandUpPos(expandNode));
	if(!(expandDownPos(expandNode) == null))
	neighbours.add(expandDownPos(expandNode));

	return neighbours;
	}    


  static AStarNode expandLeftPos(AStarNode oldPos){
    int newx, newy;
	int[][] maze = oldPos.maze;
	float cost, estimate;
	newx = oldPos.x - 1;
	newy = oldPos.y;	

	/*
	 * Hier wordt eerst gekeken of de array van het doolhof binnen de bounds blijft, en daarnaast
	 * of de nieuwe node niet in een muur zit. Een muur is gerepresenteerd door een 0.
	 * 
	 * Er wordt een tempNode aangemaakt om de estimate en de cost te berekenen en deze worden
	 * daarna aan de uiteindelijke node toegevoegd, deze node wordt terug gegeven.	
	 */

	if(!(newx < 0) && !(maze[newx][newy] == 0)){
	AStarNode tempPos = new AStarNode(newx, newy, maze);
	cost = oldPos.getCost(tempPos) + oldPos.costFromStart;
	estimate = oldPos.goalNode.getEstimatedCost(tempPos);
	AStarNode pos = new AStarNode(newx, newy, maze, cost, estimate, oldPos, oldPos.goalNode);
		return pos;
		}
	else
        return null;
        
    }

  static AStarNode expandRightPos(AStarNode oldPos){
    int newx, newy;
	int[][] maze = oldPos.maze;
	float cost, estimate;
	newx = oldPos.x + 1;
	newy = oldPos.y;	

	if(!(newx > maze.length) && !(maze[newx][newy] == 0 )){
	AStarNode tempPos = new AStarNode(newx, newy, maze);
	cost = oldPos.getCost(tempPos) + oldPos.costFromStart;
	estimate = oldPos.goalNode.getEstimatedCost(tempPos);
	AStarNode pos = new AStarNode(newx, newy, maze, cost, estimate, oldPos, oldPos.goalNode);	
		return pos;
		}
	else
        return null;
        
    }

  static AStarNode expandUpPos(AStarNode oldPos){
    int newx, newy;
	int[][] maze = oldPos.maze;
	float cost, estimate;
	newx = oldPos.x;
	newy = oldPos.y + 1;	

	if(!(newy > maze[1].length) && !(maze[newx][newy] == 0 )){
	AStarNode tempPos = new AStarNode(newx, newy, maze);
	cost = oldPos.getCost(tempPos) + oldPos.costFromStart;
	estimate = oldPos.goalNode.getEstimatedCost(tempPos);
	AStarNode pos = new AStarNode(newx, newy, maze, cost, estimate, oldPos, oldPos.goalNode);
		return pos;
		}
	else
        return null;
        
    }

  static AStarNode expandDownPos(AStarNode oldPos){
    int newx, newy;
	int[][] maze = oldPos.maze;
	float cost, estimate;
	newx = oldPos.x;
	newy = oldPos.y - 1;	

	if(!(newy < 0) && !(maze[newx][newy] == 0 )){
	AStarNode tempPos = new AStarNode(newx, newy, maze);
	cost = oldPos.getCost(tempPos) + oldPos.costFromStart;
	estimate = oldPos.goalNode.getEstimatedCost(tempPos);
	AStarNode pos = new AStarNode(newx, newy, maze, cost, estimate, oldPos, oldPos.goalNode);
		return pos;
		}
	else
        return null;
	}
	
 
}