include/piplib/piplib.h

   1 /******************************************************************************
   2  *                     PIP : Parametric Integer Programming                   *
   3  ******************************************************************************
   4  *                                 piplib.h                                   *
   5  ******************************************************************************
   6  *                                                                            *
   7  * Copyright Paul Feautrier, 1988-2005                                        *
   8  *                                                                            *
   9  * This is free software; you can redistribute it and/or modify it under the  *
  10  * terms of the GNU General Public License as published by the Free Software  *
  11  * Foundation; either version 2 of the License, or (at your option) any later *
  12  * 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 General Public License along    *
  20  * with software; if not, write to the Free Software Foundation, Inc.,        *
  21  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  22  *                                                                            *
  23  * Written by Cedric Bastoul                                                  *
  24  *                                                                            *
  25  ******************************************************************************/
  26
  27 /* Premiere version du 18 septembre 2002. */
  28
  29 #if !defined(LINEAR_VALUE_IS_LONGLONG) && !defined(LINEAR_VALUE_IS_INT)
  30 #if !defined(LINEAR_VALUE_IS_MP)
  31 # error Please define LINEAR_VALUE_IS_* or #include polylib32.h or polylib64.h
  32 #endif
  33 #endif
  34
  35 #if defined(LINEAR_VALUE_IS_LONGLONG)
  36
  37 # define Entier   long long
  38 # define FORMAT   "%lld"
  39 # define VAL_UN   1LL
  40 # define VAL_ZERO 0LL
  41
  42 #define VALUE_TO_INT(val) ((int)(val))
  43
  44 #elif defined(LINEAR_VALUE_IS_INT)
  45
  46 # define Entier   long int
  47 # define FORMAT   "%ld"
  48 # define VAL_UN   1L
  49 # define VAL_ZERO 0L
  50
  51 #define VALUE_TO_INT(val) ((int)(val))
  52
  53 #elif defined(LINEAR_VALUE_IS_MP)
  54
  55 # include <gmp.h>
  56 # define Entier   mpz_t
  57 # define FORMAT   "%d"
  58 # define GMP_INPUT_FORMAT   "%lZd"
  59
  60 #define VALUE_TO_INT(val) ((int)mpz_get_si(val))
  61
  62 #endif
  63
  64 #if defined(LINEAR_VALUE_IS_MP)
  65
  66 #define value_addto(ref,val1,val2)      (mpz_add((ref),(val1),(val2)))
  67 #define value_assign(v1,v2)             (mpz_set((v1),(v2)))
  68 #define value_clear(val)                (mpz_clear((val)))
  69 #define value_divexact(d,v1,v2)         (mpz_divexact((d),(v1),(v2)))
  70 #define value_gcd(g,v1,v2)              (mpz_gcd((g),(v1),(v2)))
  71 #define value_init(val)                 (mpz_init((val)))
  72 #define value_init_set(v1,v2)           (mpz_init_set((v1),(v2)))
  73 #define value_oppose(ref,val)           (mpz_neg((ref),(val)))
  74 #define value_set_si(val,i)             (mpz_set_si((val),(i)))
  75 #define value_subtract(ref,val1,val2)   (mpz_sub((ref),(val1),(val2)))
  76 #define value_eq(v1,v2)                 (mpz_cmp((v1),(v2)) == 0)
  77 #define value_ne(v1,v2)                 (mpz_cmp((v1),(v2)) != 0)
  78 #define value_notzero_p(val)            (mpz_sgn(val) != 0)
  79
  80 #else
  81
  82 #define value_addto(ref,val1,val2)      ((ref) = (val1)+(val2))
  83 #define value_assign(v1,v2)             ((v1) = (v2))
  84 #define value_clear(val)                ((val) = 0)
  85 #define value_divexact(d,v1,v2)         ((d) = (v1) / (v2))
  86 #define value_gcd(g,v1,v2)              ((g) = pgcd((v1),(v2)))
  87 #define value_init(val)                 ((val) = 0)
  88 #define value_init_set(v1,v2)           ((v1) = (v2))
  89 #define value_oppose(ref,val)           ((ref) = -(val))
  90 #define value_set_si(val,i)             ((val) = (Entier)(i))
  91 #define value_subtract(ref,val1,val2)   ((ref) = (val1)-(val2))
  92 #define value_eq(v1,v2)                 ((v1) == (v2))
  93 #define value_ne(v1,v2)                 ((v1) != (v2))
  94 #define value_notzero_p(val)            ((val) != 0)
  95
  96 #endif
  97
  98
  99 #ifndef PIPLIB_H
 100 #define PIPLIB_H
 101 #if defined(__cplusplus)
 102 extern "C"
 103   {
 104 #endif
 105
 106 #include <stdio.h> /* various function declarations use FILE */
 107 # include <piplib/type.h>
 108 # include <piplib/sol.h>
 109 # include <piplib/tab.h>
 110 # include <piplib/funcall.h>
 111
 112
 113 /* Structure PipMatrix :
 114  * Structure de matrice au format PolyLib. Le premier element d'une ligne
 115  * indique quand il vaut 1 que la ligne decrit une inequation de la forme
 116  * p(x)>=0 et quand il vaut 0, que la ligne decrit une egalite de la forme
 117  * p(x)=0. Le dernier element de chaque ligne correspond au coefficient
 118  * constant.
 119  */
 120 struct pipmatrix
 121 { unsigned NbRows, NbColumns ;
 122   Entier **p ;
 123   Entier *p_Init ;
 124   int p_Init_size;              /* Only for PolyLib compatibility under MP
 125                                  * version: PolyLib makes sometimes
 126                                  * overestimates on the size of the matrices,
 127                                  * in order to go faster. Thus
 128                                  * NbRows*NbColumns is not the number of
 129                                  * allocated elements. With MP version, we
 130                                  * have to think to mpz_clear() all the
 131                                  * initialized elements before freing, then
 132                                  * we need to know the number of allocated
 133                                  * elements: p_Init_size.
 134                                  */
 135 } ;
 136 typedef struct pipmatrix PipMatrix ;
 137
 138
 139 /* Structure PipVector :
 140  * Cette structure contient un Vector de 'nb_elements' la ieme composante de
 141  * ce vecteur vaut the_vector[i]/the_deno[i].
 142  */
 143 struct pipvector
 144 { int nb_elements ;             /* Nombre d'elements du vecteur. */
 145   Entier * the_vector ;         /* Numerateurs du vecteur. */
 146   Entier * the_deno ;           /* Denominateurs du vecteur. */
 147 } ;
 148 typedef struct pipvector PipVector ;
 149
 150
 151 /* Structure PipNewparm :
 152  * Liste chainee de Newparm, les informations d'un newparm etant son rang, un
 153  * vecteur de coefficients et un denominateur. Le newparm est egal a la division
 154  * du vecteur par le denominateur.
 155  */
 156 struct pipnewparm
 157 { int rank ;                    /* Rang du 'newparm'. */
 158   PipVector * vector ;          /* Le vector decrivant le newparm. */
 159   Entier deno ;                 /* Denominateur du 'newparm'. */
 160   struct pipnewparm * next ;    /* Pointeur vers le newparm suivant. */
 161 } ;
 162 typedef struct pipnewparm PipNewparm ;
 163
 164
 165 /* Structure PipList :
 166  * Liste chainee de Vector.
 167  */
 168 struct piplist
 169 { PipVector * vector ;          /* Le vector contenant la partie de solution. */
 170   struct piplist * next ;       /* Pointeur vers l'element suivant. */
 171 } ;
 172 typedef struct piplist PipList ;
 173
 174
 175 /* Structure pipquast :
 176  * Arbre binaire. Conformement a la grammaire de sortie (voir mode d'emploi), un
 177  * noeud de l'arbre des solutions debute par une liste de 'newparm'. Il continue
 178  * ensuite soit par une 'list' (alors condition vaut null), soit par un 'if'
 179  * (alors le champ condition contient la condition).
 180  */
 181 struct pipquast
 182 { PipNewparm * newparm ;        /* Les 'newparm'. */
 183   PipList * list ;              /* La 'list' si pas de 'if'. */
 184   PipVector * condition ;       /* La condition si 'if'. */
 185   struct pipquast * next_then ; /* Noeud si condition et si verifiee. */
 186   struct pipquast * next_else ; /* Noeud si condition et si non verifiee. */
 187   struct pipquast * father ;    /* Pointeur vers le quast pere. */
 188 } ;
 189 typedef struct pipquast PipQuast ;
 190
 191
 192 /* Structure pipoptions:
 193  * This structure contains each option that can be set to change the PIP
 194  * behaviour.
 195  */
 196 struct pipoptions
 197 { int Nq ;                      /* 1 if an integer solution is needed,
 198                                  * 0 otherwise.
 199                                  */
 200   int Verbose ;                 /* -1 -> absolute silence,
 201                                  *  0 -> relative silence,
 202                                  *  1 -> information on cuts when an integer
 203                                  *       solution is needed,
 204                                  *  2 -> information sur les pivots et les
 205                                  *       déterminants,
 206                                  *  3 -> information on arrays,
 207                                  * Each option include the preceding.
 208                                  */
 209   int Simplify ;                /* Set to 1 to eliminate some trivial
 210                                  * solutions, 0 otherwise.
 211                                  */
 212   int Deepest_cut ;             /* Set to 1 to include deepest cut
 213                                  * algorithm.
 214                                  */
 215   int Maximize;                 /* Set to 1 if maximum is needed. */
 216   int Urs_parms;                /* -1 -> all parameters may be negative
 217                                  *  0 -> all parameters are non-negative
 218                                  */
 219   int Urs_unknowns;             /* -1 -> all unknowns may be negative
 220                                  *  0 -> all unknowns are non-negative
 221                                  */
 222 } ;
 223 typedef struct pipoptions PipOptions ;
 224
 225
 226 /* Prototypes des fonctions d'affichages des structures de la PipLib. */
 227 void pip_matrix_print(FILE *, PipMatrix *) ;
 228 void pip_vector_print(FILE *, PipVector *) ;
 229 void pip_newparm_print(FILE * foo, PipNewparm *, int indent) ;
 230 void pip_list_print(FILE * foo, PipList *, int indent) ;
 231 void pip_quast_print(FILE *, PipQuast *, int) ;
 232
 233
 234 /* Prototypes des fonctions de liberation memoire des structures de la PipLib.*/
 235 void pip_matrix_free(PipMatrix *) ;
 236 void pip_vector_free(PipVector *) ;
 237 void pip_newparm_free(PipNewparm *) ;
 238 void pip_list_free(PipList *) ;
 239 void pip_quast_free(PipQuast *) ;
 240 void pip_options_free(PipOptions *) ;
 241
 242
 243 /* Prototypes des fonctions d'acquisition de matrices de contraintes et
 244  * options.
 245  */
 246 PipMatrix * pip_matrix_alloc(unsigned, unsigned) ;
 247 PipMatrix * pip_matrix_read(FILE *) ;
 248 PipOptions * pip_options_init(void) ;
 249
 250
 251 /* initialization of pip library */
 252 void pip_init();
 253 void pip_close();
 254
 255
 256 /* Prototype de la fonction de resolution :
 257  * pip_solve resoud le probleme qu'on lui passe en parametre, suivant les
 258  * options elles aussi en parametre. Elle renvoie la solution sous forme
 259  * d'un arbre de PipQuast. Parametres :
 260  * - probleme :
 261  * 1 PipMatrix  : systeme des inequations definissant le domaine des inconnues,
 262  * 2 PipMatrix  : systeme des inequations satisfaites par les parametres,
 263  * 3 int        : column rank of the bignum, or negative value if there
 264  *                is no big parameter.
 265  * 4 PipOptions : options for PIP.
 266  */
 267 PipQuast * pip_solve(PipMatrix *, PipMatrix *, int, PipOptions *) ;
 268
 269 /* Ced : ajouts specifiques a la PipLib pour funcall. */
 270 Tableau * tab_Matrix2Tableau(PipMatrix *, int, int, int, int, int, int);
 271 Tableau * tab_Matrix2TableauMax(PipMatrix *, int, int, int, int) ;
 272 #define SOL_SHIFT               (1 << 0)    /* Shift solution over -bigparam */
 273 #define SOL_NEGATE              (1 << 1)    /* Negate solution */
 274 #define SOL_REMOVE              (1 << 2)    /* Remove big parameter */
 275 #define SOL_MAX                 (SOL_SHIFT | SOL_NEGATE)
 276                                             /* Maximum was computed */
 277 PipQuast *sol_quast_edit(int *i, PipQuast *father, int Bg, int Urs_p, int flags);
 278
 279 #if defined(__cplusplus)
 280   }
 281 #endif
 282 #endif /* define PIPLIB_H */