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