/* sort.c - Shell-Metzner sort algorithm implemented by Glenn M. Lewis - 7/26/91
 */

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

static char rcs_id[] = "$Id: sort.c,v 1.3 1991/09/05 17:51:13 glewis Exp glewis $";

void swap_points(desc, p1, p2)
register DESC *desc;
register int p1, p2;
{
	register UWORD *edge;
	register int i;
	XYZ_st tmp;
	if (p1==p2) return;
	for (edge=desc->edge,i=2*desc->ecount; i--; edge++) {
		if (*edge==p1) *edge=p2;
		else if (*edge==p2) *edge=p1;
	}
	bcopy((char*)&desc->pnts[p1], (char*)&tmp, sizeof(XYZ_st));
	bcopy((char*)&desc->pnts[p2], (char*)&desc->pnts[p1], sizeof(XYZ_st));
	bcopy((char*)&tmp, (char*)&desc->pnts[p2], sizeof(XYZ_st));
}

void sort_points(desc, cmp)	/* Sort the boxes w/ Shell-Metzner algorithm */
register DESC *desc;
int (*cmp)();
{
	register int i, j, gap;

/* Sort the puppies! */

	if (desc->pcount <= 1) return;
	for (gap = desc->pcount/2; gap>0; gap/=2)
		for (i=gap; i<desc->pcount; i++)
			for (j=i-gap; j>=0; j-=gap) {
				if (cmp(&desc->pnts[j], &desc->pnts[j+gap])<0) break;
				/* Swap the points */
				swap_points(desc, j, j+gap);
			}
}