aboutsummaryrefslogtreecommitdiff
path: root/collections/double_ended_queue.adoc
diff options
context:
space:
mode:
Diffstat (limited to 'collections/double_ended_queue.adoc')
-rw-r--r--collections/double_ended_queue.adoc527
1 files changed, 0 insertions, 527 deletions
diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
deleted file mode 100644
index c5a1323..0000000
--- a/collections/double_ended_queue.adoc
+++ /dev/null
@@ -1,527 +0,0 @@
-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]
-----