#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 17

struct deque {
	T **map;

	size_t first_chunk;
	size_t last_chunk;

	size_t start;
	size_t size;
	size_t capacity;
};

void
deque_init(struct deque *d)
{
	d->first_chunk = 0;
	d->last_chunk  = 0;
	d->start       = 0;
	d->size        = 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
map_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
map_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
map_remove_front_chunk(struct deque *d)
{
	if ( d->first_chunk == d->last_chunk )
		return;

	const size_t next = (d->first_chunk + 1) % d->capacity;

	free(d->map[d->first_chunk]);
	d->map[d->first_chunk] = NULL;

	d->first_chunk = next;
}

static void
map_remove_tail_chunk(struct deque *d)
{
	if ( d->first_chunk == d->last_chunk )
		return;

	const size_t prev = (d->last_chunk + d->capacity - 1) % d->capacity;

	free(d->map[prev]);
	d->map[prev] = NULL;

	d->last_chunk = prev;
}

void
deque_get_at(struct deque *d, size_t idx, T *data)
{
	const size_t offset    = d->start + idx;
	const size_t chunk_off = offset % CHUNK_CAPACITY;
	const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;

	*data = d->map[chunk_num][chunk_off];
}

void
deque_push_back(struct deque *d, T data)
{
	const size_t offset    = d->start + d->size;
	const size_t chunk_off = offset % CHUNK_CAPACITY;
	size_t       chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;

	if ( chunk_num == d->last_chunk ) {
		map_append_chunk(d);
		chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;
	}

	d->map[chunk_num][chunk_off] = data;
	++d->size;
}

bool
deque_pop_front(struct deque *d, T *data)
{
	if ( d->size == 0 )
		return false;

	const size_t chunk_off = d->start % CHUNK_CAPACITY;
	const size_t chunk_num = ((d->start / CHUNK_CAPACITY) + d->first_chunk) % d->capacity;

	*data = d->map[chunk_num][chunk_off];

	--d->size;
	++d->start;

	if ( d->size == 0 || d->start == CHUNK_CAPACITY ) {
		map_remove_front_chunk(d);
		d->start = 0;
	}

	return true;
}

static void
deque_show(struct deque *d)
{
	printf("first: %zu -- last: %zu -- size: %zu -- capacity: %zu -- start: %zu\n",
	       d->first_chunk, d->last_chunk, d->size, d->capacity, d->start);
	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);

	for ( int i = 0; i != 100; ++i ) {
		deque_push_back(&c, i);
		//deque_show(&c);
	}

	T data;
	while ( deque_pop_front(&c, &data) ) {
		printf("%u, ", data);
	}
	putchar('\n');
	deque_show(&c);

	deque_free(&c);

	return 0;
}