3 files changed, 1011 insertions, 0 deletions
diff --git a/collections/double_ended_queue/double_ended_queue.adoc b/collections/double_ended_queue/double_ended_queue.adoc
new file mode 100644
index 0000000..c5a1323
--- /dev/null
+++ b/collections/double_ended_queue/double_ended_queue.adoc
@@ -0,0 +1,527 @@
+Double Ended Queue
+==================
+Tucker Evans
+v1.0, 2020-06-10
+
+A double ended queue implemented in a circular buffer.
+
+NOTE: There is currently no way to distinquish between a failed retrieval
+(pop_front, index, back, etc.) and returning a NULL value. Keep this in mind if
+you plan on storing NULL values in the queue, there are plans to fix this in
+the future.
+
+Types
+-----
+
++deq+
+~~~~~
+This structure holds all internal information regarding a double ended queue.
+All functions (except constructors) expect a pointer to this struct as their
+first parameter.
+
+Functions
+---------
+
++deq* deq_new()+
+~~~~~~~~~~~~~~~~
+Constructs an empty double ended queue.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_new();
+----
+
+`deq* deq_with_capacity(int capacity)`
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Constructs an empty double ended queue with space for +capacity+ items.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_with_capacity(16);
+----
+
++int deq_size(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the number of elements in queue +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_new();
+assert(deq_size(queue) == 0);
+deq_push_back(queue, NULL);
+assert(deq_size(queue) == 1);
+----
+
++int deq_capacity(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the maximun number of elements in queue +self+ before the buffer needs
+to be resized.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_with_capacity(16);
+assert(deq_capacity(queue) == 16);
+----
+
++deq* deq_cp(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~
+Returns a copy of the queue +self+.
+All elements are kept in the same order however the placement in the buffer may
+change.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_with_capacity(16);
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+deq *new = deq_cp(queue);
+assert(strcmp(deq_pop_back, str2) == 0);
+assert(strcmp(deq_pop_back, str1) == 0);
+----
+
++void deq_free(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+Frees all internal memory and +self+.
+
+NOTE: All item pointers are still valid after a call to +deq_free+, deq_clear
+should be called before if they are no longer needed to avoid memory leaks.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_new();
+deq_free(queue);
+----
+
++void deq_clear(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Free all elements within queue +self+, and sets queue to empty (size 0).
+
+NOTE: Does not free internal memory of +self+ or +self+ itself, if this is desired +deq_free()+ should be called immediatly after this.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+deq_clear(queue);
+assert(deq_size(queue) == 0);
+deq_free(queue);
+----
+
++void deq_push_front(deq *self, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pushes +item+ into front of +self+. This may cause a resize of internal buffer.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_new();
+deq_push_front(queue, NULL);
+assert(deq_size(queue) == 1);
+----
+
++void deq_push_back(deq *self, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pushes +item+ into back of +self+. This may cause a resize of internal buffer.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_new();
+deq_push_back(queue, NULL);
+assert(deq_size(queue) == 1);
+----
+
++void deq_set(deq *self, int index, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Sets the element at position +index+ in +self+ to +item+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+deq_set(queue, 0, str2);
+
+assert(str_cmp(deq_pop_back(queue), str2) == 0);
+assert(str_cmp(deq_pop_back(queue), str2) == 0);
+----
+
++void deq_insert(deq *self, int index, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Inserts +item+ into queue +self+ at index +index+, all items after the index
+are pushed toward the end.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+deq_insert(queue, 1, str_dup(str3));
+
+assert(str_cmp(deq_index(queue, 1), str3) == 0);
+assert(str_cmp(deq_index(queue, 2), str2) == 0);
+----
+
++void* deq_pop_front(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pops an item off of the front of the queue +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+assert(str_cmp(deq_pop_front(queue), str1) == 0);
+assert(str_cmp(deq_pop_front(queue), str2) == 0);
+----
+
++void* deq_pop_back(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pops an item off of the back of the queue +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+assert(str_cmp(deq_pop_back(queue), str2) == 0);
+assert(str_cmp(deq_pop_back(queue), str1) == 0);
+----
+
++void* deq_index(deq *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the element at position +index+ of +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+assert(str_cmp(deq_index(queue, 1), str2) == 0);
+----
+
++void* deq_front(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the element at the front of the queue +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+assert(strcmp(deq_front(queue), str1) == 0);
+----
+
++void* deq_back(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the element at the back of the queue +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+assert(strcmp(deq_back(queue), str2) == 0);
+----
+
++void deq_swap(deq *self, int i, int j)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Swaps elements at positions +i+ and +j+, does nothing if +i+ or +j+ are out of
+bounds.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+
+deq_swap(queue, 0, 1);
+
+assert(str_cmp(deq_front(queue), str2) == 0);
+assert(str_cmp(deq_back(queue), str1) == 0);
+----
+
++void* deq_swap_rm_front(deq *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Swaps front element with item at +index+, and pops item now at front.
+Does not keep order of elements, but faster that +deq_remove()+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+assert(str_cmp(deq_swap_front(queue, 2), str3) == 0);
+assert(str_cmp(deq_front(queue, str2) == 0);
+assert(deq_size == 2);
+----
+
++void* deq_swap_rm_back(deq *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Swaps back element with item at +index+, and pops item now at back.
+Will return same element as +deq_remove(self, index)+.
+Does not keep order of elements, but faster that +deq_remove()+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+assert(str_cmp(deq_swap_rm_back(queue, 2), str3) == 0);
+assert(str_cmp(deq_back(queue, str2) == 0);
+assert(deq_size == 2);
+----
+
++void deq_truncate(deq *self, int size)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Truncates queue +self+ to +size+ elements, elements in positions > +size+ will
+no longer be accessable through +self+. Does nothing if +size+ > current number
+of elements.  NOTE: Does not currently reduce memory footprint
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+deq_truncate(queue, 1);
+
+assert(deq_size == 1);
+----
+
++void deq_reserve(deq *self, int additional)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Reserves space for +additional+ items. May reserve more memory to avoid too
+many reallocations.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+
+deq *queue = deq_with_capacity(16);
+
+deq_reserve(queue, 20);
+assert(deq_capacity(queue) >= 20);
+----
+
++void deq_remove(deq *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Element at position +index+ of +self+ is removed from queue and the remaining
+items are shifted towards the front.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+deq_remove(queue, 1);
+
+assert(deq_size == 2);
+assert(strcmp(deq_front(queue), str1) == 0);
+assert(strcmp(deq_back(queue), str3) == 0);
+----
+
++void deq_print(deq *self, (char* to_string(void*)))+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Prints out the contents of the queue +self+ to +stdout+ (surounded by square brackets and separated by commas ','). +to_string+ is a
+function that takes a pointer to the type of elements stored in +self+ and
+returns a string representation.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "double_ended_queue.h"
+#include <string.h>
+
+char* to_string(str)
+void *str;
+{
+	return str;
+}
+
+int main()
+{
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+deq *queue = deq_new();
+deq_push_back(queue, str_dup(str1));
+deq_push_back(queue, str_dup(str2));
+deq_push_back(queue, str_dup(str3));
+
+printf("DEQ CONTENTS:\n\t")
+deq_print(queue, to_string)
+}
+----
+
+Output:
+----
+DEQ_CONTENTS:
+	[ONE,TWO,THREE]
+----
diff --git a/collections/double_ended_queue/double_ended_queue.c b/collections/double_ended_queue/double_ended_queue.c
new file mode 100644
index 0000000..015b90b
--- /dev/null
+++ b/collections/double_ended_queue/double_ended_queue.c
@@ -0,0 +1,441 @@
+#include "double_ended_queue.h"
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include <stdio.h>
+
+/*Checks bounds for index (y) in queue*/
+#define DEQ_IN_BOUNDS(x, y) (y < deq_size(x)) \
+
+#define START_SIZE 64;
+
+/*TODO add returned error codes for current void functions
+ * (resize, push, etc.)
+ *
+ * Should all functions return a status code and take in a dest argument?
+ */
+
+/* Double ended queue as a circular buffer
+ * base is pointer to buffer.
+ * beg: postiton of the first element is stored.
+ * end: position for the next element to be stored.
+ * limit: the maximum number of elements.
+ */
+
+struct double_ended_queue {
+	void **base;
+	int beg, end, limit;
+};
+
+deq* deq_new()
+{
+	deq *root;
+
+	root = malloc(sizeof(deq));
+	assert(root);
+
+	root->limit = START_SIZE;
+	root->beg = root->end = 0;
+	root->base = malloc(root->limit * sizeof(void*));
+	assert(root->base);
+
+	return root;
+}
+
+deq* deq_with_capacity(n)
+int n;
+{
+	deq *root;
+
+	root = malloc(sizeof(deq));
+	assert(root);
+
+	root->limit = n;
+	root->beg = root->end = 0;
+	root->base = malloc(root->limit * sizeof(void*));
+	assert(root->base);
+
+	return root;
+}
+
+int deq_size(root)
+deq *root;
+{
+	if (!root)
+		return -1;
+
+	if (root->beg <= root->end)
+		return (root->end - root->beg);
+
+	return (root->limit - root->beg) + (root->end);
+}
+
+int deq_capacity(root)
+deq *root;
+{
+	if (!root) {
+		return -1;
+	} else {
+		return root->limit;
+	}
+}
+
+void deq_resize(root)
+deq *root;
+{
+	void **tmp;
+	int size;
+
+	tmp = malloc(root->limit * 2 * sizeof(void*));
+	assert(tmp);
+
+	if (root->beg <= root->end) {
+		tmp = memcpy(tmp, root->base + root->beg,
+				deq_size(root) * sizeof(void*));
+	} else {
+		/*copy beg<->limit*/
+		size = root->limit - root->beg;
+		tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*));
+		assert(tmp);
+
+		/*copy base<->end*/
+		tmp = memcpy(tmp + size, root->base,
+				root->end * sizeof(void*));
+		assert(tmp);
+	}
+
+	root->limit *= 2;
+
+	free(root->base);
+	root->base = tmp;
+}
+
+void* deq_index(root, index)
+deq *root;
+int index;
+{
+	void **tmp;
+
+	if (!root || !DEQ_IN_BOUNDS(root,index))
+		return NULL;
+
+	return root->base[(root->beg + index) % root->limit];
+}
+
+void deq_push_front(root, item)
+deq *root;
+void *item;
+{
+	void **tmp;
+
+	if (!root)
+		return;
+
+	if (root->end >= root->limit)
+		deq_resize(root);
+
+	--root->beg;
+	root->beg %= root->limit;
+
+	root->base[root->beg] = item;
+
+	if (root->end == root->beg)
+		root->end = root->limit;
+}
+
+void deq_push_back(root, item)
+deq *root;
+void *item;
+{
+	void **tmp;
+
+	if (!root)
+		return;
+
+	if (root->end >= root->limit)
+		deq_resize(root);
+
+	root->base[root->end++] = item;
+	root->end %= root->limit;
+
+	if (root->end == root->beg)
+		root->end = root->limit;
+}
+
+void deq_set(root, index, item)
+deq *root;
+int index;
+void *item;
+{
+	if (!root || !DEQ_IN_BOUNDS(root, index))
+		return;
+	root->base[(root->beg + index) % root->limit] = item;
+}
+
+void deq_insert(root, index, item)
+deq *root;
+int index;
+void *item;
+{
+	if (!root)
+		return;
+
+	if (index > deq_size(root))
+		return;
+
+	if (root->end >= root->limit)
+		deq_resize(root);
+
+	index = (root->beg + index) % root->limit;
+
+	if (root->beg < root->end) {
+		memmove(root->base + index + 1, root->base + index,
+				(root->end - index) * sizeof(void*));
+		++root->end;
+		root->end = root->end % root->limit;
+	} else if (index < root->end) {
+		memmove(root->base + index + 1,
+				root->base + index,
+				(root->end - index) * sizeof(void*));
+		++root->end;
+	} else {
+		memmove(root->base + root->beg - 1, root->base + root->beg,
+				(index - root->beg) * sizeof(void*));
+		--root->beg;
+	}
+
+	if (root->end == root->beg)
+		root->end = root->limit;
+
+	root->base[index] = item;
+}
+
+void* deq_pop_front(root)
+deq *root;
+{
+	void* tmp;
+	if (!root || root->beg == root->end)
+		return NULL;
+
+	tmp = root->base[root->beg];
+
+	++root->beg;
+	root->beg %= root->limit;
+
+	return tmp;
+}
+
+void* deq_pop_back(root)
+deq *root;
+{
+	if (!root || root->end == root->beg)
+		return NULL;
+
+	--root->end;
+	root->end %= root->limit;
+
+	return root->base[root->end];
+}
+
+void* deq_swap_rm_front(root, index)
+deq *root;
+int index;
+{
+	if (!root || !DEQ_IN_BOUNDS(root,index))
+		return NULL;
+
+	deq_swap(root, 0, index);
+	return deq_pop_front(root);
+}
+
+void* deq_swap_rm_back(root, index)
+deq *root;
+int index;
+{
+	if (!root || !DEQ_IN_BOUNDS(root,index))
+		return NULL;
+
+	deq_swap(root,deq_size(root) - 1,index);
+	return deq_pop_back(root);
+}
+
+void deq_swap(root, i, j)
+deq *root;
+int i, j;
+{
+	int len;
+	void *tmp;
+
+	if (!root)
+		return;
+
+	len = deq_size(root);
+
+	if (i >= len || j >= len)
+		return;
+
+	i += root->beg;
+	i %= root->limit;
+
+	j += root->beg;
+	j %= root->limit;
+
+	tmp = root->base[i];
+	root->base[i] = root->base[j];
+	root->base[j] = tmp;
+}
+
+void deq_remove(root, index)
+deq *root;
+int index;
+{
+	if (!root || !DEQ_IN_BOUNDS(root,index));
+		return;
+
+	index = (root->beg + index) % root->limit;
+
+	root->base[index] = NULL;
+
+	if (root->beg < root->end || index >= root->beg) {
+		memmove(root->base + root->beg + 1,
+				root->base + root->beg,
+				(index - root->beg) * sizeof(void*));
+		++root->beg;
+	} else {
+		memmove(root->base + index, root->base + index + 1,
+				(--root->end - index) * sizeof(void*));
+	}
+}
+
+/* Note: Elements are not freed
+ * deq_clear should be called before if they are no longer needed.
+ */
+void deq_free(root)
+deq *root;
+{
+	free(root->base);
+	root->base = NULL;
+
+	free(root);
+}
+
+void deq_clear(root)
+deq *root;
+{
+	int i, size;
+
+	size = deq_size(root);
+	for (i = 0; i < size; i++) {
+		free(deq_index(root, i));
+	}
+}
+
+void deq_print(root, to_string)
+deq *root;
+char* to_string(void*);
+{
+	int i, size;;
+
+	size = deq_size(root);
+
+	printf("[");
+	for (i = 0; i < size; i++) {
+		printf("%s,", to_string(deq_index(root, i)));
+	}
+	printf("\b]\n");
+}
+
+void deq_debug_print(root)
+deq *root;
+{
+	void **tmp;
+
+	fprintf(stderr, "VEC[b: %p, beg: %d, end:%d]:\n\t ",
+			root->base, root->beg, root->end);
+	for (tmp = root->base; tmp < root->base + root->limit; tmp++){
+		fprintf(stderr, "[%p]", *tmp);
+	}
+	fprintf(stderr, "\n");
+}
+
+deq* deq_cp(root)
+deq *root;
+{
+	deq *copy;
+
+	copy = deq_with_capacity(root->limit);
+	assert(copy->base);
+
+	copy->base = memcpy(copy->base, root->base,
+			root->limit * sizeof(void*));
+	assert(copy->base);
+
+	copy->beg = root->beg;
+	copy->end = root->end;
+
+	return copy;
+}
+
+/*Note: Does not currently reduce memory footprint*/
+void deq_truncate(root, size)
+deq *root;
+int size;
+{
+	if (!root || size > deq_size(root))
+		return;
+
+	root->end = (root->beg + size) % root->limit;
+}
+
+void* deq_front(root)
+deq *root;
+{
+	if (!root)
+		return NULL;
+
+	return root->base[root->beg];
+}
+
+void* deq_back(root)
+deq *root;
+{
+	if (!root)
+		return NULL;
+
+	return root->base[(root->end - 1) % root->limit];
+}
+
+void deq_reserve(root, size)
+deq *root;
+int size;
+{
+	void **tmp;
+	int i, cur_size;
+
+	cur_size = deq_size(root);
+	for (i = root->limit; i - cur_size < size; i*=2);
+
+	tmp = malloc(i * sizeof(void*));
+	assert(tmp);
+
+	if (root->beg <= root->end) {
+		tmp = memcpy(tmp, root->base + root->beg,
+				deq_size(root) * sizeof(void*));
+	} else {
+		/*copy beg<->limit*/
+		size = root->limit - root->beg;
+		tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*));
+		assert(tmp);
+
+		/*copy base<->end*/
+		tmp = memcpy(tmp + size, root->base,
+				root->end * sizeof(void*));
+		assert(tmp);
+	}
+
+	root->limit *= 2;
+
+	free(root->base);
+	root->base = tmp;
+}
diff --git a/collections/double_ended_queue/double_ended_queue.h b/collections/double_ended_queue/double_ended_queue.h
new file mode 100644
index 0000000..6448c8a
--- /dev/null
+++ b/collections/double_ended_queue/double_ended_queue.h
@@ -0,0 +1,43 @@
+#ifndef VECTOR_H
+#define VECTOR_H
+
+typedef struct double_ended_queue deq;
+
+/*constructors*/
+deq* deq_new();
+deq* deq_with_capacity(int);
+
+/*management*/
+int deq_size(deq*);
+int deq_capacity(deq*);
+deq* deq_cp(deq*);
+
+/* Note: Elements are not freed
+ * deq_clear should be called before if they are no longer needed.*/
+void deq_free(deq*);
+
+/*Free all elements within queue*/
+void deq_clear(deq*);
+
+/*data*/
+void deq_push_front(deq*, void*);
+void deq_push_back(deq*, void*);
+void deq_set(deq*, int, void*);
+void deq_insert(deq*, int, void*);
+void* deq_pop_front(deq*);
+void* deq_pop_back(deq*);
+void* deq_index(deq*, int);
+void* deq_front(deq*);
+void* deq_back(deq*);
+void* deq_swap_rm_front(deq*, int);
+void* deq_swap_rm_back(deq*, int);
+
+void deq_swap(deq*, int, int);
+
+/*Note: Does not currently reduce memory footprint*/
+void deq_truncate(deq*, int);
+void deq_reserve(deq*, int);
+
+void deq_remove(deq*, int);
+void deq_print(deq*, char* (void*));
+#endif