?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_basic_map_solve_lp: use denominator
[isl.git] / isl_map_subtract.c
blob59df4b162564bed2c369fd83d079b8d63ebb2e3b
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10 #include <isl/seq.h>
11 #include <isl/set.h>
12 #include <isl/map.h>
13 #include "isl_map_private.h"
14 #include "isl_tab.h"
15 #include <isl_point_private.h>
16
17 static void expand_constraint(isl_vec *v, unsigned dim,
18 isl_int *c, int *div_map, unsigned n_div)
19 {
20 int i;
21
22 isl_seq_cpy(v->el, c, 1 + dim);
23 isl_seq_clr(v->el + 1 + dim, v->size - (1 + dim));
24
25 for (i = 0; i < n_div; ++i)
26 isl_int_set(v->el[1 + dim + div_map[i]], c[1 + dim + i]);
27 }
28
29 /* Add all constraints of bmap to tab. The equalities of bmap
30 * are added as a pair of inequalities.
31 */
32 static int tab_add_constraints(struct isl_tab *tab,
33 __isl_keep isl_basic_map *bmap, int *div_map)
34 {
35 int i;
36 unsigned dim;
37 unsigned tab_total;
38 unsigned bmap_total;
39 isl_vec *v;
40
41 if (!tab || !bmap)
42 return -1;
43
44 tab_total = isl_basic_map_total_dim(tab->bmap);
45 bmap_total = isl_basic_map_total_dim(bmap);
46 dim = isl_dim_total(tab->bmap->dim);
47
48 if (isl_tab_extend_cons(tab, 2 * bmap->n_eq + bmap->n_ineq) < 0)
49 return -1;
50
51 v = isl_vec_alloc(bmap->ctx, 1 + tab_total);
52 if (!v)
53 return -1;
54
55 for (i = 0; i < bmap->n_eq; ++i) {
56 expand_constraint(v, dim, bmap->eq[i], div_map, bmap->n_div);
57 if (isl_tab_add_ineq(tab, v->el) < 0)
58 goto error;
59 isl_seq_neg(bmap->eq[i], bmap->eq[i], 1 + bmap_total);
60 expand_constraint(v, dim, bmap->eq[i], div_map, bmap->n_div);
61 if (isl_tab_add_ineq(tab, v->el) < 0)
62 goto error;
63 isl_seq_neg(bmap->eq[i], bmap->eq[i], 1 + bmap_total);
64 if (tab->empty)
65 break;
66 }
67
68 for (i = 0; i < bmap->n_ineq; ++i) {
69 expand_constraint(v, dim, bmap->ineq[i], div_map, bmap->n_div);
70 if (isl_tab_add_ineq(tab, v->el) < 0)
71 goto error;
72 if (tab->empty)
73 break;
74 }
75
76 isl_vec_free(v);
77 return 0;
78 error:
79 isl_vec_free(v);
80 return -1;
81 }
82
83 /* Add a specific constraint of bmap (or its opposite) to tab.
84 * The position of the constraint is specified by "c", where
85 * the equalities of bmap are counted twice, once for the inequality
86 * that is equal to the equality, and once for its negation.
87 */
88 static int tab_add_constraint(struct isl_tab *tab,
89 __isl_keep isl_basic_map *bmap, int *div_map, int c, int oppose)
90 {
91 unsigned dim;
92 unsigned tab_total;
93 unsigned bmap_total;
94 isl_vec *v;
95 int r;
96
97 if (!tab || !bmap)
98 return -1;
99
100 tab_total = isl_basic_map_total_dim(tab->bmap);
101 bmap_total = isl_basic_map_total_dim(bmap);
102 dim = isl_dim_total(tab->bmap->dim);
103
104 v = isl_vec_alloc(bmap->ctx, 1 + tab_total);
105 if (!v)
106 return -1;
107
108 if (c < 2 * bmap->n_eq) {
109 if ((c % 2) != oppose)
110 isl_seq_neg(bmap->eq[c/2], bmap->eq[c/2],
111 1 + bmap_total);
112 if (oppose)
113 isl_int_sub_ui(bmap->eq[c/2][0], bmap->eq[c/2][0], 1);
114 expand_constraint(v, dim, bmap->eq[c/2], div_map, bmap->n_div);
115 r = isl_tab_add_ineq(tab, v->el);
116 if (oppose)
117 isl_int_add_ui(bmap->eq[c/2][0], bmap->eq[c/2][0], 1);
118 if ((c % 2) != oppose)
119 isl_seq_neg(bmap->eq[c/2], bmap->eq[c/2],
120 1 + bmap_total);
121 } else {
122 c -= 2 * bmap->n_eq;
123 if (oppose) {
124 isl_seq_neg(bmap->ineq[c], bmap->ineq[c],
125 1 + bmap_total);
126 isl_int_sub_ui(bmap->ineq[c][0], bmap->ineq[c][0], 1);
127 }
128 expand_constraint(v, dim, bmap->ineq[c], div_map, bmap->n_div);
129 r = isl_tab_add_ineq(tab, v->el);
130 if (oppose) {
131 isl_int_add_ui(bmap->ineq[c][0], bmap->ineq[c][0], 1);
132 isl_seq_neg(bmap->ineq[c], bmap->ineq[c],
133 1 + bmap_total);
134 }
135 }
136
137 isl_vec_free(v);
138 return r;
139 }
140
141 static int tab_add_divs(struct isl_tab *tab, __isl_keep isl_basic_map *bmap,
142 int **div_map)
143 {
144 int i, j;
145 struct isl_vec *vec;
146 unsigned total;
147 unsigned dim;
148
149 if (!bmap)
150 return -1;
151 if (!bmap->n_div)
152 return 0;
153
154 if (!*div_map)
155 *div_map = isl_alloc_array(bmap->ctx, int, bmap->n_div);
156 if (!*div_map)
157 return -1;
158
159 total = isl_basic_map_total_dim(tab->bmap);
160 dim = total - tab->bmap->n_div;
161 vec = isl_vec_alloc(bmap->ctx, 2 + total + bmap->n_div);
162 if (!vec)
163 return -1;
164
165 for (i = 0; i < bmap->n_div; ++i) {
166 isl_seq_cpy(vec->el, bmap->div[i], 2 + dim);
167 isl_seq_clr(vec->el + 2 + dim, tab->bmap->n_div);
168 for (j = 0; j < i; ++j)
169 isl_int_set(vec->el[2 + dim + (*div_map)[j]],
170 bmap->div[i][2 + dim + j]);
171 for (j = 0; j < tab->bmap->n_div; ++j)
172 if (isl_seq_eq(tab->bmap->div[j],
173 vec->el, 2 + dim + tab->bmap->n_div))
174 break;
175 (*div_map)[i] = j;
176 if (j == tab->bmap->n_div) {
177 vec->size = 2 + dim + tab->bmap->n_div;
178 if (isl_tab_add_div(tab, vec, NULL, NULL) < 0)
179 goto error;
180 }
181 }
182
183 isl_vec_free(vec);
184
185 return 0;
186 error:
187 isl_vec_free(vec);
188
189 return -1;
190 }
191
192 /* Freeze all constraints of tableau tab.
193 */
194 static int tab_freeze_constraints(struct isl_tab *tab)
195 {
196 int i;
197
198 for (i = 0; i < tab->n_con; ++i)
199 if (isl_tab_freeze_constraint(tab, i) < 0)
200 return -1;
201
202 return 0;
203 }
204
205 /* Check for redundant constraints starting at offset.
206 * Put the indices of the redundant constraints in index
207 * and return the number of redundant constraints.
208 */
209 static int n_non_redundant(struct isl_tab *tab, int offset, int **index)
210 {
211 int i, n;
212 int n_test = tab->n_con - offset;
213
214 if (isl_tab_detect_redundant(tab) < 0)
215 return -1;
216
217 if (!*index)
218 *index = isl_alloc_array(tab->mat->ctx, int, n_test);
219 if (!*index)
220 return -1;
221
222 for (n = 0, i = 0; i < n_test; ++i) {
223 int r;
224 r = isl_tab_is_redundant(tab, offset + i);
225 if (r < 0)
226 return -1;
227 if (r)
228 continue;
229 (*index)[n++] = i;
230 }
231
232 return n;
233 }
234
235 /* basic_map_collect_diff calls add on each of the pieces of
236 * the set difference between bmap and map until the add method
237 * return a negative value.
238 */
239 struct isl_diff_collector {
240 int (*add)(struct isl_diff_collector *dc,
241 __isl_take isl_basic_map *bmap);
242 };
243
244 /* Compute the set difference between bmap and map and call
245 * dc->add on each of the piece until this function returns
246 * a negative value.
247 * Return 0 on success and -1 on error. dc->add returning
248 * a negative value is treated as an error, but the calling
249 * function can interpret the results based on the state of dc.
250 *
251 * Assumes that both bmap and map have known divs.
252 *
253 * The difference is computed by a backtracking algorithm.
254 * Each level corresponds to a basic map in "map".
255 * When a node in entered for the first time, we check
256 * if the corresonding basic map intersects the current piece
257 * of "bmap". If not, we move to the next level.
258 * Otherwise, we split the current piece into as many
259 * pieces as there are non-redundant constraints of the current
260 * basic map in the intersection. Each of these pieces is
261 * handled by a child of the current node.
262 * In particular, if there are n non-redundant constraints,
263 * then for each 0 <= i < n, a piece is cut off by adding
264 * constraints 0 <= j < i and adding the opposite of constraint i.
265 * If there are no non-redundant constraints, meaning that the current
266 * piece is a subset of the current basic map, then we simply backtrack.
267 *
268 * In the leaves, we check if the remaining piece has any integer points
269 * and if so, pass it along to dc->add. As a special case, if nothing
270 * has been removed when we end up in a leaf, we simply pass along
271 * the original basic map.
272 */
273 static int basic_map_collect_diff(__isl_take isl_basic_map *bmap,
274 __isl_take isl_map *map, struct isl_diff_collector *dc)
275 {
276 int i;
277 int modified;
278 int level;
279 int init;
280 int empty;
281 struct isl_tab *tab = NULL;
282 struct isl_tab_undo **snap = NULL;
283 int *k = NULL;
284 int *n = NULL;
285 int **index = NULL;
286 int **div_map = NULL;
287
288 empty = isl_basic_map_is_empty(bmap);
289 if (empty) {
290 isl_basic_map_free(bmap);
291 isl_map_free(map);
292 return empty < 0 ? -1 : 0;
293 }
294
295 bmap = isl_basic_map_cow(bmap);
296 map = isl_map_cow(map);
297
298 if (!bmap || !map)
299 goto error;
300
301 snap = isl_alloc_array(map->ctx, struct isl_tab_undo *, map->n);
302 k = isl_alloc_array(map->ctx, int, map->n);
303 n = isl_alloc_array(map->ctx, int, map->n);
304 index = isl_calloc_array(map->ctx, int *, map->n);
305 div_map = isl_calloc_array(map->ctx, int *, map->n);
306 if (!snap || !k || !n || !index || !div_map)
307 goto error;
308
309 bmap = isl_basic_map_order_divs(bmap);
310 map = isl_map_order_divs(map);
311
312 tab = isl_tab_from_basic_map(bmap);
313 if (isl_tab_track_bmap(tab, isl_basic_map_copy(bmap)) < 0)
314 goto error;
315
316 modified = 0;
317 level = 0;
318 init = 1;
319
320 while (level >= 0) {
321 if (level >= map->n) {
322 int empty;
323 struct isl_basic_map *bm;
324 if (!modified) {
325 if (dc->add(dc, isl_basic_map_copy(bmap)) < 0)
326 goto error;
327 break;
328 }
329 bm = isl_basic_map_copy(tab->bmap);
330 bm = isl_basic_map_cow(bm);
331 bm = isl_basic_map_update_from_tab(bm, tab);
332 bm = isl_basic_map_simplify(bm);
333 bm = isl_basic_map_finalize(bm);
334 empty = isl_basic_map_is_empty(bm);
335 if (empty)
336 isl_basic_map_free(bm);
337 else if (dc->add(dc, bm) < 0)
338 goto error;
339 if (empty < 0)
340 goto error;
341 level--;
342 init = 0;
343 continue;
344 }
345 if (init) {
346 int offset;
347 struct isl_tab_undo *snap2;
348 snap2 = isl_tab_snap(tab);
349 if (tab_add_divs(tab, map->p[level],
350 &div_map[level]) < 0)
351 goto error;
352 offset = tab->n_con;
353 snap[level] = isl_tab_snap(tab);
354 if (tab_freeze_constraints(tab) < 0)
355 goto error;
356 if (tab_add_constraints(tab, map->p[level],
357 div_map[level]) < 0)
358 goto error;
359 k[level] = 0;
360 n[level] = 0;
361 if (tab->empty) {
362 if (isl_tab_rollback(tab, snap2) < 0)
363 goto error;
364 level++;
365 continue;
366 }
367 modified = 1;
368 n[level] = n_non_redundant(tab, offset, &index[level]);
369 if (n[level] < 0)
370 goto error;
371 if (n[level] == 0) {
372 level--;
373 init = 0;
374 continue;
375 }
376 if (isl_tab_rollback(tab, snap[level]) < 0)
377 goto error;
378 if (tab_add_constraint(tab, map->p[level],
379 div_map[level], index[level][0], 1) < 0)
380 goto error;
381 level++;
382 continue;
383 } else {
384 if (k[level] + 1 >= n[level]) {
385 level--;
386 continue;
387 }
388 if (isl_tab_rollback(tab, snap[level]) < 0)
389 goto error;
390 if (tab_add_constraint(tab, map->p[level],
391 div_map[level],
392 index[level][k[level]], 0) < 0)
393 goto error;
394 snap[level] = isl_tab_snap(tab);
395 k[level]++;
396 if (tab_add_constraint(tab, map->p[level],
397 div_map[level],
398 index[level][k[level]], 1) < 0)
399 goto error;
400 level++;
401 init = 1;
402 continue;
403 }
404 }
405
406 isl_tab_free(tab);
407 free(snap);
408 free(n);
409 free(k);
410 for (i = 0; index && i < map->n; ++i)
411 free(index[i]);
412 free(index);
413 for (i = 0; div_map && i < map->n; ++i)
414 free(div_map[i]);
415 free(div_map);
416
417 isl_basic_map_free(bmap);
418 isl_map_free(map);
419
420 return 0;
421 error:
422 isl_tab_free(tab);
423 free(snap);
424 free(n);
425 free(k);
426 for (i = 0; index && i < map->n; ++i)
427 free(index[i]);
428 free(index);
429 for (i = 0; div_map && i < map->n; ++i)
430 free(div_map[i]);
431 free(div_map);
432 isl_basic_map_free(bmap);
433 isl_map_free(map);
434 return -1;
435 }
436
437 /* A diff collector that actually collects all parts of the
438 * set difference in the field diff.
439 */
440 struct isl_subtract_diff_collector {
441 struct isl_diff_collector dc;
442 struct isl_map *diff;
443 };
444
445 /* isl_subtract_diff_collector callback.
446 */
447 static int basic_map_subtract_add(struct isl_diff_collector *dc,
448 __isl_take isl_basic_map *bmap)
449 {
450 struct isl_subtract_diff_collector *sdc;
451 sdc = (struct isl_subtract_diff_collector *)dc;
452
453 sdc->diff = isl_map_union_disjoint(sdc->diff,
454 isl_map_from_basic_map(bmap));
455
456 return sdc->diff ? 0 : -1;
457 }
458
459 /* Return the set difference between bmap and map.
460 */
461 static __isl_give isl_map *basic_map_subtract(__isl_take isl_basic_map *bmap,
462 __isl_take isl_map *map)
463 {
464 struct isl_subtract_diff_collector sdc;
465 sdc.dc.add = &basic_map_subtract_add;
466 sdc.diff = isl_map_empty_like_basic_map(bmap);
467 if (basic_map_collect_diff(bmap, map, &sdc.dc) < 0) {
468 isl_map_free(sdc.diff);
469 sdc.diff = NULL;
470 }
471 return sdc.diff;
472 }
473
474 /* Return the set difference between map1 and map2.
475 * (U_i A_i) \ (U_j B_j) is computed as U_i (A_i \ (U_j B_j))
476 */
477 struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2)
478 {
479 int i;
480 struct isl_map *diff;
481
482 if (!map1 || !map2)
483 goto error;
484
485 isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
486
487 if (isl_map_is_empty(map2)) {
488 isl_map_free(map2);
489 return map1;
490 }
491
492 map1 = isl_map_compute_divs(map1);
493 map2 = isl_map_compute_divs(map2);
494 if (!map1 || !map2)
495 goto error;
496
497 map1 = isl_map_remove_empty_parts(map1);
498 map2 = isl_map_remove_empty_parts(map2);
499
500 diff = isl_map_empty_like(map1);
501 for (i = 0; i < map1->n; ++i) {
502 struct isl_map *d;
503 d = basic_map_subtract(isl_basic_map_copy(map1->p[i]),
504 isl_map_copy(map2));
505 if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT))
506 diff = isl_map_union_disjoint(diff, d);
507 else
508 diff = isl_map_union(diff, d);
509 }
510
511 isl_map_free(map1);
512 isl_map_free(map2);
513
514 return diff;
515 error:
516 isl_map_free(map1);
517 isl_map_free(map2);
518 return NULL;
519 }
520
521 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
522 {
523 return (struct isl_set *)
524 isl_map_subtract(
525 (struct isl_map *)set1, (struct isl_map *)set2);
526 }
527
528 /* A diff collector that aborts as soon as its add function is called,
529 * setting empty to 0.
530 */
531 struct isl_is_empty_diff_collector {
532 struct isl_diff_collector dc;
533 int empty;
534 };
535
536 /* isl_is_empty_diff_collector callback.
537 */
538 static int basic_map_is_empty_add(struct isl_diff_collector *dc,
539 __isl_take isl_basic_map *bmap)
540 {
541 struct isl_is_empty_diff_collector *edc;
542 edc = (struct isl_is_empty_diff_collector *)dc;
543
544 edc->empty = 0;
545
546 isl_basic_map_free(bmap);
547 return -1;
548 }
549
550 /* Check if bmap \ map is empty by computing this set difference
551 * and breaking off as soon as the difference is known to be non-empty.
552 */
553 static int basic_map_diff_is_empty(__isl_keep isl_basic_map *bmap,
554 __isl_keep isl_map *map)
555 {
556 int r;
557 struct isl_is_empty_diff_collector edc;
558
559 r = isl_basic_map_fast_is_empty(bmap);
560 if (r)
561 return r;
562
563 edc.dc.add = &basic_map_is_empty_add;
564 edc.empty = 1;
565 r = basic_map_collect_diff(isl_basic_map_copy(bmap),
566 isl_map_copy(map), &edc.dc);
567 if (!edc.empty)
568 return 0;
569
570 return r < 0 ? -1 : 1;
571 }
572
573 /* Check if map1 \ map2 is empty by checking if the set difference is empty
574 * for each of the basic maps in map1.
575 */
576 static int map_diff_is_empty(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
577 {
578 int i;
579 int is_empty = 1;
580
581 if (!map1 || !map2)
582 return -1;
583
584 for (i = 0; i < map1->n; ++i) {
585 is_empty = basic_map_diff_is_empty(map1->p[i], map2);
586 if (is_empty < 0 || !is_empty)
587 break;
588 }
589
590 return is_empty;
591 }
592
593 /* Return 1 if "bmap" contains a single element.
594 */
595 int isl_basic_map_is_singleton(__isl_keep isl_basic_map *bmap)
596 {
597 if (!bmap)
598 return -1;
599 if (bmap->n_div)
600 return 0;
601 if (bmap->n_ineq)
602 return 0;
603 return bmap->n_eq == isl_basic_map_total_dim(bmap);
604 }
605
606 /* Return 1 if "map" contains a single element.
607 */
608 int isl_map_is_singleton(__isl_keep isl_map *map)
609 {
610 if (!map)
611 return -1;
612 if (map->n != 1)
613 return 0;
614
615 return isl_basic_map_is_singleton(map->p[0]);
616 }
617
618 /* Given a singleton basic map, extract the single element
619 * as an isl_point.
620 */
621 static __isl_give isl_point *singleton_extract_point(
622 __isl_keep isl_basic_map *bmap)
623 {
624 int i, j;
625 unsigned dim;
626 struct isl_vec *point;
627 isl_int m;
628
629 if (!bmap)
630 return NULL;
631
632 dim = isl_basic_map_total_dim(bmap);
633 isl_assert(bmap->ctx, bmap->n_eq == dim, return NULL);
634 point = isl_vec_alloc(bmap->ctx, 1 + dim);
635 if (!point)
636 return NULL;
637
638 isl_int_init(m);
639
640 isl_int_set_si(point->el[0], 1);
641 for (j = 0; j < bmap->n_eq; ++j) {
642 int s;
643 int i = dim - 1 - j;
644 isl_assert(bmap->ctx,
645 isl_seq_first_non_zero(bmap->eq[j] + 1, i) == -1,
646 goto error);
647 isl_assert(bmap->ctx,
648 isl_int_is_one(bmap->eq[j][1 + i]) ||
649 isl_int_is_negone(bmap->eq[j][1 + i]),
650 goto error);
651 isl_assert(bmap->ctx,
652 isl_seq_first_non_zero(bmap->eq[j]+1+i+1, dim-i-1) == -1,
653 goto error);
654
655 isl_int_gcd(m, point->el[0], bmap->eq[j][1 + i]);
656 isl_int_divexact(m, bmap->eq[j][1 + i], m);
657 isl_int_abs(m, m);
658 isl_seq_scale(point->el, point->el, m, 1 + i);
659 isl_int_divexact(m, point->el[0], bmap->eq[j][1 + i]);
660 isl_int_neg(m, m);
661 isl_int_mul(point->el[1 + i], m, bmap->eq[j][0]);
662 }
663
664 isl_int_clear(m);
665 return isl_point_alloc(isl_basic_map_get_dim(bmap), point);
666 error:
667 isl_int_clear(m);
668 isl_vec_free(point);
669 return NULL;
670 }
671
672 /* Return 1 is the singleton map "map1" is a subset of "map2",
673 * i.e., if the single element of "map1" is also an element of "map2".
674 */
675 static int map_is_singleton_subset(__isl_keep isl_map *map1,
676 __isl_keep isl_map *map2)
677 {
678 int i;
679 int is_subset = 0;
680 struct isl_point *point;
681
682 if (!map1 || !map2)
683 return -1;
684 if (map1->n != 1)
685 return -1;
686
687 point = singleton_extract_point(map1->p[0]);
688 if (!point)
689 return -1;
690
691 for (i = 0; i < map2->n; ++i) {
692 is_subset = isl_basic_map_contains_point(map2->p[i], point);
693 if (is_subset)
694 break;
695 }
696
697 isl_point_free(point);
698 return is_subset;
699 }
700
701 int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
702 {
703 int is_subset = 0;
704 struct isl_map *diff;
705
706 if (!map1 || !map2)
707 return -1;
708
709 if (isl_map_is_empty(map1))
710 return 1;
711
712 if (isl_map_is_empty(map2))
713 return 0;
714
715 if (isl_map_fast_is_universe(map2))
716 return 1;
717
718 map1 = isl_map_compute_divs(isl_map_copy(map1));
719 map2 = isl_map_compute_divs(isl_map_copy(map2));
720 if (isl_map_is_singleton(map1)) {
721 is_subset = map_is_singleton_subset(map1, map2);
722 isl_map_free(map1);
723 isl_map_free(map2);
724 return is_subset;
725 }
726 is_subset = map_diff_is_empty(map1, map2);
727 isl_map_free(map1);
728 isl_map_free(map2);
729
730 return is_subset;
731 }
732
733 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
734 {
735 return isl_map_is_subset(
736 (struct isl_map *)set1, (struct isl_map *)set2);
737 }
738
739 __isl_give isl_map *isl_map_make_disjoint(__isl_take isl_map *map)
740 {
741 int i;
742 struct isl_subtract_diff_collector sdc;
743 sdc.dc.add = &basic_map_subtract_add;
744
745 if (!map)
746 return NULL;
747 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
748 return map;
749 if (map->n <= 1)
750 return map;
751
752 map = isl_map_compute_divs(map);
753 map = isl_map_remove_empty_parts(map);
754
755 if (!map || map->n <= 1)
756 return map;
757
758 sdc.diff = isl_map_from_basic_map(isl_basic_map_copy(map->p[0]));
759
760 for (i = 1; i < map->n; ++i) {
761 struct isl_basic_map *bmap = isl_basic_map_copy(map->p[i]);
762 struct isl_map *copy = isl_map_copy(sdc.diff);
763 if (basic_map_collect_diff(bmap, copy, &sdc.dc) < 0) {
764 isl_map_free(sdc.diff);
765 sdc.diff = NULL;
766 break;
767 }
768 }
769
770 isl_map_free(map);
771
772 return sdc.diff;
773 }
774
775 __isl_give isl_set *isl_set_make_disjoint(__isl_take isl_set *set)
776 {
777 return (struct isl_set *)isl_map_make_disjoint((struct isl_map *)set);
778 }
779
780 __isl_give isl_set *isl_set_complement(__isl_take isl_set *set)
781 {
782 isl_set *universe;
783
784 if (!set)
785 return NULL;
786
787 universe = isl_set_universe(isl_set_get_dim(set));
788
789 return isl_set_subtract(universe, set);
790 }
Integer set library