#include "ge_sort.h"

inline void GeSortAndSearch::Bswap(CHAR *a,CHAR *b,LONG i)
{
	CHAR tmp;
  		
	for(a--,b--,i++;--i;)
  {
 		tmp=*++b;
 		*b=*++a;
 		*a=tmp;
  }
}

inline void GeSortAndSearch::Wswap(WORD *a,WORD *b,LONG i)
{
	WORD tmp;
		
	for(a--,b--,i++;--i;)
  {
 		tmp=*++b;
 		*b=*++a;
 		*a=tmp;
  }
}

inline void GeSortAndSearch::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 GeSortAndSearch::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 GeSortAndSearch::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((WORD*)lp,(WORD*)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((WORD*)ip,(WORD*)jp,s);	
			else break;
		}
	}
}

void GeSortAndSearch::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 GeSortAndSearch::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 *GeSortAndSearch::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;
}
