#ifndef __LIST_H__
#define __LIST_H__
#include "lazy.h"
// #include "functional.h"
#include <exception>
#include <iostream>

class EmptyList : std::exception { };

template <typename T>
class List
{
	public:
		typedef T list_item_type;
		List() { }
		virtual ~List() { }
		virtual Lazy<T> getHead() = 0;
		virtual Lazy< List<T> > getTail() = 0;
		virtual bool isEmpty() = 0;
};

template <typename T>
using LazyList = R<LazyBase<List<T>>, true>;

template <typename T>
class Cons : public List<T>
{
	public:
		typedef T list_item_type;
		Cons(Lazy<T> head, LazyList<T> tail) : List<T>(), head(head), tail(tail) { }
		virtual ~Cons() { }
		virtual Lazy<T> getHead() { return head; }
		virtual LazyList<T> getTail() { return tail; }
		virtual bool isEmpty() { return false; }
	private:
		Lazy<T> head;
		LazyList<T> tail;
};

template <typename T>
class Nil : public List<T>
{
	public:
		typedef T list_item_type;
		Nil() : List<T>() { }
		virtual ~Nil() { }
		virtual Lazy<T> getHead() { throw EmptyList(); }
		virtual LazyList<T> getTail() { throw EmptyList(); }
		virtual bool isEmpty() { return true; }

		static LazyList<T> instance;
	private:
		static LazyList<T> initInstance();
};

template<typename T>
LazyList<T> Nil<T>::instance = Nil<T>::initInstance();

template<typename T>
LazyList<T> Nil<T>::initInstance()
{
	auto rNil = Ref::mk<Nil<T>>();
	return suspend(rNil);
}

template <typename T>
LazyList<T> cons(Lazy<T> head, LazyList<T> tail)
{
	return suspend<List<T>> (Ref::mk<Cons<T>> (head, tail));
}

template <typename T>
inline LazyList<T> operator<<=(Lazy<T> head, LazyList<T> tail)
{
	return cons(head, tail);
}

/*template <typename T>
class LLIterator
{
	public:
		LLIterator(LazyList<T> list) : list(list) { }
		T& operator *()
		{
			return lazyVal(head(list)).deref();
		}
		LLIterator& operator++()
		{
			list = tail(list);
		}
	private:
		LazyList<T> list;
};*/

template <typename T>
LazyList<T> drop(LazyList<T> list, Int i)
{
	if (i == 0L)
	{
		return list;
	}
	else
	{
		return drop(list.tail(), i - 1L);
	}
}

/**** iterate ****/

template <typename T>
LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, Lazy<T> init)
{
	return mkLazy(mkLFun([] (decltype(fun) fun, decltype(init) init) {
		return Ref::mk<Cons<T>> (init, iterate (fun, fun(init)));
	}, fun, init));
}

/**** map ****/

template <typename TSource, typename TDest>
LazyList<TDest> map(Delegate1< LazyBase<TDest>, LazyBase<TSource> > fun, LazyList<TSource> l)
{
	return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l) l) {
		return Ref::mk<Cons<TDest>> (fun(l.head()), map(fun, l.tail()));
	}, fun, l));
}

/**** filter ****/
template <typename T>
LazyList<T> filter(Delegate1<bool, LazyBase<T>> fun, LazyList<T> l)
{
	return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l) l) {
		auto lx = l;
		while (*fun(lx.head()) == false)
		{
			lx = lx.tail();
		}
		return Ref::mk<Cons<T>> (lx.head(), filter(fun, lx.tail()));
	}, fun, l));
}

/**** zipWith ****/

template <typename T> // TODO allow different lists
LazyList<T> zipWith(Delegate2<LazyBase<T>, LazyBase<T>, LazyBase<T>> fun, LazyList<T> l1, LazyList<T> l2)
{
	return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l1) l1, decltype(l2) l2) {
		return Ref::mk<Cons<T>> (fun(l1.head(), l2.head()), zipWith(fun, l1.tail(), l2.tail()));
	}, fun, l1, l2));
}

/**** specialization ****/
template <typename T>
class R<LazyBase<List<T>>, true> : public R<LazyBase<List<T>>, false>
{
	protected:
		// passing protected constructor
		inline R(int i) : R<LazyBase<List<T>>, false>(i) { }
	public:
		inline R() : R<LazyBase<List<T>>, false>() { }
		template<typename U, bool od> inline R(R<LazyBase<U>, od>&  o) : R<LazyBase<List<T>>, false>(o, 0)
		{
			_assert_subclass<U, List<typename U::list_item_type>> ERRORList;
			_assert_subclass<typename U::list_item_type, T> ERRORItem;
		}
		template<typename U, bool od> inline R(R<LazyBase<U>, od>&& o) : R<LazyBase<List<T>>, false>(o, 0)
		{
			_assert_subclass<U, List<typename U::list_item_type>> ERRORList;
			_assert_subclass<typename U::list_item_type, T> ERRORItem;
		}
		// passing operator=
		template<typename U, bool od> inline R<LazyBase<List<T>>, true>& operator=(R<LazyBase<U>, od>&  o)
		{
			_assert_subclass<U, List<typename U::list_item_type>> ERRORList;
			_assert_subclass<typename U::list_item_type, T> ERRORItem;
			R<LazyBase<List<T>>, false>::copy(o);
			return *this;
		}
		template<typename U, bool od> inline R<LazyBase<List<T>>, true>& operator=(R<LazyBase<U>, od>&& o)
		{
			_assert_subclass<U, List<typename U::list_item_type>> ERRORList;
			_assert_subclass<typename U::list_item_type, T> ERRORItem;
			R<LazyBase<List<T>>, false>::copy(o);
			return *this;
		}
		// additional functionality
		inline Lazy<T>     head() { return this->deref().get().deref().getHead(); }
		inline LazyList<T> tail() { return this->deref().get().deref().getTail(); }
		inline static LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, Lazy<T> init) { return ::iterate(fun, init); }
		inline static LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, T init) { return ::iterate(fun, suspend(init)); }
		template<typename U> inline LazyList<U> map(Delegate1<LazyBase<U>, LazyBase<T>> fun) { return ::map(fun, *this); }
		inline LazyList<T> filter(Delegate1<bool, LazyBase<T>> fun) { return ::filter(fun, *this); }
		inline LazyList<T> drop(Int i) { return ::drop(*this, i); }
		// keep reference makeable with Ref::mk
		friend Ref;
};

#endif