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