123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
export interface PriorityQueue<T = any> {    at(index: number): T | undefined;    isEmpty(): boolean;
    clear: () => void;
    length: () => number;
    comparator: (a: T, b: T) => number;
    offer: (value: T) => void;
    head: () => T | undefined;
    tail: () => T | undefined;
    pop: () => T | undefined;
    shift: () => T | undefined;    toArray(): T[];}
export function PriorityQueue<T = any>(    comparator: (a: T, b: T) => number,    values?: T[],): PriorityQueue<T> {    if (typeof comparator !== "function") {        throw Error("expect comparator to be function");    }    const data: T[] = [];    if (values?.length) {        values.forEach((value) => data.push(value));        data.sort(comparator);    }    function length(): number {        return data.length;    }    function swap(i1: number, i2: number) {        [data[i1], data[i2]] = [data[i2], data[i1]];    }    function bubble_head_to_tail() {        if (data.length < 2) {            return;        }        for (let i = 0, j = 1; j < data.length && i < data.length; i++, j++) {            if (comparator(data[i], data[j]) > 0) {                swap(i, j);            } else {                break;            }        }    }    function bubble_tail_to_head() {        if (data.length < 2) {            return;        }
        for (            let i = data.length - 2, j = data.length - 1;            j >= 0 && i >= 0;            i--, j--        ) {            if (comparator(data[i], data[j]) > 0) {                swap(i, j);            } else {                break;            }        }    }
    function offer(value: T) {        const f = head();        if (typeof f === "undefined") {            data.push(value);            return;        }        const l = tail();        if (typeof l === "undefined") {            data.push(value);            return;        }        if (comparator(value, l) > 0) {            data.push(value);        } else if (comparator(value, f) < 0) {            data.unshift(value);        } else {            if (comparator(value, data[Math.floor(data.length / 2)]) > 0) {                data.push(value);                bubble_tail_to_head();            } else {                data.unshift(value);                bubble_head_to_tail();            }        }    }    function head() {        if (!data.length) {            return undefined;        }        return data[0];    }    function tail() {        if (!data.length) {            return undefined;        }        return data[data.length - 1];    }    function pop() {        return data.pop();    }    function shift() {        return data.shift();    }    function clear() {        data.length = 0;    }    function at(index: number): T | undefined {        return data.at(index);    }    function toArray() {        return Array.from(data);    }    function isEmpty() {        return data.length === 0;    }    return {        isEmpty,        toArray,        clear,        length,        comparator,        offer,        head,        tail,        pop,        shift,        at,    };}