//
//	clipdlst.cs
//
//	ユーティリティ：ダブルリンクリスト
//
//	CLiP - Common Library for P/ECE
//	Copyright (C) 2017 Naoyuki Sawa
//
//	* Sat Apr 15 21:38:10 JST 2017 Naoyuki Sawa
//	- 1st リリース。
//
using System;
namespace org.piece_me {
	public static partial class libclip {
		//*****************************************************************************
		//	ユーティリティ：ダブルリンクリスト
		//*****************************************************************************
		public class LIST_ENTRY {
			public LIST_ENTRY		Flink;		//前方リンク
			public LIST_ENTRY		Blink;		//後方リンク
			public readonly object		Value;		//外側のオブジェクト	null可		//┐
			public LIST_ENTRY() { /** no job **/ }							//│
			public LIST_ENTRY(object Value) { this.Value = Value; }					//├【C#版特有】
		}												//│
		public static T CONTAINING_RECORD<T>(LIST_ENTRY e) where T : class { return (T)e.Value; }	//┘
		//-----------------------------------------------------------------------------
		//ダブルリンクリストを初期化します。
		public static void InitializeListHead(LIST_ENTRY ListHead) {
			ListHead.Flink = ListHead.Blink = ListHead;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストが空か否か、判定します。
		public static bool IsListEmpty(LIST_ENTRY ListHead) {
			return ListHead.Flink == ListHead;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストから、先頭の要素を取り除きます。
		public static LIST_ENTRY RemoveHeadList(LIST_ENTRY ListHead) {
			LIST_ENTRY Head = ListHead.Flink;
			RemoveEntryList(Head);
			return Head;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストから、末尾の要素を取り除きます。
		public static LIST_ENTRY RemoveTailList(LIST_ENTRY ListHead) {
			LIST_ENTRY Tail = ListHead.Blink;
			RemoveEntryList(Tail);
			return Tail;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストから、指定した要素を取り除きます。
		public static void RemoveEntryList(LIST_ENTRY Entry) {
			LIST_ENTRY Flink = Entry.Flink;
			LIST_ENTRY Blink = Entry.Blink;
			Blink.Flink = Flink;
			Flink.Blink = Blink;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストの先頭に、指定した要素を追加します。
		public static void InsertHeadList(LIST_ENTRY ListHead, LIST_ENTRY Entry) {
			LIST_ENTRY Head = ListHead.Flink;
			Entry.Flink = Head;
			Entry.Blink = ListHead;
			ListHead.Flink = Head.Blink = Entry;
		}
		//-----------------------------------------------------------------------------
		//ダブルリンクリストの末尾に、指定した要素を追加します。q
		public static void InsertTailList(LIST_ENTRY ListHead, LIST_ENTRY Entry) {
			LIST_ENTRY Tail = ListHead.Blink;
			Entry.Flink = ListHead;
			Entry.Blink = Tail;
			Tail.Flink = ListHead.Blink = Entry;
		}
		//*****************************************************************************
		//	独自拡張
		//*****************************************************************************
		//ダブルリンクリストをソートします。
		public static void SortList(LIST_ENTRY ListHead, Func<LIST_ENTRY/*a*/,LIST_ENTRY/*b*/,int> Compare) {
			SortList_r(ListHead, delegate(LIST_ENTRY a, LIST_ENTRY b, object Param) { return Compare.Invoke(a, b); }, null);
		}
		//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
		//○マージソートのアルゴリズムによる実装。
		//│リストを二等分して再帰するので、最悪でも30回程度の再帰呼出しに抑えられるので、クイックソート版の問題が回避出来る。
		//│ただし、本来のマージソートは安定ソートだが、当関数の動作は不安定ソートである事に注意せよ。
		public static void SortList_r(LIST_ENTRY ListHead, Func<LIST_ENTRY/*a*/,LIST_ENTRY/*b*/,object/*Param*/,int> Compare, object Param) {
			LIST_ENTRY List1 = new LIST_ENTRY(), List2 = new LIST_ENTRY(), Entry1, Entry2;
			//左右のリストを初期化する。
			InitializeListHead(List1);
			InitializeListHead(List2);
			//元のリストが空になるまで…
			for(;;) {
				//元のリストが空ならば、抜ける。				//┐
				if(IsListEmpty(ListHead)) { break; }				//│
				//元のリストの先頭要素を取り外し、左のリストに追加する。	//│
				Entry1 = RemoveHeadList(ListHead);				//│
				InsertTailList(List1, Entry1);					//│固定配列のマージソートと違って最初に全体の要素数が判らないので、二等分するために一要素づつ振り分ける事にした。
				//元のリストが空ならば、抜ける。				//│固定配列のマージソートは安定ソートであるが、当関数の実装はこの動作を行うために安定ソートではない事に注意せよ。
				if(IsListEmpty(ListHead)) { break; }				//│
				//元のリストの先頭要素を取り外し、右のリストに追加する。	//│
				Entry2 = RemoveHeadList(ListHead);				//│
				InsertTailList(List2, Entry2);					//┘
			}
			//右のリストが空でなければ…
			// - 元のリストの要素数が0,又は,1になったら、再帰を停止するための判断である。
			//   この判断を行わないと、0,又は,1要素のリストに対して無限に再帰してしまう。
			if(!IsListEmpty(List2)) {
				//左右のリストをソートする。
				SortList_r(List1, Compare, Param);
				SortList_r(List2, Compare, Param);
			}
			//左右のリストが空になるまで…
			for(;;) {
				//左右のリストの先頭要素を取り外す。空ならばnullとする。
				Entry1 = IsListEmpty(List1) ? null : RemoveHeadList(List1);
				Entry2 = IsListEmpty(List2) ? null : RemoveHeadList(List2);
				//左の要素が有れば…
				if(Entry1 != null) {
					//右の要素が有れば…
					if(Entry2 != null) {
						//左の要素が右の要素よりも小さいか同じならば…
						if(Compare.Invoke(Entry1, Entry2, Param) <= 0) {
							//左の要素を元のリストの末尾に追加する。
							InsertTailList(ListHead, Entry1);
							//右の要素を右のリストの先頭に書き戻す。
							InsertHeadList(List2, Entry2);
						//右の要素が左の要素よりも小さければ…
						} else {
							//右の要素を元のリストの末尾に追加する。
							InsertTailList(ListHead, Entry2);
							//左の要素を左のリストの先頭に書き戻す。
							InsertHeadList(List1, Entry1);
						}
					//右の要素が無ければ…
					} else {
						//左の要素を元のリストの末尾に追加する。
						InsertTailList(ListHead, Entry1);
					}
				//左の要素が無ければ…
				} else {
					//右の要素が有れば…
					if(Entry2 != null) {
						//右の要素を元のリストの末尾に追加する。
						InsertTailList(ListHead, Entry2);
					//右の要素が無ければ…
					} else {
						//ループを抜ける。
						break;
					}
				}
			}
		}
	}
}
