// Main.cpp

#include <cstdlib>
#include <ctime>
#include <iostream>
#include "mergClassM.h"
//#include "DoublyLinkedList.hpp"

using namespace std;

int compare(const int& a, const int& b)
{
	return a - b;
}


template<class T>
class DoublyLinkedList;

// Link.hpp

template<class T>
class Link
{
private:
	T data;
	Link<T> *next;
	Link<T> *previous;
public:
	Link(T data);
	Link(T data, Link<T> * next, Link<T> * previous);
	void displayLink();
	T getData();
	void setData(T data);
	Link<T> *getNext();
	void setNext(Link<T> *next);
	Link<T> *getPrevious();
	void setPrevious(Link<T> *previous);	
	friend std::ostream& operator<< (std::ostream& print, Link<T>& obj);
	friend class DoublyLinkedList<T>;
};

template<class T>
Link<T>::Link(T data)
	: Link(data, nullptr, nullptr)
{
}

template<class T>
Link<T>::Link(T data, Link<T> * next, Link<T> * previous)
	: data(data), next(next), previous(previous)
{
}

template<class T>
void Link<T>::displayLink()
{
	std::cout << getData() << " ";
}

template<class T>
T Link<T>::getData()
{
	return data;
}

template<class T>
void Link<T>::setData(T data)
{
	this->data = data;
}

template<class T>
Link<T> *Link<T>::getNext()
{
	return next;
}

template<class T>
void Link<T>::setNext(Link<T> *next)
{
	this->next = next;
}

template<class T>
Link<T> *Link<T>::getPrevious()
{
	return previous;
}

template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
	this->previous = previous;
}


template <class T>
std::ostream& operator<<(std::ostream& print, Link<T> & L)
{
	print << L.getData();
	return print;
}

//DoublyLinkedList.hpp


//#include "Link.hpp"

template<class T>
class DoublyLinkedList
{
private:
	Link<T> *first;
	Link<T> *last;
	Link<T> *headdel();
	void tailins(Link<T> *p);
public:
	DoublyLinkedList();
	~DoublyLinkedList();
	Link<T> *getFirst();
	void setFirst(Link<T> *first);
	Link<T> *getLast();
	void setLast(Link<T> *first);
	bool isEmpty();
	Link<T> *find(T key);
	void insertFirst(T dd);
	void insertLast(T dd);
	void deleteFirst();
	void deleteLast();
	void insert(T k, int(*compare)(const T&, const T&));
	bool insertAfter(T key, T dd);
	void deleteKey(T key);
	void displayForward();
	void displayBackward();
	bool Split(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&));
	void Merge(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&));
	void MergeSort(int(*compare)(const T&, const T&));
};

//template<class T>
//using Link = typename DoublyLinkedList<T>::Link;

template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
	: first(nullptr), last(nullptr)
{
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
	while (!isEmpty())
	{
		deleteFirst();
	}
}

template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
	return first;
}

template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
	this->first = first;
}

template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
	return last;
}

template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
	this->last = last;
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
	return getFirst() == nullptr;
}

template<class T>
Link<T> *DoublyLinkedList<T>::find(T key)
{
	Link<T> *current = getFirst();
	while (current != nullptr && !(current->getData == key))
		current = current->getNext();
	return current;
}

template<class T>
void DoublyLinkedList<T>::insertFirst(T dd)
{
	Link<T> *newLink = new Link<T>(dd);
	if (isEmpty())
		setLast(newLink);
	else
		getFirst()->setPrevious(newLink);
	newLink->setNext(getFirst());
	setFirst(newLink);
}

