const howFast = function howFast(func, params) {
    const start = performance.now();
    func(params);
    const end = performance.now();

    return (end - start).toFixed(10) + ' ms';

}

const swap = function swap(array, first, second) {
    let temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

const print = function print(array) {
    console.log(arrToString(array));
}


const arrToString = function arrToString(array) {
    return array.join(' - ');
}

const createNodeWithContent = function createNodeWithContent(htmlElement, content) {

    if (typeof htmlElement !== 'string') throw new Error('Please enter a valid html element!');

    const newNode = document.createElement(htmlElement);
    newNode.appendChild(document.createTextNode(content));

    return newNode;
}

const test = function test(functionToTest, testCase, label) {

    const contentNode = document.getElementById('sorting');

    const labelNode = createNodeWithContent('h2', label);
    const resultNode = createNodeWithContent('p', functionToTest(testCase));
    const timeNode = createNodeWithContent('small', howFast(functionToTest, testCase))

    contentNode.appendChild(labelNode);
    contentNode.appendChild(resultNode);
    contentNode.appendChild(timeNode);
    contentNode.appendChild(document.createElement('hr'));
}

const selectionSort = function selectionSort(array) {
    let min;

    for (let i = 0; i < array.length; i++) {
        min = i;

        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }

        if (i != min) {
            swap(array, i, min);
        }
    }

    return arrToString(array);
}

const bubbleSort = function bubbleSort(array) {
    for (let k = 1; k < array.length; k++) {
        let flag = false;

        // to avoid sorting on sorted part
        // loop from 0 to n-k
        for (let i = 0; i < array.length - k; i++) {
            if (array[i] > array[i + 1]) {
                // swap two adjacent elements
                swap(array, i, i + 1);

                flag = true;
            }
        }
        if (flag === false) break;
    }

    return arrToString(array);
}

const insertionSort = function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
        let value = array[i];

        // index of the comparing value
        let holeIndex = i;

        while (holeIndex > 0 && array[holeIndex] > value) {

            // keep going backward until the right place is found
            array[holeIndex] = array[holIndex - 1];
            holeIndex -= 1;
        }

        // put the comparing value to the right position
        array[holeIndex] = value;
    }

    return arrToString(array);
}


const mergeSort = function mergeSort(array) {

    const merge = function merge(left, right) {

        let rightIndex = 0,
            leftIndex = 0,
            result = [];

        while (leftIndex < left.length && rightIndex < right.length) {

            if (left[leftIndex] <= right[rightIndex]) {

                result.push(left[leftIndex]);
                leftIndex++;
            } else {

                result.push(right[rightIndex]);
                rightIndex++;
            }
        }

        return arrToString(result
            .concat(left.slice(leftIndex))
            .concat(right.slice(rightIndex)));
    }

    const arrayLength = array.length;

    if (arrayLength < 2) {
        return array;
    }

    let midPoint = Math.floor(arrayLength / 2);

    const left = array.slice(0, midPoint);
    const right = array.slice(midPoint);

    mergeSort(left);
    mergeSort(right);

    return merge(left, right);
}

const interativeBNS = function interativeBNS(sortedArray, target) {

    let start = 0,
        end = sortedArray.length - 1;

    while (start <= end) {

        let mid = Math.floor((start + end) / 2);

        if (target === sortedArray[mid]) {

            return mid;
        } else if (target < sortedArray[mid]) {

            end = mid - 1;
        } else {

            start = mid + 1;
        }
    }

    return -1;
}

const recursiveBNS = function recursiveBNS(sortedArray, target, start = 0, end = sortedArray.length - 1) {

    if (start > end) return 'Error 404: Not found.';

    let mid = Math.floor((start + end) / 2);

    if (target === sortedArray[mid]) {

        return mid;
    } else if (target < sortedArray[mid]) {

        end = mid - 1;
    } else {

        start = mid + 1;
    }

    return recursiveBNS(sortedArray, target, start, end);
}

/**
 * Find the {first} or {last} occurence of a target number in a sorted array.
 *
 * @param {Array} sortedArray
 * @param {number} target The number to search for.
 * @param {string} condition Either 'first' or 'last'.
 * @param {number} result The index of the number that we are looking for.
 * @param {number} start Start index. Defautl 0.
 * @param {number} end End index. Default array.length - 1
 */
const findOccurence = function findOccurence(sortedArray, target, condition = 'first', result = -1, start = 0, end = sortedArray.length - 1) {

    if (start > end) {

        if (result === -1) {

            return 'Error 404: Not found.';
        } else {

            return result;
        }
    }

    let mid = Math.floor((start + end) / 2);

    if (target === sortedArray[mid]) {

        result = mid;

        if (condition === 'first') {

            // if we want to find the first occurence, keep going to the left
            end = mid - 1;
        } else if (condition === 'last') {

            // if we want to find the last occurence, keep going to the right
            start = mid + 1;
        } else {

            throw new Error('The condition must either be `last` or `first`!')
        }
    } else if (target < sortedArray[mid]) {

        end = mid - 1;
    } else {

        start = mid + 1;
    }

    return findOccurence(sortedArray, target, condition, result, start, end);
}

///////////////////////////////////////////////////////////////////////////////////////////////////

const array = [6, 3, 9, 2, 1];
const sortedArray = [2, 4, 6, 7, 8, 9, 9, 10];
const testCaseNode = document.createTextNode(arrToString(array));
document.getElementById('test-case').appendChild(testCaseNode);

test(bubbleSort, array, 'Bubble Sort');
test(selectionSort, array, 'Selection Sort');
test(insertionSort, array, 'Insertion Sort');
test(mergeSort, array, 'Merge Sort');


console.log(findOccurence(sortedArray, 9, 'last'));