/*
 *------------------------------------------------------------
 *
 *      File..........: $RCSfile: splaysort.c,v $
 *      Revision......: $Revision: 1.2 $
 *      Author........: Gary Eddy (gary@cs.mu.OZ.AU)
 *			Alistair Moffat (alistair@cs.mu.OZ.AU)
 *      Date..........: $Date: 1995/09/07 06:19:17 $
 *
 *	Description:
 *		Sorts by repeated insertion into a splay tree.
 *		Insertions are done top down
 *
 *------------------------------------------------------------
 */

#include	<stdio.h>
#include	<stdlib.h>
#include	<malloc.h>
#include	<alloca.h>

char	*sort_name = "Splaysort";
char	*sort_version = "$Revision: 1.2 $";

/*
** Define DATAPTR for the 12 byte per record version of the program.
** Otherwise only 8 extra bytes per record are used and data
** references are done by indexing the data array.
** Different compiler/architecture combinations can cause wild
** variation in the ratio of speeds between these variations.
*/

#define DATAPTR

#ifdef DATAPTR
#define DATA(p) ((p)->data)
#else
#define DATA(p) (A+size*(p-T))
#endif

/*
** With the fast copy option enabled a more intelligent copy is used
** depending on the size of the items being copied.
** This approach adopted from the nqsort program of Bentley and McIlroy,
** see Software Practice and Experience, v23, n11, November 1993, 1249-65.
*/

#define FASTCOPY

#ifdef FASTCOPY
#define COPYCODE(TYPE, parmi, parmj, n) {         long i = (n) / sizeof (TYPE);         register TYPE *pi = (TYPE *) (parmi);         register TYPE *pj = (TYPE *) (parmj);         do {                 *pi++ = *pj++;                            } while (--i > 0);      }

void
copyfunc(char *d, char *s, int size, int copytype)
{
        if(copytype <= 1)
                COPYCODE(long, d, s, size)
        else
                COPYCODE(char, d, s, size)
	return;
}

#define COPY(d,s,size)         if (copytype == 0) {                 *(long *)(d) = *(long *)(s);         } else                 copyfunc(d, s, size, copytype)
#else
#define COPY(d,s,size)	memcpy(d,s,size)
#endif

typedef struct  node_rec node;

struct	node_rec {
	node	*left, *rght;
#ifdef DATAPTR
	char	*data;
#endif
};

/*
 *	sort():
 *		The entire sort code 
 *
 *	Accesses outside variables:	none
 *
 *	Return value...:		none
 */

