source/sol.c

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