module ytl.fastlist;
private import ytl.y4d_result;

///	巡回の高速なlist。
/**
	listを持っていてそれを呼び出す処理を考える。

	ただし、listはnewを行なうので、速度低下を招く可能性がある。
	大量の要素(100～1000個単位)を扱うときにはこういう実装は
	良くないと思われる。<BR>

	よって少なくともタスクのinsert,removeに際してnewは行なわない
	ようなlist管理の方法が問われることになる。<BR>

	それがこのクラスの目的である。<BR>

	このクラスの使用例は、 GameTaskController を参照すること。
*/
template fastlist(T) {
/// fastlist本体
class fastlist {

	///	事前にサイズを指定してpoolを確保する
	/**
		確保できれば0が返る。
	*/
	y4d_result		setMax(int n){
		release();

		if (n<=0) {
			return y4d_result.invalid_parameter; // ダメやん
		}

		nodeList = new Node[n+2];

		//	空領域として先頭を指すようにしておく
		// emptyTask = &taskList[0];
		nodeList[1].next = &nodeList[2];
		// emptyList[0].next = null;は保証されているのでやる必要ない

		//	emptyブロックを数珠つなぎにしておく
		for(int i=2;i<n+1;++i){
			nodeList[i].next = &nodeList[i+1];
		}
		return y4d_result.no_error;
	}

	///	確保しているものを解放する
	/**
		明示的に呼び出す必要はない。
	*/
	void	release() {
		if (nodeList) {
			//	nodeListも巡回して明示的にdeleteするべきか?
			delete nodeList;
			nodeList = null;
		}
	}

	///	ひとつの要素
	struct Node {
		Node*	next;		//!<	数珠つなぎにして管理
		T		element;	//!<	データ
		int		priority;	//!<	順位(Nodeを降順で並べるときに使う)
		bool	dead;		//!<	このデータは死亡なので回収すべき
	}

	///	全部の要素を得る
	/**
		ただし、Node[0].nextは、使用しているブロックの先頭へのポインタ。
		Node[1].nextは、空きブロックの先頭へのポインタ。
		そのポイント先からは、nextを数珠つなぎにして管理されている。
	*/
	Node[]	getNodeList() { return nodeList; }

	///	foreachに対応させるためのもの
	/**
		死んでいるタスクの回収は行なわない。
	*/
	int opApply(int delegate(inout T) dg)
	{
		if (!nodeList) return 0;	//	ダメやん

		int result = 0;
		Node* node = nodeList[0].next; // startTask;
		while (node) {
			if (!node.dead) {
				result = dg(node.element);
				if (result)	break;
			}
			node = node.next;
		}
		return result;
	}

	///	foreachに対応させるためのもの
	int opApply(int delegate(inout Node) dg)
	{
		if (!nodeList) return 0;	//	ダメやん

		int result = 0;
		Node* node = nodeList[0].next; // startTask;
		while (node) {
			if (!node.dead) {
				result = dg(*node);
				if (result)	break;
			}
			node = node.next;
		}

		return result;
	}

	///	デリートマーカーのついているものを削除する
	/**
		巡回のあととかに呼び出すようにしてネ。
	*/
	void	collect() {
		Node* prev = &nodeList[0];
		Node* now = prev.next; // startNode;
		Node* next;
		while (now) {
			if (now.dead) {
			//	このタスクは死んでいるので回収すべき
				Node* e = &nodeList[1];

				next = now.next;
				//	事前に獲得しておかないとつなぎかえたあとでは
				//	正しいポインタを取得できない

				//	empty poolに入れる
				now.next = e.next;
				e.next = now;

				//	生きてるlinkから消す
				prev.next = next;
				now = next;

			} else {
				prev = now;
				now = now.next;
			}
		}
	}

	///	空き要素をひとつ取得する
	/**
		空きがなければ、nullが返る。
		空きリストを調べて空きがあれば、そこに登録して、
		登録したNodeのポインタを返す。
		これを、生きてるチェインの正しい位置に挿入する必要がある。
	*/
	Node* getEmptyNode(T t){
		Node* emptyNode = nodeList[1].next;
		if (!emptyNode) {
			//	空きが無いやん
			return null;
		}
		// 空き要素をひとつ消費(empty listから切り離す)
		nodeList[1].next = emptyNode.next;

		emptyNode.element = t;
		emptyNode.dead = false;
		// これをpriorityの正しい位置に挿入する必要がある。(かも知れない)

		return emptyNode;
	}

	///	要素の挿入
	/**
		getEmptyNodeで取得した空きブロックを生きブロックの先頭に突っ込む。
	*/
	y4d_result insert(Node* emptyblock) {
		if (!emptyblock) return y4d_result.invalid_parameter;
		emptyblock.next = nodeList[0].next;
		nodeList[0].next = emptyblock;
		return y4d_result.no_error;
	}

	///	要素の挿入
	/**
		getEmptyNodeで取得した空きブロックを
		生きブロックのpriorityで指定されたところに突っ込む。
	*/
	y4d_result insert(Node* emptyNode,int priority) {
		if (!emptyNode) return y4d_result.invalid_parameter;

		emptyNode.priority = priority;

		Node* prev = &nodeList[0];
		Node* now = prev.next;
		while (now && now.priority < priority) {
			prev = now;
			now = now.next;
		}
		//	終端まで行ったのでとりあえず挿入する
		emptyNode.next = now;
		prev.next = emptyNode;
		return y4d_result.no_error;
	}

	///	要素の挿入
	/**
		空きブロックから一個空きをもらって、
		順序無視で生きブロックの先頭に突っ込む。
	*/
	y4d_result add(T t){
		return insert(getEmptyNode(t));
	}

	///	要素の挿入
	/**
		空きブロックから一個空きをもらって、
		生きブロックのpriorityの順序のところに突っ込む。
	*/
	y4d_result add(T t,int priority){
		Node* e = getEmptyNode(t);
		if (!e) { return y4d_result.invalid_parameter; }
		e.priority = priority;
		return insert(e,priority);
	}

	///	要素の削除
	/**
		優先度を指定して、その要素を削除する。
		消したオブジェクトは、デリートマーカーをつけておき、
		次回のcollect時に回収される。
	*/
	void	kill(int priority){
		foreach(inout Node e;this){
			int n = e.priority;
			if (n==priority){
				e.dead = true;
			} else if (n>priority) break;
		}
	}

	///	要素の一括削除
	/**
		nStartPriority～nEndPriorityまでを削除する。
		(nEndPriorityも削除対象に含む。)<BR>

		消したオブジェクトは、デリートマーカーをつけておき、
		次回のcollect時に回収される。
	*/
	void	kill(int nStartPriority,int nEndPriority){
		foreach(inout Node e;nodeList){
			int n = e.priority;
			if (n>=nStartPriority) continue;
			if (n<=nEndPriority) {
				e.dead = true;
			} else break;
		}
	}

	///	プライオリティを変更
	/**
		プライオリティを変更する。
	*/
	void	changePriority(int beforePriority,int afterPriority){
		// killして、追加するか..

		foreach(inout Node e;nodeList){
			int n = e.priority;
			if (n<beforePriority) { continue; }
			if (n==beforePriority) {
				e.dead = true;
				add(e.element,afterPriority);
				//	↑要素を無効化していないので、
				//	sはiteratorとして無効ではないので
				//	これは許される
			} else break;
		}
	}

	///	指定したプライオリティの要素を得る
	/**
		もし指定したプライオリティの要素がなければnullが戻る。
		プライオリティに対応する要素が唯一であるような設計をしている
		場合に使うと便利。
	*/
	T getElement(int priority) {
		foreach(inout Node node;this){
			int n = node.priority;
			if (n==priority){
				return node.element;
			} else if (n>priority) break;
		}
		return null;
	}

	bool isExistElement(int priority){
		return cast(bool) !!getElement(priority);
		//		↑これ何かいい方法ないの？(´Д｀)
	}

protected:
	Node[] nodeList;

}}
