From 784f93c625260942c1961c3034ee9b57d253c696 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 31 Oct 2020 09:10:07 +0100 Subject: Import ArrayList-Implementation --- arraylist.c | 295 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 295 insertions(+) create mode 100644 arraylist.c (limited to 'arraylist.c') 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 +#include +#include +#include +#include +#include + +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; +} -- cgit v1.3