#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

struct TNode
{
	int data;
	struct TNode *next;
	struct TNode *prev;
};

struct TList
{
	struct TNode *head;
	struct TNode *tail;
};

void ListInit(struct TList *L)
{
	assert(L);
	L->head = NULL;
	L->tail = NULL;
}

int ListIsEmpty(struct TList *L)
{
	assert(L);
	return L->head == NULL;
}

void ListDisplayForward(struct TList* L)
{
	assert(L);
	int counter = 0;
	struct TNode *curr = L->head;
	printf("List (head-->tail): ");
	while (curr != NULL)
	{
		printf("%d -> ", curr->data);
		curr = curr->next;
		counter++;
	}
	printf("NULL \n");
	printf("Liczba wezlow listy: %d \n", counter);
}

void ListDisplayBackward(struct TList* L)
{
	assert(L);
	int counter = 0;
	struct TNode *curr = L->tail;
	printf("List (tail-->head): ");
	while (curr != NULL)
	{
		printf("%d -> ", curr->data);
		curr = curr->prev;
		counter++;
	}
	printf("NULL \n");
	printf("Liczba wezlow listy: %d \n", counter);
}

void ListInsertNodeTail(struct TList *L, struct TNode *p)
{
	assert(L);
	assert(p);
	p->next = NULL;
	if (L->head == NULL)
	{
		p->prev = NULL;
		L->head = p;
	}
	else
	{
		L->tail->next = p;
		p->prev = L->tail;
	}
	L->tail = p;
}

void ListInsertValueTail(struct TList *L, int k)
{
	assert(L);
	struct TNode *node = (struct TNode *)malloc(sizeof(struct TNode));
	assert(node);
	node->data = k;
	ListInsertNodeTail(L, node);
}

struct TNode *ListDetachHead(struct TList *L)
{
	assert(L);
	struct TNode *temp = L->head;
	if (L->head)
	{
		if (L->head->next == NULL)
			L->tail = NULL;
		else
			L->head->next->prev = NULL;
		L->head = L->head->next;
	}
	return temp;
}

void ListDeleteHead(struct TList *L)
{
	assert(L);
	free(ListDetachHead(L));
}

void ListDelete(struct TList *L)
{
	assert(L);
	while (!ListIsEmpty(L))
		ListDeleteHead(L);
}

void SwapNodePointers(struct TNode **A, struct TNode **B)
{
	assert(A);
	assert(B);
	struct TNode *tmp = *A;
	*A = *B;
	*B = tmp;
}

void SwapListPointers(struct TList **A, struct TList **B)
{
	assert(A);
	assert(B);
	struct TList *tmp = *A;
	*A = *B;
	*B = tmp;
}

int ListSplit(struct TList *L, struct TList *A, struct TList *B)
{
	assert(L);
	assert(A);
	assert(B);
	// prevNode trzeba zainicjalizowac nullem, coby się nie wysypać na początku
	struct TNode *currNode, *prevNode = NULL;
	ListInit(A);
	ListInit(B);
	while (currNode = ListDetachHead(L)) // "odłączamy głowę", dopóki nie zwróci nulla
	{
		// jeśli mamy początek nowej serii, to zamieniamy ze sobą wskaźniki do list,
		// w ten sposób poniższy kod zapisujący do A będzie zapisywał naprzemiennie do list A, B
		//  (coby kod niżej był prostszy - jeden przypadek zamiast dwóch)
		if (prevNode && prevNode->data > currNode->data)
			SwapListPointers(&A, &B);

		// zawsze zapisujemy do A, ale A nie zawsze wskazuje tę samą listę
		ListInsertNodeTail(A, currNode);
		// pamiętamy poprzednią wartość (węzeł z wartością), coby wykryć koniec aktualnej serii
		prevNode = currNode;
	}
	return ListIsEmpty(B);
}

void ListMerge(struct TList* A, struct TList* B, struct TList *L)
{
	assert(L);
	assert(A);
	assert(B);
	struct TNode *tmpA, *tmpB, *prevA, *prevB;
	tmpA = ListDetachHead(A); // akutalna wartość z A
	tmpB = ListDetachHead(B); // akutalna wartość z B
	ListInit(L);
	while (tmpA && tmpB) // obie serie niepuste
	{
		// zapewnienie, że w A mamy serię z aktualnie niewiększą wartością,
		// w razie potrzeby zamieniamy odpowiednie wskaźniki
		//  (coby kod niżej był prostszy - jeden przypadek zamiast dwóch)
		if (tmpA->data > tmpB->data)
		{
			SwapNodePointers(&tmpA, &tmpB);
			SwapNodePointers(&prevA, &prevB);
			SwapListPointers(&A, &B);
		}

		// przepisanie aktualnej wartości z serii w A (czyli wartości niewiększej od tej z B)
		ListInsertNodeTail(L, tmpA);
		// i pobranie kolejnej
		prevA = tmpA;
		tmpA = ListDetachHead(A);

		// sprawdzenie, czy była to ostatnia liczba z serii
		if (!tmpA || tmpA->data < prevA->data)
		{
			// jeśli tak, przenosimy do końca aktualną serię z B (na pewno jest niepusta)
			do
			{
				ListInsertNodeTail(L, tmpB);
				prevB = tmpB;
				tmpB = ListDetachHead(B);
			} while (tmpB && prevB->data <= tmpB->data);
		}
	}
	// w którejś z list (ale tylko jednej) mogły zostać jeszcze jakieś serie
	// upewniamy się, że ewentualne "resztki" są w A
	// (tu wskaźnik tmp można nadpisać, ale wskaźniki do list trzeba ewentualnie podmienić)
	if (!tmpA)
	{
		tmpA = tmpB;
		SwapListPointers(&A, &B);
	}
	// przenosimy ewentualne "resztki"
	while (tmpA)
	{
		ListInsertNodeTail(L, tmpA);
		tmpA = ListDetachHead(A);
	}
}

int main()
{
	int k, n, m;
	struct TList L, L1, L2;
	ListInit(&L);
	srand(time(NULL));
	n = 20; m = 50;
	//scanf("%d %d", &n, &m);
	for (k = 1; k <= n; k++)
		ListInsertValueTail(&L, rand() % m);

	printf("List L \n");
	ListDisplayForward(&L);
	ListDisplayBackward(&L);

	ListSplit(&L, &L1, &L2);

	printf("\nList L1 \n");
	ListDisplayForward(&L1);
	ListDisplayBackward(&L1);
	printf("\nList L2 \n");
	ListDisplayForward(&L2);
	ListDisplayBackward(&L2);

	ListMerge(&L1, &L2, &L);

	printf("\nList L \n");
	ListDisplayForward(&L);
	ListDisplayBackward(&L);

	ListDelete(&L);

	system("PAUSE");
	return 0;
}