#include "sorted_array.h"

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int lower_bound(int array_length, uint64_t *array, uint64_t value) {
    int low = 0;
    int high = array_length - 1;

    while (low <= high) {
        int m = (low + high) / 2;

        if (array[m] < value) {
            low = m + 1;
        } else if (array[m] > value) {
            high = m - 1;
        } else {
            return m;
        }
    }

    return low;
}

int sorted_array_find_index(int array_length, uint64_t *array, uint64_t value) {
    int low = 0;
    int high = array_length - 1;

    while (low <= high) {
        int m = (low + high) / 2;

        if (array[m] < value) {
            low = m + 1;
        } else if (array[m] > value) {
            high = m - 1;
        } else {
            return m;
        }
    }

    return -1;
}

bool sorted_array_search(int array_length, uint64_t *array, uint64_t value, int *index) {
    int i = sorted_array_find_index(array_length, array, value);

    if (index != NULL) {
        *index = i;
    }

    return i != -1;
}

int sorted_array_insert(int *array_length, uint64_t *array, uint64_t value) {
    int insertion_index = lower_bound(*array_length, array, value);

    for (int i = *array_length - 1; i >= insertion_index; i--) {
        array[i + 1] = array[i];
    }

    array[insertion_index] = value;
    *array_length += 1;
    return insertion_index;
}

void sorted_array_delete(int *array_length, uint64_t *array, uint64_t value) {
    int index = sorted_array_find_index(*array_length, array, value);

    for (int i = index; i < *array_length; i++) {
        array[i] = array[i + 1];
    }

    *array_length -= 1;
}

void array_insert_at_index(int *array_length, uint64_t *array, int insertion_index, uint64_t value) {
    for (int i = *array_length - 1; i >= insertion_index; i--) {
        array[i + 1] = array[i];
    }

    array[insertion_index] = value;
    *array_length += 1;
}

void array_append(int *array_length, uint64_t *array, uint64_t value) {
    array[*array_length] = value;
    *array_length += 1;
}

void array_print(int array_length, uint64_t *array) {
    printf("[");

    for (int i = 0; i < array_length; i++) {
        printf("%ld", array[i]);

        if (i < array_length - 1) {
            printf(", ");
        }
    }

    printf("]\n");
}

void array_insert_at_index_BPTreeNode(int *array_length, BPTreeNode **array, int insertion_index, BPTreeNode *value) {
    for (int i = *array_length - 1; i >= insertion_index; i--) {
        array[i + 1] = array[i];
    }

    array[insertion_index] = value;
    *array_length += 1;
}

void array_append_BPTreeNode(int *array_length, BPTreeNode **array, BPTreeNode *value) {
    array[*array_length] = value;
    *array_length += 1;
}

void array_delete_at_index_BPTreeNode(int *array_length, BPTreeNode **array, int deletion_index) {
    for (int i = deletion_index; i < *array_length; i++) {
        array[i] = array[i + 1];
    }

    *array_length -= 1;
}