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_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;
}