Merge branch 'vector' into develop

3 files changed, 788 insertions, 0 deletions

diff --git a/collections/vector/vector.adoc b/collections/vector/vector.adoc
new file mode 100644
index 0000000..7c4bc7f
--- /dev/null
+++ b/collections/vector/vector.adoc
@@ -0,0 +1,465 @@
+Vector
+======
+Tucker Evans
+v0.17, 2020-07-04
+
+A basic vector, that hold pointers to your data structures.
+
+NOTE: There is currently no way to distinquish between a failed retrieval
+(pop, index, back, etc.) and returning a NULL value. Keep this in mind if
+you plan on storing NULL values in the vector, there are plans to fix this in
+the future.
+
+Types
+-----
+
++vec+
+
+This structure holds all internal information regarding a vector.
+All functions (except constructors) expect a pointer to this struct as their
+first parameter.
+
+Functions
+---------
+[[vec_new]]
++vec* vec_new()+
+~~~~~~~~~~~~~~~~
+Constructs an empty vector.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_new();
+----
+
+`vec* vec_with_capacity(int capacity)`
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Constructs an empty vector with space for +capacity+ items.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_with_capacity(16);
+----
+
+[[vec_size]]
++int vec_size(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the number of elements in vector +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_new();
+assert(vec_size(vector) == 0);
+vec_push(vector, NULL);
+assert(vec_size(vector) == 1);
+----
+
++int vec_capacity(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the maximun number of elements in vector +self+ before the buffer needs
+to be resized (does not take the current size into consideration).
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_with_capacity(16);
+assert(vec_capacity(vector) == 16);
+----
+
+[[vec_cp]]
++vec* vec_cp(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~
+Returns a copy of the vector +self+. All elements are kept in the same order.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_with_capacity(16);
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+vec *new = vec_cp(vector);
+assert(strcmp(vec_pop, str2) == 0);
+assert(strcmp(vec_pop, str1) == 0);
+----
+
+[[vec_print]]
++void vec_print(vec *self, (char* to_string(void*)))+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Prints out the contents of the vector +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 "vector.h"
+#include <string.h>
+
+char* to_string(str)
+void *str;
+{
+	return strdup(str);
+}
+
+int main()
+{
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+vec_push(vector, str_dup(str3));
+
+printf("VEC CONTENTS:\n\t")
+vec_print(vector, to_string)
+}
+----
+
+Output:
+----
+VEC_CONTENTS:
+	[ONE,TWO,THREE]
+----
+
+[[vec_push]]
++void vec_push(vec *self, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pushes +item+ into back of +self+. This may cause a resize of the internal buffer.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_new();
+vec_push(vector, NULL);
+assert(vec_size(vector) == 1);
+----
+
+[[vec_pop]]
++void* vec_pop(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+Pops an item off of the back of the vector +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+assert(str_cmp(vec_pop(vector), str2) == 0);
+assert(str_cmp(vec_pop(vector), str1) == 0);
+----
+
+[[vec_back]]
++void* vec_back(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the element at the back of the vector +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+assert(strcmp(vec_back(vector), str2) == 0);
+----
+
+[[vec_set]]
++void vec_set(vec *self, int index, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Sets the element at position +index+ in +self+ to +item+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+vec_set(vector, 0, str2);
+
+assert(str_cmp(vec_pop(vector), str2) == 0);
+assert(str_cmp(vec_pop(vector), str2) == 0);
+----
+
+[[vec_index]]
++void* vec_index(vec *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Returns the element at position +index+ of +self+.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+vec_push(vector, str_dup(str3));
+
+assert(str_cmp(vec_index(vector, 1), str2) == 0);
+----
+
+[[vec_insert]]
++void vec_insert(vec *self, int index, void *item)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Inserts +item+ into vector +self+ at index +index+, all items after the index
+are pushed toward the end.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+vec_insert(vector, 1, str_dup(str3));
+
+assert(str_cmp(vec_index(vector, 1), str3) == 0);
+assert(str_cmp(vec_index(vector, 2), str2) == 0);
+----
+
+[[vec_remove]]
++void vec_remove(vec *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Element at position +index+ of +self+ is removed from vector and the remaining
+items are shifted towards the front.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+vec_push(vector, str_dup(str3));
+
+vec_remove(vector, 1);
+
+assert(vec_size == 2);
+assert(strcmp(vec_pop(vector), str3) == 0);
+assert(strcmp(vec_pop(vector), str1) == 0);
+----
+
+[[vec_swap]]
++void vec_swap(vec *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 "dvector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+vec_swap(vector, 0, 1);
+
+assert(str_cmp(vec_index(vector, 0), str2) == 0);
+assert(str_cmp(vec_back(vector), str1) == 0);
+----
+
+[[vec_swap_pop]]
++void* vec_swap_pop(vec *self, int index)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Swaps back element with item at +index+, and pops item now at back.
+Will return same element as +vec_remove(self, index)+.
+Does not keep order of elements, but faster that <<vec_remove,+vec_remove()+>>.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+vec_push(vector, str_dup(str3));
+
+assert(str_cmp(vec_swap_pop(vector, 2), str3) == 0);
+assert(str_cmp(vec_back(vector, str2) == 0);
+assert(vec_size == 2);
+----
+
+[[vec_truncate]]
++void vec_truncate(vec *self, int size)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Truncates vector +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 "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+char *str3 = "THREE";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+vec_push(vector, str_dup(str3));
+
+vec_truncate(vector, 1);
+
+assert(vec_size == 1);
+----
+
+[[vec_reserve]]
++void vec_reserve(vec *self, int additional)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Reserves space for +additional+ items. May reserve more memory to avoid too
+many reallocations.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_with_capacity(16);
+
+vec_reserve(vector, 20);
+assert(vec_capacity(vector) >= 20);
+----
+
+[[vec_clear]]
++void vec_clear(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Free all elements within vector +self+, and sets vector to empty (size 0).
+
+NOTE: Does not free internal memory of +self+ or +self+ itself, if this is desired
+<<vec_free,+vec_free()+>> should be called immediatly after this.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+#include <string.h>
+
+char *str1 = "ONE";
+char *str2 = "TWO";
+
+vec *vector = vec_new();
+vec_push(vector, str_dup(str1));
+vec_push(vector, str_dup(str2));
+
+vec_clear(vector);
+assert(vec_size(vector) == 0);
+vec_free(vector);
+----
+
+[[vec_free]]
++void vec_free(vec *self)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+Frees all internal memory and +self+.
+
+NOTE: All item pointers are still valid after a call to
+<<vec_free,+vec_free()+>>, <<vec_clear,+vec_clear()+>> should be called before
+if they are no longer needed to avoid memory leaks.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "vector.h"
+
+vec *vector = vec_new();
+vec_free(vector);
+----
diff --git a/collections/vector/vector.c b/collections/vector/vector.c
new file mode 100644
index 0000000..f14c302
--- /dev/null
+++ b/collections/vector/vector.c
@@ -0,0 +1,286 @@
+#include "vector.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#define START_SIZE 64;
+
+struct vector {
+	void **base;
+	int end, limit;
+};
+
+void vec_debug_print(root)
+vec *root;
+{
+	int i;
+
+	fprintf(stderr, "VEC[base: %p, end: %p, limit:%p]:\n\t ",
+			root->base, root->end, root->limit);
+	for (i=0; i < root->end; i++){
+		fprintf(stderr, "[%p]", vec_index(root,i));
+	}
+	fprintf(stderr, "\n");
+}
+
+vec* vec_new()
+{
+	vec *root;
+
+	root = malloc(sizeof(vec));
+	assert(root);
+
+	root->limit = START_SIZE;
+	root->base = malloc(root->limit * sizeof(void*));
+	assert(root->base);
+
+	return root;
+}
+
+vec* vec_with_capacity(n)
+int n;
+{
+	vec *root;
+
+	root = malloc(sizeof(vec));
+	assert(root);
+
+	root->limit = n;
+	root->base = malloc(root->limit * sizeof(void*));
+	assert(root->base);
+
+	return root;
+}
+
+int vec_size(root)
+vec *root;
+{
+	if (!root) {
+		return -1;
+	}
+	return root->end;
+}
+
+int vec_capacity(root)
+vec *root;
+{
+	if (!root) {
+		return -1;
+	}
+	
+	return root->limit;
+}
+
+void vec_resize(root)
+vec *root;
+{
+	if (!root)
+		return;
+
+	root->base = reallocarray(root->base, root->limit * 2, sizeof(void*));
+	assert(root->base);
+}
+
+vec* vec_cp(root)
+vec *root;
+{
+	vec *copy;
+
+	if (!root)
+		return NULL;
+
+	copy = vec_with_capacity(root->limit);
+
+	copy->base = memcpy(copy->base, root->base,
+			vec_size(root) * sizeof(void*));
+	assert(copy->base);
+
+	copy->end = root->end;
+	copy->limit = root->limit;
+
+	return copy;
+}
+
+void vec_print(root, to_string)
+vec *root;
+char* to_string(void*);
+{
+	int i;
+	char *tmp;
+
+	printf("[");
+	for(i = 0; i < root->end; i++) {
+		printf("%s", tmp = to_string(vec_index(root, i)));
+		free(tmp);
+		tmp = NULL;
+	}
+	printf("\b]\n");
+
+}
+
+void vec_push(root, item)
+vec *root;
+void *item;
+{
+	if (!root) {
+		return;
+	}
+
+	if (root->end >= root->limit) {
+		vec_resize(root);
+	}
+
+	root->base[root->end++] = item;
+}
+
+void* vec_pop(root)
+vec *root;
+{
+	if (!root || root->end <= 0) {
+		return NULL;
+	}
+
+	return root->base[--root->end];
+}
+
+void* vec_back(root)
+vec *root;
+{
+	if (!root || root->end == 0) {
+		return NULL;
+	}
+
+	return root->base[root->end - 1];
+}
+
+void vec_set(root, index, item)
+vec *root;
+int index;
+void *item;
+{
+	if (!root || index >= root->end || index < 0)
+		return;
+
+	root->base[index] = item;
+}
+
+void* vec_index(root, index)
+vec *root;
+int index;
+{
+	if (!root || index >= root->end || index < 0) {
+		return NULL;
+	}
+
+	return root->base[index];
+}
+
+void vec_insert(root, index, item)
+vec *root;
+int index;
+void *item;
+{
+	if (!root || index > root->end || index < 0)
+		return;
+
+	if (root->end >= root->limit)
+		vec_resize(root);
+
+	memmove(root->base + index + 1, root->base + index,
+			(root->end++ - index) * sizeof(void*));
+
+	root->base[index] = item;
+}
+
+void* vec_remove(root, index)
+vec *root;
+int index;
+{
+	void *tmp;
+
+	if (!root || index > root->end || index < 0)
+		return NULL;
+
+	tmp = vec_index(root, index);
+	memmove(root->base + index, root->base + index + 1,
+			(--root->end - index) * sizeof(void*));
+
+	return tmp;
+}
+
+void vec_swap(root, i, j)
+vec *root;
+int i,j;
+{
+	void *tmp;
+
+	if (!root || i >= root->end || i < 0 || j >= root->end || j < 0)
+		return;
+
+	tmp = root->base[i];
+	root->base[i] = root->base[j];
+	root->base[j] = tmp;
+
+	return;
+}
+
+void* vec_swap_pop(root, i)
+vec *root;
+int i;
+{
+	void *tmp;
+	int j;
+
+	if (!root || i >= root->end || i < 0 || root->end <= 0)
+		return NULL;
+
+	vec_swap(root, i, root->end - 1);
+	return vec_pop(root);
+}
+
+void vec_truncate(root, size)
+vec *root;
+int size;
+{
+	if (!root || size < 0 || size >= root->end)
+		return;
+
+	root->end = size;
+}
+
+void vec_reserve(root, n)
+vec *root;
+int n;
+{
+	int i;
+
+	if (!root || n + root->end <= root->limit)
+		return;
+
+	for (i = root->limit; i < root->end + n; i*=2);
+
+	root->base = reallocarray(root->base, i, sizeof(void*));
+}
+
+void vec_clear(root)
+vec *root;
+{
+	int i;
+
+	for (i = 0; i < root->end; i++) {
+		free(vec_index(root, i));
+	}
+
+	root->end = 0;
+}
+
+void vec_free(root)
+vec *root;
+{
+	free(root->base);
+	root->base = NULL;
+
+	free(root);
+}
diff --git a/collections/vector/vector.h b/collections/vector/vector.h
new file mode 100644
index 0000000..4d6d04c
--- /dev/null
+++ b/collections/vector/vector.h
@@ -0,0 +1,37 @@
+#ifndef VECTOR_H
+#define VECTOR_H
+
+typedef struct vector vec;
+
+/*constructors*/
+vec* vec_new();
+vec* vec_with_capacity(int);
+
+/*management*/
+int vec_size(vec*);
+int vec_capacity(vec*);
+vec* vec_cp(vec*);
+void vec_print(vec*, char* (void*));
+
+/*data*/
+void vec_push(vec*, void*);
+void* vec_pop(vec*);
+void* vec_back(vec*);
+
+void vec_set(vec*, int, void*);
+void* vec_index(vec*, int);
+
+void vec_insert(vec*, int, void*);
+void* vec_remove(vec*, int);
+
+void vec_swap(vec*, int, int);
+void* vec_swap_pop(vec*, int);
+
+
+/*memory*/
+void vec_truncate(vec*, int);
+void vec_reserve(vec*, int);
+
+void vec_clear(vec*);
+void vec_free(vec*);
+#endif