#include <string.h>
#include <assert.h>
#include "vfs.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.	
*/
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