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