/* simple Implementation of single linked lists */
/* written and placed in the public domain by Thomas Schmucker */

/* Standard C */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Project */
#include "util.h"

/* --8<-- list_type */
typedef int T;

struct list_item {
	struct list_item *next;
	T                 data;
};
/* -->8-- */

/* --8<-- list_add */
struct list_item *
list_add(struct list_item *next, T data)
{
	struct list_item *new_item;

	new_item = malloc(sizeof *new_item);
	if ( new_item ) {
		new_item->data = data;
		new_item->next = next;
	}
	else {
		ERROR("out of memory");
	}

	return new_item;
}
/* -->8-- */

/* --8<-- list_insert_next */
void
list_insert_next(struct list_item *list, T data)
{
	struct list_item *new_item;

	new_item = list_add(list->next, data);
	if ( new_item ) {
		list->next = new_item;
	}
	else {
		ERROR("out of memory");
	}
}
/* -->8-- */

/* --8<-- list_delete */
struct list_item *
list_delete(struct list_item *list, T data)
{
	struct list_item *prev = NULL;

	for ( struct list_item *p = list; p; p = p->next ) {
		if ( p->data == data ) {
			if ( prev == NULL ) { /* first element in list? */
				list = p->next;
			}
			else {
				prev->next = p->next;
			}

			free(p);

			return list;
		}
		prev = p;
	}
#ifdef LIST_REPORT_ERROR
	ERROR("data not found");
#endif
	return list;
}
/* -->8-- */

/* --8<-- list_delete_next */
void
list_delete_next(struct list_item *list)
{
	if ( list->next ) {
		struct list_item *temp = list->next;

		list->next = list->next->next;

		free(temp);
	}
}
/* -->8-- */

/* --8<-- list_length */
size_t
list_length(struct list_item *list)
{
	size_t len = 0;

	for ( ; list; list = list->next ) {
		++len;
	}

	return len;
}
/* -->8-- */

/* --8<-- list_copy */
struct list_item *
list_copy(struct list_item *list)
{
	struct list_item *head = NULL, **p = &head;

	for ( ; list; list = list->next ) {
		*p = malloc(sizeof **p);
		if ( *p ) {
			(*p)->data = list->data; // copy elements
			p          = &(*p)->next;
		}
		else {
			ERROR("out of memory");
		}
	}
	*p = NULL;
	return head;
}
/* -->8-- */

/* --8<-- list_reverse */
struct list_item *
list_reverse(struct list_item *list)
{
	struct list_item *head = NULL, *next;

	for ( ; list; list = next ) {
		next       = list->next;
		list->next = head;
		head       = list;
	}
	return head;
}
/* -->8-- */

/* --8<-- list_apply */
void
list_apply(struct list_item *list, void (*visit)(T data, void *cl), void *cl)
{
	for ( ; list; list = list->next ) {
		visit(list->data, cl);
	}
}
/* -->8-- */

/* --8<-- list_merge */
struct list_item *
list_merge(struct list_item *a, struct list_item *b)
{
	struct list_item  dummy = { .next = NULL };
	struct list_item *head = &dummy, *c = head;

	while ( a && b )
		if ( a->data < b->data ) {
			c->next = a, c = a, a = a->next;
		}
		else {
			c->next = b, c = b, b = b->next;
		}

	c->next = a ? a : b;

	return head->next;
}
/* -->8-- */

/* --8<-- list_sort */
struct list_item *
list_sort(struct list_item *c)
{
	if ( c == NULL || c->next == NULL )
		return c;

	struct list_item *a = c,
	                 *b = c->next;

	while ( b && b->next ) {
		c = c->next, b = b->next->next;
	}

	b = c->next, c->next = NULL;

	return list_merge(list_sort(a), list_sort(b));
}
/* -->8-- */

/* --8<-- list_free */
void
list_free(struct list_item *list)
{
	struct list_item *next;

	for ( ; list; list = next ) {
		next = list->next;
		free(list);
	}
}
/* -->8-- */

/* --8<-- list_apply_sample */
static void
print_data(T data, void *cl)
{
	fprintf(cl, "%d\n", data);
}
/* -->8-- */

int
main()
{
	clock_t start;

	/*
	struct list_item *mylist = NULL;

	mylist = list_add(mylist, 42);
	mylist = list_add(mylist, 43);
	mylist = list_add(mylist, 44);

	mylist = list_delete(mylist, 45);

	list_apply(mylist, print_data, stdout);

	struct list_item *mylist2 = list_reverse(list_copy(mylist));

	list_free(mylist);
	list_apply(mylist2, print_data);
	list_free(mylist2);
	*/

	srand(time(NULL));

	static const int COUNT = 10000000;

	struct list_item *x = NULL;
	for ( int i = 0; i != COUNT; ++i ) {
		int r = rand();
		x     = list_add(x, r);
	}

	puts("start");
	start = clock();
	x     = list_sort(x);
	printf("Fertig: %.3lf sec\n", (double) (clock() - start) / CLOCKS_PER_SEC);

	//list_apply(x, print_data);
	printf("Len: %zu\n", list_length(x));

	list_free(x);

	return EXIT_SUCCESS;
}