import { compare } from '../functional/compare';

function isHeapUntilHelper<T>(array: T[], first: number, len: number, comparefn: (lhs: T, rhs: T) => number) {
    let parent = 0;
    for (let child = 1; child < len; ++child) {
        if (comparefn(array[first + parent], array[first + child]) > 0)
            return child;
        if ((child & 1) === 0)
            ++parent;
    }
    return len;
}

function pushHeapHelper<T>(array: T[], first: number, holeIndex: number, topIndex: number, value: T, comparefn: (lhs: T, rhs: T) => number) {
    let parent = (holeIndex - 1) / 2 | 0;
    while (holeIndex > topIndex && comparefn(array[first + parent], value) > 0) {
        array[first + holeIndex] = array[first + parent];
        holeIndex = parent;
        parent = (holeIndex - 1) / 2 | 0;
    }
    array[first + holeIndex] = value;
}

function adjustHeap<T>(array: T[], first: number, holeIndex: number, len: number, value: T, comparefn: (lhs: T, rhs: T) => number) {
    const top = holeIndex;
    let second = holeIndex;
    while (second < ((len - 1) / 2 | 0)) {
        second = 2 * (second + 1);
        if (comparefn(array[first + second], array[first + (second - 1)]) > 0)
            second--;
        array[first + holeIndex] = array[first + second];
        holeIndex = second;
    }
    if ((len & 1) === 0 && second === ((len - 2) / 2 | 0)) {
        second = 2 * (second + 1);
        array[first + holeIndex] = array[first + (second - 1)];
        holeIndex = second - 1;
    }
    pushHeapHelper(array, first, holeIndex, top, value, comparefn);
}

function popHeapHelper<T>(array: T[], first: number, last: number, result: number, comparefn: (lhs: T, rhs: T) => number) {
    const value = array[result];
    array[result] = array[first];
    adjustHeap(array, first, 0, last - first, value, comparefn);
}

export function isHeapUntil<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length): number {
    return first + isHeapUntilHelper(array, first, last - first, comparefn);
}

export function isHeap<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length): boolean {
    return isHeapUntil(array, comparefn, first, last) === last;
}

export function makeHeap<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length) {
    const len = last - first;
    if (len < 2)
        return;
    let parent = (len - 2) / 2 | 0;
    while (true) {
        const value = array[first + parent];
        adjustHeap(array, first, parent, len, value, comparefn);
        if (parent === 0)
            return;
        parent--;
    }
}

export function pushHeap<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length) {
    const value = array[last - 1];
    pushHeapHelper(array, first, (last - first) - 1,  0, value, comparefn);
}

export function popHeap<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length) {
    if (last - first > 1) {
        --last;
        popHeapHelper(array, first, last, last, comparefn);
    }
}

export function replaceHeap<T>(array: T[], index: number, value: T, comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length) {
    if (index < (last - first) && comparefn(array[first + index], value) > 0)
        pushHeapHelper(array, first, first + index, 0, value, comparefn);
}

export function sortHeap<T>(array: T[], comparefn: (lhs: T, rhs: T) => number = compare, first = 0, last = array.length) {
    while (last - first > 1) {
        --last;
        popHeapHelper(array, first, last, last, comparefn);
    }
}