?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_set_insert
[isl.git] / isl_fold.c
blob8f9ce114635fca29918e2b1eadb81dffcf1fe88c
1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 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 #include <isl_union_map_private.h>
12 #include <isl_polynomial_private.h>
13 #include <isl_point_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_map_private.h>
16 #include <isl_lp.h>
17 #include <isl_seq.h>
18
19 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
20 enum isl_fold type, __isl_take isl_dim *dim, int n)
21 {
22 isl_qpolynomial_fold *fold;
23
24 if (!dim)
25 goto error;
26
27 isl_assert(dim->ctx, n >= 0, goto error);
28 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
29 sizeof(struct isl_qpolynomial_fold) +
30 (n - 1) * sizeof(struct isl_qpolynomial *));
31 if (!fold)
32 goto error;
33
34 fold->ref = 1;
35 fold->size = n;
36 fold->n = 0;
37 fold->type = type;
38 fold->dim = dim;
39
40 return fold;
41 error:
42 isl_dim_free(dim);
43 return NULL;
44 }
45
46 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_dim(
47 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
48 {
49 if (!fold || !dim)
50 goto error;
51
52 isl_dim_free(fold->dim);
53 fold->dim = dim;
54
55 return fold;
56 error:
57 isl_qpolynomial_fold_free(fold);
58 isl_dim_free(dim);
59 return NULL;
60 }
61
62 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
63 enum isl_dim_type type, unsigned first, unsigned n)
64 {
65 int i;
66
67 if (!fold)
68 return -1;
69 if (fold->n == 0 || n == 0)
70 return 0;
71
72 for (i = 0; i < fold->n; ++i) {
73 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
74 type, first, n);
75 if (involves < 0 || involves)
76 return involves;
77 }
78 return 0;
79 }
80
81 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
82 __isl_take isl_qpolynomial_fold *fold,
83 enum isl_dim_type type, unsigned first, unsigned n)
84 {
85 int i;
86
87 if (!fold)
88 return NULL;
89 if (n == 0)
90 return fold;
91
92 fold = isl_qpolynomial_fold_cow(fold);
93 if (!fold)
94 return NULL;
95 fold->dim = isl_dim_drop(fold->dim, type, first, n);
96 if (!fold->dim)
97 goto error;
98
99 for (i = 0; i < fold->n; ++i) {
100 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
101 type, first, n);
102 if (!fold->qp[i])
103 goto error;
104 }
105
106 return fold;
107 error:
108 isl_qpolynomial_fold_free(fold);
109 return NULL;
110 }
111
112 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
113 {
114 struct isl_upoly_cst *cst;
115
116 cst = isl_upoly_as_cst(qp->upoly);
117 if (!cst)
118 return 0;
119
120 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
121 }
122
123 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
124 __isl_keep isl_qpolynomial *qp)
125 {
126 enum isl_lp_result res;
127 isl_vec *aff;
128 isl_int opt;
129 int sgn = 0;
130
131 aff = isl_qpolynomial_extract_affine(qp);
132 if (!aff)
133 return 0;
134
135 isl_int_init(opt);
136
137 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
138 &opt, NULL, NULL);
139 if (res == isl_lp_error)
140 goto done;
141 if (res == isl_lp_empty ||
142 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
143 sgn = 1;
144 goto done;
145 }
146
147 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
148 &opt, NULL, NULL);
149 if (res == isl_lp_ok && !isl_int_is_pos(opt))
150 sgn = -1;
151
152 done:
153 isl_int_clear(opt);
154 isl_vec_free(aff);
155 return sgn;
156 }
157
158 /* Determine, if possible, the sign of the quasipolynomial "qp" on
159 * the domain "set".
160 *
161 * If qp is a constant, then the problem is trivial.
162 * If qp is linear, then we check if the minimum of the corresponding
163 * affine constraint is non-negative or if the maximum is non-positive.
164 *
165 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
166 * in "set". If so, we write qp(v,v') as
167 *
168 * q(v,v') * (v - l) + r(v')
169 *
170 * if q(v,v') and r(v') have the same known sign, then the original
171 * quasipolynomial has the same sign as well.
172 *
173 * Return
174 * -1 if qp <= 0
175 * 1 if qp >= 0
176 * 0 if unknown
177 */
178 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
179 __isl_keep isl_qpolynomial *qp)
180 {
181 int d;
182 int i;
183 int is;
184 struct isl_upoly_rec *rec;
185 isl_vec *v;
186 isl_int l;
187 enum isl_lp_result res;
188 int sgn = 0;
189
190 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
191 if (is < 0)
192 return 0;
193 if (is)
194 return isl_qpolynomial_cst_sign(qp);
195
196 is = isl_qpolynomial_is_affine(qp);
197 if (is < 0)
198 return 0;
199 if (is)
200 return isl_qpolynomial_aff_sign(set, qp);
201
202 if (qp->div->n_row > 0)
203 return 0;
204
205 rec = isl_upoly_as_rec(qp->upoly);
206 if (!rec)
207 return 0;
208
209 d = isl_dim_total(qp->dim);
210 v = isl_vec_alloc(set->ctx, 2 + d);
211 if (!v)
212 return 0;
213
214 isl_seq_clr(v->el + 1, 1 + d);
215 isl_int_set_si(v->el[0], 1);
216 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
217
218 isl_int_init(l);
219
220 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
221 if (res == isl_lp_ok) {
222 isl_qpolynomial *min;
223 isl_qpolynomial *base;
224 isl_qpolynomial *r, *q;
225 isl_qpolynomial *t;
226
227 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
228 base = isl_qpolynomial_pow(isl_dim_copy(qp->dim),
229 qp->upoly->var, 1);
230
231 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
232 isl_upoly_copy(rec->p[rec->n - 1]));
233 q = isl_qpolynomial_copy(r);
234
235 for (i = rec->n - 2; i >= 0; --i) {
236 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
237 t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
238 isl_upoly_copy(rec->p[i]));
239 r = isl_qpolynomial_add(r, t);
240 if (i == 0)
241 break;
242 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
243 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
244 }
245
246 if (isl_qpolynomial_is_zero(q))
247 sgn = isl_qpolynomial_sign(set, r);
248 else if (isl_qpolynomial_is_zero(r))
249 sgn = isl_qpolynomial_sign(set, q);
250 else {
251 int sgn_q, sgn_r;
252 sgn_r = isl_qpolynomial_sign(set, r);
253 sgn_q = isl_qpolynomial_sign(set, q);
254 if (sgn_r == sgn_q)
255 sgn = sgn_r;
256 }
257
258 isl_qpolynomial_free(min);
259 isl_qpolynomial_free(base);
260 isl_qpolynomial_free(q);
261 isl_qpolynomial_free(r);
262 }
263
264 isl_int_clear(l);
265
266 isl_vec_free(v);
267
268 return sgn;
269 }
270
271 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
272 __isl_keep isl_set *set,
273 __isl_take isl_qpolynomial_fold *fold1,
274 __isl_take isl_qpolynomial_fold *fold2)
275 {
276 int i, j;
277 int n1;
278 struct isl_qpolynomial_fold *res = NULL;
279 int better;
280
281 if (!fold1 || !fold2)
282 goto error;
283
284 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
285 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
286 goto error);
287
288 better = fold1->type == isl_fold_max ? -1 : 1;
289
290 if (isl_qpolynomial_fold_is_empty(fold1)) {
291 isl_qpolynomial_fold_free(fold1);
292 return fold2;
293 }
294
295 if (isl_qpolynomial_fold_is_empty(fold2)) {
296 isl_qpolynomial_fold_free(fold2);
297 return fold1;
298 }
299
300 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
301 fold1->n + fold2->n);
302 if (!res)
303 goto error;
304
305 for (i = 0; i < fold1->n; ++i) {
306 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
307 if (!res->qp[res->n])
308 goto error;
309 res->n++;
310 }
311 n1 = res->n;
312
313 for (i = 0; i < fold2->n; ++i) {
314 for (j = n1 - 1; j >= 0; --j) {
315 isl_qpolynomial *d;
316 int sgn;
317 d = isl_qpolynomial_sub(
318 isl_qpolynomial_copy(res->qp[j]),
319 isl_qpolynomial_copy(fold2->qp[i]));
320 sgn = isl_qpolynomial_sign(set, d);
321 isl_qpolynomial_free(d);
322 if (sgn == 0)
323 continue;
324 if (sgn != better)
325 break;
326 isl_qpolynomial_free(res->qp[j]);
327 if (j != n1 - 1)
328 res->qp[j] = res->qp[n1 - 1];
329 n1--;
330 if (n1 != res->n - 1)
331 res->qp[n1] = res->qp[res->n - 1];
332 res->n--;
333 }
334 if (j >= 0)
335 continue;
336 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
337 if (!res->qp[res->n])
338 goto error;
339 res->n++;
340 }
341
342 isl_qpolynomial_fold_free(fold1);
343 isl_qpolynomial_fold_free(fold2);
344
345 return res;
346 error:
347 isl_qpolynomial_fold_free(res);
348 isl_qpolynomial_fold_free(fold1);
349 isl_qpolynomial_fold_free(fold2);
350 return NULL;
351 }
352
353 #undef PW
354 #define PW isl_pw_qpolynomial_fold
355 #undef EL
356 #define EL isl_qpolynomial_fold
357 #undef IS_ZERO
358 #define IS_ZERO is_empty
359 #undef FIELD
360 #define FIELD fold
361 #undef ADD
362 #define ADD(d,e1,e2) isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
363
364 #include <isl_pw_templ.c>
365
366 #undef UNION
367 #define UNION isl_union_pw_qpolynomial_fold
368 #undef PART
369 #define PART isl_pw_qpolynomial_fold
370 #undef PARTS
371 #define PARTS pw_qpolynomial_fold
372
373 #include <isl_union_templ.c>
374
375 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
376 __isl_take isl_dim *dim)
377 {
378 return qpolynomial_fold_alloc(type, dim, 0);
379 }
380
381 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
382 enum isl_fold type, __isl_take isl_qpolynomial *qp)
383 {
384 isl_qpolynomial_fold *fold;
385
386 if (!qp)
387 return NULL;
388
389 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
390 if (!fold)
391 goto error;
392
393 fold->qp[0] = qp;
394 fold->n++;
395
396 return fold;
397 error:
398 isl_qpolynomial_fold_free(fold);
399 isl_qpolynomial_free(qp);
400 return NULL;
401 }
402
403 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
404 __isl_keep isl_qpolynomial_fold *fold)
405 {
406 if (!fold)
407 return NULL;
408
409 fold->ref++;
410 return fold;
411 }
412
413 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
414 __isl_keep isl_qpolynomial_fold *fold)
415 {
416 int i;
417 isl_qpolynomial_fold *dup;
418
419 if (!fold)
420 return NULL;
421 dup = qpolynomial_fold_alloc(fold->type,
422 isl_dim_copy(fold->dim), fold->n);
423 if (!dup)
424 return NULL;
425
426 dup->n = fold->n;
427 for (i = 0; i < fold->n; ++i) {
428 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
429 if (!dup->qp[i])
430 goto error;
431 }
432
433 return dup;
434 error:
435 isl_qpolynomial_fold_free(dup);
436 return NULL;
437 }
438
439 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
440 __isl_take isl_qpolynomial_fold *fold)
441 {
442 if (!fold)
443 return NULL;
444
445 if (fold->ref == 1)
446 return fold;
447 fold->ref--;
448 return isl_qpolynomial_fold_dup(fold);
449 }
450
451 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
452 {
453 int i;
454
455 if (!fold)
456 return;
457 if (--fold->ref > 0)
458 return;
459
460 for (i = 0; i < fold->n; ++i)
461 isl_qpolynomial_free(fold->qp[i]);
462 isl_dim_free(fold->dim);
463 free(fold);
464 }
465
466 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
467 {
468 if (!fold)
469 return -1;
470
471 return fold->n == 0;
472 }
473
474 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
475 __isl_take isl_qpolynomial_fold *fold1,
476 __isl_take isl_qpolynomial_fold *fold2)
477 {
478 int i;
479 struct isl_qpolynomial_fold *res = NULL;
480
481 if (!fold1 || !fold2)
482 goto error;
483
484 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
485 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
486 goto error);
487
488 if (isl_qpolynomial_fold_is_empty(fold1)) {
489 isl_qpolynomial_fold_free(fold1);
490 return fold2;
491 }
492
493 if (isl_qpolynomial_fold_is_empty(fold2)) {
494 isl_qpolynomial_fold_free(fold2);
495 return fold1;
496 }
497
498 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
499 fold1->n + fold2->n);
500 if (!res)
501 goto error;
502
503 for (i = 0; i < fold1->n; ++i) {
504 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
505 if (!res->qp[res->n])
506 goto error;
507 res->n++;
508 }
509
510 for (i = 0; i < fold2->n; ++i) {
511 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
512 if (!res->qp[res->n])
513 goto error;
514 res->n++;
515 }
516
517 isl_qpolynomial_fold_free(fold1);
518 isl_qpolynomial_fold_free(fold2);
519
520 return res;
521 error:
522 isl_qpolynomial_fold_free(res);
523 isl_qpolynomial_fold_free(fold1);
524 isl_qpolynomial_fold_free(fold2);
525 return NULL;
526 }
527
528 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
529 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
530 {
531 int i;
532 isl_pw_qpolynomial_fold *pwf;
533
534 if (!pwqp)
535 return NULL;
536
537 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
538
539 for (i = 0; i < pwqp->n; ++i)
540 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
541 isl_set_copy(pwqp->p[i].set),
542 isl_qpolynomial_fold_alloc(type,
543 isl_qpolynomial_copy(pwqp->p[i].qp)));
544
545 isl_pw_qpolynomial_free(pwqp);
546
547 return pwf;
548 }
549
550 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
551 __isl_keep isl_qpolynomial_fold *fold2)
552 {
553 int i;
554
555 if (!fold1 || !fold2)
556 return -1;
557
558 if (fold1->n != fold2->n)
559 return 0;
560
561 /* We probably want to sort the qps first... */
562 for (i = 0; i < fold1->n; ++i) {
563 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
564 if (eq < 0 || !eq)
565 return eq;
566 }
567
568 return 1;
569 }
570
571 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
572 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
573 {
574 isl_qpolynomial *qp;
575
576 if (!fold || !pnt)
577 goto error;
578 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
579 isl_assert(pnt->dim->ctx,
580 fold->type == isl_fold_max || fold->type == isl_fold_min,
581 goto error);
582
583 if (fold->n == 0)
584 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
585 else {
586 int i;
587 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
588 isl_point_copy(pnt));
589 for (i = 1; i < fold->n; ++i) {
590 isl_qpolynomial *qp_i;
591 qp_i = isl_qpolynomial_eval(
592 isl_qpolynomial_copy(fold->qp[i]),
593 isl_point_copy(pnt));
594 if (fold->type == isl_fold_max)
595 qp = isl_qpolynomial_max_cst(qp, qp_i);
596 else
597 qp = isl_qpolynomial_min_cst(qp, qp_i);
598 }
599 }
600 isl_qpolynomial_fold_free(fold);
601 isl_point_free(pnt);
602
603 return qp;
604 error:
605 isl_qpolynomial_fold_free(fold);
606 isl_point_free(pnt);
607 return NULL;
608 }
609
610 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
611 {
612 int i;
613 size_t n = 0;
614
615 for (i = 0; i < pwf->n; ++i)
616 n += pwf->p[i].fold->n;
617
618 return n;
619 }
620
621 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
622 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
623 {
624 int i;
625 isl_qpolynomial *opt;
626
627 if (!set || !fold)
628 goto error;
629
630 if (fold->n == 0) {
631 isl_dim *dim = isl_dim_copy(fold->dim);
632 isl_set_free(set);
633 isl_qpolynomial_fold_free(fold);
634 return isl_qpolynomial_zero(dim);
635 }
636
637 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
638 isl_set_copy(set), max);
639 for (i = 1; i < fold->n; ++i) {
640 isl_qpolynomial *opt_i;
641 opt_i = isl_qpolynomial_opt_on_domain(
642 isl_qpolynomial_copy(fold->qp[i]),
643 isl_set_copy(set), max);
644 if (max)
645 opt = isl_qpolynomial_max_cst(opt, opt_i);
646 else
647 opt = isl_qpolynomial_min_cst(opt, opt_i);
648 }
649
650 isl_set_free(set);
651 isl_qpolynomial_fold_free(fold);
652
653 return opt;
654 error:
655 isl_set_free(set);
656 isl_qpolynomial_fold_free(fold);
657 return NULL;
658 }
659
660 /* Check whether for each quasi-polynomial in "fold2" there is
661 * a quasi-polynomial in "fold1" that dominates it on "set".
662 */
663 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
664 __isl_keep isl_qpolynomial_fold *fold1,
665 __isl_keep isl_qpolynomial_fold *fold2)
666 {
667 int i, j;
668 int covers;
669
670 if (!set || !fold1 || !fold2)
671 return -1;
672
673 covers = fold1->type == isl_fold_max ? 1 : -1;
674
675 for (i = 0; i < fold2->n; ++i) {
676 for (j = 0; j < fold1->n; ++j) {
677 isl_qpolynomial *d;
678 int sgn;
679
680 d = isl_qpolynomial_sub(
681 isl_qpolynomial_copy(fold1->qp[j]),
682 isl_qpolynomial_copy(fold2->qp[i]));
683 sgn = isl_qpolynomial_sign(set, d);
684 isl_qpolynomial_free(d);
685 if (sgn == covers)
686 break;
687 }
688 if (j >= fold1->n)
689 return 0;
690 }
691
692 return 1;
693 }
694
695 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
696 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
697 * that of pwf2.
698 */
699 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
700 __isl_keep isl_pw_qpolynomial_fold *pwf2)
701 {
702 int i, j;
703 isl_set *dom1, *dom2;
704 int is_subset;
705
706 if (!pwf1 || !pwf2)
707 return -1;
708
709 if (pwf2->n == 0)
710 return 1;
711 if (pwf1->n == 0)
712 return 0;
713
714 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
715 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
716 is_subset = isl_set_is_subset(dom2, dom1);
717 isl_set_free(dom1);
718 isl_set_free(dom2);
719
720 if (is_subset < 0 || !is_subset)
721 return is_subset;
722
723 for (i = 0; i < pwf2->n; ++i) {
724 for (j = 0; j < pwf1->n; ++j) {
725 int is_empty;
726 isl_set *common;
727 int covers;
728
729 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
730 isl_set_copy(pwf2->p[i].set));
731 is_empty = isl_set_is_empty(common);
732 if (is_empty < 0 || is_empty) {
733 isl_set_free(common);
734 if (is_empty < 0)
735 return -1;
736 continue;
737 }
738 covers = qpolynomial_fold_covers_on_domain(common,
739 pwf1->p[j].fold, pwf2->p[i].fold);
740 isl_set_free(common);
741 if (covers < 0 || !covers)
742 return covers;
743 }
744 }
745
746 return 1;
747 }
748
749 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
750 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
751 {
752 int i;
753 isl_ctx *ctx;
754
755 if (!fold || !morph)
756 goto error;
757
758 ctx = fold->dim->ctx;
759 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
760
761 fold = isl_qpolynomial_fold_cow(fold);
762 if (!fold)
763 goto error;
764
765 isl_dim_free(fold->dim);
766 fold->dim = isl_dim_copy(morph->ran->dim);
767 if (!fold->dim)
768 goto error;
769
770 for (i = 0; i < fold->n; ++i) {
771 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
772 isl_morph_copy(morph));
773 if (!fold->qp[i])
774 goto error;
775 }
776
777 isl_morph_free(morph);
778
779 return fold;
780 error:
781 isl_qpolynomial_fold_free(fold);
782 isl_morph_free(morph);
783 return NULL;
784 }
785
786 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
787 {
788 if (!fold)
789 return isl_fold_list;
790 return fold->type;
791 }
792
793 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
794 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
795 {
796 int i;
797 isl_ctx *ctx;
798
799 if (!fold || !dim)
800 goto error;
801
802 if (isl_dim_equal(fold->dim, dim)) {
803 isl_dim_free(dim);
804 return fold;
805 }
806
807 fold = isl_qpolynomial_fold_cow(fold);
808 if (!fold)
809 goto error;
810
811 isl_dim_free(fold->dim);
812 fold->dim = isl_dim_copy(dim);
813 if (!fold->dim)
814 goto error;
815
816 for (i = 0; i < fold->n; ++i) {
817 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
818 isl_dim_copy(dim));
819 if (!fold->qp[i])
820 goto error;
821 }
822
823 isl_dim_free(dim);
824
825 return fold;
826 error:
827 isl_qpolynomial_fold_free(fold);
828 isl_dim_free(dim);
829 return NULL;
830 }
831
832 int isl_qpolynomial_fold_foreach_qpolynomial(
833 __isl_keep isl_qpolynomial_fold *fold,
834 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
835 {
836 int i;
837
838 if (!fold)
839 return -1;
840
841 for (i = 0; i < fold->n; ++i)
842 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
843 return -1;
844
845 return 0;
846 }
847
848 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
849 __isl_take isl_qpolynomial_fold *fold,
850 enum isl_dim_type dst_type, unsigned dst_pos,
851 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
852 {
853 int i;
854
855 if (n == 0)
856 return fold;
857
858 fold = isl_qpolynomial_fold_cow(fold);
859 if (!fold)
860 return NULL;
861
862 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
863 src_type, src_pos, n);
864 if (!fold->dim)
865 goto error;
866
867 for (i = 0; i < fold->n; ++i) {
868 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
869 dst_type, dst_pos, src_type, src_pos, n);
870 if (!fold->qp[i])
871 goto error;
872 }
873
874 return fold;
875 error:
876 isl_qpolynomial_fold_free(fold);
877 return NULL;
878 }
Integer set library