Import ArrayList-Implementation

1 files changed, 295 insertions, 0 deletions

diff --git a/arraylist.c b/arraylist.c
new file mode 100644
index 0000000..21b8229
--- /dev/null
+++ b/arraylist.c
@@ -0,0 +1,295 @@
+/* arraylist */
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+typedef int T;
+
+struct ArrayList {
+        T **   array;
+        size_t size;
+        size_t capacity;
+};
+
+// Utils...
+static void
+ERROR(const char *msg)
+{
+        fprintf(stderr, "Error: %s\n", msg);
+        exit(EXIT_FAILURE);
+}
+
+static T **
+ArrayList_allocate(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 != NULL);
+
+        arrayList->array    = NULL;
+        arrayList->size     = 0;
+        arrayList->capacity = 0;
+}
+
+struct ArrayList *
+ArrayList_new(void)
+{
+        struct ArrayList *arrayList = malloc(sizeof *arrayList);
+        if ( arrayList != NULL ) {
+                ArrayList_init(arrayList);
+        }
+        return arrayList;
+}
+
+void
+ArrayList_free(struct ArrayList *arrayList)
+{
+        assert(arrayList != NULL);
+
+        free(arrayList->array);
+        ArrayList_init(arrayList);
+}
+
+void
+ArrayList_delete(struct ArrayList *arrayList)
+{
+        assert(arrayList != NULL);
+
+        ArrayList_free(arrayList);
+        free(arrayList);
+}
+
+static void
+ArrayList_growIfNeeded(struct ArrayList *arrayList)
+{
+        assert(arrayList != NULL);
+
+        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_allocate(NULL, DEFAULT_CAPACITY);
+                }
+                else {
+                        size_t new_capacity  = (arrayList->capacity * 3) / 2; // *= 1.5
+                        T **   new_arrayList = ArrayList_allocate(arrayList->array, new_capacity);
+
+                        arrayList->capacity = new_capacity;
+                        arrayList->array    = new_arrayList;
+                }
+
+                assert(arrayList->array != NULL);
+        }
+}
+
+void
+ArrayList_append(struct ArrayList *arrayList, T *ptr)
+{
+        assert(arrayList != NULL);
+
+        ArrayList_growIfNeeded(arrayList);
+
+        arrayList->array[arrayList->size++] = ptr;
+}
+
+void
+ArrayList_insertAt(struct ArrayList *arrayList, size_t idx, T *ptr)
+{
+        assert(arrayList != NULL);
+        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 != NULL);
+        assert(idx < arrayList->size);
+
+        return arrayList->array[idx];
+}
+
+size_t
+ArrayList_size(struct ArrayList *arrayList)
+{
+        assert(arrayList != NULL);
+
+        return arrayList->size;
+}
+
+bool
+ArrayList_empty(struct ArrayList *arrayList)
+{
+        assert(arrayList != NULL);
+
+        return arrayList->size == 0;
+}
+
+void
+ArrayList_removeAt(struct ArrayList *arrayList, size_t idx, void clear_func(T *, void *), void *args)
+{
+        assert(arrayList != NULL);
+        assert(idx < arrayList->size);
+
+        if ( clear_func != NULL ) {
+                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 ArrayList_sort_ctx {
+        int (*cmp)(const T *, const T *, void *);
+        void *args;
+};
+
+typedef const T *const_ptr;
+
+static int
+ArrayList_compareAdapter(void *ctx, const void *a, const void *b)
+{
+        const const_ptr *aa = a;
+        const const_ptr *bb = b;
+
+        const struct ArrayList_sort_ctx *sort_ctx = ctx;
+
+        return sort_ctx->cmp(*aa, *bb, sort_ctx->args);
+}
+
+void
+ArrayList_sort(struct ArrayList *arrayList, int cmp(const T *, const T *, void *), void *args)
+{
+        assert(arrayList != NULL);
+        assert(cmp != NULL);
+
+        struct ArrayList_sort_ctx sort_ctx = {
+                .cmp  = cmp,
+                .args = args
+        };
+
+        qsort_r(arrayList->array, arrayList->size, sizeof(arrayList->array[0]), &sort_ctx, ArrayList_compareAdapter);
+}
+
+void
+ArrayList_shuffle(struct ArrayList *arrayList, size_t rng(size_t, void *), void *args)
+{
+        assert(arrayList != NULL);
+        assert(rng != NULL);
+
+        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 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
+
+        ArrayList_shuffle(arrayList, my_rng, NULL);
+        ArrayList_debugPrint(arrayList); // ??
+
+        ArrayList_delete(arrayList);
+
+        return EXIT_SUCCESS;
+}