polysign_polylib.c

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