module ytl.vector;

///	C++のSTLのvectorのようなクラス。
template vector(T) {
class vector
///	vectorクラス本体
/**
<PRE>
	使用例)
	vector!(foo) gg = new vector!(foo).t;
	for(int i=0;i<30;++i) {
		foo f = new foo;
		f.a = 20; f.b = 10;
		gg.push_back(f);
	}
	gg[15].a = 12;

	printf("%d %d \n",gg[25].a,gg[15].a);

	foreach (int i,foo ff;gg){
		printf("gg[%d] = %d\n",i,ff.a);
	}

	//	あるいは、逆巡回
	alias vector!(foo) vectfoo;
	foreach (int i,foo ff,vectfoo.reverse r;gg){
		printf("gg[%d] = %d\n",i,ff.a);
	}

	//	iteratorを用いた巡回
	vectfoo.iterator it;
	it = gg.begin();
	while(it!=gg.end()){
		printf("%d \n",it().a);
		++it;
	}

	//	もちろんreverse_iteratorも健在
	vectfoo.reverse_iterator it;
	it = gg.rbegin();
	while(it!=gg.rend()){
		printf("%d \n",it().a);
		++it;
	}

	//	iterator,reverse_iteratorはランダムアクセス反復子なので
	//	当然順序比較も可能
	if (gg.begin() < gg.end()){
		printf("こんちわ！\n");
	}
	if (gg.rbegin() < gg.rend()){
		printf("さよなら！\n");
	}
</PRE>
	@todo	RanIteratorに対するbinary_searchとかfindとかsortとか必要。
*/
{

	T at(int n)	///	n番目の要素を取得。nは0～size()-1まで。範囲外のときは知らネ
	{
		assert(a_ && n>=0 && n<size());
		return a_[n];
	}

	int size()		/// vectorの要素数を返す
	{ return size_; }

	int capacity()	///	確保してあるvectorサイズ (2^nで確保)
	{
		if (!a_) return 0;
		return a_.length;
	}
	
	/// n個の要素をtで埋める
	void assign(int n, T t) {
		clear();
		if (n==0) return ;
		a_ = new T[n];
		foreach(inout data; a_) {
			data = t;
		}
	}

	T opIndex(int n)	///	[ ] operator : n番目の要素を取得する
	{ return at(n); }

	T opIndexAssign(T t,int n)/// [ ] = operator : n番目の要素に代入する
	{ return a_[n] = t;}

	void push_back(T t)	///	後ろに要素を追加
	{
		// 追加できるか?
		if (capacity() == size()) {
			//	駄目やん。再確保しる！
			int s = size()*2; // 現在のサイズの倍で再確保
			if (s == 0) {
				s++;
			}
			T[] a = new T[s];
			for(int i=0;i<size_;++i)
				a[i] = a_[i];	// これdeep copyにはならんのでそ？
			a_ = a;
		}
		a_[size_] = t;
		size_++;
	}

	void clear()		///	コンテナのクリア
	{ 
		size_ = 0;
		if (!a_){
			a_ = new T[16];	//	一応16個だけ確保しておくか..
		}
	}

	bool empty() 		/// コンテナは空か？
	{	return cast(bool) !size; }

	///	サイズの変更。
	void resize(int n)
	/**
		size()は、ここで設定した値が返るようになる。
		ただし、いったんclearするので以前に格納していたものは、無くなる。
	*/
	{
		clear();
		if (n==0) return ;
		size_ = n;
		//	これを2^nになるように繰り上げて確保
		int i=n-1,j=1;
		while (i!=0) { i>>=1; j<<=1; }
		a_ = new T[j];
	}
	void reserve(int n)
	/**
		capacityが最低でもnを返すように予約する
		ただし、いったんclearするので以前に格納していたものは、無くなる。
	*/
	{
		clear();
		if (n==0) return ;
		//	これを2^nになるように繰り上げて確保
		int i=n-1,j=1;
		while (i!=0) { i>>=1; j<<=1; }
		a_ = new T[j];
	}

	///	最後尾の要素を除去し、それを返す。
	T pop_back()
	/**
		要素が一つもない場合はnullを返します。
	*/
	{
		T t;
		if (size() != 0) {
			t = a_[--size_];
		}
		return t;
	}

	///	foreachに対応させるためのもの
	int opApply(int delegate(inout T) dg)
	{
		int result = 0;
		for (int i = 0; i < size_; ++i)
		{
			result = dg(a_[i]);
			if (result)	break;
		}
		return result;
	}

	///	foreachに対応させるためのもの
	int opApply(int delegate(inout int,inout T) dg)
	{
		int result = 0;
		for (int i = 0; i < size_; ++i)
		{
			result = dg(i,a_[i]);
			if (result)	break;
		}
		return result;
	}

	/// foreachで逆巡回のときに使うマーカー
	class reverse { }

	///	foreachに対応させるためのもの。reverseマーカーを用いた逆巡回用。
	/**
	<PRE>
		alias vector!(int) vect;
		vect v = new vect;
		//	(ごにょごにょ)
		foreach(inout int n,vect.reverse r;v)
			...
	</PRE>
	*/
	int opApply(int delegate(inout T,inout reverse) dg)
	{
		reverse r;	//	rはダミーのマーカー
		int result = 0;
		for (int i = size_-1 ; i >= 0; --i)
		{
			result = dg(a_[i],r);
			if (result)	break;
		}
		return result;
	}

	///	foreachに対応させるためのもの。reverseマーカーを用いた逆巡回用。
	/**
	<PRE>
		alias vector!(int) vect;
		vect v = new vect;
		//	(ごにょごにょ)
		foreach(int i,inout int n,vect.reverse r;v)
			...
		※　このとき、iはsize()-1から0へ向かってダウンカウントされる
	</PRE>
	*/
	int opApply(int delegate(inout int,inout T,inout reverse) dg)
	{
		reverse r;	//	rはダミーのマーカー
		int result = 0;
		for (int i = size_-1 ; i >= 0; --i)
		{
			result = dg(i,a_[i],r);
			if (result)	break;
		}
		return result;
	}

	///	先頭の要素を返す。要素は除去しない。
	/**
		空のシーケンスの場合、T.init(クラスの場合null、基本型の場合0)が返る
	*/
	T front() { return (a_) ? a_[0] : T.init; }

	///	最後尾の要素を返す。要素は除去しない。
	/**
		空のシーケンスの場合、T.init(クラスの場合null、基本型の場合0)が返る
	*/
	T back() { return (a_) ? a_[size()-1] : T.init; }

	///	先頭の要素を指す iterator を返す。
	iterator begin() { return new iterator(this,0); }

	///	最後尾の要素+1を指す iterator を返す。
	iterator end() { return new iterator(this,size()); }

	///	最後尾の要素を指す reverse_iterator を返す。
	reverse_iterator rbegin() { return new reverse_iterator(this,size()-1); }

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

	///	n番目の要素の除去。n = 0～。
	void erase(int n)
	{
		for(int i=n ; i<size()-2 ; ++i){
			a_[i] = a_[i+1];
		}
		a_[--size_] = T.init; // null;
	}

	///	n番目からm番目までの要素の除去。m番目は含まない。n = 0～。
	void	erase(int n,int m)
	{
		int nFirst = n;
		int nLast  = m;
		if (nLast>size()) nLast = size();
		if (nFirst >= nLast) return ; // (;´Д`)

		for(int i=nFirst;i<nLast;++i){
			int nFrom = i+nLast;
			if (nFrom >= size()) {
				a_[nFirst] = T.init; // null;
			} else {
				a_[i] = a_[nFrom];
			}
		}
	}

	///	iteratorの指し示す要素を除去
	iterator	erase(iterator it1)
	{
		for(int i=it1.getPos() ; i<size()-2 ; ++i){
			a_[i] = a_[i+1];
		}
		a_[--size_] = T.init; // null;
		return it1;
	}

	///	iteratorの指し示す範囲の要素を除去。it2の指す要素は含まない。
	iterator	erase(iterator it1,iterator it2)
	{
		int nFirst = it1.getPos();
		int nLast  = it2.getPos();
		if (nLast>size()) nLast = size();
		if (nFirst >= nLast) return it1; // (;´Д`)

		for(int i=nFirst;i<nLast;++i){
			int nFrom = i+nLast;
			if (nFrom >= size()) {
				a_[nFirst] = T.init; // null;
			} else {
				a_[i] = a_[nFrom];
			}
		}
		return it1;
	}

	this() { clear(); }

	// -------------------------------------------------------------------
	///	vectorのiterator
	/**
		vectorのiteratorはRanIt(ランダムアクセス反復子)です。
	*/
	static class iterator {
		this() {}
		this(vector v) { v_ = v; }
		this(vector v,int pos) { v_ = v; pos_ = pos; }
		this(iterator it) { v_ = it.v_; pos_ = it.pos_; }

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

		///	= による同値性の判定
		bool opEquals(iterator it)
		{ return cast(bool) (v_ == it.v_ && pos_ == it.pos_);}

		///	< , > operator
		int opCmp(iterator it)
		{ return pos_ - it.pos_; }

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

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

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

		///	前置--,-=
		iterator opSubAssign(int n)
		{ dec(n); return this; }

		///	+
		iterator opAdd(int n)
		{ iterator it = new iterator(this); it+=n; return it; }

		///	-
		iterator opSub(int n)
		{ iterator it = new iterator(this); it+=n; return it; }

		//	class内classはfriendではないようなのでaccessorが必要のようだ
		int getPos() { return pos_; }
		void setPos(int n) { pos_ = n; }

	private:
		void inc() { inc(1); }
		void dec() { dec(1); }
		void inc(int n) { pos_+=n; if (pos_>v_.size()) pos_=v_.size(); }
		void dec(int n) { pos_-=n; if (pos_<0) pos_=0; }

		int pos_;	//	現在指しているポジション
		vector v_;	//	親のvector
	}

	///	vectorのreverse_iterator
	/**
		vectorのreverse_iteratorはRanIt(ランダムアクセス反復子)です。
	*/

	static class reverse_iterator {
		this() {}
		this(vector v) { v_ = v; }
		this(vector v,int pos) { v_ = v; pos_ = pos; }
		this(reverse_iterator it) { v_ = it.v_; pos_ = it.pos_; }

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

		///	= による同値性の判定
		bool opEquals(reverse_iterator it)
		{ return cast(bool) (v_ == it.v_ && pos_ == it.pos_);}

		///	< , > operator
		int opCmp(reverse_iterator it)
		{ return it.pos_ - pos_; }

		///	後置++
		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)
		{ inc(n); return this; }

		///	前置--,-=
		reverse_iterator opSubAssign(int n)
		{ dec(n); return this; }

		///	+
		reverse_iterator opAdd(int n)
		{ reverse_iterator it = new reverse_iterator(this); it+=n; return it; }

		///	-
		reverse_iterator opSub(int n)
		{ reverse_iterator it = new reverse_iterator(this); it+=n; return it; }

		//	class内classはfriendではないようなのでaccessorが必要のようだ
		/*
			reverse_iteratorのgetPos/setPosがこの仕様でいいかどうかは考えちゅう
			ひょっとすると、size()-1-pos_ とかを返すほうがいいのか？
		*/
		int getPos() { return pos_; }
		void setPos(int n) { pos_ = n; }

	private:
		void inc() { inc(1); }
		void dec() { dec(1); }
		void inc(int n) { pos_-=n; if (pos_<-1) pos_=-1; }
		void dec(int n) { pos_+=n; if (pos_>=v_.size()) pos_=v_.size()-1; }

		int pos_;	//	現在指しているポジション
		vector v_;	//	親のvector
	}

private:
	T[] a_;
	int size_;	//	サイズ
}

}

