/* test_heap.c Permet de tester les fonctions de heap.c en remplissant un tas avec des éléments aléatoires d'un type donné, puis de les extraire en vérifiant qu'ils apparaissent dans l'ordre croissant. Plusieurs types et fonctions de comparaisons peuvent être testés. NB: La fonction de comparaison double2(), qui consiste à renvoyer "x-y" converti en "int", produit un comportement intéressant qui est doublement erroné. D'abord "0.5-0.3", par exemple, est interprété comme "0.5-0.3"<=0 car (int)(0.5-0.3) = (int)(0.2) = 0. Et donc le programme pourra penser que le tableau final est effectivement trié ("success!") par ordre croissant, alors que c'est visiblement pas le cas. Mais plus grave encore, le programme peut afficher un échec ("fail!") alors que l'implémentation du tas est tout à fait correcte. Pourtant, "success!" et "fail!" sont déterminés d'après la même fonction de comparaison: pour la gestion du tas et pour la vérification final du tri. Cela vient du fait que la fonction double2() n'est pas transitive. On peut très bien avoir "x-y"=0 et "y-z"=0 mais avoir "x-z">0, par exemple avec x=1.2, y=0.7 et z=0.2. Donc, même avec une implémentation correcte, une fonction de comparaison non transitive peut faire échouer un tri par tas. */ #include "heap.h" #include #include #include #include #include #define BAR "-" // un tiret #define MAXSTR 7 // taille max d'une string #define xstr(s) str(s) // permet l'expansion d'une macro #define str(s) #s // Ex: scanf("%"xstr(DMAX)"s",buffer); typedef int (*fcmp)(const void*,const void*); // type fonction de comparaison typedef char* string; // type chaîne de caractères typedef struct{ double x,y; } point; // type point du plan //////////////////////////////////////////////////// int fcmp_int(const void *x, const void *y) { return *(int*)x - *(int*)y; } int fcmp_char(const void *x, const void *y) { return *(char*)x - *(char*)y; } int fcmp_double(const void *x, const void *y) { const double a = *(double*)x; const double b = *(double*)y; return (ab); // ou encore return (a>b) - (ax), &(((point*)q)->x) ); } //////////////////////////////////////////////////// enum{ // les types possibles, pour les switch() INT=0, CHAR, DOUBLE, DOUBLE2, STRING, POINT, }; int size[] = { // tableau des tailles des types sizeof(int), sizeof(char), sizeof(double), sizeof(double), sizeof(string), sizeof(point), }; int psize[] = { // tableau des tailles d'affichage des types 2, 1, 5, 5, MAXSTR, 9, }; fcmp cmp[] = { // tableau des fonctions de comparaison fcmp_int, fcmp_char, fcmp_double, fcmp_double2, fcmp_string, fcmp_pointx, }; char *type[] = { // tableau des types pour l'aide "int", "integers in [0,100[ (default)", "char", "capital letters in ['A','Z'[", "double", "real numbers in ]-1.00,+1.00[", "double2", "same as 'double' but with 'x-y' like fcmp()", "string", "strings of length at most "xstr(MAXSTR), "point", "real points of [0,9.9]×[0,9.9] with 'x' like fcmp()", }; //////////////////////////////////////////////////// // affiche T[i] avec le bon format suivant le type t // en ajoutant un espace " " terminal void print(int t, void *T, int i){ switch(t){ case INT: printf("%02i ", ((int*) T)[i]); break; case CHAR: printf("%c ", ((char*) T)[i]); break; case DOUBLE: case DOUBLE2: printf("%+1.2lf ", ((double*) T)[i]); break; case STRING: printf("%s ", ((string*) T)[i]); break; case POINT: printf("(%.1lf,%.1lf) ",((point*)T)[i].x, ((point*)T)[i].y); break; } } // initialisation aléatoire de l'élément T[i] void init(int t, void *T, int i){ switch(t){ case INT: { // entiers aléatoires dans [0,100[ ((int*)T)[i] = random()%100; } break; case CHAR: { // lettres majuscules aléatoires ((char*)T)[i] = 'A' + (random()%('Z'-'A'+1)); } break; case DOUBLE: case DOUBLE2: { // double aléatoires dans [-1,+1] avec 2 chiffres ((double*)T)[i] = ((random()%2000)-1000) / 1000.0; } break; case STRING: { // construit une chaîne aléatoire d'au plus MAXSTR char const int k = 1 + random()%MAXSTR; // k=1..MAXSTR string s = calloc(k+1,sizeof(char)); // remplit de '\0' for(int i=0; in; while(j>0) haut++, j>>=1; // On suppose que le pattern est de taille impaire 2s+1 avec s = // floor(psize[t]/2). Si taille est paire on fait pareil, ce qui // revient à ajouter virtuellement un espace terminal. On pourrait // faire une meilleure présentation dans le cas pair (= plus // compacte notamment sur la dernière ligne), mais cela complexifie. // // Ex: pattern PPP de taille psize[t] = 3 // // y=3| PPP // y=3| ┌───────┴───────┐ // y=2| PPP PPP // y=2| ┌───┴───┐ ┌───┴───┐ // y=1| PPP PPP PPP PPP // y=1| ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ // y=0|PPP PPP PPP PPP PPP PPP PPP PPP // // Variables (les positions démarrent à 0): // // pm = position du milieu (┴) // pp = position du début du pattern // pb = position du début de branche (┌) // lb = longueur de branche (entre ┌ et ┴) // eb = espace entre deux branches (entre ┐ et ┌) // ep = espace entre deux patterns // // Evolution des variables, à partir du bas (y=0,1,2,...): // // y=0 y=1 y=2 // // pm = s 2s+1 4s+3 ... => pm(y) = 2*pm(y-1)+1 = (s+1)*2^y - 1 // lb = . s 2s+1 ... => lb(y) = pm(y-1) // pb = . s 2s+1 ... => pb(y) = lb(y) // pp = 0 s+1 3s+3 ... => pp(y) = pm(y)-s // eb = . 2s+1 4s+3 ... => eb(y) = 2*eb(y-1)+1 = pm(y) // ep = 1 ... ... => ep(y) = 2*lb(y+1)+1-2s = 2*pm(y)+1-2s int s1,s2; int s=psize[t]/2; // nombre de caractères avant le milieu du pattern int B=1; // B = nombre de patterns dans la ligne j=0; // j = nombre d'éléments déjà affichés for(int y=haut-1; y>=0; y--, B<<=1){ // on part du haut int pm=(s+1)*(1<n); b++){ j++; if(psize[t]%2==0) printf(" "); // cas pair if(t==STRING){ // centrage si string s1=strlen(*(string*)h->array[j]); s2=(psize[t]-s1)/2; s1=psize[t]-s2-s1; rule(s1," "); // [s1 string s2] } print(t, h->array[j], 0); if(t==STRING) rule(s2," "); // centrage si string if(b=2)? atoi(argv[1]) : -1; // n = nombre d'éléments char *s = (argc>=3)? argv[2] : type[INT]; // t = type des éléments // double x=1.2, y=0.7, z=0.2; // printf("%g %g -> %d\n", x, y, fcmp_double2(&x,&y)); // 0 // printf("%g %g -> %d\n", y, z, fcmp_double2(&y,&z)); // 0 // printf("%g %g -> %d\n", x, z, fcmp_double2(&x,&z)); // 1 // exit(1); for(t=0; tf != cmp[t]){ printf(FAIL" wrong function\n\n"); fflush(stdout); goto fin; } printf("correct\n"); fflush(stdout); // teste que le tas soit bien vide au départ printf("heap empty? "); fflush(stdout); if ( !heap_empty(h) ){ printf(FAIL" it should be empty\n\n"); fflush(stdout); goto fin; } printf("yes\n"); fflush(stdout); // teste que le nombre max d'éléments soit correct printf("heap size? "); fflush(stdout); if (h->nmax != n){ printf(FAIL" heap size is %d whereas it should be %d\n\n", h->nmax, n); fflush(stdout); goto fin; } printf("correct\n"); fflush(stdout); // pour les tests de lecture/écriture dans la zone allouée on fait // une petite pause pour permettre de voir où le 'segmentation // fault' se produit, s'il se produit. Malheureusement passer le // test ne signifie pas que les malloc() dans heap_create() étaient // corrects. Ces tests pourraient peut-être affinés avec l'usage de // mmap() ou mprotect(). // test lecture printf("reading test in the heap array[1..%d]... ",n); printf("\E[?25l"); // echo off fflush(stdout); for(i=1; i<=n; i++){ int k = printf("%d",i); printf("\E[%dD",k); // retour de k colonnes à gauche fflush(stdout); usleep(1000000/n); // pause d'une seconde au total void *w = h->array[i]; // lecture (void)w; // pour éviter le warning 'w not used' } printf("\E[?25h"); // echo on printf("ok\E[K\n"); fflush(stdout); // test écriture printf("writing test in the heap array[1..%d]... ",n); printf("\E[?25l"); // echo off fflush(stdout); for(i=1; i<=n; i++){ int k = printf("%d",i); printf("\E[%dD",k); // retour de k colonnes à gauche fflush(stdout); // écriture usleep(1000000/n); // pause d'une seconde au total h->array[i] = (void*)main; } printf("\E[?25h"); // echo on printf("ok\E[K\n"); fflush(stdout); // déplace les éléments de T[] vers h avec des add() printf("\ntesting insertions:\n\n"); fflush(stdout); for (i = 0; i] y ..." si x>y (pas le bon ordre) printf("output array: "); for (i=0, r=1; i0){ // seulement à partir du 2e élément int c = cmp[t](S+(i-1)*size[t],S+i*size[t]); // S[i-1] <= S[i] ? if( c>0 ){ r=0; printf("[>] "); } // y'a un problème } print(t, S, i); // affiche S[i] } printf("\n%s the above array is %ssorted\n\n", r? "success!" : FAIL, r?"":"not "); fflush(stdout); fin:; // libération de la mémoire if(t==STRING) // cas d'un tableau de string for(i=0; i