isl_fold.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #define ISL_DIM_H
  12 #include <isl_map_private.h>
  13 #include <isl_union_map_private.h>
  14 #include <isl_polynomial_private.h>
  15 #include <isl_point_private.h>
  16 #include <isl_space_private.h>
  17 #include <isl_lp_private.h>
  18 #include <isl_seq.h>
  19 #include <isl_mat_private.h>
  20 #include <isl_val_private.h>
  21 #include <isl_vec_private.h>
  22 #include <isl_config.h>
  23 #include <isl/deprecated/polynomial_int.h>
  24
  25 enum isl_fold isl_fold_type_negate(enum isl_fold type)
  26 {
  27         switch (type) {
  28         case isl_fold_min:
  29                 return isl_fold_max;
  30         case isl_fold_max:
  31                 return isl_fold_min;
  32         case isl_fold_list:
  33                 return isl_fold_list;
  34         }
  35
  36         isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort());
  37 }
  38
  39 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
  40         enum isl_fold type, __isl_take isl_space *dim, int n)
  41 {
  42         isl_qpolynomial_fold *fold;
  43
  44         if (!dim)
  45                 goto error;
  46
  47         isl_assert(dim->ctx, n >= 0, goto error);
  48         fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
  49                         sizeof(struct isl_qpolynomial_fold) +
  50                         (n - 1) * sizeof(struct isl_qpolynomial *));
  51         if (!fold)
  52                 goto error;
  53
  54         fold->ref = 1;
  55         fold->size = n;
  56         fold->n = 0;
  57         fold->type = type;
  58         fold->dim = dim;
  59
  60         return fold;
  61 error:
  62         isl_space_free(dim);
  63         return NULL;
  64 }
  65
  66 isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
  67 {
  68         return fold ? fold->dim->ctx : NULL;
  69 }
  70
  71 __isl_give isl_space *isl_qpolynomial_fold_get_domain_space(
  72         __isl_keep isl_qpolynomial_fold *fold)
  73 {
  74         return fold ? isl_space_copy(fold->dim) : NULL;
  75 }
  76
  77 __isl_give isl_space *isl_qpolynomial_fold_get_space(
  78         __isl_keep isl_qpolynomial_fold *fold)
  79 {
  80         isl_space *space;
  81         if (!fold)
  82                 return NULL;
  83         space = isl_space_copy(fold->dim);
  84         space = isl_space_from_domain(space);
  85         space = isl_space_add_dims(space, isl_dim_out, 1);
  86         return space;
  87 }
  88
  89 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space(
  90         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
  91 {
  92         int i;
  93
  94         fold = isl_qpolynomial_fold_cow(fold);
  95         if (!fold || !dim)
  96                 goto error;
  97
  98         for (i = 0; i < fold->n; ++i) {
  99                 fold->qp[i] = isl_qpolynomial_reset_domain_space(fold->qp[i],
 100                                                         isl_space_copy(dim));
 101                 if (!fold->qp[i])
 102                         goto error;
 103         }
 104
 105         isl_space_free(fold->dim);
 106         fold->dim = dim;
 107
 108         return fold;
 109 error:
 110         isl_qpolynomial_fold_free(fold);
 111         isl_space_free(dim);
 112         return NULL;
 113 }
 114
 115 /* Reset the space of "fold".  This function is called from isl_pw_templ.c
 116  * and doesn't know if the space of an element object is represented
 117  * directly or through its domain.  It therefore passes along both.
 118  */
 119 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain(
 120         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space,
 121         __isl_take isl_space *domain)
 122 {
 123         isl_space_free(space);
 124         return isl_qpolynomial_fold_reset_domain_space(fold, domain);
 125 }
 126
 127 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
 128         enum isl_dim_type type, unsigned first, unsigned n)
 129 {
 130         int i;
 131
 132         if (!fold)
 133                 return -1;
 134         if (fold->n == 0 || n == 0)
 135                 return 0;
 136
 137         for (i = 0; i < fold->n; ++i) {
 138                 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
 139                                                             type, first, n);
 140                 if (involves < 0 || involves)
 141                         return involves;
 142         }
 143         return 0;
 144 }
 145
 146 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
 147         __isl_take isl_qpolynomial_fold *fold,
 148         enum isl_dim_type type, unsigned pos, const char *s)
 149 {
 150         int i;
 151
 152         fold = isl_qpolynomial_fold_cow(fold);
 153         if (!fold)
 154                 return NULL;
 155         fold->dim = isl_space_set_dim_name(fold->dim, type, pos, s);
 156         if (!fold->dim)
 157                 goto error;
 158
 159         for (i = 0; i < fold->n; ++i) {
 160                 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
 161                                                             type, pos, s);
 162                 if (!fold->qp[i])
 163                         goto error;
 164         }
 165
 166         return fold;
 167 error:
 168         isl_qpolynomial_fold_free(fold);
 169         return NULL;
 170 }
 171
 172 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
 173         __isl_take isl_qpolynomial_fold *fold,
 174         enum isl_dim_type type, unsigned first, unsigned n)
 175 {
 176         int i;
 177         enum isl_dim_type set_type;
 178
 179         if (!fold)
 180                 return NULL;
 181         if (n == 0)
 182                 return fold;
 183
 184         set_type = type == isl_dim_in ? isl_dim_set : type;
 185
 186         fold = isl_qpolynomial_fold_cow(fold);
 187         if (!fold)
 188                 return NULL;
 189         fold->dim = isl_space_drop_dims(fold->dim, set_type, first, n);
 190         if (!fold->dim)
 191                 goto error;
 192
 193         for (i = 0; i < fold->n; ++i) {
 194                 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
 195                                                             type, first, n);
 196                 if (!fold->qp[i])
 197                         goto error;
 198         }
 199
 200         return fold;
 201 error:
 202         isl_qpolynomial_fold_free(fold);
 203         return NULL;
 204 }
 205
 206 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
 207         __isl_take isl_qpolynomial_fold *fold,
 208         enum isl_dim_type type, unsigned first, unsigned n)
 209 {
 210         int i;
 211
 212         if (!fold)
 213                 return NULL;
 214         if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type))
 215                 return fold;
 216
 217         fold = isl_qpolynomial_fold_cow(fold);
 218         if (!fold)
 219                 return NULL;
 220         fold->dim = isl_space_insert_dims(fold->dim, type, first, n);
 221         if (!fold->dim)
 222                 goto error;
 223
 224         for (i = 0; i < fold->n; ++i) {
 225                 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
 226                                                             type, first, n);
 227                 if (!fold->qp[i])
 228                         goto error;
 229         }
 230
 231         return fold;
 232 error:
 233         isl_qpolynomial_fold_free(fold);
 234         return NULL;
 235 }
 236
 237 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
 238 {
 239         struct isl_upoly_cst *cst;
 240
 241         cst = isl_upoly_as_cst(qp->upoly);
 242         if (!cst)
 243                 return 0;
 244
 245         return isl_int_sgn(cst->n) < 0 ? -1 : 1;
 246 }
 247
 248 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
 249         __isl_keep isl_qpolynomial *qp)
 250 {
 251         enum isl_lp_result res;
 252         isl_vec *aff;
 253         isl_int opt;
 254         int sgn = 0;
 255
 256         aff = isl_qpolynomial_extract_affine(qp);
 257         if (!aff)
 258                 return 0;
 259
 260         isl_int_init(opt);
 261
 262         res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
 263                                 &opt, NULL, NULL);
 264         if (res == isl_lp_error)
 265                 goto done;
 266         if (res == isl_lp_empty ||
 267             (res == isl_lp_ok && !isl_int_is_neg(opt))) {
 268                 sgn = 1;
 269                 goto done;
 270         }
 271
 272         res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
 273                                 &opt, NULL, NULL);
 274         if (res == isl_lp_ok && !isl_int_is_pos(opt))
 275                 sgn = -1;
 276
 277 done:
 278         isl_int_clear(opt);
 279         isl_vec_free(aff);
 280         return sgn;
 281 }
 282
 283 /* Determine, if possible, the sign of the quasipolynomial "qp" on
 284  * the domain "set".
 285  *
 286  * If qp is a constant, then the problem is trivial.
 287  * If qp is linear, then we check if the minimum of the corresponding
 288  * affine constraint is non-negative or if the maximum is non-positive.
 289  *
 290  * Otherwise, we check if the outermost variable "v" has a lower bound "l"
 291  * in "set".  If so, we write qp(v,v') as
 292  *
 293  *      q(v,v') * (v - l) + r(v')
 294  *
 295  * if q(v,v') and r(v') have the same known sign, then the original
 296  * quasipolynomial has the same sign as well.
 297  *
 298  * Return
 299  *      -1 if qp <= 0
 300  *       1 if qp >= 0
 301  *       0 if unknown
 302  */
 303 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
 304         __isl_keep isl_qpolynomial *qp)
 305 {
 306         int d;
 307         int i;
 308         int is;
 309         struct isl_upoly_rec *rec;
 310         isl_vec *v;
 311         isl_int l;
 312         enum isl_lp_result res;
 313         int sgn = 0;
 314
 315         is = isl_qpolynomial_is_cst(qp, NULL, NULL);
 316         if (is < 0)
 317                 return 0;
 318         if (is)
 319                 return isl_qpolynomial_cst_sign(qp);
 320
 321         is = isl_qpolynomial_is_affine(qp);
 322         if (is < 0)
 323                 return 0;
 324         if (is)
 325                 return isl_qpolynomial_aff_sign(set, qp);
 326
 327         if (qp->div->n_row > 0)
 328                 return 0;
 329
 330         rec = isl_upoly_as_rec(qp->upoly);
 331         if (!rec)
 332                 return 0;
 333
 334         d = isl_space_dim(qp->dim, isl_dim_all);
 335         v = isl_vec_alloc(set->ctx, 2 + d);
 336         if (!v)
 337                 return 0;
 338
 339         isl_seq_clr(v->el + 1, 1 + d);
 340         isl_int_set_si(v->el[0], 1);
 341         isl_int_set_si(v->el[2 + qp->upoly->var], 1);
 342
 343         isl_int_init(l);
 344
 345         res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
 346         if (res == isl_lp_ok) {
 347                 isl_qpolynomial *min;
 348                 isl_qpolynomial *base;
 349                 isl_qpolynomial *r, *q;
 350                 isl_qpolynomial *t;
 351
 352                 min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l);
 353                 base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim),
 354                                                 qp->upoly->var, 1);
 355
 356                 r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
 357                                           isl_upoly_copy(rec->p[rec->n - 1]));
 358                 q = isl_qpolynomial_copy(r);
 359
 360                 for (i = rec->n - 2; i >= 0; --i) {
 361                         r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
 362                         t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
 363                                                   isl_upoly_copy(rec->p[i]));
 364                         r = isl_qpolynomial_add(r, t);
 365                         if (i == 0)
 366                                 break;
 367                         q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
 368                         q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
 369                 }
 370
 371                 if (isl_qpolynomial_is_zero(q))
 372                         sgn = isl_qpolynomial_sign(set, r);
 373                 else if (isl_qpolynomial_is_zero(r))
 374                         sgn = isl_qpolynomial_sign(set, q);
 375                 else {
 376                         int sgn_q, sgn_r;
 377                         sgn_r = isl_qpolynomial_sign(set, r);
 378                         sgn_q = isl_qpolynomial_sign(set, q);
 379                         if (sgn_r == sgn_q)
 380                                 sgn = sgn_r;
 381                 }
 382
 383                 isl_qpolynomial_free(min);
 384                 isl_qpolynomial_free(base);
 385                 isl_qpolynomial_free(q);
 386                 isl_qpolynomial_free(r);
 387         }
 388
 389         isl_int_clear(l);
 390
 391         isl_vec_free(v);
 392
 393         return sgn;
 394 }
 395
 396 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
 397         __isl_keep isl_set *set,
 398         __isl_take isl_qpolynomial_fold *fold1,
 399         __isl_take isl_qpolynomial_fold *fold2)
 400 {
 401         int i, j;
 402         int n1;
 403         struct isl_qpolynomial_fold *res = NULL;
 404         int better;
 405
 406         if (!fold1 || !fold2)
 407                 goto error;
 408
 409         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 410         isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
 411                         goto error);
 412
 413         better = fold1->type == isl_fold_max ? -1 : 1;
 414
 415         if (isl_qpolynomial_fold_is_empty(fold1)) {
 416                 isl_qpolynomial_fold_free(fold1);
 417                 return fold2;
 418         }
 419
 420         if (isl_qpolynomial_fold_is_empty(fold2)) {
 421                 isl_qpolynomial_fold_free(fold2);
 422                 return fold1;
 423         }
 424
 425         res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
 426                                         fold1->n + fold2->n);
 427         if (!res)
 428                 goto error;
 429
 430         for (i = 0; i < fold1->n; ++i) {
 431                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 432                 if (!res->qp[res->n])
 433                         goto error;
 434                 res->n++;
 435         }
 436         n1 = res->n;
 437
 438         for (i = 0; i < fold2->n; ++i) {
 439                 for (j = n1 - 1; j >= 0; --j) {
 440                         isl_qpolynomial *d;
 441                         int sgn;
 442                         d = isl_qpolynomial_sub(
 443                                 isl_qpolynomial_copy(res->qp[j]),
 444                                 isl_qpolynomial_copy(fold2->qp[i]));
 445                         sgn = isl_qpolynomial_sign(set, d);
 446                         isl_qpolynomial_free(d);
 447                         if (sgn == 0)
 448                                 continue;
 449                         if (sgn != better)
 450                                 break;
 451                         isl_qpolynomial_free(res->qp[j]);
 452                         if (j != n1 - 1)
 453                                 res->qp[j] = res->qp[n1 - 1];
 454                         n1--;
 455                         if (n1 != res->n - 1)
 456                                 res->qp[n1] = res->qp[res->n - 1];
 457                         res->n--;
 458                 }
 459                 if (j >= 0)
 460                         continue;
 461                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 462                 if (!res->qp[res->n])
 463                         goto error;
 464                 res->n++;
 465         }
 466
 467         isl_qpolynomial_fold_free(fold1);
 468         isl_qpolynomial_fold_free(fold2);
 469
 470         return res;
 471 error:
 472         isl_qpolynomial_fold_free(res);
 473         isl_qpolynomial_fold_free(fold1);
 474         isl_qpolynomial_fold_free(fold2);
 475         return NULL;
 476 }
 477
 478 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
 479         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
 480 {
 481         int i;
 482
 483         if (!fold || !qp)
 484                 goto error;
 485
 486         if (isl_qpolynomial_is_zero(qp)) {
 487                 isl_qpolynomial_free(qp);
 488                 return fold;
 489         }
 490
 491         fold = isl_qpolynomial_fold_cow(fold);
 492         if (!fold)
 493                 goto error;
 494
 495         for (i = 0; i < fold->n; ++i) {
 496                 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
 497                                                 isl_qpolynomial_copy(qp));
 498                 if (!fold->qp[i])
 499                         goto error;
 500         }
 501
 502         isl_qpolynomial_free(qp);
 503         return fold;
 504 error:
 505         isl_qpolynomial_fold_free(fold);
 506         isl_qpolynomial_free(qp);
 507         return NULL;
 508 }
 509
 510 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
 511         __isl_keep isl_set *dom,
 512         __isl_take isl_qpolynomial_fold *fold1,
 513         __isl_take isl_qpolynomial_fold *fold2)
 514 {
 515         int i;
 516         isl_qpolynomial_fold *res = NULL;
 517
 518         if (!fold1 || !fold2)
 519                 goto error;
 520
 521         if (isl_qpolynomial_fold_is_empty(fold1)) {
 522                 isl_qpolynomial_fold_free(fold1);
 523                 return fold2;
 524         }
 525
 526         if (isl_qpolynomial_fold_is_empty(fold2)) {
 527                 isl_qpolynomial_fold_free(fold2);
 528                 return fold1;
 529         }
 530
 531         if (fold1->n == 1 && fold2->n != 1)
 532                 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
 533
 534         if (fold2->n == 1) {
 535                 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
 536                                         isl_qpolynomial_copy(fold2->qp[0]));
 537                 isl_qpolynomial_fold_free(fold2);
 538                 return res;
 539         }
 540
 541         res = isl_qpolynomial_fold_add_qpolynomial(
 542                                 isl_qpolynomial_fold_copy(fold1),
 543                                 isl_qpolynomial_copy(fold2->qp[0]));
 544
 545         for (i = 1; i < fold2->n; ++i) {
 546                 isl_qpolynomial_fold *res_i;
 547                 res_i = isl_qpolynomial_fold_add_qpolynomial(
 548                                         isl_qpolynomial_fold_copy(fold1),
 549                                         isl_qpolynomial_copy(fold2->qp[i]));
 550                 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
 551         }
 552
 553         isl_qpolynomial_fold_free(fold1);
 554         isl_qpolynomial_fold_free(fold2);
 555         return res;
 556 error:
 557         isl_qpolynomial_fold_free(res);
 558         isl_qpolynomial_fold_free(fold1);
 559         isl_qpolynomial_fold_free(fold2);
 560         return NULL;
 561 }
 562
 563 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
 564         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
 565 {
 566         int i;
 567
 568         if (!fold || !eq)
 569                 goto error;
 570
 571         fold = isl_qpolynomial_fold_cow(fold);
 572         if (!fold)
 573                 return NULL;
 574
 575         for (i = 0; i < fold->n; ++i) {
 576                 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
 577                                                         isl_basic_set_copy(eq));
 578                 if (!fold->qp[i])
 579                         goto error;
 580         }
 581
 582         isl_basic_set_free(eq);
 583         return fold;
 584 error:
 585         isl_basic_set_free(eq);
 586         isl_qpolynomial_fold_free(fold);
 587         return NULL;
 588 }
 589
 590 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
 591         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
 592 {
 593         int i;
 594
 595         if (!fold || !context)
 596                 goto error;
 597
 598         fold = isl_qpolynomial_fold_cow(fold);
 599         if (!fold)
 600                 return NULL;
 601
 602         for (i = 0; i < fold->n; ++i) {
 603                 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
 604                                                         isl_set_copy(context));
 605                 if (!fold->qp[i])
 606                         goto error;
 607         }
 608
 609         isl_set_free(context);
 610         return fold;
 611 error:
 612         isl_set_free(context);
 613         isl_qpolynomial_fold_free(fold);
 614         return NULL;
 615 }
 616
 617 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
 618         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
 619 {
 620         isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
 621         isl_set *dom_context = isl_set_universe(space);
 622         dom_context = isl_set_intersect_params(dom_context, context);
 623         return isl_qpolynomial_fold_gist(fold, dom_context);
 624 }
 625
 626 #define HAS_TYPE
 627
 628 #undef PW
 629 #define PW isl_pw_qpolynomial_fold
 630 #undef EL
 631 #define EL isl_qpolynomial_fold
 632 #undef EL_IS_ZERO
 633 #define EL_IS_ZERO is_empty
 634 #undef ZERO
 635 #define ZERO zero
 636 #undef IS_ZERO
 637 #define IS_ZERO is_zero
 638 #undef FIELD
 639 #define FIELD fold
 640 #undef DEFAULT_IS_ZERO
 641 #define DEFAULT_IS_ZERO 1
 642
 643 #define NO_NEG
 644 #define NO_PULLBACK
 645
 646 #include <isl_pw_templ.c>
 647
 648 #undef UNION
 649 #define UNION isl_union_pw_qpolynomial_fold
 650 #undef PART
 651 #define PART isl_pw_qpolynomial_fold
 652 #undef PARTS
 653 #define PARTS pw_qpolynomial_fold
 654 #define ALIGN_DOMAIN
 655
 656 #define NO_SUB
 657
 658 #include <isl_union_templ.c>
 659
 660 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
 661         __isl_take isl_space *dim)
 662 {
 663         return qpolynomial_fold_alloc(type, dim, 0);
 664 }
 665
 666 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
 667         enum isl_fold type, __isl_take isl_qpolynomial *qp)
 668 {
 669         isl_qpolynomial_fold *fold;
 670
 671         if (!qp)
 672                 return NULL;
 673
 674         fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1);
 675         if (!fold)
 676                 goto error;
 677
 678         fold->qp[0] = qp;
 679         fold->n++;
 680
 681         return fold;
 682 error:
 683         isl_qpolynomial_fold_free(fold);
 684         isl_qpolynomial_free(qp);
 685         return NULL;
 686 }
 687
 688 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
 689         __isl_keep isl_qpolynomial_fold *fold)
 690 {
 691         if (!fold)
 692                 return NULL;
 693
 694         fold->ref++;
 695         return fold;
 696 }
 697
 698 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
 699         __isl_keep isl_qpolynomial_fold *fold)
 700 {
 701         int i;
 702         isl_qpolynomial_fold *dup;
 703
 704         if (!fold)
 705                 return NULL;
 706         dup = qpolynomial_fold_alloc(fold->type,
 707                                         isl_space_copy(fold->dim), fold->n);
 708         if (!dup)
 709                 return NULL;
 710
 711         dup->n = fold->n;
 712         for (i = 0; i < fold->n; ++i) {
 713                 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
 714                 if (!dup->qp[i])
 715                         goto error;
 716         }
 717
 718         return dup;
 719 error:
 720         isl_qpolynomial_fold_free(dup);
 721         return NULL;
 722 }
 723
 724 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
 725         __isl_take isl_qpolynomial_fold *fold)
 726 {
 727         if (!fold)
 728                 return NULL;
 729
 730         if (fold->ref == 1)
 731                 return fold;
 732         fold->ref--;
 733         return isl_qpolynomial_fold_dup(fold);
 734 }
 735
 736 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
 737 {
 738         int i;
 739
 740         if (!fold)
 741                 return;
 742         if (--fold->ref > 0)
 743                 return;
 744
 745         for (i = 0; i < fold->n; ++i)
 746                 isl_qpolynomial_free(fold->qp[i]);
 747         isl_space_free(fold->dim);
 748         free(fold);
 749 }
 750
 751 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
 752 {
 753         if (!fold)
 754                 return -1;
 755
 756         return fold->n == 0;
 757 }
 758
 759 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
 760         __isl_take isl_qpolynomial_fold *fold1,
 761         __isl_take isl_qpolynomial_fold *fold2)
 762 {
 763         int i;
 764         struct isl_qpolynomial_fold *res = NULL;
 765
 766         if (!fold1 || !fold2)
 767                 goto error;
 768
 769         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 770         isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
 771                         goto error);
 772
 773         if (isl_qpolynomial_fold_is_empty(fold1)) {
 774                 isl_qpolynomial_fold_free(fold1);
 775                 return fold2;
 776         }
 777
 778         if (isl_qpolynomial_fold_is_empty(fold2)) {
 779                 isl_qpolynomial_fold_free(fold2);
 780                 return fold1;
 781         }
 782
 783         res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
 784                                         fold1->n + fold2->n);
 785         if (!res)
 786                 goto error;
 787
 788         for (i = 0; i < fold1->n; ++i) {
 789                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 790                 if (!res->qp[res->n])
 791                         goto error;
 792                 res->n++;
 793         }
 794
 795         for (i = 0; i < fold2->n; ++i) {
 796                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 797                 if (!res->qp[res->n])
 798                         goto error;
 799                 res->n++;
 800         }
 801
 802         isl_qpolynomial_fold_free(fold1);
 803         isl_qpolynomial_fold_free(fold2);
 804
 805         return res;
 806 error:
 807         isl_qpolynomial_fold_free(res);
 808         isl_qpolynomial_fold_free(fold1);
 809         isl_qpolynomial_fold_free(fold2);
 810         return NULL;
 811 }
 812
 813 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
 814         __isl_take isl_pw_qpolynomial_fold *pw1,
 815         __isl_take isl_pw_qpolynomial_fold *pw2)
 816 {
 817         int i, j, n;
 818         struct isl_pw_qpolynomial_fold *res;
 819         isl_set *set;
 820
 821         if (!pw1 || !pw2)
 822                 goto error;
 823
 824         isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
 825
 826         if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
 827                 isl_pw_qpolynomial_fold_free(pw1);
 828                 return pw2;
 829         }
 830
 831         if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
 832                 isl_pw_qpolynomial_fold_free(pw2);
 833                 return pw1;
 834         }
 835
 836         if (pw1->type != pw2->type)
 837                 isl_die(pw1->dim->ctx, isl_error_invalid,
 838                         "fold types don't match", goto error);
 839
 840         n = (pw1->n + 1) * (pw2->n + 1);
 841         res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim),
 842                                                 pw1->type, n);
 843
 844         for (i = 0; i < pw1->n; ++i) {
 845                 set = isl_set_copy(pw1->p[i].set);
 846                 for (j = 0; j < pw2->n; ++j) {
 847                         struct isl_set *common;
 848                         isl_qpolynomial_fold *sum;
 849                         set = isl_set_subtract(set,
 850                                         isl_set_copy(pw2->p[j].set));
 851                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 852                                                 isl_set_copy(pw2->p[j].set));
 853                         if (isl_set_plain_is_empty(common)) {
 854                                 isl_set_free(common);
 855                                 continue;
 856                         }
 857
 858                         sum = isl_qpolynomial_fold_fold_on_domain(common,
 859                                isl_qpolynomial_fold_copy(pw1->p[i].fold),
 860                                isl_qpolynomial_fold_copy(pw2->p[j].fold));
 861
 862                         res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
 863                 }
 864                 res = isl_pw_qpolynomial_fold_add_piece(res, set,
 865                         isl_qpolynomial_fold_copy(pw1->p[i].fold));
 866         }
 867
 868         for (j = 0; j < pw2->n; ++j) {
 869                 set = isl_set_copy(pw2->p[j].set);
 870                 for (i = 0; i < pw1->n; ++i)
 871                         set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
 872                 res = isl_pw_qpolynomial_fold_add_piece(res, set,
 873                                     isl_qpolynomial_fold_copy(pw2->p[j].fold));
 874         }
 875
 876         isl_pw_qpolynomial_fold_free(pw1);
 877         isl_pw_qpolynomial_fold_free(pw2);
 878
 879         return res;
 880 error:
 881         isl_pw_qpolynomial_fold_free(pw1);
 882         isl_pw_qpolynomial_fold_free(pw2);
 883         return NULL;
 884 }
 885
 886 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 887         __isl_take isl_union_pw_qpolynomial_fold *u,
 888         __isl_take isl_pw_qpolynomial_fold *part)
 889 {
 890         uint32_t hash;
 891         struct isl_hash_table_entry *entry;
 892
 893         u = isl_union_pw_qpolynomial_fold_cow(u);
 894
 895         if (!part || !u)
 896                 goto error;
 897
 898         isl_assert(u->dim->ctx, isl_space_match(part->dim, isl_dim_param, u->dim,
 899                                               isl_dim_param), goto error);
 900
 901         hash = isl_space_get_hash(part->dim);
 902         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 903                                     &has_dim, part->dim, 1);
 904         if (!entry)
 905                 goto error;
 906
 907         if (!entry->data)
 908                 entry->data = part;
 909         else {
 910                 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
 911                                             isl_pw_qpolynomial_fold_copy(part));
 912                 if (!entry->data)
 913                         goto error;
 914                 isl_pw_qpolynomial_fold_free(part);
 915         }
 916
 917         return u;
 918 error:
 919         isl_pw_qpolynomial_fold_free(part);
 920         isl_union_pw_qpolynomial_fold_free(u);
 921         return NULL;
 922 }
 923
 924 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
 925 {
 926         isl_union_pw_qpolynomial_fold **u;
 927         u = (isl_union_pw_qpolynomial_fold **)user;
 928
 929         *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
 930
 931         return 0;
 932 }
 933
 934 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
 935         __isl_take isl_union_pw_qpolynomial_fold *u1,
 936         __isl_take isl_union_pw_qpolynomial_fold *u2)
 937 {
 938         u1 = isl_union_pw_qpolynomial_fold_cow(u1);
 939
 940         if (!u1 || !u2)
 941                 goto error;
 942
 943         if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
 944                                                         &fold_part, &u1) < 0)
 945                 goto error;
 946
 947         isl_union_pw_qpolynomial_fold_free(u2);
 948
 949         return u1;
 950 error:
 951         isl_union_pw_qpolynomial_fold_free(u1);
 952         isl_union_pw_qpolynomial_fold_free(u2);
 953         return NULL;
 954 }
 955
 956 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
 957         enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
 958 {
 959         int i;
 960         isl_pw_qpolynomial_fold *pwf;
 961
 962         if (!pwqp)
 963                 return NULL;
 964
 965         pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim),
 966                                                 type, pwqp->n);
 967
 968         for (i = 0; i < pwqp->n; ++i)
 969                 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
 970                         isl_set_copy(pwqp->p[i].set),
 971                         isl_qpolynomial_fold_alloc(type,
 972                                 isl_qpolynomial_copy(pwqp->p[i].qp)));
 973
 974         isl_pw_qpolynomial_free(pwqp);
 975
 976         return pwf;
 977 }
 978
 979 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
 980         __isl_take isl_pw_qpolynomial_fold *pwf1,
 981         __isl_take isl_pw_qpolynomial_fold *pwf2)
 982 {
 983         return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2);
 984 }
 985
 986 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
 987         __isl_keep isl_qpolynomial_fold *fold2)
 988 {
 989         int i;
 990
 991         if (!fold1 || !fold2)
 992                 return -1;
 993
 994         if (fold1->n != fold2->n)
 995                 return 0;
 996
 997         /* We probably want to sort the qps first... */
 998         for (i = 0; i < fold1->n; ++i) {
 999                 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
1000                 if (eq < 0 || !eq)
1001                         return eq;
1002         }
1003
1004         return 1;
1005 }
1006
1007 __isl_give isl_val *isl_qpolynomial_fold_eval(
1008         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
1009 {
1010         isl_ctx *ctx;
1011         isl_val *v;
1012
1013         if (!fold || !pnt)
1014                 goto error;
1015         ctx = isl_point_get_ctx(pnt);
1016         isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
1017         isl_assert(pnt->dim->ctx,
1018                 fold->type == isl_fold_max || fold->type == isl_fold_min,
1019                 goto error);
1020
1021         if (fold->n == 0)
1022                 v = isl_val_zero(ctx);
1023         else {
1024                 int i;
1025                 v = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
1026                                                 isl_point_copy(pnt));
1027                 for (i = 1; i < fold->n; ++i) {
1028                         isl_val *v_i;
1029                         v_i = isl_qpolynomial_eval(
1030                                             isl_qpolynomial_copy(fold->qp[i]),
1031                                             isl_point_copy(pnt));
1032                         if (fold->type == isl_fold_max)
1033                                 v = isl_val_max(v, v_i);
1034                         else
1035                                 v = isl_val_min(v, v_i);
1036                 }
1037         }
1038         isl_qpolynomial_fold_free(fold);
1039         isl_point_free(pnt);
1040
1041         return v;
1042 error:
1043         isl_qpolynomial_fold_free(fold);
1044         isl_point_free(pnt);
1045         return NULL;
1046 }
1047
1048 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
1049 {
1050         int i;
1051         size_t n = 0;
1052
1053         for (i = 0; i < pwf->n; ++i)
1054                 n += pwf->p[i].fold->n;
1055
1056         return n;
1057 }
1058
1059 __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain(
1060         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1061 {
1062         int i;
1063         isl_val *opt;
1064
1065         if (!set || !fold)
1066                 goto error;
1067
1068         if (fold->n == 0) {
1069                 opt = isl_val_zero(isl_set_get_ctx(set));
1070                 isl_set_free(set);
1071                 isl_qpolynomial_fold_free(fold);
1072                 return opt;
1073         }
1074
1075         opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1076                                                 isl_set_copy(set), max);
1077         for (i = 1; i < fold->n; ++i) {
1078                 isl_val *opt_i;
1079                 opt_i = isl_qpolynomial_opt_on_domain(
1080                                 isl_qpolynomial_copy(fold->qp[i]),
1081                                 isl_set_copy(set), max);
1082                 if (max)
1083                         opt = isl_val_max(opt, opt_i);
1084                 else
1085                         opt = isl_val_min(opt, opt_i);
1086         }
1087
1088         isl_set_free(set);
1089         isl_qpolynomial_fold_free(fold);
1090
1091         return opt;
1092 error:
1093         isl_set_free(set);
1094         isl_qpolynomial_fold_free(fold);
1095         return NULL;
1096 }
1097
1098 /* Check whether for each quasi-polynomial in "fold2" there is
1099  * a quasi-polynomial in "fold1" that dominates it on "set".
1100  */
1101 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1102         __isl_keep isl_qpolynomial_fold *fold1,
1103         __isl_keep isl_qpolynomial_fold *fold2)
1104 {
1105         int i, j;
1106         int covers;
1107
1108         if (!set || !fold1 || !fold2)
1109                 return -1;
1110
1111         covers = fold1->type == isl_fold_max ? 1 : -1;
1112
1113         for (i = 0; i < fold2->n; ++i) {
1114                 for (j = 0; j < fold1->n; ++j) {
1115                         isl_qpolynomial *d;
1116                         int sgn;
1117
1118                         d = isl_qpolynomial_sub(
1119                                 isl_qpolynomial_copy(fold1->qp[j]),
1120                                 isl_qpolynomial_copy(fold2->qp[i]));
1121                         sgn = isl_qpolynomial_sign(set, d);
1122                         isl_qpolynomial_free(d);
1123                         if (sgn == covers)
1124                                 break;
1125                 }
1126                 if (j >= fold1->n)
1127                         return 0;
1128         }
1129
1130         return 1;
1131 }
1132
1133 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1134  * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1135  * that of pwf2.
1136  */
1137 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1138         __isl_keep isl_pw_qpolynomial_fold *pwf2)
1139 {
1140         int i, j;
1141         isl_set *dom1, *dom2;
1142         int is_subset;
1143
1144         if (!pwf1 || !pwf2)
1145                 return -1;
1146
1147         if (pwf2->n == 0)
1148                 return 1;
1149         if (pwf1->n == 0)
1150                 return 0;
1151
1152         dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1153         dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1154         is_subset = isl_set_is_subset(dom2, dom1);
1155         isl_set_free(dom1);
1156         isl_set_free(dom2);
1157
1158         if (is_subset < 0 || !is_subset)
1159                 return is_subset;
1160
1161         for (i = 0; i < pwf2->n; ++i) {
1162                 for (j = 0; j < pwf1->n; ++j) {
1163                         int is_empty;
1164                         isl_set *common;
1165                         int covers;
1166
1167                         common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1168                                                    isl_set_copy(pwf2->p[i].set));
1169                         is_empty = isl_set_is_empty(common);
1170                         if (is_empty < 0 || is_empty) {
1171                                 isl_set_free(common);
1172                                 if (is_empty < 0)
1173                                         return -1;
1174                                 continue;
1175                         }
1176                         covers = qpolynomial_fold_covers_on_domain(common,
1177                                         pwf1->p[j].fold, pwf2->p[i].fold);
1178                         isl_set_free(common);
1179                         if (covers < 0 || !covers)
1180                                 return covers;
1181                 }
1182         }
1183
1184         return 1;
1185 }
1186
1187 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain(
1188         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1189 {
1190         int i;
1191         isl_ctx *ctx;
1192
1193         if (!fold || !morph)
1194                 goto error;
1195
1196         ctx = fold->dim->ctx;
1197         isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error);
1198
1199         fold = isl_qpolynomial_fold_cow(fold);
1200         if (!fold)
1201                 goto error;
1202
1203         isl_space_free(fold->dim);
1204         fold->dim = isl_space_copy(morph->ran->dim);
1205         if (!fold->dim)
1206                 goto error;
1207
1208         for (i = 0; i < fold->n; ++i) {
1209                 fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i],
1210                                                 isl_morph_copy(morph));
1211                 if (!fold->qp[i])
1212                         goto error;
1213         }
1214
1215         isl_morph_free(morph);
1216
1217         return fold;
1218 error:
1219         isl_qpolynomial_fold_free(fold);
1220         isl_morph_free(morph);
1221         return NULL;
1222 }
1223
1224 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1225 {
1226         if (!fold)
1227                 return isl_fold_list;
1228         return fold->type;
1229 }
1230
1231 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1232         __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1233 {
1234         if (!upwf)
1235                 return isl_fold_list;
1236         return upwf->type;
1237 }
1238
1239 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1240         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
1241 {
1242         int i;
1243
1244         if (!fold || !dim)
1245                 goto error;
1246
1247         if (isl_space_is_equal(fold->dim, dim)) {
1248                 isl_space_free(dim);
1249                 return fold;
1250         }
1251
1252         fold = isl_qpolynomial_fold_cow(fold);
1253         if (!fold)
1254                 goto error;
1255
1256         isl_space_free(fold->dim);
1257         fold->dim = isl_space_copy(dim);
1258         if (!fold->dim)
1259                 goto error;
1260
1261         for (i = 0; i < fold->n; ++i) {
1262                 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1263                                                 isl_space_copy(dim));
1264                 if (!fold->qp[i])
1265                         goto error;
1266         }
1267
1268         isl_space_free(dim);
1269
1270         return fold;
1271 error:
1272         isl_qpolynomial_fold_free(fold);
1273         isl_space_free(dim);
1274         return NULL;
1275 }
1276
1277 int isl_qpolynomial_fold_foreach_qpolynomial(
1278         __isl_keep isl_qpolynomial_fold *fold,
1279         int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1280 {
1281         int i;
1282
1283         if (!fold)
1284                 return -1;
1285
1286         for (i = 0; i < fold->n; ++i)
1287                 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1288                         return -1;
1289
1290         return 0;
1291 }
1292
1293 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1294         __isl_take isl_qpolynomial_fold *fold,
1295         enum isl_dim_type dst_type, unsigned dst_pos,
1296         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1297 {
1298         int i;
1299
1300         if (n == 0)
1301                 return fold;
1302
1303         fold = isl_qpolynomial_fold_cow(fold);
1304         if (!fold)
1305                 return NULL;
1306
1307         fold->dim = isl_space_move_dims(fold->dim, dst_type, dst_pos,
1308                                                 src_type, src_pos, n);
1309         if (!fold->dim)
1310                 goto error;
1311
1312         for (i = 0; i < fold->n; ++i) {
1313                 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1314                                 dst_type, dst_pos, src_type, src_pos, n);
1315                 if (!fold->qp[i])
1316                         goto error;
1317         }
1318
1319         return fold;
1320 error:
1321         isl_qpolynomial_fold_free(fold);
1322         return NULL;
1323 }
1324
1325 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1326  * in fold->qp[k] by subs[i].
1327  */
1328 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1329         __isl_take isl_qpolynomial_fold *fold,
1330         enum isl_dim_type type, unsigned first, unsigned n,
1331         __isl_keep isl_qpolynomial **subs)
1332 {
1333         int i;
1334
1335         if (n == 0)
1336                 return fold;
1337
1338         fold = isl_qpolynomial_fold_cow(fold);
1339         if (!fold)
1340                 return NULL;
1341
1342         for (i = 0; i < fold->n; ++i) {
1343                 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1344                                 type, first, n, subs);
1345                 if (!fold->qp[i])
1346                         goto error;
1347         }
1348
1349         return fold;
1350 error:
1351         isl_qpolynomial_fold_free(fold);
1352         return NULL;
1353 }
1354
1355 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1356 {
1357         isl_ctx *ctx;
1358         isl_pw_qpolynomial_fold *pwf;
1359         isl_union_pw_qpolynomial_fold **upwf;
1360         uint32_t hash;
1361         struct isl_hash_table_entry *entry;
1362
1363         upwf = (isl_union_pw_qpolynomial_fold **)user;
1364
1365         ctx = pwqp->dim->ctx;
1366         hash = isl_space_get_hash(pwqp->dim);
1367         entry = isl_hash_table_find(ctx, &(*upwf)->table,
1368                                      hash, &has_dim, pwqp->dim, 1);
1369         if (!entry)
1370                 goto error;
1371
1372         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1373         if (!entry->data)
1374                 entry->data = pwf;
1375         else {
1376                 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1377                 if (!entry->data)
1378                         return -1;
1379                 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) {
1380                         isl_pw_qpolynomial_fold_free(entry->data);
1381                         isl_hash_table_remove(ctx, &(*upwf)->table, entry);
1382                 }
1383         }
1384
1385         return 0;
1386 error:
1387         isl_pw_qpolynomial_free(pwqp);
1388         return -1;
1389 }
1390
1391 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1392         __isl_take isl_union_pw_qpolynomial_fold *upwf,
1393         __isl_take isl_union_pw_qpolynomial *upwqp)
1394 {
1395         upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1396                                 isl_union_pw_qpolynomial_get_space(upwqp));
1397         upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1398                                 isl_union_pw_qpolynomial_fold_get_space(upwf));
1399
1400         upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1401         if (!upwf || !upwqp)
1402                 goto error;
1403
1404         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1405                                                          &upwf) < 0)
1406                 goto error;
1407
1408         isl_union_pw_qpolynomial_free(upwqp);
1409
1410         return upwf;
1411 error:
1412         isl_union_pw_qpolynomial_fold_free(upwf);
1413         isl_union_pw_qpolynomial_free(upwqp);
1414         return NULL;
1415 }
1416
1417 static int join_compatible(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1418 {
1419         int m;
1420         m = isl_space_match(dim1, isl_dim_param, dim2, isl_dim_param);
1421         if (m < 0 || !m)
1422                 return m;
1423         return isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_in);
1424 }
1425
1426 /* Compute the intersection of the range of the map and the domain
1427  * of the piecewise quasipolynomial reduction and then compute a bound
1428  * on the associated quasipolynomial reduction over all elements
1429  * in this intersection.
1430  *
1431  * We first introduce some unconstrained dimensions in the
1432  * piecewise quasipolynomial, intersect the resulting domain
1433  * with the wrapped map and the compute the sum.
1434  */
1435 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1436         __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1437         int *tight)
1438 {
1439         isl_ctx *ctx;
1440         isl_set *dom;
1441         isl_space *map_dim;
1442         isl_space *pwf_dim;
1443         unsigned n_in;
1444         int ok;
1445
1446         ctx = isl_map_get_ctx(map);
1447         if (!ctx)
1448                 goto error;
1449
1450         map_dim = isl_map_get_space(map);
1451         pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1452         ok = join_compatible(map_dim, pwf_dim);
1453         isl_space_free(map_dim);
1454         isl_space_free(pwf_dim);
1455         if (!ok)
1456                 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1457                         goto error);
1458
1459         n_in = isl_map_dim(map, isl_dim_in);
1460         pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in);
1461
1462         dom = isl_map_wrap(map);
1463         pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf,
1464                                                 isl_set_get_space(dom));
1465
1466         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1467         pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1468
1469         return pwf;
1470 error:
1471         isl_map_free(map);
1472         isl_pw_qpolynomial_fold_free(pwf);
1473         return NULL;
1474 }
1475
1476 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1477         __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1478         int *tight)
1479 {
1480         return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight);
1481 }
1482
1483 struct isl_apply_fold_data {
1484         isl_union_pw_qpolynomial_fold *upwf;
1485         isl_union_pw_qpolynomial_fold *res;
1486         isl_map *map;
1487         int tight;
1488 };
1489
1490 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1491         void *user)
1492 {
1493         isl_space *map_dim;
1494         isl_space *pwf_dim;
1495         struct isl_apply_fold_data *data = user;
1496         int ok;
1497
1498         map_dim = isl_map_get_space(data->map);
1499         pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1500         ok = join_compatible(map_dim, pwf_dim);
1501         isl_space_free(map_dim);
1502         isl_space_free(pwf_dim);
1503
1504         if (ok) {
1505                 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1506                                     pwf, data->tight ? &data->tight : NULL);
1507                 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1508                                                         data->res, pwf);
1509         } else
1510                 isl_pw_qpolynomial_fold_free(pwf);
1511
1512         return 0;
1513 }
1514
1515 static int map_apply(__isl_take isl_map *map, void *user)
1516 {
1517         struct isl_apply_fold_data *data = user;
1518         int r;
1519
1520         data->map = map;
1521         r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1522                                 data->upwf, &pw_qpolynomial_fold_apply, data);
1523
1524         isl_map_free(map);
1525         return r;
1526 }
1527
1528 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1529         __isl_take isl_union_map *umap,
1530         __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1531 {
1532         isl_space *dim;
1533         enum isl_fold type;
1534         struct isl_apply_fold_data data;
1535
1536         upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1537                                 isl_union_map_get_space(umap));
1538         umap = isl_union_map_align_params(umap,
1539                                 isl_union_pw_qpolynomial_fold_get_space(upwf));
1540
1541         data.upwf = upwf;
1542         data.tight = tight ? 1 : 0;
1543         dim = isl_union_pw_qpolynomial_fold_get_space(upwf);
1544         type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1545         data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1546         if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1547                 goto error;
1548
1549         isl_union_map_free(umap);
1550         isl_union_pw_qpolynomial_fold_free(upwf);
1551
1552         if (tight)
1553                 *tight = data.tight;
1554
1555         return data.res;
1556 error:
1557         isl_union_map_free(umap);
1558         isl_union_pw_qpolynomial_fold_free(upwf);
1559         isl_union_pw_qpolynomial_fold_free(data.res);
1560         return NULL;
1561 }
1562
1563 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
1564         __isl_take isl_union_set *uset,
1565         __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1566 {
1567         return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight);
1568 }
1569
1570 /* Reorder the dimension of "fold" according to the given reordering.
1571  */
1572 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
1573         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1574 {
1575         int i;
1576
1577         fold = isl_qpolynomial_fold_cow(fold);
1578         if (!fold || !r)
1579                 goto error;
1580
1581         for (i = 0; i < fold->n; ++i) {
1582                 fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i],
1583                                                     isl_reordering_copy(r));
1584                 if (!fold->qp[i])
1585                         goto error;
1586         }
1587
1588         fold = isl_qpolynomial_fold_reset_domain_space(fold,
1589                                                     isl_space_copy(r->dim));
1590
1591         isl_reordering_free(r);
1592
1593         return fold;
1594 error:
1595         isl_qpolynomial_fold_free(fold);
1596         isl_reordering_free(r);
1597         return NULL;
1598 }
1599
1600 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
1601         __isl_take isl_qpolynomial_fold *fold, isl_int v)
1602 {
1603         int i;
1604
1605         if (isl_int_is_one(v))
1606                 return fold;
1607         if (fold && isl_int_is_zero(v)) {
1608                 isl_qpolynomial_fold *zero;
1609                 isl_space *dim = isl_space_copy(fold->dim);
1610                 zero = isl_qpolynomial_fold_empty(fold->type, dim);
1611                 isl_qpolynomial_fold_free(fold);
1612                 return zero;
1613         }
1614
1615         fold = isl_qpolynomial_fold_cow(fold);
1616         if (!fold)
1617                 return NULL;
1618
1619         if (isl_int_is_neg(v))
1620                 fold->type = isl_fold_type_negate(fold->type);
1621         for (i = 0; i < fold->n; ++i) {
1622                 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1623                 if (!fold->qp[i])
1624                         goto error;
1625         }
1626
1627         return fold;
1628 error:
1629         isl_qpolynomial_fold_free(fold);
1630         return NULL;
1631 }
1632
1633 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
1634         __isl_take isl_qpolynomial_fold *fold, isl_int v)
1635 {
1636         return isl_qpolynomial_fold_mul_isl_int(fold, v);
1637 }
1638
1639 /* Multiply "fold" by "v".
1640  */
1641 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val(
1642         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
1643 {
1644         int i;
1645
1646         if (!fold || !v)
1647                 goto error;
1648
1649         if (isl_val_is_one(v)) {
1650                 isl_val_free(v);
1651                 return fold;
1652         }
1653         if (isl_val_is_zero(v)) {
1654                 isl_qpolynomial_fold *zero;
1655                 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
1656                 zero = isl_qpolynomial_fold_empty(fold->type, space);
1657                 isl_qpolynomial_fold_free(fold);
1658                 isl_val_free(v);
1659                 return zero;
1660         }
1661         if (!isl_val_is_rat(v))
1662                 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
1663                         "expecting rational factor", goto error);
1664
1665         fold = isl_qpolynomial_fold_cow(fold);
1666         if (!fold)
1667                 goto error;
1668
1669         if (isl_val_is_neg(v))
1670                 fold->type = isl_fold_type_negate(fold->type);
1671         for (i = 0; i < fold->n; ++i) {
1672                 fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i],
1673                                                         isl_val_copy(v));
1674                 if (!fold->qp[i])
1675                         goto error;
1676         }
1677
1678         isl_val_free(v);
1679         return fold;
1680 error:
1681         isl_val_free(v);
1682         isl_qpolynomial_fold_free(fold);
1683         return NULL;
1684 }