var Heap       = require('../core/Heap');
var Util       = require('../core/Util');
var Heuristic  = require('../core/Heuristic');

/**
 * A* path-finder.
 * based upon https://github.com/bgrins/javascript-astar
 * @constructor
 * @param {object} opt 
 * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.
 * @param {function} opt.heuristic Heuristic function to estimate the distance
 *     (defaults to manhattan).
 */
function AStarFinder(opt) {
    opt = opt || {};
    this.allowDiagonal = opt.allowDiagonal;
    this.heuristic = opt.heuristic || Heuristic.manhattan;
}

/**
 * Find and return the the path.
 * @return {Array.<[number, number]>} The path, including both start and 
 *     end positions.
 */
AStarFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {
    var openList = new Heap(function(nodeA, nodeB) {
            return nodeA.f < nodeB.f;
        }),
        startNode = grid.getNodeAt(startX, startY),
        endNode = grid.getNodeAt(endX, endY),
        heuristic = this.heuristic,
        abs = Math.abs, SQRT2 = Math.SQRT2,
        allowDiagonal = this.allowDiagonal,
        node, neighbors, neighbor, i, l, x, y;

    // set the `g` and `f` value of the start node to be 0
    startNode.g = 0;
    startNode.f = 0;

    // push the start node into the open list
    openList.push(startNode);
    startNode.opened = true;

    // while the open list is not empty
    while (!openList.isEmpty()) {
        // pop the position of node which has the minimum `f` value.
        node = openList.pop();
        node.closed = true;

        // if reached the end position, construct the path and return it
        if (node === endNode) {
            return Util.backtrace(endNode);
        }

        // get neigbours of the current node
        neighbors = grid.getNeighbors(node, allowDiagonal);
        for (i = 0, l = neighbors.length; i < l; ++i) {
            neighbor = neighbors[i];

            if (neighbor.closed) {
                continue;
            }

            x = neighbor.x;
            y = neighbor.y;

            // get the distance between current node and the neighbor
            // and calculate the next g score
            dx = x - node.x;
            dy = y - node.y;
            ng = node.g + ((dx === 0 || dy === 0) ? 1 : SQRT2);

            // check if the neighbor has not been inspected yet, or
            // can be reached with smaller cost from the current node
            if (!neighbor.opened || ng < neighbor.g) {
                neighbor.g = ng;
                neighbor.h = neighbor.h || heuristic(abs(x - endX), abs(y - endY));
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = node;

                if (!neighbor.opened) {
                    openList.push(neighbor);
                    neighbor.opened = true;
                } else {
                    // the neighbor can be reached with smaller cost.
                    // Since its f value has been updated, we have to 
                    // update its position in the open list
                    openList.heapify();
                }
            }
        } // end for each neighbor
    } // end while not open list empty

    // fail to find the path
    return [];
};

module.exports = AStarFinder;

@@ -1056,85 +1056,85 @@
    a
-bs = Math.abs, SQRT2 = Math.SQRT2,%0A        allowDiagonal = this.allowDiagonal
+llowDiagonal = this.allowDiagonal,%0A        abs = Math.abs, SQRT2 = Math.SQRT2
 ,%0A  
@@ -2214,83 +2214,33 @@
     
-dx = x - node.x;%0A            dy = y - node.y;%0A            ng = node.g + ((d
+ng = node.g + ((x - node.
 x ==
@@ -2246,17 +2246,25 @@
 == 0 %7C%7C 
-d
+y - node.
 y === 0)
@@ -3072,16 +3072,27 @@
 ist.
-heapify(
+updateItem(neighbor
 );%0A 

optimize AStarFinder