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

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

typedef DoubleLinkedList<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;
}

bool copyTest() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	TestList cl = l;
	TestList::I it = l.begin();
	*it = 20;
	return *cl.begin() == 1;
}

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

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;
}

template <typename T, typename U, typename I>
U foldl(List<T, I> const& l, U nv, U (*op)(U,T)) {
	U result = nv;
	for(I it = l.begin(); it; ++it)
		result = op(result, *it);
	return result;
}

template <typename T, typename U, typename I>
U foldr_help(I& it, U nv, U (*op)(T,U)) {
	if (!it)
		return nv;
	T x = *it;
	return op(x, foldr_help(++it, nv, op));
}

template <typename T, typename U, typename I>
U foldr(List<T, I> const& l, U nv, U (*op)(T,U)) {
	I it = l.begin();
	return foldr_help(it, nv, op);
}

template <typename T, typename I>
List<T, I>& map(List<T, I>& l,T (*f)(T)) {
	for(I it = l.begin(); it; ++it)
		*it = f(*it);
	return l;
}

template <typename T, typename I>
List<T, I>& filter(List<T, I>& l, bool (*p)(T)) {
	if (l.empty()) // !!!
		return l;
	I it = l.begin(), pit = it++;
	T x;
	while (it) {
		if (!p(*it)) {
			l.deleteAfter(x, pit);
			it = pit;
		} else
			++pit;
		++it;
	}
	it = l.begin();
	if (!p(*it)) {
		// трябва да изтрием първия елемент
		l.deleteAt(x, it);
	}
	return l;
}

int add(int x, int y) { return x + y; }
int square(int x) { return x * x; }
bool odd(int x) { return x % 2 == 1; }

void sumList() {
	TestList l;
	for(int i = 1; i <= 10; i++)
		l.toEnd(i);
	cout << foldl(l, 0, add) << endl;
	cout << foldr(l, 0, add) << endl;
	cout << foldl(map(filter(l, odd),square), 0, add);
}

// списък от списъци
// сумата на елементите на всички списъци, които съдържат положително число

bool isPositive(int x) { return x > 0; }

bool hasPositive(LinkedList<int> l) {
	return !filter(l, isPositive).empty();
}

LinkedList<int> addNewSum(LinkedList<int> r, LinkedList<int> l) {
	r.toEnd(foldl(l,0,add));
	return r;
}

void sum2List() {
	LinkedList<LinkedList<int> > ll;
	for(int i = 1; i <= 10; i++) {
		LinkedList<int> l;
		for(int j = -i; j <= i-2; j++)
			l.toEnd(j);
		ll.toEnd(l);
		cout << hasPositive(l) << endl;
	}
	cout << ll << endl;
	// T = LinkedList<int>
	// U = LinkedList<int>
	cout << foldl(
				foldl(
					filter(ll, hasPositive),
				LinkedList<int>(),
				addNewSum),
			0, add);
}

template <typename T>
bool isPalindrome(DoubleLinkedList<T> const& dl) {
	// или DoubleLinkedListIterator<T>
	typename DoubleLinkedList<T>::I fit = dl.begin(),
						   	   	    bit = dl.end();
	while (fit != bit && *fit == *bit) {
		++fit;
		if (fit != bit)
			--bit;
	}
	// да - fit == bit
	// не - *fit != *bit
	return fit == bit;
}

void palindromeList() {
	DoubleLinkedList<int> dl;
	int i;
	for(i = 1; i <= 10; i++)
		dl.toEnd(i);
	for(; i >= 1; i--)
		dl.toEnd(i);
	cout << dl << isPalindrome(dl) << endl;
}

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