/**
 * @file array.002.c
 * @ingroup experimental
 * Dynamic array using hidden header.
 * @date 08/13/2026
 */

#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

//
// Utility.
//

#define REF_T(T, ...) \
    ((T[]){__VA_ARGS__})

#define DEREF_T(T, p) \
    (((T*)(void*)(p))[0])

#define MAX(a, b) \
({ __auto_type _x = (a); __auto_type _y = (b); \
   (_y > _x) ? _y : _x; })

void *memfill(void *base, size_t n, size_t size, const void *fill)
{
    if (n*size != 0)
    {
        memmove(base, fill, size);
        size_t i = 1;
        for (; i <= n/2; i *= 2)
            memcpy((char*)base + i*size, base, i*size);
        memcpy((char*)base + i*size, base, (n-i)*size);
    }
    return base;
}

//
// Array.
//

#define ar_size(a) _ar_size(a)
#define ar_itemsize(a) _ar_itemsize(a)
#define ar_capacity(a) _ar_capacity(a)
#define ar_putitem(a) _ar_putitem(a)
#define ar_set_putitem(a, f) _ar_set_putitem(a, f)
#define ar_at(a, i) (((__typeof__(*(a))*)_ar_at(a, i))[0])
#define ar_at_c(a, i) (((const __typeof__(*(a))*)_ar_at_c(a, i))[0])
#define ar_reserve(a, n) ((a) = _ar_reserve(a, n))
#define ar_resize(a, n, v) ((a) = _ar_resize(a, n, (__typeof__(*(a))[]){v}))
#define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, n))
#define ar_remove(a, i, n) _ar_remove(a, i, n)
#define ar_push(a, v) ((a) = _ar_push(a, (__typeof__(*(a))[]){v}))
#define ar_pop(a) _ar_pop(a)
#define ar_clear(a) _ar_clear(a)
#define ar_free(a) (_ar_free(a), (a) = 0)
#define ar_init(a, n) ((a) = _ar_init(sizeof *(a), n))
#define ar_init_size(a, n, v) ((a) = _ar_init_size(sizeof *(a), n, (__typeof__(*(a))[]){v}))
#define ar_init_copy(a, b, n) ((a) = (__typeof__(*(b))*)_ar_init_copy(b, n))
#define ar_print(a) _ar_print(a, stdout)
#define ar_println(a) _ar_println(a, stdout)

// ..

#define _BASE_TO_SELF(p) ((_Header*)((char*)p - sizeof(_Header)))
#define _SELF_TO_BASE(p) ((void*)((char*)p + sizeof(_Header)))

typedef struct {
    size_t size;
    size_t itemsize;
    size_t capacity;
    void (*putitem)(const void *item, FILE *stream);
} _Header;

size_t _ar_size(const void *base)
{
    assert(base != 0);
    return _BASE_TO_SELF(base)->size;
}

size_t _ar_itemsize(const void *base)
{
    assert(base != 0);
    return _BASE_TO_SELF(base)->itemsize;
}

size_t _ar_capacity(const void *base)
{
    assert(base != 0);
    return _BASE_TO_SELF(base)->capacity;
}

void (*_ar_putitem(const void *base))(const void *, FILE *)
{
    assert(base != 0);
    return _BASE_TO_SELF(base)->putitem;
}

void _ar_set_putitem(void *base, void (*putitem)(const void *, FILE *))
{
    assert(base != 0);
    _BASE_TO_SELF(base)->putitem = putitem;
}

const void *_ar_at_c(const void *base, ptrdiff_t i)
{
    assert(base != 0);
    const _Header *self = _BASE_TO_SELF(base);

    size_t size = self->size;
    size_t j = (i < 0) ? i + size : (size_t)i;
    assert(j < size);
    return (const char*)base + j*self->itemsize;
}

void *_ar_at(void *base, ptrdiff_t i)
{
    return (void*)_ar_at_c(base, i);
}

void *_ar_reserve(void *base, size_t capacity)
{
    // Ensure array has enough memory for capacity items.

    assert(base != 0);
    _Header *self = _BASE_TO_SELF(base);

    if (capacity > self->capacity)
    {
        self = realloc(self, sizeof *self + capacity*self->itemsize);
        assert(self != 0);
        self->capacity = capacity;
    }
    return _SELF_TO_BASE(self);
}

void *_ar_resize(void *base, size_t size, const void *fill)
{
    // Change array size and initialize newly revealed items to specified fill
    // value. If fill is not provided, items are not initialized.

    assert(base != 0);
    base = _ar_reserve(base, size);

    _Header *self = _BASE_TO_SELF(base);
    size_t oldsize = self->size;
    self->size = size;

    if (fill != 0 && size > oldsize)
        memfill(_ar_at(base, oldsize), size - oldsize, self->itemsize, fill);
    return base;
}