void
sort(void *A, size_t n, size_t size, int (*cmp)(const void *, const void *))
{
	register node *next, *curr, *prnt;
	char 	*item;
	node	*l, *r, *ch;
	node	root, *T, *new, *end, *move;
#ifndef DATAPTR
	char	*p;
#endif

/*
** Determine which copying method will be used.
*/
#ifdef FASTCOPY
	int	copytype=((char *)A - (char *)0) % sizeof(long) ||
		size % sizeof(long) ? 2 : size == sizeof(long) ? 0 : 1;
#endif


	if(n < 2)
		return;
	if((T = new = (node *) malloc(sizeof(*T)*n)) == NULL) {
		fprintf(stderr, "Couldn't allocate space for structure\n");
	}
	/* 
	** Do the first insertion manually to avoid the empty tree
	** case in the main loop.
	*/
	curr = new++;
	item = A;
	curr->left = curr->rght = NULL;
#ifdef DATAPTR
	curr->data = item;
#endif
	item += size;
	end = T+n;
	/*
	** For each item move down the tree dividing it into
	** two subtrees, one containing items less than the new
	** element and the other those which are greater.
	** The pointers l and r refer to the greatest element in the
	** smaller subtree and the smallest element in the large
	** subtree respectively. During the splitting of the tree
	** l and r retain children that may be incorrect in the final
	** tree but these false links are cut at the end of the
	** insertion.
	*/

	for( ; new<end; ) {
		l = r = &root;
		while(curr != NULL) {
			if(cmp(item, DATA(curr)) < 0) {
				/* Left root case */
				if((ch = curr->left) == NULL) {
					r = r->left = curr;
					break;
				}
				/* Left zig-zig */
				else if(cmp(item, DATA(ch)) < 0) {
					curr->left = ch->rght;
					ch->rght = curr;
					r = r->left = ch;
					curr = ch->left;
				}
				/* Left zig-zag */
				else {
					r = r->left = curr;
					l = l->rght = ch;
					curr = ch->rght;
				}
			}
			else {
				/* Right root case */
				if((ch = curr->rght) == NULL) {
					l = l->rght = curr;
					break;
				}
				/* Right zig-zag */
				else if (cmp(item, DATA(ch)) < 0) {
					l = l->rght = curr;
					r = r->left = ch;
					curr = ch->left;
				}
				/* Right zig-zig */
				else {
					curr->rght = ch->left;
					ch->left = curr;
					l = l->rght = ch;
					curr = ch->rght;
				}
			}
		}
		/* Cut false links */
		r->left = l->rght = NULL;
		new->rght = root.left;
		new->left = root.rght;
#ifdef DATAPTR
		new->data = item;
#endif
		curr = new++;
		item += size;
	}
	/* Now copy all of the data back into the input array.
	** Uses an iterative destructive inorder traversal.
	** Last item inserted is the current root.
	*/
	prnt = NULL;
	move = T;
	while (1) {
		if ((next = curr->left) != NULL) {
			/* left subtree exists */
			curr->left = prnt;
			prnt = curr;
			curr = next;
		}
		else {
			next = curr->rght;
			curr->rght = move++;
			if (next != NULL) {
				/* and arrange for a visit */
				if((curr = next->left) != NULL) {
					next->left = prnt;
					prnt = next;
					continue;
				}
				else {
					curr = next;
					continue;
				}
			}
			/* no right subtree either, turn around*/
			if (prnt != NULL) {
				curr = prnt;
				prnt = prnt->left;
				curr->left = NULL;
				continue;
			}
			/* nothing left to be done */
			break;
		}
	}
#ifndef DATAPTR
	/*
	** Change the goes-to array in rght to a comes_from in left.
	** Note the kludge on pointers, where left points into the 
	** character array containing the elements.
	*/
	for(next = T, p = A; next < end; p += size, next++)
		next->rght->left = (node *)p;
	/* and use the `comes from' array to unscramble the permutation */
	item = (char *)malloc(size);
        for (next=T; next<end; next++) {
                char *datacurr, *dataleftcurr, *final;
                if (next->left == NULL)
                        continue;
                curr = next;
                final = datacurr = DATA(curr);
                COPY(item, datacurr, size);
                while ((char *)(curr->left) != final) {
                        dataleftcurr = (char *)(curr->left);
                        COPY(datacurr, dataleftcurr, size);
                        prnt = curr;
                        curr = T + (((char *)(curr->left)-A)/size);
                        prnt->left = NULL;
                        datacurr = dataleftcurr;
                }
                COPY(datacurr, item, size);
                curr->left = NULL;
        }
#else
	/* Change the goes-to array in rght to a comes_from in left */
	for(next = T; next < end; next++)
		next->rght->left = next;
	/* and use the `comes from' array to unscramble the permutation */
	/*
	** This 12 byte version uses the presence of the data pointer
	** by making it the flag for already placed items. This means
	** that left pointers can point to nodes, eliminating the
	** calculation to find the next node.
	*/
	item = (char *)malloc(size);
	for (next=T; next<end; next++) {
		char *datacurr, *dataleftcurr, *final;
		/* second condition guarantees at least one iteration
		** of while loop.
		*/
		if (DATA(next) == (char *) NULL || next->left == next)
			continue;
		final = datacurr = DATA(next);
		curr = next->left;
		COPY(item, datacurr, size);
		while ((dataleftcurr = DATA(curr)) != final) {
			COPY(datacurr, dataleftcurr, size);
			prnt = curr;
			curr = curr->left;
			DATA(prnt) = (char *) NULL;
			datacurr = dataleftcurr;
		}
		COPY(datacurr, item, size);
		DATA(curr) = (char *) NULL;
	}
#endif
	free(item);
	free(T);
} /* sort() */