diff options
Diffstat (limited to 'collections/double_ended_queue.adoc')
| -rw-r--r-- | collections/double_ended_queue.adoc | 527 |
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] ----- |