/*
 * linked_list_tests.cpp
 *
 *  Created on: 14.11.2013
 *      Author: trifon
 */

#include "test.h"
#include "linked_list.cpp"
#include <queue>

typedef LinkedList<int> TestList;

bool createEmptyTest() {
	return TestList().empty();
}

bool toEndEmptyTest() {
	TestList l;
	l.toEnd(1);
	return !l.empty();
}

bool toEndTest() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	// cout << l;
	int i = 1;
	for(TestList::I it = l.begin(); it; it++, i++)
		if (*it != i)
			return false;

	return i == 11;
}

bool insertBeforeTest() {
	TestList l;
	for(int i = 1; i <= 5; i++)
		l.toEnd(i*2);
	int i = 1;
	for(TestList::I it = l.begin(); it; it++, i+=2)
		l.insertBefore(i, it);
	// cout << l;
	// да проверим дали сме получили списъка от 1 до 10
	i = 1;
	for(TestList::I it = l.begin(); it; it++, i++)
		if (*it != i)
			return false;

	return i == 11;
}

bool deleteAfterTest() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	int i = 2;
	for(TestList::I it = l.begin(); it && it != l.end(); it++, i+=2) {
		int j;
		// cout << "i = " << i << endl;
		if (!l.deleteAfter(j, it) || /*cout << j << endl && */
				i != j)
			return false;
	}

	l.toEnd(11);

	return true;
}

bool deleteAtTest() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	int i = 1;
	for(TestList::I it = l.begin(); it; ++(++it), i+=2) {
		TestList::I it2 = it;
		int j;
		if (!l.deleteAt(j, it2) || i != j)
			return false;
	}
	l.toEnd(11);
	// cout << l;
	return true;
}

bool deleteBeforeTest() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	int i = 1;
	TestList::I it = l.begin();
	it++;
	for(; it; ++(++it), i += 2) {
		int j;
		if (!l.deleteBefore(j, it) || i != j)
			return false;
	}
	// cout << l;
	return true;
}

const int NTESTS = 7;
Test tests[] = {
		{ "createEmptyTest", createEmptyTest },
		{ "toEndEmptyTest", toEndEmptyTest },
		{ "toEndTest", toEndTest },
		{ "insertBeforeTest", insertBeforeTest },
		{ "deleteAfterTest", deleteAfterTest },
		{ "deleteAtTest", deleteAtTest },
		{ "deleteBeforeTest", deleteBeforeTest },
};

template <typename T, typename I>
void concat(List<T, I>& dest, List<T, I> const& src) {
	for(I it = src.begin(); it; it++)
		dest.toEnd(*it);
}

void concatLists() {
	TestList l1, l2;
	int i;
	for(i = 1; i <= 10; i++)
		l1.toEnd(i);
	for(;i <= 20; i++)
		l2.toEnd(i);
	concat(l1, l2);
	cout << l1 << endl;
}

template <typename T, typename I>
void reverse(List<T, I>& l) {
	I originalBegin = l.begin();
	while (originalBegin != l.end()) {
		T x;
		l.deleteAfter(x, originalBegin);
		l.insertBefore(x, l.begin());
	}
}

void reverseList() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	reverse(l);
	cout << l << endl;
}

template <typename T, typename I>
void merge(List<T, I> const& l1, List<T, I> const& l2, List<T, I>& l) {
	I it1 = l1.begin(), it2 = l2.begin();
	while (it1 && it2) {
		if (*it1 < *it2)
			l.toEnd(*it1++);
		else
			l.toEnd(*it2++);
	}
	// !it1 || !it2
	while (it1)
		l.toEnd(*it1++);
	while (it2)
		l.toEnd(*it2++);
}

void mergeLists() {
	TestList l1, l2, l;
	for(int i = 1; i <= 5; i++) {
		l1.toEnd(2*i - 1);
		l2.toEnd(2*i);
	}
	cout << l1 << endl;
	cout << l2 << endl;
	merge(l1, l2, l);
	cout << l << endl;
}

template <typename T, typename I>
void split(List<T, I> const& l, List<T, I>& l1, List<T, I>& l2) {
	bool first = true;
	for(I it = l.begin(); it; it++) {
		if (first)
			l1.toEnd(*it);
		else
			l2.toEnd(*it);
		first = !first;
	}
}

void splitList() {
	TestList l,l1,l2;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	split(l, l1, l2);
	cout << l1 << endl;
	cout << l2 << endl;
}

TestList mergeSort(TestList const& l) {
	// дъно
	// списъкът е от 0 или от 1 елемента
	if (l.begin() == l.end())
		return l;
	TestList l1, l2;
	// 1.
	split(l, l1, l2);
	TestList result;
	// 2 & 3
	merge(mergeSort(l1), mergeSort(l2), result);
	return result;
}

void mergeSortList() {
	int n;
	TestList l;
	cout << "n = "; cin >> n;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		l.toEnd(x);
	}
	cout << mergeSort(l) << endl;
}


int main() {
	// runTests(tests, NTESTS);
	concatLists();
	reverseList();
	mergeLists();
	splitList();
	mergeSortList();
	return 0;
}