1 files changed, 368 insertions, 0 deletions

diff --git a/src/arraylist.c b/src/arraylist.c
new file mode 100644
index 0000000..f010d07
--- /dev/null
+++ b/src/arraylist.c
@@ -0,0 +1,368 @@
+/* arraylist */
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#include "util.h"
+
+typedef int T;
+
+struct ArrayList {
+        T **   array;
+        size_t size;
+        size_t capacity;
+};
+
+static T **
+ArrayList_allocateArray(void *ptr, size_t nelem)
+{
+        T **new_ptr = reallocarray(ptr, nelem, sizeof *new_ptr);
+
+        if ( new_ptr == NULL ) {
+                ERROR("out of memory");
+        }
+
+        return new_ptr;
+}
+
+void
+ArrayList_init(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        arrayList->array    = NULL;
+        arrayList->size     = 0;
+        arrayList->capacity = 0;
+}
+
+struct ArrayList *
+ArrayList_new(void)
+{
+        struct ArrayList *arrayList = malloc(sizeof *arrayList);
+        if ( arrayList ) {
+                ArrayList_init(arrayList);
+        }
+        return arrayList;
+}
+
+void
+ArrayList_free(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        free(arrayList->array);
+        ArrayList_init(arrayList);
+}
+
+void
+ArrayList_delete(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        ArrayList_free(arrayList);
+        free(arrayList);
+}
+
+static void
+ArrayList_growIfNeeded(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        if ( arrayList->size == arrayList->capacity ) {
+                if ( arrayList->array == NULL ) { // leere Liste
+                        assert(arrayList->size == 0);
+                        assert(arrayList->capacity == 0);
+
+                        static const size_t DEFAULT_CAPACITY = 10;
+
+                        arrayList->capacity = DEFAULT_CAPACITY;
+                        arrayList->array    = ArrayList_allocateArray(NULL, DEFAULT_CAPACITY);
+                }
+                else {
+                        size_t new_capacity  = (arrayList->capacity * 3) / 2; // *= 1.5
+                        T **   new_arrayList = ArrayList_allocateArray(arrayList->array, new_capacity);
+
+                        arrayList->capacity = new_capacity;
+                        arrayList->array    = new_arrayList;
+                }
+
+                assert(arrayList->array);
+        }
+
+        assert(arrayList->capacity > arrayList->size);
+}
+
+void
+ArrayList_append(struct ArrayList *arrayList, T *ptr)
+{
+        assert(arrayList);
+
+        ArrayList_growIfNeeded(arrayList);
+
+        arrayList->array[arrayList->size++] = ptr;
+}
+
+void
+ArrayList_insertAt(struct ArrayList *arrayList, size_t idx, T *ptr)
+{
+        assert(arrayList);
+        assert(idx <= arrayList->size); // allow last position
+
+        ArrayList_growIfNeeded(arrayList);
+
+        memmove(&arrayList->array[idx + 1],
+                &arrayList->array[idx],
+                (arrayList->size - idx) * sizeof arrayList->array[0]);
+        arrayList->array[idx] = ptr;
+        ++arrayList->size;
+}
+
+T *
+ArrayList_getAt(struct ArrayList *arrayList, size_t idx)
+{
+        assert(arrayList);
+        assert(idx < arrayList->size);
+
+        return arrayList->array[idx];
+}
+
+size_t
+ArrayList_size(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        return arrayList->size;
+}
+
+bool
+ArrayList_empty(struct ArrayList *arrayList)
+{
+        assert(arrayList);
+
+        return arrayList->size == 0;
+}
+
+void
+ArrayList_removeAt(struct ArrayList *arrayList, size_t idx, void clear_func(T *, void *), void *args)
+{
+        assert(arrayList);
+        assert(idx < arrayList->size);
+
+        if ( clear_func ) {
+                clear_func(arrayList->array[idx], args);
+        }
+
+#if defined(ARRAYLIST_KEEP_ORDER)
+        memmove(&arrayList->arrayList[idx],
+                &arrayList->arrayList[idx + 1],
+                (arrayList->size - (idx + 1)) * sizeof arrayList->arrayList[0]);
+#else
+        arrayList->array[idx] = arrayList->array[arrayList->size - 1];
+#endif
+
+        --arrayList->size;
+}
+
+struct qsortHelper_context {
+        int (*cmp)(const T *, const T *, void *);
+        void *args;
+};
+
+typedef const T *const_T_ptr;
+
+static int
+ArrayList_qsortHelper(void *ctx, const void *a, const void *b)
+{
+        const const_T_ptr *aa = a;
+        const const_T_ptr *bb = b;
+
+        const struct qsortHelper_context *context = ctx;
+
+        return context->cmp(*aa, *bb, context->args);
+}
+
+void
+ArrayList_sort(struct ArrayList *arrayList, int cmp(const T *, const T *, void *), void *args)
+{
+        assert(arrayList);
+        assert(cmp);
+
+        struct qsortHelper_context context = {
+                .cmp  = cmp,
+                .args = args
+        };
+
+        // Das vollständige qsort_x()-Drama: https://stackoverflow.com/a/46042467
+        qsort_r(arrayList->array, arrayList->size, sizeof arrayList->array[0], &context, ArrayList_qsortHelper);
+}
+
+bool
+ArrayList_linearSearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc)
+{
+        assert(arrayList);
+        assert(cmp);
+        assert(loc);
+
+        for ( size_t idx = 0; idx != arrayList->size; ++idx ) {
+                if ( cmp(key, arrayList->array[idx], args) == 0 ) {
+                        *loc = idx;
+                        return true;
+                }
+        }
+        return false;
+}
+
+struct bsearchHelper_context {
+        void *key;
+        int (*cmp)(void *, const T *, void *);
+        void *args;
+};
+
+static int
+ArrayList_bsearchHelper(const void *ctx, const void *el)
+{
+        const struct bsearchHelper_context *context = ctx;
+        const const_T_ptr *                 element = el;
+
+        return context->cmp(context->key, *element, context->args);
+}
+
+bool
+ArrayList_binarySearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *, void *), void *args, size_t *loc)
+{
+        assert(arrayList);
+        assert(cmp);
+        assert(loc);
+
+        struct bsearchHelper_context context = {
+                .key  = key,
+                .cmp  = cmp,
+                .args = args
+        };
+
+        T **pos = bsearch(&context, arrayList->array, arrayList->size, sizeof arrayList->array[0], ArrayList_bsearchHelper);
+        if ( pos ) {
+                *loc = (size_t)(pos - arrayList->array);
+                return true;
+        }
+        else {
+                return false;
+        }
+}
+
+void
+ArrayList_shuffle(struct ArrayList *arrayList, size_t rng(size_t, void *), void *args)
+{
+        assert(arrayList);
+        assert(rng);
+
+        if ( arrayList->size > 1 ) {
+                for ( size_t i = arrayList->size - 1; i > 0; --i ) {
+                        size_t j = rng(i + 1, args);
+
+                        // swap
+                        T *t                = arrayList->array[j];
+                        arrayList->array[j] = arrayList->array[i];
+                        arrayList->array[i] = t;
+                }
+        }
+}
+
+static void
+ArrayList_debugPrint(struct ArrayList *arrayList)
+{
+        for ( size_t idx = 0; idx != ArrayList_size(arrayList); ++idx ) {
+                T *ptr = ArrayList_getAt(arrayList, idx);
+                printf("%d, ", *ptr);
+        }
+        putchar('\n');
+}
+
+static int
+my_compare(const T *a, const T *b, void *args)
+{
+        (void) args;
+
+        if ( *a > *b )
+                return 1;
+        else if ( *a < *b )
+                return -1;
+        else
+                return 0;
+}
+
+static int
+my_search_compare(void *key, const T *element, void *args)
+{
+        (void) args;
+
+        int *a = key;
+
+        if ( *a < *element )
+                return -1;
+        else if ( *a > *element )
+                return 1;
+        else
+                return 0;
+}
+
+static size_t
+my_rng(size_t max, void *args)
+{
+        (void) args;
+        return (size_t) rand() % max;
+}
+
+static void
+ArrayList_testSort(struct ArrayList *arrayList)
+{
+        for ( size_t i = 1; i < arrayList->size; ++i ) {
+                if ( *arrayList->array[i - 1] > *arrayList->array[i] ) {
+                        fprintf(stderr, "Fehler: %zu (%d, %d)\n", i, *arrayList->array[i - 1], *arrayList->array[i]);
+                        exit(EXIT_FAILURE);
+                }
+        }
+}
+
+int
+main(void)
+{
+        srand(time(NULL));
+
+        int a = 11, b = 22, c = 33, d = 44;
+
+        struct ArrayList *arrayList = ArrayList_new();
+
+        ArrayList_append(arrayList, &a);
+        ArrayList_append(arrayList, &b);
+        ArrayList_append(arrayList, &c);
+        ArrayList_append(arrayList, &d);
+        ArrayList_debugPrint(arrayList); // 11, 22, 33, 44
+
+        ArrayList_removeAt(arrayList, 0, NULL, NULL);
+        ArrayList_debugPrint(arrayList); // 44, 22, 33
+
+        ArrayList_insertAt(arrayList, 3, &a);
+        ArrayList_debugPrint(arrayList); // 44, 22, 33, 11
+
+        ArrayList_sort(arrayList, my_compare, NULL);
+        ArrayList_testSort(arrayList);
+
+        ArrayList_debugPrint(arrayList); // 11, 22, 33, 44
+
+        size_t loc;
+        int    dummy = 44;
+        if ( ArrayList_binarySearch(arrayList, &dummy, my_search_compare, NULL, &loc) ) {
+                printf("Gefunden: %zu\n", loc);
+        }
+
+        ArrayList_shuffle(arrayList, my_rng, NULL);
+        ArrayList_debugPrint(arrayList); // ??
+
+        ArrayList_delete(arrayList);
+
+        return EXIT_SUCCESS;
+}