UN_COMP_PROC(un_sort_std_comp_proc) {
    assert(a != NULL);
    assert(b != NULL);
    return memcmp((u8*)a, (u8*)b, size);
}

UN_COMP_PROC(un_sort_s8_comp_proc) {
    s8 a_s8, b_s8;
    assert(size == sizeof(s8));
    assert(a != NULL);
    assert(b != NULL);

    a_s8 = *(s8*)a;
    b_s8 = *(s8*)b;

    if (a_s8 < b_s8) return -1;
    if (a_s8 > b_s8) return  1;

    return 0;
}

UN_COMP_PROC(un_sort_s16_comp_proc) {
    s16 a_s16, b_s16;
    assert(size == sizeof(s16));
    assert(a != NULL);
    assert(b != NULL);

    a_s16 = *(s16*)a;
    b_s16 = *(s16*)b;

    if (a_s16 < b_s16) return -1;
    if (a_s16 > b_s16) return  1;

    return 0;
}

UN_COMP_PROC(un_sort_s32_comp_proc) {
    s32 a_s32, b_s32;
    assert(size == sizeof(s32));
    assert(a != NULL);
    assert(b != NULL);

    a_s32 = *(s32*)a;
    b_s32 = *(s32*)b;

    if (a_s32 < b_s32) return -1;
    if (a_s32 > b_s32) return  1;

    return 0;
}

UN_COMP_PROC(un_sort_s64_comp_proc) {
    s64 a_s64, b_s64;
    assert(size == sizeof(s64));
    assert(a != NULL);
    assert(b != NULL);

    a_s64 = *(s64*)a;
    b_s64 = *(s64*)b;

    if (a_s64 < b_s64) return -1;
    if (a_s64 > b_s64) return  1;
    return 0;
}

UN_COMP_PROC(un_sort_string_comp_proc) {
    assert(a != NULL);
    assert(b != NULL);
    assert(size == sizeof(String));
    UNUSED(size);

    String va = *(String*)a;
    String vb = *(String*)b;

    return un_string_compare(va, vb);
}

static void sort_swap(void *data, u32 size, u64 a, u64 b) {
    void *temp;
    void *a_addr, *b_addr;

    a_addr = (u8*)data + a * size;
    b_addr = (u8*)data + b * size;

    temp = un_memory_alloc(size, un_alloc_temp_get());

    memcpy(temp,   a_addr, size);
    memcpy(a_addr, b_addr, size);
    memcpy(b_addr, temp,   size);
}

// start - in elements, inclusive
// stop  - in elements, exclusive
void un_sort_quick(void *data, u32 element_size, u64 start, u64 stop, compare_func_proc *comp) {
    s64 size;
    u64 begin_index, end_index, pivot_index;
    u8 *pivot, *begin, *end;
    Allocator talloc;

    size = stop - start;

    if (size < 2) {
        return;
    }

    if (comp == NULL) {
        comp = un_sort_std_comp_proc;
    }

    if (size == 2) {
        if (comp(element_size, ((u8*)data) + start * element_size, ((u8*)data) + (stop - 1) * element_size) > 0) {
            sort_swap(data, element_size, start, stop - 1);
        }

        return;
    }     
    
    talloc = un_alloc_temp_get();

    // u64 pivot_index = start + (stop - start) / 2; // center
    pivot_index = stop - 1;
    pivot       = (u8*)un_memory_alloc(element_size, talloc);
    memcpy(pivot, (u8*)data + pivot_index * element_size, element_size);

    begin_index = start;
    end_index   = stop - 1;

    while (begin_index < end_index) {
        begin = ((u8*)data) + begin_index * element_size;
        end   = ((u8*)data) + end_index * element_size;

        if (comp(element_size, begin, pivot) < 0) {
            begin_index++;
            continue;
        }

        if (comp(element_size, end, pivot) > 0) {
            end_index--;
            continue;
        }

        if (comp(element_size, begin, end) == 0) {
            begin_index++;
            end_index--;
            continue;
        }

        sort_swap(data, element_size, begin_index, end_index);
        if (begin_index == pivot_index) {
            pivot_index = end_index;
        } else if (end_index == pivot_index) {
            pivot_index = begin_index;
        }
    }

    un_sort_quick(data, element_size, start, pivot_index, comp);
    un_sort_quick(data, element_size, pivot_index + 1, stop, comp);
}