template <class T>
void DoublyLinkedList<T>::insert(T value, int(*compare)(const T&, const T&))
{
	// wskazanie na wskaźnik wskazujący węzeł następujący po nowo dodawanym
	Link<T> **addrNextPtr = &first; // adres pola składowego klasy, nie kopii wskaźnika zwracanego przez getFirst()
	// znajdujemy odpowiednie miejsce do wstawienia wartości
	while (*addrNextPtr && compare(value, (*addrNextPtr)->data) > 0)
	{
		addrNextPtr = &(*addrNextPtr)->next; // adres pola składowego węzła, nie kopii wskaźnika zwracanego przez getNext();
	}

	// wskazanie na wskaźnik wskazujący węzeł poprzedzający nowo dodawany
	Link<T> **addrPrevPtr =
		*addrNextPtr // jeśli wstawiamy przed jakiś węzeł (jeśli jest kolejny węzeł)
		? &(*addrNextPtr)->previous // to wskazujemy adres poprzednika następnego węzła
		: &last; // w przeciwnym razie wskazujemy na adres ostatniego elementu
	//
	// powyższa "linijka" bardziej rozwięźle:
	// Link<T> **addrPrevPtr;
	// if (*addrNextPtr)
	// {
	// 	addrPrevPtr = &(*addrNextPtr)->previous;
	// }
	// else
	// {
	// 	addrPrevPtr = &last;
	// }

	// tworzymy węzeł z odpowiednimi wskazaniami oraz ustawiamy odpowiednie wskazania na nowy węzeł
	*addrNextPtr = *addrPrevPtr = new Link<T>(value, *addrNextPtr, *addrPrevPtr);
	// powyższa linijka bardziej rozwięźle:
	// Link<T> *newNode = new Link<T>(value, *addrNextPtr, *addrPrevPtr);
	// *addrNextPtr = *addrPrevPtr = newNode;
	//
	// jeszcze bardziej rozwięźle:
	// Link<T> *newNode = new Link<T>(value);
	// newNode-next = *addrNextPtr;
	// newNode->previous = *addrPrevPtr;
	// *addrNextPtr = newNode;
	// *addrPrevPtr = newNode;
}

template<class T>
void DoublyLinkedList<T>::insertLast(T dd)
{
	Link<T> *newLink = new Link<T>(dd);
	if (isEmpty())
	{
		setFirst(newLink);
	}
	else
	{
		getLast()->setNext(newLink);
		newLink->setPrevious(getLast());
	}
	setLast(newLink);
}

template<class T>
void DoublyLinkedList<T>::deleteFirst()
{
	if (isEmpty())
		return;
	Link<T> *temp = getFirst();
	if (getFirst()->getNext() == nullptr)
		setLast(nullptr);
	else
		getFirst()->getNext()->setPrevious(nullptr);
	setFirst(getFirst()->getNext());
	delete temp;
}

template<class T>
void DoublyLinkedList<T>::deleteLast()
{
	if (isEmpty())
		return;
	Link<T> *temp = getLast();
	if (getFirst()->getNext() == nullptr)
		setFirst(nullptr);
	else
		getLast()->getPrevious()->setNext(nullptr);
	setLast(getLast()->getPrevious());
	delete temp;
}

template<class T>
bool DoublyLinkedList<T>::insertAfter(T key, T dd)
{
	Link<T> *current = find(key);
	if (current == nullptr)
		return false;
	Link<T> *newLink = new Link<T>(dd);
	if (current->getNext() == nullptr)
	{
		newLink->setNext(nullptr);
		setLast(newLink);
	}
	else
	{
		newLink->setNext(current->getNext());
		current->getNext()->setPrevious(newLink);
	}
	newLink->setPrevious(current);
	current->setNext(newLink);
	return true;
}

template<class T>
void DoublyLinkedList<T>::deleteKey(T key)
{
	Link<T> *current = find(key);
	if (current == nullptr)
		return;
	if (current->getPrevious() == nullptr)
		setFirst(current->getNext());
	else
		current->getPrevious()->setNext(current->getNext());
	if (current->getNext() == nullptr)
		setLast(current->getPrevious());
	else
		current->getNext()->setPrevious(current->getPrevious());
	delete current;
}

template<class T>
void DoublyLinkedList<T>::displayForward()
{
	std::cout << "List (first-->last): ";
	Link<T> *current = getFirst();
	while (current != nullptr)
	{
		current->displayLink();
		current = current->getNext();
	}
	std::cout << "\n";
}

template<class T>
void DoublyLinkedList<T>::displayBackward()
{
	std::cout << "List (last-->first): ";
	Link<T> *current = getLast();
	while (current != nullptr)
	{
		current->displayLink();
		current = current->getPrevious();
	}
	std::cout << "\n";
}

template <class T>
Link<T> *DoublyLinkedList<T>::headdel()
{
	Link<T> *temp = getFirst();
	if (!isEmpty())
	{
		if (getFirst()->getNext() == nullptr)
			setLast(nullptr);
		else
			getFirst()->getNext()->setPrevious(nullptr);
		setFirst(getFirst()->getNext());
	}
	return temp;
}

