path: root/arraylist.c

/* 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 != 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_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 != 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 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 != NULL);
	assert(cmp != NULL);

	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 != NULL);
	assert(cmp != NULL);
	assert(loc != NULL);

	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 != NULL);
	assert(cmp != NULL);
	assert(loc != NULL);

	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 != NULL ) {
		*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 != 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 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;
}