import { HashSet } from '../../containers/HashSet';
import { HashMap } from '../../containers/HashMap';
import { PriorityQueue } from '../../containers/PriorityQueue';

const enum Color {
    White = 0,
    Gray = 1,
    Black = 2
}

export type SearchResult<V> = HashMap<V, V>;

export abstract class Grid<V> extends HashSet<V> {
    constructor(hashfn: (key: V) => number, equalfn: (lhs: V, rhs: V) => boolean, vertices?: ArrayLike<V> | Iterable<V>) {
        super(hashfn, equalfn, vertices);
    }

    abstract neighbors(v: V, visitfn: (u: V, distance: number, grid: Grid<V>) => void): void;

    findPath(previous: SearchResult<V>, source: V, target: V) {
        const result: V[] = [];
        let current = target;
        for (; previous.has(current); current = previous.get(current)!)
            result.push(current);
        if (source === current)
            result.push(current);
        return result;
    }

    dijkstraSearch(source: V, visitfn?: (u: V, grid: Grid<V>) => boolean, thisArg?: any): SearchResult<V> {
        const previous = new HashMap<V, V>(this._hash, this._equal);
        const distance = new HashMap<V, number>(this._hash, this._equal, [[source, 0]]);
        const explored = new HashSet<V>(this._hash, this._equal);
        const queue = new PriorityQueue<[V, number]>([[source, 0]], (lhs, rhs) => lhs[1] - rhs[1]);

        while (!queue.isEmpty()) {
            const [u, uDist] = queue.pop()!;

            if (visitfn !== undefined
                && visitfn.call(thisArg, u, this))
                return previous;

            explored.add(u);
            this.neighbors(u, (v, d) => {
                if (explored.has(v))
                    return;
                const alt = uDist + d; // distance.get(u)! + d;
                const dst = distance.get(v);
                if (dst === undefined || alt < dst) {
                    distance.set(v, alt);
                    previous.set(v, u);
                    queue.push([v, alt]);
                }
            });
        }
        return previous;
    }

    breadthFirstSearch(source: V, visitfn?: (u: V, grid: Grid<V>) => boolean, thisArg?: any): SearchResult<V> {
        const previous = new HashMap<V, V>(this._hash, this._equal);
        const color = new HashMap<V, Color>(this._hash, this._equal, [[source, Color.Gray]]);
        const queue = [source];

        while (queue.length !== 0) {
            const u = queue.shift()!;

            if (visitfn !== undefined
                && visitfn.call(thisArg, u, this))
                return previous;

            this.neighbors(u, (v) => {
                const col = color.get(v);
                if (col === undefined || col === Color.White) {
                    previous.set(v, u);
                    color.set(v, Color.Gray);
                    queue.push(v);
                }
            });
            color.set(u, Color.Black);
        }
        return previous;
    }
}