#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 map_begin;
	size_t map_end;
	size_t map_capacity;

	size_t offset;
	size_t size;
};

void
deque_init(struct deque *d)
{
	d->map_begin = 0;
	d->map_end   = 0;
	d->offset    = 0;
	d->size      = 0;

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

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

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

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

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

	// copy elements
	size_t i;
	for ( i = 0; i != d->map_capacity; ++i ) {
		map[i] = d->map[(i + d->map_begin) % d->map_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->map_begin = 0;
	d->map_end   = d->map_capacity - 1;

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

static void
map_append_chunk(struct deque *d)
{
	size_t next = (d->map_end + 1) % d->map_capacity;

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

		next = d->map_end + 1;
	}

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

static void
map_prepend_chunk(struct deque *d)
{
	size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity;

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

		prev = d->map_capacity - 1;
	}

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

static void
map_remove_front_chunk(struct deque *d)
{
	if ( d->map_begin == d->map_end )
		return;

	const size_t next = (d->map_begin + 1) % d->map_capacity;

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

	d->map_begin = next;
}

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

	const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity;

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

	d->map_end = prev;
}

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

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

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

	if ( chunk_num == d->map_end ) {
		map_append_chunk(d);
		chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
	}

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

void
deque_push_front(struct deque *d, T data)
{
	if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei!
		map_prepend_chunk(d);
		d->offset = CHUNK_CAPACITY;
	}

	++d->size;
	--d->offset;

	size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;

	d->map[chunk_num][d->offset] = data;
}

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

	--d->size;

	const size_t offset    = d->offset + d->size;
	const size_t chunk_off = offset % CHUNK_CAPACITY;
	const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;

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

	if ( d->size == 0 || chunk_off == 0 ) {
		map_remove_tail_chunk(d);
	}

	return true;
}

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

	const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;

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

	--d->size;
	++d->offset;

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

	return true;
}

static void
deque_show(struct deque *d)
{
	printf("first: %zu -- last: %zu -- size: %zu -- map_capacity: %zu -- offset: %zu\n",
	       d->map_begin, d->map_end, d->size, d->map_capacity, d->offset);
	for ( size_t i = 0; i != d->map_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);
	}

	for ( int i = 0; i != 100; ++i ) {
		deque_push_front(&c, 1000 + i);
	}

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

	deque_free(&c);

	return 0;
}