reducer.h

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