// Hidden header style array. (2.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; })

// Array (private).

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, size_t itemsize)
{
    assert(p != 0);
    p = _ar_reserve(p, size, itemsize);
    _PTR_TO_HDR(p)->size = size;
    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);
}

const void *_ar_at_c(const void *p, ptrdiff_t i, size_t itemsize)
{
    assert(p != 0);
    ptrdiff_t size = _PTR_TO_HDR(p)->size;
    if (i < 0)
        i += size;
    assert(0 <= i && i < size);
    return (const char*)p + 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);

    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_append(void *p, const void *item, size_t itemsize)
{
    assert(p != 0);
    return _ar_insert(p, _PTR_TO_HDR(p)->size, item, 1, itemsize);
}

// Array (public).

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

#define ar_init(a) ((a) = _ar_init())
#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) ((a) = _ar_resize(a, n, sizeof *(a)))
#define ar_at(a, i) (((__typeof__(*(a))*)_ar_at(a, i, sizeof *(a)))[0])
#define ar_at_c(a, i) (((const __typeof__(*(a))*)_ar_at_c(a, i, sizeof *(a)))[0])
#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_append(a, v) ((a) = _ar_append(a, (__typeof__(*(a))[]){v}, sizeof *(a)))

// 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++)
    {
        if (i != 0) printf(", ");
        printf("%d", p[i]);
    }
    puts("]");
}

int main(void)
{
    int *p = 0;
    // Init
    ar_init(p);
    ar_print(p);
    // Append
    for (int i = 0; i < 4; i++)
    {
        ar_append(p, i);
        ar_print(p);
    }
    // At
    for (int i = 0; i < 4; i++)
    {
        assert(p[i] == ar_at(p, i));
        assert(p[ar_size(p)-1-i] == ar_at(p, -1-i));
    }
    // Insert/Remove
    ar_insert(p, 2, ((int[]){1111, 2222}), 2); // middle
    ar_print(p);
    ar_remove(p, 2, 2);
    ar_print(p);
    ar_insert(p, 0, ((int[]){-3, -2, -1}), 3); // front
    ar_print(p);
    ar_remove(p, 0, 3);
    ar_print(p);
    ar_insert(p, ar_size(p), ((int[]){5, 6, 7, 8}), 4); // back
    ar_print(p);
    ar_remove(p, ar_size(p)-4, 4);
    ar_print(p);
    // Pop
    while (ar_size(p) != 0)
    {
        ar_pop(p);
        ar_print(p);
    }
    // Free
    ar_free(p);
    return 0;
}