1 files changed, 81 insertions, 9 deletions

diff --git a/arraylist.c b/arraylist.c
index 420dc0b..668278e 100644
--- a/arraylist.c
+++ b/arraylist.c
@@ -160,22 +160,22 @@ ArrayList_removeAt(struct ArrayList *arrayList, size_t idx, void clear_func(T *,
         --arrayList->size;
 }
 
-struct ArrayList_sort_ctx {
+struct qsortHelper_context {
         int (*cmp)(const T *, const T *, void *);
         void *args;
 };
 
-typedef const T *const_ptr;
+typedef const T *const_T_ptr;
 
 static int
-ArrayList_compareAdapter(void *ctx, const void *a, const void *b)
+ArrayList_qsortHelper(void *ctx, const void *a, const void *b)
 {
-        const const_ptr *aa = a;
-        const const_ptr *bb = b;
+        const const_T_ptr *aa = a;
+        const const_T_ptr *bb = b;
 
-        const struct ArrayList_sort_ctx *sort_ctx = ctx;
+        const struct qsortHelper_context *context = ctx;
 
-        return sort_ctx->cmp(*aa, *bb, sort_ctx->args);
+        return context->cmp(*aa, *bb, context->args);
 }
 
 void
@@ -184,12 +184,65 @@ ArrayList_sort(struct ArrayList *arrayList, int cmp(const T *, const T *, void *
         assert(arrayList != NULL);
         assert(cmp != NULL);
 
-        struct ArrayList_sort_ctx sort_ctx = {
+        struct qsortHelper_context context = {
                 .cmp  = cmp,
                 .args = args
         };
 
-        qsort_r(arrayList->array, arrayList->size, sizeof(arrayList->array[0]), &sort_ctx, ArrayList_compareAdapter);
+        // 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 *), size_t *loc)
+{
+        assert(arrayList != NULL);
+        assert(cmp != NULL);
+        assert(loc != NULL);
+
+        for ( size_t idx = 0; idx != arrayList->size; ++idx ) {
+                if ( cmp(key, arrayList->array[idx]) == 0 ) {
+                        *loc = idx;
+                        return true;
+                }
+        }
+        return false;
+}
+
+struct bsearchHelper_context {
+        void *key;
+        int (*cmp)(void *, const T *);
+};
+
+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);
+}
+
+bool
+ArrayList_binarySearch(struct ArrayList *arrayList, void *key, int cmp(void *, const T *), size_t *loc)
+{
+        assert(arrayList != NULL);
+        assert(cmp != NULL);
+        assert(loc != NULL);
+
+        struct bsearchHelper_context context = {
+                .key = key,
+                .cmp = cmp
+        };
+
+        T **pos = bsearch(&context, arrayList->array, arrayList->size, sizeof(arrayList->array[0]), ArrayList_bsearchHelper);
+        if ( pos != NULL ) {
+                *loc = (size_t)(pos - arrayList->array);
+                return true;
+        }
+        else {
+                return false;
+        }
 }
 
 void
@@ -236,6 +289,19 @@ my_compare(const T *a, const T *b, void *args)
         }
 }
 
+static int
+my_search_compare(void *key, const T *element)
+{
+        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)
 {
@@ -280,6 +346,12 @@ main(void)
 
         ArrayList_debugPrint(arrayList); // 11, 22, 33, 44
 
+        size_t loc;
+        int    dummy = 44;
+        if ( ArrayList_binarySearch(arrayList, &dummy, my_search_compare, &loc) ) {
+                printf("Gefunden: %zu\n", loc);
+        }
+
         ArrayList_shuffle(arrayList, my_rng, NULL);
         ArrayList_debugPrint(arrayList); // ??