/* dlist -- double linked list */

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

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

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

struct dlist {
	struct dlist_element *head, *tail;
};

struct dlist_element {
	struct dlist_element *prev, *next;
	T                     data;
};
/* -->8-- */

/* --8<-- dlist_init */
void
dlist_init(struct dlist *dlist)
{
	dlist->head = NULL;
	dlist->tail = NULL;
}
/* -->8-- */

/* --8<-- dlist_empty */
bool
dlist_empty(struct dlist *dlist)
{
	return dlist->head == NULL;
}
/* -->8-- */

/* --8<-- dlist_create_element */
static struct dlist_element *
create_element(T data)
{
	struct dlist_element *element;

	element = malloc(sizeof *element);
	if ( element != NULL ) {
		element->data = data;
	}

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

/* --8<-- dlist_push_front */
struct dlist_element *
dlist_push_front(struct dlist *dlist, T data)
{
	struct dlist_element *element;

	element = create_element(data);
	if ( element != NULL ) {
		element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */

		if ( dlist_empty(dlist) ) {
			element->next = NULL;
			dlist->tail   = element;
		}
		else {
			element->next       = dlist->head;
			element->next->prev = element;
		}

		dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */
	}
	else
		ERROR("out of memory");

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

/* --8<-- dlist_push_back */
struct dlist_element *
dlist_push_back(struct dlist *dlist, T data)
{
	struct dlist_element *element;

	element = create_element(data);
	if ( element != NULL ) {
		element->next = NULL; /* Nachfolger ist in jedem Fall NULL */

		if ( dlist_empty(dlist) ) {
			element->prev = NULL;
			dlist->head   = element;
		}
		else {
			element->prev       = dlist->tail;
			element->prev->next = element;
		}

		dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */
	}
	else
		ERROR("out of memory");

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

/* --8<-- dlist_pop_front */
bool
dlist_pop_front(struct dlist *dlist, T *data)
{
	if ( dlist->head != NULL ) {
		struct dlist_element *element = dlist->head;

		dlist->head = element->next;

		if ( dlist->head == NULL )
			dlist->tail = NULL;
		else
			element->next->prev = NULL;

		if ( data != NULL ) {
			*data = element->data;
		}
		free(element);

		return true;
	}
	else
		return false;
}
/* -->8-- */

/* --8<-- dlist_pop_back */
bool
dlist_pop_back(struct dlist *dlist, T *data)
{
	if ( dlist->head != NULL ) {
		struct dlist_element *element = dlist->tail;

		dlist->tail = element->prev;

		if ( dlist->tail == NULL )
			dlist->head = NULL;
		else
			element->prev->next = NULL;

		if ( data != NULL ) {
			*data = element->data;
		}
		free(element);

		return true;
	}
	else
		return false;
}
/* -->8-- */

/* --8<-- dlist_insert_next */
struct dlist_element *
dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
{
	struct dlist_element *new_element;

	new_element = create_element(data);
	if ( new_element != NULL ) {
		if ( dlist->head == NULL ) {
			dlist->head       = new_element;
			dlist->head->prev = NULL;
			dlist->head->next = NULL;
			dlist->tail       = new_element;
		}
		else {
			new_element->next = element->next;
			new_element->prev = element;

			if ( element->next == NULL )
				dlist->tail = new_element;
			else
				element->next->prev = new_element;

			element->next = new_element;
		}
	}
	else
		ERROR("out of memory");

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

/* --8<-- dlist_insert_prev */
struct dlist_element *
dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
{
	struct dlist_element *new_element;

	new_element = create_element(data);
	if ( new_element != NULL ) {
		if ( dlist->head == NULL ) {
			dlist->head       = new_element;
			dlist->head->prev = NULL;
			dlist->head->next = NULL;
			dlist->tail       = new_element;
		}
		else {
			new_element->next = element;
			new_element->prev = element->prev;

			if ( element->prev == NULL )
				dlist->head = new_element;
			else
				element->prev->next = new_element;

			element->prev = new_element;
		}
	}
	else
		ERROR("out of memory");

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

/* --8<-- dlist_remove */
void
dlist_remove(struct dlist *dlist, struct dlist_element *element)
{
	if ( element == dlist->head ) {
		dlist->head = element->next;

		if ( dlist->head == NULL )
			dlist->tail = NULL;
		else
			element->next->prev = NULL;
	}
	else {
		element->prev->next = element->next;

		if ( element->next == NULL )
			dlist->tail = element->prev;
		else
			element->next->prev = element->prev;
	}

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

/* --8<-- dlist_free */
void
dlist_free(struct dlist *dlist)
{
	struct dlist_element *elem, *next;

	for ( elem = dlist->head; elem; elem = next ) {
		next = elem->next;
		free(elem);
	}

	dlist_init(dlist);
}
/* -->8-- */

void
dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl)
{
	for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) {
		visit(elem->data, cl);
	}
}

void
print_list(const char *msg, struct dlist *dlist)
{
	printf("%s:", msg);

	for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next )
		printf(" %d", elem->data);

	putchar('\n');
}

void
print_list_rev(const char *msg, struct dlist *dlist)
{
	printf("%s:", msg);

	for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
		printf(" %d", elem->data);

	putchar('\n');
}

void
remove_if(struct dlist *list)
{
	struct dlist_element *elem, *next;

	for ( elem = list->head; elem; elem = next ) {
		next = elem->next;

		if ( (elem->data & 1) == 1 ) {
			dlist_remove(list, elem);
		}
	}
}

/* --8<-- dlist_merge */
struct dlist *
dlist_merge(struct dlist *list1, struct dlist *list2)
{
	struct dlist_element *head = NULL,
	                     *cur  = NULL,
	                     *e1   = list1->head,
	                     *e2   = list2->head;

	while ( e1 != NULL && e2 != NULL ) // Solange in e1 UND e2 Elemente sind...
	{
		if ( e1->data < e2->data ) {
			e1->prev = cur;
			if ( cur != NULL )
				cur->next = e1;
			else
				head = e1;
			cur = e1;
			e1  = e1->next;
		}
		else {
			e2->prev = cur;
			if ( cur != NULL )
				cur->next = e2;
			else
				head = e2;
			cur = e2;
			e2  = e2->next;
		}
	}

	if ( e1 != NULL ) // in e1 sind noch Elemente vorhanden!
	{
		assert(e2 == NULL);

		e1->prev = cur;
		if ( cur != NULL )
			cur->next = e1;
		else
			head = e1;

		// list1->tail zeigt bereits auf das letzte Element in list1
	}
	else /* if ( e2 != NULL ) */
	{
		assert(e1 == NULL);
		assert(e2 != NULL);

		e2->prev = cur;
		if ( cur != NULL )
			cur->next = e2;
		else
			head = e2;

		list1->tail = list2->tail; // list2->tail ist das Ende der Liste
	}

	// Kopf neu setzen...
	list1->head = head;

	// Liste2 ist leer
	list2->head = NULL;
	list2->tail = NULL;

	// Zeiger auf Liste1 zurückliefern
	return list1;
}
/* -->8-- */

/* --8<-- dlist_sort */
struct dlist *
dlist_sort(struct dlist *list)
{
	if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig
		return list;

	struct dlist_element *slow = list->head,
	                     *fast = list->head->next;

	while ( fast != NULL && fast->next != NULL )
		slow = slow->next, fast = fast->next->next;

	struct dlist list1 = { .head = list->head, .tail = slow },
	             list2 = { .head = slow->next, .tail = list->tail };

	list1.tail->next = list2.head->prev = NULL;

	dlist_merge(dlist_sort(&list1), dlist_sort(&list2));

	list->head = list1.head;
	list->tail = list1.tail;

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

void
merge_test(void)
{
	struct dlist l1, l2;

	dlist_init(&l1);
	dlist_init(&l2);

	dlist_push_back(&l1, 7);
	dlist_push_back(&l1, 10);
	dlist_push_back(&l1, 11);
	dlist_push_back(&l1, 19);
	dlist_push_back(&l1, 23);

	dlist_push_back(&l2, 4);
	dlist_push_back(&l2, 14);
	dlist_push_back(&l2, 15);

	struct dlist *ptr;
	ptr = dlist_merge(&l1, &l2);

	struct dlist_element *cur;
	for ( cur = ptr->head; cur; cur = cur->next ) {
		if ( cur->prev )
			printf("%4d", cur->prev->data);
		else
			printf("xxx ");
		printf("%4d", cur->data);
		if ( cur->next )
			printf("%4d", cur->next->data);
		else
			printf(" xxx");

		puts("");
	}

	dlist_free(&l1);
	dlist_free(&l2);
}

void
ls()
{
	struct dlist list;

	dlist_init(&list);

	for ( int i = 0; i != 30000000; ++i )
		dlist_insert_prev(&list, list.tail, rand() % 9999);

	//print_list("Unsortiert:", &list);
	printf("start\n");
	clock_t start = clock();
	dlist_sort(&list);
	clock_t ende = clock();

	printf("Dauer: %.3fsec\n", ((double) ende - start) / CLOCKS_PER_SEC);
	//print_list("Sortiert:", &list);
	//print_list_rev("Sortiert:", &list);

	dlist_free(&list);
}

int
main(void)
{
	ls();

#if 0
	merge_test();
#endif

#if 0
	struct dlist list;

	dlist_init(&list);

	for ( int i = 0; i != 10; ++i )
		dlist_insert_prev(&list, list.tail, i);

	print_list("Ausgabe: ", &list);

	remove_if(&list);

	print_list("Ausgabe: ", &list);

	dlist_free(&list);

	ls();

	return EXIT_SUCCESS;
#endif
}