template <class T>
void DoublyLinkedList<T>::tailins(Link<T> *p)
{
	p->setNext(nullptr);
	if (isEmpty())
	{
		p->setPrevious(nullptr);
		setFirst(p);
	}
	else
	{
		getLast()->setNext(p);
		p->setPrevious(getLast());
	}
	setLast(p);
}

template <class T>
bool DoublyLinkedList<T>::Split(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&))
{
	bool isEmptyB, swapLists;
	Link<T> *currNode = nullptr;
	Link<T> *prevNode = nullptr;
	isEmptyB = true;
	swapLists = true;
	if (!isEmpty())
	{
		currNode = headdel();
		A.tailins(currNode);
		prevNode = currNode;
	}
	while (!isEmpty())
	{
		currNode = headdel();
		if (compare(prevNode->getData(), currNode->getData()) > 0)
			swapLists = !swapLists;
		if (swapLists)
			A.tailins(currNode);
		else
		{
			B.tailins(currNode);
			isEmptyB = false;
		}
		prevNode = currNode;
	}
	return isEmptyB;
}

template <class T>
void DoublyLinkedList<T>::Merge(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&))
{
	Link<T> *tmpA = nullptr;
	Link<T> *tmpB = nullptr;
	Link<T> *poprzedniZtmpA = nullptr;
	Link<T> *poprzedniZtmpB = nullptr;
	bool koniecSeriiWtmpA, koniecSeriiWtmpB;
	if (!A.isEmpty())
	{
		tmpA = A.headdel();
	}
	if (!B.isEmpty())
	{
		tmpB = B.headdel();
	}
	koniecSeriiWtmpA = (tmpA == nullptr);
	koniecSeriiWtmpB = (tmpB == nullptr);
	while (tmpA != nullptr || tmpB != nullptr)
	{
		while (!koniecSeriiWtmpA && !koniecSeriiWtmpB)
			if (compare(tmpA->getData(), tmpB->getData()) <= 0)
			{
				tailins(tmpA);
				poprzedniZtmpA = tmpA;
				tmpA = A.headdel();
				if (tmpA == nullptr || compare(poprzedniZtmpA->getData(), tmpA->getData()) > 0)
					koniecSeriiWtmpA = true;
			}
			else
			{
				tailins(tmpB);
				poprzedniZtmpB = tmpB;
				tmpB = B.headdel();
				if (tmpB == nullptr || compare(poprzedniZtmpB->getData(), tmpB->getData()) > 0)
					koniecSeriiWtmpB = true;
			}
		while (!koniecSeriiWtmpA)
		{
			tailins(tmpA);
			poprzedniZtmpA = tmpA;
			tmpA = A.headdel();
			if (tmpA == nullptr || compare(poprzedniZtmpA->getData(), tmpA->getData()) > 0)
				koniecSeriiWtmpA = true;
		}
		while (!koniecSeriiWtmpB)
		{
			tailins(tmpB);
			poprzedniZtmpB = tmpB;
			tmpB = B.headdel();
			if (tmpB == nullptr || compare(poprzedniZtmpB->getData(), tmpB->getData()) > 0)
				koniecSeriiWtmpB = true;
		}
		koniecSeriiWtmpA = (tmpA == nullptr);
		koniecSeriiWtmpB = (tmpB == nullptr);
		poprzedniZtmpA = nullptr;
		poprzedniZtmpB = nullptr;
	}
}

template <class T>
void DoublyLinkedList<T>::MergeSort(int(*compare)(const T&, const T&))
{
	bool isEmptyB = false;
	DoublyLinkedList<T> L1, L2;
	while (!isEmptyB)
	{
		isEmptyB = Split(L1, L2, compare);
		if (!isEmptyB)
			Merge(L1, L2, compare);
	}
	setFirst(L1.getFirst());
	setLast(L1.getLast());
	L1.setFirst(nullptr);
	L1.setLast(nullptr);
}

int main(int argc, char *argv[])
{
	int k, n, m;
	DoublyLinkedList<int> L;
	srand(time(nullptr));
	cin >> n >> m;
	for (k = 1; k <= n; k++)
		L.insert(rand() % m, compare);
	L.displayForward();
	L.displayBackward();
	L.MergeSort(compare);
	L.displayForward();
	L.displayBackward();
	while (!L.isEmpty())
		L.deleteFirst();
	system("PAUSE");
	return EXIT_SUCCESS;
}