/* SDB - sort routines */

#include <stdio.h>
#include "sdbio.h"

extern int dbv_token;
extern char dbv_tstring[];
extern int dbv_tvalue;

/* get_skeys - get sort key list */
static struct skey *get_skeys(sptr)
  struct scan *sptr;
{
    struct skey *skeys,*newskey,*lastskey;

    /* parse a list of attribute names */
    skeys = lastskey = NULL;
    while (TRUE) {

	/* get attribute name */
	if (db_ntoken() != ID)
	    return (db_nerror(SYNTAX));

	/* allocate a sort key structure */
	if ((newskey = malloc(sizeof(struct skey))) == NULL)
    	    return (db_nerror(INSMEM));

	/* initialize the sort key structure */
	newskey->sk_next = NULL;

    	/* lookup the attribute name */
    	if (!find_attr(sptr,newskey,dbv_tstring)) {
    	    free(newskey);
    	    return (NULL);
    	}

	/* check for ascending or descending */
	if (db_token() == ASCENDING || dbv_token == DESCENDING) {
    	    newskey->sk_type = dbv_token;
	    db_ntoken();
	}
	else
	    newskey->sk_type = ASCENDING;

	/* link the sort key structure into the list */
	if (lastskey == NULL)
	    skeys = newskey;
	else
	    lastskey->sk_next = newskey;
	lastskey = newskey;

	/* check for more attributes */
	if (db_token() != ',')
	    break;
	db_ntoken();
    }

    /* return successfully */
    return (skeys);
}

/* db_sort - sort tuples in a relation */
int *db_sort(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
  char *fmt;
{
    struct scan *sptr1,*sptr2;
    struct skey *skeys;
    int result;

    /* check for a command line */
    if (fmt != NULL)
    	db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);

    /* checks for relation name */
    if (db_token() == ID)
    	db_ntoken();
    else
    	strcpy(dbv_tstring,"sdbcur");

    /* open the relation */
    if ((sptr1 = db_ropen(dbv_tstring)) == NULL)
	return (FALSE);
    if ((sptr2 = db_ropen(dbv_tstring)) == NULL) {
    	db_rclose(sptr1);
	return (FALSE);
    }

    /* checks for "<relation-name> by <sort-list>" */
    if (db_ntoken() != BY)
    	return (db_ferror(SYNTAX));
    if ((skeys = get_skeys(sptr1)) == NULL) {
    	db_rclose(sptr1);
    	db_rclose(sptr2);
    	return (FALSE);
    }

    /* do the sort */
    result = sort(skeys,sptr1,sptr2);

    /* close the relation */
    db_rclose(sptr1);
    db_rclose(sptr2);

    /* free the sort keys */
    free_skeys(skeys);

    return (result);
}

/* free_skeys - free a list of sort keys */
static free_skeys(skeys)
  struct skey *skeys;
{
    struct skey *thisskey;

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

/* find_attr - find an attribute */
static int find_attr(sptr,newskey,aname)
  struct scan *sptr; struct skey *newskey; char *aname;
{
    struct attribute *aptr;
    int i,astart;

    /* loop through each attribute within the relation */
    astart = 1;
    for (i = 0; i < NATTRS; i++) {

	/* get a pointer to the current attribute */
	aptr = &sptr->sc_relation->rl_header.hd_attrs[i];

	/* check for last attribute */
	if (aptr->at_name[0] == 0)
	    break;

	/* check for attribute name match */
    	if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
	    newskey->sk_start = astart;
	    newskey->sk_aptr = aptr;
	    return (TRUE);
	}

	/* update the attribute start */
	astart += aptr->at_size;
    }

    /* attribute name not found */
    return (db_ferror(ATUNDF));
}

/* sort - sort the relation */
static int sort(skeys,sptr1,sptr2)
  struct skey *skeys; struct scan *sptr1,*sptr2;
{
    unsigned int j,k,l,r;
    long int passes,swaps;

    passes = 0L;
    swaps = 0L;

    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 (compare(skeys,sptr1,sptr2) > 0) {
    		swap(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 (compare(skeys,sptr1,sptr2) > 0) {
    		swap(sptr1,sptr2);
    		k = j;
    		swaps++;
    	    }
    	}
    	r = k - 1;
    	passes++;
    } while (l <= r);

    printf("[ Passes: %ld  Swaps: %ld ]\n",passes,swaps);

    return (TRUE);
}

/* compare - compare two tuples */
static int compare(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);
}

/* cattr - compare two attributes */
static 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);
}

/* swap - swap two tuples */
static int swap(sptr1,sptr2)
  struct scan *sptr1,*sptr2;
{
    unsigned int 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);
}