reducer.h

   1 #ifndef REDUCER_H
   2 #define REDUCER_H
   3
   4 #include <NTL/mat_ZZ.h>
   5 #include <barvinok/NTL_QQ.h>
   6 #include <barvinok/options.h>
   7 #include "decomposer.h"
   8 #include "dpoly.h"
   9
  10 #ifdef NTL_STD_CXX
  11 using namespace NTL;
  12 #endif
  13
  14 struct gen_fun;
  15
  16 extern struct OrthogonalException {} Orthogonal;
  17
  18 /* base for non-parametric counting */
  19 struct np_base : public signed_cone_consumer {
  20     unsigned dim;
  21     ZZ one;
  22
  23     np_base(unsigned dim) {
  24         this->dim = dim;
  25         one = 1;
  26     }
  27
  28     virtual void handle(const mat_ZZ& rays, Value *vertex, const QQ& c,
  29                         unsigned long det, int *closed,
  30                         barvinok_options *options) = 0;
  31     virtual void handle(const signed_cone& sc, barvinok_options *options);
  32     virtual void start(Polyhedron *P, barvinok_options *options);
  33     void do_vertex_cone(const QQ& factor, Polyhedron *Cone,
  34                         Value *vertex, barvinok_options *options) {
  35         current_vertex = vertex;
  36         this->factor = factor;
  37         barvinok_decompose(Cone, *this, options);
  38     }
  39     virtual void init(Polyhedron *P) {
  40     }
  41     virtual void reset() {
  42         assert(0);
  43     }
  44     virtual void get_count(Value *result) {
  45         assert(0);
  46     }
  47     virtual ~np_base() {
  48     }
  49
  50 private:
  51     QQ factor;
  52     Value *current_vertex;
  53 };
  54
  55 struct reducer : public np_base {
  56     mat_ZZ vertex;
  57     //vec_ZZ den;
  58     ZZ num;
  59     mpq_t tcount;
  60     mpz_t tn;
  61     mpz_t td;
  62     int lower;      // call base when only this many variables is left
  63
  64     reducer(unsigned dim) : np_base(dim) {
  65         vertex.SetDims(1, dim);
  66         //den.SetLength(dim);
  67         mpq_init(tcount);
  68         mpz_init(tn);
  69         mpz_init(td);
  70     }
  71
  72     ~reducer() {
  73         mpq_clear(tcount);
  74         mpz_clear(tn);
  75         mpz_clear(td);
  76     }
  77
  78     virtual void handle(const mat_ZZ& rays, Value *vertex, const QQ& c,
  79                         unsigned long det, int *closed, barvinok_options *options);
  80     void reduce(const vec_QQ& c, const mat_ZZ& num, const mat_ZZ& den_f);
  81     virtual void base(const QQ& c, const vec_ZZ& num, const mat_ZZ& den_f) = 0;
  82     virtual void base(const vec_QQ& c, const mat_ZZ& num, const mat_ZZ& den_f);
  83     virtual void split(const mat_ZZ& num, vec_ZZ& num_s, mat_ZZ& num_p,
  84                        const mat_ZZ& den_f, vec_ZZ& den_s, mat_ZZ& den_r) = 0;
  85     virtual gen_fun *get_gf() {
  86         assert(0);
  87         return NULL;
  88     }
  89 };
  90
  91 void split_one(const mat_ZZ& num, vec_ZZ& num_s, mat_ZZ& num_p,
  92                const mat_ZZ& den_f, vec_ZZ& den_s, mat_ZZ& den_r);
  93
  94 struct ireducer : public reducer {
  95     ireducer(unsigned dim) : reducer(dim) {}
  96
  97     virtual void split(const mat_ZZ& num, vec_ZZ& num_s, mat_ZZ& num_p,
  98                        const mat_ZZ& den_f, vec_ZZ& den_s, mat_ZZ& den_r) {
  99         split_one(num, num_s, num_p, den_f, den_s, den_r);
 100     }
 101 };
 102
 103 void normalize(ZZ& sign, vec_ZZ& num_s, mat_ZZ& num_p, vec_ZZ& den_s, vec_ZZ& den_p,
 104                mat_ZZ& f);
 105
 106 // incremental counter
 107 struct icounter : public ireducer {
 108     mpq_t count;
 109
 110     icounter(unsigned dim) : ireducer(dim) {
 111         mpq_init(count);
 112         lower = 1;
 113     }
 114     ~icounter() {
 115         mpq_clear(count);
 116     }
 117     virtual void base(const QQ& c, const vec_ZZ& num, const mat_ZZ& den_f);
 118     virtual void get_count(Value *result) {
 119         assert(value_one_p(&count[0]._mp_den));
 120         value_assign(*result, &count[0]._mp_num);
 121     }
 122 };
 123
 124 void normalize(ZZ& sign, ZZ& num, vec_ZZ& den);
 125
 126 /* An incremental counter for possibly infinite sets.
 127  * Rather than just keeping track of the constant term
 128  * of the Laurent expansions, we also keep track of the
 129  * coefficients of negative powers.
 130  * If any of these is non-zero, then the counted set is infinite.
 131  */
 132 struct infinite_icounter : public ireducer {
 133     /* an array of coefficients; count[i] is the coeffient of
 134      * the term with power -i.
 135      */
 136     mpq_t *count;
 137     unsigned len;
 138
 139     infinite_icounter(unsigned dim, unsigned maxlen) : ireducer(dim), len(maxlen+1) {
 140         /* Not sure whether it works for dim != 1 */
 141         assert(dim == 1);
 142         count = new mpq_t[len];
 143         for (int i = 0; i < len; ++i)
 144             mpq_init(count[i]);
 145         lower = 1;
 146     }
 147     ~infinite_icounter() {
 148         for (int i = 0; i < len; ++i)
 149             mpq_clear(count[i]);
 150         delete [] count;
 151     }
 152     virtual void base(const QQ& c, const vec_ZZ& num, const mat_ZZ& den_f);
 153 };
 154
 155 #endif