// Hidden header style array. (2.10)

#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_init(a) ((a) = _ar_init())
#define ar_init_size(a, n, v) ((a) = _ar_init_size(n, (__typeof__(*(a))[]){v}, sizeof *(a)))
#define ar_init_copy(a, b) ((a) = _ar_init_copy(b, sizeof *(a)))
#define ar_free(a) (_ar_free(a), (a) = 0)
#define ar_reserve(a, n) ((a) = _ar_reserve(a, n, sizeof *(a)))
#define ar_resize(a, n, v) ((a) = _ar_resize(a, n, (__typeof__(*(a))[]){v}, sizeof *(a)))
#define ar_at(a, i) (ar_at_p(a, i)[0])
#define ar_at_c(a, i) (ar_at_c_p(a, i)[0])
#define ar_at_p(a, i) ((__typeof__(*(a))*)_ar_at(a, i, sizeof *(a)))
#define ar_at_c_p(a, i) ((const __typeof__(*(a))*)_ar_at_c(a, i, sizeof *(a)))
#define ar_remove(a, i, n) _ar_remove(a, i, n, sizeof *(a))
#define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, n, sizeof *(a)))
#define ar_push(a, v) ((a) = _ar_push(a, (__typeof__(*(a))[]){v}, sizeof *(a)))
#define ar_pop(a) _ar_pop(a)
#define ar_clear(a) _ar_clear(a)
#define ar_size(a) _ar_size(a)
#define ar_capacity(a) _ar_capacity(a)

void *_ar_reserve(void *p, size_t capacity, size_t itemsize);
void *_ar_resize(void *p, size_t size, const void *fill, size_t itemsize);
void _ar_free(void *p);
void *_ar_init(void);
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, size_t itemsize);
void *_ar_at(void *p, ptrdiff_t i, size_t itemsize);
void _ar_remove(void *p, size_t i, size_t n, size_t itemsize);
void *_ar_insert(void *p, size_t i, const void *first, size_t n, size_t itemsize);
void *_ar_push(void *p, const void *item, size_t itemsize);
void _ar_pop(void *p);
void _ar_clear(void *p);
size_t _ar_size(const void *p);
size_t _ar_capacity(const void *p);

// Implementation.

typedef struct {
    size_t size, capacity;
} _Header;

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

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

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

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

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

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

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

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

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

void *_ar_init_copy(const void *p, size_t itemsize)
{
    assert(p != 0);
    return _ar_insert(_ar_init(), 0, p, _PTR_TO_HDR(p)->size, itemsize);
}

const void *_ar_at_c(const void *p, ptrdiff_t i, size_t itemsize)
{
    assert(p != 0);
    size_t size = _PTR_TO_HDR(p)->size;
    size_t effective_i = (i < 0) ? i + size : (size_t)i;
    assert(effective_i < size);
    return (const char*)p + effective_i*itemsize;
}

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

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

    assert(self->size >= i);
    assert(self->size >= i + n); // @bug (i + n) might overflow

    if (n != 0)
    {
        size_t oldsize = self->size;
        size_t j = i + n;

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

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

    assert(self->size >= i);

    if (n != 0)
    {
        size_t oldsize = self->size;
        size_t newsize = oldsize + n;

        if (newsize > self->capacity)
        {
            p = _ar_reserve(p, MAX(2*self->capacity, newsize), itemsize);
            self = _PTR_TO_HDR(p);
        }
        self->size = newsize;
        void *ip = _ar_at(p, i, itemsize);

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

void *_ar_push(void *p, const void *item, size_t itemsize)
{
    assert(p != 0);
    return _ar_insert(p, _PTR_TO_HDR(p)->size, item, 1, itemsize);
}

void _ar_pop(void *p)
{
    assert(p != 0);
    _Header *self = _PTR_TO_HDR(p);
    assert(self->size != 0);
    self->size--;
}

void _ar_clear(void *p)
{
    assert(p != 0);
    _PTR_TO_HDR(p)->size = 0;
}

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

// Main.

void ar_print(const int *p)
{
    printf("size/capacity: %zu/%zu [", ar_size(p), ar_capacity(p));
    for (size_t i = 0; i < ar_size(p); i++)
    {
        printf(i ? ", %d" : "%d", p[i]);
    }
    puts("]");
}

void test_init_free(void)
{
    // 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);

    printf("%s: Okay.\n", __func__);
}

void test_push_pop(void)
{
    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);

    printf("%s: Okay.\n", __func__);
}

void test_insert_remove(void)
{
    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);

    printf("%s: Okay.\n", __func__);
}

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

    int *p = 0;
    ar_init(p);

    int n = 5;

    // Push/Pop (back).

    for (int i = 0; i < n; i++)
    {
        ar_push(p, i);
        ar_print(p);
    }
    while (ar_size(p) != 0)
    {
        ar_pop(p);
        ar_print(p);
    }

    // Insert/Erase.

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

    // Resize (fill).

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

    ar_free(p);
    return 0;
}