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 }