?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_equalities.c: fix typo in comment
[isl.git] / isl_polynomial.c
blob72692240e5bd78fa72def33adfbe5c6405fb48e3
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 <stdlib.h>
12 #include <isl_seq.h>
13 #include <isl_polynomial_private.h>
14 #include <isl_point_private.h>
15 #include <isl_dim.h>
16 #include <isl_map_private.h>
17
18 static unsigned pos(__isl_keep isl_dim *dim, enum isl_dim_type type)
19 {
20 switch (type) {
21 case isl_dim_param: return 0;
22 case isl_dim_in: return dim->nparam;
23 case isl_dim_out: return dim->nparam + dim->n_in;
24 }
25 }
26
27 int isl_upoly_is_cst(__isl_keep struct isl_upoly *up)
28 {
29 if (!up)
30 return -1;
31
32 return up->var < 0;
33 }
34
35 __isl_keep struct isl_upoly_cst *isl_upoly_as_cst(__isl_keep struct isl_upoly *up)
36 {
37 if (!up)
38 return NULL;
39
40 isl_assert(up->ctx, up->var < 0, return NULL);
41
42 return (struct isl_upoly_cst *)up;
43 }
44
45 __isl_keep struct isl_upoly_rec *isl_upoly_as_rec(__isl_keep struct isl_upoly *up)
46 {
47 if (!up)
48 return NULL;
49
50 isl_assert(up->ctx, up->var >= 0, return NULL);
51
52 return (struct isl_upoly_rec *)up;
53 }
54
55 int isl_upoly_is_equal(__isl_keep struct isl_upoly *up1,
56 __isl_keep struct isl_upoly *up2)
57 {
58 int i;
59 struct isl_upoly_rec *rec1, *rec2;
60
61 if (!up1 || !up2)
62 return -1;
63 if (up1 == up2)
64 return 1;
65 if (up1->var != up2->var)
66 return 0;
67 if (isl_upoly_is_cst(up1)) {
68 struct isl_upoly_cst *cst1, *cst2;
69 cst1 = isl_upoly_as_cst(up1);
70 cst2 = isl_upoly_as_cst(up2);
71 if (!cst1 || !cst2)
72 return -1;
73 return isl_int_eq(cst1->n, cst2->n) &&
74 isl_int_eq(cst1->d, cst2->d);
75 }
76
77 rec1 = isl_upoly_as_rec(up1);
78 rec2 = isl_upoly_as_rec(up2);
79 if (!rec1 || !rec2)
80 return -1;
81
82 if (rec1->n != rec2->n)
83 return 0;
84
85 for (i = 0; i < rec1->n; ++i) {
86 int eq = isl_upoly_is_equal(rec1->p[i], rec2->p[i]);
87 if (eq < 0 || !eq)
88 return eq;
89 }
90
91 return 1;
92 }
93
94 int isl_upoly_is_zero(__isl_keep struct isl_upoly *up)
95 {
96 struct isl_upoly_cst *cst;
97
98 if (!up)
99 return -1;
100 if (!isl_upoly_is_cst(up))
101 return 0;
102
103 cst = isl_upoly_as_cst(up);
104 if (!cst)
105 return -1;
106
107 return isl_int_is_zero(cst->n) && isl_int_is_pos(cst->d);
108 }
109
110 int isl_upoly_sgn(__isl_keep struct isl_upoly *up)
111 {
112 struct isl_upoly_cst *cst;
113
114 if (!up)
115 return 0;
116 if (!isl_upoly_is_cst(up))
117 return 0;
118
119 cst = isl_upoly_as_cst(up);
120 if (!cst)
121 return 0;
122
123 return isl_int_sgn(cst->n);
124 }
125
126 int isl_upoly_is_nan(__isl_keep struct isl_upoly *up)
127 {
128 struct isl_upoly_cst *cst;
129
130 if (!up)
131 return -1;
132 if (!isl_upoly_is_cst(up))
133 return 0;
134
135 cst = isl_upoly_as_cst(up);
136 if (!cst)
137 return -1;
138
139 return isl_int_is_zero(cst->n) && isl_int_is_zero(cst->d);
140 }
141
142 int isl_upoly_is_infty(__isl_keep struct isl_upoly *up)
143 {
144 struct isl_upoly_cst *cst;
145
146 if (!up)
147 return -1;
148 if (!isl_upoly_is_cst(up))
149 return 0;
150
151 cst = isl_upoly_as_cst(up);
152 if (!cst)
153 return -1;
154
155 return isl_int_is_pos(cst->n) && isl_int_is_zero(cst->d);
156 }
157
158 int isl_upoly_is_neginfty(__isl_keep struct isl_upoly *up)
159 {
160 struct isl_upoly_cst *cst;
161
162 if (!up)
163 return -1;
164 if (!isl_upoly_is_cst(up))
165 return 0;
166
167 cst = isl_upoly_as_cst(up);
168 if (!cst)
169 return -1;
170
171 return isl_int_is_neg(cst->n) && isl_int_is_zero(cst->d);
172 }
173
174 int isl_upoly_is_one(__isl_keep struct isl_upoly *up)
175 {
176 struct isl_upoly_cst *cst;
177
178 if (!up)
179 return -1;
180 if (!isl_upoly_is_cst(up))
181 return 0;
182
183 cst = isl_upoly_as_cst(up);
184 if (!cst)
185 return -1;
186
187 return isl_int_eq(cst->n, cst->d) && isl_int_is_pos(cst->d);
188 }
189
190 int isl_upoly_is_negone(__isl_keep struct isl_upoly *up)
191 {
192 struct isl_upoly_cst *cst;
193
194 if (!up)
195 return -1;
196 if (!isl_upoly_is_cst(up))
197 return 0;
198
199 cst = isl_upoly_as_cst(up);
200 if (!cst)
201 return -1;
202
203 return isl_int_is_negone(cst->n) && isl_int_is_one(cst->d);
204 }
205
206 __isl_give struct isl_upoly_cst *isl_upoly_cst_alloc(struct isl_ctx *ctx)
207 {
208 struct isl_upoly_cst *cst;
209
210 cst = isl_alloc_type(ctx, struct isl_upoly_cst);
211 if (!cst)
212 return NULL;
213
214 cst->up.ref = 1;
215 cst->up.ctx = ctx;
216 isl_ctx_ref(ctx);
217 cst->up.var = -1;
218
219 isl_int_init(cst->n);
220 isl_int_init(cst->d);
221
222 return cst;
223 }
224
225 __isl_give struct isl_upoly *isl_upoly_zero(struct isl_ctx *ctx)
226 {
227 struct isl_upoly_cst *cst;
228
229 cst = isl_upoly_cst_alloc(ctx);
230 if (!cst)
231 return NULL;
232
233 isl_int_set_si(cst->n, 0);
234 isl_int_set_si(cst->d, 1);
235
236 return &cst->up;
237 }
238
239 __isl_give struct isl_upoly *isl_upoly_infty(struct isl_ctx *ctx)
240 {
241 struct isl_upoly_cst *cst;
242
243 cst = isl_upoly_cst_alloc(ctx);
244 if (!cst)
245 return NULL;
246
247 isl_int_set_si(cst->n, 1);
248 isl_int_set_si(cst->d, 0);
249
250 return &cst->up;
251 }
252
253 __isl_give struct isl_upoly *isl_upoly_neginfty(struct isl_ctx *ctx)
254 {
255 struct isl_upoly_cst *cst;
256
257 cst = isl_upoly_cst_alloc(ctx);
258 if (!cst)
259 return NULL;
260
261 isl_int_set_si(cst->n, -1);
262 isl_int_set_si(cst->d, 0);
263
264 return &cst->up;
265 }
266
267 __isl_give struct isl_upoly *isl_upoly_nan(struct isl_ctx *ctx)
268 {
269 struct isl_upoly_cst *cst;
270
271 cst = isl_upoly_cst_alloc(ctx);
272 if (!cst)
273 return NULL;
274
275 isl_int_set_si(cst->n, 0);
276 isl_int_set_si(cst->d, 0);
277
278 return &cst->up;
279 }
280
281 __isl_give struct isl_upoly *isl_upoly_rat_cst(struct isl_ctx *ctx,
282 isl_int n, isl_int d)
283 {
284 struct isl_upoly_cst *cst;
285
286 cst = isl_upoly_cst_alloc(ctx);
287 if (!cst)
288 return NULL;
289
290 isl_int_set(cst->n, n);
291 isl_int_set(cst->d, d);
292
293 return &cst->up;
294 }
295
296 __isl_give struct isl_upoly_rec *isl_upoly_alloc_rec(struct isl_ctx *ctx,
297 int var, int size)
298 {
299 struct isl_upoly_rec *rec;
300
301 isl_assert(ctx, var >= 0, return NULL);
302 isl_assert(ctx, size >= 0, return NULL);
303 rec = isl_calloc(dim->ctx, struct isl_upoly_rec,
304 sizeof(struct isl_upoly_rec) +
305 (size - 1) * sizeof(struct isl_upoly *));
306 if (!rec)
307 return NULL;
308
309 rec->up.ref = 1;
310 rec->up.ctx = ctx;
311 isl_ctx_ref(ctx);
312 rec->up.var = var;
313
314 rec->n = 0;
315 rec->size = size;
316
317 return rec;
318 error:
319 isl_upoly_free(&rec->up);
320 return NULL;
321 }
322
323 isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp)
324 {
325 return qp ? qp->dim->ctx : NULL;
326 }
327
328 __isl_give isl_dim *isl_qpolynomial_get_dim(__isl_keep isl_qpolynomial *qp)
329 {
330 return qp ? isl_dim_copy(qp->dim) : NULL;
331 }
332
333 int isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp)
334 {
335 return qp ? isl_upoly_is_zero(qp->upoly) : -1;
336 }
337
338 int isl_qpolynomial_is_one(__isl_keep isl_qpolynomial *qp)
339 {
340 return qp ? isl_upoly_is_one(qp->upoly) : -1;
341 }
342
343 int isl_qpolynomial_is_nan(__isl_keep isl_qpolynomial *qp)
344 {
345 return qp ? isl_upoly_is_nan(qp->upoly) : -1;
346 }
347
348 int isl_qpolynomial_is_infty(__isl_keep isl_qpolynomial *qp)
349 {
350 return qp ? isl_upoly_is_infty(qp->upoly) : -1;
351 }
352
353 int isl_qpolynomial_is_neginfty(__isl_keep isl_qpolynomial *qp)
354 {
355 return qp ? isl_upoly_is_neginfty(qp->upoly) : -1;
356 }
357
358 int isl_qpolynomial_sgn(__isl_keep isl_qpolynomial *qp)
359 {
360 return qp ? isl_upoly_sgn(qp->upoly) : 0;
361 }
362
363 static void upoly_free_cst(__isl_take struct isl_upoly_cst *cst)
364 {
365 isl_int_clear(cst->n);
366 isl_int_clear(cst->d);
367 }
368
369 static void upoly_free_rec(__isl_take struct isl_upoly_rec *rec)
370 {
371 int i;
372
373 for (i = 0; i < rec->n; ++i)
374 isl_upoly_free(rec->p[i]);
375 }
376
377 __isl_give struct isl_upoly *isl_upoly_copy(__isl_keep struct isl_upoly *up)
378 {
379 if (!up)
380 return NULL;
381
382 up->ref++;
383 return up;
384 }
385
386 __isl_give struct isl_upoly *isl_upoly_dup_cst(__isl_keep struct isl_upoly *up)
387 {
388 struct isl_upoly_cst *cst;
389 struct isl_upoly_cst *dup;
390
391 cst = isl_upoly_as_cst(up);
392 if (!cst)
393 return NULL;
394
395 dup = isl_upoly_as_cst(isl_upoly_zero(up->ctx));
396 if (!dup)
397 return NULL;
398 isl_int_set(dup->n, cst->n);
399 isl_int_set(dup->d, cst->d);
400
401 return &dup->up;
402 }
403
404 __isl_give struct isl_upoly *isl_upoly_dup_rec(__isl_keep struct isl_upoly *up)
405 {
406 int i;
407 struct isl_upoly_rec *rec;
408 struct isl_upoly_rec *dup;
409
410 rec = isl_upoly_as_rec(up);
411 if (!rec)
412 return NULL;
413
414 dup = isl_upoly_alloc_rec(up->ctx, up->var, rec->n);
415 if (!dup)
416 return NULL;
417
418 for (i = 0; i < rec->n; ++i) {
419 dup->p[i] = isl_upoly_copy(rec->p[i]);
420 if (!dup->p[i])
421 goto error;
422 dup->n++;
423 }
424
425 return &dup->up;
426 error:
427 isl_upoly_free(&dup->up);
428 return NULL;
429 }
430
431 __isl_give struct isl_upoly *isl_upoly_dup(__isl_keep struct isl_upoly *up)
432 {
433 struct isl_upoly *dup;
434
435 if (!up)
436 return NULL;
437
438 if (isl_upoly_is_cst(up))
439 return isl_upoly_dup_cst(up);
440 else
441 return isl_upoly_dup_rec(up);
442 }
443
444 __isl_give struct isl_upoly *isl_upoly_cow(__isl_take struct isl_upoly *up)
445 {
446 if (!up)
447 return NULL;
448
449 if (up->ref == 1)
450 return up;
451 up->ref--;
452 return isl_upoly_dup(up);
453 }
454
455 void isl_upoly_free(__isl_take struct isl_upoly *up)
456 {
457 if (!up)
458 return;
459
460 if (--up->ref > 0)
461 return;
462
463 if (up->var < 0)
464 upoly_free_cst((struct isl_upoly_cst *)up);
465 else
466 upoly_free_rec((struct isl_upoly_rec *)up);
467
468 isl_ctx_deref(up->ctx);
469 free(up);
470 }
471
472 static void isl_upoly_cst_reduce(__isl_keep struct isl_upoly_cst *cst)
473 {
474 isl_int gcd;
475
476 isl_int_init(gcd);
477 isl_int_gcd(gcd, cst->n, cst->d);
478 if (!isl_int_is_zero(gcd) && !isl_int_is_one(gcd)) {
479 isl_int_divexact(cst->n, cst->n, gcd);
480 isl_int_divexact(cst->d, cst->d, gcd);
481 }
482 isl_int_clear(gcd);
483 }
484
485 __isl_give struct isl_upoly *isl_upoly_sum_cst(__isl_take struct isl_upoly *up1,
486 __isl_take struct isl_upoly *up2)
487 {
488 struct isl_upoly_cst *cst1;
489 struct isl_upoly_cst *cst2;
490
491 up1 = isl_upoly_cow(up1);
492 if (!up1 || !up2)
493 goto error;
494
495 cst1 = isl_upoly_as_cst(up1);
496 cst2 = isl_upoly_as_cst(up2);
497
498 if (isl_int_eq(cst1->d, cst2->d))
499 isl_int_add(cst1->n, cst1->n, cst2->n);
500 else {
501 isl_int_mul(cst1->n, cst1->n, cst2->d);
502 isl_int_addmul(cst1->n, cst2->n, cst1->d);
503 isl_int_mul(cst1->d, cst1->d, cst2->d);
504 }
505
506 isl_upoly_cst_reduce(cst1);
507
508 isl_upoly_free(up2);
509 return up1;
510 error:
511 isl_upoly_free(up1);
512 isl_upoly_free(up2);
513 return NULL;
514 }
515
516 static __isl_give struct isl_upoly *replace_by_zero(
517 __isl_take struct isl_upoly *up)
518 {
519 struct isl_ctx *ctx;
520
521 if (!up)
522 return NULL;
523 ctx = up->ctx;
524 isl_upoly_free(up);
525 return isl_upoly_zero(ctx);
526 }
527
528 static __isl_give struct isl_upoly *replace_by_constant_term(
529 __isl_take struct isl_upoly *up)
530 {
531 struct isl_upoly_rec *rec;
532 struct isl_upoly *cst;
533
534 if (!up)
535 return NULL;
536
537 rec = isl_upoly_as_rec(up);
538 if (!rec)
539 goto error;
540 cst = isl_upoly_copy(rec->p[0]);
541 isl_upoly_free(up);
542 return cst;
543 error:
544 isl_upoly_free(up);
545 return NULL;
546 }
547
548 __isl_give struct isl_upoly *isl_upoly_sum(__isl_take struct isl_upoly *up1,
549 __isl_take struct isl_upoly *up2)
550 {
551 int i;
552 struct isl_upoly_rec *rec1, *rec2;
553
554 if (!up1 || !up2)
555 goto error;
556
557 if (isl_upoly_is_nan(up1)) {
558 isl_upoly_free(up2);
559 return up1;
560 }
561
562 if (isl_upoly_is_nan(up2)) {
563 isl_upoly_free(up1);
564 return up2;
565 }
566
567 if (isl_upoly_is_zero(up1)) {
568 isl_upoly_free(up1);
569 return up2;
570 }
571
572 if (isl_upoly_is_zero(up2)) {
573 isl_upoly_free(up2);
574 return up1;
575 }
576
577 if (up1->var < up2->var)
578 return isl_upoly_sum(up2, up1);
579
580 if (up2->var < up1->var) {
581 struct isl_upoly_rec *rec;
582 if (isl_upoly_is_infty(up2) || isl_upoly_is_neginfty(up2)) {
583 isl_upoly_free(up1);
584 return up2;
585 }
586 up1 = isl_upoly_cow(up1);
587 rec = isl_upoly_as_rec(up1);
588 if (!rec)
589 goto error;
590 rec->p[0] = isl_upoly_sum(rec->p[0], up2);
591 if (rec->n == 1)
592 up1 = replace_by_constant_term(up1);
593 return up1;
594 }
595
596 if (isl_upoly_is_cst(up1))
597 return isl_upoly_sum_cst(up1, up2);
598
599 rec1 = isl_upoly_as_rec(up1);
600 rec2 = isl_upoly_as_rec(up2);
601 if (!rec1 || !rec2)
602 goto error;
603
604 if (rec1->n < rec2->n)
605 return isl_upoly_sum(up2, up1);
606
607 up1 = isl_upoly_cow(up1);
608 rec1 = isl_upoly_as_rec(up1);
609 if (!rec1)
610 goto error;
611
612 for (i = rec2->n - 1; i >= 0; --i) {
613 rec1->p[i] = isl_upoly_sum(rec1->p[i],
614 isl_upoly_copy(rec2->p[i]));
615 if (!rec1->p[i])
616 goto error;
617 if (i == rec1->n - 1 && isl_upoly_is_zero(rec1->p[i])) {
618 isl_upoly_free(rec1->p[i]);
619 rec1->n--;
620 }
621 }
622
623 if (rec1->n == 0)
624 up1 = replace_by_zero(up1);
625 else if (rec1->n == 1)
626 up1 = replace_by_constant_term(up1);
627
628 isl_upoly_free(up2);
629
630 return up1;
631 error:
632 isl_upoly_free(up1);
633 isl_upoly_free(up2);
634 return NULL;
635 }
636
637 __isl_give struct isl_upoly *isl_upoly_neg_cst(__isl_take struct isl_upoly *up)
638 {
639 struct isl_upoly_cst *cst;
640
641 if (isl_upoly_is_zero(up))
642 return up;
643
644 up = isl_upoly_cow(up);
645 if (!up)
646 return NULL;
647
648 cst = isl_upoly_as_cst(up);
649
650 isl_int_neg(cst->n, cst->n);
651
652 return up;
653 }
654
655 __isl_give struct isl_upoly *isl_upoly_neg(__isl_take struct isl_upoly *up)
656 {
657 int i;
658 struct isl_upoly_rec *rec;
659
660 if (!up)
661 return NULL;
662
663 if (isl_upoly_is_cst(up))
664 return isl_upoly_neg_cst(up);
665
666 up = isl_upoly_cow(up);
667 rec = isl_upoly_as_rec(up);
668 if (!rec)
669 goto error;
670
671 for (i = 0; i < rec->n; ++i) {
672 rec->p[i] = isl_upoly_neg(rec->p[i]);
673 if (!rec->p[i])
674 goto error;
675 }
676
677 return up;
678 error:
679 isl_upoly_free(up);
680 return NULL;
681 }
682
683 __isl_give struct isl_upoly *isl_upoly_mul_cst(__isl_take struct isl_upoly *up1,
684 __isl_take struct isl_upoly *up2)
685 {
686 struct isl_upoly_cst *cst1;
687 struct isl_upoly_cst *cst2;
688
689 up1 = isl_upoly_cow(up1);
690 if (!up1 || !up2)
691 goto error;
692
693 cst1 = isl_upoly_as_cst(up1);
694 cst2 = isl_upoly_as_cst(up2);
695
696 isl_int_mul(cst1->n, cst1->n, cst2->n);
697 isl_int_mul(cst1->d, cst1->d, cst2->d);
698
699 isl_upoly_cst_reduce(cst1);
700
701 isl_upoly_free(up2);
702 return up1;
703 error:
704 isl_upoly_free(up1);
705 isl_upoly_free(up2);
706 return NULL;
707 }
708
709 __isl_give struct isl_upoly *isl_upoly_mul_rec(__isl_take struct isl_upoly *up1,
710 __isl_take struct isl_upoly *up2)
711 {
712 struct isl_upoly_rec *rec1;
713 struct isl_upoly_rec *rec2;
714 struct isl_upoly_rec *res;
715 int i, j;
716 int size;
717
718 rec1 = isl_upoly_as_rec(up1);
719 rec2 = isl_upoly_as_rec(up2);
720 if (!rec1 || !rec2)
721 goto error;
722 size = rec1->n + rec2->n - 1;
723 res = isl_upoly_alloc_rec(up1->ctx, up1->var, size);
724 if (!res)
725 goto error;
726
727 for (i = 0; i < rec1->n; ++i) {
728 res->p[i] = isl_upoly_mul(isl_upoly_copy(rec2->p[0]),
729 isl_upoly_copy(rec1->p[i]));
730 if (!res->p[i])
731 goto error;
732 res->n++;
733 }
734 for (; i < size; ++i) {
735 res->p[i] = isl_upoly_zero(up1->ctx);
736 if (!res->p[i])
737 goto error;
738 res->n++;
739 }
740 for (i = 0; i < rec1->n; ++i) {
741 for (j = 1; j < rec2->n; ++j) {
742 struct isl_upoly *up;
743 up = isl_upoly_mul(isl_upoly_copy(rec2->p[j]),
744 isl_upoly_copy(rec1->p[i]));
745 res->p[i + j] = isl_upoly_sum(res->p[i + j], up);
746 if (!res->p[i + j])
747 goto error;
748 }
749 }
750
751 isl_upoly_free(up1);
752 isl_upoly_free(up2);
753
754 return &res->up;
755 error:
756 isl_upoly_free(up1);
757 isl_upoly_free(up2);
758 isl_upoly_free(&res->up);
759 return NULL;
760 }
761
762 __isl_give struct isl_upoly *isl_upoly_mul(__isl_take struct isl_upoly *up1,
763 __isl_take struct isl_upoly *up2)
764 {
765 if (!up1 || !up2)
766 goto error;
767
768 if (isl_upoly_is_nan(up1)) {
769 isl_upoly_free(up2);
770 return up1;
771 }
772
773 if (isl_upoly_is_nan(up2)) {
774 isl_upoly_free(up1);
775 return up2;
776 }
777
778 if (isl_upoly_is_zero(up1)) {
779 isl_upoly_free(up2);
780 return up1;
781 }
782
783 if (isl_upoly_is_zero(up2)) {
784 isl_upoly_free(up1);
785 return up2;
786 }
787
788 if (isl_upoly_is_one(up1)) {
789 isl_upoly_free(up1);
790 return up2;
791 }
792
793 if (isl_upoly_is_one(up2)) {
794 isl_upoly_free(up2);
795 return up1;
796 }
797
798 if (up1->var < up2->var)
799 return isl_upoly_mul(up2, up1);
800
801 if (up2->var < up1->var) {
802 int i;
803 struct isl_upoly_rec *rec;
804 if (isl_upoly_is_infty(up2) || isl_upoly_is_neginfty(up2)) {
805 isl_ctx *ctx = up1->ctx;
806 isl_upoly_free(up1);
807 isl_upoly_free(up2);
808 return isl_upoly_nan(ctx);
809 }
810 up1 = isl_upoly_cow(up1);
811 rec = isl_upoly_as_rec(up1);
812 if (!rec)
813 goto error;
814
815 for (i = 0; i < rec->n; ++i) {
816 rec->p[i] = isl_upoly_mul(rec->p[i],
817 isl_upoly_copy(up2));
818 if (!rec->p[i])
819 goto error;
820 }
821 isl_upoly_free(up2);
822 return up1;
823 }
824
825 if (isl_upoly_is_cst(up1))
826 return isl_upoly_mul_cst(up1, up2);
827
828 return isl_upoly_mul_rec(up1, up2);
829 error:
830 isl_upoly_free(up1);
831 isl_upoly_free(up2);
832 return NULL;
833 }
834
835 __isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_dim *dim,
836 unsigned n_div, __isl_take struct isl_upoly *up)
837 {
838 struct isl_qpolynomial *qp = NULL;
839 unsigned total;
840
841 if (!dim || !up)
842 goto error;
843
844 total = isl_dim_total(dim);
845
846 qp = isl_calloc_type(dim->ctx, struct isl_qpolynomial);
847 if (!qp)
848 goto error;
849
850 qp->ref = 1;
851 qp->div = isl_mat_alloc(dim->ctx, n_div, 1 + 1 + total + n_div);
852 if (!qp->div)
853 goto error;
854
855 qp->dim = dim;
856 qp->upoly = up;
857
858 return qp;
859 error:
860 isl_dim_free(dim);
861 isl_upoly_free(up);
862 isl_qpolynomial_free(qp);
863 return NULL;
864 }
865
866 __isl_give isl_qpolynomial *isl_qpolynomial_copy(__isl_keep isl_qpolynomial *qp)
867 {
868 if (!qp)
869 return NULL;
870
871 qp->ref++;
872 return qp;
873 }
874
875 __isl_give isl_qpolynomial *isl_qpolynomial_dup(__isl_keep isl_qpolynomial *qp)
876 {
877 struct isl_qpolynomial *dup;
878
879 if (!qp)
880 return NULL;
881
882 dup = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row,
883 isl_upoly_copy(qp->upoly));
884 if (!dup)
885 return NULL;
886 isl_mat_free(dup->div);
887 dup->div = isl_mat_copy(qp->div);
888 if (!dup->div)
889 goto error;
890
891 return dup;
892 error:
893 isl_qpolynomial_free(dup);
894 return NULL;
895 }
896
897 __isl_give isl_qpolynomial *isl_qpolynomial_cow(__isl_take isl_qpolynomial *qp)
898 {
899 if (!qp)
900 return NULL;
901
902 if (qp->ref == 1)
903 return qp;
904 qp->ref--;
905 return isl_qpolynomial_dup(qp);
906 }
907
908 void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp)
909 {
910 if (!qp)
911 return;
912
913 if (--qp->ref > 0)
914 return;
915
916 isl_dim_free(qp->dim);
917 isl_mat_free(qp->div);
918 isl_upoly_free(qp->upoly);
919
920 free(qp);
921 }
922
923 static int compatible_divs(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
924 {
925 int n_row, n_col;
926 int equal;
927
928 isl_assert(div1->ctx, div1->n_row >= div2->n_row &&
929 div1->n_col >= div2->n_col, return -1);
930
931 if (div1->n_row == div2->n_row)
932 return isl_mat_is_equal(div1, div2);
933
934 n_row = div1->n_row;
935 n_col = div1->n_col;
936 div1->n_row = div2->n_row;
937 div1->n_col = div2->n_col;
938
939 equal = isl_mat_is_equal(div1, div2);
940
941 div1->n_row = n_row;
942 div1->n_col = n_col;
943
944 return equal;
945 }
946
947 static void expand_row(__isl_keep isl_mat *dst, int d,
948 __isl_keep isl_mat *src, int s, int *exp)
949 {
950 int i;
951 unsigned c = src->n_col - src->n_row;
952
953 isl_seq_cpy(dst->row[d], src->row[s], c);
954 isl_seq_clr(dst->row[d] + c, dst->n_col - c);
955
956 for (i = 0; i < s; ++i)
957 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
958 }
959
960 static int cmp_row(__isl_keep isl_mat *div, int i, int j)
961 {
962 int li, lj;
963
964 li = isl_seq_last_non_zero(div->row[i], div->n_col);
965 lj = isl_seq_last_non_zero(div->row[j], div->n_col);
966
967 if (li != lj)
968 return li - lj;
969
970 return isl_seq_cmp(div->row[i], div->row[j], div->n_col);
971 }
972
973 struct isl_div_sort_info {
974 isl_mat *div;
975 int row;
976 };
977
978 static int div_sort_cmp(const void *p1, const void *p2)
979 {
980 const struct isl_div_sort_info *i1, *i2;
981 i1 = (const struct isl_div_sort_info *) p1;
982 i2 = (const struct isl_div_sort_info *) p2;
983
984 return cmp_row(i1->div, i1->row, i2->row);
985 }
986
987 static __isl_give isl_mat *sort_divs(__isl_take isl_mat *div)
988 {
989 int i;
990 struct isl_div_sort_info *array = NULL;
991 int *pos = NULL;
992
993 if (!div)
994 return NULL;
995 if (div->n_row <= 1)
996 return div;
997
998 array = isl_alloc_array(div->ctx, struct isl_div_sort_info, div->n_row);
999 pos = isl_alloc_array(div->ctx, int, div->n_row);
1000 if (!array || !pos)
1001 goto error;
1002
1003 for (i = 0; i < div->n_row; ++i) {
1004 array[i].div = div;
1005 array[i].row = i;
1006 pos[i] = i;
1007 }
1008
1009 qsort(array, div->n_row, sizeof(struct isl_div_sort_info),
1010 div_sort_cmp);
1011
1012 for (i = 0; i < div->n_row; ++i) {
1013 int t;
1014 if (pos[array[i].row] == i)
1015 continue;
1016 div = isl_mat_cow(div);
1017 div = isl_mat_swap_rows(div, i, pos[array[i].row]);
1018 t = pos[array[i].row];
1019 pos[array[i].row] = pos[i];
1020 pos[i] = t;
1021 }
1022
1023 free(array);
1024
1025 return div;
1026 error:
1027 free(pos);
1028 free(array);
1029 isl_mat_free(div);
1030 return NULL;
1031 }
1032
1033 static __isl_give isl_mat *merge_divs(__isl_keep isl_mat *div1,
1034 __isl_keep isl_mat *div2, int *exp1, int *exp2)
1035 {
1036 int i, j, k;
1037 isl_mat *div = NULL;
1038 unsigned d = div1->n_col - div1->n_row;
1039
1040 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
1041 d + div1->n_row + div2->n_row);
1042 if (!div)
1043 return NULL;
1044
1045 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
1046 int cmp;
1047
1048 expand_row(div, k, div1, i, exp1);
1049 expand_row(div, k + 1, div2, j, exp2);
1050
1051 cmp = cmp_row(div, k, k + 1);
1052 if (cmp == 0) {
1053 exp1[i++] = k;
1054 exp2[j++] = k;
1055 } else if (cmp < 0) {
1056 exp1[i++] = k;
1057 } else {
1058 exp2[j++] = k;
1059 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
1060 }
1061 }
1062 for (; i < div1->n_row; ++i, ++k) {
1063 expand_row(div, k, div1, i, exp1);
1064 exp1[i] = k;
1065 }
1066 for (; j < div2->n_row; ++j, ++k) {
1067 expand_row(div, k, div2, j, exp2);
1068 exp2[j] = k;
1069 }
1070
1071 div->n_row = k;
1072 div->n_col = d + k;
1073
1074 return div;
1075 }
1076
1077 static __isl_give struct isl_upoly *expand(__isl_take struct isl_upoly *up,
1078 int *exp, int first)
1079 {
1080 int i;
1081 struct isl_upoly_rec *rec;
1082
1083 if (isl_upoly_is_cst(up))
1084 return up;
1085
1086 if (up->var < first)
1087 return up;
1088
1089 if (exp[up->var - first] == up->var - first)
1090 return up;
1091
1092 up = isl_upoly_cow(up);
1093 if (!up)
1094 goto error;
1095
1096 up->var = exp[up->var - first] + first;
1097
1098 rec = isl_upoly_as_rec(up);
1099 if (!rec)
1100 goto error;
1101
1102 for (i = 0; i < rec->n; ++i) {
1103 rec->p[i] = expand(rec->p[i], exp, first);
1104 if (!rec->p[i])
1105 goto error;
1106 }
1107
1108 return up;
1109 error:
1110 isl_upoly_free(up);
1111 return NULL;
1112 }
1113
1114 static __isl_give isl_qpolynomial *with_merged_divs(
1115 __isl_give isl_qpolynomial *(*fn)(__isl_take isl_qpolynomial *qp1,
1116 __isl_take isl_qpolynomial *qp2),
1117 __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2)
1118 {
1119 int *exp1 = NULL;
1120 int *exp2 = NULL;
1121 isl_mat *div = NULL;
1122
1123 qp1 = isl_qpolynomial_cow(qp1);
1124 qp2 = isl_qpolynomial_cow(qp2);
1125
1126 if (!qp1 || !qp2)
1127 goto error;
1128
1129 isl_assert(qp1->div->ctx, qp1->div->n_row >= qp2->div->n_row &&
1130 qp1->div->n_col >= qp2->div->n_col, goto error);
1131
1132 exp1 = isl_alloc_array(qp1->div->ctx, int, qp1->div->n_row);
1133 exp2 = isl_alloc_array(qp2->div->ctx, int, qp2->div->n_row);
1134 if (!exp1 || !exp2)
1135 goto error;
1136
1137 div = merge_divs(qp1->div, qp2->div, exp1, exp2);
1138 if (!div)
1139 goto error;
1140
1141 isl_mat_free(qp1->div);
1142 qp1->div = isl_mat_copy(div);
1143 isl_mat_free(qp2->div);
1144 qp2->div = isl_mat_copy(div);
1145
1146 qp1->upoly = expand(qp1->upoly, exp1, div->n_col - div->n_row - 2);
1147 qp2->upoly = expand(qp2->upoly, exp2, div->n_col - div->n_row - 2);
1148
1149 if (!qp1->upoly || !qp2->upoly)
1150 goto error;
1151
1152 isl_mat_free(div);
1153 free(exp1);
1154 free(exp2);
1155
1156 return fn(qp1, qp2);
1157 error:
1158 isl_mat_free(div);
1159 free(exp1);
1160 free(exp2);
1161 isl_qpolynomial_free(qp1);
1162 isl_qpolynomial_free(qp2);
1163 return NULL;
1164 }
1165
1166 __isl_give isl_qpolynomial *isl_qpolynomial_add(__isl_take isl_qpolynomial *qp1,
1167 __isl_take isl_qpolynomial *qp2)
1168 {
1169 qp1 = isl_qpolynomial_cow(qp1);
1170
1171 if (!qp1 || !qp2)
1172 goto error;
1173
1174 if (qp1->div->n_row < qp2->div->n_row)
1175 return isl_qpolynomial_add(qp2, qp1);
1176
1177 isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
1178 if (!compatible_divs(qp1->div, qp2->div))
1179 return with_merged_divs(isl_qpolynomial_add, qp1, qp2);
1180
1181 qp1->upoly = isl_upoly_sum(qp1->upoly, isl_upoly_copy(qp2->upoly));
1182 if (!qp1->upoly)
1183 goto error;
1184
1185 isl_qpolynomial_free(qp2);
1186
1187 return qp1;
1188 error:
1189 isl_qpolynomial_free(qp1);
1190 isl_qpolynomial_free(qp2);
1191 return NULL;
1192 }
1193
1194 __isl_give isl_qpolynomial *isl_qpolynomial_sub(__isl_take isl_qpolynomial *qp1,
1195 __isl_take isl_qpolynomial *qp2)
1196 {
1197 return isl_qpolynomial_add(qp1, isl_qpolynomial_neg(qp2));
1198 }
1199
1200 __isl_give isl_qpolynomial *isl_qpolynomial_neg(__isl_take isl_qpolynomial *qp)
1201 {
1202 qp = isl_qpolynomial_cow(qp);
1203
1204 if (!qp)
1205 return NULL;
1206
1207 qp->upoly = isl_upoly_neg(qp->upoly);
1208 if (!qp->upoly)
1209 goto error;
1210
1211 return qp;
1212 error:
1213 isl_qpolynomial_free(qp);
1214 return NULL;
1215 }
1216
1217 __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1,
1218 __isl_take isl_qpolynomial *qp2)
1219 {
1220 qp1 = isl_qpolynomial_cow(qp1);
1221
1222 if (!qp1 || !qp2)
1223 goto error;
1224
1225 if (qp1->div->n_row < qp2->div->n_row)
1226 return isl_qpolynomial_mul(qp2, qp1);
1227
1228 isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
1229 if (!compatible_divs(qp1->div, qp2->div))
1230 return with_merged_divs(isl_qpolynomial_mul, qp1, qp2);
1231
1232 qp1->upoly = isl_upoly_mul(qp1->upoly, isl_upoly_copy(qp2->upoly));
1233 if (!qp1->upoly)
1234 goto error;
1235
1236 isl_qpolynomial_free(qp2);
1237
1238 return qp1;
1239 error:
1240 isl_qpolynomial_free(qp1);
1241 isl_qpolynomial_free(qp2);
1242 return NULL;
1243 }
1244
1245 __isl_give isl_qpolynomial *isl_qpolynomial_zero(__isl_take isl_dim *dim)
1246 {
1247 return isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
1248 }
1249
1250 __isl_give isl_qpolynomial *isl_qpolynomial_infty(__isl_take isl_dim *dim)
1251 {
1252 return isl_qpolynomial_alloc(dim, 0, isl_upoly_infty(dim->ctx));
1253 }
1254
1255 __isl_give isl_qpolynomial *isl_qpolynomial_neginfty(__isl_take isl_dim *dim)
1256 {
1257 return isl_qpolynomial_alloc(dim, 0, isl_upoly_neginfty(dim->ctx));
1258 }
1259
1260 __isl_give isl_qpolynomial *isl_qpolynomial_nan(__isl_take isl_dim *dim)
1261 {
1262 return isl_qpolynomial_alloc(dim, 0, isl_upoly_nan(dim->ctx));
1263 }
1264
1265 __isl_give isl_qpolynomial *isl_qpolynomial_cst(__isl_take isl_dim *dim,
1266 isl_int v)
1267 {
1268 struct isl_qpolynomial *qp;
1269 struct isl_upoly_cst *cst;
1270
1271 qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
1272 if (!qp)
1273 return NULL;
1274
1275 cst = isl_upoly_as_cst(qp->upoly);
1276 isl_int_set(cst->n, v);
1277
1278 return qp;
1279 error:
1280 isl_qpolynomial_free(qp);
1281 return NULL;
1282 }
1283
1284 int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
1285 isl_int *n, isl_int *d)
1286 {
1287 struct isl_upoly_cst *cst;
1288
1289 if (!qp)
1290 return -1;
1291
1292 if (!isl_upoly_is_cst(qp->upoly))
1293 return 0;
1294
1295 cst = isl_upoly_as_cst(qp->upoly);
1296 if (!cst)
1297 return -1;
1298
1299 if (n)
1300 isl_int_set(*n, cst->n);
1301 if (d)
1302 isl_int_set(*d, cst->d);
1303
1304 return 1;
1305 }
1306
1307 int isl_upoly_is_affine(__isl_keep struct isl_upoly *up)
1308 {
1309 int is_cst;
1310 struct isl_upoly_rec *rec;
1311
1312 if (!up)
1313 return -1;
1314
1315 if (up->var < 0)
1316 return 1;
1317
1318 rec = isl_upoly_as_rec(up);
1319 if (!rec)
1320 return -1;
1321
1322 if (rec->n > 2)
1323 return 0;
1324
1325 isl_assert(up->ctx, rec->n > 1, return -1);
1326
1327 is_cst = isl_upoly_is_cst(rec->p[1]);
1328 if (is_cst < 0)
1329 return -1;
1330 if (!is_cst)
1331 return 0;
1332
1333 return isl_upoly_is_affine(rec->p[0]);
1334 }
1335
1336 int isl_qpolynomial_is_affine(__isl_keep isl_qpolynomial *qp)
1337 {
1338 if (!qp)
1339 return -1;
1340
1341 if (qp->div->n_row > 0)
1342 return 0;
1343
1344 return isl_upoly_is_affine(qp->upoly);
1345 }
1346
1347 static void update_coeff(__isl_keep isl_vec *aff,
1348 __isl_keep struct isl_upoly_cst *cst, int pos)
1349 {
1350 isl_int gcd;
1351 isl_int f;
1352
1353 if (isl_int_is_zero(cst->n))
1354 return;
1355
1356 isl_int_init(gcd);
1357 isl_int_init(f);
1358 isl_int_gcd(gcd, cst->d, aff->el[0]);
1359 isl_int_divexact(f, cst->d, gcd);
1360 isl_int_divexact(gcd, aff->el[0], gcd);
1361 isl_seq_scale(aff->el, aff->el, f, aff->size);
1362 isl_int_mul(aff->el[1 + pos], gcd, cst->n);
1363 isl_int_clear(gcd);
1364 isl_int_clear(f);
1365 }
1366
1367 int isl_upoly_update_affine(__isl_keep struct isl_upoly *up,
1368 __isl_keep isl_vec *aff)
1369 {
1370 struct isl_upoly_cst *cst;
1371 struct isl_upoly_rec *rec;
1372
1373 if (!up || !aff)
1374 return -1;
1375
1376 if (up->var < 0) {
1377 struct isl_upoly_cst *cst;
1378
1379 cst = isl_upoly_as_cst(up);
1380 if (!cst)
1381 return -1;
1382 update_coeff(aff, cst, 0);
1383 return 0;
1384 }
1385
1386 rec = isl_upoly_as_rec(up);
1387 if (!rec)
1388 return -1;
1389 isl_assert(up->ctx, rec->n == 2, return -1);
1390
1391 cst = isl_upoly_as_cst(rec->p[1]);
1392 if (!cst)
1393 return -1;
1394 update_coeff(aff, cst, 1 + up->var);
1395
1396 return isl_upoly_update_affine(rec->p[0], aff);
1397 }
1398
1399 __isl_give isl_vec *isl_qpolynomial_extract_affine(
1400 __isl_keep isl_qpolynomial *qp)
1401 {
1402 isl_vec *aff;
1403 unsigned d;
1404
1405 if (!qp)
1406 return NULL;
1407
1408 isl_assert(qp->div->ctx, qp->div->n_row == 0, return NULL);
1409 d = isl_dim_total(qp->dim);
1410 aff = isl_vec_alloc(qp->div->ctx, 2 + d);
1411 if (!aff)
1412 return NULL;
1413
1414 isl_seq_clr(aff->el + 1, 1 + d);
1415 isl_int_set_si(aff->el[0], 1);
1416
1417 if (isl_upoly_update_affine(qp->upoly, aff) < 0)
1418 goto error;
1419
1420 return aff;
1421 error:
1422 isl_vec_free(aff);
1423 return NULL;
1424 }
1425
1426 int isl_qpolynomial_is_equal(__isl_keep isl_qpolynomial *qp1,
1427 __isl_keep isl_qpolynomial *qp2)
1428 {
1429 if (!qp1 || !qp2)
1430 return -1;
1431
1432 return isl_upoly_is_equal(qp1->upoly, qp2->upoly);
1433 }
1434
1435 static void upoly_update_den(__isl_keep struct isl_upoly *up, isl_int *d)
1436 {
1437 int i;
1438 struct isl_upoly_rec *rec;
1439
1440 if (isl_upoly_is_cst(up)) {
1441 struct isl_upoly_cst *cst;
1442 cst = isl_upoly_as_cst(up);
1443 if (!cst)
1444 return;
1445 isl_int_lcm(*d, *d, cst->d);
1446 return;
1447 }
1448
1449 rec = isl_upoly_as_rec(up);
1450 if (!rec)
1451 return;
1452
1453 for (i = 0; i < rec->n; ++i)
1454 upoly_update_den(rec->p[i], d);
1455 }
1456
1457 void isl_qpolynomial_get_den(__isl_keep isl_qpolynomial *qp, isl_int *d)
1458 {
1459 isl_int_set_si(*d, 1);
1460 if (!qp)
1461 return;
1462 upoly_update_den(qp->upoly, d);
1463 }
1464
1465 __isl_give struct isl_upoly *isl_upoly_pow(isl_ctx *ctx, int pos, int power)
1466 {
1467 int i;
1468 struct isl_upoly *up;
1469 struct isl_upoly_rec *rec;
1470 struct isl_upoly_cst *cst;
1471
1472 rec = isl_upoly_alloc_rec(ctx, pos, 1 + power);
1473 if (!rec)
1474 return NULL;
1475 for (i = 0; i < 1 + power; ++i) {
1476 rec->p[i] = isl_upoly_zero(ctx);
1477 if (!rec->p[i])
1478 goto error;
1479 rec->n++;
1480 }
1481 cst = isl_upoly_as_cst(rec->p[power]);
1482 isl_int_set_si(cst->n, 1);
1483
1484 return &rec->up;
1485 error:
1486 isl_upoly_free(&rec->up);
1487 return NULL;
1488 }
1489
1490 __isl_give isl_qpolynomial *isl_qpolynomial_pow(__isl_take isl_dim *dim,
1491 int pos, int power)
1492 {
1493 struct isl_ctx *ctx;
1494
1495 if (!dim)
1496 return NULL;
1497
1498 ctx = dim->ctx;
1499
1500 return isl_qpolynomial_alloc(dim, 0, isl_upoly_pow(ctx, pos, power));
1501 }
1502
1503 __isl_give isl_qpolynomial *isl_qpolynomial_var(__isl_take isl_dim *dim,
1504 enum isl_dim_type type, unsigned pos)
1505 {
1506 if (!dim)
1507 return NULL;
1508
1509 isl_assert(dim->ctx, isl_dim_size(dim, isl_dim_in) == 0, goto error);
1510 isl_assert(dim->ctx, pos < isl_dim_size(dim, type), goto error);
1511
1512 if (type == isl_dim_set)
1513 pos += isl_dim_size(dim, isl_dim_param);
1514
1515 return isl_qpolynomial_pow(dim, pos, 1);
1516 error:
1517 isl_dim_free(dim);
1518 return NULL;
1519 }
1520
1521 __isl_give isl_qpolynomial *isl_qpolynomial_div_pow(__isl_take isl_div *div,
1522 int power)
1523 {
1524 struct isl_qpolynomial *qp = NULL;
1525 struct isl_upoly_rec *rec;
1526 struct isl_upoly_cst *cst;
1527 int i;
1528 int pos;
1529
1530 if (!div)
1531 return NULL;
1532 isl_assert(div->ctx, div->bmap->n_div == 1, goto error);
1533
1534 pos = isl_dim_total(div->bmap->dim);
1535 rec = isl_upoly_alloc_rec(div->ctx, pos, 1 + power);
1536 qp = isl_qpolynomial_alloc(isl_basic_map_get_dim(div->bmap), 1,
1537 &rec->up);
1538 if (!qp)
1539 goto error;
1540
1541 isl_seq_cpy(qp->div->row[0], div->line[0], qp->div->n_col - 1);
1542 isl_int_set_si(qp->div->row[0][qp->div->n_col - 1], 0);
1543
1544 for (i = 0; i < 1 + power; ++i) {
1545 rec->p[i] = isl_upoly_zero(div->ctx);
1546 if (!rec->p[i])
1547 goto error;
1548 rec->n++;
1549 }
1550 cst = isl_upoly_as_cst(rec->p[power]);
1551 isl_int_set_si(cst->n, 1);
1552
1553 isl_div_free(div);
1554
1555 return qp;
1556 error:
1557 isl_qpolynomial_free(qp);
1558 isl_div_free(div);
1559 return NULL;
1560 }
1561
1562 __isl_give isl_qpolynomial *isl_qpolynomial_div(__isl_take isl_div *div)
1563 {
1564 return isl_qpolynomial_div_pow(div, 1);
1565 }
1566
1567 __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(__isl_take isl_dim *dim,
1568 const isl_int n, const isl_int d)
1569 {
1570 struct isl_qpolynomial *qp;
1571 struct isl_upoly_cst *cst;
1572
1573 qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
1574 if (!qp)
1575 return NULL;
1576
1577 cst = isl_upoly_as_cst(qp->upoly);
1578 isl_int_set(cst->n, n);
1579 isl_int_set(cst->d, d);
1580
1581 return qp;
1582 error:
1583 isl_qpolynomial_free(qp);
1584 return NULL;
1585 }
1586
1587 static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d)
1588 {
1589 struct isl_upoly_rec *rec;
1590 int i;
1591
1592 if (!up)
1593 return -1;
1594
1595 if (isl_upoly_is_cst(up))
1596 return 0;
1597
1598 if (up->var < d)
1599 active[up->var] = 1;
1600
1601 rec = isl_upoly_as_rec(up);
1602 for (i = 0; i < rec->n; ++i)
1603 if (up_set_active(rec->p[i], active, d) < 0)
1604 return -1;
1605
1606 return 0;
1607 }
1608
1609 static int set_active(__isl_keep isl_qpolynomial *qp, int *active)
1610 {
1611 int i, j;
1612 int d = isl_dim_total(qp->dim);
1613
1614 if (!qp || !active)
1615 return -1;
1616
1617 for (i = 0; i < d; ++i)
1618 for (j = 0; j < qp->div->n_row; ++j) {
1619 if (isl_int_is_zero(qp->div->row[j][2 + i]))
1620 continue;
1621 active[i] = 1;
1622 break;
1623 }
1624
1625 return up_set_active(qp->upoly, active, d);
1626 }
1627
1628 int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp,
1629 enum isl_dim_type type, unsigned first, unsigned n)
1630 {
1631 int i;
1632 int *active = NULL;
1633 int involves = 0;
1634
1635 if (!qp)
1636 return -1;
1637 if (n == 0)
1638 return 0;
1639
1640 isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
1641 return -1);
1642 isl_assert(qp->dim->ctx, type == isl_dim_param ||
1643 type == isl_dim_set, return -1);
1644
1645 active = isl_calloc_array(set->ctx, int, isl_dim_total(qp->dim));
1646 if (set_active(qp, active) < 0)
1647 goto error;
1648
1649 if (type == isl_dim_set)
1650 first += isl_dim_size(qp->dim, isl_dim_param);
1651 for (i = 0; i < n; ++i)
1652 if (active[first + i]) {
1653 involves = 1;
1654 break;
1655 }
1656
1657 free(active);
1658
1659 return involves;
1660 error:
1661 free(active);
1662 return -1;
1663 }
1664
1665 __isl_give struct isl_upoly *isl_upoly_drop(__isl_take struct isl_upoly *up,
1666 unsigned first, unsigned n)
1667 {
1668 int i;
1669 struct isl_upoly_rec *rec;
1670
1671 if (!up)
1672 return NULL;
1673 if (n == 0 || up->var < 0 || up->var < first)
1674 return up;
1675 if (up->var < first + n) {
1676 up = replace_by_constant_term(up);
1677 return isl_upoly_drop(up, first, n);
1678 }
1679 up = isl_upoly_cow(up);
1680 if (!up)
1681 return NULL;
1682 up->var -= n;
1683 rec = isl_upoly_as_rec(up);
1684 if (!rec)
1685 goto error;
1686
1687 for (i = 0; i < rec->n; ++i) {
1688 rec->p[i] = isl_upoly_drop(rec->p[i], first, n);
1689 if (!rec->p[i])
1690 goto error;
1691 }
1692
1693 return up;
1694 error:
1695 isl_upoly_free(up);
1696 return NULL;
1697 }
1698
1699 __isl_give isl_qpolynomial *isl_qpolynomial_drop_dims(
1700 __isl_take isl_qpolynomial *qp,
1701 enum isl_dim_type type, unsigned first, unsigned n)
1702 {
1703 if (!qp)
1704 return NULL;
1705 if (n == 0)
1706 return qp;
1707
1708 qp = isl_qpolynomial_cow(qp);
1709 if (!qp)
1710 return NULL;
1711
1712 isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
1713 goto error);
1714 isl_assert(qp->dim->ctx, type == isl_dim_param ||
1715 type == isl_dim_set, goto error);
1716
1717 qp->dim = isl_dim_drop(qp->dim, type, first, n);
1718 if (!qp->dim)
1719 goto error;
1720
1721 if (type == isl_dim_set)
1722 first += isl_dim_size(qp->dim, isl_dim_param);
1723
1724 qp->div = isl_mat_drop_cols(qp->div, 2 + first, n);
1725 if (!qp->div)
1726 goto error;
1727
1728 qp->upoly = isl_upoly_drop(qp->upoly, first, n);
1729 if (!qp->upoly)
1730 goto error;
1731
1732 return qp;
1733 error:
1734 isl_qpolynomial_free(qp);
1735 return NULL;
1736 }
1737
1738 #undef PW
1739 #define PW isl_pw_qpolynomial
1740 #undef EL
1741 #define EL isl_qpolynomial
1742 #undef IS_ZERO
1743 #define IS_ZERO is_zero
1744 #undef FIELD
1745 #define FIELD qp
1746 #undef ADD
1747 #define ADD(d,e1,e2) isl_qpolynomial_add(e1,e2)
1748
1749 #include <isl_pw_templ.c>
1750
1751 int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp)
1752 {
1753 if (!pwqp)
1754 return -1;
1755
1756 if (pwqp->n != -1)
1757 return 0;
1758
1759 if (!isl_set_fast_is_universe(pwqp->p[0].set))
1760 return 0;
1761
1762 return isl_qpolynomial_is_one(pwqp->p[0].qp);
1763 }
1764
1765 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
1766 __isl_take isl_pw_qpolynomial *pwqp1,
1767 __isl_take isl_pw_qpolynomial *pwqp2)
1768 {
1769 int i, j, n;
1770 struct isl_pw_qpolynomial *res;
1771 isl_set *set;
1772
1773 if (!pwqp1 || !pwqp2)
1774 goto error;
1775
1776 isl_assert(pwqp1->dim->ctx, isl_dim_equal(pwqp1->dim, pwqp2->dim),
1777 goto error);
1778
1779 if (isl_pw_qpolynomial_is_zero(pwqp1)) {
1780 isl_pw_qpolynomial_free(pwqp2);
1781 return pwqp1;
1782 }
1783
1784 if (isl_pw_qpolynomial_is_zero(pwqp2)) {
1785 isl_pw_qpolynomial_free(pwqp1);
1786 return pwqp2;
1787 }
1788
1789 if (isl_pw_qpolynomial_is_one(pwqp1)) {
1790 isl_pw_qpolynomial_free(pwqp1);
1791 return pwqp2;
1792 }
1793
1794 if (isl_pw_qpolynomial_is_one(pwqp2)) {
1795 isl_pw_qpolynomial_free(pwqp2);
1796 return pwqp1;
1797 }
1798
1799 n = pwqp1->n * pwqp2->n;
1800 res = isl_pw_qpolynomial_alloc_(isl_dim_copy(pwqp1->dim), n);
1801
1802 for (i = 0; i < pwqp1->n; ++i) {
1803 for (j = 0; j < pwqp2->n; ++j) {
1804 struct isl_set *common;
1805 struct isl_qpolynomial *prod;
1806 common = isl_set_intersect(isl_set_copy(pwqp1->p[i].set),
1807 isl_set_copy(pwqp2->p[j].set));
1808 if (isl_set_fast_is_empty(common)) {
1809 isl_set_free(common);
1810 continue;
1811 }
1812
1813 prod = isl_qpolynomial_mul(
1814 isl_qpolynomial_copy(pwqp1->p[i].qp),
1815 isl_qpolynomial_copy(pwqp2->p[j].qp));
1816
1817 res = isl_pw_qpolynomial_add_piece(res, common, prod);
1818 }
1819 }
1820
1821 isl_pw_qpolynomial_free(pwqp1);
1822 isl_pw_qpolynomial_free(pwqp2);
1823
1824 return res;
1825 error:
1826 isl_pw_qpolynomial_free(pwqp1);
1827 isl_pw_qpolynomial_free(pwqp2);
1828 return NULL;
1829 }
1830
1831 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
1832 __isl_take isl_pw_qpolynomial *pwqp)
1833 {
1834 int i, j, n;
1835 struct isl_pw_qpolynomial *res;
1836 isl_set *set;
1837
1838 if (!pwqp)
1839 return NULL;
1840
1841 if (isl_pw_qpolynomial_is_zero(pwqp))
1842 return pwqp;
1843
1844 pwqp = isl_pw_qpolynomial_cow(pwqp);
1845
1846 for (i = 0; i < pwqp->n; ++i) {
1847 pwqp->p[i].qp = isl_qpolynomial_neg(pwqp->p[i].qp);
1848 if (!pwqp->p[i].qp)
1849 goto error;
1850 }
1851
1852 return pwqp;
1853 error:
1854 isl_pw_qpolynomial_free(pwqp);
1855 return NULL;
1856 }
1857
1858 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
1859 __isl_take isl_pw_qpolynomial *pwqp1,
1860 __isl_take isl_pw_qpolynomial *pwqp2)
1861 {
1862 return isl_pw_qpolynomial_add(pwqp1, isl_pw_qpolynomial_neg(pwqp2));
1863 }
1864
1865 __isl_give struct isl_upoly *isl_upoly_eval(
1866 __isl_take struct isl_upoly *up, __isl_take isl_vec *vec)
1867 {
1868 int i;
1869 struct isl_upoly_rec *rec;
1870 struct isl_upoly *res;
1871 struct isl_upoly *base;
1872
1873 if (isl_upoly_is_cst(up)) {
1874 isl_vec_free(vec);
1875 return up;
1876 }
1877
1878 rec = isl_upoly_as_rec(up);
1879 if (!rec)
1880 goto error;
1881
1882 isl_assert(up->ctx, rec->n >= 1, goto error);
1883
1884 base = isl_upoly_rat_cst(up->ctx, vec->el[1 + up->var], vec->el[0]);
1885
1886 res = isl_upoly_eval(isl_upoly_copy(rec->p[rec->n - 1]),
1887 isl_vec_copy(vec));
1888
1889 for (i = rec->n - 2; i >= 0; --i) {
1890 res = isl_upoly_mul(res, isl_upoly_copy(base));
1891 res = isl_upoly_sum(res,
1892 isl_upoly_eval(isl_upoly_copy(rec->p[i]),
1893 isl_vec_copy(vec)));
1894 }
1895
1896 isl_upoly_free(base);
1897 isl_upoly_free(up);
1898 isl_vec_free(vec);
1899 return res;
1900 error:
1901 isl_upoly_free(up);
1902 isl_vec_free(vec);
1903 return NULL;
1904 }
1905
1906 __isl_give isl_qpolynomial *isl_qpolynomial_eval(
1907 __isl_take isl_qpolynomial *qp, __isl_take isl_point *pnt)
1908 {
1909 isl_vec *ext;
1910 struct isl_upoly *up;
1911 isl_dim *dim;
1912
1913 if (!qp || !pnt)
1914 goto error;
1915 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, qp->dim), goto error);
1916
1917 if (qp->div->n_row == 0)
1918 ext = isl_vec_copy(pnt->vec);
1919 else {
1920 int i;
1921 unsigned dim = isl_dim_total(qp->dim);
1922 ext = isl_vec_alloc(qp->dim->ctx, 1 + dim + qp->div->n_row);
1923 if (!ext)
1924 goto error;
1925
1926 isl_seq_cpy(ext->el, pnt->vec->el, pnt->vec->size);
1927 for (i = 0; i < qp->div->n_row; ++i) {
1928 isl_seq_inner_product(qp->div->row[i] + 1, ext->el,
1929 1 + dim + i, &ext->el[1+dim+i]);
1930 isl_int_fdiv_q(ext->el[1+dim+i], ext->el[1+dim+i],
1931 qp->div->row[i][0]);
1932 }
1933 }
1934
1935 up = isl_upoly_eval(isl_upoly_copy(qp->upoly), ext);
1936 if (!up)
1937 goto error;
1938
1939 dim = isl_dim_copy(qp->dim);
1940 isl_qpolynomial_free(qp);
1941 isl_point_free(pnt);
1942
1943 return isl_qpolynomial_alloc(dim, 0, up);
1944 error:
1945 isl_qpolynomial_free(qp);
1946 isl_point_free(pnt);
1947 return NULL;
1948 }
1949
1950 int isl_upoly_cmp(__isl_keep struct isl_upoly_cst *cst1,
1951 __isl_keep struct isl_upoly_cst *cst2)
1952 {
1953 int cmp;
1954 isl_int t;
1955 isl_int_init(t);
1956 isl_int_mul(t, cst1->n, cst2->d);
1957 isl_int_submul(t, cst2->n, cst1->d);
1958 cmp = isl_int_sgn(t);
1959 isl_int_clear(t);
1960 return cmp;
1961 }
1962
1963 int isl_qpolynomial_le_cst(__isl_keep isl_qpolynomial *qp1,
1964 __isl_keep isl_qpolynomial *qp2)
1965 {
1966 struct isl_upoly_cst *cst1, *cst2;
1967
1968 if (!qp1 || !qp2)
1969 return -1;
1970 isl_assert(qp1->dim->ctx, isl_upoly_is_cst(qp1->upoly), return -1);
1971 isl_assert(qp2->dim->ctx, isl_upoly_is_cst(qp2->upoly), return -1);
1972 if (isl_qpolynomial_is_nan(qp1))
1973 return -1;
1974 if (isl_qpolynomial_is_nan(qp2))
1975 return -1;
1976 cst1 = isl_upoly_as_cst(qp1->upoly);
1977 cst2 = isl_upoly_as_cst(qp2->upoly);
1978
1979 return isl_upoly_cmp(cst1, cst2) <= 0;
1980 }
1981
1982 __isl_give isl_qpolynomial *isl_qpolynomial_min_cst(
1983 __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2)
1984 {
1985 struct isl_upoly_cst *cst1, *cst2;
1986 int cmp;
1987
1988 if (!qp1 || !qp2)
1989 goto error;
1990 isl_assert(qp1->dim->ctx, isl_upoly_is_cst(qp1->upoly), goto error);
1991 isl_assert(qp2->dim->ctx, isl_upoly_is_cst(qp2->upoly), goto error);
1992 cst1 = isl_upoly_as_cst(qp1->upoly);
1993 cst2 = isl_upoly_as_cst(qp2->upoly);
1994 cmp = isl_upoly_cmp(cst1, cst2);
1995
1996 if (cmp <= 0) {
1997 isl_qpolynomial_free(qp2);
1998 } else {
1999 isl_qpolynomial_free(qp1);
2000 qp1 = qp2;
2001 }
2002 return qp1;
2003 error:
2004 isl_qpolynomial_free(qp1);
2005 isl_qpolynomial_free(qp2);
2006 return NULL;
2007 }
2008
2009 __isl_give isl_qpolynomial *isl_qpolynomial_max_cst(
2010 __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2)
2011 {
2012 struct isl_upoly_cst *cst1, *cst2;
2013 int cmp;
2014
2015 if (!qp1 || !qp2)
2016 goto error;
2017 isl_assert(qp1->dim->ctx, isl_upoly_is_cst(qp1->upoly), goto error);
2018 isl_assert(qp2->dim->ctx, isl_upoly_is_cst(qp2->upoly), goto error);
2019 cst1 = isl_upoly_as_cst(qp1->upoly);
2020 cst2 = isl_upoly_as_cst(qp2->upoly);
2021 cmp = isl_upoly_cmp(cst1, cst2);
2022
2023 if (cmp >= 0) {
2024 isl_qpolynomial_free(qp2);
2025 } else {
2026 isl_qpolynomial_free(qp1);
2027 qp1 = qp2;
2028 }
2029 return qp1;
2030 error:
2031 isl_qpolynomial_free(qp1);
2032 isl_qpolynomial_free(qp2);
2033 return NULL;
2034 }
2035
2036 __isl_give isl_qpolynomial *isl_qpolynomial_add_dims(
2037 __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned n)
2038 {
2039 unsigned total;
2040 unsigned g_pos;
2041 int *exp;
2042
2043 if (n == 0)
2044 return qp;
2045
2046 qp = isl_qpolynomial_cow(qp);
2047 if (!qp)
2048 return NULL;
2049
2050 g_pos = pos(qp->dim, type) + isl_dim_size(qp->dim, type);
2051
2052 qp->div = isl_mat_insert_cols(qp->div, 2 + g_pos, n);
2053 if (!qp->div)
2054 goto error;
2055
2056 total = qp->div->n_col - 2;
2057 if (total > g_pos) {
2058 int i;
2059 exp = isl_alloc_array(qp->div->ctx, int, total - g_pos);
2060 if (!exp)
2061 goto error;
2062 for (i = 0; i < total - g_pos; ++i)
2063 exp[i] = i + n;
2064 qp->upoly = expand(qp->upoly, exp, g_pos);
2065 free(exp);
2066 if (!qp->upoly)
2067 goto error;
2068 }
2069
2070 qp->dim = isl_dim_add(qp->dim, type, n);
2071 if (!qp->dim)
2072 goto error;
2073
2074 return qp;
2075 error:
2076 isl_qpolynomial_free(qp);
2077 return NULL;
2078 }
2079
2080 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_dims(
2081 __isl_take isl_pw_qpolynomial *pwqp,
2082 enum isl_dim_type type, unsigned n)
2083 {
2084 int i;
2085
2086 if (n == 0)
2087 return pwqp;
2088
2089 pwqp = isl_pw_qpolynomial_cow(pwqp);
2090 if (!pwqp)
2091 return NULL;
2092
2093 pwqp->dim = isl_dim_add(pwqp->dim, type, n);
2094 if (!pwqp->dim)
2095 goto error;
2096
2097 for (i = 0; i < pwqp->n; ++i) {
2098 pwqp->p[i].set = isl_set_add(pwqp->p[i].set, type, n);
2099 if (!pwqp->p[i].set)
2100 goto error;
2101 pwqp->p[i].qp = isl_qpolynomial_add_dims(pwqp->p[i].qp, type, n);
2102 if (!pwqp->p[i].qp)
2103 goto error;
2104 }
2105
2106 return pwqp;
2107 error:
2108 isl_pw_qpolynomial_free(pwqp);
2109 return NULL;
2110 }
2111
2112 static int *reordering_move(isl_ctx *ctx,
2113 unsigned len, unsigned dst, unsigned src, unsigned n)
2114 {
2115 int i;
2116 int *reordering;
2117
2118 reordering = isl_alloc_array(ctx, int, len);
2119 if (!reordering)
2120 return NULL;
2121
2122 if (dst <= src) {
2123 for (i = 0; i < dst; ++i)
2124 reordering[i] = i;
2125 for (i = 0; i < n; ++i)
2126 reordering[src + i] = dst + i;
2127 for (i = 0; i < src - dst; ++i)
2128 reordering[dst + i] = dst + n + i;
2129 for (i = 0; i < len - src - n; ++i)
2130 reordering[src + n + i] = src + n + i;
2131 } else {
2132 for (i = 0; i < src; ++i)
2133 reordering[i] = i;
2134 for (i = 0; i < n; ++i)
2135 reordering[src + i] = dst + i;
2136 for (i = 0; i < dst - src; ++i)
2137 reordering[src + n + i] = src + i;
2138 for (i = 0; i < len - dst - n; ++i)
2139 reordering[dst + n + i] = dst + n + i;
2140 }
2141
2142 return reordering;
2143 }
2144
2145 static __isl_give struct isl_upoly *reorder(__isl_take struct isl_upoly *up,
2146 int *r)
2147 {
2148 int i;
2149 struct isl_upoly_rec *rec;
2150 struct isl_upoly *base;
2151 struct isl_upoly *res;
2152
2153 if (isl_upoly_is_cst(up))
2154 return up;
2155
2156 rec = isl_upoly_as_rec(up);
2157 if (!rec)
2158 goto error;
2159
2160 isl_assert(up->ctx, rec->n >= 1, goto error);
2161
2162 base = isl_upoly_pow(up->ctx, r[up->var], 1);
2163 res = reorder(isl_upoly_copy(rec->p[rec->n - 1]), r);
2164
2165 for (i = rec->n - 2; i >= 0; --i) {
2166 res = isl_upoly_mul(res, isl_upoly_copy(base));
2167 res = isl_upoly_sum(res, reorder(isl_upoly_copy(rec->p[i]), r));
2168 }
2169
2170 isl_upoly_free(base);
2171 isl_upoly_free(up);
2172
2173 return res;
2174 error:
2175 isl_upoly_free(up);
2176 return NULL;
2177 }
2178
2179 __isl_give isl_qpolynomial *isl_qpolynomial_move_dims(
2180 __isl_take isl_qpolynomial *qp,
2181 enum isl_dim_type dst_type, unsigned dst_pos,
2182 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2183 {
2184 unsigned g_dst_pos;
2185 unsigned g_src_pos;
2186 int *reordering;
2187
2188 qp = isl_qpolynomial_cow(qp);
2189 if (!qp)
2190 return NULL;
2191
2192 isl_assert(qp->dim->ctx, src_pos + n <= isl_dim_size(qp->dim, src_type),
2193 goto error);
2194
2195 g_dst_pos = pos(qp->dim, dst_type) + dst_pos;
2196 g_src_pos = pos(qp->dim, src_type) + src_pos;
2197 if (dst_type > src_type)
2198 g_dst_pos -= n;
2199
2200 qp->div = isl_mat_move_cols(qp->div, 2 + g_dst_pos, 2 + g_src_pos, n);
2201 qp->div = sort_divs(qp->div);
2202 if (!qp->div)
2203 goto error;
2204
2205 reordering = reordering_move(qp->dim->ctx,
2206 qp->div->n_col - 2, g_dst_pos, g_src_pos, n);
2207 if (!reordering)
2208 goto error;
2209
2210 qp->upoly = reorder(qp->upoly, reordering);
2211 free(reordering);
2212 if (!qp->upoly)
2213 goto error;
2214
2215 qp->dim = isl_dim_move(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
2216 if (!qp->dim)
2217 goto error;
2218
2219 return qp;
2220 error:
2221 isl_qpolynomial_free(qp);
2222 return NULL;
2223 }
2224
2225 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_move(
2226 __isl_take isl_pw_qpolynomial *pwqp,
2227 enum isl_dim_type dst_type, unsigned dst_pos,
2228 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2229 {
2230 int i;
2231
2232 pwqp = isl_pw_qpolynomial_cow(pwqp);
2233 if (!pwqp)
2234 return NULL;
2235
2236 pwqp->dim = isl_dim_move(pwqp->dim,
2237 dst_type, dst_pos, src_type, src_pos, n);
2238 if (!pwqp->dim)
2239 goto error;
2240
2241 for (i = 0; i < pwqp->n; ++i) {
2242 pwqp->p[i].set = isl_set_move_dims(pwqp->p[i].set,
2243 dst_type, dst_pos,
2244 src_type, src_pos, n);
2245 if (!pwqp->p[i].set)
2246 goto error;
2247 pwqp->p[i].qp = isl_qpolynomial_move_dims(pwqp->p[i].qp,
2248 dst_type, dst_pos, src_type, src_pos, n);
2249 if (!pwqp->p[i].qp)
2250 goto error;
2251 }
2252
2253 return pwqp;
2254 error:
2255 isl_pw_qpolynomial_free(pwqp);
2256 return NULL;
2257 }
2258
2259
2260 __isl_give struct isl_upoly *isl_upoly_from_affine(isl_ctx *ctx, isl_int *f,
2261 isl_int denom, unsigned len)
2262 {
2263 int i;
2264 struct isl_upoly *up;
2265
2266 isl_assert(ctx, len >= 1, return NULL);
2267
2268 up = isl_upoly_rat_cst(ctx, f[0], denom);
2269 for (i = 0; i < len - 1; ++i) {
2270 struct isl_upoly *t;
2271 struct isl_upoly *c;
2272
2273 if (isl_int_is_zero(f[1 + i]))
2274 continue;
2275
2276 c = isl_upoly_rat_cst(ctx, f[1 + i], denom);
2277 t = isl_upoly_pow(ctx, i, 1);
2278 t = isl_upoly_mul(c, t);
2279 up = isl_upoly_sum(up, t);
2280 }
2281
2282 return up;
2283 }
2284
2285 __isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
2286 __isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
2287 {
2288 isl_int denom;
2289 isl_dim *dim;
2290 struct isl_upoly *up;
2291 isl_qpolynomial *qp;
2292 int sgn;
2293
2294 if (!c)
2295 return NULL;
2296
2297 isl_int_init(denom);
2298
2299 isl_constraint_get_coefficient(c, type, pos, &denom);
2300 isl_constraint_set_coefficient(c, type, pos, c->ctx->zero);
2301 sgn = isl_int_sgn(denom);
2302 isl_int_abs(denom, denom);
2303 up = isl_upoly_from_affine(c->ctx, c->line[0], denom,
2304 1 + isl_constraint_dim(c, isl_dim_all));
2305 if (sgn < 0)
2306 isl_int_neg(denom, denom);
2307 isl_constraint_set_coefficient(c, type, pos, denom);
2308
2309 dim = isl_dim_copy(c->bmap->dim);
2310
2311 isl_int_clear(denom);
2312 isl_constraint_free(c);
2313
2314 qp = isl_qpolynomial_alloc(dim, 0, up);
2315 if (sgn > 0)
2316 qp = isl_qpolynomial_neg(qp);
2317 return qp;
2318 }
2319
2320 __isl_give struct isl_upoly *isl_upoly_subs(__isl_take struct isl_upoly *up,
2321 unsigned first, unsigned n, __isl_keep struct isl_upoly **subs)
2322 {
2323 int i;
2324 struct isl_upoly_rec *rec;
2325 struct isl_upoly *base, *res;
2326
2327 if (!up)
2328 return NULL;
2329
2330 if (isl_upoly_is_cst(up))
2331 return up;
2332
2333 if (up->var < first)
2334 return up;
2335
2336 rec = isl_upoly_as_rec(up);
2337 if (!rec)
2338 goto error;
2339
2340 isl_assert(up->ctx, rec->n >= 1, goto error);
2341
2342 if (up->var >= first + n)
2343 base = isl_upoly_pow(up->ctx, up->var, 1);
2344 else
2345 base = isl_upoly_copy(subs[up->var - first]);
2346
2347 res = isl_upoly_subs(isl_upoly_copy(rec->p[rec->n - 1]), first, n, subs);
2348 for (i = rec->n - 2; i >= 0; --i) {
2349 struct isl_upoly *t;
2350 t = isl_upoly_subs(isl_upoly_copy(rec->p[i]), first, n, subs);
2351 res = isl_upoly_mul(res, isl_upoly_copy(base));
2352 res = isl_upoly_sum(res, t);
2353 }
2354
2355 isl_upoly_free(base);
2356 isl_upoly_free(up);
2357
2358 return res;
2359 error:
2360 isl_upoly_free(up);
2361 return NULL;
2362 }
2363
2364 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
2365 * in "qp" by subs[i].
2366 */
2367 __isl_give isl_qpolynomial *isl_qpolynomial_substitute(
2368 __isl_take isl_qpolynomial *qp,
2369 enum isl_dim_type type, unsigned first, unsigned n,
2370 __isl_keep isl_qpolynomial **subs)
2371 {
2372 int i;
2373 struct isl_upoly **ups;
2374
2375 if (n == 0)
2376 return qp;
2377
2378 qp = isl_qpolynomial_cow(qp);
2379 if (!qp)
2380 return NULL;
2381 for (i = 0; i < n; ++i)
2382 if (!subs[i])
2383 goto error;
2384
2385 isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
2386 goto error);
2387
2388 for (i = 0; i < n; ++i)
2389 isl_assert(qp->dim->ctx, isl_dim_equal(qp->dim, subs[i]->dim),
2390 goto error);
2391
2392 isl_assert(qp->dim->ctx, qp->div->n_row == 0, goto error);
2393 for (i = 0; i < n; ++i)
2394 isl_assert(qp->dim->ctx, subs[i]->div->n_row == 0, goto error);
2395
2396 first += pos(qp->dim, type);
2397
2398 ups = isl_alloc_array(qp->dim->ctx, struct isl_upoly *, n);
2399 if (!ups)
2400 goto error;
2401 for (i = 0; i < n; ++i)
2402 ups[i] = subs[i]->upoly;
2403
2404 qp->upoly = isl_upoly_subs(qp->upoly, first, n, ups);
2405
2406 free(ups);
2407
2408 if (!qp->upoly)
2409 goto error;
2410
2411 return qp;
2412 error:
2413 isl_qpolynomial_free(qp);
2414 return NULL;
2415 }
2416
2417 __isl_give isl_basic_set *add_div_constraints(__isl_take isl_basic_set *bset,
2418 __isl_take isl_mat *div)
2419 {
2420 int i;
2421 unsigned total;
2422
2423 if (!bset || !div)
2424 goto error;
2425
2426 bset = isl_basic_set_extend_constraints(bset, 0, 2 * div->n_row);
2427 if (!bset)
2428 goto error;
2429 total = isl_basic_set_total_dim(bset);
2430 for (i = 0; i < div->n_row; ++i)
2431 if (isl_basic_set_add_div_constraints_var(bset,
2432 total - div->n_row + i, div->row[i]) < 0)
2433 goto error;
2434
2435 isl_mat_free(div);
2436 return bset;
2437 error:
2438 isl_mat_free(div);
2439 isl_basic_set_free(bset);
2440 return NULL;
2441 }
2442
2443 /* Extend "bset" with extra set dimensions for each integer division
2444 * in "qp" and then call "fn" with the extended bset and the polynomial
2445 * that results from replacing each of the integer divisions by the
2446 * corresponding extra set dimension.
2447 */
2448 int isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp,
2449 __isl_keep isl_basic_set *bset,
2450 int (*fn)(__isl_take isl_basic_set *bset,
2451 __isl_take isl_qpolynomial *poly, void *user), void *user)
2452 {
2453 isl_dim *dim;
2454 isl_mat *div;
2455 isl_qpolynomial *poly;
2456
2457 if (!qp || !bset)
2458 goto error;
2459 if (qp->div->n_row == 0)
2460 return fn(isl_basic_set_copy(bset), isl_qpolynomial_copy(qp),
2461 user);
2462
2463 div = isl_mat_copy(qp->div);
2464 dim = isl_dim_copy(qp->dim);
2465 dim = isl_dim_add(dim, isl_dim_set, qp->div->n_row);
2466 poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly));
2467 bset = isl_basic_set_copy(bset);
2468 bset = isl_basic_set_add(bset, isl_dim_set, qp->div->n_row);
2469 bset = add_div_constraints(bset, div);
2470
2471 return fn(bset, poly, user);
2472 error:
2473 return -1;
2474 }
2475
2476 __isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
2477 __isl_take isl_mat *div)
2478 {
2479 isl_term *term;
2480 int n;
2481
2482 if (!dim || !div)
2483 goto error;
2484
2485 n = isl_dim_total(dim) + div->n_row;
2486
2487 term = isl_calloc(dim->ctx, struct isl_term,
2488 sizeof(struct isl_term) + (n - 1) * sizeof(int));
2489 if (!term)
2490 goto error;
2491
2492 term->ref = 1;
2493 term->dim = dim;
2494 term->div = div;
2495 isl_int_init(term->n);
2496 isl_int_init(term->d);
2497
2498 return term;
2499 error:
2500 isl_dim_free(dim);
2501 isl_mat_free(div);
2502 return NULL;
2503 }
2504
2505 __isl_give isl_term *isl_term_copy(__isl_keep isl_term *term)
2506 {
2507 if (!term)
2508 return NULL;
2509
2510 term->ref++;
2511 return term;
2512 }
2513
2514 __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term)
2515 {
2516 int i;
2517 isl_term *dup;
2518 unsigned total;
2519
2520 if (term)
2521 return NULL;
2522
2523 total = isl_dim_total(term->dim) + term->div->n_row;
2524
2525 dup = isl_term_alloc(isl_dim_copy(term->dim), isl_mat_copy(term->div));
2526 if (!dup)
2527 return NULL;
2528
2529 isl_int_set(dup->n, term->n);
2530 isl_int_set(dup->d, term->d);
2531
2532 for (i = 0; i < total; ++i)
2533 dup->pow[i] = term->pow[i];
2534
2535 return dup;
2536 }
2537
2538 __isl_give isl_term *isl_term_cow(__isl_take isl_term *term)
2539 {
2540 if (!term)
2541 return NULL;
2542
2543 if (term->ref == 1)
2544 return term;
2545 term->ref--;
2546 return isl_term_dup(term);
2547 }
2548
2549 void isl_term_free(__isl_take isl_term *term)
2550 {
2551 if (!term)
2552 return;
2553
2554 if (--term->ref > 0)
2555 return;
2556
2557 isl_dim_free(term->dim);
2558 isl_mat_free(term->div);
2559 isl_int_clear(term->n);
2560 isl_int_clear(term->d);
2561 free(term);
2562 }
2563
2564 unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type)
2565 {
2566 if (!term)
2567 return 0;
2568
2569 switch (type) {
2570 case isl_dim_param:
2571 case isl_dim_in:
2572 case isl_dim_out: return isl_dim_size(term->dim, type);
2573 case isl_dim_div: return term->div->n_row;
2574 case isl_dim_all: return isl_dim_total(term->dim) + term->div->n_row;
2575 }
2576 }
2577
2578 isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term)
2579 {
2580 return term ? term->dim->ctx : NULL;
2581 }
2582
2583 void isl_term_get_num(__isl_keep isl_term *term, isl_int *n)
2584 {
2585 if (!term)
2586 return;
2587 isl_int_set(*n, term->n);
2588 }
2589
2590 void isl_term_get_den(__isl_keep isl_term *term, isl_int *d)
2591 {
2592 if (!term)
2593 return;
2594 isl_int_set(*d, term->d);
2595 }
2596
2597 int isl_term_get_exp(__isl_keep isl_term *term,
2598 enum isl_dim_type type, unsigned pos)
2599 {
2600 if (!term)
2601 return -1;
2602
2603 isl_assert(term->dim->ctx, pos < isl_term_dim(term, type), return -1);
2604
2605 if (type >= isl_dim_set)
2606 pos += isl_dim_size(term->dim, isl_dim_param);
2607 if (type >= isl_dim_div)
2608 pos += isl_dim_size(term->dim, isl_dim_set);
2609
2610 return term->pow[pos];
2611 }
2612
2613 __isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
2614 {
2615 isl_basic_map *bmap;
2616 unsigned total;
2617 int k;
2618
2619 if (!term)
2620 return NULL;
2621
2622 isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div),
2623 return NULL);
2624
2625 total = term->div->n_col - term->div->n_row - 2;
2626 /* No nested divs for now */
2627 isl_assert(term->dim->ctx,
2628 isl_seq_first_non_zero(term->div->row[pos] + 2 + total,
2629 term->div->n_row) == -1,
2630 return NULL);
2631
2632 bmap = isl_basic_map_alloc_dim(isl_dim_copy(term->dim), 1, 0, 0);
2633 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
2634 goto error;
2635
2636 isl_seq_cpy(bmap->div[k], term->div->row[pos], 2 + total);
2637
2638 return isl_basic_map_div(bmap, k);
2639 error:
2640 isl_basic_map_free(bmap);
2641 return NULL;
2642 }
2643
2644 __isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up,
2645 int (*fn)(__isl_take isl_term *term, void *user),
2646 __isl_take isl_term *term, void *user)
2647 {
2648 int i;
2649 struct isl_upoly_rec *rec;
2650
2651 if (!up || !term)
2652 goto error;
2653
2654 if (isl_upoly_is_zero(up))
2655 return term;
2656
2657 isl_assert(up->ctx, !isl_upoly_is_nan(up), goto error);
2658 isl_assert(up->ctx, !isl_upoly_is_infty(up), goto error);
2659 isl_assert(up->ctx, !isl_upoly_is_neginfty(up), goto error);
2660
2661 if (isl_upoly_is_cst(up)) {
2662 struct isl_upoly_cst *cst;
2663 cst = isl_upoly_as_cst(up);
2664 if (!cst)
2665 goto error;
2666 term = isl_term_cow(term);
2667 if (!term)
2668 goto error;
2669 isl_int_set(term->n, cst->n);
2670 isl_int_set(term->d, cst->d);
2671 if (fn(isl_term_copy(term), user) < 0)
2672 goto error;
2673 return term;
2674 }
2675
2676 rec = isl_upoly_as_rec(up);
2677 if (!rec)
2678 goto error;
2679
2680 for (i = 0; i < rec->n; ++i) {
2681 term = isl_term_cow(term);
2682 if (!term)
2683 goto error;
2684 term->pow[up->var] = i;
2685 term = isl_upoly_foreach_term(rec->p[i], fn, term, user);
2686 if (!term)
2687 goto error;
2688 }
2689 term->pow[up->var] = 0;
2690
2691 return term;
2692 error:
2693 isl_term_free(term);
2694 return NULL;
2695 }
2696
2697 int isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp,
2698 int (*fn)(__isl_take isl_term *term, void *user), void *user)
2699 {
2700 isl_term *term;
2701
2702 if (!qp)
2703 return -1;
2704
2705 term = isl_term_alloc(isl_dim_copy(qp->dim), isl_mat_copy(qp->div));
2706 if (!term)
2707 return -1;
2708
2709 term = isl_upoly_foreach_term(qp->upoly, fn, term, user);
2710
2711 isl_term_free(term);
2712
2713 return term ? 0 : -1;
2714 }
2715
2716 __isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term)
2717 {
2718 struct isl_upoly *up;
2719 isl_qpolynomial *qp;
2720 int i, n;
2721
2722 if (!term)
2723 return NULL;
2724
2725 n = isl_dim_total(term->dim) + term->div->n_row;
2726
2727 up = isl_upoly_rat_cst(term->dim->ctx, term->n, term->d);
2728 for (i = 0; i < n; ++i) {
2729 if (!term->pow[i])
2730 continue;
2731 up = isl_upoly_mul(up,
2732 isl_upoly_pow(term->dim->ctx, i, term->pow[i]));
2733 }
2734
2735 qp = isl_qpolynomial_alloc(isl_dim_copy(term->dim), term->div->n_row, up);
2736 if (!qp)
2737 goto error;
2738 isl_mat_free(qp->div);
2739 qp->div = isl_mat_copy(term->div);
2740 if (!qp->div)
2741 goto error;
2742
2743 isl_term_free(term);
2744 return qp;
2745 error:
2746 isl_qpolynomial_free(qp);
2747 isl_term_free(term);
2748 return NULL;
2749 }
2750
2751 int isl_pw_qpolynomial_foreach_piece(__isl_keep isl_pw_qpolynomial *pwqp,
2752 int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
2753 void *user), void *user)
2754 {
2755 int i;
2756
2757 if (!pwqp)
2758 return -1;
2759
2760 for (i = 0; i < pwqp->n; ++i)
2761 if (fn(isl_set_copy(pwqp->p[i].set),
2762 isl_qpolynomial_copy(pwqp->p[i].qp), user) < 0)
2763 return -1;
2764
2765 return 0;
2766 }
2767
2768 static int any_divs(__isl_keep isl_set *set)
2769 {
2770 int i;
2771
2772 if (!set)
2773 return -1;
2774
2775 for (i = 0; i < set->n; ++i)
2776 if (set->p[i]->n_div > 0)
2777 return 1;
2778
2779 return 0;
2780 }
2781
2782 __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
2783 __isl_take isl_dim *dim)
2784 {
2785 if (!qp || !dim)
2786 goto error;
2787
2788 if (isl_dim_equal(qp->dim, dim)) {
2789 isl_dim_free(dim);
2790 return qp;
2791 }
2792
2793 qp = isl_qpolynomial_cow(qp);
2794 if (!qp)
2795 goto error;
2796
2797 if (qp->div->n_row) {
2798 int i;
2799 int extra;
2800 unsigned total;
2801 int *exp;
2802
2803 extra = isl_dim_size(dim, isl_dim_set) -
2804 isl_dim_size(qp->dim, isl_dim_set);
2805 total = isl_dim_total(qp->dim);
2806 exp = isl_alloc_array(qp->div->ctx, int, qp->div->n_row);
2807 if (!exp)
2808 goto error;
2809 for (i = 0; i < qp->div->n_row; ++i)
2810 exp[i] = extra + i;
2811 qp->upoly = expand(qp->upoly, exp, total);
2812 free(exp);
2813 if (!qp->upoly)
2814 goto error;
2815 qp->div = isl_mat_insert_cols(qp->div, 2 + total, extra);
2816 if (!qp->div)
2817 goto error;
2818 for (i = 0; i < qp->div->n_row; ++i)
2819 isl_seq_clr(qp->div->row[i] + 2 + total, extra);
2820 }
2821
2822 isl_dim_free(qp->dim);
2823 qp->dim = dim;
2824
2825 return qp;
2826 error:
2827 isl_dim_free(dim);
2828 isl_qpolynomial_free(qp);
2829 return NULL;
2830 }
2831
2832 static int foreach_lifted_subset(__isl_take isl_set *set,
2833 __isl_take isl_qpolynomial *qp,
2834 int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
2835 void *user), void *user)
2836 {
2837 int i;
2838
2839 if (!set || !qp)
2840 goto error;
2841
2842 for (i = 0; i < set->n; ++i) {
2843 isl_set *lift;
2844 isl_qpolynomial *copy;
2845
2846 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
2847 lift = isl_set_lift(lift);
2848
2849 copy = isl_qpolynomial_copy(qp);
2850 copy = isl_qpolynomial_lift(copy, isl_set_get_dim(lift));
2851
2852 if (fn(lift, copy, user) < 0)
2853 goto error;
2854 }
2855
2856 isl_set_free(set);
2857 isl_qpolynomial_free(qp);
2858
2859 return 0;
2860 error:
2861 isl_set_free(set);
2862 isl_qpolynomial_free(qp);
2863 return -1;
2864 }
2865
2866 int isl_pw_qpolynomial_foreach_lifted_piece(__isl_keep isl_pw_qpolynomial *pwqp,
2867 int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
2868 void *user), void *user)
2869 {
2870 int i;
2871
2872 if (!pwqp)
2873 return -1;
2874
2875 for (i = 0; i < pwqp->n; ++i) {
2876 isl_set *set;
2877 isl_qpolynomial *qp;
2878
2879 set = isl_set_copy(pwqp->p[i].set);
2880 qp = isl_qpolynomial_copy(pwqp->p[i].qp);
2881 if (!any_divs(set)) {
2882 if (fn(set, qp, user) < 0)
2883 return -1;
2884 continue;
2885 }
2886 if (foreach_lifted_subset(set, qp, fn, user) < 0)
2887 return -1;
2888 }
2889
2890 return 0;
2891 }
2892
2893 /* For each parameter or variable that does not appear in qp,
2894 * first eliminate the variable from all constraints and then set it to zero.
2895 */
2896 static __isl_give isl_set *fix_inactive(__isl_take isl_set *set,
2897 __isl_keep isl_qpolynomial *qp)
2898 {
2899 int *active = NULL;
2900 int i;
2901 int d;
2902 unsigned nparam;
2903 unsigned nvar;
2904
2905 if (!set || !qp)
2906 goto error;
2907
2908 d = isl_dim_total(set->dim);
2909 active = isl_calloc_array(set->ctx, int, d);
2910 if (set_active(qp, active) < 0)
2911 goto error;
2912
2913 for (i = 0; i < d; ++i)
2914 if (!active[i])
2915 break;
2916
2917 if (i == d) {
2918 free(active);
2919 return set;
2920 }
2921
2922 nparam = isl_dim_size(set->dim, isl_dim_param);
2923 nvar = isl_dim_size(set->dim, isl_dim_set);
2924 for (i = 0; i < nparam; ++i) {
2925 if (active[i])
2926 continue;
2927 set = isl_set_eliminate(set, isl_dim_param, i, 1);
2928 set = isl_set_fix_si(set, isl_dim_param, i, 0);
2929 }
2930 for (i = 0; i < nvar; ++i) {
2931 if (active[nparam + i])
2932 continue;
2933 set = isl_set_eliminate(set, isl_dim_set, i, 1);
2934 set = isl_set_fix_si(set, isl_dim_set, i, 0);
2935 }
2936
2937 free(active);
2938
2939 return set;
2940 error:
2941 free(active);
2942 isl_set_free(set);
2943 return NULL;
2944 }
2945
2946 struct isl_opt_data {
2947 isl_qpolynomial *qp;
2948 int first;
2949 isl_qpolynomial *opt;
2950 int max;
2951 };
2952
2953 static int opt_fn(__isl_take isl_point *pnt, void *user)
2954 {
2955 struct isl_opt_data *data = (struct isl_opt_data *)user;
2956 isl_qpolynomial *val;
2957
2958 val = isl_qpolynomial_eval(isl_qpolynomial_copy(data->qp), pnt);
2959 if (data->first) {
2960 data->first = 0;
2961 data->opt = val;
2962 } else if (data->max) {
2963 data->opt = isl_qpolynomial_max_cst(data->opt, val);
2964 } else {
2965 data->opt = isl_qpolynomial_min_cst(data->opt, val);
2966 }
2967
2968 return 0;
2969 }
2970
2971 __isl_give isl_qpolynomial *isl_qpolynomial_opt_on_domain(
2972 __isl_take isl_qpolynomial *qp, __isl_take isl_set *set, int max)
2973 {
2974 struct isl_opt_data data = { NULL, 1, NULL, max };
2975
2976 if (!set || !qp)
2977 goto error;
2978
2979 if (isl_upoly_is_cst(qp->upoly)) {
2980 isl_set_free(set);
2981 return qp;
2982 }
2983
2984 set = fix_inactive(set, qp);
2985
2986 data.qp = qp;
2987 if (isl_set_foreach_point(set, opt_fn, &data) < 0)
2988 goto error;
2989
2990 if (data.first)
2991 data.opt = isl_qpolynomial_zero(isl_qpolynomial_get_dim(qp));
2992
2993 isl_set_free(set);
2994 isl_qpolynomial_free(qp);
2995 return data.opt;
2996 error:
2997 isl_set_free(set);
2998 isl_qpolynomial_free(qp);
2999 isl_qpolynomial_free(data.opt);
3000 return NULL;
3001 }
Integer set library