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