'use strict';

Object.defineProperty(exports, '__esModule', { value: true });

var queue = require('@algorithm.ts/queue');

const BIGINT_ZERO = BigInt(0);
BigInt(1);

class BellmanFord {
    ZERO;
    INF;
    dist;
    bestFrom;
    inq;
    inqTimes;
    Q;
    constructor(props) {
        this.ZERO = props.ZERO;
        this.INF = props.INF;
        this.bestFrom = [];
        this.dist = [];
        this.inq = [];
        this.inqTimes = [];
        this.Q = new queue.CircularQueue({ capacity: 1 });
    }
    bellmanFord(graph, options = {}) {
        const { N, source, edges, G } = graph;
        const { ZERO, Q, bestFrom, dist, inq, inqTimes } = this;
        const { INF = this.INF } = options;
        bestFrom.length = N;
        dist.length = N;
        inq.length = N;
        inqTimes.length = N;
        bestFrom.fill(-1, 0, N);
        dist.fill(INF, 0, N);
        inq.fill(false, 0, N);
        inqTimes.fill(0, 0, N);
        dist[source] = ZERO;
        Q.init();
        Q.resize(N + 1);
        Q.enqueue(source);
        let to;
        let candidate;
        let edge;
        for (const o of Q.consuming()) {
            inq[o] = false;
            for (let i = 0, g = G[o], _size = g.length; i < _size; ++i) {
                edge = edges[g[i]];
                to = edge.to;
                candidate = (dist[o] + edge.cost);
                if (dist[to] > candidate) {
                    dist[to] = candidate;
                    bestFrom[to] = o;
                    if (!inq[to]) {
                        Q.enqueue(to);
                        inq[to] = true;
                        if (++inqTimes[to] > N)
                            return { hasNegativeCycle: true };
                    }
                }
            }
        }
        return { hasNegativeCycle: false, INF, source, bestFrom, dist };
    }
}

let _bellmanFord = null;
const bellmanFord = (graph, options = {}) => {
    if (_bellmanFord === null) {
        _bellmanFord = new BellmanFord({
            ZERO: 0,
            INF: Math.floor(Number.MAX_SAFE_INTEGER / 2) - 1,
        });
    }
    return _bellmanFord.bellmanFord(graph, options);
};
let _bellmanFordBigint = null;
const bellmanFordBigint = (graph, options = {}) => {
    if (_bellmanFordBigint === null) {
        _bellmanFordBigint = new BellmanFord({
            ZERO: BIGINT_ZERO,
            INF: BigInt(Number.MAX_SAFE_INTEGER),
        });
    }
    return _bellmanFordBigint.bellmanFord(graph, options);
};

exports.BellmanFord = BellmanFord;
exports.bellmanFord = bellmanFord;
exports.bellmanFordBigint = bellmanFordBigint;
exports.default = bellmanFord;