/* * * (c) COPYRIGHT INRIA, 1996. * Please first read the full copyright statement in file COPYRIGHT. * */ /* module de tri d'une table d'index */ /* module indtri.c */ #include "thot_sys.h" #include "indmsg.h" #include "libmsg.h" #include "message.h" #include "constmedia.h" #include "typemedia.h" #include "constind.h" #include "typeind.h" #undef THOT_EXPORT #define THOT_EXPORT extern #include "index_tv.h" static int codech[Lg_Cle]; /* dans coder : codage d'une cle d'index */ static int homo; /* dans NouvHomo : numero de semantique pour tab_homo */ static char homo_cle[MaxHomo][Lg_Cle]; /* liste des semantiques */ /* procedures importees de l'editeur */ #include "tree_f.h" #include "search_f.h" #include "exceptions_f.h" #include "indcree_f.h" #include "indtable_f.h" #include "memory_f.h" #include "structschema_f.h" #include "registry_f.h" /*---------------------------------------------------------------------- Ind_nouvhomo calcule les numero des homographes ----------------------------------------------------------------------*/ #ifdef __STDC__ static int Ind_nouvhomo (char *cle) #else /* __STDC__ */ static int Ind_nouvhomo (cle) char *cle; #endif /* __STDC__ */ { int i = 1; boolean trouve = FALSE; /* on suppose que cle n'est pas vide */ while (i <= homo && !trouve) { if (strcmp (cle, homo_cle[i]) == 0) trouve = TRUE; else i++; } /* end of while */ if (!trouve) { /* verifier si on ne depasse pas MaxHomo ! */ if (homo >= MaxHomo) TtaDisplaySimpleMessage (INFO, INDEX, INDEX_STOP_SEMANTICS); /* Tant pis, on ne separe pas les semantiques excedentaires */ else /* ajouter une semantique dans la table */ homo++; strncpy (homo_cle[homo], cle, Lg_Cle); return (homo); } else return (i); } /* end of proc Ind_nouvhomo */ /*---------------------------------------------------------------------- Ind_indpar initialise le repertoire ou trouver les codes de tri avec la variable d'environnement indpar ----------------------------------------------------------------------*/ void Ind_indpar () { char *pt; /* prend le repertoire par defaut dans l'environnement */ pt = TtaGetEnvString ("DICOPAR"); if (pt == NULL) { /* la variable d'environnement indpar n'existe pas */ Irepertoire[0] = '\0'; /* pas de variable d'environnement dicopar */ TtaDisplayMessage (INFO, TtaGetMessage (LIB, TMSG_MISSING_DICOPAR), "DICOPAR"); } else strcpy (Irepertoire, pt); } /* end of Ind_indpar */ /********************* initcodetri *****************************/ #ifdef __STDC__ static boolean initcodetri () #else /* __STDC__ */ static boolean initcodetri () #endif /* __STDC__ */ { boolean ret = FALSE; Buffer nomfichier; FILE *fcodetri; int i; unsigned char ch1[80], ch2[80], ch3[80], ch4[80], ch5[80]; unsigned char x, y; strcpy (nomfichier, Irepertoire); switch (Ialgo) { case ALPHA: strcat (nomfichier, "/Falpha.tri"); /* tri des caracteres francais min */ break; case ALPHANUM: strcat (nomfichier, "/Fnum.tri"); /* num + alpha */ break; case ALPHATYPO: strcat (nomfichier, "/Ftypo.tri"); /* tri separe maj et min */ break; case ALPHAPERSO: strcat (nomfichier, "/Fperso.tri"); /* num + alpha */ break; default: strcat (nomfichier, "/Fdefaut.tri"); /* num + alpha + speciaux */ break; } /* end of switch */ if ((fcodetri = fopen (nomfichier, "r")) != NULL) { ret = TRUE; for (i = 0; i < 256; i++) TriCode1[i] = -1; for (i = 0; i < 256; i++) TriCode2[i] = -1; TriPrem[0] = '\0'; TriCap[0] = '\0'; i = 1; while ((fscanf (fcodetri, "%s%s%s%s%s", ch1, ch2, ch3, ch4, ch5) != EOF) && (i < NbLtrTri)) { unsigned char z; int valeur1, valeur2; sscanf (ch1, "%c", &x); sscanf (ch2, "%d", &valeur1); sscanf (ch3, "%d", &valeur2); sscanf (ch4, "%c", &y); sscanf (ch5, "%c", &z); TriCode1[x] = valeur1; TriCode2[x] = valeur2; TriPrem[x] = y; TriCap[x] = z; i++; } fclose (fcodetri); /* ajouter le code de l'espace */ x = ' '; /* toujours traite comme le trait d'union et l'apostrophe */ y = '-'; if (TriCode1[y] == 0) /* ignore dans le tri */ TriCode1[x] = 0; else TriCode1[x] = TriCode1[y] - 1; TriCode2[x] = TriCode2[y]; TriPrem[x] = TriPrem[y]; TriCap[x] = TriPrem[y]; } return ret; } /* end of initcodetri */ /********************* initgroupetri *****************************/ #ifdef __STDC__ static boolean initgroupetri (int num) #else /* __STDC__ */ static boolean initgroupetri (num) int num; #endif /* __STDC__ */ { PtrSSchema pSS; int C_PIV_TYPE; unsigned char xfirst, xlast, capfirst; int i, icode; PtrElement pEl, pGroupe, pEl1, pEl2; boolean ret = TRUE; boolean stop = FALSE, trouve = FALSE; /* rechercher le definition des groupes dans les options de cette table */ pEl = Ind_table (num); pSS = pEl->ElStructSchema; if (pEl == NULL) /* impossible de trouver les options de cette table */ TtaDisplayMessage (INFO, TtaGetMessage (INDEX, INDEX_OPTIONS), num); else { C_PIV_TYPE = GetElemWithException (1264, pSS); /* Idx_CarGroupe */ pGroupe = FwdSearchTypedElem (pEl, C_PIV_TYPE, pSS); while (!stop && pGroupe != NULL) { if (pEl == pGroupe->ElParent->ElParent->ElParent) { trouve = TRUE; /* modifier les caracteristiques du groupe */ pEl1 = pGroupe->ElFirstChild; /* Idx_CarElem */ if (pEl1 != NULL) { xfirst = pEl1->ElFirstChild->ElText->BuContent[0]; capfirst = TriCap[xfirst]; pEl2 = pEl1->ElNext; while (pEl2 != NULL) { xlast = pEl2->ElFirstChild->ElText->BuContent[0]; /* modifier le TriPrem de tous les caracteres */ /* ayant le meme TriCode2 que le cacartere xlast */ icode = TriCode2[xlast]; for (i = 0; (i <= 256); i++) if (TriCode2[i] == icode) TriPrem[i] = capfirst; pEl2 = pEl2->ElNext; } /* end of while */ } /* end of if pEl1 != NULL */ } /* end of if */ else if (trouve) stop = TRUE; /* c'est fini */ /* passer au suivant */ pGroupe = FwdSearchTypedElem (pGroupe, C_PIV_TYPE, pSS); } /* end of while */ } /* ATTENTION : Aucun controle sur l'odre des lettres d'un groupe */ /* ===> ret est toujours TRUE */ return ret; } /* end of initgroupetri */ /*---------------------------------------------------------------------- coder la chaine s avec le code num si num = 0 alors, ne pas coder ----------------------------------------------------------------------*/ #ifdef __STDC__ static int *coder (unsigned char *s, int num) #else /* __STDC__ */ static int *coder (s, num) unsigned char *s; int num; #endif /* __STDC__ */ { int i = 0; int j = 0; int n = 0; boolean stop = FALSE; int codecar = 0; char lecar[2]; if (num != 0) { while (!stop && s[i] != 0) { codecar = (num == 1) ? TriCode1[(unsigned char) s[i]] : TriCode2[(unsigned char) s[i]]; if (codecar == -1) { /* caractere SANS CODE ??? : on le mettra en tete !!! */ } if (codecar == -2) /* c'est un chiffre : coder en numerique */ { lecar[0] = s[i]; lecar[1] = '\0'; n = atoi (lecar); /* lire les chiffres suivants pour calculer ce nombre */ i++; stop = FALSE; while (!stop && s[i] != 0) { codecar = (num == 1) ? TriCode1[(unsigned char) s[i]] : TriCode2[(unsigned char) s[i]]; if (codecar == -2) /* chiffre suivant */ { lecar[0] = s[i]; n = (n * 10) + atoi (lecar); i++; } else stop = TRUE; } /* end of while */ codecar = 200 + n; /* codes < 200 reserves aux lettres */ stop = (s[i] == 0) ? TRUE : FALSE; } /* end of if */ codech[j] = codecar; if (codecar == 0) { /* dedoubler la lettre : OE ou AE */ switch (s[i]) { case 247: /* oe \367= (o + e) ou (o + e' \351) */ codech[j] = (num == 1) ? TriCode1['o'] : TriCode2['o']; j++; codech[j] = (num == 1) ? TriCode1[233] : TriCode2['e']; break; case 215: /* OE \327 = (O + E) ou (O + E' \311) */ codech[j] = (num == 1) ? TriCode1['O'] : TriCode2['O']; j++; codech[j] = (num == 1) ? TriCode1[201] : TriCode2['E']; break; case 230: /* ae \346 = (a + e) ou (a + e' \351) */ codech[j] = (num == 1) ? TriCode1['a'] : TriCode2['a']; j++; codech[j] = (num == 1) ? TriCode1[233] : TriCode2['e']; break; case 198: /* AE\306 = (A + E) ou (A + E' \311) */ codech[j] = (num == 1) ? TriCode1['A'] : TriCode2['A']; j++; codech[j] = (num == 1) ? TriCode1[201] : TriCode2['E']; break; default: /* ignorer les caracteres dont le code est 0 */ /* -, ', espace . Exemple : grand-pere = grandpere */ j--; /* ne rien mettre dans ch */ break; } /* end of switch */ } if (!stop) i++; j++; } } /* end of if */ codech[j] = -99; /* c'est la fin du codage de cette chaine ! */ return (codech); /* attention : codech peut etre plus longue que s */ } /* end of coder */ /*---------------------------------------------------------------------- codenumcmp : compare les codes c1 et c2 -1 si c1 < c2 0 si c1 = c2 1 si c1 > c2 ----------------------------------------------------------------------*/ #ifdef __STDC__ static int codenumcmp (int *c1, int *c2) #else /* __STDC__ */ static int codenumcmp (c1, c2) int *c1; int *c2; #endif /* __STDC__ */ { int i = 0; while (i < Lg_Cle) { if (c1[i] == -99 && c2[i] == -99) return (0); if (c1[i] == -99 || c1[i] < c2[i]) return (-1); if (c2[i] == -99 || c1[i] > c2[i]) return (1); else i++; } /* end of while */ return (0); } /* end of codenumcmp */ /*---------------------------------------------------------------------- codecmp : compare s1 et s2 dans le code num ----------------------------------------------------------------------*/ #ifdef __STDC__ int codecmp (unsigned char *s1, unsigned char *s2, int num) #else /* __STDC__ */ int codecmp (s1, s2, num) unsigned char *s1; unsigned char *s2; int num; #endif /* __STDC__ */ { int codech1[Lg_Cle], codech2[Lg_Cle]; int *ptch; int ret = -1; int i; if (s1 != NULL && s2 != NULL) { ptch = coder (s1, num); for (i = 0; (i < Lg_Cle && ptch[i] != -99); i++) codech1[i] = ptch[i]; codech1[i] = -99; /* marque la fin du mot code' */ ptch = coder (s2, num); for (i = 0; (i < Lg_Cle && ptch[i] != -99); i++) codech2[i] = ptch[i]; codech2[i] = -99; /* marque la fin du mot code' */ ret = codenumcmp (codech1, codech2); } /* end of if */ return (ret); } /* end of codecmp */ /*---------------------------------------------------------------------- echanger : echange t[i] et t[j] ----------------------------------------------------------------------*/ #ifdef __STDC__ static void echanger (int *t, int i, int j) #else /* __STDC__ */ static void echanger (t, i, j) int *t; int i; int j; #endif /* __STDC__ */ { int temp; temp = t[i]; t[i] = t[j]; t[j] = temp; } /* echanger */ /*---------------------------------------------------------------------- trinul : place les nuls (-1) en dernier et reordonne les indices dans tab_ind ----------------------------------------------------------------------*/ #ifdef __STDC__ static void trinul (int *t, int gauche, int droite) #else /* __STDC__ */ static void trinul (t, gauche, droite) int *t; int gauche; int droite; #endif /* __STDC__ */ { int i, premier, deb; void echanger (); i = gauche; while (i <= droite && t[tab_ind[i]] == -1) i++; if (i != gauche && i <= droite) { premier = i; deb = gauche; for (i = premier; i <= droite; echanger (tab_ind, deb++, i++)) ; } } /*trinul */ /*---------------------------------------------------------------------- trinum : tri les entiers du tableau t de gauche a droite par ordre croissant et reordonne les indices dans tab_ind ----------------------------------------------------------------------*/ #ifdef __STDC__ static void trinum (int *t, int gauche, int droite) #else /* __STDC__ */ static void trinum (t, gauche, droite) int *t; int gauche; int droite; #endif /* __STDC__ */ { int i, dernier; void echanger (); if (gauche >= droite) /* ne rien faire si le tableau */ return; /* contient moins de 2 elements */ echanger (tab_ind, gauche, (gauche + droite) / 2); dernier = gauche; for (i = gauche + 1; i <= droite; i++) if (t[tab_ind[i]] < t[tab_ind[gauche]]) echanger (tab_ind, ++dernier, i); echanger (tab_ind, gauche, dernier); trinum (t, gauche, dernier - 1); trinum (t, dernier + 1, droite); } /*---------------------------------------------------------------------- triref : tri t de gauche a droite par ordre croissant des tab_ind[valeur] et reordonne les indices dans tab_ind ----------------------------------------------------------------------*/ #ifdef __STDC__ static void triref (int *t, int gauche, int droite) #else /* __STDC__ */ static void triref (t, gauche, droite) int *t; int gauche; int droite; #endif /* __STDC__ */ { int i, j, k, dernier; void echanger (); if (gauche >= droite) /* ne rien faire si le tableau */ return; /* contient moins de 2 elements */ echanger (tab_ind, gauche, (gauche + droite) / 2); dernier = gauche; for (i = gauche + 1; i <= droite; i++) { for (j = 0; ((j < itabcle) && tab_ind[j] != t[tab_ind[i]]); j++) ; for (k = 0; ((k < itabcle) && tab_ind[k] != t[tab_ind[gauche]]); k++) ; if (j < k) echanger (tab_ind, ++dernier, i); } echanger (tab_ind, gauche, dernier); triref (t, gauche, dernier - 1); triref (t, dernier + 1, droite); } /*triref */ /*---------------------------------------------------------------------- trirapide : trie v[gauche]....v[droite] avec la fonction de comparaison passee en parametre (cf qsort) ----------------------------------------------------------------------*/ #ifdef __STDC__ static void trirapide (PtrTabCle * v, int gauche, int droite, int (*comp) (), int num) #else /* __STDC__ */ static void trirapide (v, gauche, droite, comp, num) PtrTabCle *v; int gauche; int droite; int (*comp) (); int num; #endif /* __STDC__ */ { char *ch1; char *ch2; int i, dernier; void echanger (); if (gauche >= droite) /* ne rien faire si le tableau */ return; /* contient moins de 2 elements */ echanger (tab_ind, gauche, (gauche + droite) / 2); dernier = gauche; for (i = gauche + 1; i <= droite; i++) { ch1 = v[tab_ind[i]]; ch2 = v[tab_ind[gauche]]; if ((*comp) (ch1, ch2, num) < 0) echanger (tab_ind, ++dernier, i); } echanger (tab_ind, gauche, dernier); trirapide (v, gauche, dernier - 1, comp, num); trirapide (v, dernier + 1, droite, comp, num); } /*trirapide */ /*---------------------------------------------------------------------- Ind_trier : tri des 3 niveaux de cle, de la semantique et par ordre des references ----------------------------------------------------------------------*/ #ifdef __STDC__ static void Ind_trier (int (*fcompar) ()) #else /* __STDC__ */ static void Ind_trier (fcompar) int (*fcompar) (); #endif /* __STDC__ */ { PtrTabCle *tabcar; /* tableau de pointeurs vers les cles */ PtrTabInd tabint; /* tableau d'entier : pour tri page, pagefin, note */ int i, i1, idebut, ifin, ifirst, j, jdebut, niveau, iniveau; int egal, niveau2; void *ch1; void *ch2; PtrTabTri pTT, pTT1, pTT2; boolean stop; /* allocation dynamique de memoire tabint (itabcle) */ tabint = (PtrTabInd) TtaGetMemory ((itabcle + 1) * sizeof (int)); tabcar = (PtrTabCle *) TtaGetMemory ((itabcle + 1) * sizeof (int)); /* TRI de itabcle elements (exactement) */ /* TRI de PREMIER NIVEAU */ /* d'abord, comparer tous les caracteres codes avec TriCode2 */ niveau = 0; for (i1 = 0; i1 <= itabcle; i1++) { pTT = pTri[i1]; tabcar[i1] = pTT->cle[niveau]; } trirapide (tabcar, 0, itabcle, (int (*)()) fcompar, 2); /* TRI de PREMIER NIVEAU des ex-aequo codees par TriCode2 -> avec TriCode1 */ egal = 0; i = 0; while (i < itabcle) { pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; ch1 = pTT1->cle[niveau]; ch2 = pTT2->cle[niveau]; /* retrouver les ex-aequo avec TriCode2 */ egal = fcompar (ch1, ch2, 2); if (egal == 0) { idebut = i; i++; for (j = idebut + 1; ((j < itabcle) && (egal == 0)); j++) { pTT1 = pTri[tab_ind[j]]; pTT2 = pTri[tab_ind[j + 1]]; ch1 = pTT1->cle[niveau]; ch2 = pTT2->cle[niveau]; egal = fcompar (ch1, ch2, 2); } i = j; /* retrier toutes les cles avec le TriCode1 */ j = (egal == 0) ? j : j - 1; trirapide (tabcar, idebut, j, (int (*)()) fcompar, 1); } else i++; } /* end of while */ /* boucle de TRI SUR LES AUTRES NIVEAUX (cles) */ for (niveau = 1; niveau < MaxNiveau; niveau++) { for (i1 = 0; i1 <= itabcle; i1++) { pTT = pTri[i1]; tabcar[i1] = pTT->cle[niveau]; } i = 0; while (i < itabcle) { egal = 0; pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau < niveau) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; egal = fcompar (ch1, ch2, 1); } if (egal == 0) { /* deux entrees de meme cle avant ce niveau */ niveau2 = iniveau - 1; /* le dernier niveau ou egal == 0 */ idebut = i; i++; while (egal == 0 && (i < itabcle)) { pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau <= niveau2) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; egal = fcompar (ch1, ch2, 1); } i++; } /* end of while */ /* retrier toutes les cles de ce niveau avec TriCode2 */ j = (egal == 0 && i == itabcle) ? i : i - 1; trirapide (tabcar, idebut, j, (int (*)()) fcompar, 2); } else i++; } /* end of while */ /* RETRIER ce niveau */ /* les ex-aequo codees par TriCode2 -> avec TriCode1 */ i = 0; while (i < itabcle) { egal = 0; pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau <= niveau) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; /* retrouver les ex-aequo avec TriCode2 */ egal = fcompar (ch1, ch2, (iniveau < niveau) ? 1 : 2); } if (egal == 0) { /* deux entrees de meme cle a ce niveau */ idebut = i; i++; while (egal == 0 && (i < itabcle)) { /* chercher s'il y en a d'autres egales a ces cles */ pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau <= niveau) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; egal = fcompar (ch1, ch2, (iniveau < niveau) ? 1 : 2); } i++; } /* end of while */ /* retrier toutes les cles avec le TriCode1 */ j = (egal == 0) ? i : i - 1; trirapide (tabcar, idebut, j, (int (*)()) fcompar, 1); } else i++; } /* end of while */ } /* end of for */ /* reclasser les entrees par ordre de reference (finir par les croisees) */ niveau = MaxNiveau - 1; i = 0; while (i < itabcle) { egal = 0; pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau <= niveau) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; egal = fcompar (ch1, ch2, 1); } if (egal == 0) { /* deux entrees de meme cle a tous les niveaux */ idebut = i; i++; while (egal == 0 && (i < itabcle)) { pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; for (iniveau = 0; ((iniveau <= niveau) && (egal == 0)); iniveau++) { ch1 = pTT1->cle[iniveau]; ch2 = pTT2->cle[iniveau]; egal = fcompar (ch1, ch2, 1); } i++; } /* end of while */ /* retrier toutes les references de ce niveau */ if (egal != 0) i = i - 1; ifin = i; /* ordonner selon la premiere page */ for (i1 = 0; i1 <= itabcle; i1++) { pTT = pTri[i1]; tabint[i1] = pTT->page; } trinum (tabint, idebut, ifin); /* replacer les references croisees en dernier */ trinul (tabint, idebut, ifin); /* Ordonner les intervalles de meme premiere page de cette entree */ j = idebut; while (j < ifin) { ifirst = j; egal = TRUE; while (j < ifin && egal) { pTT1 = pTri[tab_ind[j]]; pTT2 = pTri[tab_ind[j + 1]]; if (pTT1->page == pTT2->page) j++; else egal = FALSE; } if (j > ifirst) /* il y a plusieurs pages initiales egales */ { for (i1 = 0; i1 <= itabcle; i1++) { pTT = pTri[i1]; tabint[i1] = pTT->pagefin; } pTT1 = pTri[tab_ind[j]]; pTT2 = pTri[tab_ind[j - 1]]; if (j == ifin && pTT1->page != pTT2->page) trinum (tabint, ifirst, j - 1); else trinum (tabint, ifirst, j); } j++; } /* Trier les notes de meme page de cette entree */ j = idebut; while (j < ifin) { ifirst = j; egal = TRUE; while (j < ifin && egal) { pTT1 = pTri[tab_ind[j]]; pTT2 = pTri[tab_ind[j + 1]]; if (pTT1->page == pTT2->page && pTT1->pagefin == pTT2->pagefin) j++; else egal = FALSE; } if (j > ifirst) /* il y a plusieurs notes de meme page */ { for (i1 = 0; i1 <= itabcle; i1++) { pTT = pTri[i1]; tabint[i1] = pTT->note; } pTT1 = pTri[tab_ind[j]]; pTT2 = pTri[tab_ind[j - 1]]; if (j == ifin && (pTT1->page != pTT2->page || pTT1->pagefin != pTT2->pagefin)) trinum (tabint, ifirst, j - 1); else trinum (tabint, ifirst, j); } j++; } /* Trier les references croisees dans leur ordre */ /* d'apparition dans la table d'index (= ordre alphabetique) */ j = idebut; /* sauter les references non croisees */ stop = FALSE; jdebut = ifin + 1; for (j = idebut; (j < ifin) && (!stop); j++) { pTT = pTri[tab_ind[j]]; if (pTT->page == -1) { stop = TRUE; jdebut = j; } } /* end of for */ /* reordonner les references croisees */ /* pagefin contient le numero de l'entree pointee */ for (i1 = jdebut; i1 <= ifin; i1++) { pTT = pTri[tab_ind[i1]]; tabint[i1] = pTT->pagefin; } if (jdebut < ifin) triref (tabint, jdebut, ifin); } else i++; } /* end of while */ /* liberation de la memoire allouee pour tabint et tabcar */ TtaFreeMemory ((char *) tabint); TtaFreeMemory ((char *) tabcar); } /* end of Ind_trier */ /*---------------------------------------------------------------------- Ind_verifcle ----------------------------------------------------------------------*/ #ifdef __STDC__ static boolean Ind_verifcle () #else /* __STDC__ */ static boolean Ind_verifcle () #endif /* __STDC__ */ { boolean ok = TRUE; int i, j, k, isi, isj; PtrTabTri pTT; isi = 0; isj = 0; /* verifier que les cles a trier et la semantique */ /* sont dans l'alphabet defini pour le tri sinon ARRET et msg d'erreur */ for (i = 0; (i < MaxNiveau && ok); i++) for (j = 0; (j <= itabcle && ok); j++) { pTT = pTri[j]; for (k = 0; (pTT->cle[i][k] != '\0' && ok); k++) { /* ce caractere est-il codable ? */ if (TriCode1[(unsigned char) pTT->cle[i][k]] == -1) { ok = FALSE; isi = i; isj = j; } } /* end of for k */ } /* end of for j */ if (!ok) { pTT = pTri[isj]; TtaDisplayMessage (INFO, TtaGetMessage (INDEX, INDEX_BAD_KEY), pTT->cle[isi]); } /* end of if */ return (ok); } /* end of Ind_verifcle */ /*---------------------------------------------------------------------- Ind_tritable trier dans l'ordre de tri et remplir tab_homo > 0 des homographes ----------------------------------------------------------------------*/ #ifdef __STDC__ static int Ind_tritable (int (*fcomp) ()) #else /* __STDC__ */ static int Ind_tritable (fcomp) int (*fcomp) (); #endif /* __STDC__ */ { int i, j, k, k1, idebut, ifin; boolean egal; int (*fcompar) (); void *ch1; void *ch2; int list_ind[MaxRefCle1]; /* pour le tri des semantiques */ PtrTabTri pTT1, pTT2; /* allouer et initialiser tab_ind avant de faire le tri */ tab_ind = (PtrTabInd) TtaGetMemory ((itabcle + 1) * sizeof (int)); /* initialiser cette table d'indice */ for (i = 0; i <= itabcle; i++) tab_ind[i] = i; /* pas de tri a faire pour une seule entree */ if (itabcle == 0) return (1); /* ATTENTION : verifier au prealable que les cles a trier */ /* sont dans l'alphabet defini pour le tri */ /* sinon convertir ces cles ou les refuser !!! */ if (!Ind_verifcle ()) { Ialgo = -1; /* cle non triable avec l'algo de tri choisi */ return (-1); /* on abandonne le tri */ } /* trier les cles, la semantique et les references aux pages */ fcompar = fcomp; Ind_trier (fcomp); /* remplir tab_homo dans le cas des homographes */ i = 0; while (i < itabcle) { /* comparer seulement la premiere cle de ces deux descripteurs */ pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; ch1 = pTT1->cle[0]; ch2 = pTT2->cle[0]; egal = fcompar (ch1, ch2, 1); idebut = i; if (egal == 0) /* les 1e cles sont egales */ { i++; while ((egal == 0) && (i < itabcle)) { pTT1 = pTri[tab_ind[i]]; pTT2 = pTri[tab_ind[i + 1]]; ch1 = pTT1->cle[0]; ch2 = pTT2->cle[0]; egal = fcompar (ch1, ch2, 1); i++; } /* end of while */ if (egal != 0) i = i - 1; } /* end of if (egal == 0) */ ifin = i; /* remplir tab_homo de idebut a ifin */ j = idebut; homo = 0; /* renumerotation des semantiques a partir de 0 */ while (j <= ifin) { pTT1 = pTri[tab_ind[j]]; /* remplir tab_homo */ pTT1->homo = (pTT1->cle[MaxNiveau][0] == '\0') ? 0 : Ind_nouvhomo (pTT1->cle[MaxNiveau]); j++; } /* end of while */ if (homo != 0) { /* trier dans l'ordre des homo (sans changer l'ordre des cles) */ k1 = 0; /* indice dans la liste list_ind */ for (j = 0; j <= MaxHomo; j++) { k = idebut; while (k <= ifin) { pTT2 = pTri[tab_ind[k]]; if (pTT2->homo == j) { /* mettre dans la liste */ list_ind[k1] = tab_ind[k]; k1++; } /* end of if */ k++; } /* end of while */ } /* end of for */ /* recopier list_ind dans tab_ind (entre idebut et ifin) */ k = 0; for (j = idebut; j <= ifin; j++, k++) tab_ind[j] = list_ind[k]; } /* end of if */ /* passer au suivant */ i++; } /* end of while (i < itabcle) */ return (itabcle + 1); /* c'est OK */ } /* end of Ind_tritable */ /*---------------------------------------------------------------------- Ind_tri retourne -1 en cas d'erreur retourne nb d'entrees triees si c'est OK ----------------------------------------------------------------------*/ #ifdef __STDC__ int Ind_tri (int numtable) #else /* __STDC__ */ int Ind_tri (numtable) int numtable; #endif /* __STDC__ */ { if (numtable == 0) /* INITIALISE la table de codage pour le tri */ { if (!initcodetri ()) { /* impossible de trouver le fichier de tri dans indpar */ TtaDisplayMessage (INFO, TtaGetMessage (INDEX, INDEX_NO_FILE), numtable); return (-1); } return (0); } else { /* EFFECTUE le tri */ if (initgroupetri (numtable)) return (Ind_tritable (codecmp)); /* effectue le tri */ else /* erreur dans les options : definition des groupes */ { TtaDisplayMessage (INFO, TtaGetMessage (INDEX, INDEX_BAD_GROUP), numtable); return (-1); } } } /* end of Ind_tri */