#include <al/test.h>
#include <al/array.h>
#include <al/random.h>

#include "array.h"
#include "common.h"

static bool array_test_init(void)
{
    AL_TEST_START("array_init");

    array(u32) ints;
    al_array_init(ints);

    AL_TEST_EQ(ints.count, 0, u32);
    AL_TEST_EQ(ints.alloc, 0, u32);
    AL_TEST_EQ(ints.data, NULL, ptr);

    al_array_free(ints);
    // Not a double-free.
    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_reserve(void)
{
    AL_TEST_START("array_reserve");

    array(u32) ints;
    al_array_init(ints);

    al_array_reserve(ints, 64);
    AL_TEST_EQ(ints.alloc, 256, u32);
    AL_TEST_NEQ(ints.data, NULL, ptr);

    al_array_reserve(ints, 128);
    AL_TEST_EQ(ints.alloc, 512, u32);
    AL_TEST_NEQ(ints.data, NULL, ptr);

    al_array_reserve(ints, 129);
    AL_TEST_EQ(ints.alloc, 1024, u32);
    AL_TEST_NEQ(ints.data, NULL, ptr);

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_at(void)
{
    AL_TEST_START("array_at");

    array(u32) ints;
    al_array_init(ints);

    u32 x = 5;
    al_array_push(ints, x);
    al_array_push(ints, (u32)4);

    AL_TEST_EQ(al_array_at(ints, 0), 5, u32);
    AL_TEST_EQ(al_array_at(ints, 1), 4, u32);
    AL_TEST_EQ(ints.count, 2, u32);
    AL_TEST_EQ(ints.alloc, 8, u32);

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_last(void)
{
    AL_TEST_START("array_last");

    array(u32) ints;
    al_array_init(ints);

    u32 x = 1, y = 2, z = 3;
    al_array_push(ints, x);
    al_array_push(ints, y);
    al_array_push(ints, z);

    AL_TEST_EQ(al_array_last(ints), z, u32);
    AL_TEST_EQ(ints.count, 3, u32);
    AL_TEST_EQ(ints.alloc, 16, u32);

    al_array_free(ints);

    AL_TEST_END();
}

//#define ENABLE_MAX_ALLOC_SORT

#ifdef ENABLE_MAX_ALLOC_SORT
static s32 uint8_compare(const void *a, const void *b)
{
    if (*(u8 *)a < *(u8 *)b) return 1;
    else if (*(u8 *)b < *(u8 *)a) return -1;
    return 0;
}
#endif

static bool array_test_push(void)
{
    AL_TEST_START("array_push");

    array(u8) bytes;
    al_array_init(bytes);

    u8 increment = 0;
    for (u32 i = 0; i < MAX_ALLOC_32; i++) {
        al_array_push(bytes, (increment = (u8)al_u32_add_wrap((u32)increment, 2, UINT8_MAX)));
    }
    AL_TEST_EQ(bytes.count, MAX_ALLOC_32, u32);
    AL_TEST_EQ(bytes.alloc, MAX_ALLOC_32, u32);

    AL_TEST_EQ(&al_array_at(bytes, MAX_ALLOC_32 - 1), &al_array_last(bytes), ptr);

    AL_TEST_EQ(al_array_at(bytes, 3535), 187, u8);
    AL_TEST_EQ(al_array_at(bytes, 2348151), 224, u8);
    AL_TEST_EQ(al_array_at(bytes, 75134), 75, u8);
    AL_TEST_EQ(al_array_at(bytes, 1735095), 152, u8);
    AL_TEST_EQ(al_array_at(bytes, 191236099), 250, u8);
    if (MAX_ALLOC_32 > INT32_MAX) {
        AL_TEST_EQ(al_array_at(bytes, 3116282697), 236, u8);
        AL_TEST_EQ(al_array_at(bytes, 2923789681), 199, u8);
    }

#ifdef ENABLE_MAX_ALLOC_SORT // This is very slow.
    al_array_sort(bytes, u8, uint8_compare);
    AL_TEST_LTE(al_array_at(bytes, MAX_ALLOC_32 - 1), al_array_at(bytes, MAX_ALLOC_32 - 26000000), u8);
    AL_TEST_LTE(al_array_at(bytes, MAX_ALLOC_32 - 27000000), al_array_at(bytes, MAX_ALLOC_32 - 52000000), u8);
    AL_TEST_LTE(al_array_at(bytes, MAX_ALLOC_32 - 53000000), al_array_at(bytes, MAX_ALLOC_32 - 78000000), u8);
    AL_TEST_LTE(al_array_at(bytes, MAX_ALLOC_32 - 79000000), al_array_at(bytes, MAX_ALLOC_32 - 104000000), u8);
#endif

    al_array_free(bytes);

    AL_TEST_END();
}

static bool array_test_pop(void)
{
    AL_TEST_START("array_pop");

    array(u32) ints;
    al_array_init(ints);

    u32 x = 4, y = 5;
    al_array_push(ints, x);
    al_array_push(ints, y);

    u32 ry = al_array_pop(ints);
    AL_TEST_EQ(ints.count, 1, u32);

    u32 rx = al_array_pop(ints);
    AL_TEST_EQ(ints.count, 0, u32);

    AL_TEST_EQ(rx, x, u32);
    AL_TEST_EQ(ry, y, u32);

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_remove_at(void)
{
    AL_TEST_START("array_remove_at");

    array(u32) ints;
    al_array_init(ints);
    al_array_reserve(ints, 12);

    u32 array_before[] = { 1, 2, 3, 4, 5, 6 };
    u32 array_after[] = { 2, 3, 4 };

    for (u32 i = 0; i < ARRAY_SIZE(array_before); i++) {
        al_array_push(ints, array_before[i]);
    }

    al_array_remove_at(ints, 0);
    al_array_remove_at(ints, 3);
    al_array_remove_at(ints, 3);

    AL_TEST_EQ(ints.count, ARRAY_SIZE(array_after), u32);

    for (u32 i = 0; i < ARRAY_SIZE(array_after); i++) {
        AL_TEST_EQ(al_array_at(ints, i), array_after[i], u32);
    }

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_remove_range(void)
{
    AL_TEST_START("array_remove_range");

    array(u32) ints;
    al_array_init(ints);
    al_array_reserve(ints, 12);

    u32 array_before[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
    u32 array_after[] = { 1, 3, 4, 7, 8, 11 };

    for (u32 i = 0; i < ARRAY_SIZE(array_before); i++) {
        al_array_push(ints, array_before[i]);
    }

    al_array_remove_range(ints, 1, 2);
    al_array_remove_range(ints, 3, 5);
    AL_TEST_EQ(ints.count, 9, u32);

    al_array_remove_range(ints, 5, 7);
    AL_TEST_EQ(ints.count, 7, u32);

    al_array_remove_range(ints, 6, 7);

    AL_TEST_EQ(ints.count, ARRAY_SIZE(array_after), u32);

    for (u32 i = 0; i < ARRAY_SIZE(array_after); i++) {
        AL_TEST_EQ(al_array_at(ints, i), array_after[i], u32);
    }

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_pop_at(void)
{
    AL_TEST_START("array_pop_at");

    array(u32) ints;
    al_array_init(ints);

    u32 array_before[] = { 1, 2, 3, 4, 5, 6 };
    u32 array_after[] = { 2, 3, 4 };

    for (u32 i = 0; i < ARRAY_SIZE(array_before); i++) {
        al_array_push(ints, array_before[i]);
    }

    u32 x, y, z;
    al_array_pop_at(ints, 0, x);
    al_array_pop_at(ints, 3, y);
    al_array_pop_at(ints, 3, z);

    AL_TEST_EQ(x, array_before[0], u32);
    AL_TEST_EQ(y, array_before[4], u32);
    AL_TEST_EQ(z, array_before[5], u32);

    AL_TEST_EQ(ints.count, ARRAY_SIZE(array_after), u32);

    for (u32 i = 0; i < ARRAY_SIZE(array_after); i++) {
        AL_TEST_EQ(al_array_at(ints, i), array_after[i], u32);
    }

    al_array_free(ints);

    AL_TEST_END();
}

static bool array_test_insert(void)
{
    AL_TEST_START("array_insert");

    array(struct test_t) objects;
    al_array_init(objects);

    struct test_t x = { .d = 5 };
    struct test_t y = { .d = 2 };
    struct test_t z = { .d = 6 };

    al_array_push(objects, (struct test_t){ .d = 7 });
    al_array_push(objects, (struct test_t){ .d = 9 });
    al_array_push(objects, (struct test_t){ .d = 444 });

    al_array_insert(objects, 1, x);
    al_array_insert(objects, 0, y);
    al_array_insert(objects, 1, z);

    AL_TEST_EQ(al_array_at(objects, 3).d, x.d, u32);
    AL_TEST_EQ(al_array_at(objects, 0).d, y.d, u32);
    AL_TEST_EQ(al_array_at(objects, 1).d, z.d, u32);

    AL_TEST_EQ(objects.count, 6, u32);

    al_array_remove_at(objects, 3);

    AL_TEST_EQ(objects.count, 5, u32);

    AL_TEST_NEQ(al_array_at(objects, 3).d, x.d, u32);
    AL_TEST_EQ(al_array_at(objects, 0).d, y.d, u32);
    AL_TEST_EQ(al_array_at(objects, 1).d, z.d, u32);

    al_array_free(objects);

    AL_TEST_END();
}

static bool array_test_foreach(void)
{
    AL_TEST_START("array_foreach");

    array(u32) ints;
    al_array_init(ints);

    al_array_push(ints, (u32)0);
    al_array_push(ints, (u32)1);
    al_array_push(ints, (u32)2);
    al_array_push(ints, (u32)3);
    al_array_push(ints, (u32)4);
    al_array_push(ints, (u32)5);

    u32 iter0;
    al_array_foreach(ints, i, iter0) {
        AL_TEST_EQ(iter0, i, u32);
    }

    u32 iter1;
    al_array_foreach_rev(ints, i, iter1) {
        AL_TEST_EQ(iter1, i, u32);
    }

    u32 *ptr0;
    al_array_foreach_ptr(ints, i, ptr0) {
        AL_TEST_EQ(*ptr0, i, u32);
    }

    u32 iter2;
    al_array_foreach_rev(ints, i, iter2) {
        AL_TEST_EQ(iter2, i, u32);
        al_array_remove_at(ints, i);
    }

    AL_TEST_EQ(ints.count, 0, u32);

    al_array_push(ints, (u32)0);
    al_array_push(ints, (u32)1);
    al_array_push(ints, (u32)2);
    al_array_push(ints, (u32)3);
    al_array_push(ints, (u32)4);
    al_array_push(ints, (u32)5);
    al_array_push(ints, (u32)6);
    al_array_push(ints, (u32)7);
    al_array_push(ints, (u32)8);
    al_array_push(ints, (u32)9);

    u32 iter3, count = 0;
    al_array_foreach(ints, i, iter3) {
        AL_TEST_EQ(iter3, count, u32);
        count++;
        al_array_remove_at_iter(ints, i);
    }

    al_array_push(ints, (u32)0);
    al_array_push(ints, (u32)1);
    al_array_push(ints, (u32)2);
    al_array_push(ints, (u32)3);
    al_array_push(ints, (u32)4);
    al_array_push(ints, (u32)5);
    al_array_push(ints, (u32)6);
    al_array_push(ints, (u32)7);
    al_array_push(ints, (u32)8);
    al_array_push(ints, (u32)9);

    u32 iter4;
    al_array_foreach(ints, i, iter4) {
        AL_TEST_EQ(iter4, i + i, u32);
        al_array_remove_at(ints, i);
    }

    al_array_free(ints);

    AL_TEST_END();
}

static s32 int32_compare(const void *a, const void *b)
{
    if (*(s32 *)a < *(s32 *)b) return 1;
    else if (*(s32 *)b < *(s32 *)a) return -1;
    return 0;
}

static s32 int32_compare_reverse(const void *a, const void *b)
{
    if (*(s32 *)a < *(s32 *)b) return -1;
    else if (*(s32 *)b < *(s32 *)a) return 1;
    return 0;
}

static inline s64 sum_of_array(s32 *data, u32 count)
{
    s64 sum = 0;
    while (count-- > 0) {
        sum += *data++;
    }
    return sum;
}

static bool array_test_sort(void)
{
    AL_TEST_START("array_sort");

    array(s32) ints;
    al_array_init(ints);

    al_array_push(ints, 0);
    al_array_push(ints, 1);
    al_array_push(ints, 2);
    al_array_push(ints, 3);
    al_array_push(ints, 4);
    al_array_push(ints, 0);
    al_array_push(ints, 99);
    AL_TEST_EQ(sum_of_array(ints.data, ints.count), 109, s64);

    s32 end = al_rand() % 4000;
    for (s32 i = 0; i < end; i++) {
        al_array_push(ints, (al_rand() % 9001) - 9000);
    }

    s64 before_sort_sum = sum_of_array(ints.data, ints.count);
    al_array_sort(ints, s32, int32_compare);
    AL_TEST_EQ(sum_of_array(ints.data, ints.count), before_sort_sum, s64);

    for (u32 i = 1; i < ints.count; i++) {
        AL_TEST_GTE(al_array_at(ints, i - 1), al_array_at(ints, i), s32);
    }

    end = al_rand() % 4000;
    for (s32 i = 0; i < end; i++) {
        al_array_push(ints, (al_rand() % 90001) - 90000);
    }

    before_sort_sum = sum_of_array(ints.data, ints.count);
    al_array_sort(ints, s32, int32_compare_reverse);
    AL_TEST_EQ(sum_of_array(ints.data, ints.count), before_sort_sum, s64);

    for (u32 i = 1; i < ints.count; i++) {
        AL_TEST_LTE(al_array_at(ints, i - 1), al_array_at(ints, i), s32);
    }

    end = al_rand() % 4000;
    for (s32 i = 0; i < end; i++) {
        al_array_push(ints, (al_rand() % 900001) - 900000);
    }

    before_sort_sum = sum_of_array(ints.data, ints.count);
    al_array_sort(ints, s32, int32_compare);
    AL_TEST_EQ(sum_of_array(ints.data, ints.count), before_sort_sum, s64);

    for (u32 i = 1; i < ints.count; i++) {
        AL_TEST_GTE(al_array_at(ints, i - 1), al_array_at(ints, i), s32);
    }

    AL_TEST_END();
}

bool array_tests_run(u32 skip_mask)
{
    AL_TEST_START_GROUP("array");

    AL_TEST_RUN(array_test_init);
    AL_TEST_RUN(array_test_reserve);
    AL_TEST_RUN(array_test_at);
    AL_TEST_RUN(array_test_last);
    if (skip_mask & AL_TESTS_RUN_LIMITS) {
        AL_TEST_RUN(array_test_push);
    }
    AL_TEST_RUN(array_test_pop);
    AL_TEST_RUN(array_test_remove_at);
    AL_TEST_RUN(array_test_remove_range);
    AL_TEST_RUN(array_test_pop_at);
    AL_TEST_RUN(array_test_insert);
    AL_TEST_RUN(array_test_foreach);
    AL_TEST_RUN(array_test_sort);

    AL_TEST_END_GROUP();
}