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,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 NULL;
 163         if (--pw->ref > 0)
 164                 return NULL;
 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         return NULL;
 174 }
 175
 176 int FN(PW,IS_ZERO)(__isl_keep PW *pw)
 177 {
 178         if (!pw)
 179                 return -1;
 180
 181         return pw->n == 0;
 182 }
 183
 184 __isl_give PW *FN(PW,add)(__isl_take PW *pw1, __isl_take PW *pw2)
 185 {
 186         int i, j, n;
 187         struct PW *res;
 188         isl_ctx *ctx;
 189         isl_set *set;
 190
 191         if (!pw1 || !pw2)
 192                 goto error;
 193
 194         ctx = isl_dim_get_ctx(pw1->dim);
 195 #ifdef HAS_TYPE
 196         if (pw1->type != pw2->type)
 197                 isl_die(ctx, isl_error_invalid,
 198                         "fold types don't match", goto error);
 199 #endif
 200         isl_assert(ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 201
 202         if (FN(PW,IS_ZERO)(pw1)) {
 203                 FN(PW,free)(pw1);
 204                 return pw2;
 205         }
 206
 207         if (FN(PW,IS_ZERO)(pw2)) {
 208                 FN(PW,free)(pw2);
 209                 return pw1;
 210         }
 211
 212         n = (pw1->n + 1) * (pw2->n + 1);
 213 #ifdef HAS_TYPE
 214         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->type, n);
 215 #else
 216         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), n);
 217 #endif
 218
 219         for (i = 0; i < pw1->n; ++i) {
 220                 set = isl_set_copy(pw1->p[i].set);
 221                 for (j = 0; j < pw2->n; ++j) {
 222                         struct isl_set *common;
 223                         EL *sum;
 224                         set = isl_set_subtract(set,
 225                                         isl_set_copy(pw2->p[j].set));
 226                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 227                                                 isl_set_copy(pw2->p[j].set));
 228                         if (isl_set_plain_is_empty(common)) {
 229                                 isl_set_free(common);
 230                                 continue;
 231                         }
 232
 233                         sum = FN(EL,add_on_domain)(common,
 234                                                    FN(EL,copy)(pw1->p[i].FIELD),
 235                                                    FN(EL,copy)(pw2->p[j].FIELD));
 236
 237                         res = FN(PW,add_piece)(res, common, sum);
 238                 }
 239                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
 240         }
 241
 242         for (j = 0; j < pw2->n; ++j) {
 243                 set = isl_set_copy(pw2->p[j].set);
 244                 for (i = 0; i < pw1->n; ++i)
 245                         set = isl_set_subtract(set,
 246                                         isl_set_copy(pw1->p[i].set));
 247                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
 248         }
 249
 250         FN(PW,free)(pw1);
 251         FN(PW,free)(pw2);
 252
 253         return res;
 254 error:
 255         FN(PW,free)(pw1);
 256         FN(PW,free)(pw2);
 257         return NULL;
 258 }
 259
 260 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
 261 {
 262         int i;
 263         isl_ctx *ctx;
 264         PW *res;
 265
 266         if (!pw1 || !pw2)
 267                 goto error;
 268
 269         ctx = isl_dim_get_ctx(pw1->dim);
 270 #ifdef HAS_TYPE
 271         if (pw1->type != pw2->type)
 272                 isl_die(ctx, isl_error_invalid,
 273                         "fold types don't match", goto error);
 274 #endif
 275         isl_assert(ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 276
 277         if (FN(PW,IS_ZERO)(pw1)) {
 278                 FN(PW,free)(pw1);
 279                 return pw2;
 280         }
 281
 282         if (FN(PW,IS_ZERO)(pw2)) {
 283                 FN(PW,free)(pw2);
 284                 return pw1;
 285         }
 286
 287 #ifdef HAS_TYPE
 288         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->type, pw1->n + pw2->n);
 289 #else
 290         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->n + pw2->n);
 291 #endif
 292
 293         for (i = 0; i < pw1->n; ++i)
 294                 res = FN(PW,add_piece)(res,
 295                                 isl_set_copy(pw1->p[i].set),
 296                                 FN(EL,copy)(pw1->p[i].FIELD));
 297
 298         for (i = 0; i < pw2->n; ++i)
 299                 res = FN(PW,add_piece)(res,
 300                                 isl_set_copy(pw2->p[i].set),
 301                                 FN(EL,copy)(pw2->p[i].FIELD));
 302
 303         FN(PW,free)(pw1);
 304         FN(PW,free)(pw2);
 305
 306         return res;
 307 error:
 308         FN(PW,free)(pw1);
 309         FN(PW,free)(pw2);
 310         return NULL;
 311 }
 312
 313 #ifndef NO_NEG
 314 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
 315 {
 316         int i;
 317
 318         if (!pw)
 319                 return NULL;
 320
 321         if (FN(PW,IS_ZERO)(pw))
 322                 return pw;
 323
 324         pw = FN(PW,cow)(pw);
 325         if (!pw)
 326                 return NULL;
 327
 328         for (i = 0; i < pw->n; ++i) {
 329                 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
 330                 if (!pw->p[i].FIELD)
 331                         return FN(PW,free)(pw);
 332         }
 333
 334         return pw;
 335 }
 336
 337 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
 338 {
 339         return FN(PW,add)(pw1, FN(PW,neg)(pw2));
 340 }
 341 #endif
 342
 343 #ifndef NO_EVAL
 344 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
 345         __isl_take isl_point *pnt)
 346 {
 347         int i;
 348         int found = 0;
 349         isl_ctx *ctx;
 350         isl_dim *pnt_dim = NULL;
 351         isl_qpolynomial *qp;
 352
 353         if (!pw || !pnt)
 354                 goto error;
 355         ctx = isl_point_get_ctx(pnt);
 356         pnt_dim = isl_point_get_dim(pnt);
 357         isl_assert(ctx, isl_dim_equal(pnt_dim, pw->dim), goto error);
 358
 359         for (i = 0; i < pw->n; ++i) {
 360                 found = isl_set_contains_point(pw->p[i].set, pnt);
 361                 if (found < 0)
 362                         goto error;
 363                 if (found)
 364                         break;
 365         }
 366         if (found)
 367                 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
 368                                             isl_point_copy(pnt));
 369         else
 370                 qp = isl_qpolynomial_zero(isl_dim_copy(pw->dim));
 371         FN(PW,free)(pw);
 372         isl_dim_free(pnt_dim);
 373         isl_point_free(pnt);
 374         return qp;
 375 error:
 376         FN(PW,free)(pw);
 377         isl_dim_free(pnt_dim);
 378         isl_point_free(pnt);
 379         return NULL;
 380 }
 381 #endif
 382
 383 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
 384 {
 385         int i;
 386         isl_set *dom;
 387
 388         if (!pw)
 389                 return NULL;
 390
 391         dom = isl_set_empty(isl_dim_copy(pw->dim));
 392         for (i = 0; i < pw->n; ++i)
 393                 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
 394
 395         FN(PW,free)(pw);
 396
 397         return dom;
 398 }
 399
 400 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw, __isl_take isl_set *set)
 401 {
 402         int i;
 403
 404         if (!pw || !set)
 405                 goto error;
 406
 407         if (pw->n == 0) {
 408                 isl_set_free(set);
 409                 return pw;
 410         }
 411
 412         pw = FN(PW,cow)(pw);
 413         if (!pw)
 414                 goto error;
 415
 416         for (i = pw->n - 1; i >= 0; --i) {
 417                 isl_basic_set *aff;
 418                 pw->p[i].set = isl_set_intersect(pw->p[i].set, isl_set_copy(set));
 419                 if (!pw->p[i].set)
 420                         goto error;
 421                 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
 422                 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
 423                                                                 aff);
 424                 if (!pw->p[i].FIELD)
 425                         goto error;
 426                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 427                         isl_set_free(pw->p[i].set);
 428                         FN(EL,free)(pw->p[i].FIELD);
 429                         if (i != pw->n - 1)
 430                                 pw->p[i] = pw->p[pw->n - 1];
 431                         pw->n--;
 432                 }
 433         }
 434
 435         isl_set_free(set);
 436         return pw;
 437 error:
 438         isl_set_free(set);
 439         FN(PW,free)(pw);
 440         return NULL;
 441 }
 442
 443 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
 444 {
 445         int i;
 446         isl_basic_set *hull = NULL;
 447
 448         if (!pw || !context)
 449                 goto error;
 450
 451         if (pw->n == 0) {
 452                 isl_set_free(context);
 453                 return pw;
 454         }
 455
 456         context = isl_set_compute_divs(context);
 457         hull = isl_set_simple_hull(isl_set_copy(context));
 458
 459         pw = FN(PW,cow)(pw);
 460         if (!pw)
 461                 goto error;
 462
 463         for (i = pw->n - 1; i >= 0; --i) {
 464                 pw->p[i].set = isl_set_intersect(pw->p[i].set,
 465                                                  isl_set_copy(context));
 466                 if (!pw->p[i].set)
 467                         goto error;
 468                 pw->p[i].FIELD = FN(EL,gist)(pw->p[i].FIELD,
 469                                              isl_set_copy(pw->p[i].set));
 470                 pw->p[i].set = isl_set_gist_basic_set(pw->p[i].set,
 471                                                 isl_basic_set_copy(hull));
 472                 if (!pw->p[i].set)
 473                         goto error;
 474                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 475                         isl_set_free(pw->p[i].set);
 476                         FN(EL,free)(pw->p[i].FIELD);
 477                         if (i != pw->n - 1)
 478                                 pw->p[i] = pw->p[pw->n - 1];
 479                         pw->n--;
 480                 }
 481         }
 482
 483         isl_basic_set_free(hull);
 484         isl_set_free(context);
 485
 486         return pw;
 487 error:
 488         FN(PW,free)(pw);
 489         isl_basic_set_free(hull);
 490         isl_set_free(context);
 491         return NULL;
 492 }
 493
 494 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
 495 {
 496         int i, j;
 497
 498         if (!pw)
 499                 return NULL;
 500         if (pw->n == 0)
 501                 return pw;
 502
 503         for (i = pw->n - 1; i >= 0; --i) {
 504                 for (j = i - 1; j >= 0; --j) {
 505                         if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
 506                                                         pw->p[j].FIELD))
 507                                 continue;
 508                         pw->p[j].set = isl_set_union(pw->p[j].set,
 509                                                         pw->p[i].set);
 510                         FN(EL,free)(pw->p[i].FIELD);
 511                         if (i != pw->n - 1)
 512                                 pw->p[i] = pw->p[pw->n - 1];
 513                         pw->n--;
 514                         break;
 515                 }
 516                 if (j >= 0)
 517                         continue;
 518                 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
 519                 if (!pw->p[i].set)
 520                         goto error;
 521         }
 522
 523         return pw;
 524 error:
 525         FN(PW,free)(pw);
 526         return NULL;
 527 }
 528
 529 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
 530 {
 531         return pw ? isl_dim_get_ctx(pw->dim) : NULL;
 532 }
 533
 534 #ifndef NO_INVOLVES_DIMS
 535 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
 536         unsigned first, unsigned n)
 537 {
 538         int i;
 539
 540         if (!pw)
 541                 return -1;
 542         if (pw->n == 0 || n == 0)
 543                 return 0;
 544         for (i = 0; i < pw->n; ++i) {
 545                 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
 546                                                         type, first, n);
 547                 if (involves < 0 || involves)
 548                         return involves;
 549                 involves = isl_set_involves_dims(pw->p[i].set, type, first, n);
 550                 if (involves < 0 || involves)
 551                         return involves;
 552         }
 553         return 0;
 554 }
 555 #endif
 556
 557 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
 558         enum isl_dim_type type, unsigned pos, const char *s)
 559 {
 560         int i;
 561
 562         pw = FN(PW,cow)(pw);
 563         if (!pw)
 564                 return NULL;
 565
 566         pw->dim = isl_dim_set_name(pw->dim, type, pos, s);
 567         if (!pw->dim)
 568                 goto error;
 569
 570         for (i = 0; i < pw->n; ++i) {
 571                 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set, type, pos, s);
 572                 if (!pw->p[i].set)
 573                         goto error;
 574                 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
 575                 if (!pw->p[i].FIELD)
 576                         goto error;
 577         }
 578
 579         return pw;
 580 error:
 581         FN(PW,free)(pw);
 582         return NULL;
 583 }
 584
 585 #ifndef NO_DROP_DIMS
 586 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
 587         enum isl_dim_type type, unsigned first, unsigned n)
 588 {
 589         int i;
 590
 591         if (!pw)
 592                 return NULL;
 593         if (n == 0 && !isl_dim_get_tuple_name(pw->dim, type))
 594                 return pw;
 595
 596         pw = FN(PW,cow)(pw);
 597         if (!pw)
 598                 return NULL;
 599         pw->dim = isl_dim_drop(pw->dim, type, first, n);
 600         if (!pw->dim)
 601                 goto error;
 602         for (i = 0; i < pw->n; ++i) {
 603                 pw->p[i].set = isl_set_drop(pw->p[i].set, type, first, n);
 604                 if (!pw->p[i].set)
 605                         goto error;
 606                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 607                 if (!pw->p[i].FIELD)
 608                         goto error;
 609         }
 610
 611         return pw;
 612 error:
 613         FN(PW,free)(pw);
 614         return NULL;
 615 }
 616 #endif
 617
 618 #ifndef NO_INSERT_DIMS
 619 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 620         unsigned first, unsigned n)
 621 {
 622         int i;
 623
 624         if (!pw)
 625                 return NULL;
 626         if (n == 0 && !isl_dim_is_named_or_nested(pw->dim, type))
 627                 return pw;
 628
 629         pw = FN(PW,cow)(pw);
 630         if (!pw)
 631                 return NULL;
 632
 633         pw->dim = isl_dim_insert(pw->dim, type, first, n);
 634         if (!pw->dim)
 635                 goto error;
 636
 637         for (i = 0; i < pw->n; ++i) {
 638                 pw->p[i].set = isl_set_insert(pw->p[i].set, type, first, n);
 639                 if (!pw->p[i].set)
 640                         goto error;
 641                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 642                                                                 type, first, n);
 643                 if (!pw->p[i].FIELD)
 644                         goto error;
 645         }
 646
 647         return pw;
 648 error:
 649         FN(PW,free)(pw);
 650         return NULL;
 651 }
 652 #endif
 653
 654 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 655         enum isl_dim_type type, unsigned pos, isl_int v)
 656 {
 657         int i;
 658
 659         if (!pw)
 660                 return NULL;
 661
 662         pw = FN(PW,cow)(pw);
 663         if (!pw)
 664                 return NULL;
 665         for (i = 0; i < pw->n; ++i) {
 666                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 667                 if (!pw->p[i].set)
 668                         goto error;
 669         }
 670
 671         return pw;
 672 error:
 673         FN(PW,free)(pw);
 674         return NULL;
 675 }
 676
 677 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 678 {
 679         return pw ? isl_dim_size(pw->dim, type) : 0;
 680 }
 681
 682 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 683         enum isl_dim_type type, unsigned first, unsigned n)
 684 {
 685         int i;
 686
 687         if (!pw)
 688                 return NULL;
 689         if (n == 0)
 690                 return pw;
 691
 692         pw = FN(PW,cow)(pw);
 693         if (!pw)
 694                 return NULL;
 695         if (!pw->dim)
 696                 goto error;
 697         for (i = 0; i < pw->n; ++i) {
 698                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 699                 if (!pw->p[i].set)
 700                         goto error;
 701         }
 702
 703         return pw;
 704 error:
 705         FN(PW,free)(pw);
 706         return NULL;
 707 }
 708
 709 #ifndef NO_OPT
 710 /* Compute the maximal value attained by the piecewise quasipolynomial
 711  * on its domain or zero if the domain is empty.
 712  * In the worst case, the domain is scanned completely,
 713  * so the domain is assumed to be bounded.
 714  */
 715 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 716 {
 717         int i;
 718         isl_qpolynomial *opt;
 719
 720         if (!pw)
 721                 return NULL;
 722
 723         if (pw->n == 0) {
 724                 isl_dim *dim = isl_dim_copy(pw->dim);
 725                 FN(PW,free)(pw);
 726                 return isl_qpolynomial_zero(dim);
 727         }
 728
 729         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 730                                         isl_set_copy(pw->p[0].set), max);
 731         for (i = 1; i < pw->n; ++i) {
 732                 isl_qpolynomial *opt_i;
 733                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 734                                                 isl_set_copy(pw->p[i].set), max);
 735                 if (max)
 736                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 737                 else
 738                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 739         }
 740
 741         FN(PW,free)(pw);
 742         return opt;
 743 }
 744
 745 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 746 {
 747         return FN(PW,opt)(pw, 1);
 748 }
 749
 750 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 751 {
 752         return FN(PW,opt)(pw, 0);
 753 }
 754 #endif
 755
 756 __isl_give isl_dim *FN(PW,get_dim)(__isl_keep PW *pw)
 757 {
 758         return pw ? isl_dim_copy(pw->dim) : NULL;
 759 }
 760
 761 #ifndef NO_RESET_DIM
 762 __isl_give PW *FN(PW,reset_dim)(__isl_take PW *pw, __isl_take isl_dim *dim)
 763 {
 764         int i;
 765
 766         pw = FN(PW,cow)(pw);
 767         if (!pw || !dim)
 768                 goto error;
 769
 770         for (i = 0; i < pw->n; ++i) {
 771                 pw->p[i].set = isl_set_reset_dim(pw->p[i].set,
 772                                                  isl_dim_copy(dim));
 773                 if (!pw->p[i].set)
 774                         goto error;
 775                 pw->p[i].FIELD = FN(EL,reset_dim)(pw->p[i].FIELD,
 776                                                   isl_dim_copy(dim));
 777                 if (!pw->p[i].FIELD)
 778                         goto error;
 779         }
 780         isl_dim_free(pw->dim);
 781         pw->dim = dim;
 782
 783         return pw;
 784 error:
 785         isl_dim_free(dim);
 786         FN(PW,free)(pw);
 787         return NULL;
 788 }
 789 #endif
 790
 791 int FN(PW,has_equal_dim)(__isl_keep PW *pw1, __isl_keep PW *pw2)
 792 {
 793         if (!pw1 || !pw2)
 794                 return -1;
 795
 796         return isl_dim_equal(pw1->dim, pw2->dim);
 797 }
 798
 799 #ifndef NO_MORPH
 800 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
 801 {
 802         int i;
 803         isl_ctx *ctx;
 804
 805         if (!pw || !morph)
 806                 goto error;
 807
 808         ctx = isl_dim_get_ctx(pw->dim);
 809         isl_assert(ctx, isl_dim_equal(pw->dim, morph->dom->dim),
 810                 goto error);
 811
 812         pw = FN(PW,cow)(pw);
 813         if (!pw)
 814                 goto error;
 815         isl_dim_free(pw->dim);
 816         pw->dim = isl_dim_copy(morph->ran->dim);
 817         if (!pw->dim)
 818                 goto error;
 819
 820         for (i = 0; i < pw->n; ++i) {
 821                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
 822                 if (!pw->p[i].set)
 823                         goto error;
 824                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
 825                                                 isl_morph_copy(morph));
 826                 if (!pw->p[i].FIELD)
 827                         goto error;
 828         }
 829
 830         isl_morph_free(morph);
 831
 832         return pw;
 833 error:
 834         FN(PW,free)(pw);
 835         isl_morph_free(morph);
 836         return NULL;
 837 }
 838 #endif
 839
 840 int FN(PW,foreach_piece)(__isl_keep PW *pw,
 841         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
 842         void *user)
 843 {
 844         int i;
 845
 846         if (!pw)
 847                 return -1;
 848
 849         for (i = 0; i < pw->n; ++i)
 850                 if (fn(isl_set_copy(pw->p[i].set),
 851                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
 852                         return -1;
 853
 854         return 0;
 855 }
 856
 857 #ifndef NO_LIFT
 858 static int any_divs(__isl_keep isl_set *set)
 859 {
 860         int i;
 861
 862         if (!set)
 863                 return -1;
 864
 865         for (i = 0; i < set->n; ++i)
 866                 if (set->p[i]->n_div > 0)
 867                         return 1;
 868
 869         return 0;
 870 }
 871
 872 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
 873         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
 874                     void *user), void *user)
 875 {
 876         int i;
 877
 878         if (!set || !el)
 879                 goto error;
 880
 881         for (i = 0; i < set->n; ++i) {
 882                 isl_set *lift;
 883                 EL *copy;
 884
 885                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
 886                 lift = isl_set_lift(lift);
 887
 888                 copy = FN(EL,copy)(el);
 889                 copy = FN(EL,lift)(copy, isl_set_get_dim(lift));
 890
 891                 if (fn(lift, copy, user) < 0)
 892                         goto error;
 893         }
 894
 895         isl_set_free(set);
 896         FN(EL,free)(el);
 897
 898         return 0;
 899 error:
 900         isl_set_free(set);
 901         FN(EL,free)(el);
 902         return -1;
 903 }
 904
 905 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
 906         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
 907                     void *user), void *user)
 908 {
 909         int i;
 910
 911         if (!pw)
 912                 return -1;
 913
 914         for (i = 0; i < pw->n; ++i) {
 915                 isl_set *set;
 916                 EL *el;
 917
 918                 set = isl_set_copy(pw->p[i].set);
 919                 el = FN(EL,copy)(pw->p[i].FIELD);
 920                 if (!any_divs(set)) {
 921                         if (fn(set, el, user) < 0)
 922                                 return -1;
 923                         continue;
 924                 }
 925                 if (foreach_lifted_subset(set, el, fn, user) < 0)
 926                         return -1;
 927         }
 928
 929         return 0;
 930 }
 931 #endif
 932
 933 #ifndef NO_MOVE_DIMS
 934 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
 935         enum isl_dim_type dst_type, unsigned dst_pos,
 936         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 937 {
 938         int i;
 939
 940         pw = FN(PW,cow)(pw);
 941         if (!pw)
 942                 return NULL;
 943
 944         pw->dim = isl_dim_move(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
 945         if (!pw->dim)
 946                 goto error;
 947
 948         for (i = 0; i < pw->n; ++i) {
 949                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
 950                                                 dst_type, dst_pos,
 951                                                 src_type, src_pos, n);
 952                 if (!pw->p[i].set)
 953                         goto error;
 954                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
 955                                         dst_type, dst_pos, src_type, src_pos, n);
 956                 if (!pw->p[i].FIELD)
 957                         goto error;
 958         }
 959
 960         return pw;
 961 error:
 962         FN(PW,free)(pw);
 963         return NULL;
 964 }
 965 #endif
 966
 967 #ifndef NO_REALIGN
 968 __isl_give PW *FN(PW,realign)(__isl_take PW *pw, __isl_take isl_reordering *exp)
 969 {
 970         int i;
 971
 972         pw = FN(PW,cow)(pw);
 973         if (!pw || !exp)
 974                 return NULL;
 975
 976         for (i = 0; i < pw->n; ++i) {
 977                 pw->p[i].set = isl_set_realign(pw->p[i].set,
 978                                                     isl_reordering_copy(exp));
 979                 if (!pw->p[i].set)
 980                         goto error;
 981                 pw->p[i].FIELD = FN(EL,realign)(pw->p[i].FIELD,
 982                                                     isl_reordering_copy(exp));
 983                 if (!pw->p[i].FIELD)
 984                         goto error;
 985         }
 986
 987         pw = FN(PW,reset_dim)(pw, isl_dim_copy(exp->dim));
 988
 989         isl_reordering_free(exp);
 990         return pw;
 991 error:
 992         isl_reordering_free(exp);
 993         FN(PW,free)(pw);
 994         return NULL;
 995 }
 996
 997 /* Align the parameters of "pw" to those of "model".
 998  */
 999 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_dim *model)
