/*
 * llist_examples.cpp
 *
 *  Created on: 21.11.2012
 *      Author: trifon
 */

#include <iostream>
#include "linked_list.cpp"
#include "double_linked_list.cpp"
using namespace std;

typedef LinkedList<> TestList;

template <typename T, typename I>
void concatenate(List<T, I >& l, List<T, I > const& l2)
{
	for(I it = l2.iteratorBegin(); it; ++it)
		l.toEnd(*it);
}

void concatLists() {
	TestList l1, l2;
	int i;
	for(i = 1; i <= 5; i++)
		l1.toEnd(i);
	for(;i <= 10; i++)
		l2.toEnd(i);
	concatenate(l1, l2);
	l1.print();
}

template <typename T, typename I>
void reverse(List<T, I>& l)
{
	I it = l.iteratorBegin();
	// it към началото на оригиналния списък
	T x;
	while (l.deleteAfter(x, it))
		l.insertBefore(x, l.iteratorBegin());
}

void reverseList() {
	TestList l;
	int i;
	for(i = 1; i <= 5; i++)
		l.toEnd(i);
	reverse(l);
	l.print();
}

template <typename T, typename I>
List<T, I>& merge(List<T, I> const& l1, List<T, I> const& l2,
		           List<T, I>& l)
{
	I p = l1.iteratorBegin(), q = l2.iteratorBegin();
	while (p && q)
	{
		if (*p < *q)
			l.toEnd(*p++);
		else
			l.toEnd(*q++);
	}
	while (p)
		l.toEnd(*p++);
	while (q)
		l.toEnd(*q++);
	return l;
}

void mergeLists() {
	TestList l1, l2;
	for(int i = 1; i <= 9; i++)
	{
		l1.toEnd(i++);
		l2.toEnd(i);
	}
	l1.print();
	l2.print();
	TestList l;
	merge(l1,l2,l).print();
}

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

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

int plus_op(int x, int y) { return x + y; }

void sumList()
{
	TestList l;
	for(int i = 1; i <= 5; i++)
		l.toEnd(i);
	cout << foldl(l, plus_op, 0);
}

int square(int x) { return x * x; }

void squareList()
{
	TestList l;
	for(int i = 1; i <= 5; i++)
		l.toEnd(i);
	map(l, square);
	l.print();
}

template <typename T, typename I>
List<T, I>& filter(List<T, I> const& l, bool (*p)(T), List<T, I>& result)
{
	for(I it = l.iteratorBegin(); it; ++it)
		if (p(*it))
			result.toEnd(*it);
	return result;
}

bool odd(int x) { return x % 2 != 0; }

void oddList()
{
	TestList l;
	for(int i = 1; i <= 5; i++)
		l.toEnd(i);
	TestList result;
	filter(l, odd, result).print();
}

void sumOddSquaresList()
{
	TestList l;
	for(int i = 1; i <= 5; i++)
		l.toEnd(i);
	TestList result;
	cout << foldl(filter(map(l, square), odd, result), plus_op, 0);
}

template <typename T>
bool isPalindrome(DoubleLinkedList<T> const& dl)
{
	DoubleLinkedListIterator<T> sit = dl.iteratorBegin(),
							    eit = dl.iteratorEnd();
	while (sit != eit && *sit == *eit)
	{
		++sit;
		if (sit != eit)
			--eit;
	}
	// sit == eit || *sit != *eit
	return sit == eit;
}

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

int main()
{
//	concatLists();
//	reverseList();
//	mergeLists();
//	sumList();
//	squareList();
//	oddList();
//	sumOddSquaresList();
//	palindromeList();
	return 0;
}