#include <isl_seq.h>
#include <isl_polynomial_private.h>
#include <isl_point_private.h>
-#include <isl_dim.h>
+#include <isl_dim_private.h>
#include <isl_map_private.h>
static unsigned pos(__isl_keep isl_dim *dim, enum isl_dim_type type)
case isl_dim_param: return 0;
case isl_dim_in: return dim->nparam;
case isl_dim_out: return dim->nparam + dim->n_in;
+ default: return 0;
}
}
isl_assert(ctx, var >= 0, return NULL);
isl_assert(ctx, size >= 0, return NULL);
- rec = isl_calloc(dim->ctx, struct isl_upoly_rec,
+ rec = isl_calloc(ctx, struct isl_upoly_rec,
sizeof(struct isl_upoly_rec) +
(size - 1) * sizeof(struct isl_upoly *));
if (!rec)
rec->size = size;
return rec;
-error:
- isl_upoly_free(&rec->up);
- return NULL;
}
isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp)
return qp ? isl_dim_copy(qp->dim) : NULL;
}
+unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp,
+ enum isl_dim_type type)
+{
+ return qp ? isl_dim_size(qp->dim, type) : 0;
+}
+
int isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp)
{
return qp ? isl_upoly_is_zero(qp->upoly) : -1;
isl_int_set(cst->n, v);
return qp;
-error:
- isl_qpolynomial_free(qp);
- return NULL;
}
int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
isl_int_set(cst->d, d);
return qp;
-error:
- isl_qpolynomial_free(qp);
- return NULL;
}
static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d)
return NULL;
}
-__isl_give isl_qpolynomial *isl_qpolynomial_add_dims(
- __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned n)
+__isl_give isl_qpolynomial *isl_qpolynomial_insert_dims(
+ __isl_take isl_qpolynomial *qp, enum isl_dim_type type,
+ unsigned first, unsigned n)
{
unsigned total;
unsigned g_pos;
if (!qp)
return NULL;
- g_pos = pos(qp->dim, type) + isl_dim_size(qp->dim, type);
+ isl_assert(qp->div->ctx, first <= isl_dim_size(qp->dim, type),
+ goto error);
+
+ g_pos = pos(qp->dim, type) + first;
qp->div = isl_mat_insert_cols(qp->div, 2 + g_pos, n);
if (!qp->div)
goto error;
}
- qp->dim = isl_dim_add(qp->dim, type, n);
+ qp->dim = isl_dim_insert(qp->dim, type, first, n);
if (!qp->dim)
goto error;
return NULL;
}
+__isl_give isl_qpolynomial *isl_qpolynomial_add_dims(
+ __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned n)
+{
+ unsigned pos;
+
+ pos = isl_qpolynomial_dim(qp, type);
+
+ return isl_qpolynomial_insert_dims(qp, type, pos, n);
+}
+
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_dims(
__isl_take isl_pw_qpolynomial *pwqp,
enum isl_dim_type type, unsigned n)
return NULL;
}
-__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_move(
- __isl_take isl_pw_qpolynomial *pwqp,
- enum isl_dim_type dst_type, unsigned dst_pos,
- enum isl_dim_type src_type, unsigned src_pos, unsigned n)
-{
- int i;
-
- pwqp = isl_pw_qpolynomial_cow(pwqp);
- if (!pwqp)
- return NULL;
-
- pwqp->dim = isl_dim_move(pwqp->dim,
- dst_type, dst_pos, src_type, src_pos, n);
- if (!pwqp->dim)
- goto error;
-
- for (i = 0; i < pwqp->n; ++i) {
- pwqp->p[i].set = isl_set_move_dims(pwqp->p[i].set,
- dst_type, dst_pos,
- src_type, src_pos, n);
- if (!pwqp->p[i].set)
- goto error;
- pwqp->p[i].qp = isl_qpolynomial_move_dims(pwqp->p[i].qp,
- dst_type, dst_pos, src_type, src_pos, n);
- if (!pwqp->p[i].qp)
- goto error;
- }
-
- return pwqp;
-error:
- isl_pw_qpolynomial_free(pwqp);
- return NULL;
-}
-
-
__isl_give struct isl_upoly *isl_upoly_from_affine(isl_ctx *ctx, isl_int *f,
isl_int denom, unsigned len)
{
return up;
}
+__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_dim *dim,
+ isl_int *f, isl_int denom)
+{
+ struct isl_upoly *up;
+
+ if (!dim)
+ return NULL;
+
+ up = isl_upoly_from_affine(dim->ctx, f, denom, 1 + isl_dim_total(dim));
+
+ return isl_qpolynomial_alloc(dim, 0, up);
+}
+
__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
__isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
{
return -1;
}
+/* Return total degree in variables first (inclusive) up to last (exclusive).
+ */
+int isl_upoly_degree(__isl_keep struct isl_upoly *up, int first, int last)
+{
+ int deg = -1;
+ int i;
+ struct isl_upoly_rec *rec;
+
+ if (!up)
+ return -2;
+ if (isl_upoly_is_zero(up))
+ return -1;
+ if (isl_upoly_is_cst(up) || up->var < first)
+ return 0;
+
+ rec = isl_upoly_as_rec(up);
+ if (!rec)
+ return -2;
+
+ for (i = 0; i < rec->n; ++i) {
+ int d;
+
+ if (isl_upoly_is_zero(rec->p[i]))
+ continue;
+ d = isl_upoly_degree(rec->p[i], first, last);
+ if (up->var < last)
+ d += i;
+ if (d > deg)
+ deg = d;
+ }
+
+ return deg;
+}
+
+/* Return total degree in set variables.
+ */
+int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly)
+{
+ unsigned ovar;
+ unsigned nvar;
+
+ if (!poly)
+ return -2;
+
+ ovar = isl_dim_offset(poly->dim, isl_dim_set);
+ nvar = isl_dim_size(poly->dim, isl_dim_set);
+ return isl_upoly_degree(poly->upoly, ovar, ovar + nvar);
+}
+
+__isl_give struct isl_upoly *isl_upoly_coeff(__isl_keep struct isl_upoly *up,
+ unsigned pos, int deg)
+{
+ int i;
+ struct isl_upoly_rec *rec;
+
+ if (!up)
+ return NULL;
+
+ if (isl_upoly_is_cst(up) || up->var < pos) {
+ if (deg == 0)
+ return isl_upoly_copy(up);
+ else
+ return isl_upoly_zero(up->ctx);
+ }
+
+ rec = isl_upoly_as_rec(up);
+ if (!rec)
+ return NULL;
+
+ if (up->var == pos) {
+ if (deg < rec->n)
+ return isl_upoly_copy(rec->p[deg]);
+ else
+ return isl_upoly_zero(up->ctx);
+ }
+
+ up = isl_upoly_copy(up);
+ up = isl_upoly_cow(up);
+ rec = isl_upoly_as_rec(up);
+ if (!rec)
+ goto error;
+
+ for (i = 0; i < rec->n; ++i) {
+ struct isl_upoly *t;
+ t = isl_upoly_coeff(rec->p[i], pos, deg);
+ if (!t)
+ goto error;
+ isl_upoly_free(rec->p[i]);
+ rec->p[i] = t;
+ }
+
+ return up;
+error:
+ isl_upoly_free(up);
+ return NULL;
+}
+
+/* Return coefficient of power "deg" of variable "t_pos" of type "type".
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_coeff(
+ __isl_keep isl_qpolynomial *qp,
+ enum isl_dim_type type, unsigned t_pos, int deg)
+{
+ unsigned g_pos;
+ struct isl_upoly *up;
+ isl_qpolynomial *c;
+
+ if (!qp)
+ return NULL;
+
+ isl_assert(qp->div->ctx, t_pos < isl_dim_size(qp->dim, type),
+ return NULL);
+
+ g_pos = pos(qp->dim, type) + t_pos;
+ up = isl_upoly_coeff(qp->upoly, g_pos, deg);
+
+ c = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row, up);
+ if (!c)
+ return NULL;
+ isl_mat_free(c->div);
+ c->div = isl_mat_copy(qp->div);
+ if (!c->div)
+ goto error;
+ return c;
+error:
+ isl_qpolynomial_free(c);
+ return NULL;
+}
+
+/* Homogenize the polynomial in the variables first (inclusive) up to
+ * last (exclusive) by inserting powers of variable first.
+ * Variable first is assumed not to appear in the input.
+ */
+__isl_give struct isl_upoly *isl_upoly_homogenize(
+ __isl_take struct isl_upoly *up, int deg, int target,
+ int first, int last)
+{
+ int i;
+ struct isl_upoly_rec *rec;
+
+ if (!up)
+ return NULL;
+ if (isl_upoly_is_zero(up))
+ return up;
+ if (deg == target)
+ return up;
+ if (isl_upoly_is_cst(up) || up->var < first) {
+ struct isl_upoly *hom;
+
+ hom = isl_upoly_pow(up->ctx, first, target - deg);
+ if (!hom)
+ goto error;
+ rec = isl_upoly_as_rec(hom);
+ rec->p[target - deg] = isl_upoly_mul(rec->p[target - deg], up);
+
+ return hom;
+ }
+
+ up = isl_upoly_cow(up);
+ rec = isl_upoly_as_rec(up);
+ if (!rec)
+ goto error;
+
+ for (i = 0; i < rec->n; ++i) {
+ if (isl_upoly_is_zero(rec->p[i]))
+ continue;
+ rec->p[i] = isl_upoly_homogenize(rec->p[i],
+ up->var < last ? deg + i : i, target,
+ first, last);
+ if (!rec->p[i])
+ goto error;
+ }
+
+ return up;
+error:
+ isl_upoly_free(up);
+ return NULL;
+}
+
+/* Homogenize the polynomial in the set variables by introducing
+ * powers of an extra set variable at position 0.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_homogenize(
+ __isl_take isl_qpolynomial *poly)
+{
+ unsigned ovar;
+ unsigned nvar;
+ int deg = isl_qpolynomial_degree(poly);
+
+ if (deg < -1)
+ goto error;
+
+ poly = isl_qpolynomial_insert_dims(poly, isl_dim_set, 0, 1);
+ poly = isl_qpolynomial_cow(poly);
+ if (!poly)
+ goto error;
+
+ ovar = isl_dim_offset(poly->dim, isl_dim_set);
+ nvar = isl_dim_size(poly->dim, isl_dim_set);
+ poly->upoly = isl_upoly_homogenize(poly->upoly, 0, deg,
+ ovar, ovar + nvar);
+ if (!poly->upoly)
+ goto error;
+
+ return poly;
+error:
+ isl_qpolynomial_free(poly);
+ return NULL;
+}
+
__isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
__isl_take isl_mat *div)
{
case isl_dim_out: return isl_dim_size(term->dim, type);
case isl_dim_div: return term->div->n_row;
case isl_dim_all: return isl_dim_total(term->dim) + term->div->n_row;
+ default: return 0;
}
}
return NULL;
}
-int isl_pw_qpolynomial_foreach_piece(__isl_keep isl_pw_qpolynomial *pwqp,
- int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
- void *user), void *user)
-{
- int i;
-
- if (!pwqp)
- return -1;
-
- for (i = 0; i < pwqp->n; ++i)
- if (fn(isl_set_copy(pwqp->p[i].set),
- isl_qpolynomial_copy(pwqp->p[i].qp), user) < 0)
- return -1;
-
- return 0;
-}
-
-static int any_divs(__isl_keep isl_set *set)
-{
- int i;
-
- if (!set)
- return -1;
-
- for (i = 0; i < set->n; ++i)
- if (set->p[i]->n_div > 0)
- return 1;
-
- return 0;
-}
-
__isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
__isl_take isl_dim *dim)
{
+ int i;
+ int extra;
+ unsigned total;
+
if (!qp || !dim)
goto error;
if (!qp)
goto error;
+ extra = isl_dim_size(dim, isl_dim_set) -
+ isl_dim_size(qp->dim, isl_dim_set);
+ total = isl_dim_total(qp->dim);
if (qp->div->n_row) {
- int i;
- int extra;
- unsigned total;
int *exp;
- extra = isl_dim_size(dim, isl_dim_set) -
- isl_dim_size(qp->dim, isl_dim_set);
- total = isl_dim_total(qp->dim);
exp = isl_alloc_array(qp->div->ctx, int, qp->div->n_row);
if (!exp)
goto error;
free(exp);
if (!qp->upoly)
goto error;
- qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra);
- if (!qp->div)
- goto error;
- for (i = 0; i < qp->div->n_row; ++i)
- isl_seq_clr(qp->div->row[i] + 2 + total, extra);
}
+ qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra);
+ if (!qp->div)
+ goto error;
+ for (i = 0; i < qp->div->n_row; ++i)
+ isl_seq_clr(qp->div->row[i] + 2 + total, extra);
isl_dim_free(qp->dim);
qp->dim = dim;
return NULL;
}
-static int foreach_lifted_subset(__isl_take isl_set *set,
- __isl_take isl_qpolynomial *qp,
- int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
- void *user), void *user)
-{
- int i;
-
- if (!set || !qp)
- goto error;
-
- for (i = 0; i < set->n; ++i) {
- isl_set *lift;
- isl_qpolynomial *copy;
-
- lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
- lift = isl_set_lift(lift);
-
- copy = isl_qpolynomial_copy(qp);
- copy = isl_qpolynomial_lift(copy, isl_set_get_dim(lift));
-
- if (fn(lift, copy, user) < 0)
- goto error;
- }
-
- isl_set_free(set);
- isl_qpolynomial_free(qp);
-
- return 0;
-error:
- isl_set_free(set);
- isl_qpolynomial_free(qp);
- return -1;
-}
-
-int isl_pw_qpolynomial_foreach_lifted_piece(__isl_keep isl_pw_qpolynomial *pwqp,
- int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
- void *user), void *user)
-{
- int i;
-
- if (!pwqp)
- return -1;
-
- for (i = 0; i < pwqp->n; ++i) {
- isl_set *set;
- isl_qpolynomial *qp;
-
- set = isl_set_copy(pwqp->p[i].set);
- qp = isl_qpolynomial_copy(pwqp->p[i].qp);
- if (!any_divs(set)) {
- if (fn(set, qp, user) < 0)
- return -1;
- continue;
- }
- if (foreach_lifted_subset(set, qp, fn, user) < 0)
- return -1;
- }
-
- return 0;
-}
-
/* For each parameter or variable that does not appear in qp,
* first eliminate the variable from all constraints and then set it to zero.
*/