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.c277
1 files changed, 140 insertions, 137 deletions
diff --git a/collections/double_ended_queue/double_ended_queue.c b/collections/double_ended_queue/double_ended_queue.c
index f5e9880..c08169d 100644
--- a/collections/double_ended_queue/double_ended_queue.c
+++ b/collections/double_ended_queue/double_ended_queue.c
@@ -28,6 +28,19 @@ struct double_ended_queue {
int beg, end, limit;
};
+void deq_debug_print(root)
+deq *root;
+{
+ void **tmp;
+
+ fprintf(stderr, "DEQ[base: %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_new()
{
deq *root;
@@ -111,16 +124,40 @@ deq *root;
root->base = tmp;
}
-void* deq_index(root, index)
+deq* deq_cp(root)
deq *root;
-int index;
{
- void **tmp;
+ deq *copy;
- if (!root || !DEQ_IN_BOUNDS(root,index))
- return NULL;
+ copy = deq_with_capacity(root->limit);
+ assert(copy->base);
- return root->base[(root->beg + index) % root->limit];
+ copy->base = memcpy(copy->base, root->base,
+ root->limit * sizeof(void*));
+ assert(copy->base);
+
+ copy->beg = root->beg;
+ copy->end = root->end;
+
+ return copy;
+}
+
+void deq_print(root, to_string)
+deq *root;
+char* to_string(void*);
+{
+ int i, size;;
+ char *tmp;
+
+ size = deq_size(root);
+
+ printf("[");
+ for (i = 0; i < size; i++) {
+ printf("%s,", tmp = to_string(deq_index(root, i)));
+ free(tmp);
+ tmp = NULL;
+ }
+ printf("\b]\n");
}
void deq_push_front(root, item)
@@ -163,54 +200,23 @@ void *item;
root->end = root->limit;
}
-void deq_set(root, index, item)
+void* deq_front(root)
deq *root;
-int index;
-void *item;
{
- if (!root || !DEQ_IN_BOUNDS(root, index))
- return;
- root->base[(root->beg + index) % root->limit] = item;
+ if (!root)
+ return NULL;
+
+ return root->base[root->beg];
}
-void deq_insert(root, index, item)
+void* deq_back(root)
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;
+ return NULL;
- root->base[index] = item;
+ return root->base[(root->end - 1) % root->limit];
}
-
void* deq_pop_front(root)
deq *root;
{
@@ -238,63 +244,78 @@ deq *root;
return root->base[root->end];
}
-void* deq_swap_rm_front(root, index)
+void deq_set(root, index, item)
deq *root;
int index;
+void *item;
{
- if (!root || !DEQ_IN_BOUNDS(root,index))
- return NULL;
-
- deq_swap(root, 0, index);
- return deq_pop_front(root);
+ if (!root || !DEQ_IN_BOUNDS(root, index))
+ return;
+ root->base[(root->beg + index) % root->limit] = item;
}
-void* deq_swap_rm_back(root, index)
+void* deq_index(root, index)
deq *root;
int index;
{
+ void **tmp;
+
if (!root || !DEQ_IN_BOUNDS(root,index))
return NULL;
- deq_swap(root,deq_size(root) - 1,index);
- return deq_pop_back(root);
+ return root->base[(root->beg + index) % root->limit];
}
-void deq_swap(root, i, j)
+void deq_insert(root, index, item)
deq *root;
-int i, j;
+int index;
+void *item;
{
- int len;
- void *tmp;
-
if (!root)
return;
- len = deq_size(root);
-
- if (i >= len || j >= len)
+ if (index > deq_size(root))
return;
- i += root->beg;
- i %= root->limit;
+ if (root->end >= root->limit)
+ deq_resize(root);
- j += root->beg;
- j %= root->limit;
+ index = (root->beg + index) % root->limit;
- tmp = root->base[i];
- root->base[i] = root->base[j];
- root->base[j] = tmp;
+ 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_remove(root, index)
deq *root;
int index;
{
+ void *tmp;
+
if (!root || !DEQ_IN_BOUNDS(root,index));
return;
index = (root->beg + index) % root->limit;
+ tmp = root->base[index];
root->base[index] = NULL;
if (root->beg < root->end || index >= root->beg) {
@@ -306,78 +327,58 @@ int index;
memmove(root->base + index, root->base + index + 1,
(--root->end - index) * sizeof(void*));
}
+
+ return tmp;
}
-/* Note: Elements are not freed
- * deq_clear should be called before if they are no longer needed.
- */
-void deq_free(root)
+void deq_swap(root, i, j)
deq *root;
+int i, j;
{
- free(root->base);
- root->base = NULL;
+ int len;
+ void *tmp;
- free(root);
-}
+ if (!root)
+ return;
-void deq_clear(root)
-deq *root;
-{
- int i, size;
+ len = deq_size(root);
- size = deq_size(root);
- for (i = 0; i < size; i++) {
- free(deq_index(root, i));
- }
-}
+ if (i >= len || j >= len)
+ return;
-void deq_print(root, to_string)
-deq *root;
-char* to_string(void*);
-{
- int i, size;;
+ i += root->beg;
+ i %= root->limit;
- size = deq_size(root);
+ j += root->beg;
+ j %= root->limit;
- printf("[");
- for (i = 0; i < size; i++) {
- printf("%s,", to_string(deq_index(root, i)));
- }
- printf("\b]\n");
+ tmp = root->base[i];
+ root->base[i] = root->base[j];
+ root->base[j] = tmp;
}
-void deq_debug_print(root)
+void* deq_swap_rm_front(root, index)
deq *root;
+int index;
{
- void **tmp;
+ if (!root || !DEQ_IN_BOUNDS(root,index))
+ return NULL;
- fprintf(stderr, "DEQ[base: %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_swap(root, 0, index);
+ return deq_pop_front(root);
}
-deq* deq_cp(root)
+void* deq_swap_rm_back(root, index)
deq *root;
+int index;
{
- 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;
+ if (!root || !DEQ_IN_BOUNDS(root,index))
+ return NULL;
- return copy;
+ deq_swap(root,deq_size(root) - 1,index);
+ return deq_pop_back(root);
}
-/*Note: Does not currently reduce memory footprint*/
void deq_truncate(root, size)
deq *root;
int size;
@@ -388,24 +389,6 @@ int size;
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;
@@ -439,3 +422,23 @@ int size;
free(root->base);
root->base = tmp;
}
+
+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_free(root)
+deq *root;
+{
+ free(root->base);
+ root->base = NULL;
+
+ free(root);
+}
generated by cgit v1.1 at 2024-04-29 15:10:44 +0000