From f3b075e842cfbccfe668853266c83766bec0e3a3 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 31 Oct 2020 19:03:04 +0100
Subject: Suche in ArrayList hinzugefügt. Sortierfunktion benutzt nun
 einheitliches Namensschema.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 arraylist.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file 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); // ??
 
-- 
cgit v1.3