Add documentation for double ended queue.

1 files changed, 484 insertions, 0 deletions

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]
+----