Annotation of rpl/src/simplification.c, revision 1.70
1.1 bertrand 1: /*
2: ================================================================================
1.68 bertrand 3: RPL/2 (R) version 4.1.32
1.66 bertrand 4: Copyright (C) 1989-2019 Dr. BERTRAND Joël
1.1 bertrand 5:
6: This file is part of RPL/2.
7:
8: RPL/2 is free software; you can redistribute it and/or modify it
9: under the terms of the CeCILL V2 License as published by the french
10: CEA, CNRS and INRIA.
11:
12: RPL/2 is distributed in the hope that it will be useful, but WITHOUT
13: ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14: FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL V2 License
15: for more details.
16:
17: You should have received a copy of the CeCILL License
18: along with RPL/2. If not, write to info@cecill.info.
19: ================================================================================
20: */
21:
22:
1.11 bertrand 23: #include "rpl-conv.h"
1.1 bertrand 24:
25:
26: /*
27: ================================================================================
1.69 bertrand 28: Fonction d'affichage d'un arbre q-aire
29: ================================================================================
30: Entrées : pointeur sur une structure struct_processus
31: --------------------------------------------------------------------------------
32: Sorties :
33: --------------------------------------------------------------------------------
34: Effets de bord : néant
35: ================================================================================
36: */
37:
38: static void
39: affichage_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre,
40: int niveau)
41: {
42: int i;
43:
44: integer8 branche;
45:
46: struct_liste_chainee *l_element_courant;
47:
48: unsigned char *chaine;
49:
50: if (niveau == 0)
51: {
1.70 ! bertrand 52: printf("--- Arbre $%016X\n", s_arbre);
1.69 bertrand 53: }
54:
55: // Affichage de la feuille (fonction ou donnée générale s'il n'y
56: // a pas de branche)
57:
58: l_element_courant = (*s_arbre).feuille;
59:
60: while(l_element_courant != NULL)
61: {
62: if ((chaine = formateur(s_etat_processus, 0,
63: (*l_element_courant).donnee)) == NULL)
64: {
65: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
66: return;
67: }
68:
69: for(i = 0; i < niveau; i++)
70: {
71: printf(" ");
72: }
73:
74: printf("%s\n", chaine);
75: free(chaine);
76:
77: l_element_courant = (*l_element_courant).suivant;
78: }
79:
80: // Affichage des branches (arguments de la fonction dans la feuille)
81:
82: for(branche = 0; branche < (*s_arbre).nombre_branches; branche++)
83: {
84: affichage_arbre(s_etat_processus, (*s_arbre).branches[branche],
85: niveau + 1);
86: }
87:
88: if (niveau == 0)
89: {
1.70 ! bertrand 90: printf("--- Fin de l'arbre\n");
1.69 bertrand 91: }
92:
93: return;
94: }
95:
96:
97: /*
98: ================================================================================
1.50 bertrand 99: Fonction de transcription d'un arbre en liste chaînée
1.1 bertrand 100: ================================================================================
101: Entrées : pointeur sur une structure struct_processus
102: --------------------------------------------------------------------------------
103: Sorties :
104: --------------------------------------------------------------------------------
105: Effets de bord : néant
106: ================================================================================
107: */
108:
1.50 bertrand 109: static struct_liste_chainee *
110: transcription_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre)
1.1 bertrand 111: {
1.50 bertrand 112: integer8 i;
1.1 bertrand 113:
114: struct_liste_chainee *l_element_courant;
1.50 bertrand 115: struct_liste_chainee *l_liste;
116: struct_liste_chainee *l_nouvelle_pile_locale;
117: struct_liste_chainee *l_pile_locale;
1.1 bertrand 118:
1.50 bertrand 119: l_pile_locale = NULL;
1.1 bertrand 120:
1.50 bertrand 121: for(i = 0; i < (*s_arbre).nombre_branches; i++)
1.1 bertrand 122: {
1.50 bertrand 123: if ((l_nouvelle_pile_locale = allocation_maillon(s_etat_processus))
124: == NULL)
125: {
126: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
127: return(NULL);
128: }
1.1 bertrand 129:
1.50 bertrand 130: (*l_nouvelle_pile_locale).suivant = l_pile_locale;
131: l_pile_locale = l_nouvelle_pile_locale;
1.1 bertrand 132:
1.50 bertrand 133: if (((*l_pile_locale).donnee = (void *) transcription_arbre(
134: s_etat_processus, (*s_arbre).branches[i])) == NULL)
1.1 bertrand 135: {
1.50 bertrand 136: return(NULL);
1.1 bertrand 137: }
1.50 bertrand 138: }
139:
1.52 bertrand 140: // Ajout des fonctions
1.70 ! bertrand 141: // Arbre q-aire => si q branches, q-1 fonctions
1.1 bertrand 142:
1.52 bertrand 143: l_liste = (*s_arbre).feuille;
1.50 bertrand 144:
1.70 ! bertrand 145: for(i = 0; i < (*s_arbre).nombre_branches - 2; i++)
! 146: {
! 147: if ((l_element_courant = allocation_maillon(s_etat_processus))
! 148: == NULL)
! 149: {
! 150: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
! 151: return(NULL);
! 152: }
! 153:
! 154: (*l_element_courant).suivant = l_liste;
! 155:
! 156: if (((*l_element_courant).donnee = copie_objet(s_etat_processus,
! 157: (*l_liste).donnee, 'P')) == NULL)
! 158: {
! 159: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
! 160: return(NULL);
! 161: }
! 162:
! 163: l_liste = l_element_courant;
! 164: }
! 165:
1.50 bertrand 166: free((*s_arbre).branches);
167: free(s_arbre);
168:
169: // Chaînage des arguments
170:
171: while(l_pile_locale != NULL)
172: {
173: l_element_courant = (void *) (*l_pile_locale).donnee;
174:
175: if (l_element_courant == NULL)
1.1 bertrand 176: {
1.50 bertrand 177: (*s_etat_processus).erreur_systeme = d_es_pile_vide;
1.1 bertrand 178: return(NULL);
179: }
180:
1.50 bertrand 181: while((*l_element_courant).suivant != NULL)
1.1 bertrand 182: {
183: l_element_courant = (*l_element_courant).suivant;
184: }
185:
1.50 bertrand 186: (*l_element_courant).suivant = l_liste;
187: l_liste = (void *) (*l_pile_locale).donnee;
1.1 bertrand 188:
1.50 bertrand 189: l_nouvelle_pile_locale = (*l_pile_locale).suivant;
190: liberation_maillon(s_etat_processus, l_pile_locale);
191: l_pile_locale = l_nouvelle_pile_locale;
1.1 bertrand 192: }
193:
1.50 bertrand 194: return(l_liste);
1.1 bertrand 195: }
196:
197:
198: /*
199: ================================================================================
1.51 bertrand 200: Fonction de simplification d'un arbre
201: ================================================================================
202: Entrées : pointeur sur une structure struct_processus
203: --------------------------------------------------------------------------------
204: Sorties :
205: --------------------------------------------------------------------------------
206: Effets de bord : néant
207: ================================================================================
208: */
209:
1.70 ! bertrand 210: static int
! 211: ordonnancement_branches(const void *a1, const void *a2)
1.51 bertrand 212: {
1.70 ! bertrand 213: struct_arbre **_a1;
! 214: struct_arbre **_a2;
! 215:
! 216: _a1 = (struct_arbre **) a1;
! 217: _a2 = (struct_arbre **) a2;
! 218:
! 219: if (((**_a1).feuille != NULL) && ((**_a2).feuille != NULL))
! 220: {
! 221: if ((*(*(**_a1).feuille).donnee).type ==
! 222: (*(*(**_a2).feuille).donnee).type)
! 223: {
! 224: return(0);
! 225: }
! 226:
! 227: if (((*(*(**_a1).feuille).donnee).type == INT) ||
! 228: ((*(*(**_a1).feuille).donnee).type == REL) ||
! 229: ((*(*(**_a1).feuille).donnee).type == CPL))
! 230: {
! 231: return(1);
! 232: }
! 233: else
! 234: {
! 235: return(-1);
! 236: }
! 237: }
! 238:
! 239: return(0);
1.51 bertrand 240: }
241:
242:
243: static void
244: simplification_arbre(struct_processus *s_etat_processus,
1.52 bertrand 245: struct_arbre *s_arbre)
1.51 bertrand 246: {
1.52 bertrand 247: integer8 i;
1.70 ! bertrand 248: integer8 j;
! 249: integer8 nouveaux_elements;
! 250:
! 251: struct_objet *s_objet;
1.52 bertrand 252:
253: if ((*(*(*s_arbre).feuille).donnee).type != FCT)
254: {
255: // L'objet formant le noeud n'est pas une fonction. Il n'y a aucune
256: // simplification possible.
257:
258: return;
259: }
260:
1.70 ! bertrand 261: // La feuille est une fonction, on peut envisager la simplification
! 262: // de l'arbre. Pour cela, on descend d'un niveau pour greffer
! 263: // de nouvelles branches.
! 264:
! 265: if (strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee).objet))
! 266: .nom_fonction, "+") == 0)
1.52 bertrand 267: {
268: for(i = 0; i < (*s_arbre).nombre_branches; i++)
269: {
1.70 ! bertrand 270: s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
! 271:
! 272: if ((*s_objet).type == FCT)
! 273: {
! 274: if (strcmp((*((struct_fonction *) (*s_objet).objet))
! 275: .nom_fonction, "-") == 0)
! 276: {
! 277: }
! 278:
! 279: if (strcmp((*((struct_fonction *) (*s_objet).objet))
! 280: .nom_fonction, "+") == 0)
! 281: {
! 282: simplification_arbre(s_etat_processus,
! 283: (*s_arbre).branches[i]);
! 284:
! 285: /*
! 286: On greffe.
! 287: +
! 288: +
! 289: 2
! 290: SIN
! 291: 3
! 292: 10
! 293:
! 294: doit donner :
! 295: +
! 296: 2
! 297: SIN
! 298: 3
! 299: 10
! 300: */
! 301:
! 302: nouveaux_elements = (*(*s_arbre).branches[i])
! 303: .nombre_branches;
! 304:
! 305: if (((*s_arbre).branches = realloc((*s_arbre).branches,
! 306: ((unsigned) ((*s_arbre).nombre_branches
! 307: + nouveaux_elements))
! 308: * sizeof(struct_arbre *))) == NULL)
! 309: {
! 310: (*s_etat_processus).erreur_systeme =
! 311: d_es_allocation_memoire;
! 312: return;
! 313: }
! 314:
! 315: for(j = 0; j < nouveaux_elements; j++)
! 316: {
! 317: (*s_arbre).branches[(*s_arbre).nombre_branches++] =
! 318: (*(*s_arbre).branches[i]).branches[j];
! 319: }
! 320:
! 321: free((*s_arbre).branches[i]);
! 322:
! 323: // Retrait de la branche
! 324:
! 325: for(j = i + 1; j < (*s_arbre).nombre_branches; j++)
! 326: {
! 327: (*s_arbre).branches[j - 1] = (*s_arbre).branches[j];
! 328: }
! 329:
! 330: (*s_arbre).nombre_branches--;
! 331:
! 332: // Réorganisation des valeurs numériques en queue.
! 333:
! 334: qsort((*s_arbre).branches, (size_t) (*s_arbre)
! 335: .nombre_branches, sizeof(struct_arbre *),
! 336: ordonnancement_branches);
! 337: }
! 338: }
1.52 bertrand 339: }
1.70 ! bertrand 340:
! 341: if (((*s_arbre).branches = realloc((*s_arbre).branches,
! 342: ((unsigned) (*s_arbre).nombre_branches)
! 343: * sizeof(struct_arbre *))) == NULL)
1.52 bertrand 344: {
1.70 ! bertrand 345: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
! 346: return;
1.52 bertrand 347: }
348: }
349:
1.51 bertrand 350: return;
351: }
352:
353:
354: /*
355: ================================================================================
1.50 bertrand 356: Fonction 'simplification' (ne libère pas les paramètres)
1.1 bertrand 357: ================================================================================
1.50 bertrand 358: Entrées : pointeur sur une structure struct_processus
1.1 bertrand 359: --------------------------------------------------------------------------------
360: Sorties :
361: --------------------------------------------------------------------------------
362: Effets de bord : néant
363: ================================================================================
364: */
365:
1.50 bertrand 366: struct_objet *
367: simplification(struct_processus *s_etat_processus, struct_objet *s_objet)
1.1 bertrand 368: {
1.50 bertrand 369: struct_objet *s_objet_simplifie;
370:
371: integer8 i;
372: integer8 nombre_arguments;
373:
374: struct_arbre *s_arbre;
375:
376: struct_liste_chainee *l_element_courant;
377:
378: // Attention : l_liste_locale et l_ancienne_liste_locale ne contiennent pas
379: // un pointeur sur une struct_objet, mais sur une struct_arbre.
1.1 bertrand 380:
1.50 bertrand 381: struct_liste_chainee *l_liste_locale;
382: struct_liste_chainee *l_ancienne_liste_locale;
1.1 bertrand 383:
1.50 bertrand 384: if ((*s_objet).type == ALG)
1.1 bertrand 385: {
1.50 bertrand 386: /*
387: * Transcription de l'expression algébrique en arbre q-aire
388: */
1.1 bertrand 389:
1.50 bertrand 390: l_liste_locale = NULL;
391: l_element_courant = (*s_objet).objet;
1.1 bertrand 392:
1.50 bertrand 393: while(l_element_courant != NULL)
1.1 bertrand 394: {
1.50 bertrand 395: switch((*(*l_element_courant).donnee).type)
396: {
397: // Toutes les fonctions (intrinsèques, extrinsèques et
398: // utilisateurs).
399:
400: case FCT:
401: {
402: // Il s'agit d'un objet de type ALG. Nous pouvons donc
403: // sauter les délimiteurs d'expression.
404:
405: if ((l_element_courant != (*s_objet).objet) &&
406: ((*l_element_courant).suivant != NULL))
407: {
408: nombre_arguments = (*((struct_fonction *)
409: (*(*l_element_courant).donnee).objet))
410: .nombre_arguments;
411:
412: // Si le nombre d'arguments vaut 0, la fonction
413: // apparaît en notation algébrique comme une fonction
414: // infixe.
415:
416: if (nombre_arguments == 0)
417: {
418: nombre_arguments = 2;
419: }
420:
421: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
422: {
423: (*s_etat_processus).erreur_systeme =
424: d_es_allocation_memoire;
425: return(NULL);
426: }
427:
428: (*s_arbre).nombre_branches = nombre_arguments;
1.52 bertrand 429:
430: if (((*s_arbre).feuille = allocation_maillon(
431: s_etat_processus)) == NULL)
432: {
433: (*s_etat_processus).erreur_systeme =
434: d_es_allocation_memoire;
435: return(NULL);
436: }
437:
438: (*(*s_arbre).feuille).donnee = copie_objet(
439: s_etat_processus, (*l_element_courant).donnee,
440: 'P');
441: (*(*s_arbre).feuille).suivant = NULL;
1.50 bertrand 442:
443: if (((*s_arbre).branches = malloc(((size_t) (*s_arbre)
444: .nombre_branches) * sizeof(struct_arbre *)))
445: == NULL)
446: {
447: (*s_etat_processus).erreur_systeme =
448: d_es_allocation_memoire;
449: return(NULL);
450: }
451:
1.51 bertrand 452: for(i = nombre_arguments - 1; i >= 0; i--)
1.50 bertrand 453: {
454: if (l_liste_locale == NULL)
455: {
456: (*s_etat_processus).erreur_execution =
457: d_ex_manque_argument;
458: return(NULL);
459: }
460:
1.51 bertrand 461: (*s_arbre).branches[i] = (struct_arbre *)
1.50 bertrand 462: (*l_liste_locale).donnee;
463:
464: l_ancienne_liste_locale = l_liste_locale;
465: l_liste_locale = (*l_liste_locale).suivant;
466:
467: liberation_maillon(s_etat_processus,
468: l_ancienne_liste_locale);
469: }
470:
471: // Introduction de l'arbre dans la pile locale
472:
473: l_ancienne_liste_locale = l_liste_locale;
474:
475: if ((l_liste_locale = allocation_maillon(
476: s_etat_processus)) == NULL)
477: {
478: (*s_etat_processus).erreur_systeme =
479: d_es_allocation_memoire;
480: return(NULL);
481: }
482:
483: (*l_liste_locale).suivant = l_ancienne_liste_locale;
484: (*l_liste_locale).donnee = (void *) s_arbre;
485: }
1.1 bertrand 486:
1.50 bertrand 487: break;
488: }
1.1 bertrand 489:
1.50 bertrand 490: default:
1.1 bertrand 491: {
1.50 bertrand 492: l_ancienne_liste_locale = l_liste_locale;
493:
494: if ((l_liste_locale = allocation_maillon(s_etat_processus))
495: == NULL)
496: {
497: (*s_etat_processus).erreur_systeme =
498: d_es_allocation_memoire;
499: return(NULL);
500: }
501:
502: (*l_liste_locale).suivant = l_ancienne_liste_locale;
503:
504: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
505: {
506: (*s_etat_processus).erreur_systeme =
507: d_es_allocation_memoire;
508: return(NULL);
509: }
510:
1.52 bertrand 511: if (((*s_arbre).feuille = allocation_maillon(
512: s_etat_processus)) == NULL)
513: {
514: (*s_etat_processus).erreur_systeme =
515: d_es_allocation_memoire;
516: return(NULL);
517: }
518:
519: (*(*s_arbre).feuille).donnee = copie_objet(
520: s_etat_processus, (*l_element_courant).donnee, 'P');
521: (*(*s_arbre).feuille).suivant = NULL;
1.50 bertrand 522: (*s_arbre).nombre_branches = 0;
523: (*s_arbre).branches = NULL;
524:
525: (*l_liste_locale).donnee = (void *) s_arbre;
526: break;
1.1 bertrand 527: }
528: }
1.50 bertrand 529:
530: l_element_courant = (*l_element_courant).suivant;
1.1 bertrand 531: }
532:
1.50 bertrand 533: // Toute l'expression a été balayée. On ne doit plus avoir qu'un
534: // seul niveau dans la pile locale, ce niveau contenant l'arbre
535: // à réduire.
536:
537: if (l_liste_locale == NULL)
538: {
539: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
540: return(NULL);
541: }
542: else if ((*l_liste_locale).suivant != NULL)
543: {
544: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
545: return(NULL);
546: }
547:
548: s_arbre = (void *) (*l_liste_locale).donnee;
549:
550: liberation_maillon(s_etat_processus, l_liste_locale);
551: l_liste_locale = NULL;
552:
553: /*
554: * Simplification de l'arbre
555: */
556:
1.69 bertrand 557: affichage_arbre(s_etat_processus, s_arbre, 0);
558:
1.70 ! bertrand 559: //# ifdef EXPERIMENTAL_CODE
1.52 bertrand 560: simplification_arbre(s_etat_processus, s_arbre);
1.70 ! bertrand 561: affichage_arbre(s_etat_processus, s_arbre, 0);
1.51 bertrand 562:
563: if ((*s_etat_processus).erreur_systeme != d_es)
564: {
565: return(NULL);
566: }
1.70 ! bertrand 567: //# endif
1.50 bertrand 568:
569: /*
570: * Transcription de l'arbre q-aire simplifié en expression algébrique.
571: * Seule une fonction récursive permet de faire cette conversion
572: * simplement.
573: */
574:
575: l_liste_locale = transcription_arbre(s_etat_processus, s_arbre);
1.1 bertrand 576:
1.50 bertrand 577: if ((s_objet_simplifie = allocation(s_etat_processus, ALG))
578: == NULL)
579: {
580: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
581: return(NULL);
582: }
1.1 bertrand 583:
1.50 bertrand 584: // Ajout des délimiteurs '<<' et '>>' à la liste d'instructions
1.1 bertrand 585:
1.50 bertrand 586: if (((*s_objet_simplifie).objet = allocation_maillon(s_etat_processus))
587: == NULL)
1.1 bertrand 588: {
1.50 bertrand 589: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
590: return(NULL);
591: }
1.1 bertrand 592:
1.50 bertrand 593: l_element_courant = (*s_objet_simplifie).objet;
1.1 bertrand 594:
1.50 bertrand 595: if (((*l_element_courant).donnee = allocation(s_etat_processus,
596: FCT)) == NULL)
597: {
598: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
599: return(NULL);
1.1 bertrand 600: }
601:
1.50 bertrand 602: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
603: .nombre_arguments = 0;
604: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
605: .fonction = instruction_vers_niveau_superieur;
1.1 bertrand 606:
1.50 bertrand 607: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
608: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
609: {
610: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
611: return(NULL);
612: }
1.1 bertrand 613:
1.50 bertrand 614: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
615: .nom_fonction, "<<");
1.1 bertrand 616:
1.50 bertrand 617: (*l_element_courant).suivant = l_liste_locale;
1.1 bertrand 618:
1.50 bertrand 619: while((*l_element_courant).suivant != NULL)
1.1 bertrand 620: {
1.50 bertrand 621: l_element_courant = (*l_element_courant).suivant;
1.1 bertrand 622: }
623:
1.50 bertrand 624: if (((*l_element_courant).suivant =
625: allocation_maillon(s_etat_processus)) == NULL)
626: {
627: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
628: return(NULL);
629: }
1.1 bertrand 630:
1.50 bertrand 631: l_element_courant = (*l_element_courant).suivant;
632: (*l_element_courant).suivant = NULL;
1.1 bertrand 633:
1.50 bertrand 634: if (((*l_element_courant).donnee = allocation(s_etat_processus,
635: FCT)) == NULL)
636: {
637: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
638: return(NULL);
639: }
1.1 bertrand 640:
1.50 bertrand 641: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
642: .nombre_arguments = 0;
643: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
644: .fonction = instruction_vers_niveau_inferieur;
1.1 bertrand 645:
1.50 bertrand 646: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
647: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
1.1 bertrand 648: {
1.50 bertrand 649: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
650: return(NULL);
1.1 bertrand 651: }
1.50 bertrand 652:
653: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
654: .nom_fonction, ">>");
655: }
656: else
657: {
658: s_objet_simplifie = copie_objet(s_etat_processus, s_objet, 'P');
1.1 bertrand 659: }
660:
1.50 bertrand 661: return(s_objet_simplifie);
1.1 bertrand 662: }
663:
664: // vim: ts=4
CVSweb interface <joel.bertrand@systella.fr>