module ytl.list;

///	C++のSTLのlistのようなクラス。
template list(T) { class list
///	listクラス本体。
/**
<PRE>
	使用例)
	class foo {
		int a,b;
	}

	alias list!(foo) foolist;
	foolist l = new foolist;

	for(int i=0;i<5;++i){
		foo f = new foo;
		f.a = i; f.b = i*2;
		l.push_back(f);
		f = new foo;
		f.a = -i; f.b = -i*2;
		l.push_front(f);
	}
	printf("--start of printing\n");

	foreach(inout foo f;l){
		printf("%d,%d\n",f.a,f.b);
	}
	foreach(inout foo f,foolist.reverse r;l){
		printf("%d,%d\n",f.a,f.b);
	}
	foreach(int i,foo f,foolist.reverse r;l){
		//	この場合、i=n-1...0 になる
		printf("%d,%d\n",f.a,f.b);
	}

	printf("obverse\n");
	foolist.iterator it = l.begin();
	while(it!=l.end()) {
		printf("%d,%d\n",it().a,it().b);
		++it;
	}

	printf("reverse\n");
	foolist.reverse_iterator it2 = l.rbegin();
	while(it2!=l.rend()) {
		printf("%d,%d\n",it2().a,it2().b);
		++it2;
	}
</PRE>

	@todo	C++のlistのメンバ全部足りてナー。
*/
{

	///	コンテナの先頭に要素を積む
	void	push_front(T x) {
	//	- endnode - first -
	//	- endnode - L - first -
		list_element first = endnode.next;
		list_element l = new list_element(x,endnode,first);
		first.prev = l; // 繋ぎかえしとかないとな
		endnode.next = l;
		s++;
	}

	///	コンテナの最後尾に要素を積む
	void	push_back(T x) {
		list_element last = endnode.prev;
		list_element l = new list_element(x,last,endnode);
		last.next = l; // 繋ぎかえしとかないとな
		endnode.prev = l;
		s++;
	}

	///	コンテナから先頭要素を除去して、それを返す
	T	pop_front()
	{
	//	- endnode - first - second
	//	- endnode - second - 
		//		if (empty()) return null;
		//		↑これをやってしまうとnullから基本型(intとか)にcast
		//		できないため、よくないのだ

		list_element first = endnode.next;
		list_element second = first.next;
		endnode.next = second;
		second.prev = endnode;
		if (s>=1) --s;
		return first.x;
	}

	///	コンテナから最後尾の要素を除去して、それを返す
	T	pop_back()
	{
	//	2nd - last - endnode
	//	2nd  - endnode - 
		//	if (empty()) return null;
		//		↑これをやってしまうとnullから基本型(intとか)にcast
		//		できないため、よくないのだ
		list_element last = endnode.prev;
		list_element booby = last.prev;
		endnode.prev = booby;
		booby.next = endnode;
		if (s>=1) --s;
		return last.x;
	}

	T	front()
	///	先頭要素を返す。要素は除去しない。
	/**
		(空のシーケンスの場合null,基本型の場合はディフォルト値を返す)
	*/
	{
		return endnode.next.x;
	}

	T	back()
	///	最後尾の要素を返す。要素は除去しない。
	/**
		(空のシーケンスの場合null,基本型の場合はディフォルト値を返す)
	*/
	{
		return endnode.prev.x;
	}

	///	先頭の要素を指すiteratorを返す。
	iterator begin()
	{ return new iterator(endnode.next); }

	///	終端の要素+1 を指すiteratorを返す。
	iterator end()
	{ return new iterator(endnode); }

	///	最後尾の要素 を指すreverse_iteratorを返す。
	reverse_iterator rbegin()
	{ return new reverse_iterator(endnode.prev); }

	///	先頭の要素-1 を指すreverse_iteratorを返す。
	reverse_iterator rend()
	{ return new reverse_iterator(endnode); }

	///	コンテナの内容をクリアする
	void	erase() {
		//	リングバッファみたくしておくのがスマート
		endnode.next = endnode.prev = endnode;
		s = 0;
	}

	///	保持している要素数を返す
	int size()	{ return s; }

	///	コンテナが空のシーケンスならばtrueが返る
	bool empty() { return !s; }

	///	foreachに対応させるためのもの
	int opApply(int delegate(inout T) dg)
	{
		list_element l = endnode.next;
		int result = 0;
		while ( l != endnode )
		{
			result = dg(l.x);
			if (result)	break;
			l = l.next;
		}
		return result;
	}

	///	foreachに対応させるためのもの
	int opApply(int delegate(inout int,inout T) dg)
	{
		list_element l = endnode.next;
		int result = 0;
		for (int i = 0; l!= endnode ; ++i)
		{
			result = dg(i,l.x);
			if (result)	break;
			l = l.next;
		}
		return result;
	}

	/// 逆巡回用マーカー(foreachで逆巡回するときに用いる)
	class reverse { }

	///	foreachの逆巡回に対応させるためのもの
	/**
		逆巡回には、ダミーマーカーである reverse クラスを用いる。
	*/
	int opApply(int delegate(inout T,inout reverse) dg)
	{
		reverse r;	//	rはダミーのマーカー
		list_element l = endnode.prev;
		int result = 0;
		for (int i = s-1 ; l!=endnode ; --i)
		{
			result = dg(l.x,r);
			if (result)	break;
			l = l.prev;
		}
		return result;
	}

	///	foreachの逆巡回に対応させるためのもの
	/**
		逆巡回には、ダミーマーカーである reverse クラスを用いる。
		また、ループカウンターは、size()-1から0へ向かってダウンカウントされる。
	*/
	int opApply(int delegate(inout int,inout T,inout reverse) dg)
	{
		reverse r;	//	rはダミーのマーカー
		list_element l = endnode.prev;
		int result = 0;
		for (int i = s-1 ; l!=endnode ; --i)
		{
			result = dg(i,l.x,r);
			if (result)	break;
			l = l.prev;
		}
		return result;
	}

	this() {
		endnode = new list_element;
		erase();
	}

	//---------------------------------------------------------------

	///	listのiterator
	class iterator
	{
		this() {}
		this(list_element e_) { e = e_; }
		this(iterator it) { e = it.e; }

		///	* 演算子をoverload出来ないので、かわりに () を用いる
		T opCall() { return e.x; }

		///	== を用いたときの同値性の判定
		bool opEquals(iterator it)
		{ return (e is it.e);}
		//	↑同値性、これでいいのかな??

		///	後置++
		iterator opPostInc()
		{ iterator it = new iterator(this); inc(); return it; }

		///	後置--
		iterator opPostDec()
		{ iterator it = new iterator(this); dec(); return it; }

		///	前置++,+=
		iterator opAddAssign(int n)
		{ for(int i=0;i<n;++i) inc(); return this; }

		///	前置--,-=
		iterator opSubAssign(int n)
		{ for(int i=0;i<n;++i) dec(); return this; }

	private:
		void inc() { if (e) e = e.next; }
		void dec() { if (e) e = e.prev; }

		list_element e;
	}

	///	listのreverse_iterator
	class reverse_iterator
	{
		this() {}
		this(list_element e_) { e = e_; }
		this(reverse_iterator it) { e = it.e; }

		///	* 演算子をoverload出来ないので、かわりに () を用いる
		T opCall() { return e.x; }

		///	== を用いたときの同値性の判定
		bool opEquals(reverse_iterator it)
		{ return (e is it.e);}
		//	↑同値性、これでいいのかな??

		///	後置++
		reverse_iterator opPostInc()
		{ reverse_iterator it = new reverse_iterator(this); inc(); return it; }

		///	後置--
		reverse_iterator opPostDec()
		{ reverse_iterator it = new reverse_iterator(this); dec(); return it; }

		///	前置++,+=
		reverse_iterator opAddAssign(int n)
		{ for(int i=0;i<n;++i) inc(); return this; }

		///	前置--,-=
		reverse_iterator opSubAssign(int n)
		{ for(int i=0;i<n;++i) dec(); return this; }

	private:
		void inc() { if (e) e = e.prev; }
		void dec() { if (e) e = e.next; }

		list_element e;
	}

	//---------------------------------------------------------------

private:
	//	要素ひとつ分
	class list_element {
		list_element prev;
		list_element next;
		T x;

		this() {}
		this(T x_) { x = x_; }
		this(T x_,list_element prev_,list_element next_)
		{ x = x_; prev = prev_; next = next_; }
	}

	list_element endnode;
	//	endnode.next == first
	//	endnode.prev == last
	int s;
}}
