aboutsummaryrefslogtreecommitdiff
path: root/collections/double_ended_queue/double_ended_queue.c
diff options
context:
space:
mode:
Diffstat (limited to 'collections/double_ended_queue/double_ended_queue.c')
-rw-r--r--collections/double_ended_queue/double_ended_queue.c441
1 files changed, 441 insertions, 0 deletions
diff --git a/collections/double_ended_queue/double_ended_queue.c b/collections/double_ended_queue/double_ended_queue.c
new file mode 100644
index 0000000..015b90b
--- /dev/null
+++ b/collections/double_ended_queue/double_ended_queue.c
@@ -0,0 +1,441 @@
+#include "double_ended_queue.h"
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include <stdio.h>
+
+/*Checks bounds for index (y) in queue*/
+#define DEQ_IN_BOUNDS(x, y) (y < deq_size(x)) \
+
+#define START_SIZE 64;
+
+/*TODO add returned error codes for current void functions
+ * (resize, push, etc.)
+ *
+ * Should all functions return a status code and take in a dest argument?
+ */
+
+/* Double ended queue as a circular buffer
+ * base is pointer to buffer.
+ * beg: postiton of the first element is stored.
+ * end: position for the next element to be stored.
+ * limit: the maximum number of elements.
+ */
+
+struct double_ended_queue {
+ void **base;
+ int beg, end, limit;
+};
+
+deq* deq_new()
+{
+ deq *root;
+
+ root = malloc(sizeof(deq));
+ assert(root);
+
+ root->limit = START_SIZE;
+ root->beg = root->end = 0;
+ root->base = malloc(root->limit * sizeof(void*));
+ assert(root->base);
+
+ return root;
+}
+
+deq* deq_with_capacity(n)
+int n;
+{
+ deq *root;
+
+ root = malloc(sizeof(deq));
+ assert(root);
+
+ root->limit = n;
+ root->beg = root->end = 0;
+ root->base = malloc(root->limit * sizeof(void*));
+ assert(root->base);
+
+ return root;
+}
+
+int deq_size(root)
+deq *root;
+{
+ if (!root)
+ return -1;
+
+ if (root->beg <= root->end)
+ return (root->end - root->beg);
+
+ return (root->limit - root->beg) + (root->end);
+}
+
+int deq_capacity(root)
+deq *root;
+{
+ if (!root) {
+ return -1;
+ } else {
+ return root->limit;
+ }
+}
+
+void deq_resize(root)
+deq *root;
+{
+ void **tmp;
+ int size;
+
+ tmp = malloc(root->limit * 2 * sizeof(void*));
+ assert(tmp);
+
+ if (root->beg <= root->end) {
+ tmp = memcpy(tmp, root->base + root->beg,
+ deq_size(root) * sizeof(void*));
+ } else {
+ /*copy beg<->limit*/
+ size = root->limit - root->beg;
+ tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*));
+ assert(tmp);
+
+ /*copy base<->end*/
+ tmp = memcpy(tmp + size, root->base,
+ root->end * sizeof(void*));
+ assert(tmp);
+ }
+
+ root->limit *= 2;
+
+ free(root->base);
+ root->base = tmp;
+}
+
+void* deq_index(root, index)
+deq *root;
+int index;
+{
+ void **tmp;
+
+ if (!root || !DEQ_IN_BOUNDS(root,index))
+ return NULL;
+
+ return root->base[(root->beg + index) % root->limit];
+}
+
+void deq_push_front(root, item)
+deq *root;
+void *item;
+{
+ void **tmp;
+
+ if (!root)
+ return;
+
+ if (root->end >= root->limit)
+ deq_resize(root);
+
+ --root->beg;
+ root->beg %= root->limit;
+
+ root->base[root->beg] = item;
+
+ if (root->end == root->beg)
+ root->end = root->limit;
+}
+
+void deq_push_back(root, item)
+deq *root;
+void *item;
+{
+ void **tmp;
+
+ if (!root)
+ return;
+
+ if (root->end >= root->limit)
+ deq_resize(root);
+
+ root->base[root->end++] = item;
+ root->end %= root->limit;
+
+ if (root->end == root->beg)
+ root->end = root->limit;
+}
+
+void deq_set(root, index, item)
+deq *root;
+int index;
+void *item;
+{
+ if (!root || !DEQ_IN_BOUNDS(root, index))
+ return;
+ root->base[(root->beg + index) % root->limit] = item;
+}
+
+void deq_insert(root, index, item)
+deq *root;
+int index;
+void *item;
+{
+ if (!root)
+ return;
+
+ if (index > deq_size(root))
+ return;
+
+ if (root->end >= root->limit)
+ deq_resize(root);
+
+ index = (root->beg + index) % root->limit;
+
+ if (root->beg < root->end) {
+ memmove(root->base + index + 1, root->base + index,
+ (root->end - index) * sizeof(void*));
+ ++root->end;
+ root->end = root->end % root->limit;
+ } else if (index < root->end) {
+ memmove(root->base + index + 1,
+ root->base + index,
+ (root->end - index) * sizeof(void*));
+ ++root->end;
+ } else {
+ memmove(root->base + root->beg - 1, root->base + root->beg,
+ (index - root->beg) * sizeof(void*));
+ --root->beg;
+ }
+
+ if (root->end == root->beg)
+ root->end = root->limit;
+
+ root->base[index] = item;
+}
+
+void* deq_pop_front(root)
+deq *root;
+{
+ void* tmp;
+ if (!root || root->beg == root->end)
+ return NULL;
+
+ tmp = root->base[root->beg];
+
+ ++root->beg;
+ root->beg %= root->limit;
+
+ return tmp;
+}
+
+void* deq_pop_back(root)
+deq *root;
+{
+ if (!root || root->end == root->beg)
+ return NULL;
+
+ --root->end;
+ root->end %= root->limit;
+
+ return root->base[root->end];
+}
+
+void* deq_swap_rm_front(root, index)
+deq *root;
+int index;
+{
+ if (!root || !DEQ_IN_BOUNDS(root,index))
+ return NULL;
+
+ deq_swap(root, 0, index);
+ return deq_pop_front(root);
+}
+
+void* deq_swap_rm_back(root, index)
+deq *root;
+int index;
+{
+ if (!root || !DEQ_IN_BOUNDS(root,index))
+ return NULL;
+
+ deq_swap(root,deq_size(root) - 1,index);
+ return deq_pop_back(root);
+}
+
+void deq_swap(root, i, j)
+deq *root;
+int i, j;
+{
+ int len;
+ void *tmp;
+
+ if (!root)
+ return;
+
+ len = deq_size(root);
+
+ if (i >= len || j >= len)
+ return;
+
+ i += root->beg;
+ i %= root->limit;
+
+ j += root->beg;
+ j %= root->limit;
+
+ tmp = root->base[i];
+ root->base[i] = root->base[j];
+ root->base[j] = tmp;
+}
+
+void deq_remove(root, index)
+deq *root;
+int index;
+{
+ if (!root || !DEQ_IN_BOUNDS(root,index));
+ return;
+
+ index = (root->beg + index) % root->limit;
+
+ root->base[index] = NULL;
+
+ if (root->beg < root->end || index >= root->beg) {
+ memmove(root->base + root->beg + 1,
+ root->base + root->beg,
+ (index - root->beg) * sizeof(void*));
+ ++root->beg;
+ } else {
+ memmove(root->base + index, root->base + index + 1,
+ (--root->end - index) * sizeof(void*));
+ }
+}
+
+/* Note: Elements are not freed
+ * deq_clear should be called before if they are no longer needed.
+ */
+void deq_free(root)
+deq *root;
+{
+ free(root->base);
+ root->base = NULL;
+
+ free(root);
+}
+
+void deq_clear(root)
+deq *root;
+{
+ int i, size;
+
+ size = deq_size(root);
+ for (i = 0; i < size; i++) {
+ free(deq_index(root, i));
+ }
+}
+
+void deq_print(root, to_string)
+deq *root;
+char* to_string(void*);
+{
+ int i, size;;
+
+ size = deq_size(root);
+
+ printf("[");
+ for (i = 0; i < size; i++) {
+ printf("%s,", to_string(deq_index(root, i)));
+ }
+ printf("\b]\n");
+}
+
+void deq_debug_print(root)
+deq *root;
+{
+ void **tmp;
+
+ fprintf(stderr, "VEC[b: %p, beg: %d, end:%d]:\n\t ",
+ root->base, root->beg, root->end);
+ for (tmp = root->base; tmp < root->base + root->limit; tmp++){
+ fprintf(stderr, "[%p]", *tmp);
+ }
+ fprintf(stderr, "\n");
+}
+
+deq* deq_cp(root)
+deq *root;
+{
+ deq *copy;
+
+ copy = deq_with_capacity(root->limit);
+ assert(copy->base);
+
+ copy->base = memcpy(copy->base, root->base,
+ root->limit * sizeof(void*));
+ assert(copy->base);
+
+ copy->beg = root->beg;
+ copy->end = root->end;
+
+ return copy;
+}
+
+/*Note: Does not currently reduce memory footprint*/
+void deq_truncate(root, size)
+deq *root;
+int size;
+{
+ if (!root || size > deq_size(root))
+ return;
+
+ root->end = (root->beg + size) % root->limit;
+}
+
+void* deq_front(root)
+deq *root;
+{
+ if (!root)
+ return NULL;
+
+ return root->base[root->beg];
+}
+
+void* deq_back(root)
+deq *root;
+{
+ if (!root)
+ return NULL;
+
+ return root->base[(root->end - 1) % root->limit];
+}
+
+void deq_reserve(root, size)
+deq *root;
+int size;
+{
+ void **tmp;
+ int i, cur_size;
+
+ cur_size = deq_size(root);
+ for (i = root->limit; i - cur_size < size; i*=2);
+
+ tmp = malloc(i * sizeof(void*));
+ assert(tmp);
+
+ if (root->beg <= root->end) {
+ tmp = memcpy(tmp, root->base + root->beg,
+ deq_size(root) * sizeof(void*));
+ } else {
+ /*copy beg<->limit*/
+ size = root->limit - root->beg;
+ tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*));
+ assert(tmp);
+
+ /*copy base<->end*/
+ tmp = memcpy(tmp + size, root->base,
+ root->end * sizeof(void*));
+ assert(tmp);
+ }
+
+ root->limit *= 2;
+
+ free(root->base);
+ root->base = tmp;
+}
generated by cgit v1.1 at 2024-05-18 23:42:11 +0000