import { assert } from 'chai';
import { lowerBound, upperBound, binarySearch, equalRange } from '../../../lib/algorithms/binarySearch';

const ascending = (a: number, b: number) => a - b;
const descending = (a: number, b: number) => b - a;

describe('algorithms.binarySearch', () => {
    describe('lowerBound', () => {
        test.each([
            //0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, 7, ascending, 0, 13],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, 7, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 2, 2, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, 12, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 7, 13, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 3, 3, ascending, 2, 10],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, 10, ascending, 2, 10],
            [[6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1], 4, 3, descending, undefined, undefined],
        ])('lowerBound#%#', (array: number[], value: number, result: number, comparefn: (a: number, b: number) => number, first: number, last: number) => {
            assert.strictEqual(lowerBound(array, value, comparefn, first, last), result);
        });
    });

    describe('upperBound', () => {
        test.each([
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, 10, ascending, 0, 13],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, 10, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 2, 3, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, 13, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 7, 13, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 3, 7, ascending, 2, 10],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, 10, ascending, 2, 10],
            [[6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1], 4, 6, descending, undefined, undefined],
        ])('upperBound#%#', (array: number[], value: number, result: number, comparefn: (a: number, b: number) => number, first: number, last: number) => {
            assert.strictEqual(upperBound(array, value, comparefn, first, last), result);
        });
    });

    describe('binarySearch', () => {
        test.each([
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, true, ascending, 0, 13],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, true, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 2, true, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, true, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 7, false, undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 3, true, ascending, 2, 10],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, false, ascending, 2, 10],
            [[6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1], 4, true, descending, undefined, undefined],
            [[6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1], 7, false, descending, undefined, undefined],
        ])('binarySearch#%#', (array: number[], value: number, result: boolean, comparefn: (a: number, b: number) => number, first: number, last: number) => {
            assert.strictEqual(binarySearch(array, value, comparefn, first, last), result);
        });
    });

    describe('equalRange', () => {
        test.each([
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, [7, 10], ascending, 0, 13],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 4, [7, 10], undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 2, [2, 3], undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, [12, 13], undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 7, [13, 13], undefined, undefined, undefined],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 3, [3, 7], ascending, 2, 10],
            [[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6], 6, [10, 10], ascending, 2, 10],
            [[6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1], 4, [3, 6], descending, undefined, undefined],
        ])('equalRange#%#', (array: number[], value: number, result: [number, number], comparefn: (a: number, b: number) => number, first: number, last: number) => {
            assert.deepEqual(equalRange(array, value, comparefn, first, last), result);
        });
    });

    describe('insertSorted', () => {
        test.each([
            [[], 2, [2]],
            [[2], 5, [2, 5]],
            [[2, 5], 1, [1, 2, 5]],
            [[1, 2, 5], 2, [1, 2, 2, 5]],
            [[1, 2, 2, 5], 4, [1, 2, 2, 4, 5]],
            [[1, 2, 2, 4, 5], -4, [-4, 1, 2, 2, 4, 5]],
        ])('insertSorted#%#', (array: number[], value: number, result: number[]) => {
            array.splice(lowerBound(array, value), 0, value);
            assert.deepEqual(array, result);
        });
    });
});