polysign_polylib.c

   1 #include <barvinok/util.h>
   2 #include <barvinok/options.h>
   3 #include "polysign.h"
   4
   5 static enum order_sign interval_minmax(Polyhedron *I)
   6 {
   7     int i;
   8     int min = 1;
   9     int max = -1;
  10     assert(I->Dimension == 1);
  11     POL_ENSURE_VERTICES(I);
  12     for (i = 0; i < I->NbRays; ++i) {
  13         if (value_pos_p(I->Ray[i][1]))
  14             max = 1;
  15         else if (value_neg_p(I->Ray[i][1]))
  16             min = -1;
  17         else {
  18             if (max < 0)
  19                 max = 0;
  20             if (min > 0)
  21                 min = 0;
  22         }
  23     }
  24     if (min > 0)
  25         return order_gt;
  26     if (max < 0)
  27         return order_lt;
  28     if (min == max)
  29         return order_eq;
  30     if (max == 0)
  31         return order_le;
  32     if (min == 0)
  33         return order_ge;
  34     return order_unknown;
  35 }
  36
  37 /* Returns the sign of the affine function specified by T on the polyhedron D */
  38 enum order_sign PL_polyhedron_affine_sign(Polyhedron *D, Matrix *T,
  39                                             struct barvinok_options *options)
  40 {
  41     enum order_sign sign;
  42     Polyhedron *I = Polyhedron_Image(D, T, options->MaxRays);
  43     if (POL_ISSET(options->MaxRays, POL_INTEGER))
  44         I = DomainConstraintSimplify(I, options->MaxRays);
  45     if (emptyQ2(I)) {
  46         Polyhedron_Free(I);
  47         I = Polyhedron_Image(D, T, options->MaxRays);
  48     }
  49     sign = interval_minmax(I);
  50     Polyhedron_Free(I);
  51     return sign;
  52 }
  53
  54 enum lp_result PL_polyhedron_range(Polyhedron *D, Value *obj, Value denom,
  55                                 Value *min, Value *max,
  56                                 struct barvinok_options *options)
  57 {
  58     Polyhedron *I;
  59     int bounded;
  60
  61     Matrix *T = Matrix_Alloc(2, D->Dimension+1);
  62     Vector_Copy(obj, T->p[0], D->Dimension+1);
  63     value_assign(T->p[1][D->Dimension], denom);
  64
  65     I = Polyhedron_Image(D, T, options->MaxRays);
  66     Matrix_Free(T);
  67     POL_ENSURE_VERTICES(I);
  68
  69     if (emptyQ(I)) {
  70         Polyhedron_Free(I);
  71         return lp_empty;
  72     }
  73     bounded = line_minmax(I, min, max);
  74
  75     if (!bounded)
  76         return lp_unbounded;
  77     if (value_gt(*min, *max))
  78         return lp_empty;
  79     return lp_ok;
  80 }