// Hidden header style array. (3.00)

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

// Utility.

#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 != 0 && 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;
}

// Interface.

#define ar_size(a) _ar_size(a)
#define ar_capacity(a) _ar_capacity(a)
#define ar_itemsize(a) _ar_itemsize(a)
#define ar_putitem(a) _ar_putitem(a)
#define ar_set_putitem(a, f) _ar_set_putitem(a, f)
#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_free(a) (_ar_free(a), (a) = 0)
#define ar_init(a) ((a) = _ar_init(sizeof *(a)))
#define ar_init_size(a, n, v) ((a) = _ar_init_size(n, (__typeof__(*(a))[]){v}, sizeof *(a)))
#define ar_init_copy(a, b) ((a) = (__typeof__(*(b))*)_ar_init_copy(b, sizeof *(a)))
#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_remove(a, i, n) _ar_remove(a, i, n)
#define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, 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_print(a) _ar_print(a, stdout)
#define ar_println(a) _ar_println(a, stdout)

size_t _ar_size(const void *p);
size_t _ar_capacity(const void *p);
size_t _ar_itemsize(const void *p);
void (*_ar_putitem(const void *p))(const void *, FILE *);
void _ar_set_putitem(void *p, void (*putitem)(const void *, FILE *));
void *_ar_reserve(void *p, size_t capacity);
void *_ar_resize(void *p, size_t size, const void *fill);
void _ar_free(void *p);
void *_ar_init(size_t itemsize);
void *_ar_init_size(size_t size, const void *fill, size_t itemsize);
void *_ar_init_copy(const void *p, size_t itemsize);
const void *_ar_at_c(const void *p, ptrdiff_t i);
void *_ar_at(void *p, ptrdiff_t i);
void _ar_remove(void *p, size_t i, size_t n);
void *_ar_insert(void *p, size_t i, const void *first, size_t n);
void *_ar_push(void *p, const void *item);
void _ar_pop(void *p);
void _ar_clear(void *p);
void _ar_print(const void *p, FILE *stream);
void _ar_println(const void *p, FILE *stream);

// Implementation.

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

#define _PTR_TO_HDR(p) ((_Header*)((char*)p - sizeof(_Header)))
#define _HDR_TO_PTR(p) ((void*)((char*)p + sizeof(_Header)))

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

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

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

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

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

void *_ar_reserve(void *p, size_t capacity)
{
    assert(p != 0);
    _Header *self = _PTR_TO_HDR(p);

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

void *_ar_resize(void *p, size_t size, const void *fill)
{
    assert(p != 0);
    p = _ar_reserve(p, size);

    _Header *self = _PTR_TO_HDR(p);
    size_t oldsize = self->size;
    self->size = size;

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

void _ar_free(void *p)
{
    if (p != 0)
        free(_PTR_TO_HDR(p));
}

void *_ar_init(size_t itemsize)
{
    _Header *self = malloc(sizeof *self);
    assert(self != 0);
    self->size = 0;
    self->capacity = 0;
    self->itemsize = itemsize;
    self->putitem = 0;
    return _HDR_TO_PTR(self);
}

void *_ar_init_size(size_t size, const void *fill, size_t itemsize)
{
    return _ar_resize(_ar_init(itemsize), size, fill);
}

void *_ar_init_copy(const void *p, size_t itemsize)
{
    assert(p != 0);
    const _Header *other = _PTR_TO_HDR(p);

    assert(itemsize == other->itemsize);
    return _ar_insert(_ar_init(itemsize), 0, p, other->size);
}

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

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

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

void _ar_remove(void *p, size_t i, size_t n)
{
    assert(p != 0);
    _Header *self = _PTR_TO_HDR(p);

    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(p, i), _ar_at(p, j), (oldsize - j)*self->itemsize);
        self->size = oldsize - n;
    }
}

void *_ar_insert(void *p, size_t i, const void *first, size_t n)
{
    assert(p != 0);
    _Header *self = _PTR_TO_HDR(p);

    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)
        {
            p = _ar_reserve(p, MAX(2*self->capacity, size));
            self = _PTR_TO_HDR(p);
        }
        self->size = size;
        void *ip = _ar_at(p, i);

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

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

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

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

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

    assert(self->putitem != 0);
    size_t n = self->size;

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

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

// Putitem callback.

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);
}

// Test.

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

    // Init.

    int *p = 0;
    ar_init(p);
    assert(ar_size(p) == 0);
    ar_free(p);
    assert(p == 0);

    // Init size.

    ar_init_size(p, 3, 123);
    assert(ar_size(p) == 3);
    for (size_t i = 0; i < 3; i++)
        assert(ar_at(p, i) == 123);

    // Init copy.

    int *q = 0;
    ar_init_copy(q, p);
    ar_free(p);
    assert(p == 0);

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

    puts("..Okay");
}

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

    int *p = 0;
    ar_init(p);

    // Push (back).

    for (int i = 0; i < 8; i++)
    {
        assert(ar_size(p) == i);
        int cp2 = i ? 1<<(31 - __builtin_clz(2*i-1)) : 0;
        assert(ar_capacity(p) == cp2);
        ar_push(p, i);
        assert(ar_at(p, -1) == i);
    }

    // Pop (back).

    for (int i = 7; i >= 0; i--)
    {
        assert(ar_at(p, -1) == i);
        ar_pop(p);
    }
    assert(ar_size(p) == 0);
    ar_free(p);

    puts("..Okay");
}

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

    int *p = 0;
    ar_init(p);

    // Insert even (bulk).

    ar_insert(p, 0, ((int[]){0, 2, 4}), 3);
    assert(ar_size(p) == 3);
    for (int i = 0; i < 3; i++)
        assert(ar_at(p, i) == 2*i);

    // Insert odd (single).

    for (int i = 0; i < 3; i++)
        ar_insert(p, 2*i+1, (int[]){2*i+1}, 1);
    assert(ar_size(p) == 6);
    for (int i = 0; i < 6; i++)
        assert(ar_at(p, i) == i);

    // Remove even (single).

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

    // Remove odd (bulk).

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

    puts("..Okay");
}

// Show.

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

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

    int n = 4;

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

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

    ar_free(p);
}

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

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

    int n = 4;

    for (int i = 0; i < n; i++)
    {
        ar_insert(p, i, ((int[]){i+1, i+1+n}), 2);
        ar_println(p);
    }

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

    ar_free(p);
}

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

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

    int n = 5;

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

    ar_free(p);
}

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

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

    int n = 4;
    int v = 1;

    for (int i = 0; i < n; i++)
    {
        int *q = 0;
        ar_init(q);
        ar_set_putitem(q, putitem_int);
        for (int j = 0; j < i+1; j++)
            ar_push(q, v++);
        ar_push(p, q);
        ar_println(p);
    }

    while (ar_size(p) != 0)
    {
        int *q = ar_at(p, -1);
        ar_free(q);
        ar_pop(p);
    }

    ar_free(p);
}

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

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