From c38089c8246d25f64557de6cf2542b48f91ace4c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Sun, 23 Feb 2020 13:34:38 -0500
Subject: Add swap to double ended queue

---
 collections/double_ended_queue.c | 22 ++++++++++++++++++++++
 collections/double_ended_queue.h |  2 +-
 2 files changed, 23 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index ee93196..6a3a810 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -159,3 +159,25 @@ deq *root;
 	copy->beg = copy->base;
 	copy->end = copy->base + deq_size(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;
+	}
+
+	tmp = root->end[i];
+	root->end[j] = root->end[i];
+	root->end[i] = tmp;
+}
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index a5645e2..d1d687a 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -19,10 +19,10 @@ void* deq_pop_front(deq*);
 void* deq_index(deq*, int);
 void* deq_pop_back(deq*);
 
+void deq_swap(deq*, int, int);
 
 
 /*
- * swap
  * resevee
  * truncate
  * front
-- 
cgit v1.1


From 995f7838c0d47b3f4974e8bf501daf1d1f5e247f Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Sun, 23 Feb 2020 14:09:26 -0500
Subject: Add truncate function for double ended queue

---
 collections/double_ended_queue.c | 11 +++++++++++
 collections/double_ended_queue.h |  2 +-
 2 files changed, 12 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 6a3a810..1f18330 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -181,3 +181,14 @@ int i, j;
 	root->end[j] = root->end[i];
 	root->end[i] = tmp;
 }
+
+void deq_truncate(root, size)
+deq *root;
+int size;
+{
+	if ((!root) || size > deq_size(root)) {
+		return;
+	}
+
+	root->end = root->beg + size;
+}
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index d1d687a..283d9c3 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -20,11 +20,11 @@ void* deq_index(deq*, int);
 void* deq_pop_back(deq*);
 
 void deq_swap(deq*, int, int);
+void deq_truncate(deq*, int);
 
 
 /*
  * resevee
- * truncate
  * front
  * back
  * push/pop front
-- 
cgit v1.1


From 25395399f6a2822042a445fd6c812566d36dc3f9 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Sun, 23 Feb 2020 14:21:16 -0500
Subject: Add front/back access functions for double ended queue

---
 collections/double_ended_queue.c | 20 ++++++++++++++++++++
 collections/double_ended_queue.h |  8 ++++----
 2 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 1f18330..ac9c131 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -192,3 +192,23 @@ int size;
 
 	root->end = root->beg + size;
 }
+
+void* deq_front(root)
+deq *root;
+{
+	if (!root) {
+		return;
+	}
+
+	return *root->beg;
+}
+
+void* deq_back(root)
+deq *root;
+{
+	if (!root) {
+		return;
+	}
+
+	return *root->end;
+}
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index 283d9c3..226918d 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -22,13 +22,13 @@ void* deq_pop_back(deq*);
 void deq_swap(deq*, int, int);
 void deq_truncate(deq*, int);
 
+void* deq_front(deq*);
+void* deq_back(deq*);
+
 
 /*
  * resevee
- * front
- * back
- * push/pop front
- * push/pop back
+ * push back
  * swap_rm_front/back
  * insert
  * remove
-- 
cgit v1.1


From 7b4a46a736f47222937ba875c162591d50b08d72 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 25 May 2020 00:01:22 -0400
Subject: Fix typo in struct name.

---
 collections/double_ended_queue.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index ac9c131..dac22b6 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -7,7 +7,7 @@
 
 #define START_SIZE 64;
 
-struct double_ended_queeu {
+struct double_ended_queue {
 	void **base, **end, **beg;
 	int i, limit;
 };
-- 
cgit v1.1


From 8860413709853bf1daede5e2c95d502791952b7b Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 25 May 2020 00:45:51 -0400
Subject: Add push front for double ended queue.

---
 collections/double_ended_queue.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index dac22b6..967a716 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -88,6 +88,20 @@ void *item;
 	*(root->end++) = item;
 }
 
+void deq_push_front(root, item)
+deq *root;
+void *item;
+{
+	if (!root) {
+		return;
+	}
+	if (root->end == root->base + root->limit) {
+		deq_resize(root);
+	}
+
+	*(root->end++) = item;
+}
+
 void* deq_pop_front(root)
 deq *root;
 {
-- 
cgit v1.1


From 56f138f1de82d4bf7e21282f115fbcb63a6fe4d4 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 25 May 2020 00:47:06 -0400
Subject: Fix index function for double ended queue.

Double ended queue's did not account for pushing in-front of the base
i.e. a truly circular buffer, this is the start to fixing that across
all functions.
---
 collections/double_ended_queue.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 967a716..88d4641 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -117,11 +117,18 @@ void* deq_index(root, index)
 deq *root;
 int index;
 {
-	if (!root || root->beg + index >= root->end) {
+	void *tmp;
+
+	if (!root) {
+		return NULL;
+	}
+
+	tmp = root->base + (root->beg + index - root->base) % root->limit);
+	if (tmp > root->end) {
 		return NULL;
 	}
 
-	return root->beg[index];
+	return *tmp;
 }
 
 void* deq_pop_back(root)
-- 
cgit v1.1


From 6eb63be564e5d99e9ead3c10e98ab684363428f2 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 25 May 2020 01:02:43 -0400
Subject: Fix double ended queue size.

---
 collections/double_ended_queue.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 88d4641..a49b018 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -9,7 +9,7 @@
 
 struct double_ended_queue {
 	void **base, **end, **beg;
-	int i, limit;
+	int limit;
 };
 
 deq* deq_new()
@@ -47,7 +47,12 @@ deq *root;
 	if (!root) {
 		return -1;
 	}
-	return (root->end - root->beg);
+
+	if (root->beg <= root->end) {
+		return (root->end - root->beg);
+	}
+
+	return (root->base + root->limit - root->beg) + (root->end - root->base);
 }
 
 void deq_resize(root)
-- 
cgit v1.1


From 68b53a55f308d02be02130ef32038b6d707a6b55 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 25 May 2020 01:22:01 -0400
Subject: Fix double ended queue push back.

---
 collections/double_ended_queue.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index a49b018..81bee47 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -7,6 +7,10 @@
 
 #define START_SIZE 64;
 
+/*TODO add returned error codes for current void functions
+ * (resize, push, etc.)
+ */
+
 struct double_ended_queue {
 	void **base, **end, **beg;
 	int limit;
@@ -86,11 +90,14 @@ void *item;
 	if (!root) {
 		return;
 	}
-	if (root->end == root->base + root->limit) {
+
+	tmp = (root->base + (root->end - root->base) % root->limit);
+	if (tmp == root->beg) {
 		deq_resize(root);
+		tmp = (root->base + (root->end - root->base) % root->limit);
 	}
 
-	*(root->end++) = item;
+	*(root->end = tmp) = item;
 }
 
 void deq_push_front(root, item)
-- 
cgit v1.1


From c3f2eed02152d5902fa26a625d11207e64301849 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tuckerevans24@gmail.com>
Date: Tue, 26 May 2020 01:19:31 -0400
Subject: Fix push front for double ended queue.

Was only a copy of push back.
---
 collections/double_ended_queue.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 81bee47..8a6a91e 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -104,14 +104,19 @@ void deq_push_front(root, item)
 deq *root;
 void *item;
 {
+	void *tmp;
+
 	if (!root) {
 		return;
 	}
-	if (root->end == root->base + root->limit) {
+
+	tmp = (root->base + ((root->beg - 1) - root->base) % root->limit);
+	if (tmp == root->beg) {
 		deq_resize(root);
+		tmp = (root->base + ((root->beg - 1) - root->base) % root->limit);
 	}
 
-	*(root->end++) = item;
+	*(root->beg = tmp) = item;
 }
 
 void* deq_pop_front(root)
-- 
cgit v1.1


From ee17ff1921ea790125d0c4b804f3c78a1f4c0a34 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 03:32:07 -0400
Subject: Fix double ended queue pop front w/ wrap around.

---
 collections/double_ended_queue.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 8a6a91e..285983b 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -127,7 +127,10 @@ deq *root;
 		return NULL;
 	}
 
-	return tmp = *(root->beg++);
+	tmp = *(root->beg++);
+	root->beg = (root->base + (root->beg - root->base) % root->limit);
+
+	return tmp;
 }
 
 void* deq_index(root, index)
