From 4e48f3928ed2aff30173e8911db84efc37fc3d54 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 20 Jul 2009 11:33:41 +0200 Subject: [PATCH] extract out param_polynomial from laurent.cc --- Makefile.am | 2 ++ laurent.cc | 75 ++++++----------------------------------------------- param_polynomial.cc | 50 +++++++++++++++++++++++++++++++++++ param_polynomial.h | 20 ++++++++++++++ 4 files changed, 80 insertions(+), 67 deletions(-) create mode 100644 param_polynomial.cc create mode 100644 param_polynomial.h diff --git a/Makefile.am b/Makefile.am index 8ccfc95..9cca929 100644 --- a/Makefile.am +++ b/Makefile.am @@ -131,6 +131,8 @@ libbarvinok_core_la_SOURCES = \ normalization.c \ normalization.h \ options.c \ + param_polynomial.cc \ + param_polynomial.h \ param_util.c \ param_util.h \ piputil.h \ diff --git a/laurent.cc b/laurent.cc index 53269b3..91e3bc7 100644 --- a/laurent.cc +++ b/laurent.cc @@ -6,6 +6,7 @@ #include "conversion.h" #include "decomposer.h" #include "laurent.h" +#include "param_polynomial.h" #include "param_util.h" #include "reduce_domain.h" #include "vertex_cone.h" @@ -480,79 +481,19 @@ const evalue *reciprocal::get_coefficient() return c; } -/* A term in the input polynomial */ -struct term { - vector powers; - const evalue *coeff; -}; - -static void collect_terms_r(vector &terms, vector &powers, - const evalue *polynomial, unsigned nvar) -{ - if (EVALUE_IS_ZERO(*polynomial)) - return; - - if (value_zero_p(polynomial->d)) - assert(polynomial->x.p->type == ::polynomial); - if (value_notzero_p(polynomial->d) || polynomial->x.p->pos > nvar) { - struct term t; - t.powers = powers; - t.coeff = polynomial; - terms.push_back(t); - return; - } - - for (int i = polynomial->x.p->size-1; i >= 0; --i) { - powers[polynomial->x.p->pos-1] = i; - collect_terms_r(terms, powers, &polynomial->x.p->arr[i], nvar); - } -} - -/* Expand "polynomial" as a sum of powers of the "nvar" variables, - * collect the terms in "terms" and return the maximal total degree. - */ -static unsigned collect_terms(vector &terms, - const evalue *polynomial, unsigned nvar) -{ - vector powers(nvar); - for (int i = 0; i < nvar; ++i) - powers[i] = 0; - collect_terms_r(terms, powers, polynomial, nvar); - - unsigned max_degree = 0; - for (int i = 0; i < terms.size(); ++i) { - int sum = 0; - for (int j = 0; j < nvar; ++j) - sum += terms[i].powers[j]; - if (sum > max_degree) - max_degree = sum; - } - return max_degree; -} - -/* -static void dump_terms(const vector &terms) -{ - for (int i = 0; i < terms.size(); ++i) { - cerr << terms[i].powers; - print_evalue(stderr, terms[i].coeff, test); - } -} -*/ - struct laurent_summator : public signed_cone_consumer, public vertex_decomposer { const evalue *polynomial; unsigned dim; vertex_cone vc; - vector terms; + param_polynomial poly; evalue *result; unsigned max_power; laurent_summator(const evalue *e, unsigned dim, Param_Polyhedron *PP) : polynomial(e), dim(dim), vertex_decomposer(PP, *this), - vc(dim) { - max_power = dim + collect_terms(terms, polynomial, dim); + vc(dim), poly(e, dim) { + max_power = dim + poly.degree(); result = NULL; } ~laurent_summator() { @@ -577,8 +518,8 @@ void laurent_summator::handle(const signed_cone& sc, barvinok_options *options) vc.init(sc.rays, V, max_power); reciprocal recip(vc); todd_product tp(vc); - for (int i = 0; i < terms.size(); ++i) { - recip.start(terms[i].powers); + for (int i = 0; i < poly.terms.size(); ++i) { + recip.start(poly.terms[i].powers); do { const evalue *c = recip.get_coefficient(); if (!c) @@ -586,11 +527,11 @@ void laurent_summator::handle(const signed_cone& sc, barvinok_options *options) const evalue *t = tp.get_coefficient(recip.power); - evalue *f = evalue_dup(terms[i].coeff); + evalue *f = evalue_dup(poly.terms[i].coeff); if (sc.sign < 0) evalue_negate(f); for (int j = 0; j < dim; ++j) - evalue_mul(f, *factorial(terms[i].powers[j])); + evalue_mul(f, *factorial(poly.terms[i].powers[j])); evalue_shift_variables(f, 0, -dim); emul(c, f); emul(t, f); diff --git a/param_polynomial.cc b/param_polynomial.cc new file mode 100644 index 0000000..84dd7d2 --- /dev/null +++ b/param_polynomial.cc @@ -0,0 +1,50 @@ +#include "param_polynomial.h" + +using std::vector; + +/* Expand "polynomial" as a sum of powers of the "nvar" variables, + * and collect the terms in "terms". + */ +static void collect_terms(vector &terms, vector &powers, + const evalue *polynomial, unsigned nvar) +{ + if (EVALUE_IS_ZERO(*polynomial)) + return; + + if (value_zero_p(polynomial->d)) + assert(polynomial->x.p->type == ::polynomial); + if (value_notzero_p(polynomial->d) || polynomial->x.p->pos > nvar) { + struct param_term t; + t.powers = powers; + t.coeff = polynomial; + terms.push_back(t); + return; + } + + for (int i = polynomial->x.p->size-1; i >= 0; --i) { + powers[polynomial->x.p->pos-1] = i; + collect_terms(terms, powers, &polynomial->x.p->arr[i], nvar); + } +} + +param_polynomial::param_polynomial(const evalue *polynomial, unsigned nvar) +{ + vector powers(nvar); + for (int i = 0; i < nvar; ++i) + powers[i] = 0; + collect_terms(terms, powers, polynomial, nvar); +} + +unsigned param_polynomial::degree() +{ + unsigned max_degree = 0; + + for (int i = 0; i < terms.size(); ++i) { + int sum = 0; + for (int j = 0; j < terms[i].powers.size(); ++j) + sum += terms[i].powers[j]; + if (sum > max_degree) + max_degree = sum; + } + return max_degree; +} diff --git a/param_polynomial.h b/param_polynomial.h new file mode 100644 index 0000000..35e3410 --- /dev/null +++ b/param_polynomial.h @@ -0,0 +1,20 @@ +#ifndef PARAM_POLYNOMIAL_H +#define PARAM_POLYNOMIAL_H + +#include +#include + +/* A term in the parametric polynomial */ +struct param_term { + std::vector powers; + const evalue *coeff; +}; + +struct param_polynomial { + std::vector terms; + + param_polynomial(const evalue *polynomial, unsigned nvar); + unsigned degree(); +}; + +#endif -- 2.11.4.GIT