/*	
 *	clipsort.c
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2007 Naoyuki Sawa
 *
 *	* Fri Apr 13 00:10:09 JST 2007 Naoyuki Sawa
 *	- 新規作成。
 *	* Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
 *	- 非常に深い再帰呼び出しが発生する場合があったのを防ぐための変更を行いました。
 *	* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
 *	- ループを一か所、while(){...}からdo{...}while()に変更し、少し効率化しました。
 *	* Sun May 13 14:21:21 JST 2007 Naoyuki Sawa
 *	- ヒープソートの実装例を追加しました。
 *	  コメントアウトしてありますので、ライブラリプログラム自体には変化ありません。
 */
#include "clip.h"

/*****************************************************************************
 *	
 *****************************************************************************/

/* * 標準CライブラリのEPSON版qsort()を置き換えます。
 * - EPSON版qsort()に不具合があるわけでは無いので、そのままでも正しく動作します。
 *   しかし、EPSON版qsort()には少し無駄な処理が含まれていて、サイズと実行速度に無駄ががります。
 *   クィックソートアルゴリズムの勉強も兼ねて、自分でCLiP版を実装してみることにしました。
 *   ほとんどEPSON版qsort()と同じで、一部の無駄な処理を削除(関数内のコメント参照)しただけです。
 * - EPSON版→CLiP版への置き換えによる、サイズ節約と高速化の効果は、以下のとおりです。
 *	qsort()+swap()全体のモジュールサイズ
 *		EPSON版: 196バイト
 *		CLiP版 : 128バイト (68バイト節約)
 *	10000要素のランダムなint配列をソートする時間
 *		EPSON版: 1852ミリ秒
 *		CLiP版 : 1682ミリ秒 (約10%高速化)
 * * Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
 * - 非常に深い再帰呼び出しが発生する場合があったのを防ぐための変更を行ったことにより、
 *   サイズと速度の特性が少し変わりました。
 *	qsort()+swap()全体のモジュールサイズ
 *		EPSON版: 196バイト
 *		CLiP版 : 140バイト (56バイト節約)
 *	10000要素のランダムなint配列をソートする時間
 *		EPSON版: 1852ミリ秒
 *		CLiP版 : 1645ミリ秒 (約11%高速化)
 * * Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
 * - ループを一か所、while(){...}からdo{...}while()に変更し、少し効率化しました。
 *   ごくわずかに速くなったけれど、サイズは減りませんでした。
 *	qsort()+swap()全体のモジュールサイズ
 *		EPSON版: 196バイト
 *		CLiP版 : 140バイト (56バイト節約)
 *	10000要素のランダムなint配列をソートする時間
 *		EPSON版: 1852ミリ秒
 *		CLiP版 : 1642ミリ秒 (約11%高速化)
 */