-- 
cgit v1.1


From 0b8aa4ce92c042eabb3ebed94674aa6dc099a23c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 03:34:37 -0400
Subject: Fix move index function for double ended queue.

---
 collections/double_ended_queue.c | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 285983b..25167e3 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -83,6 +83,24 @@ deq *root;
 	}
 }
 
+void* deq_index(root, index)
+deq *root;
+int index;
+{
+	void *tmp;
+
+	if (!root) {
+		return NULL;
+	}
+
+	tmp = root->base + (root->beg + index - root->base) % root->limit);
+	if (tmp > root->end) {
+		return NULL;
+	}
+
+	return *tmp;
+}
+
 void deq_push_back(root, item)
 deq *root;
 void *item;
@@ -133,24 +151,6 @@ deq *root;
 	return tmp;
 }
 
-void* deq_index(root, index)
-deq *root;
-int index;
-{
-	void *tmp;
-
-	if (!root) {
-		return NULL;
-	}
-
-	tmp = root->base + (root->beg + index - root->base) % root->limit);
-	if (tmp > root->end) {
-		return NULL;
-	}
-
-	return *tmp;
-}
-
 void* deq_pop_back(root)
 deq *root;
 {
-- 
cgit v1.1


From df2e0f59747d55ffd6fd47468d098aab1e9abfbe Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 03:39:03 -0400
Subject: Fix double ended queue pop back w/ wrap around.

---
 collections/double_ended_queue.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 25167e3..31ede5f 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -159,7 +159,10 @@ deq *root;
 		return NULL;
 	}
 
-	return tmp = *(--root->end);
+	tmp = *(root->end--);
+	root->end = (root->base + (root->end - root->base) % root->limit);
+
+	return tmp;
 }
 
 void deq_free(root)
-- 
cgit v1.1


From a89e4d56a242073982ca3620a00c6e04bf5e82d8 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 04:05:57 -0400
Subject: Fix trivial compiler errors.

