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