import java.util.Collections; // 1.3+, TODO: implement sort differently to use in 1.1
import java.util.Vector;
import java.util.Iterator;

public class AStar {

  // the nodes define our nodes:
  // - what's walkable or not
  // - what's connected to what
  // doesn't assume a grid
  public Vector nodes;

  // open nodes are things we're still evaluating
  public Vector open = new Vector();
  // closed nodes have already been the lowest cost
  public Vector closed = new Vector();
 
  public AStar(Vector nodes) {
    this.nodes = nodes;
  }

  public Vector getNodes() {
    return nodes;
  }

  public Vector getPath(Node start, Node finish) {

    // reset f/g/h and parent for nodes
    for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
      Node n = (Node)iterator.next();
      n.reset();
    }  

    // clear Vectors
    open.clear();
    closed.clear();

    // add start node to open Vector
    open.add(start);

    // loop until no open nodes left
    while(open.size() > 0) {

      // nodes are comparable, using f values
      Collections.sort(open);

      // take the open node with lowest f
      Node current = (Node)open.remove(0);
      // move it to the closed Vector
      closed.add(current);

      // if we've found the end, quit!
      if (current == finish) {
        break;
      }

      // otherwise, loop through neighbours
      Iterator iter = current.neighbours.iterator();
      while(iter.hasNext()) {
        Node adjacent = (Node)iter.next();
        if (adjacent.walkable && !closed.contains(adjacent)) {
          if (!open.contains(adjacent)) {
            open.add(adjacent);
            adjacent.parent = current;
            adjacent.setF(finish);
          }
          else {
            // if this is a better way to get there than last time we looked at it
            if (adjacent.g > current.g + current.location.dist(adjacent.location)) {
              adjacent.parent = current;
              adjacent.setF(finish);
            }
          }
        }
      }
      
    }

    // trace parents to get path
    Vector path = new Vector();
    Node pathNode = finish;
    while (pathNode != null) {
      path.add(pathNode);
      pathNode = pathNode.parent;
    }

    return path;
  }

}