/*	SDB - sort routines	*/

#include "bdscio.h"
#include "dbqdefs.h"

struct skey *get_skeys(sptr)
	struct scan *sptr;
{
	struct skey *skeys,*newskey,*lastskey;

	skeys = lastskey = NULL;
	while (TRUE) {
		if (db_ntoken() != ID)
			{ RETERR(SYNTAX) }

		if ((newskey = CALLOC(KEYSIZE)) == NULL)
			{ RETERR(INSMEM) }

		newskey->sk_next = NULL;
		if (!sfind_attr(sptr,newskey,dbv_tstring)) {
			CFREE(newskey);
			return (NULL);
		}
		if (db_token() == ASCENDING || dbv_token == DESCENDING) {
			newskey->sk_type = dbv_token;
			db_ntoken();
		}
		else
			newskey->sk_type = ASCENDING;

		if (lastskey == NULL)
			skeys = newskey;
		else
			lastskey->sk_next = newskey;
		lastskey = newskey;

		if (db_token() != ',')
			break;
		db_ntoken();
	}
	return (skeys);
}

int *db_sort(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
	char *fmt;
{
	struct scan *sptr1,*sptr2,*sptr3;
	struct skey *skeys;
	int result;
#ifdef DBPI
	if (fmt != NULL)
		db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
#endif
	result = FALSE;		/* be pessimistic */
	if (db_token() == ID)
		db_ntoken();
	else
		strcpy(dbv_tstring,"current");
	if ((sptr1 = db_ropen(dbv_tstring)) == NULL)
		goto sortex;
	if ((sptr2 = db_ropen(dbv_tstring)) == NULL)
		goto sortx1;
#ifdef QUICKSORT
	if ((sptr3 = db_ropen(dbv_tstring)) == NULL)
		goto sortx2;
#endif
	if (db_ntoken() != BY) {
		dbv_errcode = SYNTAX;
		goto sortx3; }
	if ((skeys = get_skeys(sptr1)) == NULL)
		goto sortx3;

	result = dqsort(skeys,sptr1,sptr2,sptr3);

	free_skeys(skeys);

sortx3:
#ifdef QUICKSORT
	db_rclose(sptr3);
#endif
sortx2:
	db_rclose(sptr2);
sortx1:
	db_rclose(sptr1);
sortex:
	return (result);
}

free_skeys(skeys)
	struct skey *skeys;
{
	struct skey *thisskey;

	for (thisskey = skeys; skeys != NULL; thisskey = skeys) {
		skeys = skeys->sk_next;
		CFREE(thisskey);
	}
}

int sfind_attr(sptr,newskey,aname)
	struct scan *sptr; struct skey *newskey; char *aname;
{
	struct attribute *aptr;
	int i,astart;
	astart = 1;
	for (i = 0; i < NATTRS; i++) {
		aptr = &sptr->sc_relation->rl_header.hd_attrs[i];

		if (aptr->at_name[0] == 0)
			break;

		if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
			newskey->sk_start = astart;
			newskey->sk_aptr = aptr;
			return (TRUE);
		}

		astart += aptr->at_size;
	}

	RETERR(ATUNDF)
}

int dqsort(skeys,sptr1,sptr2,sptr3)
	struct skey *skeys; struct scan *sptr1,*sptr2,*sptr3;
{
	int passes, swaps;
	int i,j,m,n;
	int rec1,rec2,rec3;
	int k, l, r;	/* orig */

	passes = 0; swaps = 0;

#ifdef QUICKSORT

	rec1 = 0; rec2 = 0; rec3 = 0;
	n = sptr1->sc_relation->rl_tcnt;
	m = n;

	while(m>1) {
		passes++;
		if ((m/=3) < 1) m = 1;
		for (j=1; j<=n-m; j++) {
		  if (rec1 != j+m) {
			if (!db_rget(sptr1, rec1=j+m)) return (FALSE);
			}
		  for (i=j; i>=1; i-=m) {
			if (rec2 != i) {
				if (!db_rget(sptr2, rec2=i)) return (FALSE);
				}
			if (scompare(skeys,sptr1,sptr2) > 0)
				break;
			if (rec3 != i+m) {
				if (!db_rget(sptr3, rec3=i+m)) return (FALSE);
				}
			sassign( sptr3, sptr2);
			swaps++;
			}
		  if (rec1 != i+m) {
			if (rec3 != i+m) {
				if (!db_rget(sptr3, rec3=i+m)) return (FALSE);
				}
			sassign( sptr3, sptr1);
			swaps++;
			}
		  }
		}

#else
/*	original sort	*/

	l = 2;
	r = sptr1->sc_relation->rl_tcnt;
	k = r;

	do {
		for (j = r; j >= l; j--) {
			if (!db_rget(sptr1,j-1))
				return (FALSE);
			if (!db_rget(sptr2,j))
				return (FALSE);
			if (scompare(skeys,sptr1,sptr2) > 0) {
				sswap(sptr1,sptr2);
				k = j;
				swaps++;
			}
		}
		l = k + 1;
		for (j = l; j <= r; j++) {
			if (!db_rget(sptr1,j-1))
				return (FALSE);
			if (!db_rget(sptr2,j))
				return (FALSE);
			if (scompare(skeys,sptr1,sptr2) > 0) {
				sswap(sptr1,sptr2);
				k = j;
				swaps++;
			}
		}
		r = k - 1;
		passes++;
	} while (l <= r);

#endif

	printf("%d swaps in %d passes\n",swaps,passes);

	return (TRUE);
}

int scompare(skeys,sptr1,sptr2)
	struct skey *skeys; struct scan *sptr1,*sptr2;
{
	struct skey *cskey;
	int result;
	for (cskey = skeys; cskey != NULL; cskey = cskey->sk_next)
		if ((result = cattr(cskey,sptr1,sptr2)) != 0)
			break;
	return (result);
}

int cattr(cskey,sptr1,sptr2)
	struct skey *cskey; struct scan *sptr1,*sptr2;
{
	int astart,aend,i;

	astart = cskey->sk_start;
	aend = astart + cskey->sk_aptr->at_size;
	for (i = astart; i < aend; i++)
		if (sptr1->sc_tuple[i] != sptr2->sc_tuple[i])
			break;
	if (i == aend)
		return (0);

	if (sptr1->sc_tuple[i] < sptr2->sc_tuple[i])
		if (cskey->sk_type == ASCENDING)
			return (-1);
		else
			return (1);
	else
		if (cskey->sk_type == ASCENDING)
			return (1);
		else
			return (-1);
}

#ifdef QUICKSORT
int sassign(sptr1,sptr2)
	struct scan *sptr1,*sptr2;
{
	unsigned tnum1, tnum2;

	tnum1 = sptr1->sc_atnum;

	if (!db_rput(sptr2,tnum1))
		return (FALSE);
	return (TRUE);
}

#else

int sswap(sptr1,sptr2)
	struct scan *sptr1,*sptr2;
{
	unsigned tnum1, tnum2;

	tnum1 = sptr1->sc_atnum;
	tnum2 = sptr2->sc_atnum;

	if (!db_rput(sptr1,tnum2))
		return (FALSE);
	if (!db_rput(sptr2,tnum1))
		return (FALSE);
	return (TRUE);
}

#endif

	if (!db_rput(sptr1,tnum2))
		return (FALSE);
	if (!db_rput(sptr2,tnum1))
		return (FALSE);
	return (TRUE);