import { CostOptions } from "./cost_options.js";
export interface AStarOptions<Node, Cost = number> {
    /**
     * The starting node.
     */
    start: Node;
    /**
     * Returns a list of successors for a given node, along with the cost for
     * moving from the node to the successor.
     */
    successors: (node: Node) => Iterable<[Node, Cost]>;
    /**
     * Returns an approximation of the cost from a given node to the goal.
     * The approximation must not be greater than the real cost, or a wrong shortest
     * path may be returned.
     */
    heuristic: (node: Node) => Cost;
    /**
     * Checks whether the goal has been reached. It is not a node as some
     * problems require a dynamic solution instead of a fixed node.
     */
    success: (node: Node) => boolean;
    /**
     * A function that returns a unique key for a node. Equal nodes must return keys
     * that are equal.
     * If the nodes are primitive values, are represented by persistent unique objects,
     * or are never encountered more than once, then the identity function (`x => x`)
     * can be used here.
     * Otherwise, a custom function that converts the node to a string is
     * recommended. (`JSON.stringify` can be used for this.)
     *
     * In the future, if the Javascript [Record and
     * Tuple](https://tc39.es/proposal-record-tuple/tutorial/) proposal is implemented,
     * then this option may be changed to be optional with a default value set to the identity function,
     * in order to make Record and Tuple nodes work as simply as possible.
     */
    key: (node: Node) => unknown;
    /**
     * This option lets custom functions for managing the Cost values be specified.
     * This is not necessary to use if the Cost type is a number.
     * This option is useful if you want a different type of Cost value, such as a tuple of numbers
     * representing separate resource costs where 1 of an earlier index is worth more than any amount in
     * further indexes.
     */
    costOptions?: CostOptions<Cost>;
    /**
     * Stop considering paths that have a cost greater than this value.
     */
    maxCost?: Cost;
}
/**
 * Compute a shortest path using the [A* search
 * algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm).
 *
 * Multiple equivalent nodes (determined by the {@link AStarOptions.key()} function) will never
 * be included twice in the path.
 *
 * The shortest path starting from {@link AStarOptions.start} up to a node for which {@link AStarOptions.success()} returns `true`
 * is computed and returned along with its total cost, or `undefined` is returned if no successful path
 * was found. The returned path comprises both the start and end node.
 *
 * # Example
 *
 * ```ts
 * import { assertEquals } from "https://deno.land/std@0.189.0/testing/asserts.ts";
 * import { aStar } from "https://deno.land/x/lazy_pathfinding/directed/a_star.ts";
 *
 * type Pos = [number, number];
 *
 * function distance(a: Pos, b: Pos): number {
 *   return Math.abs(a[0] - a[1]) + Math.abs(b[0] - b[1]);
 * }
 *
 * const goal: Pos = [4, 6];
 *
 * const result = aStar<Pos>({
 *   start: [1, 1],
 *   successors: ([x, y]) =>
 *     ([
 *       [x + 1, y + 2],
 *       [x + 1, y - 2],
 *       [x - 1, y + 2],
 *       [x - 1, y - 2],
 *       [x + 2, y + 1],
 *       [x + 2, y - 1],
 *       [x - 2, y + 1],
 *       [x - 2, y - 1],
 *     ] as Pos[])
 *       .map((p) => [p, 1]),
 *   heuristic: (node) => distance(node, goal) / 3,
 *   success: (node) => node[0] === goal[0] && node[1] === goal[1],
 *   key: (node) => node[0] + "," + node[1],
 * });
 *
 * assertEquals(result![1], 4);
 * ```
 */
export declare function aStar<Node, Cost = number>(options: AStarOptions<Node, Cost>): [Node[], Cost] | undefined;
/**
 * Compute all shortest paths using the [A* search
 * algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm). Whereas {@link aStar}
 * (non-deterministic-ally) returns a single shortest path, `aStarBag` returns all shortest paths
 * (in a non-deterministic order).
 *
 * Multiple equivalent nodes (determined by the {@link AStarOptions.key()} function) will never
 * be included twice in the path.
 *
 * The shortest paths starting from {@link AStarOptions.start} up to a node for which {@link AStarOptions.success()} returns `true`
 * are computed and returned in an iterable along with the cost (which, by definition, is the same for
 * each shortest path). If no paths are found, `undefined` is returned. Each path comprises both the start and an end node. Note that while every path shares the same
 * start node, different paths may have different end nodes.
 */
export declare function aStarBag<Node, Cost = number>(options: AStarOptions<Node, Cost>): [Iterable<Node[]>, Cost] | undefined;