#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define NELEM(x) (sizeof(x) / sizeof(x[0]))

typedef int T;

#define START_MAP_CAPACITY 4
#define CHUNK_CAPACITY 10

struct deque {
	T **map;

	size_t first_chunk;
	size_t last_chunk;

	size_t capacity;
};

void
deque_init(struct deque *d)
{
	d->first_chunk = 0;
	d->last_chunk  = 0;

	// TODO: Error handling
	d->map = calloc(START_MAP_CAPACITY, sizeof *d->map);
	if ( d->map != NULL ) {
		d->capacity = START_MAP_CAPACITY;

		for ( size_t i = 0; i != d->capacity; ++i ) {
			d->map[i] = NULL;
		}
	}
}

void
deque_free(struct deque *d)
{
	// free all chunks
	for ( size_t i = 0; i != d->capacity; ++i ) {
		free(d->map[i]);
	}

	// free the map itself
	free(d->map);
}

static void
grow_map(struct deque *d)
{
	const size_t capacity = d->capacity + (d->capacity / 2);
	T **         map      = calloc(capacity, sizeof *map);

	// copy elements
	size_t i;
	for ( i = 0; i != d->capacity; ++i ) {
		map[i] = d->map[(i + d->first_chunk) % d->capacity];
	}

	// initialize the rest (new) elements with NULL
	for ( ; i != capacity; ++i ) {
		map[i] = NULL;
	}

	// free old & assign new map
	free(d->map);
	d->map = map;

	// adjust pointers
	d->first_chunk = 0;
	d->last_chunk  = d->capacity - 1;

	// set new capacity
	d->capacity = capacity;
}

static void
append_chunk(struct deque *d)
{
	size_t next = (d->last_chunk + 1) % d->capacity;

	if ( next == d->first_chunk ) { // Resize the map
		grow_map(d);

		next = d->last_chunk + 1;
	}

	d->map[d->last_chunk] = calloc(CHUNK_CAPACITY, sizeof **d->map);
	d->last_chunk         = next;
}

static void
prepend_chunk(struct deque *d)
{
	size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity;

	if ( prev == d->last_chunk ) {
		grow_map(d);

		prev = d->capacity - 1;
	}

	d->map[prev]   = calloc(CHUNK_CAPACITY, sizeof **d->map);
	d->first_chunk = prev;
}

static void
deque_show(struct deque *d)
{
	printf("first: %zu -- last: %zu -- capacity: %zu\n", d->first_chunk, d->last_chunk, d->capacity);
	for ( size_t i = 0; i != d->capacity; ++i ) {
		printf("%zu(%p) ", i, (void *) d->map[i]);
	}
	puts("");
}

int
main(void)
{
	struct deque c;

	deque_init(&c);

	deque_show(&c);
	append_chunk(&c);
	deque_show(&c);
	append_chunk(&c);
	deque_show(&c);
	append_chunk(&c);
	deque_show(&c);
	prepend_chunk(&c);
	deque_show(&c);
	append_chunk(&c);
	deque_show(&c);
	prepend_chunk(&c);
	deque_show(&c);
	prepend_chunk(&c);
	deque_show(&c);

	deque_free(&c);

	return 0;
}