#include "ge_sort.h"
#ifdef __API_INTERN__
	#include "ge_tools.h"
#else
	#include "c4d_general.h"
#endif

inline void GeSortAndSearchEx::Bswap(CHAR *a, CHAR *b, LONG i)
{
	CHAR tmp;

	for (a--, b--, i++; --i; )
	{
		tmp = *++b;
		*b = *++a;
		*a = tmp;
	}
}

inline void GeSortAndSearchEx::Wswap(SWORD *a, SWORD *b, LONG i)
{
	SWORD tmp;

	for (a--, b--, i++; --i; )
	{
		tmp = *++b;
		*b = *++a;
		*a = tmp;
	}
}

inline void GeSortAndSearchEx::Lswap(LONG *a, LONG *b, LONG i)
{
	LONG tmp;

	for (a--, b--, i++; --i; )
	{
		tmp = *++b;
		*b = *++a;
		*a = tmp;
	}
}

#define CalcSortPtr(i)	(((CHAR*)start)+(msize*((i)-1)))

void GeSortAndSearchEx::Bsort(void *start, LONG count, LONG msize)
{
	LONG l, r, j;
	CHAR *lp, *rp, *ip, *jp, *kp;

	if (count < 2) return;

	r = count;
	l = (r >> 1) + 1;

	lp = CalcSortPtr(l);
	rp = CalcSortPtr(r);

	for (;;)
	{
		if (l > 1)
		{
			l--;
			lp -= msize;
		}
		else
		{
			Bswap(lp, rp, msize);
			if (--r == 1) return;
			rp -= msize;
		}

		j = l;
		jp = CalcSortPtr(j);

		while ((j << 1) <= r)
		{
			j <<= 1;
			ip = jp;
			jp = CalcSortPtr(j);

			if (j < r)
			{
				kp = jp + msize;
				if (Compare(jp, kp) < 0)
				{
					j++;
					jp = kp;
				}
			}

			if (Compare(ip, jp) < 0) Bswap(ip, jp, msize);
			else break;
		}
	}
}

void GeSortAndSearchEx::Wsort(void *start, LONG count, LONG msize)
{
	LONG l, r, j, s = msize >> 1;
	CHAR *lp, *rp, *ip, *jp, *kp;

	if (count < 2) return;

	r = count;
	l = (r >> 1) + 1;

	lp = CalcSortPtr(l);
	rp = CalcSortPtr(r);

	for (;;)
	{
		if (l > 1)
		{
			l--;
			lp -= msize;
		}
		else
		{
			Wswap((SWORD*)lp, (SWORD*)rp, s);
			if (--r == 1) return;
			rp -= msize;
		}

		j = l;
		jp = CalcSortPtr(j);

		while ((j << 1) <= r)
		{
			j <<= 1;
			ip = jp;
			jp = CalcSortPtr(j);

			if (j < r)
			{
				kp = jp + msize;
				if (Compare(jp, kp) < 0)
				{
					j++;
					jp = kp;
				}
			}

			if (Compare(ip, jp) < 0) Wswap((SWORD*)ip, (SWORD*)jp, s);
			else break;
		}
	}
}

void GeSortAndSearchEx::Lsort(void *start, LONG count, LONG msize)
{
	LONG l, r, j, s = msize >> 2;
	CHAR *lp, *rp, *ip, *jp, *kp;

	if (count < 2) return;

	r = count;
	l = (r >> 1) + 1;

	lp = CalcSortPtr(l);
	rp = CalcSortPtr(r);

	for (;;)
	{
		if (l > 1)
		{
			l--;
			lp -= msize;
		}
		else
		{
			Lswap((LONG*)lp, (LONG*)rp, s);
			if (--r == 1) return;
			rp -= msize;
		}

		j = l;
		jp = CalcSortPtr(j);

		while ((j << 1) <= r)
		{
			j <<= 1;
			ip = jp;
			jp = CalcSortPtr(j);

			if (j < r)
			{
				kp = jp + msize;
				if (Compare(jp, kp) < 0)
				{
					j++;
					jp = kp;
				}
			}

			if (Compare(ip, jp) < 0) Lswap((LONG*)ip, (LONG*)jp, s);
			else break;
		}
	}
}

void GeSortAndSearchEx::Sort(void *start, LONG count, LONG msize)
{
	if (!(msize&3)) Lsort(start, count, msize);
	else if (!(msize&1)) Wsort(start, count, msize);
	else Bsort(start, count, msize);
}


#define CalcSearchPtr(i)	(((CHAR*)Start)+(msize*(i)))

void *GeSortAndSearchEx::Search(void *Key, void *Start, LONG count, LONG msize)
{
	LONG l, r, m, c;
	CHAR *mp, *mt;

	if (!Key || !Start || !count || !msize) return NULL;

	mp = CalcSearchPtr(0);
	c = Compare(Key, mp);

	if (c == 0) return (mp);
	else if (c < 0) return NULL;

	l = 1;
	r = count - 1;

	while (l <= r)
	{
		m = (l + r) >> 1;
		mp = CalcSearchPtr(m);
		c = Compare(Key, mp);
		if (c == 0)
		{
			while (m > 0)
			{
				m--;
				mt = CalcSearchPtr(m);
				if (Compare(Key, mt)) break;
				else mp = mt;
			}
			return mp;
		}
		else if (c < 0) r = m - 1;
		else l = m + 1;
	}

	return NULL;
}

void *GeSortAndSearchEx::SearchOrInsert(void *Key,void *Start,LONG count,LONG msize, LONG &insertidx)
{
	LONG l,r,m,c;
	CHAR *mp,*mt;

	if (!Key||!Start||!count||!msize)
	{
		insertidx = NOTOK;
		return NULL;
	}

	mp=CalcSearchPtr(0);
	c=Compare(Key,mp);

	if (c==0) return(mp);
	else if(c<0)
	{
		insertidx = 0;
		return NULL;
	}

	l=1;
	r=count-1;
	m=0; // if (c>0) but r<l

	while(l<=r)
	{
		m=(l+r)>>1;
		mp=CalcSearchPtr(m);
		c=Compare(Key,mp);
		if(c==0)
		{
			while(m>0)
			{
				m--;
				mt=CalcSearchPtr(m);
				if(Compare(Key,mt)) break;
				else mp=mt;
			}
			return mp;
		}
		else if(c<0) r=m-1;
		else l=m+1;
	}

	if (c>0)
	{
		insertidx = m+1;
	}
	else
	{
		insertidx = m;
	}
#ifdef _DEBUG
	if (insertidx<count)
	{
		mp=CalcSearchPtr(insertidx);
		if (Compare(Key,mp)>=0)
			GeBoom();
	}
	if (insertidx>0)
	{
		mp=CalcSearchPtr(insertidx-1);
		if (Compare(Key,mp)<=0)
			GeBoom();
	}
#endif
	return NULL;
}
