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

// find first element not before value, using comparefn
export function lowerBound<T>(array: T[], value: T, comparefn: (lhs: T, rhs: T) => number = compare, first: number = 0, last: number = array.length) {
    let count = last - first;

    while (count > 0) { // divide and conquer, find half that contains answer
        const count2 = count / 2 | 0;
        let mid = first + count2;

        if (comparefn(array[mid], value) < 0) { // try top half
            first = ++mid;
            count -= count2 + 1;
        }
        else
            count = count2;
    }

    return first;
}

// find first element that value is before, using comparefn
export function upperBound<T>(array: T[], value: T, comparefn: (lhs: T, rhs: T) => number = compare, first: number = 0, last: number = array.length) {
    let count = last - first;

    while (count > 0) {	// divide and conquer, find half that contains answer
        const count2 = count / 2 | 0;
        let mid = first + count2;

        if (comparefn(value, array[mid]) >= 0) { // try top half
            first = ++mid;
            count -= count2 + 1;
        }
        else
            count = count2;
    }

    return first;
}

// test if value equivalent to some element, using comparefn
export function binarySearch<T>(array: T[], value: T, comparefn: (lhs: T, rhs: T) => number = compare, first: number = 0, last: number = array.length) {
    first = lowerBound(array, value, comparefn, first, last);
    return first != last && comparefn(value, array[first]) >= 0;
}

// find range equivalent to value, using comparefn
export function equalRange<T>(array: T[], value: T, comparefn: (lhs: T, rhs: T) => number = compare, first: number = 0, last: number = array.length): [number, number] {
    let count = last - first;

    while (0 < count) { // divide and conquer, check midpoint
        const count2 = count / 2 | 0;
        let mid = first + count2;

        if (comparefn(array[mid], value) < 0) { // range begins above mid, loop
            first = ++mid;
            count -= count2 + 1;
        }
        else if (comparefn(value, array[mid]) < 0)
            count = count2; // range in first half, loop
        else { // range straddles mid, find each end and return
            const first2 = lowerBound(array, value, comparefn, first, mid);
            first += count;
            const last2 = upperBound(array, value, comparefn, ++mid, first);
            return [first2, last2];
        }
    }

    return [first, first]; // empty range
}