bfcounter.h

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