import { manhattanDistance } from './other/helperFunctions';
import MapWithDefaultValue from './other/mapWithDefaultValue';

import { PriorityQueue } from 'libstl'; // note: imported from a node module

/** @module findPath */

/**
 * Heavily modified implementation of the A* algorithm
 * @param  {Object} start object containing numeric attributes `x` and `y` that represent the first endpoint of the wire in grid pixels
 * @param  {Object} end   object containing numeric attributes `x` and `y` that represent the second endpoint of the wire in grid pixels
 * @param  {Set} nonRoutable set of non routable nodes
 * @param  {Set} punishedButRoutable set of nodes that are not optimal for routing
 * @return {Array} array of objects containing numeric attributes `x` and `y`
 */
export default function findPath(start, end, nonRoutable, punishedButRoutable) {
    const distanceFunction = manhattanDistance;

    const wireCrossPunishment = 1;
    const wireBendPunishment = 1;

    // number of nodes, that can be opened at once
    // once is this limit exceeded, aStar will fail and return undefined
    const maxNodeLimit = 100000;

    let closedNodes = new Set();
    let openNodes = new Set();
    let openNodeQueue = new PriorityQueue();

    // functions for working with open nodes:

    /**
     * add a new open node to the structure
     * @param {Object} node   object containing numeric attributes `x` and `y` that represent the first endpoint of the wire
     * @param {number} fscore fScore of this node
     */
    const addOpenNode = (node, fscore) => {
        openNodes.add(node);
        // flip the fscore, because PriorityQueue uses max heap
        openNodeQueue.enqueue(node, 1 / fscore);
    };

    /**
     * get the open node with the lowest fScore and remove it
     * @return {Object} object containing numeric attributes `x` and `y` that represent the first endpoint of the wire
     */
    const getOpenNode = () => {
        const node = openNodeQueue.dequeue();
        openNodes.delete(node);
        return node;
    };

    let cameFrom = new Map();

    // default value: infinity
    let gScore = new MapWithDefaultValue(Infinity);
    gScore.set(start, 0);

    let startFScore = distanceFunction(start, end);

    addOpenNode(start, startFScore);

    openNodes.add(start);
    openNodeQueue.enqueue(start, 1 / startFScore);

    while (openNodes.size > 0) {
        // get the value from openNodes that has the lowest fScore
        const currentNode = getOpenNode();

        // if we reached the end point, reconstruct the path and return it
        if (currentNode.x == end.x && currentNode.y == end.y) {
            return reconstructPath(cameFrom, currentNode);
        }

        // add this node to the closed nodes
        closedNodes.add(currentNode);

        // the farthest points accessible without avoiding obstacles in every direction
        // (but max 50 in each direction)
        for (let direction = 0; direction < 4; direction++) {
            let newPoint = movePoint(currentNode, direction);

            let wiresCrossed = 0;

            for (let i = 0; i < 50; i++) {
                // if newPoint is in the set of non routable points,
                // don't add it and stop proceeding in this direction
                if (setHasThisPoint(nonRoutable, newPoint)) {
                    // if this not the end or start point, break
                    if (
                        !(newPoint.x === end.x && newPoint.y === end.y) &&
                        !(newPoint.x === start.x && newPoint.y === start.y)
                    ) {
                        break;
                    }
                }

                // skip this node, if it has been already closed
                // or if it is on the list of non routable nodes
                if (closedNodes.has(newPoint)) {
                    continue;
                }

                // calculate possible GScore by applying a punishment for each node ("bend") in the path
                let newGScore = wireBendPunishment + gScore.getWithDefault(currentNode);

                if (setHasThisPoint(punishedButRoutable, newPoint)) {
                    // if the node is in the set of punished nodes, apply the punishment
                    wiresCrossed++;
                }

                // apply the punishment for each wire crossed in this direction
                // note: we are counting the wires crossed when exporting this direction, not the wires
                // crossed in the final path, there will be probably only at most of these nodes in the
                // final path, not multiple
                newGScore += wiresCrossed * wireCrossPunishment;

                // skip this node if it has worst estimage gscore than in the gscore table
                if (newGScore >= gScore.getWithDefault(newPoint)) {
                    continue;
                }

                cameFrom.set(newPoint, currentNode);
                gScore.set(newPoint, newGScore);

                const newFScore = newGScore + distanceFunction(newPoint, end);

                if (!openNodes.has(newPoint)) {
                    // add the point to the list of points
                    addOpenNode(newPoint, newFScore);
                }

                // move to the next point in the direciton
                newPoint = movePoint(newPoint, direction);
            }
        }

        if (openNodes.size > maxNodeLimit) {
            console.log(
                `aStar: Number of open nodes (${
                    openNodes.size
                }) exceeded the limit for open nodes (${maxNodeLimit}).`
            );
            break;
        }
    }
    // if we got here, the path was not found

    return undefined;
}

/**
 * returns `true` if the specified set of points contains the specified point (and returns `false` otherwise)
 * @param {Set} set set of points
 * @param {Object} point object containing numeric attributes `x` and `y`
 */
function setHasThisPoint(set, point) {
    for (let item of set) {
        if (item.x === point.x && item.y === point.y) {
            return true;
        }
    }
    return false;
}

/**
 * Helper that moves the passed point in the specified direction. It simply adds or subtracts 1 from one of the coordinates depending on the direction attribute.
 * @param  {Object} point     object containing numeric attributes `x` and `y`
 * @param  {number} direction directions:
 *     - 0: up
 *     - 1: right
 *     - 2: down
 *     - 3: left
 * @return {Object}           object containing numeric attributes `x` and `y`
 */
function movePoint({ x, y }, direction) {
    // map direction do point coordinate modification
    const dirMap = {
        0: () => {
            y -= 1;
        },
        1: () => {
            x += 1;
        },
        2: () => {
            y += 1;
        },
        3: () => {
            x -= 1;
        }
    };

    dirMap[direction]();

    return { x, y };
}

/**
 * helper backtracking function used by the aStar algorithm to construct the final path
 * @param  {Object} cameFrom    object containing numeric attributes `x` and `y`
 * @param  {Object} currentNode object containing numeric attributes `x` and `y`
 * @return {Array} array of objects containing numeric attributes `x` and `y`
 */
function reconstructPath(cameFrom, currentNode) {
    let path = [];

    path.push({
        x: currentNode.x,
        y: currentNode.y
    });

    while (cameFrom.has(currentNode)) {
        currentNode = cameFrom.get(currentNode);
        path.push({
            x: currentNode.x,
            y: currentNode.y
        });
    }

    return path;
}
