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

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

size_t
deque_size(struct deque *d)
{
	return d->size;
}

bool
deque_is_empty(struct deque *d)
{
	return d->map_begin == d->map_end;
}

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, j;
	for ( i = 0, j = d->map_begin; i != d->map_capacity; ++i, ++j ) {
		if ( j == d->map_capacity ) {
			j = 0;
		}
		map[i] = d->map[j];
	}

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

bool
deque_get_at(struct deque *d, size_t idx, T *data)
{
	if ( idx >= d->size ) {
		return false;
	}

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

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

	return true;
}

bool
deque_set_at(struct deque *d, size_t idx, T data)
{
	if ( idx >= d->size ) {
		return false;
	}

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

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

	return true;
}

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

	if ( chunk_num == d->map_end ) {
		map_append_chunk(d);
		chunk_num = (pos / 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->offset;

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

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

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

	--d->size;

	const size_t pos       = d->offset + d->size;
	const size_t chunk_off = pos % CHUNK_CAPACITY;
	const size_t chunk_num = (pos / 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;
	}

	--d->size;

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

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

	++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]);
	}
	putchar('\n');
}

void
test_deque(void)
{
	struct deque d[1];

	deque_init(d);

	const int N = 100000;

	for ( int i = 0; i != N; ++i ) {
		deque_push_front(d, i);
	}

	for ( int i = 0; i != N; ++i ) {
		int data;
		assert(deque_pop_back(d, &data) == true);
		assert(data == i);
	}
	assert(deque_is_empty(d) == true);
	assert(deque_size(d) == 0);

	deque_free(d);

	deque_init(d);

	for ( int i = 0; i != N; ++i ) {
		deque_push_back(d, i);
	}

	for ( int i = 0; i != N; ++i ) {
		int data;
		assert(deque_pop_front(d, &data) == true);
		assert(data == i);
	}
	assert(deque_is_empty(d) == true);
	assert(deque_size(d) == 0);

	deque_free(d);

	deque_init(d);

	for ( int i = 0; i != N; ++i ) {
		deque_push_back(d, i);
	}

	for ( int i = N - 1; i >= 0; --i ) {
		int data;
		assert(deque_pop_back(d, &data) == true);
		assert(data == i);
	}
	assert(deque_is_empty(d) == true);
	assert(deque_size(d) == 0);

	deque_free(d);

	deque_init(d);

	for ( int i = 0; i != N; ++i ) {
		if ( i & 1 ) {
			deque_push_front(d, i);
		}
		else {
			deque_push_back(d, i);
		}
	}

	for ( int i = N - 1; i >= 0; --i ) {
		int data;
		if ( i & 1 ) {
			assert(deque_pop_front(d, &data) == true);
		}
		else {
			assert(deque_pop_back(d, &data) == true);
		}
		if ( data != i ) {
			printf("i: %d - data: %d\n", i, data);
		}
		assert(data == i);
	}
	assert(deque_is_empty(d) == true);
	assert(deque_size(d) == 0);

	deque_free(d);

	deque_init(d);

	for ( int i = 0; i != N; ++i ) {
		deque_push_front(d, i);
	}

	for ( int i = N - 1; i >= 0; --i ) {
		int data;
		assert(deque_pop_front(d, &data) == true);
		assert(data == i);
	}
	assert(deque_is_empty(d) == true);
	assert(deque_size(d) == 0);

	deque_free(d);
}

int
main(void)
{
	test_deque();

	struct deque c;

	deque_init(&c);

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

	deque_free(&c);

	return 0;
}