#include <string.h>
#include <assert.h>
#include "etc.h"

#define baseelm(i) ((void*)((char*)base+(i)*sizeelm))
/*
	Tri général basé sur l'algorythme du shell sort
	Ce tri est pratiquement aussi rapide que qsort().
	Il n'est pas récursif, donc pas de stack overflow.
	Il devrait être utilisé de préférence à qsort. Il est complètement
	compatible.	
*/
export void hsort (
	void *base,			/* Adresse de base du vecteur à trier */
	int   nbelm,		/* Nombre d'élément dans le vecteur */
	int   sizeelm,		/* Dimension d'un élément en byte */
	int (*cmp) (const void *p1, const void *p2))
						/* Fonction de comparaison */
{
	if (nbelm > 1){
		int h;
		assert (sizeelm < 200);
		for (h = 1; h <= nbelm; h += h+h+1) ;

		do {
			h /= 3;
			for (int i = h; i < nbelm; i++) {
				int j = i;
				char tmp[200];
				memmove (tmp,baseelm(i),sizeelm);
				while ((*cmp)(tmp,baseelm(j-h)) < 0){
					memmove (baseelm(j),baseelm(j-h),sizeelm);
					j -= h;
					if (j < h) break;
				}
				memmove (baseelm(j),tmp,sizeelm);
			}
		} while (h != 1);
	}
}

#ifdef TEST
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

static void check (char *tb[], int nbelm)
{
	int i;
	for (i=0; i<nbelm-1; i++){
		if (strcmp(tb[i],tb[i+1])>0){
			printf ("Erreur %5d :%s: <-> :%s:\n",i,tb[i],tb[i+1]);
		}
	}
}

static int cmp (const void *p1, const void *p2)
{
	char **pt1 = (char**)p1;
	char **pt2 = (char**)p2;
	return (strcmp(*pt1,*pt2));
}

unsigned _stklen=30000;

void main (void)
{
	int i;
	static char *tb[]={
		"9","0","8","7","6","5","1","2","3","4"
	};
	char **tb2 = malloc (2000*sizeof(char*));
	for (i=0; i<10; i++) printf (":%s:\n",tb[i]);
	hsort (tb,10,sizeof(char*),cmp);
	for (i=0; i<10; i++) printf (":%s:\n",tb[i]);
	for (i=0; i<2000; i++) tb2[i] = tb[i%10];
	printf ("Debut du test long avec hsort, appuyez sur enter\n");
	getch();
	hsort (tb2,2000,sizeof(char*),cmp);
	printf ("fin\n");
	check (tb2,2000);
	printf ("fin check\n");
	for (i=0; i<2000; i++) tb2[i] = tb[i%10];
	printf ("Debut du test long avec qsort, appuyez sur enter\n");
	getch();
	qsort (tb2,2000,sizeof(char*),cmp);
	printf ("fin");
}

#endif