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 /* base for non-parametric counting */
  17 struct np_base : public polar_decomposer {
  18     unsigned dim;
  19     ZZ one;
  20
  21     np_base(unsigned dim) {
  22         this->dim = dim;
  23         one = 1;
  24     }
  25
  26     virtual void handle_polar(Polyhedron *C, Value *vertex, QQ c) = 0;
  27     virtual void handle_polar(Polyhedron *C, int s);
  28     virtual void start(Polyhedron *P, barvinok_options *options);
  29     void do_vertex_cone(const QQ& factor, Polyhedron *Cone,
  30                         Value *vertex, barvinok_options *options) {
  31         current_vertex = vertex;
  32         this->factor = factor;
  33         decompose(Cone, options);
  34     }
  35     virtual void init(Polyhedron *P) {
  36     }
  37     virtual void get_count(Value *result) {
  38         assert(0);
  39     }
  40     virtual ~np_base() {
  41     }
  42
  43 private:
  44     QQ factor;
  45     Value *current_vertex;
  46 };
  47
  48 struct reducer : public np_base {
  49     vec_ZZ vertex;
  50     //vec_ZZ den;
  51     ZZ num;
  52     mpq_t tcount;
  53     mpz_t tn;
  54     mpz_t td;
  55     int lower;      // call base when only this many variables is left
  56
  57     reducer(unsigned dim) : np_base(dim) {
  58         //den.SetLength(dim);
  59         mpq_init(tcount);
  60         mpz_init(tn);
  61         mpz_init(td);
  62     }
  63
  64     ~reducer() {
  65         mpq_clear(tcount);
  66         mpz_clear(tn);
  67         mpz_clear(td);
  68     }
  69
  70     virtual void handle_polar(Polyhedron *C, Value *vertex, QQ c);
  71     void reduce(QQ c, vec_ZZ& num, mat_ZZ& den_f);
  72     virtual void base(QQ& c, const vec_ZZ& num, const mat_ZZ& den_f) = 0;
  73     virtual void split(vec_ZZ& num, ZZ& num_s, vec_ZZ& num_p,
  74                        mat_ZZ& den_f, vec_ZZ& den_s, mat_ZZ& den_r) = 0;
  75     virtual gen_fun *get_gf() {
  76         assert(0);
  77         return NULL;
  78     }
  79 };
  80
  81 struct ireducer : public reducer {
  82     ireducer(unsigned dim) : reducer(dim) {}
  83
  84     virtual void split(vec_ZZ& num, ZZ& num_s, vec_ZZ& num_p,
  85                        mat_ZZ& den_f, vec_ZZ& den_s, mat_ZZ& den_r);
  86 };
  87
  88 void normalize(ZZ& sign, ZZ& num_s, vec_ZZ& num_p, vec_ZZ& den_s, vec_ZZ& den_p,
  89                mat_ZZ& f);
  90
  91 // incremental counter
  92 struct icounter : public ireducer {
  93     mpq_t count;
  94
  95     icounter(unsigned dim) : ireducer(dim) {
  96         mpq_init(count);
  97         lower = 1;
  98     }
  99     ~icounter() {
 100         mpq_clear(count);
 101     }
 102     virtual void base(QQ& c, const vec_ZZ& num, const mat_ZZ& den_f);
 103     virtual void get_count(Value *result) {
 104         assert(value_one_p(&count[0]._mp_den));
 105         value_assign(*result, &count[0]._mp_num);
 106     }
 107 };
 108
 109 void normalize(ZZ& sign, ZZ& num, vec_ZZ& den);
 110
 111 /* An incremental counter for possibly infinite sets.
 112  * Rather than just keeping track of the constant term
 113  * of the Laurent expansions, we also keep track of the
 114  * coefficients of negative powers.
 115  * If any of these is non-zero, then the counted set is infinite.
 116  */
 117 struct infinite_icounter : public ireducer {
 118     /* an array of coefficients; count[i] is the coeffient of
 119      * the term with power -i.
 120      */
 121     mpq_t *count;
 122     unsigned len;
 123
 124     infinite_icounter(unsigned dim, unsigned maxlen) : ireducer(dim), len(maxlen+1) {
 125         /* Not sure whether it works for dim != 1 */
 126         assert(dim == 1);
 127         count = new mpq_t[len];
 128         for (int i = 0; i < len; ++i)
 129             mpq_init(count[i]);
 130         lower = 1;
 131     }
 132     ~infinite_icounter() {
 133         for (int i = 0; i < len; ++i)
 134             mpq_clear(count[i]);
 135         delete [] count;
 136     }
 137     virtual void base(QQ& c, const vec_ZZ& num, const mat_ZZ& den_f);
 138 };
 139
 140 #endif