static void
swap(unsigned char* p1, unsigned char* p2, int size) {
#if 0
//	int tmp;
//	do {
//		tmp = *p1;
//		      *p1++ = *p2;
//		              *p2++ = tmp;
//	} while(--size);
#else
	asm("
	ld.ub	%r4, [%r12]
	ld.ub	%r5, [%r13]
	ld.b	[%r13]+, %r4	; *anti-interlock*
	ld.b	[%r12]+, %r5
	sub	%r14, 1
	jrne	-5
	");
#endif
}

//-------------------------------------------------------------------------------------------------------------
//void
//qsort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*))
//{
//	unsigned char* pv;	/* ピボットへのポインタ */
//	unsigned char* lo;	/* 低位ポインタ (次に低位要素(ピボット以下の要素)を格納する位置へのポインタ) */
//	unsigned char* hi;	/* 高位ポインタ (次に高位要素(ピボット超過の要素)を格納する位置へのポインタ) */
//	int lo_cnt;		/* 低位要素数 */
//	int hi_cnt;		/* 高位要素数 */
//
//	/* 要素数が0または1ならば、何もせずに帰ります。
//	 * - EPSON版は、2要素の場合も特別扱いして、単純な比較と入れ替えを行っていますが、その必要はありません。
//	 *   2要素の場合も、それ以上の要素数の場合と同じ、通常の処理で対応できます。
//	 */
//	if(num <= 1) {
//		return;
//	}
//
//	/* ポインタと要素数を初期化します。
//	 * - EPSON版は、配列の中央付近と先頭の要素を入れ替え、もともと中央付近にあった値をピボットとしています。
//	 *   元からある程度昇順に並んでいると仮定して、中央付近に中央値があることを期待しているのだと思います。
//	 *   しかし実際にはあまり効果が無く、むしろ余計な入れ替えの回数が増える分、性能を落としているようです。
//	 *   そこでCLiP版では、単純に先頭の要素をピボットとして採用することにしました。
//	 */
//	pv = base;			/* ピボット     = 先頭 */
//	lo = pv + width;		/* 低位ポインタ = ピボットの次 */
//	hi = pv + width * (num - 1);	/* 高位ポインタ = 末尾 */
//	lo_cnt = 0;			/* 低位要素数   = 0 */
//	hi_cnt = 0;			/* 高位要素数   = 0 */
//
//	/* 低位ポインタと高位ポインタが交差するまで...(即ち、ピボット以外の全要素の低位or高位が確定するまで)
//	 * - (num-1)回のカウントダウンでループする方法でも同じ結果を得られますが、(lo<=hi)でループする方が、
//	 *   num変数の生存期間を短くし、自動変数のレジスタ割り当て最適化がより有効に働くことが期待できます。
//	 */
//	while(lo <= hi) { /* 注意!!(lo<hi)ではありません!! */
//		/* 低位ポインタの位置に有る要素を、ピボットと比較します。 */
//		if(compare(lo, pv) <= 0) {
//			/* 低位要素ならば、低位ポインタの位置に格納します。
//			 * 低位ポインタの次の位置に有る要素が、次回の比較対象となります。
//			 */
//			lo += width;
//			lo_cnt++;
//		} else {
//			/* 高位要素ならば、高位ポインタの位置に格納します。
//			 * 高位ポインタの位置に有った要素が、次回の比較位置に移動します。
//			 */
//			swap(lo, hi, width);
//			hi -= width;
//			hi_cnt++;
//		}
//	}
//
//	/* 以上の処理が終わった時点で[ピボット,[低位要素の並び],[高位要素の並び]]となっています。
//	 * [[低位要素の並び],ピボット,[高位要素の並び]]と入れ替えて、ピボットの位置を確定します。
//	 * - 入れ替え時に低位要素の並び順が変化しますが、まだ並び順に意味はないので、大丈夫です。
//	 * - もし低位要素が一つも無い場合、pv==hiとなっていて、このswap()処理はダミーとなります。
//	 */
//	swap(pv, hi, width);
//
//	/* [低位要素の並び]をソートします。 */
//	qsort(pv, lo_cnt, width, compare); /* 注意!![低位要素の並び]の先頭を指しているのは、loでなくpvです!! */
//
//	/* [高位要素の並び]をソートします。 */
//	qsort(lo, hi_cnt, width, compare); /* 注意!![高位要素の並び]の先頭を指しているのは、hiでなくloです!! */
//}
//-------------------------------------------------------------------------------------------------------------
//↓* Thu Apr 19 11:44:36 JST 2007 Naoyuki Sawa
//↓- 非常に深い再帰呼び出しが発生する場合があったのを防ぐための変更を行いました。
//↓- 上のコメントアウトした実装は、クイックソートのいちばん素直な実装です。
//↓  アルゴリズム的にはこのままでも間違いではありませんが、非常に深い再帰呼び出しが発生する場合があるという問題があります。
//↓- どのようなケースで非常に深い再帰呼び出しが発生するかというと、あらかじめソートされた数列をソートしようとした場合です。
//↓
//↓	<例>	次のような呼び出しを行った場合を考えてみます。
//↓
//↓			int array[10000] = { 1,2,3,...,10000 };
//↓			qsort(array, 10000, sizeof(int), compare);
//↓
//↓		最初の呼び出しレベルで、[[低位要素の並び],ピボット,[高位要素の並び]]は、以下のようになります。
//↓
//↓			[[(空)],1,[2,3,4,...,10000]]	(呼び出しの深さ=1)
//↓
//↓		[高位要素の並び]に対する再帰呼び出しに注目すると、次のレベルで、[[低位要素の並び],ピボット,[高位要素の並び]]は、以下のようになります。
//↓
//↓			[[(空)],2,[3,4,5,...,10000]]	(呼び出しの深さ=2)
//↓
//↓		さらに次のレベルでは、[[低位要素の並び],ピボット,[高位要素の並び]]は、以下のようになります。
//↓
//↓			[[(空)],3,[4,5,6,...,10000]]	(呼び出しの深さ=3)
//↓
//↓		最後には、こうなります。
//↓
//↓			[[(空)],10000,[(空)]]	(呼び出しの深さ=10000)
//↓
//↓		以上の例のように、あらかじめソートされた数列をソートしようとすると、非常に深い再帰呼び出しが発生する場合があります。
//↓		数列の長さをNとすると、最大Nレベルの再帰呼び出しが発生します。(あらかじめ完全にソートされている数列をソートしようとした場合)
//↓		あらかじめ完全にソートされている数列に限らずとも、ある程度ソートされていればいるほど、再帰呼び出しが深くなる可能性があります。
//↓
//↓		実際にどのぐらい深くなるかは数列の初期状態に依存し、qsort()を実行してみるまでわからないので、危険です。
//↓		特に、P/ECEのようなスタック領域の小さな実行環境で利用する場合に危険です。
//↓
//↓- 上述の問題を改善する方法は、以下のとおりです。
//↓	・[低位要素の並び]と[高位要素の並び]のうち、要素が少ない方を再帰呼び出しでソートします。
//↓	・要素が多い方は、現在の呼び出しレベルのまま、最初から処理を繰り返すことでソートします。
//↓  このように変更することで、再帰呼び出しの最大深さが、最悪でも log2(N) に抑えられます。
//↓- たとえば、10000要素の数列をソートする場合、改善前は最悪10000レベルの再帰呼び出しが発生していましたが、改善後は最悪でも14レベルに抑えられます。
//↓  ソート対象の現実的な長さを考慮すると、約20レベル以上の再帰呼び出しが発生する状況はほぼ有り得ないと考えられるので、P/ECEでも充分に安全です。
//↓- ただし、上述の改善はあくまでもメモリ効率(=再帰呼び出しレベル)に関するものであり、時間効率は改善されないことに注意してください。
//↓  10000要素のint配列をソートする時間を計ってみると、ランダム数列ならば約1600ミリ秒ですが、あらかじめソートされていると約15300ミリ秒かかりました。
//↓
//↓	[参考文献：P.J.プラウガー著「標準Ｃライブラリ ANSI/ISO/JIS C規格」（トッパン）初版 411〜412ページ 本文]
void
qsort(void* base, size_t num, size_t width, int (*compare)(const void*, const void*))
{
	unsigned char* pv;	/* ピボットへのポインタ */
	unsigned char* lo;	/* 低位ポインタ (次に低位要素(ピボット以下の要素)を格納する位置へのポインタ) */
	unsigned char* hi;	/* 高位ポインタ (次に高位要素(ピボット超過の要素)を格納する位置へのポインタ) */
	int lo_cnt;		/* 低位要素数 */
	int hi_cnt;		/* 高位要素数 */

	/* 要素数が0または1ならば、何もせずに帰ります。
	 * - EPSON版は、2要素の場合も特別扱いして、単純な比較と入れ替えを行っていますが、その必要はありません。
	 *   2要素の場合も、それ以上の要素数の場合と同じ、通常の処理で対応できます。
	 */
	while(num >= 2) {
		/* ポインタと要素数を初期化します。
		 * - EPSON版は、配列の中央付近と先頭の要素を入れ替え、もともと中央付近にあった値をピボットとしています。
		 *   元からある程度昇順に並んでいると仮定して、中央付近に中央値があることを期待しているのだと思います。
		 *   しかし実際にはあまり効果が無く、むしろ余計な入れ替えの回数が増える分、性能を落としているようです。
		 *   そこでCLiP版では、単純に先頭の要素をピボットとして採用することにしました。
		 */
		pv = base;			/* ピボット     = 先頭 */
		lo = pv + width;		/* 低位ポインタ = ピボットの次 */
		hi = pv + width * (num - 1);	/* 高位ポインタ = 末尾 */
		lo_cnt = 0;			/* 低位要素数   = 0 */
		hi_cnt = 0;			/* 高位要素数   = 0 */

		/* 低位ポインタと高位ポインタが交差するまで...(即ち、ピボット以外の全要素の低位or高位が確定するまで)
		 * - (num-1)回のカウントダウンでループする方法でも同じ結果を得られますが、(lo<=hi)でループする方が、
		 *   num変数の生存期間を短くし、自動変数のレジスタ割り当て最適化がより有効に働くことが期待できます。
		 */
		//while(lo <= hi) { /* 注意!!(lo<hi)ではありません!! */
		//↓* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
		//↓- (num>=2)の条件より初回は必ず(lo<=hi)となるので、while(){...}よりも効率的なdo{...}while()に替えられます。
		do {
			/* 低位ポインタの位置に有る要素を、ピボットと比較します。 */
			if(compare(lo, pv) <= 0) {
				/* 低位要素ならば、低位ポインタの位置に格納します。
				 * 低位ポインタの次の位置に有る要素が、次回の比較対象となります。
				 */
				lo += width;
				lo_cnt++;
			} else {
				/* 高位要素ならば、高位ポインタの位置に格納します。
				 * 高位ポインタの位置に有った要素が、次回の比較位置に移動します。
				 */
				swap(lo, hi, width);
				hi -= width;
				hi_cnt++;
			}
		//}
		//↓* Thu Apr 19 14:58:48 JST 2007 Naoyuki Sawa
		//↓- (num>=2)の条件より初回は必ず(lo<=hi)となるので、while(){...}よりも効率的なdo{...}while()に替えられます。
		} while(lo <= hi); /* 注意!!(lo<hi)ではありません!! */

		/* 以上の処理が終わった時点で[ピボット,[低位要素の並び],[高位要素の並び]]となっています。
		 * [[低位要素の並び],ピボット,[高位要素の並び]]と入れ替えて、ピボットの位置を確定します。
		 * - 入れ替え時に低位要素の並び順が変化しますが、まだ並び順に意味はないので、大丈夫です。
		 * - もし低位要素が一つも無い場合、pv==hiとなっていて、このswap()処理はダミーとなります。
		 */
		swap(pv, hi, width);

		/* [低位要素の並び]と[高位要素の並び]のうち、要素が少ない方を再帰呼び出しでソートします。
		 * 要素が多い方は、現在の呼び出しレベルのまま、最初から処理を繰り返すことでソートします。
		 * - 両方を再帰呼び出しでソートすると、非常に深い再帰が発生してしまう場合を防ぐためです。
		 *   具体的には、この関数の上に書いたコメントを参照してください。
		 */
		if(lo_cnt <= hi_cnt) {
			/* [低位要素の並び]をソートします。 */
			qsort(pv, lo_cnt, width, compare); /* 注意!![低位要素の並び]の先頭を指しているのは、loでなくpvです!! */
			/* [高位要素の並び]をソートします。 */
			base = lo, num = hi_cnt;           /* 注意!![高位要素の並び]の先頭を指しているのは、hiでなくloです!! */
		} else {
			/* [高位要素の並び]をソートします。 */
			qsort(lo, hi_cnt, width, compare); /* 注意!![高位要素の並び]の先頭を指しているのは、hiでなくloです!! */
			/* [低位要素の並び]をソートします。 */
			base = pv, num = lo_cnt;           /* 注意!![低位要素の並び]の先頭を指しているのは、loでなくpvです!! */
		}
	}
}

/*****************************************************************************
 *	
 *****************************************************************************/

#if 0	/*{{ヒープソートの実装例*/

* Sun May 13 14:21:21 JST 2007 Naoyuki Sawa
- 「ヒープソート - Wikipedia」の擬似コードを参考に、最適化して作成しました。
  (URL: http://ja.wikipedia.org/w/index.php?title=%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88&oldid=12248591)
  最適化した主な点は、親や子の要素を指し示すためのインデクスを使わずに、すべてポインタで処理して高速化を図ったことです。
- ヒープソートがクィックソートよりも優れている点は、データのかたよりが速度にあまり影響しないことです。
  クィックソートは、一様にランダムな数列のソートがいちばん早く、元々順列のソートは遅く、逆順のソートがもっとも遅いです。
  ヒープソートは、どのケースに対してもおおよそ同じぐらいの速度で完了します。
- しかし実際には、クィックソートよりもヒープソートを選択する場面は無いと思います。
  クィックソートに不利な逆順のソートであっても、クィックソートの方がヒープソートよりも二倍ぐらい早く完了できるようです。
  一様にランダムな数列のソートの場合は、50倍以上の速度差が付いてしまいます。
  (Windowsで実験した場合はここまでの速度差は付かなかったのですが、P/ECEではなぜか上述のような大差になってしまいました。)
- 以下のコードは、正しく動くことを確認済みですが、実際に使うことは無いと思います。
  リンクサイズが増えないようにコメントアウトしてありますので、もし使う場合はアプリケーションにコピーして使ってください。

static void
make_heap(unsigned char* base, unsigned char* last, size_t width, int (*compare)(const void*, const void*), unsigned char* parent)
{
	unsigned char* child1;
	unsigned char* child2;

	/* 左の子が有れば... */
	child1 = (base + (parent - base) * 2) + width;
	if(child1 <= last) {
		/* 左の子のツリーをソートします。 */
		make_heap(base, last, width, compare, child1);
		/* 右の子が有れば... */
		child2 = child1 + width;
		if(child2 <= last) {
			/* 右の子のツリーをソートします。 */
			make_heap(base, last, width, compare, child2);
			/* child1が大きい方の子を指すようにします。 */
			if(compare(child1, child2) < 0) {
				child1 = child2;
			}
		}
		/* 大きい方の子が親よりも大きければ... */
		if(compare(parent, child1) < 0) {
			/* 大きい方の子と親を入れ替えます。 */
			swap(parent, child1, width);
			//make_heap(base, last, width, compare, child1);
			//→子のツリーのソートは次回に行うので不要です。
		}
	}
}

void
hsort(void* _base, size_t num, size_t width, int (*compare)(const void*, const void*))
{
	unsigned char* base = _base;
	unsigned char* last = base + (width * (num - 1));

	while(base < last) {
		/* ツリー全体を降順にソートします。 */
		make_heap(base, last, width, compare, base);
		/* 最大要素をツリーの末尾に切り離します。 */
		swap(base, last, width);
		last -= width;
	}
}

#endif	/*}}ヒープソートの実装例*/
