From fcf2831e9151e87f3feed9827ce56a39c9256804 Mon Sep 17 00:00:00 2001 From: Tucker Evans 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 (limited to '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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 + +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 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 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) (limited to 'collections/double_ended_queue.adoc') 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)+ -- cgit v1.1 From 277e14127bbe1a5080a2a88b6ee3ef94859bc3a5 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 10 Jun 2020 23:37:15 -0400 Subject: Add insert function to double ended queue. --- collections/double_ended_queue.adoc | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) (limited to 'collections/double_ended_queue.adoc') 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 + +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+. -- cgit v1.1 From 349c75c16a3713ee6f3ffd701f1c88ce31ecd8de Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 11 Jun 2020 14:42:06 -0400 Subject: Add reserve function for double ended queue. --- collections/double_ended_queue.adoc | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) (limited to 'collections/double_ended_queue.adoc') 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 -- cgit v1.1 From d904ea42acf2a4c03ee7dfb0f172d6deb1fd857f Mon Sep 17 00:00:00 2001 From: Tucker Evans 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(-) (limited to 'collections/double_ended_queue.adoc') 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