void *_ar_insert(void *base, size_t i, const void *first, size_t n)
{
    // Insert n items starting at first into array before position i.

    assert(base != 0);
    _Header *self = _BASE_TO_SELF(base);

    size_t oldsize = self->size;
    assert(oldsize >= i);

    if (n != 0)
    {
        size_t size;
        if (__builtin_add_overflow(oldsize, n, &size))
            assert(0 && "integer overflow");

        if (size > self->capacity)
        {
            base = _ar_reserve(base, MAX(2*self->capacity, size));
            self = _BASE_TO_SELF(base);
        }
        self->size = size;
        void *ip = _ar_at(base, i);

        if (oldsize > i)
            memmove(_ar_at(base, i + n), ip, (oldsize - i)*self->itemsize);
        memcpy(ip, first, n*self->itemsize);
    }
    return base;
}

void _ar_remove(void *base, size_t i, size_t n)
{
    // Remove n items from array starting at position i.

    assert(base != 0);
    _Header *self = _BASE_TO_SELF(base);

    size_t oldsize = self->size;
    assert(oldsize >= i);

    if (n != 0)
    {
        size_t j;
        if (__builtin_add_overflow(i, n, &j))
            assert(0 && "integer overflow");
        assert(oldsize >= j);

        if (oldsize > j)
            memmove(_ar_at(base, i), _ar_at(base, j), (oldsize - j)*self->itemsize);
        self->size = oldsize - n;
    }
}

void *_ar_push(void *base, const void *item)
{
    return _ar_insert(base, _ar_size(base), item, 1);
}

void _ar_pop(void *base)
{
    _ar_remove(base, _ar_size(base)-1, 1);
}

void _ar_clear(void *base)
{
    _ar_resize(base, 0, 0);
}

void _ar_free(void *base)
{
    if (base != 0)
        free(_BASE_TO_SELF(base));
}

void *_ar_init(size_t itemsize, size_t capacity)
{
    // Create array with enough memory for capacity items.

    _Header *self = malloc(sizeof *self + capacity*itemsize);
    assert(self != 0);
    self->size = 0;
    self->itemsize = itemsize;
    self->capacity = capacity;
    self->putitem = 0;
    return _SELF_TO_BASE(self);
}

void *_ar_init_size(size_t itemsize, size_t size, const void *fill)
{
    // Create with size items and initialize with specified fill value.

    return _ar_resize(_ar_init(itemsize, size), size, fill);
}

void *_ar_init_copy(const void *other_base, size_t capacity)
{
    // Create copy of an array with at least capacity items reserved.

    assert(other_base != 0);
    const _Header *other = _BASE_TO_SELF(other_base);

    void *base = _ar_init(other->itemsize, MAX(other->size, capacity));
    return _ar_insert(base, 0, other_base, other->size);
}

void _ar_print(const void *base, FILE *stream)
{
    assert(base != 0);
    const _Header *self = _BASE_TO_SELF(base);

    void (*putitem)(const void *, FILE *) = self->putitem;
    assert(putitem != 0);

    size_t n = self->size;

    fputc('{', stream);
    if (n != 0)
    {
        for (size_t i = 0;;)
        {
            putitem(_ar_at_c(base, i), stream);
            if (++i == n) break;
            fputs(", ", stream);
        }
    }
    fputc('}', stream);
}

void _ar_println(const void *base, FILE *stream)
{
    _ar_print(base, stream); fputc('\n', stream);
}

//
// Main.
//

void test_init_free(void)
{
    printf("<%s>\n", __func__);

    // Init.

    int *a = 0;
    ar_init(a, 0);
    assert(ar_size(a) == 0);
    assert(ar_itemsize(a) == sizeof(*a));
    assert(ar_capacity(a) == 0);

    ar_free(a);
    assert(a == 0);

    // Init (capacity).

    ar_init(a, 8);
    assert(ar_size(a) == 0);
    assert(ar_itemsize(a) == sizeof(*a));
    assert(ar_capacity(a) == 8);

    ar_free(a);
    assert(a == 0);

    // Init size.

    ar_init_size(a, 3, 123);
    assert(ar_size(a) == 3);
    assert(ar_itemsize(a) == sizeof(*a));
    assert(ar_capacity(a) == 3);

    for (size_t i = 0; i < 3; i++)
        assert(ar_at(a, i) == 123);

    // Init copy.

    int *b = 0;
    ar_init_copy(b, a, 0);

    ar_free(a);
    assert(a == 0);

    assert(ar_size(b) == 3);
    assert(ar_itemsize(b) == sizeof(*b));
    assert(ar_capacity(b) == 3);

    for (size_t i = 0; i < 3; i++)
        assert(ar_at(b, i) == 123);

    // Init copy (capacity).

    ar_init_copy(a, b, 8);

    ar_free(b);
    assert(b == 0);

    assert(ar_size(a) == 3);
    assert(ar_itemsize(a) == sizeof(*a));
    assert(ar_capacity(a) == 8);

    for (size_t i = 0; i < 3; i++)
        assert(ar_at(a, i) == 123);
    ar_free(a);
    assert(a == 0);

    puts("..Okay");
}

