bfcounter.h

   1 #include <vector>
   2 #include <gmp.h>
   3 #include <barvinok/polylib.h>
   4 #include <barvinok/NTL_QQ.h>
   5 #include "reducer.h"
   6
   7 struct bfc_term_base {
   8     // the number of times a given factor appears in the denominator
   9     int     *powers;
  10     mat_ZZ   terms;
  11
  12     bfc_term_base(int len) {
  13         powers = new int[len];
  14     }
  15
  16     virtual ~bfc_term_base() {
  17         delete [] powers;
  18     }
  19 };
  20
  21 struct bfc_term : public bfc_term_base {
  22     vec_QQ   c;
  23
  24     bfc_term(int len) : bfc_term_base(len) {}
  25 };
  26
  27 typedef std::vector< bfc_term_base * > bfc_vec;
  28
  29 struct bf_reducer;
  30
  31 struct bf_base : public np_base {
  32     ZZ one;
  33     mpq_t tcount;
  34     mpz_t tn;
  35     mpz_t td;
  36     int lower;      // call base when only this many variables is left
  37
  38     bf_base(unsigned dim) : np_base(dim) {
  39         mpq_init(tcount);
  40         mpz_init(tn);
  41         mpz_init(td);
  42         one = 1;
  43     }
  44
  45     ~bf_base() {
  46         mpq_clear(tcount);
  47         mpz_clear(tn);
  48         mpz_clear(td);
  49     }
  50
  51     virtual void handle(const mat_ZZ& rays, Value *vertex, QQ c, int *closed);
  52     int setup_factors(const mat_ZZ& rays, mat_ZZ& factors, bfc_term_base* t, int s);
  53
  54     bfc_term_base* find_bfc_term(bfc_vec& v, int *powers, int len);
  55     void add_term(bfc_term_base *t, vec_ZZ& num1, vec_ZZ& num);
  56     void add_term(bfc_term_base *t, vec_ZZ& num);
  57
  58     void reduce(mat_ZZ& factors, bfc_vec& v);
  59     virtual void base(mat_ZZ& factors, bfc_vec& v) = 0;
  60
  61     virtual bfc_term_base* new_bf_term(int len) = 0;
  62     virtual void set_factor(bfc_term_base *t, int k, int change) = 0;
  63     virtual void set_factor(bfc_term_base *t, int k, mpq_t &f, int change) = 0;
  64     virtual void set_factor(bfc_term_base *t, int k, const QQ& c, int change) = 0;
  65     virtual void update_term(bfc_term_base *t, int i) = 0;
  66     virtual void insert_term(bfc_term_base *t, int i) = 0;
  67     virtual bool constant_vertex(int dim) = 0;
  68     virtual void cum(bf_reducer *bfr, bfc_term_base *t, int k,
  69                      dpoly_r *r) = 0;
  70 };
  71
  72 struct bfcounter_base : public bf_base {
  73     QQ c;
  74
  75     bfcounter_base(unsigned dim) : bf_base(dim) {
  76     }
  77
  78     bfc_term_base* new_bf_term(int len);
  79
  80     virtual void set_factor(bfc_term_base *t, int k, int change);
  81     virtual void set_factor(bfc_term_base *t, int k, mpq_t &f, int change);
  82     virtual void set_factor(bfc_term_base *t, int k, const QQ& c_factor, int change);
  83     virtual void insert_term(bfc_term_base *t, int i);
  84     virtual void update_term(bfc_term_base *t, int i);
  85
  86     virtual bool constant_vertex(int dim) { return true; }
  87     virtual void cum(bf_reducer *bfr, bfc_term_base *t, int k, dpoly_r *r) {
  88         assert(0);
  89     }
  90 };
  91
  92 struct bf_reducer {
  93     mat_ZZ& factors;
  94     bfc_vec& v;
  95     bf_base *bf;
  96
  97     unsigned nf;
  98     unsigned d;
  99
 100     mat_ZZ nfactors;
 101     int *old2new;
 102     int *sign;
 103     unsigned int nnf;
 104     bfc_vec vn;
 105
 106     vec_ZZ extra_num;
 107     int changes;
 108     int no_param;           // r from text
 109     int only_param;         // k-r-s from text
 110     int total_power;        // k from text
 111
 112     // created in compute_reduced_factors
 113     int *bpowers;
 114     // set in update_powers
 115     int *npowers;
 116     vec_ZZ l_extra_num;
 117     int l_changes;
 118
 119     bf_reducer(mat_ZZ& factors, bfc_vec& v, bf_base *bf)
 120             : factors(factors), v(v), bf(bf) {
 121         nf = factors.NumRows();
 122         d = factors.NumCols();
 123         old2new = new int[nf];
 124         sign = new int[nf];
 125
 126         extra_num.SetLength(d-1);
 127     }
 128     ~bf_reducer() {
 129         delete [] old2new;
 130         delete [] sign;
 131         delete [] npowers;
 132         delete [] bpowers;
 133     }
 134
 135     void compute_reduced_factors();
 136     void compute_extra_num(int i);
 137
 138     void reduce();
 139
 140     void update_powers(const std::vector<int>& powers);
 141 };