source/sol.c

   1 /******************************************************************************
   2  *                     PIP : Parametric Integer Programming                   *
   3  ******************************************************************************
   4  *                                   sol.h                                    *
   5  ******************************************************************************
   6  *                                                                            *
   7  * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002                     *
   8  *                                                                            *
   9  * This library is free software; you can redistribute it and/or modify it    *
  10  * under the terms of the GNU Lesser General Public License as published by   *
  11  * the Free Software Foundation; either version 2.1 of the License, or (at    *
  12  * your option) any later version.                                            *
  13  *                                                                            *
  14  * This software is distributed in the hope that it will be useful, but       *
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  17  * for more details.                                                          *
  18  *                                                                            *
  19  * You should have received a copy of the GNU Lesser General Public License   *
  20  * along with this library; if not, write to the Free Software Foundation,    *
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA         *
  22  *                                                                            *
  23  * Written by Paul Feautrier and Cedric Bastoul                               *
  24  *                                                                            *
  25  ******************************************************************************/
  26
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29 #include <string.h>
  30
  31 #include "pip.h"
  32
  33 extern long int cross_product, limit;
  34 extern int verbose;
  35 extern FILE *dump;
  36
  37 struct S
  38     {int flags;
  39      Entier param1, param2;
  40     };
  41
  42 #define Free 0
  43 #define Nil  1
  44 #define If   2
  45 #define List 3
  46 #define Form 4
  47 #define New  5
  48 #define Div  6
  49 #define Val  7
  50 #define Error 8
  51
  52 struct S * sol_space;
  53 static int sol_free;
  54
  55 #if !defined(LINEAR_VALUE_IS_MP)
  56 Entier mod(Entier, Entier);
  57
  58 Entier pgcd(Entier x, Entier y)
  59 {Entier r;
  60  while(y)
  61      {r = mod(x, y);
  62       x = y;
  63       y = r;
  64      }
  65  return(x>= 0? x : -x);
  66 }
  67 #endif
  68
  69 void sol_init(void)
  70 {
  71  sol_free = 0;
  72  sol_space = (struct S *)malloc(SOL_SIZE*sizeof(struct S)) ;
  73 }
  74
  75 void sol_close(void)
  76 {
  77  free(sol_space) ;
  78 }
  79
  80 int sol_hwm()
  81 {
  82  return(sol_free);
  83 }
  84
  85 void sol_reset(p)
  86 int p;
  87 {int i;
  88  if(p<0 || p>=SOL_SIZE)
  89      {fprintf(stderr, "Syserr : sol_reset : Memory allocation error\n");
  90       exit(40);
  91      }
  92  #if defined(LINEAR_VALUE_IS_MP)
  93  for(i=p; i<sol_free; i++){
  94    mpz_clear(sol_space[i].param1);
  95    mpz_clear(sol_space[i].param2);
  96  }
  97  #endif
  98  sol_free = p;
  99 }
 100
 101 struct S *sol_alloc(void)
 102 {struct S *r;
 103  r = sol_space + sol_free;
 104  r->flags = Free;
 105  #if defined(LINEAR_VALUE_IS_MP)
 106  mpz_init_set_si(r->param1,0);
 107  mpz_init_set_si(r->param2,0);
 108  #else
 109  r->param1 = r->param2 = 0;
 110  #endif
 111  sol_free++;
 112  if(sol_free >= SOL_SIZE)
 113      {fprintf(stderr, "The solution is too complex! : sol\n");
 114       exit(26);
 115      }
 116      return(r);
 117 }
 118
 119 void sol_nil(void)
 120 {
 121  struct S * r;
 122  r = sol_alloc();
 123  r -> flags = Nil;
 124  if(verbose > 0)
 125    {fprintf(dump, "\nNil");
 126     fflush(dump);
 127   }
 128 }
 129
 130 void sol_error(int c)
 131 {
 132  struct S *r;
 133  r = sol_alloc();
 134  r->flags = Nil;
 135  #if defined(LINEAR_VALUE_IS_MP)
 136  mpz_set_si(r->param1, c);
 137  #else
 138  r->param1 = c;
 139  #endif
 140  if(verbose > 0) {
 141      fprintf(dump, "Erreur %d\n", c);
 142      fflush(dump);
 143      }
 144 }
 145
 146 int is_not_Nil(p)
 147 int p;
 148 {
 149  return(sol_space[p].flags != Nil);
 150 }
 151
 152 void sol_if(void)
 153 {
 154  struct S *r;
 155  r = sol_alloc();
 156  r -> flags = If;
 157  if(verbose > 0) {
 158      fprintf(dump, "\nIf ");
 159      fflush(dump);
 160    }
 161 }
 162
 163 void sol_list(n)
 164 int n;
 165 {struct S * r;
 166  r = sol_alloc();
 167  r->flags = List;
 168  #if defined(LINEAR_VALUE_IS_MP)
 169  mpz_set_si(r->param1, n);
 170  #else
 171  r->param1 = n;
 172  #endif
 173  if(verbose > 0) {
 174      fprintf(dump, "\nList %d ", n);
 175      fflush(dump);
 176 }
 177 }
 178
 179 void sol_forme(l)
 180 int l;
 181 {
 182  struct S *r;
 183  r = sol_alloc();
 184  r -> flags = Form;
 185  #if defined(LINEAR_VALUE_IS_MP)
 186  mpz_set_ui(r -> param1, l);
 187  #else
 188  r -> param1 = l;
 189  #endif
 190  if(verbose > 0) {
 191      fprintf(dump, "\nForme %d ", l);
 192      fflush(dump);
 193    }
 194 }
 195
 196 void sol_new(k)
 197 int k;
 198 {
 199  struct S *r;
 200  r = sol_alloc();
 201  r -> flags = New;
 202  #if defined(LINEAR_VALUE_IS_MP)
 203  mpz_set_ui(r -> param1, k);
 204  #else
 205  r -> param1 = k;
 206  #endif
 207  if(verbose > 0) {
 208      fprintf(dump, "New %d ", k);
 209      fflush(dump);
 210    }
 211 }
 212
 213 void sol_div()
 214 {
 215  struct S *r;
 216  r = sol_alloc();
 217  r -> flags = Div;
 218  if(verbose > 0) {
 219      fprintf(dump, "Div ");
 220      fflush(dump);
 221    }
 222 }
 223
 224 void sol_val(n, d)
 225 Entier n, d;
 226 {
 227  struct S *r;
 228  r = sol_alloc();
 229  r -> flags = Val;
 230  #if defined(LINEAR_VALUE_IS_MP)
 231  mpz_set(r -> param1, n);
 232  mpz_set(r -> param2, d);
 233  #else
 234  r -> param1 = n;
 235  r -> param2 = d;
 236  #endif
 237  if(verbose > 0) {
 238    fprintf(dump, "val(");
 239    #if defined(LINEAR_VALUE_IS_MP)
 240    mpz_out_str(dump, 10, n);
 241    fprintf(dump, "/");
 242    mpz_out_str(dump, 10, d);
 243    #else
 244    fprintf(dump, FORMAT, n);
 245    fprintf(dump, "/");
 246    fprintf(dump, FORMAT, d);
 247    #endif
 248    fprintf(dump, ") ");
 249    fflush(dump);
 250   }
 251 }
 252
 253 int skip(int);
 254
 255 /* a` partir d'un point de la solution, sauter un objet
 256 bien forme' ainsi qu'un e'ventuel New et pointer sur l'objet
 257 suivant */
 258
 259 int skip_New (int i)
 260 {
 261  if(sol_space[i].flags != New) return i;
 262  i = skip(i+1);      /* sauter le Div */
 263  return i;
 264 }
 265 /* au lancement, i indexe une cellule qui est la te^te d'un objet.
 266    la valeur retourne'e est la te^te de l'objet qui suit. Les
 267    objets de type New sont e'limine's                                */
 268
 269 int skip (int i)
 270 {int n, f;
 271  while((f = sol_space[i].flags) == Free || f == Error) i++;
 272  switch (sol_space[i].flags) {
 273  case Nil : case Val : i++; break;
 274  case New : i = skip_New(i); break;
 275  case If : i = skip(i+1);        /* sauter le pre'dicat */
 276            i = skip(i);          /* sauter le vrai */
 277            i = skip(i); break;   /* sauter le faux */
 278  case List : case Form :
 279            #if defined(LINEAR_VALUE_IS_MP)
 280            n = mpz_get_si(sol_space[i].param1);
 281            #else
 282            n = sol_space[i].param1;
 283            #endif
 284            i++;
 285            while(n--) i = skip(i);
 286            break;
 287  case Div : i = skip(i+1);       /* sauter la forme */
 288             i = skip(i);         /* sauter le diviseur */
 289             break;
 290  default : fprintf(stderr,
 291               "Syserr : skip : unknown %d\n", sol_space[i].flags);
 292  }
 293  return skip_New(i);
 294 }
 295 /* simplification de la solution : e'limination des constructions
 296    (if p () ()). N'est en service qu'en pre'sence de l'option -z */
 297
 298 void sol_simplify(int i)
 299 {int j, k, l;
 300  if(sol_space[i].flags == If) {
 301      j = skip(i+1);        /* j : debut de la partie vraie */
 302      k = skip(j);          /* k : debut de la partie fausse */
 303      sol_simplify(k);
 304      sol_simplify(j);
 305      if(sol_space[j].flags == Nil && sol_space[k].flags == Nil) {
 306          sol_space[i].flags = Nil;
 307          if (k >= sol_free - 1)
 308             sol_reset(i+1);
 309          else for(l = i+1; l<=k; l++) sol_space[l].flags = Free;
 310        }
 311    }
 312
 313 }
 314 /* e'dition de la solution */
 315
 316 int sol_edit(FILE *foo, int i)
 317 {int j, n;
 318  struct S *p;
 319  Entier N, D, d;
 320  #if defined(LINEAR_VALUE_IS_MP)
 321  mpz_init(N);
 322  mpz_init(D);
 323  mpz_init(d);
 324  #endif
 325
 326  p = sol_space + i;
 327  for(;;) {
 328    if(p->flags == Free) {
 329      p++;
 330      i++;
 331      continue;
 332    }
 333    if(p->flags == New) {
 334      #if defined(LINEAR_VALUE_IS_MP)
 335      n = mpz_get_si(p->param1);
 336      #else
 337      n = p->param1;
 338      #endif
 339      fprintf(foo, "(newparm %d ", n);
 340      if(verbose>0)fprintf(dump, "(newparm %d ", n);
 341      i = sol_edit(foo, ++i);
 342      p = sol_space +i;
 343      fprintf(foo, ")\n");
 344      if(verbose>0)fprintf(dump, ")\n");
 345      continue;
 346    }
 347    break;
 348  }
 349  switch(p->flags){
 350  case Nil : fprintf(foo, "()\n");
 351    if(verbose>0)fprintf(dump, "()\n");
 352    i++; break;
 353  case Error :
 354    #if defined(LINEAR_VALUE_IS_MP)
 355    fprintf(foo, "Error %d\n", mpz_get_si(p->param1));
 356    if(verbose>0)
 357    fprintf(dump, "Error %d\n", mpz_get_si(p->param1));
 358    #else
 359    fprintf(foo, "Error %d\n", p->param1);
 360    if(verbose>0)
 361    fprintf(dump, "Error %d\n", p->param1);
 362    #endif
 363    i++; break;
 364  case If  : fprintf(foo, "(if ");
 365    if(verbose>0)fprintf(dump, "(if ");
 366    i = sol_edit(foo, ++i);
 367    i = sol_edit(foo, i);
 368    i = sol_edit(foo, i);
 369    fprintf(foo, ")\n");
 370    if(verbose>0)fprintf(dump, ")\n");
 371    break;
 372  case List: fprintf(foo, "(list ");
 373    if(verbose>0)fprintf(dump, "(list ");
 374    #if defined(LINEAR_VALUE_IS_MP)
 375    n = mpz_get_si(p->param1);
 376    #else
 377    n = p->param1;
 378    #endif
 379    i++;
 380    while(n--) i = sol_edit(foo, i);
 381    fprintf(foo, ")\n");
 382    if(verbose>0)fprintf(dump, ")\n");
 383    break;
 384  case Form: fprintf(foo, "#[");
 385    if(verbose>0)fprintf(dump, "#[");
 386    #if defined(LINEAR_VALUE_IS_MP)
 387    n = mpz_get_si(p->param1);
 388    #else
 389    n = p->param1;
 390    #endif
 391    for(j = 0; j<n; j++){
 392      i++; p++;
 393      #if defined(LINEAR_VALUE_IS_MP)
 394      mpz_set(N, p->param1); mpz_set(D, p->param2);
 395      mpz_gcd(d, N, D);
 396      if(mpz_cmp(d, D) == 0){
 397        putc(' ', foo);
 398        mpz_divexact(N, N, d);
 399        mpz_out_str(foo, 10, N);
 400        if(verbose>0){
 401          putc(' ', dump);
 402          mpz_out_str(dump, 10, N);
 403        }
 404      }
 405      else{
 406        mpz_divexact(N, N, d);
 407        mpz_divexact(D, D, d);
 408        putc(' ', foo);
 409        mpz_out_str(foo, 10, N);
 410        putc('/', foo);
 411        mpz_out_str(foo, 10, D);
 412        if(verbose>0){
 413          putc(' ', dump);
 414          mpz_out_str(dump, 10, N);
 415          putc('/', dump);
 416          mpz_out_str(dump, 10, D);
 417        }
 418      }
 419      #else
 420      N = p->param1; D = p->param2;
 421      d = pgcd(N, D);
 422      if(d == D){
 423        putc(' ', foo);
 424        fprintf(foo, FORMAT, N/d);
 425        if(verbose>0){
 426          putc(' ', dump);
 427          fprintf(dump, FORMAT, N/d);
 428        }
 429      }
 430      else{
 431        putc(' ', foo);
 432        fprintf(foo,FORMAT,N/d);
 433        fprintf(foo,"/");
 434        fprintf(foo,FORMAT, D/d);
 435        if(verbose>0){
 436          putc(' ', dump);
 437          fprintf(dump,FORMAT,N/d);
 438          fprintf(dump,"/");
 439          fprintf(dump,FORMAT, D/d);
 440        }
 441      }
 442      #endif
 443    }
 444    fprintf(foo, "]\n");
 445    if(verbose>0)fprintf(dump, "]\n");
 446    i++;
 447    break;
 448  case Div : fprintf(foo, "(div ");
 449    if(verbose>0)fprintf(dump, "(div ");
 450    i = sol_edit(foo, ++i);
 451    i = sol_edit(foo, i);
 452    fprintf(foo, ")\n");
 453    if(verbose>0)fprintf(dump, ")\n");
 454    break;
 455  case Val :
 456    #if defined(LINEAR_VALUE_IS_MP)
 457    mpz_set(N, p->param1); mpz_set(D, p->param2);
 458    mpz_gcd(d, N, D);
 459    if(mpz_cmp(d, D) == 0){
 460      mpz_divexact(N, N, d);
 461      putc(' ', foo);
 462      mpz_out_str(foo, 10, N);
 463      if(verbose>0){
 464        putc(' ', dump);
 465        mpz_out_str(dump, 10, N);
 466      }
 467    }
 468    else{
 469      mpz_divexact(N, N, d);
 470      mpz_divexact(D, D, d);
 471      putc(' ', foo);
 472      mpz_out_str(foo, 10, N);
 473      fprintf(foo, "/");
 474      mpz_out_str(foo, 10, D);
 475      if(verbose>0){
 476        putc(' ', dump);
 477        mpz_out_str(dump, 10, N);
 478        fprintf(dump, "/");
 479        mpz_out_str(dump, 10, D);
 480      }
 481    }
 482    #else
 483    N = p->param1; D = p->param2;
 484    d = pgcd(N, D);
 485    if(d == D){putc(' ', foo);
 486    fprintf(foo, FORMAT, N/d);
 487    if(verbose>0)
 488      {putc(' ', dump);
 489      fprintf(dump, FORMAT, N/d);
 490      }
 491    }
 492    else{putc(' ', foo);
 493    fprintf(foo, FORMAT, N/d);
 494    fprintf(foo, "/");
 495    fprintf(foo, FORMAT, D/d);
 496    if(verbose>0)
 497      {putc(' ', dump);
 498      fprintf(dump, FORMAT, N/d);
 499      fprintf(dump, "/");
 500      fprintf(dump, FORMAT, D/d);
 501      }
 502    }
 503    #endif
 504    i++;
 505    break;
 506  default  : fprintf(foo, "Inconnu : sol\n");
 507    if(verbose>0)fprintf(dump, "Inconnu : sol\n");
 508  }
 509  #if defined(LINEAR_VALUE_IS_MP)
 510  mpz_clear(d);
 511  mpz_clear(D);
 512  mpz_clear(N);
 513  #endif
 514  return(i);
 515 }
 516
 517
 518 /* Fonction sol_vector_edit :
 519  * Cette fonction a pour but de placer les informations correspondant
 520  * a un Vector dans la grammaire dans une structure de type PipVector. Elle
 521  * prend en parametre un pointeur vers une case memoire contenant le
 522  * numero de cellule du tableau sol_space a partir de laquelle on doit
 523  * commencer la lecture des informations. Elle retourne un pointeur vers
 524  * une structure de type PipVector contenant les informations de ce Vector.
 525  * Premiere version : Ced. 20 juillet 2001.
 526  */
 527 PipVector * sol_vector_edit(int *i, int Bg, int Urs_p, int flags)
 528 { int j, k, n, unbounded  = 0, first_urs;
 529   struct S *p ;
 530   Entier N, D, d ;
 531   PipVector * vector ;
 532
 533   entier_init(N);
 534   entier_init(D);
 535   entier_init(d);
 536
 537   vector = (PipVector *)malloc(sizeof(PipVector)) ;
 538   if (vector == NULL)
 539   { fprintf(stderr, "Memory Overflow.\n") ;
 540     exit(1) ;
 541   }
 542   p = sol_space + (*i) ;
 543   n = VALUE_TO_INT(p->param1);
 544   if (flags & SOL_REMOVE)
 545     --n;
 546   n -= Urs_p;
 547   first_urs = Urs_p + (Bg >= 0);
 548   vector->nb_elements = n ;
 549   vector->the_vector = (Entier *)malloc(sizeof(Entier)*n) ;
 550   if (vector->the_vector == NULL)
 551   { fprintf(stderr, "Memory Overflow.\n") ;
 552     exit(1) ;
 553   }
 554   vector->the_deno = (Entier *)malloc(sizeof(Entier)*n) ;
 555   if (vector->the_deno == NULL)
 556   { fprintf(stderr, "Memory Overflow.\n") ;
 557     exit(1) ;
 558   }
 559
 560   for (j=0, k=0; k < n; j++) {
 561     (*i)++ ;
 562     p++ ;
 563
 564     entier_assign(N, p->param1);
 565     entier_assign(D, p->param2);
 566     entier_gcd(d, N, D);
 567
 568     if ((flags & SOL_SHIFT) && j == Bg) {
 569       entier_subtract(N, N, D);   /* subtract 1 */
 570       if (entier_notzero_p(N))
 571         unbounded = 1;
 572     }
 573
 574     if ((flags & SOL_REMOVE) && j == Bg)
 575       continue;
 576
 577     if (first_urs <= j && j < first_urs+Urs_p)
 578       continue;
 579
 580     entier_init(vector->the_vector[k]);
 581     entier_divexact(vector->the_vector[k], N, d);
 582     if (flags & SOL_NEGATE)
 583       entier_oppose(vector->the_vector[k], vector->the_vector[k]);
 584     entier_init(vector->the_deno[k]);
 585     if (entier_eq(d, D))
 586       entier_assign(vector->the_deno[k], UN);
 587     else
 588       entier_divexact(vector->the_deno[k], D, d);
 589     ++k;
 590   }
 591   if (unbounded)
 592     for (k=0; k < n; k++)
 593       entier_assign(vector->the_deno[k], ZERO);
 594   (*i)++ ;
 595
 596   entier_clear(d);
 597   entier_clear(D);
 598   entier_clear(N);
 599
 600   return(vector) ;
 601 }
 602
 603
 604 /* Fonction sol_newparm_edit :
 605  * Cette fonction a pour but de placer les informations correspondant
 606  * a un Newparm dans la grammaire dans une structure de type PipNewparm. Elle
 607  * prend en parametre un pointeur vers une case memoire contenant le
 608  * numero de cellule du tableau sol_space a partir de laquelle on doit
 609  * commencer la lecture des informations. Elle retourne un pointeur vers
 610  * une structure de type PipNewparm contenant les informations de ce Newparm.
 611  * Premiere version : Ced. 18 octobre 2001.
 612  */
 613 PipNewparm * sol_newparm_edit(int *i, int Bg, int Urs_p, int flags)
 614 { struct S * p ;
 615   PipNewparm * newparm, * newparm_first = NULL, * newparm_now = NULL;
 616
 617   /* On place p au lieu de lecture. */
 618   p = sol_space + (*i) ;
 619
 620   do {
 621     /* On passe le New et le Div pour aller a Form et lire le VECTOR. */
 622     (*i) += 2 ;
 623
 624     newparm = (PipNewparm *)malloc(sizeof(PipNewparm)) ;
 625     if (newparm == NULL)
 626     { fprintf(stderr, "Memory Overflow.\n") ;
 627       exit(1) ;
 628     }
 629     newparm->vector = sol_vector_edit(i, Bg, Urs_p, flags);
 630     newparm->rank = VALUE_TO_INT(p->param1);
 631     /* On met p a jour pour lire le denominateur (un Val de param2 UN). */
 632     p = sol_space + (*i) ;
 633     entier_init_set(newparm->deno, p->param1);
 634     if (flags & SOL_REMOVE)
 635       newparm->rank--;
 636     newparm->rank -= Urs_p;
 637     newparm->next = NULL ;
 638
 639     if (newparm_now)
 640       newparm_now->next = newparm;
 641     else
 642       newparm_first = newparm;
 643     newparm_now = newparm ;
 644     if (verbose > 0)
 645     { fprintf(dump,"\n(newparm ") ;
 646       fprintf(dump,FORMAT,newparm->rank) ;
 647       fprintf(dump," (div ") ;
 648       pip_vector_print(dump,newparm->vector) ;
 649       fprintf(dump," ") ;
 650       #if defined(LINEAR_VALUE_IS_MP)
 651       mpz_out_str(dump,10,newparm->deno) ;
 652       #else
 653       fprintf(dump,FORMAT,newparm->deno) ;
 654       #endif
 655       fprintf(dump,"))") ;
 656     }
 657
 658     /* On passe aux elements suivants. */
 659     (*i) ++ ;
 660     p = sol_space + (*i) ;
 661   } while (p->flags == New);
 662
 663   return newparm_first;
 664 }
 665
 666
 667 /* Fonction sol_list_edit :
 668  * Cette fonction a pour but de placer les informations correspondant
 669  * a une List dans la grammaire dans une structure de type PipList. Elle
 670  * prend en parametre un pointeur vers une case memoire contenant le
 671  * numero de cellule du tableau sol_space a partir de laquelle on doit
 672  * commencer la lecture des informations. Elle retourne un pointeur vers
 673  * une structure de type PipList contenant les informations de cette List.
 674  * Premiere version : Ced. 18 octobre 2001.
 675  * 16 novembre 2005 : Ced. Prise en compte du cas 0 éléments, avant impossible.
 676  */
 677 PipList * sol_list_edit(int *i, int nb_elements, int Bg, int Urs_p, int flags)
 678 { PipList * list, * list_new, * list_now ;
 679
 680   /* Pour le premier element. */
 681   list = (PipList *)malloc(sizeof(PipList)) ;
 682   if (list == NULL)
 683   { fprintf(stderr, "Memory Overflow.\n") ;
 684     exit(1) ;
 685   }
 686   list->next = NULL ;
 687
 688   if (nb_elements == 0)
 689   { list->vector = NULL ;
 690     return(list) ;
 691   }
 692
 693   list->vector = sol_vector_edit(i, Bg, Urs_p, flags);
 694
 695   list_now = list ;
 696   if (verbose > 0)
 697   { fprintf(dump,"\n(list ") ;
 698     pip_vector_print(dump,list->vector) ;
 699   }
 700   nb_elements-- ;
 701
 702   /* Pour les elements suivants. */
 703   while (nb_elements--)
 704   { list_new = (PipList *)malloc(sizeof(PipList)) ;
 705     if (list_new == NULL)
 706     { fprintf(stderr, "Memory Overflow.\n") ;
 707       exit(1) ;
 708     }
 709     list_new->vector = sol_vector_edit(i, Bg, Urs_p, flags);
 710     list_new->next = NULL ;
 711
 712     if (verbose > 0)
 713     { fprintf(dump,"\n") ;
 714       pip_vector_print(dump,list_new->vector) ;
 715     }
 716     list_now->next = list_new ;
 717     list_now = list_now->next ;
 718   }
 719   if (verbose > 0)
 720   fprintf(dump,"\n)") ;
 721
 722   return(list) ;
 723 }
 724
 725
 726 /* Fonction sol_quast_edit :
 727  * Cette fonction a pour but de placer les informations de la solution
 728  * (qui sont contenues dans le tableau sol_space) dans une structure de
 729  * type PipQuast en vue d'une utilisation directe de la solution par une
 730  * application exterieure. Elle prend en parametre un pointeur vers une
 731  * case memoire contenant le numero de cellule du tableau sol_space
 732  * a partir de laquelle on doit commencer la lecture des informations. Elle
 733  * recoit aussi l'adresse du PipQuast qui l'a appelle (pour le champ father).
 734  * Elle retourne un pointeur vers une structure de type PipQuast qui
 735  * contient toutes les informations sur la solution (sous forme d'arbre).
 736  * Remarques : cette fonction lit les informations comme elles doivent
 737  * se presenter a la fin du traitement. Elle respecte scrupuleusement
 738  * la grammaire attendue et n'accepte de passer des cellules a Free
 739  * qu'entre une des trois grandes formes (if, list ou suite de newparm).
 740  * 20  juillet 2001 : Premiere version, Ced.
 741  * 31  juillet 2001 : Ajout du traitement de l'option verbose = code*2 :0(
 742  * 18  octobre 2001 : Grands changements dus a l'eclatement de la structure
 743  *                    PipVector en PipVector, PipNewparm et PipList, et
 744  *                    eclatement de la fonction avec sol_newparm_edit et
 745  *                    sol_list_edit.
 746  * 16 novembre 2005 : (debug) Même si une liste est vide il faut la créer pour
 747  *                    afficher plus tard le (list), repéré par Sven Verdoolaege.
 748  */
 749 PipQuast *sol_quast_edit(int *i, PipQuast *father, int Bg, int Urs_p, int flags)
 750 { int nb_elements ;
 751   struct S * p ;
 752   PipQuast * solution ;
 753   PipList * list_new, * list_now ;
 754   PipNewparm * newparm_new, * newparm_now ;
 755
 756   /* On place p au lieu de lecture. */
 757   p = sol_space + (*i) ;
 758   /* En cas d'utilisation de l'option de simplification, une plage de
 759    * structures S peut avoir les flags a Free. On doit alors les passer.
 760    */
 761   while (p->flags == Free)
 762   { p ++ ;
 763     (*i) ++ ;
 764   }
 765
 766   solution = (PipQuast *)malloc(sizeof(PipQuast)) ;
 767   if (solution == NULL)
 768   { fprintf(stderr, "Memory Overflow.\n") ;
 769     exit(1) ;
 770   }
 771   solution->newparm = NULL ;
 772   solution->list = NULL ;
 773   solution->condition = NULL ;
 774   solution->next_then = NULL ;
 775   solution->next_else = NULL ;
 776   solution->father = father ;
 777
 778   /* On peut commencer par une chaine de nouveaux parametres... */
 779   if (p->flags == New)
 780   { solution->newparm = sol_newparm_edit(i, Bg, Urs_p, flags & SOL_REMOVE);
 781     p = sol_space + (*i) ;
 782   }
 783
 784   /* ...ensuite soit par une liste (vide ou non) soit par un if. */
 785   (*i)++ ; /* Factorise de List, Nil et If. */
 786   switch (p->flags)
 787   { case List :
 788                 #if defined(LINEAR_VALUE_IS_MP)
 789                 nb_elements = mpz_get_si(p->param1) ;
 790                 #else
 791                 nb_elements = p->param1 ;
 792                 #endif
 793                 solution->list = sol_list_edit(i, nb_elements, Bg, Urs_p, flags);
 794                 if (flags & SOL_DUAL)
 795                     solution->next_then = sol_quast_edit(i, solution, Bg, Urs_p, 0);
 796                 break ;
 797     case Nil  : if (verbose > 0)
 798                 fprintf(dump,"\n()") ;
 799                 break ;
 800     case If   : solution->condition =
 801                             sol_vector_edit(i, Bg, Urs_p, flags & SOL_REMOVE);
 802                 if (verbose > 0)
 803                 { fprintf(dump,"\n(if ") ;
 804                   pip_vector_print(dump,solution->condition) ;
 805                 }
 806                 solution->next_then = sol_quast_edit(i, solution, Bg, Urs_p, flags);
 807                 solution->next_else = sol_quast_edit(i, solution, Bg, Urs_p, flags);
 808                 if (verbose > 0)
 809                 fprintf(dump,"\n)") ;
 810                 break ;
 811     default   : fprintf(stderr,"\nAie !!! Flag %d inattendu.\n",p->flags) ;
 812                 if (verbose > 0)
 813                 fprintf(dump,"\nAie !!! Flag %d inattendu.\n",p->flags) ;
 814                 exit(1) ;
 815   }
 816
 817   return(solution) ;
 818 }