1000 {
1001         isl_ctx *ctx;
1002
1003         if (!pw || !model)
1004                 goto error;
1005
1006         ctx = isl_dim_get_ctx(model);
1007         if (!isl_dim_has_named_params(model))
1008                 isl_die(ctx, isl_error_invalid,
1009                         "model has unnamed parameters", goto error);
1010         if (!isl_dim_has_named_params(pw->dim))
1011                 isl_die(ctx, isl_error_invalid,
1012                         "input has unnamed parameters", goto error);
1013         if (!isl_dim_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
1014                 isl_reordering *exp;
1015
1016                 model = isl_dim_drop(model, isl_dim_in,
1017                                         0, isl_dim_size(model, isl_dim_in));
1018                 model = isl_dim_drop(model, isl_dim_out,
1019                                         0, isl_dim_size(model, isl_dim_out));
1020                 exp = isl_parameter_alignment_reordering(pw->dim, model);
1021                 exp = isl_reordering_extend_dim(exp, FN(PW,get_dim)(pw));
1022                 pw = FN(PW,realign)(pw, exp);
1023         }
1024
1025         isl_dim_free(model);
1026         return pw;
1027 error:
1028         isl_dim_free(model);
1029         FN(PW,free)(pw);
1030         return NULL;
1031 }
1032 #endif
1033
1034 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1035 {
1036         int i;
1037
1038         if (isl_int_is_one(v))
1039                 return pw;
1040         if (pw && isl_int_is_zero(v)) {
1041                 PW *zero;
1042                 isl_dim *dim = FN(PW,get_dim)(pw);
1043 #ifdef HAS_TYPE
1044                 zero = FN(PW,ZERO)(dim, pw->type);
1045 #else
1046                 zero = FN(PW,ZERO)(dim);
1047 #endif
1048                 FN(PW,free)(pw);
1049                 return zero;
1050         }
1051         pw = FN(PW,cow)(pw);
1052         if (!pw)
1053                 return NULL;
1054         if (pw->n == 0)
1055                 return pw;
1056
1057 #ifdef HAS_TYPE
1058         if (isl_int_is_neg(v))
1059                 pw->type = isl_fold_type_negate(pw->type);
1060 #endif
1061         for (i = 0; i < pw->n; ++i) {
1062                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1063                 if (!pw->p[i].FIELD)
1064                         goto error;
1065         }
1066
1067         return pw;
1068 error:
1069         FN(PW,free)(pw);
1070         return NULL;
1071 }
1072
1073 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1074 {
1075         return FN(PW,mul_isl_int)(pw, v);
1076 }