---
 collections/double_ended_queue.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 31ede5f..fab92c7 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -87,13 +87,13 @@ void* deq_index(root, index)
 deq *root;
 int index;
 {
-	void *tmp;
+	void **tmp;
 
 	if (!root) {
 		return NULL;
 	}
 
-	tmp = root->base + (root->beg + index - root->base) % root->limit);
+	tmp = root->base + ((root->beg + index - root->base) % root->limit);
 	if (tmp > root->end) {
 		return NULL;
 	}
@@ -105,6 +105,8 @@ void deq_push_back(root, item)
 deq *root;
 void *item;
 {
+	void **tmp;
+
 	if (!root) {
 		return;
 	}
@@ -122,7 +124,7 @@ void deq_push_front(root, item)
 deq *root;
 void *item;
 {
-	void *tmp;
+	void **tmp;
 
 	if (!root) {
 		return;
@@ -241,7 +243,7 @@ void* deq_front(root)
 deq *root;
 {
 	if (!root) {
-		return;
+		return NULL;
 	}
 
 	return *root->beg;
@@ -251,7 +253,7 @@ void* deq_back(root)
 deq *root;
 {
 	if (!root) {
-		return;
+		return NULL;
 	}
 
 	return *root->end;
-- 
cgit v1.1


From 533d7755f866257c78299561b2634a3ea54f9a87 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 04:26:00 -0400
Subject: Add print function for double ended queue.

Moves original print to debug_print.
---
 collections/double_ended_queue.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index fab92c7..29c8873 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -178,7 +178,22 @@ deq *root;
 	free(root);
 }
 
-void deq_print(root)
+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;
-- 
cgit v1.1


From 735a88c02286a01c2a4edb8f7f6ccf0a93de24b0 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 04:39:59 -0400
Subject: Add brief description of double ended queue struct.

---
 collections/double_ended_queue.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 29c8873..25f3181 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -11,6 +11,17 @@
  * (resize, push, etc.)
  */
 
+/*TODO
+ * Fix empty vs totally full ambiquity
+ */
+
+/* Double ended queue as a circular buffer
+ * base is pointer to buffer.
+ * beg is where the first element is stored.
+ * end is where the last element is stored.
+ * limit is the maximum number of elements.
+ */
+
 struct double_ended_queue {
 	void **base, **end, **beg;
 	int limit;
-- 
cgit v1.1


From dbb5ba792719088f99b58a954a53b1cdab213f0c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 27 May 2020 04:41:40 -0400
Subject: Fix resize implementation (double ended queue).

Needed to take into account circular buffer i.e. handle a split buffer
(base<->end & beg<->limit) along with regular (beg<->end).
---
 collections/double_ended_queue.c | 35 +++++++++++++++++++++--------------
 1 file changed, 21 insertions(+), 14 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 25f3181..b555e3a 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -73,25 +73,32 @@ deq *root;
 void deq_resize(root)
 deq *root;
 {
-	if (root->beg != root->base) {
-		memmove(root->base, root->beg, root->end - root->beg);
-		root->end = root->base + deq_size(root);
-		root->beg = root->base;
-	} else {
-		root->base = malloc(root->limit * 2 * sizeof(void*));
-		assert(root->base);
+	void **tmp;
+	int size;
 
+	tmp = malloc(root->limit * 2 * sizeof(void*));
+	assert(root->base);
 
-		root->base = memcpy(root->base, root->beg, root->limit * sizeof(void*));
-		assert(root->base);
+	if (root->beg > root->end) {
+		/*copy beg<->limit*/
+		size = (root->base + (root->limit*sizeof(void*)) - root->beg);
+		tmp = memcpy(tmp, root->beg, size * sizeof(void*);
+		assert(tmp);
 
+		/*copy base<->end*/
+		tmp = memcpy(tmp + size, root->beg,
+			(root->end - root->base)* sizeof(void*));
+		assert(tmp);
+	} else {
+		size = deq_size(root);
+		tmp = memcpy(tmp, root->beg, size*sizeof(void*));
+	}
 
-		root->end = root->base + deq_size(root);
-		root->limit = root->limit * 2;
+	root->limit *= 2;
 
-		free(root->beg);
-		root->beg = root->base;
-	}
+	free(root->base);
+	root->base = root->beg = tmp;
+	root->end = root->base + size;
 }
 
 void* deq_index(root, index)
-- 
cgit v1.1


From 4e4704b0251bb2b03d0fa573437b77b15567441c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Fri, 29 May 2020 17:15:53 -0400
Subject: Fix change beg, end to indices.

These are now indices of the buffer rather than pointers into buffer,
as this is simpler to maintain and extend.
end is also changed to point to next location for storage rather than
the last element.
---
 collections/double_ended_queue.c | 154 ++++++++++++++++++++-------------------
 1 file changed, 78 insertions(+), 76 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index b555e3a..956e362 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -17,14 +17,14 @@
 
 /* Double ended queue as a circular buffer
  * base is pointer to buffer.
- * beg is where the first element is stored.
- * end is where the last element is stored.
- * limit is the maximum number of elements.
+ * 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, **end, **beg;
-	int limit;
+	void **base;
+	int beg, end, limit;
 };
 
 deq* deq_new()
@@ -35,7 +35,8 @@ deq* deq_new()
 	assert(root);
 
 	root->limit = START_SIZE;
-	root->base = root->end = root->beg = malloc(root->limit * sizeof(void*));
+	root->beg = root->end = 0;
+	root->base = malloc(root->limit * sizeof(void*));
 	assert(root->base);
 
 	return root;
@@ -50,7 +51,8 @@ int n;
 	assert(root);
 
 	root->limit = n;
-	root->base = root->end = root->beg = malloc(root->limit * sizeof(void*));
+	root->beg = root->end = 0;
+	root->base = malloc(root->limit * sizeof(void*));
 	assert(root->base);
 
 	return root;
@@ -59,15 +61,13 @@ int n;
 int deq_size(root)
 deq *root;
 {
-	if (!root) {
+	if (!root)
 		return -1;
-	}
 
-	if (root->beg <= root->end) {
+	if (root->beg <= root->end)
 		return (root->end - root->beg);
-	}
 
-	return (root->base + root->limit - root->beg) + (root->end - root->base);
+	return (root->limit - root->beg) + (root->end);
 }
 
 void deq_resize(root)
@@ -79,26 +79,25 @@ deq *root;
 	tmp = malloc(root->limit * 2 * sizeof(void*));
 	assert(root->base);
 
-	if (root->beg > root->end) {
+	if (root->beg <= root->end) {
+		tmp = memcpy(tmp, root->base + root->beg,
+				deq_size(root) * sizeof(void*));
+	} else {
 		/*copy beg<->limit*/
-		size = (root->base + (root->limit*sizeof(void*)) - root->beg);
-		tmp = memcpy(tmp, root->beg, size * sizeof(void*);
+		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->beg,
-			(root->end - root->base)* sizeof(void*));
+		tmp = memcpy(tmp + size, root->base,
+				root->end * sizeof(void*));
 		assert(tmp);
-	} else {
-		size = deq_size(root);
-		tmp = memcpy(tmp, root->beg, size*sizeof(void*));
 	}
 
 	root->limit *= 2;
 
 	free(root->base);
-	root->base = root->beg = tmp;
-	root->end = root->base + size;
+	root->base = tmp;
 }
 
 void* deq_index(root, index)
@@ -107,16 +106,15 @@ int index;
 {
 	void **tmp;
 
-	if (!root) {
+	if (!root || index > root->limit
+			|| (index >= root->end && index < root->beg))
 		return NULL;
-	}
 
-	tmp = root->base + ((root->beg + index - root->base) % root->limit);
-	if (tmp > root->end) {
+	index = (root->beg + index) % root->limit;
+	if (index >= root->end)
 		return NULL;
-	}
 
-	return *tmp;
+	return root->base[index];
 }
 
 void deq_push_back(root, item)
@@ -125,17 +123,17 @@ void *item;
 {
 	void **tmp;
 
-	if (!root) {
+	if (!root)
 		return;
-	}
 
-	tmp = (root->base + (root->end - root->base) % root->limit);
-	if (tmp == root->beg) {
+	if (root->end >= root->limit)
 		deq_resize(root);
-		tmp = (root->base + (root->end - root->base) % root->limit);
-	}
 
-	*(root->end = tmp) = item;
+	root->base[root->end++] = item;
+	root->end %= root->limit;
+
+	if (root->end == root->beg)
+		root->end = root->limit;
 }
 
 void deq_push_front(root, item)
@@ -144,29 +142,32 @@ void *item;
 {
 	void **tmp;
 
-	if (!root) {
+	if (!root)
 		return;
-	}
 
-	tmp = (root->base + ((root->beg - 1) - root->base) % root->limit);
-	if (tmp == root->beg) {
+	if (root->end >= root->limit)
 		deq_resize(root);
-		tmp = (root->base + ((root->beg - 1) - root->base) % root->limit);
-	}
 
-	*(root->beg = tmp) = item;
+	--root->beg;
+	root->beg %= root->limit;
+
+	root->base[root->beg] = item;
+
+	if (root->end == root->beg)
+		root->end = root->limit;
 }
 
 void* deq_pop_front(root)
 deq *root;
 {
 	void* tmp;
-	if (!root || root->beg == root->end) {
+	if (!root || root->beg == root->end)
 		return NULL;
-	}
 
-	tmp = *(root->beg++);
-	root->beg = (root->base + (root->beg - root->base) % root->limit);
+	tmp = root->base[root->beg];
+
+	++root->beg;
+	root->beg %= root->limit;
 
 	return tmp;
 }
@@ -174,15 +175,13 @@ deq *root;
 void* deq_pop_back(root)
 deq *root;
 {
-	void* tmp;
-	if (!root || root->end == root->beg) {
+	if (!root || root->end == root->beg)
 		return NULL;
-	}
 
-	tmp = *(root->end--);
-	root->end = (root->base + (root->end - root->base) % root->limit);
+	--root->end;
+	root->end %= root->limit;
 
-	return tmp;
+	return root->base[root->end];
 }
 
 void deq_free(root)
@@ -190,8 +189,6 @@ deq *root;
 {
 	free(root->base);
 	root->base = NULL;
-	root->end = NULL;
-	root->beg = NULL;
 
 	free(root);
 }
@@ -216,9 +213,9 @@ deq *root;
 {
 	void **tmp;
 
-	fprintf(stderr, "VEC[b: %p, p: %p, n:%p]:\n\t ",
+	fprintf(stderr, "VEC[b: %p, beg: %d, end:%d]:\n\t ",
 			root->base, root->beg, root->end);
-	for (tmp = root->beg; tmp < root->end; tmp++){
+	for (tmp = root->base; tmp < root->base + root->limit; tmp++){
 		fprintf(stderr, "[%p]", *tmp);
 	}
 	fprintf(stderr, "\n");
@@ -230,13 +227,16 @@ deq *root;
 	deq *copy;
 
 	copy = deq_with_capacity(root->limit);
+	assert(copy->base);
 
-	copy->base = memcpy(copy->base, root->beg,
-			deq_size(root) * sizeof(void*));
+	copy->base = memcpy(copy->base, root->base,
+			root->limit * sizeof(void*));
 	assert(copy->base);
 
-	copy->beg = copy->base;
-	copy->end = copy->base + deq_size(root);
+	copy->beg = root->beg;
+	copy->end = root->end;
+
+	return copy;
 }
 
 void deq_swap(root, i, j)
@@ -246,48 +246,50 @@ int i, j;
 	int len;
 	void *tmp;
 
-	if (!root) {
+	if (!root)
 		return;
-	}
 
 	len = deq_size(root);
 
-	if (i >= len || j >= len) {
+	if (i >= len || j >= len)
 		return;
-	}
 
-	tmp = root->end[i];
-	root->end[j] = root->end[i];
-	root->end[i] = tmp;
+	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;
 }
 
+/*Note: Does not currently reduce memory footprint*/
 void deq_truncate(root, size)
 deq *root;
 int size;
 {
-	if ((!root) || size > deq_size(root)) {
+	if (!root || size > deq_size(root))
 		return;
-	}
 
-	root->end = root->beg + size;
+	root->end = (root->beg + size) % root->limit;
 }
 
 void* deq_front(root)
 deq *root;
 {
-	if (!root) {
+	if (!root)
 		return NULL;
-	}
 
-	return *root->beg;
+	return root->base[root->beg];
 }
 
 void* deq_back(root)
 deq *root;
 {
-	if (!root) {
+	if (!root)
 		return NULL;
-	}
 
-	return *root->end;
+	return root->base[(root->end - 1) % root->limit];
 }
-- 
cgit v1.1


From 10cd9eadf3f14d4b25ef85ea563938a784fcf20c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Sat, 30 May 2020 20:11:45 -0400
Subject: Add deq_clear function for double ended queue.

Frees all elements in double ended queue, does not free the queue struct
itself (deq_free is used for this).
---
 collections/double_ended_queue.c | 14 ++++++++++++++
 collections/double_ended_queue.h |  8 ++++++++
 2 files changed, 22 insertions(+)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 956e362..7938307 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -184,6 +184,9 @@ deq *root;
 	return root->base[root->end];
 }
 
+/* Note: Elements are not freed
+ * deq_clear should be called before if they are no longer needed.
+ */
 void deq_free(root)
 deq *root;
 {
@@ -193,6 +196,17 @@ deq *root;
 	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*);
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index 226918d..7f11f66 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -11,8 +11,14 @@ deq* deq_with_capacity(int);
 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()
+
 /*data*/
 void deq_push_back(deq*, void*);
 void* deq_pop_front(deq*);
@@ -20,6 +26,8 @@ void* deq_index(deq*, int);
 void* deq_pop_back(deq*);
 
 void deq_swap(deq*, int, int);
+
+/*Note: Does not currently reduce memory footprint*/
 void deq_truncate(deq*, int);
 
 void* deq_front(deq*);
-- 
cgit v1.1


From b93a7b87b55a42ca864325ae91328a5627885471 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Sat, 30 May 2020 20:35:05 -0400
Subject: Add remove index function for double ended queue.

---
 collections/double_ended_queue.c | 26 ++++++++++++++++++++++++++
 collections/double_ended_queue.h |  3 ++-
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 7938307..0348cfa 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -184,6 +184,32 @@ deq *root;
 	return root->base[root->end];
 }
 
+void deq_remove(root, index)
+deq *root;
+int index;
+{
+	if (!root || index > root->limit
+			|| (index >= root->end && index < root->beg))
+		return;
+
+	index = (root->beg + index) % root->limit;
+	if (index >= root->end)
+		return NULL;
+
+	root->base[index] = NULL;
+
+	if (root->beg < root->end || index >= root->beg) {
+		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.
  */
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index 7f11f66..bfc9d20 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -33,12 +33,13 @@ void deq_truncate(deq*, int);
 void* deq_front(deq*);
 void* deq_back(deq*);
 
+void remove(deq*, int);
+
 
 /*
  * resevee
  * push back
  * swap_rm_front/back
  * insert
- * remove
  */
 #endif
-- 
cgit v1.1


From 7e3a4d7bd009df8975f5ef374f979da7405fd501 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 8 Jun 2020 22:14:02 -0400
Subject: Fix trivial compiler errors.

---
 collections/double_ended_queue.c | 4 ++--
 collections/double_ended_queue.h | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 0348cfa..a8daf92 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -194,12 +194,12 @@ int index;
 
 	index = (root->beg + index) % root->limit;
 	if (index >= root->end)
-		return NULL;
+		return;
 
 	root->base[index] = NULL;
 
 	if (root->beg < root->end || index >= root->beg) {
-		root->beg = memmove(root->base + root->beg + 1,
+		memmove(root->base + root->beg + 1,
 				root->base + root->beg,
 				(index - root->beg) * sizeof(void*));
 		++root->beg;
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index bfc9d20..b708624 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -17,7 +17,7 @@ deq* deq_cp(deq*);
 void deq_free(deq*);
 
 /*Free all elements within queue*/
-void deq_clear()
+void deq_clear();
 
 /*data*/
 void deq_push_back(deq*, void*);
@@ -33,7 +33,7 @@ void deq_truncate(deq*, int);
 void* deq_front(deq*);
 void* deq_back(deq*);
 
-void remove(deq*, int);
+void deq_remove(deq*, int);
 
 
 /*
-- 
cgit v1.1


From f4ce6540cfaf754ab4f0a6d4b8ed6b38c0cbe956 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 8 Jun 2020 22:25:24 -0400
Subject: Add double ended queue swap remove front/back functions.

---
 collections/double_ended_queue.c | 16 ++++++++++++++++
 collections/double_ended_queue.h |  5 +++--
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index a8daf92..169693d 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -184,6 +184,22 @@ deq *root;
 	return root->base[root->end];
 }
 
+void* deq_swap_rm_front(root, index)
+deq *root;
+int index;
+{
+	deq_swap(root, 0, index);
+	return deq_pop_front(root);
+}
+
+void* deq_swap_rm_back(root, index)
+deq *root;
+int index;
+{
+	deq_swap(root,deq_size(root) - 1,index);
+	return deq_pop_back(root);
+}
+
 void deq_remove(root, index)
 deq *root;
 int index;
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index b708624..877503d 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -27,6 +27,9 @@ void* deq_pop_back(deq*);
 
 void deq_swap(deq*, int, int);
 
+void* deq_swap_rm_front(deq*, int);
+void* deq_swap_rm_back(deq*, int);
+
 /*Note: Does not currently reduce memory footprint*/
 void deq_truncate(deq*, int);
 
@@ -38,8 +41,6 @@ void deq_remove(deq*, int);
 
 /*
  * resevee
- * push back
- * swap_rm_front/back
  * insert
  */
 #endif
-- 
cgit v1.1


From 92b0bac22ab3f3feeb48feb013753961581c7615 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Mon, 8 Jun 2020 22:59:05 -0400
Subject: Fix bounds checking for deq remove.

Bounds checking is now down after index is converted to a position in
base array.

Removed TODO comment was handled in previous commit
(SHA: 4e4704b0251bb2b03d0fa573437b77b15567441c).
---
 collections/double_ended_queue.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 169693d..e06ba36 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -11,10 +11,6 @@
  * (resize, push, etc.)
  */
 
-/*TODO
- * Fix empty vs totally full ambiquity
- */
-
 /* Double ended queue as a circular buffer
  * base is pointer to buffer.
  * beg: postiton of the first element is stored.
@@ -204,12 +200,14 @@ void deq_remove(root, index)
 deq *root;
 int index;
 {
-	if (!root || index > root->limit
-			|| (index >= root->end && index < root->beg))
+	if (!root || index > root->limit)
 		return;
 
 	index = (root->beg + index) % root->limit;
-	if (index >= root->end)
+
+	/*Bounds check*/
+	if ((root->beg <= root->end && index < root->beg || index >= root->end)
+			|| (index >= root->end && index < root->beg))
 		return;
 
 	root->base[index] = NULL;
@@ -223,7 +221,6 @@ int index;
 		memmove(root->base + index, root->base + index + 1,
 				(--root->end - index) * sizeof(void*));
 	}
-
 }
 
 /* Note: Elements are not freed
-- 
cgit v1.1


From fb65c9cc91fe5bcf75e1519bd73d31242fbccb9d Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 12:34:11 -0400
Subject: Add bounds checking macro for double ended queue.

---
 collections/double_ended_queue.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index e06ba36..f8f59e4 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -5,10 +5,15 @@
 
 #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
@@ -184,6 +189,9 @@ 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);
 }
@@ -192,6 +200,9 @@ 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);
 }
@@ -200,16 +211,11 @@ void deq_remove(root, index)
 deq *root;
 int index;
 {
-	if (!root || index > root->limit)
+	if (!root || !DEQ_IN_BOUNDS(root,index));
 		return;
 
 	index = (root->beg + index) % root->limit;
 
-	/*Bounds check*/
-	if ((root->beg <= root->end && index < root->beg || index >= root->end)
-			|| (index >= root->end && index < root->beg))
-		return;
-
 	root->base[index] = NULL;
 
 	if (root->beg < root->end || index >= root->beg) {
-- 
cgit v1.1


From ce6d7f43e7ad77b3eec043ff731d17ab21e89e87 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 12:51:52 -0400
Subject: Fix double ended queue index  to use bounds check.

---
 collections/double_ended_queue.c | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index f8f59e4..e737d28 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -107,15 +107,10 @@ int index;
 {
 	void **tmp;
 
-	if (!root || index > root->limit
-			|| (index >= root->end && index < root->beg))
-		return NULL;
-
-	index = (root->beg + index) % root->limit;
-	if (index >= root->end)
+	if (!root || !DEQ_IN_BOUNDS(root,index))
 		return NULL;
 
-	return root->base[index];
+	return root->base[(root->beg + index) % root->limit];
 }
 
 void deq_push_back(root, item)
-- 
cgit v1.1


From b38bcd56356973a50797630f8366d6701dd7c988 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 12:55:33 -0400
Subject: Add set index function for double ended queue.

---
 collections/double_ended_queue.c | 10 ++++++++++
 collections/double_ended_queue.h |  3 ++-
 2 files changed, 12 insertions(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index e737d28..232fb44 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -101,6 +101,16 @@ deq *root;
 	root->base = tmp;
 }
 
+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_index(root, index)
 deq *root;
 int index;
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index 877503d..332b16f 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -22,8 +22,9 @@ void deq_clear();
 /*data*/
 void deq_push_back(deq*, void*);
 void* deq_pop_front(deq*);
-void* deq_index(deq*, int);
 void* deq_pop_back(deq*);
+void deq_set(deq*, int, void*);
+void* deq_index(deq*, int);
 
 void deq_swap(deq*, int, int);
 
-- 
cgit v1.1


From 6dce1b32a4e19c875131cdbb441cca0ca23f73f5 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 18:09:48 -0400
Subject: Add capacity function to double ended queue.

---
 collections/double_ended_queue.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 232fb44..7857c3a 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -71,6 +71,16 @@ deq *root;
 	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;
 {
-- 
cgit v1.1


From 282a63e054231481fd2107d78cb36f79cdf8867c Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 18:10:13 -0400
Subject: Fix update double ended queue header to match implementation.

---
 collections/double_ended_queue.h | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index 332b16f..dd476af 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -17,15 +17,19 @@ deq* deq_cp(deq*);
 void deq_free(deq*);
 
 /*Free all elements within queue*/
-void deq_clear();
+void deq_clear(deq*);
 
 /*data*/
+void deq_push_front(deq*, void*);
 void deq_push_back(deq*, void*);
 void* deq_pop_front(deq*);
 void* deq_pop_back(deq*);
 void deq_set(deq*, int, void*);
 void* deq_index(deq*, int);
 
+void* deq_front(deq*);
+void* deq_back(deq*);
+
 void deq_swap(deq*, int, int);
 
 void* deq_swap_rm_front(deq*, int);
@@ -34,13 +38,13 @@ void* deq_swap_rm_back(deq*, int);
 /*Note: Does not currently reduce memory footprint*/
 void deq_truncate(deq*, int);
 
-void* deq_front(deq*);
-void* deq_back(deq*);
 
 void deq_remove(deq*, int);
 
+void deq_print(deq*, char* (void*));
+
 
-/*
+/*TODO
  * resevee
  * insert
  */
-- 
cgit v1.1


From fcf2831e9151e87f3feed9827ce56a39c9256804 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 18:10:50 -0400
Subject: Add documentation for double ended queue.

---
 collections/double_ended_queue.adoc | 484 ++++++++++++++++++++++++++++++++++++
 1 file changed, 484 insertions(+)
 create mode 100644 collections/double_ended_queue.adoc

diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
new file mode 100644
index 0000000..00c6dad
--- /dev/null
+++ b/collections/double_ended_queue.adoc
@@ -0,0 +1,484 @@
+Double Ended Queue
+==================
+Tucker Evans
+v0.1, 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_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_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_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_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]
+----
-- 
cgit v1.1


From 0f7085dedd2f60f2ccc0b1f49558f5be89de97b2 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 23:23:52 -0400
Subject: Fix change order of functions in double ended queue.

Groups functions that return items together.
---
 collections/double_ended_queue.adoc | 32 +++++++-------
 collections/double_ended_queue.c    | 88 ++++++++++++++++++-------------------
 collections/double_ended_queue.h    | 10 ++---
 3 files changed, 63 insertions(+), 67 deletions(-)

diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
index 00c6dad..f583df3 100644
--- a/collections/double_ended_queue.adoc
+++ b/collections/double_ended_queue.adoc
@@ -176,9 +176,9 @@ deq_push_back(queue, NULL);
 assert(deq_size(queue) == 1);
 ----
 
-+void* deq_pop_front(deq *self)+
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Pops an item off of the front of the queue +self+.
++void deq_set(deq *self, int index, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Sets the element at position +index+ in +self+ to +item+.
 
 Examples
 ^^^^^^^^
@@ -194,13 +194,15 @@ 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);
+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_pop_back(deq *self)+
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Pops an item off of the back of the queue +self+.
++void* deq_pop_front(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pops an item off of the front of the queue +self+.
 
 Examples
 ^^^^^^^^
@@ -216,13 +218,13 @@ 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);
+assert(str_cmp(deq_pop_front(queue), str1) == 0);
+assert(str_cmp(deq_pop_front(queue), str2) == 0);
 ----
 
-+void deq_set(deq *self, int index, void *item)+
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Sets the element at position +index+ in +self+ to +item+.
++void* deq_pop_back(deq *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pops an item off of the back of the queue +self+.
 
 Examples
 ^^^^^^^^
@@ -238,10 +240,8 @@ 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);
+assert(str_cmp(deq_pop_back(queue), str1) == 0);
 ----
 
 +void* deq_index(deq *self, int index)+
diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 7857c3a..bf329ca 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -111,16 +111,6 @@ deq *root;
 	root->base = tmp;
 }
 
-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_index(root, index)
 deq *root;
 int index;
@@ -133,7 +123,7 @@ int index;
 	return root->base[(root->beg + index) % root->limit];
 }
 
-void deq_push_back(root, item)
+void deq_push_front(root, item)
 deq *root;
 void *item;
 {
@@ -145,14 +135,16 @@ void *item;
 	if (root->end >= root->limit)
 		deq_resize(root);
 
-	root->base[root->end++] = item;
-	root->end %= root->limit;
+	--root->beg;
+	root->beg %= root->limit;
+
+	root->base[root->beg] = item;
 
 	if (root->end == root->beg)
 		root->end = root->limit;
 }
 
-void deq_push_front(root, item)
+void deq_push_back(root, item)
 deq *root;
 void *item;
 {
@@ -164,15 +156,23 @@ void *item;
 	if (root->end >= root->limit)
 		deq_resize(root);
 
-	--root->beg;
-	root->beg %= root->limit;
-
-	root->base[root->beg] = item;
+	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_pop_front(root)
 deq *root;
 {
@@ -222,6 +222,32 @@ int 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;
@@ -313,32 +339,6 @@ deq *root;
 	return copy;
 }
 
-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;
-}
-
 /*Note: Does not currently reduce memory footprint*/
 void deq_truncate(root, size)
 deq *root;
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index dd476af..fac2231 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -22,25 +22,21 @@ 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_pop_front(deq*);
 void* deq_pop_back(deq*);
-void deq_set(deq*, int, void*);
 void* deq_index(deq*, int);
-
 void* deq_front(deq*);
 void* deq_back(deq*);
-
-void deq_swap(deq*, int, int);
-
 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_remove(deq*, int);
-
 void deq_print(deq*, char* (void*));
 
 
-- 
cgit v1.1


From 277e14127bbe1a5080a2a88b6ee3ef94859bc3a5 Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Wed, 10 Jun 2020 23:37:15 -0400
Subject: Add insert function to double ended queue.

---
 collections/double_ended_queue.adoc | 28 ++++++++++++++++++++++++++-
 collections/double_ended_queue.c    | 38 +++++++++++++++++++++++++++++++++++++
 collections/double_ended_queue.h    |  2 +-
 3 files changed, 66 insertions(+), 2 deletions(-)

diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
index f583df3..70cbbaf 100644
--- a/collections/double_ended_queue.adoc
+++ b/collections/double_ended_queue.adoc
@@ -1,7 +1,7 @@
 Double Ended Queue
 ==================
 Tucker Evans
-v0.1, 2020-06-10
+v0.2, 2020-06-10
 
 A double ended queue implemented in a circular buffer.
 
@@ -200,6 +200,32 @@ 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+.
diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index bf329ca..4de6a27 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -173,6 +173,44 @@ void *item;
 	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;
 {
diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h
index fac2231..c45b11b 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -23,6 +23,7 @@ void deq_clear(deq*);
 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);
@@ -42,6 +43,5 @@ void deq_print(deq*, char* (void*));
 
 /*TODO
  * resevee
- * insert
  */
 #endif
-- 
cgit v1.1


From 349c75c16a3713ee6f3ffd701f1c88ce31ecd8de Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Thu, 11 Jun 2020 14:42:06 -0400
Subject: Add reserve function for double ended queue.

---
 collections/double_ended_queue.adoc | 19 ++++++++++++++++++-
 collections/double_ended_queue.c    | 36 +++++++++++++++++++++++++++++++++++-
 collections/double_ended_queue.h    |  6 +-----
 3 files changed, 54 insertions(+), 7 deletions(-)

diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
index 70cbbaf..9ecf9cb 100644
--- a/collections/double_ended_queue.adoc
+++ b/collections/double_ended_queue.adoc
@@ -1,7 +1,7 @@
 Double Ended Queue
 ==================
 Tucker Evans
-v0.2, 2020-06-10
+v0.3, 2020-06-10
 
 A double ended queue implemented in a circular buffer.
 
@@ -440,6 +440,23 @@ 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
diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 4de6a27..015b90b 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -88,7 +88,7 @@ deq *root;
 	int size;
 
 	tmp = malloc(root->limit * 2 * sizeof(void*));
-	assert(root->base);
+	assert(tmp);
 
 	if (root->beg <= root->end) {
 		tmp = memcpy(tmp, root->base + root->beg,
@@ -405,3 +405,37 @@ deq *root;
 
 	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.h b/collections/double_ended_queue.h
index c45b11b..6448c8a 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -36,12 +36,8 @@ 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*));
-
-
-/*TODO
- * resevee
- */
 #endif
-- 
cgit v1.1


From d904ea42acf2a4c03ee7dfb0f172d6deb1fd857f Mon Sep 17 00:00:00 2001
From: Tucker Evans <tucker@tuckerevans.com>
Date: Thu, 11 Jun 2020 15:03:27 -0400
Subject: Finish initial implementation of double ended queue.

---
 collections/double_ended_queue.adoc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
index 9ecf9cb..c5a1323 100644
--- a/collections/double_ended_queue.adoc
+++ b/collections/double_ended_queue.adoc
@@ -1,7 +1,7 @@
 Double Ended Queue
 ==================
 Tucker Evans
-v0.3, 2020-06-10
+v1.0, 2020-06-10
 
 A double ended queue implemented in a circular buffer.
 
-- 
cgit v1.1