isl_pw_templ.c

   1 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
   2 #define FN(TYPE,NAME) xFN(TYPE,NAME)
   3 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
   4 #define S(TYPE,NAME) xS(TYPE,NAME)
   5
   6 #ifdef HAS_TYPE
   7 static __isl_give PW *FN(PW,alloc_)(__isl_take isl_dim *dim,
   8         enum isl_fold type, int n)
   9 #else
  10 static __isl_give PW *FN(PW,alloc_)(__isl_take isl_dim *dim, int n)
  11 #endif
  12 {
  13         isl_ctx *ctx;
  14         struct PW *pw;
  15
  16         if (!dim)
  17                 return NULL;
  18         ctx = isl_dim_get_ctx(dim);
  19         isl_assert(ctx, n >= 0, goto error);
  20         pw = isl_alloc(ctx, struct PW,
  21                         sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
  22         if (!pw)
  23                 goto error;
  24
  25         pw->ref = 1;
  26 #ifdef HAS_TYPE
  27         pw->type = type;
  28 #endif
  29         pw->size = n;
  30         pw->n = 0;
  31         pw->dim = dim;
  32         return pw;
  33 error:
  34         isl_dim_free(dim);
  35         return NULL;
  36 }
  37
  38 #ifdef HAS_TYPE
  39 __isl_give PW *FN(PW,zero)(__isl_take isl_dim *dim, enum isl_fold type)
  40 {
  41         return FN(PW,alloc_)(dim, type, 0);
  42 }
  43 #else
  44 __isl_give PW *FN(PW,zero)(__isl_take isl_dim *dim)
  45 {
  46         return FN(PW,alloc_)(dim, 0);
  47 }
  48 #endif
  49
  50 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
  51         __isl_take isl_set *set, __isl_take EL *el)
  52 {
  53         isl_ctx *ctx;
  54         isl_dim *el_dim = NULL;
  55
  56         if (!pw || !set || !el)
  57                 goto error;
  58
  59         if (isl_set_plain_is_empty(set) || FN(EL,IS_ZERO)(el)) {
  60                 isl_set_free(set);
  61                 FN(EL,free)(el);
  62                 return pw;
  63         }
  64
  65         ctx = isl_set_get_ctx(set);
  66 #ifdef HAS_TYPE
  67         if (pw->type != el->type)
  68                 isl_die(ctx, isl_error_invalid, "fold types don't match",
  69                         goto error);
  70 #endif
  71         el_dim = FN(EL,get_dim(el));
  72         isl_assert(ctx, isl_dim_equal(pw->dim, el_dim), goto error);
  73         isl_assert(ctx, pw->n < pw->size, goto error);
  74
  75         pw->p[pw->n].set = set;
  76         pw->p[pw->n].FIELD = el;
  77         pw->n++;
  78
  79         isl_dim_free(el_dim);
  80         return pw;
  81 error:
  82         isl_dim_free(el_dim);
  83         FN(PW,free)(pw);
  84         isl_set_free(set);
  85         FN(EL,free)(el);
  86         return NULL;
  87 }
  88
  89 #ifdef HAS_TYPE
  90 __isl_give PW *FN(PW,alloc)(enum isl_fold type,
  91         __isl_take isl_set *set, __isl_take EL *el)
  92 #else
  93 __isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el)
  94 #endif
  95 {
  96         PW *pw;
  97
  98         if (!set || !el)
  99                 goto error;
 100
 101 #ifdef HAS_TYPE
 102         pw = FN(PW,alloc_)(isl_set_get_dim(set), type, 1);
 103 #else
 104         pw = FN(PW,alloc_)(isl_set_get_dim(set), 1);
 105 #endif
 106
 107         return FN(PW,add_piece)(pw, set, el);
 108 error:
 109         isl_set_free(set);
 110         FN(EL,free)(el);
 111         return NULL;
 112 }
 113
 114 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
 115 {
 116         int i;
 117         PW *dup;
 118
 119         if (!pw)
 120                 return NULL;
 121
 122 #ifdef HAS_TYPE
 123         dup = FN(PW,alloc_)(isl_dim_copy(pw->dim), pw->type, pw->n);
 124 #else
 125         dup = FN(PW,alloc_)(isl_dim_copy(pw->dim), pw->n);
 126 #endif
 127         if (!dup)
 128                 return NULL;
 129
 130         for (i = 0; i < pw->n; ++i)
 131                 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set),
 132                                             FN(EL,copy)(pw->p[i].FIELD));
 133
 134         return dup;
 135 }
 136
 137 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
 138 {
 139         if (!pw)
 140                 return NULL;
 141
 142         if (pw->ref == 1)
 143                 return pw;
 144         pw->ref--;
 145         return FN(PW,dup)(pw);
 146 }
 147
 148 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
 149 {
 150         if (!pw)
 151                 return NULL;
 152
 153         pw->ref++;
 154         return pw;
 155 }
 156
 157 void FN(PW,free)(__isl_take PW *pw)
 158 {
 159         int i;
 160
 161         if (!pw)
 162                 return;
 163         if (--pw->ref > 0)
 164                 return;
 165
 166         for (i = 0; i < pw->n; ++i) {
 167                 isl_set_free(pw->p[i].set);
 168                 FN(EL,free)(pw->p[i].FIELD);
 169         }
 170         isl_dim_free(pw->dim);
 171         free(pw);
 172 }
 173
 174 int FN(PW,is_zero)(__isl_keep PW *pw)
 175 {
 176         if (!pw)
 177                 return -1;
 178
 179         return pw->n == 0;
 180 }
 181
 182 __isl_give PW *FN(PW,add)(__isl_take PW *pw1, __isl_take PW *pw2)
 183 {
 184         int i, j, n;
 185         struct PW *res;
 186         isl_ctx *ctx;
 187         isl_set *set;
 188
 189         if (!pw1 || !pw2)
 190                 goto error;
 191
 192         ctx = isl_dim_get_ctx(pw1->dim);
 193 #ifdef HAS_TYPE
 194         if (pw1->type != pw2->type)
 195                 isl_die(ctx, isl_error_invalid,
 196                         "fold types don't match", goto error);
 197 #endif
 198         isl_assert(ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 199
 200         if (FN(PW,is_zero)(pw1)) {
 201                 FN(PW,free)(pw1);
 202                 return pw2;
 203         }
 204
 205         if (FN(PW,is_zero)(pw2)) {
 206                 FN(PW,free)(pw2);
 207                 return pw1;
 208         }
 209
 210         n = (pw1->n + 1) * (pw2->n + 1);
 211 #ifdef HAS_TYPE
 212         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->type, n);
 213 #else
 214         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), n);
 215 #endif
 216
 217         for (i = 0; i < pw1->n; ++i) {
 218                 set = isl_set_copy(pw1->p[i].set);
 219                 for (j = 0; j < pw2->n; ++j) {
 220                         struct isl_set *common;
 221                         EL *sum;
 222                         set = isl_set_subtract(set,
 223                                         isl_set_copy(pw2->p[j].set));
 224                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 225                                                 isl_set_copy(pw2->p[j].set));
 226                         if (isl_set_plain_is_empty(common)) {
 227                                 isl_set_free(common);
 228                                 continue;
 229                         }
 230
 231                         sum = FN(EL,add_on_domain)(common,
 232                                                    FN(EL,copy)(pw1->p[i].FIELD),
 233                                                    FN(EL,copy)(pw2->p[j].FIELD));
 234
 235                         res = FN(PW,add_piece)(res, common, sum);
 236                 }
 237                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
 238         }
 239
 240         for (j = 0; j < pw2->n; ++j) {
 241                 set = isl_set_copy(pw2->p[j].set);
 242                 for (i = 0; i < pw1->n; ++i)
 243                         set = isl_set_subtract(set,
 244                                         isl_set_copy(pw1->p[i].set));
 245                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
 246         }
 247
 248         FN(PW,free)(pw1);
 249         FN(PW,free)(pw2);
 250
 251         return res;
 252 error:
 253         FN(PW,free)(pw1);
 254         FN(PW,free)(pw2);
 255         return NULL;
 256 }
 257
 258 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
 259 {
 260         int i;
 261         isl_ctx *ctx;
 262         PW *res;
 263
 264         if (!pw1 || !pw2)
 265                 goto error;
 266
 267         ctx = isl_dim_get_ctx(pw1->dim);
 268 #ifdef HAS_TYPE
 269         if (pw1->type != pw2->type)
 270                 isl_die(ctx, isl_error_invalid,
 271                         "fold types don't match", goto error);
 272 #endif
 273         isl_assert(ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 274
 275         if (FN(PW,is_zero)(pw1)) {
 276                 FN(PW,free)(pw1);
 277                 return pw2;
 278         }
 279
 280         if (FN(PW,is_zero)(pw2)) {
 281                 FN(PW,free)(pw2);
 282                 return pw1;
 283         }
 284
 285 #ifdef HAS_TYPE
 286         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->type, pw1->n + pw2->n);
 287 #else
 288         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->n + pw2->n);
 289 #endif
 290
 291         for (i = 0; i < pw1->n; ++i)
 292                 res = FN(PW,add_piece)(res,
 293                                 isl_set_copy(pw1->p[i].set),
 294                                 FN(EL,copy)(pw1->p[i].FIELD));
 295
 296         for (i = 0; i < pw2->n; ++i)
 297                 res = FN(PW,add_piece)(res,
 298                                 isl_set_copy(pw2->p[i].set),
 299                                 FN(EL,copy)(pw2->p[i].FIELD));
 300
 301         FN(PW,free)(pw1);
 302         FN(PW,free)(pw2);
 303
 304         return res;
 305 error:
 306         FN(PW,free)(pw1);
 307         FN(PW,free)(pw2);
 308         return NULL;
 309 }
 310
 311 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
 312         __isl_take isl_point *pnt)
 313 {
 314         int i;
 315         int found = 0;
 316         isl_ctx *ctx;
 317         isl_dim *pnt_dim = NULL;
 318         isl_qpolynomial *qp;
 319
 320         if (!pw || !pnt)
 321                 goto error;
 322         ctx = isl_point_get_ctx(pnt);
 323         pnt_dim = isl_point_get_dim(pnt);
 324         isl_assert(ctx, isl_dim_equal(pnt_dim, pw->dim), goto error);
 325
 326         for (i = 0; i < pw->n; ++i) {
 327                 found = isl_set_contains_point(pw->p[i].set, pnt);
 328                 if (found < 0)
 329                         goto error;
 330                 if (found)
 331                         break;
 332         }
 333         if (found)
 334                 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
 335                                             isl_point_copy(pnt));
 336         else
 337                 qp = isl_qpolynomial_zero(isl_dim_copy(pw->dim));
 338         FN(PW,free)(pw);
 339         isl_dim_free(pnt_dim);
 340         isl_point_free(pnt);
 341         return qp;
 342 error:
 343         FN(PW,free)(pw);
 344         isl_dim_free(pnt_dim);
 345         isl_point_free(pnt);
 346         return NULL;
 347 }
 348
 349 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
 350 {
 351         int i;
 352         isl_set *dom;
 353
 354         if (!pw)
 355                 return NULL;
 356
 357         dom = isl_set_empty(isl_dim_copy(pw->dim));
 358         for (i = 0; i < pw->n; ++i)
 359                 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
 360
 361         FN(PW,free)(pw);
 362
 363         return dom;
 364 }
 365
 366 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw, __isl_take isl_set *set)
 367 {
 368         int i;
 369
 370         if (!pw || !set)
 371                 goto error;
 372
 373         if (pw->n == 0) {
 374                 isl_set_free(set);
 375                 return pw;
 376         }
 377
 378         pw = FN(PW,cow)(pw);
 379         if (!pw)
 380                 goto error;
 381
 382         for (i = pw->n - 1; i >= 0; --i) {
 383                 isl_basic_set *aff;
 384                 pw->p[i].set = isl_set_intersect(pw->p[i].set, isl_set_copy(set));
 385                 if (!pw->p[i].set)
 386                         goto error;
 387                 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
 388                 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
 389                                                                 aff);
 390                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 391                         isl_set_free(pw->p[i].set);
 392                         FN(EL,free)(pw->p[i].FIELD);
 393                         if (i != pw->n - 1)
 394                                 pw->p[i] = pw->p[pw->n - 1];
 395                         pw->n--;
 396                 }
 397         }
 398
 399         isl_set_free(set);
 400         return pw;
 401 error:
 402         isl_set_free(set);
 403         FN(PW,free)(pw);
 404         return NULL;
 405 }
 406
 407 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
 408 {
 409         int i;
 410         isl_basic_set *hull = NULL;
 411
 412         if (!pw || !context)
 413                 goto error;
 414
 415         if (pw->n == 0) {
 416                 isl_set_free(context);
 417                 return pw;
 418         }
 419
 420         context = isl_set_compute_divs(context);
 421         hull = isl_set_simple_hull(isl_set_copy(context));
 422
 423         pw = FN(PW,cow)(pw);
 424         if (!pw)
 425                 goto error;
 426
 427         for (i = pw->n - 1; i >= 0; --i) {
 428                 pw->p[i].set = isl_set_intersect(pw->p[i].set,
 429                                                  isl_set_copy(context));
 430                 if (!pw->p[i].set)
 431                         goto error;
 432                 pw->p[i].FIELD = FN(EL,gist)(pw->p[i].FIELD,
 433                                              isl_set_copy(pw->p[i].set));
 434                 pw->p[i].set = isl_set_gist_basic_set(pw->p[i].set,
 435                                                 isl_basic_set_copy(hull));
 436                 if (!pw->p[i].set)
 437                         goto error;
 438                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 439                         isl_set_free(pw->p[i].set);
 440                         FN(EL,free)(pw->p[i].FIELD);
 441                         if (i != pw->n - 1)
 442                                 pw->p[i] = pw->p[pw->n - 1];
 443                         pw->n--;
 444                 }
 445         }
 446
 447         isl_basic_set_free(hull);
 448         isl_set_free(context);
 449
 450         return pw;
 451 error:
 452         FN(PW,free)(pw);
 453         isl_basic_set_free(hull);
 454         isl_set_free(context);
 455         return NULL;
 456 }
 457
 458 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
 459 {
 460         int i, j;
 461
 462         if (!pw)
 463                 return NULL;
 464         if (pw->n == 0)
 465                 return pw;
 466
 467         for (i = pw->n - 1; i >= 0; --i) {
 468                 for (j = i - 1; j >= 0; --j) {
 469                         if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
 470                                                         pw->p[j].FIELD))
 471                                 continue;
 472                         pw->p[j].set = isl_set_union(pw->p[j].set,
 473                                                         pw->p[i].set);
 474                         FN(EL,free)(pw->p[i].FIELD);
 475                         if (i != pw->n - 1)
 476                                 pw->p[i] = pw->p[pw->n - 1];
 477                         pw->n--;
 478                         break;
 479                 }
 480                 if (j >= 0)
 481                         continue;
 482                 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
 483                 if (!pw->p[i].set)
 484                         goto error;
 485         }
 486
 487         return pw;
 488 error:
 489         FN(PW,free)(pw);
 490         return NULL;
 491 }
 492
 493 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
 494 {
 495         return pw ? isl_dim_get_ctx(pw->dim) : NULL;
 496 }
 497
 498 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
 499         unsigned first, unsigned n)
 500 {
 501         int i;
 502
 503         if (!pw)
 504                 return -1;
 505         if (pw->n == 0 || n == 0)
 506                 return 0;
 507         for (i = 0; i < pw->n; ++i) {
 508                 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
 509                                                         type, first, n);
 510                 if (involves < 0 || involves)
 511                         return involves;
 512                 involves = isl_set_involves_dims(pw->p[i].set, type, first, n);
 513                 if (involves < 0 || involves)
 514                         return involves;
 515         }
 516         return 0;
 517 }
 518
 519 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
 520         enum isl_dim_type type, unsigned pos, const char *s)
 521 {
 522         int i;
 523
 524         pw = FN(PW,cow)(pw);
 525         if (!pw)
 526                 return NULL;
 527
 528         pw->dim = isl_dim_set_name(pw->dim, type, pos, s);
 529         if (!pw->dim)
 530                 goto error;
 531
 532         for (i = 0; i < pw->n; ++i) {
 533                 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set, type, pos, s);
 534                 if (!pw->p[i].set)
 535                         goto error;
 536                 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
 537                 if (!pw->p[i].FIELD)
 538                         goto error;
 539         }
 540
 541         return pw;
 542 error:
 543         FN(PW,free)(pw);
 544         return NULL;
 545 }
 546
 547 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
 548         enum isl_dim_type type, unsigned first, unsigned n)
 549 {
 550         int i;
 551
 552         if (!pw)
 553                 return NULL;
 554         if (n == 0 && !isl_dim_get_tuple_name(pw->dim, type))
 555                 return pw;
 556
 557         pw = FN(PW,cow)(pw);
 558         if (!pw)
 559                 return NULL;
 560         pw->dim = isl_dim_drop(pw->dim, type, first, n);
 561         if (!pw->dim)
 562                 goto error;
 563         for (i = 0; i < pw->n; ++i) {
 564                 pw->p[i].set = isl_set_drop(pw->p[i].set, type, first, n);
 565                 if (!pw->p[i].set)
 566                         goto error;
 567                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 568                 if (!pw->p[i].FIELD)
 569                         goto error;
 570         }
 571
 572         return pw;
 573 error:
 574         FN(PW,free)(pw);
 575         return NULL;
 576 }
 577
 578 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 579         unsigned first, unsigned n)
 580 {
 581         int i;
 582
 583         if (!pw)
 584                 return NULL;
 585         if (n == 0 && !isl_dim_is_named_or_nested(pw->dim, type))
 586                 return pw;
 587
 588         pw = FN(PW,cow)(pw);
 589         if (!pw)
 590                 return NULL;
 591
 592         pw->dim = isl_dim_insert(pw->dim, type, first, n);
 593         if (!pw->dim)
 594                 goto error;
 595
 596         for (i = 0; i < pw->n; ++i) {
 597                 pw->p[i].set = isl_set_insert(pw->p[i].set, type, first, n);
 598                 if (!pw->p[i].set)
 599                         goto error;
 600                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 601                                                                 type, first, n);
 602                 if (!pw->p[i].FIELD)
 603                         goto error;
 604         }
 605
 606         return pw;
 607 error:
 608         FN(PW,free)(pw);
 609         return NULL;
 610 }
 611
 612 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 613         enum isl_dim_type type, unsigned pos, isl_int v)
 614 {
 615         int i;
 616
 617         if (!pw)
 618                 return NULL;
 619
 620         pw = FN(PW,cow)(pw);
 621         if (!pw)
 622                 return NULL;
 623         for (i = 0; i < pw->n; ++i) {
 624                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 625                 if (!pw->p[i].set)
 626                         goto error;
 627         }
 628
 629         return pw;
 630 error:
 631         FN(PW,free)(pw);
 632         return NULL;
 633 }
 634
 635 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 636 {
 637         return pw ? isl_dim_size(pw->dim, type) : 0;
 638 }
 639
 640 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 641         enum isl_dim_type type, unsigned first, unsigned n)
 642 {
 643         int i;
 644
 645         if (!pw)
 646                 return NULL;
 647         if (n == 0)
 648                 return pw;
 649
 650         pw = FN(PW,cow)(pw);
 651         if (!pw)
 652                 return NULL;
 653         if (!pw->dim)
 654                 goto error;
 655         for (i = 0; i < pw->n; ++i) {
 656                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 657                 if (!pw->p[i].set)
 658                         goto error;
 659         }
 660
 661         return pw;
 662 error:
 663         FN(PW,free)(pw);
 664         return NULL;
 665 }
 666
 667 /* Compute the maximal value attained by the piecewise quasipolynomial
 668  * on its domain or zero if the domain is empty.
 669  * In the worst case, the domain is scanned completely,
 670  * so the domain is assumed to be bounded.
 671  */
 672 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 673 {
 674         int i;
 675         isl_qpolynomial *opt;
 676
 677         if (!pw)
 678                 return NULL;
 679
 680         if (pw->n == 0) {
 681                 isl_dim *dim = isl_dim_copy(pw->dim);
 682                 FN(PW,free)(pw);
 683                 return isl_qpolynomial_zero(dim);
 684         }
 685
 686         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 687                                         isl_set_copy(pw->p[0].set), max);
 688         for (i = 1; i < pw->n; ++i) {
 689                 isl_qpolynomial *opt_i;
 690                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 691                                                 isl_set_copy(pw->p[i].set), max);
 692                 if (max)
 693                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 694                 else
 695                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 696         }
 697
 698         FN(PW,free)(pw);
 699         return opt;
 700 }
 701
 702 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 703 {
 704         return FN(PW,opt)(pw, 1);
 705 }
 706
 707 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 708 {
 709         return FN(PW,opt)(pw, 0);
 710 }
 711
 712 __isl_give isl_dim *FN(PW,get_dim)(__isl_keep PW *pw)
 713 {
 714         return pw ? isl_dim_copy(pw->dim) : NULL;
 715 }
 716
 717 __isl_give PW *FN(PW,reset_dim)(__isl_take PW *pw, __isl_take isl_dim *dim)
 718 {
 719         int i;
 720
 721         pw = FN(PW,cow)(pw);
 722         if (!pw || !dim)
 723                 goto error;
 724
 725         for (i = 0; i < pw->n; ++i) {
 726                 pw->p[i].set = isl_set_reset_dim(pw->p[i].set,
 727                                                  isl_dim_copy(dim));
 728                 if (!pw->p[i].set)
 729                         goto error;
 730                 pw->p[i].FIELD = FN(EL,reset_dim)(pw->p[i].FIELD,
 731                                                   isl_dim_copy(dim));
 732                 if (!pw->p[i].FIELD)
 733                         goto error;
 734         }
 735         isl_dim_free(pw->dim);
 736         pw->dim = dim;
 737
 738         return pw;
 739 error:
 740         isl_dim_free(dim);
 741         FN(PW,free)(pw);
 742         return NULL;
 743 }
 744
 745 int FN(PW,has_equal_dim)(__isl_keep PW *pw1, __isl_keep PW *pw2)
 746 {
 747         if (!pw1 || !pw2)
 748                 return -1;
 749
 750         return isl_dim_equal(pw1->dim, pw2->dim);
 751 }
 752
 753 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
 754 {
 755         int i;
 756         isl_ctx *ctx;
 757
 758         if (!pw || !morph)
 759                 goto error;
 760
 761         ctx = isl_dim_get_ctx(pw->dim);
 762         isl_assert(ctx, isl_dim_equal(pw->dim, morph->dom->dim),
 763                 goto error);
 764
 765         pw = FN(PW,cow)(pw);
 766         if (!pw)
 767                 goto error;
 768         isl_dim_free(pw->dim);
 769         pw->dim = isl_dim_copy(morph->ran->dim);
 770         if (!pw->dim)
 771                 goto error;
 772
 773         for (i = 0; i < pw->n; ++i) {
 774                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
 775                 if (!pw->p[i].set)
 776                         goto error;
 777                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
 778                                                 isl_morph_copy(morph));
 779                 if (!pw->p[i].FIELD)
 780                         goto error;
 781         }
 782
 783         isl_morph_free(morph);
 784
 785         return pw;
 786 error:
 787         FN(PW,free)(pw);
 788         isl_morph_free(morph);
 789         return NULL;
 790 }
 791
 792 int FN(PW,foreach_piece)(__isl_keep PW *pw,
 793         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
 794         void *user)
 795 {
 796         int i;
 797
 798         if (!pw)
 799                 return -1;
 800
 801         for (i = 0; i < pw->n; ++i)
 802                 if (fn(isl_set_copy(pw->p[i].set),
 803                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
 804                         return -1;
 805
 806         return 0;
 807 }
 808
 809 static int any_divs(__isl_keep isl_set *set)
 810 {
 811         int i;
 812
 813         if (!set)
 814                 return -1;
 815
 816         for (i = 0; i < set->n; ++i)
 817                 if (set->p[i]->n_div > 0)
 818                         return 1;
 819
 820         return 0;
 821 }
 822
 823 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
 824         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
 825                     void *user), void *user)
 826 {
 827         int i;
 828
 829         if (!set || !el)
 830                 goto error;
 831
 832         for (i = 0; i < set->n; ++i) {
 833                 isl_set *lift;
 834                 EL *copy;
 835
 836                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
 837                 lift = isl_set_lift(lift);
 838
 839                 copy = FN(EL,copy)(el);
 840                 copy = FN(EL,lift)(copy, isl_set_get_dim(lift));
 841
 842                 if (fn(lift, copy, user) < 0)
 843                         goto error;
 844         }
 845
 846         isl_set_free(set);
 847         FN(EL,free)(el);
 848
 849         return 0;
 850 error:
 851         isl_set_free(set);
 852         FN(EL,free)(el);
 853         return -1;
 854 }
 855
 856 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
 857         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
 858                     void *user), void *user)
 859 {
 860         int i;
 861
 862         if (!pw)
 863                 return -1;
 864
 865         for (i = 0; i < pw->n; ++i) {
 866                 isl_set *set;
 867                 EL *el;
 868
 869                 set = isl_set_copy(pw->p[i].set);
 870                 el = FN(EL,copy)(pw->p[i].FIELD);
 871                 if (!any_divs(set)) {
 872                         if (fn(set, el, user) < 0)
 873                                 return -1;
 874                         continue;
 875                 }
 876                 if (foreach_lifted_subset(set, el, fn, user) < 0)
 877                         return -1;
 878         }
 879
 880         return 0;
 881 }
 882
 883 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
 884         enum isl_dim_type dst_type, unsigned dst_pos,
 885         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 886 {
 887         int i;
 888
 889         pw = FN(PW,cow)(pw);
 890         if (!pw)
 891                 return NULL;
 892
 893         pw->dim = isl_dim_move(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
 894         if (!pw->dim)
 895                 goto error;
 896
 897         for (i = 0; i < pw->n; ++i) {
 898                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
 899                                                 dst_type, dst_pos,
 900                                                 src_type, src_pos, n);
 901                 if (!pw->p[i].set)
 902                         goto error;
 903                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
 904                                         dst_type, dst_pos, src_type, src_pos, n);
 905                 if (!pw->p[i].FIELD)
 906                         goto error;
 907         }
 908
 909         return pw;
 910 error:
 911         FN(PW,free)(pw);
 912         return NULL;
 913 }
 914
 915 __isl_give PW *FN(PW,realign)(__isl_take PW *pw, __isl_take isl_reordering *exp)
 916 {
 917         int i;
 918
 919         pw = FN(PW,cow)(pw);
 920         if (!pw || !exp)
 921                 return NULL;
 922
 923         for (i = 0; i < pw->n; ++i) {
 924                 pw->p[i].set = isl_set_realign(pw->p[i].set,
 925                                                     isl_reordering_copy(exp));
 926                 if (!pw->p[i].set)
 927                         goto error;
 928                 pw->p[i].FIELD = FN(EL,realign)(pw->p[i].FIELD,
 929                                                     isl_reordering_copy(exp));
 930                 if (!pw->p[i].FIELD)
 931                         goto error;
 932         }
 933
 934         pw = FN(PW,reset_dim)(pw, isl_dim_copy(exp->dim));
 935
 936         isl_reordering_free(exp);
 937         return pw;
 938 error:
 939         isl_reordering_free(exp);
 940         FN(PW,free)(pw);
 941         return NULL;
 942 }
 943
 944 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
 945 {
 946         int i;
 947
 948         if (isl_int_is_one(v))
 949                 return pw;
 950         if (pw && isl_int_is_zero(v)) {
 951                 PW *zero;
 952                 isl_dim *dim = FN(PW,get_dim)(pw);
 953 #ifdef HAS_TYPE
 954                 zero = FN(PW,zero)(dim, pw->type);
 955 #else
 956                 zero = FN(PW,zero)(dim);
 957 #endif
 958                 FN(PW,free)(pw);
 959                 return zero;
 960         }
 961         pw = FN(PW,cow)(pw);
 962         if (!pw)
 963                 return NULL;
 964         if (pw->n == 0)
 965                 return pw;
 966
 967 #ifdef HAS_TYPE
 968         if (isl_int_is_neg(v))
 969                 pw->type = isl_fold_type_negate(pw->type);
 970 #endif
 971         for (i = 0; i < pw->n; ++i) {
 972                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
 973                 if (!pw->p[i].FIELD)
 974                         goto error;
 975         }
 976
 977         return pw;
 978 error:
 979         FN(PW,free)(pw);
 980         return NULL;
 981 }