Double Ended Queue
==================
Tucker Evans
v1.0.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_new]]
+deq* deq_new()+
~~~~~~~~~~~~~~~~
Constructs an empty double ended queue.

Examples
^^^^^^^^
[source,c]
----
#include "double_ended_queue.h"

deq *queue = deq_new();
----

[[deq_with_capacity]]
`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);
----

[[deq_size]]
+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);
----

[[deq_capacity]]
+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_cp]]
+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);
----

[[deq_free]]
+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_free()+>>, <<deq_clear,+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);
----

[[deq_clear]]
+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,+deq_free()+>> should be called immediately 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);
----

[[deq_push_front]]
+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);
----

[[deq_push_back]]
+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);
----

[[deq_set]]
+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);
----

[[deq_insert]]
+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);
----

[[deq_pop_front]]
+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);
----

[[deq_pop_back]]
+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);
----

[[deq_index]]
+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);
----

[[deq_front]]
+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);
----

[[deq_back]]
+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);
----

[[deq_swap]]
+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);
----

[[deq_swap_rm_front]]
+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,+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);
----

[[deq_swap_rm_back]]
+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,+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);
----

[[deq_truncate]]
+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);
----

[[deq_reserve]]
+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);
----

[[deq_remove]]
+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);
----

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