void test_push_pop(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);

    // Push (back).

    for (int i = 0; i < 8; i++)
    {
        ar_push(a, i);
        assert(ar_size(a) == (size_t)i+1);
        assert(ar_at(a, -1) == i);
    }

    // Pop (back).

    for (int i = 8-1; i >= 0; i--)
    {
        assert(ar_at(a, -1) == i);
        ar_pop(a);
        assert(ar_size(a) == (size_t)i);
    }

    ar_free(a);

    puts("..Okay");
}

void test_insert_remove(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);

    // Insert even (bulk).

    ar_insert(a, 0, REF_T(int, 0, 2, 4), 3);
    assert(ar_size(a) == 3);
    for (int i = 0; i < 3; i++)
        assert(ar_at(a, i) == 2*i);

    // Insert odd (single).

    for (int i = 0; i < 3; i++)
        ar_insert(a, 2*i+1, REF_T(int, 2*i+1), 1);
    assert(ar_size(a) == 6);
    for (int i = 0; i < 6; i++)
        assert(ar_at(a, i) == i);

    // Remove even (single).

    for (int i = 2; i >= 0; i--)
        ar_remove(a, 2*i, 1);
    assert(ar_size(a) == 3);
    for (int i = 0; i < 3; i++)
        assert(ar_at(a, i) == 2*i+1);

    // Remove odd (bulk).

    ar_remove(a, 0, 3);
    assert(ar_size(a) == 0);
    ar_free(a);

    puts("..Okay");
}

void test_resize(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);

    // Resize (with clear).

    for (int i = 0; i < 3; i++)
    {
        int n = i+1;
        ar_resize(a, n, i);
        assert(ar_size(a) == (size_t)n);
        for (int j = 0; j < n; j++)
            assert(ar_at(a, j) == i);
        ar_clear(a);
        assert(ar_size(a) == 0);
    }

    // Resize (without clear).

    for (int i = 0; i < 3; i++)
    {
        int n = i+1;
        ar_resize(a, n, i);
        assert(ar_size(a) == (size_t)n);
        for (int j = 0; j < n; j++)
            assert(ar_at(a, j) == j);
    }

    ar_free(a);

    puts("..Okay");
}

// ..

void putitem_ar(const void *item, FILE *stream)
{
    _ar_print(*(const void **)item, stream);
}

void putitem_int(const void *item, FILE *stream)
{
    fprintf(stream, "%d", *(const int *)item);
}

int *iota(int n, int start, int step)
{
    int *a = 0;
    ar_init(a, MAX(n, 0));
    ar_set_putitem(a, putitem_int);
    for (int i = 0; i < n; i++)
        ar_push(a, start + i*step);
    return a;
}

void show_push_pop(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);
    ar_set_putitem(a, putitem_int);

    int n = 4;

    for (int i = 0; i < n; i++)
    {
        ar_push(a, i);
        ar_println(a);
    }

    while (ar_size(a) != 0)
    {
        ar_pop(a);
        ar_println(a);
    }

    ar_free(a);
}

void show_insert_remove(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);
    ar_set_putitem(a, putitem_int);

    int n = 4;

    for (int i = 0; i < n; i++)
    {
        ar_insert(a, i, REF_T(int, i+1, i+1+n), 2);
        ar_println(a);
    }

    for (int i = n-1; i >= 0; i--)
    {
        ar_remove(a, i, 2);
        ar_println(a);
    }

    ar_free(a);
}

void show_resize(void)
{
    printf("<%s>\n", __func__);

    int *a = 0;
    ar_init(a, 0);
    ar_set_putitem(a, putitem_int);

    int n = 4;

    for (int i = 1; i <= n; i++)
    {
        ar_resize(a, i, -i);
        ar_println(a);
        ar_clear(a);
    }

    for (int i = 1; i <= n; i++)
    {
        ar_resize(a, i, -i);
        ar_println(a);
    }

    ar_free(a);
}

void show_array_of_array(void)
{
    printf("<%s>\n", __func__);

    int **a = 0;
    ar_init(a, 0);
    ar_set_putitem(a, putitem_ar);

    int n = 4;

    for (int i = 0; i < n; i++)
    {
        int count = i+1;
        int start = i*(i+1)/2+1;
        ar_push(a, iota(count, start, 1));
        ar_println(a);
    }

    for (size_t i = 0; i < ar_size(a); i++)
        ar_free(a[i]);
    ar_free(a);
}

int main(void)
{
    test_init_free();
    test_push_pop();
    test_insert_remove();
    test_resize();

    show_push_pop();
    show_insert_remove();
    show_resize();
    show_array_of_array();
    return 0;
}