import { assert } from 'chai';
import * as binaryHeap from '../../../lib/algorithms/binaryHeap';

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

describe('algorithms.binaryHeap', () => {
    describe('isHeapUntil', () => {
        test.each([
            [[], 0, undefined],
            [[1, 2], 2, undefined],
            [[2, 1], 1, undefined],
            [[2, 2, 2], 3, undefined],
            [[2, 2, 2], 3, descending],
            [[2, 1], 2, descending],
            [[1, 5, 3, 7, 9, 8], 6, undefined],
            [[1, 3, 5, 7, 9, 8], 6, undefined],
            [[1, 5, 3, 7, 9, 8], 6, ascending],
            [[9, 8, 7, 5, 3, 1], 6, descending],
            [[1, 5, 3, 4, 9, 8], 3, undefined],
            [[1, 5, 3, 5, 9, 8], 6, undefined],
        ])('isHeapUntil#%#', (array: number[], n: number, compare: (a: number, b: number) => number) => {
            const isHeap = array.length === n;
            assert.isTrue(binaryHeap.isHeapUntil(array, compare) === n);
            assert.isTrue(binaryHeap.isHeap(array, compare) === isHeap);
        });
    });

    describe('pushHeap', () => {
        test.each([
            [[3, 7, 9, 5, 1, 8], undefined],
            [[3, 7, 9, 5, 1, 8], descending],
            [[1, 5, 3, 7, 9, 8], undefined],
            [[1, 1, 1, 1], undefined],
            [[1, 2, 3, 4, 5], undefined],
            [[5, 4, 3, 2, 1], undefined],
            [[1], undefined],
        ])('pushHeap#%#', (values: number[], compare: (a: number, b: number) => number) => {
            const array = [];
            for (const value of values) {
                array.push(value);
                binaryHeap.pushHeap(array, compare);
                assert.isTrue(binaryHeap.isHeap(array, compare))
            }
        });
    });

    describe('popHeap', () => {
        test.each([
            [[], undefined, undefined],
            [[1], 1, undefined],
            [[1, 1], 1, undefined],
            [[1, 3, 5, 7, 9, 8], 1, undefined],
            [[3, 7, 5, 8, 9], 3, undefined],
            [[5, 7, 9, 8], 5, undefined],
            [[7, 8, 9], 7, undefined],
            [[8, 9], 8, undefined],
            [[9], 9, undefined],
            [[9, 8, 7, 5, 3, 1], 9, descending],
            [[8, 5, 7, 1, 3], 8, descending],
            [[7, 5, 3, 1], 7, descending],
            [[5, 1, 3], 5, descending],
            [[3, 1], 3, descending],
            [[1], 1, descending],
            [[1, 5, 3, 7, 9, 8], 1, undefined],
        ])('popHeap#%#', (values: number[], result: number, compare: (a: number, b: number) => number) => {
            const array = [...values];
            binaryHeap.popHeap(array, compare);
            const value = array.pop();
            assert.strictEqual(value, result);
        });
    });

    describe('makeHeap', () => {
        test.each([
            [[], ascending],
            [[1], undefined],
            [[1, 1], undefined],
            [[1, 2, 3, 4, 5], undefined],
            [[5, 4, 3, 2, 1], undefined],
            [[3, 7, 9, 5, 1, 8], undefined],
            [[5, 1, 3, 9, 7, 8], undefined],
            [[3, 7, 9, 5, 1, 8], descending],
        ])('makeHeap#%#', (values: number[], compare: (a: number, b: number) => number) => {
            const array = [...values];
            binaryHeap.makeHeap(array, compare);
            assert.isTrue(binaryHeap.isHeap(array, compare));
        });
    });

    describe('sortHeap', () => {
        test.each([
            [[], [], undefined],
            [[1], [1], undefined],
            [[1, 1], [1, 1], undefined],
            [[5, 1, 3, 9, 7, 8], [9, 8, 7, 5, 3, 1], undefined],
            [[5, 1, 3, 9, 7, 8], [1, 3, 5, 7, 8, 9], descending],
        ])('sortHeap#%#', (values: number[], result: number[], compare: (a: number, b: number) => number) => {
            const array = [...values];
            binaryHeap.makeHeap(array, compare);
            binaryHeap.sortHeap(array, compare);
            assert.deepEqual(array, result);
        });
    });

    describe('replaceHeap', () => {
        test.each([
            [[], 0, 1, [], undefined],
            [[2], 0, 1, [1], undefined],
            [[2], 0, 1, [1], undefined],
            [[1, 5, 3, 7, 9, 8], 7, 2, [1, 5, 3, 7, 9, 8], undefined],
            [[1, 5, 3, 7, 9, 8], 3, 2, [1, 2, 3, 5, 9, 8], undefined],
            [[1, 5, 3, 7, 9, 8], 3, 8, [1, 5, 3, 7, 9, 8], undefined],
            [[9, 8, 7, 5, 3, 1], 3, 10, [10, 9, 7, 8, 3, 1], descending],
            [[9, 8, 7, 5, 3, 1], 3, 4, [9, 8, 7, 5, 3, 1], descending],
        ])('replaceHeap#%#', (values: number[], index: number, value: number, result: number[], compare: (a: number, b: number) => number) => {
            const array = [...values];
            binaryHeap.replaceHeap(array, index, value, compare);
            assert.deepEqual(array, result);
        });
    });
});