Double Ended Queue ================== Tucker Evans v1.0.2, 2020-07-06 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 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_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. NOTE: Strings are freed after printing, therefore +strdup()+ should be used on any strings that are not for the sole purpose of printing here. Examples ^^^^^^^^ [source,c] ---- #include "double_ended_queue.h" #include char* to_string(str) void *str; { return strdup(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] ---- [[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_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 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 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_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 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 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_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 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_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 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_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 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_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 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_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 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 <>. 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); ---- [[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 <>. 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); ---- [[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 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_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 <> should be called immediately 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); ---- [[deq_free]] +void deq_free(deq *self)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~ Frees all internal memory and +self+. NOTE: All item pointers are still valid after a call to <>, <> 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); ----