isl_point.c

   1 #include <isl_map_private.h>
   2 #include <isl_point_private.h>
   3 #include <isl/set.h>
   4 #include <isl/union_set.h>
   5 #include <isl_sample.h>
   6 #include <isl_scan.h>
   7 #include <isl_seq.h>
   8 #include <isl_space_private.h>
   9 #include <isl_val_private.h>
  10 #include <isl_vec_private.h>
  11 #include <isl_output_private.h>
  12 #include <isl/deprecated/point_int.h>
  13
  14 #include <set_to_map.c>
  15
  16 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
  17 {
  18         return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
  19 }
  20
  21 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
  22 {
  23         return pnt ? isl_space_copy(pnt->dim) : NULL;
  24 }
  25
  26 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
  27         __isl_take isl_vec *vec)
  28 {
  29         struct isl_point *pnt;
  30
  31         if (!dim || !vec)
  32                 goto error;
  33
  34         if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
  35                 vec = isl_vec_cow(vec);
  36                 if (!vec)
  37                         goto error;
  38                 vec->size = 1 + isl_space_dim(dim, isl_dim_all);
  39         }
  40
  41         pnt = isl_alloc_type(dim->ctx, struct isl_point);
  42         if (!pnt)
  43                 goto error;
  44
  45         pnt->ref = 1;
  46         pnt->dim = dim;
  47         pnt->vec = vec;
  48
  49         return pnt;
  50 error:
  51         isl_space_free(dim);
  52         isl_vec_free(vec);
  53         return NULL;
  54 }
  55
  56 __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
  57 {
  58         isl_vec *vec;
  59
  60         if (!dim)
  61                 return NULL;
  62         vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
  63         if (!vec)
  64                 goto error;
  65         isl_int_set_si(vec->el[0], 1);
  66         isl_seq_clr(vec->el + 1, vec->size - 1);
  67         return isl_point_alloc(dim, vec);
  68 error:
  69         isl_space_free(dim);
  70         return NULL;
  71 }
  72
  73 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
  74 {
  75         struct isl_point *pnt2;
  76
  77         if (!pnt)
  78                 return NULL;
  79         pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
  80         return pnt2;
  81 }
  82
  83 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
  84 {
  85         struct isl_point *pnt2;
  86         if (!pnt)
  87                 return NULL;
  88
  89         if (pnt->ref == 1)
  90                 return pnt;
  91
  92         pnt2 = isl_point_dup(pnt);
  93         isl_point_free(pnt);
  94         return pnt2;
  95 }
  96
  97 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
  98 {
  99         if (!pnt)
 100                 return NULL;
 101
 102         pnt->ref++;
 103         return pnt;
 104 }
 105
 106 __isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
 107 {
 108         if (!pnt)
 109                 return NULL;
 110
 111         if (--pnt->ref > 0)
 112                 return NULL;
 113
 114         isl_space_free(pnt->dim);
 115         isl_vec_free(pnt->vec);
 116         free(pnt);
 117         return NULL;
 118 }
 119
 120 __isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
 121 {
 122         if (!dim)
 123                 return NULL;
 124
 125         return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
 126 }
 127
 128 isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
 129 {
 130         if (!pnt)
 131                 return isl_bool_error;
 132
 133         return pnt->vec->size == 0;
 134 }
 135
 136 int isl_point_get_coordinate(__isl_keep isl_point *pnt,
 137         enum isl_dim_type type, int pos, isl_int *v)
 138 {
 139         if (!pnt || isl_point_is_void(pnt))
 140                 return -1;
 141
 142         if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
 143                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 144                         "position out of bounds", return -1);
 145
 146         if (type == isl_dim_set)
 147                 pos += isl_space_dim(pnt->dim, isl_dim_param);
 148         isl_int_set(*v, pnt->vec->el[1 + pos]);
 149
 150         return 0;
 151 }
 152
 153 /* Return the value of coordinate "pos" of type "type" of "pnt".
 154  */
 155 __isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
 156         enum isl_dim_type type, int pos)
 157 {
 158         isl_ctx *ctx;
 159         isl_val *v;
 160
 161         if (!pnt)
 162                 return NULL;
 163
 164         ctx = isl_point_get_ctx(pnt);
 165         if (isl_point_is_void(pnt))
 166                 isl_die(ctx, isl_error_invalid,
 167                         "void point does not have coordinates", return NULL);
 168         if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
 169                 isl_die(ctx, isl_error_invalid,
 170                         "position out of bounds", return NULL);
 171
 172         if (type == isl_dim_set)
 173                 pos += isl_space_dim(pnt->dim, isl_dim_param);
 174
 175         v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
 176                                                 pnt->vec->el[0]);
 177         return isl_val_normalize(v);
 178 }
 179
 180 __isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt,
 181         enum isl_dim_type type, int pos, isl_int v)
 182 {
 183         if (!pnt || isl_point_is_void(pnt))
 184                 return pnt;
 185
 186         pnt = isl_point_cow(pnt);
 187         if (!pnt)
 188                 return NULL;
 189         pnt->vec = isl_vec_cow(pnt->vec);
 190         if (!pnt->vec)
 191                 goto error;
 192
 193         if (type == isl_dim_set)
 194                 pos += isl_space_dim(pnt->dim, isl_dim_param);
 195
 196         isl_int_set(pnt->vec->el[1 + pos], v);
 197
 198         return pnt;
 199 error:
 200         isl_point_free(pnt);
 201         return NULL;
 202 }
 203
 204 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
 205  */
 206 __isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
 207         enum isl_dim_type type, int pos, __isl_take isl_val *v)
 208 {
 209         if (!pnt || !v)
 210                 goto error;
 211         if (isl_point_is_void(pnt))
 212                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 213                         "void point does not have coordinates", goto error);
 214         if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
 215                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 216                         "position out of bounds", goto error);
 217         if (!isl_val_is_rat(v))
 218                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 219                         "expecting rational value", goto error);
 220
 221         if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
 222             isl_int_eq(pnt->vec->el[0], v->d)) {
 223                 isl_val_free(v);
 224                 return pnt;
 225         }
 226
 227         pnt = isl_point_cow(pnt);
 228         if (!pnt)
 229                 goto error;
 230         pnt->vec = isl_vec_cow(pnt->vec);
 231         if (!pnt->vec)
 232                 goto error;
 233
 234         if (isl_int_eq(pnt->vec->el[0], v->d)) {
 235                 isl_int_set(pnt->vec->el[1 + pos], v->n);
 236         } else if (isl_int_is_one(v->d)) {
 237                 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 238         } else {
 239                 isl_seq_scale(pnt->vec->el + 1,
 240                                 pnt->vec->el + 1, v->d, pnt->vec->size - 1);
 241                 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 242                 isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
 243                 pnt->vec = isl_vec_normalize(pnt->vec);
 244                 if (!pnt->vec)
 245                         goto error;
 246         }
 247
 248         isl_val_free(v);
 249         return pnt;
 250 error:
 251         isl_val_free(v);
 252         isl_point_free(pnt);
 253         return NULL;
 254 }
 255
 256 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
 257         enum isl_dim_type type, int pos, unsigned val)
 258 {
 259         if (!pnt || isl_point_is_void(pnt))
 260                 return pnt;
 261
 262         pnt = isl_point_cow(pnt);
 263         if (!pnt)
 264                 return NULL;
 265         pnt->vec = isl_vec_cow(pnt->vec);
 266         if (!pnt->vec)
 267                 goto error;
 268
 269         if (type == isl_dim_set)
 270                 pos += isl_space_dim(pnt->dim, isl_dim_param);
 271
 272         isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 273
 274         return pnt;
 275 error:
 276         isl_point_free(pnt);
 277         return NULL;
 278 }
 279
 280 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
 281         enum isl_dim_type type, int pos, unsigned val)
 282 {
 283         if (!pnt || isl_point_is_void(pnt))
 284                 return pnt;
 285
 286         pnt = isl_point_cow(pnt);
 287         if (!pnt)
 288                 return NULL;
 289         pnt->vec = isl_vec_cow(pnt->vec);
 290         if (!pnt->vec)
 291                 goto error;
 292
 293         if (type == isl_dim_set)
 294                 pos += isl_space_dim(pnt->dim, isl_dim_param);
 295
 296         isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 297
 298         return pnt;
 299 error:
 300         isl_point_free(pnt);
 301         return NULL;
 302 }
 303
 304 struct isl_foreach_point {
 305         struct isl_scan_callback callback;
 306         isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
 307         void *user;
 308         isl_space *dim;
 309 };
 310
 311 static isl_stat foreach_point(struct isl_scan_callback *cb,
 312         __isl_take isl_vec *sample)
 313 {
 314         struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
 315         isl_point *pnt;
 316
 317         pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
 318
 319         return fp->fn(pnt, fp->user);
 320 }
 321
 322 isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
 323         isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 324 {
 325         struct isl_foreach_point fp = { { &foreach_point }, fn, user };
 326         int i;
 327
 328         if (!set)
 329                 return isl_stat_error;
 330
 331         fp.dim = isl_set_get_space(set);
 332         if (!fp.dim)
 333                 return isl_stat_error;
 334
 335         set = isl_set_copy(set);
 336         set = isl_set_cow(set);
 337         set = isl_set_make_disjoint(set);
 338         set = isl_set_compute_divs(set);
 339         if (!set)
 340                 goto error;
 341
 342         for (i = 0; i < set->n; ++i)
 343                 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
 344                                         &fp.callback) < 0)
 345                         goto error;
 346
 347         isl_set_free(set);
 348         isl_space_free(fp.dim);
 349
 350         return isl_stat_ok;
 351 error:
 352         isl_set_free(set);
 353         isl_space_free(fp.dim);
 354         return isl_stat_error;
 355 }
 356
 357 /* Return 1 if "bmap" contains the point "point".
 358  * "bmap" is assumed to have known divs.
 359  * The point is first extended with the divs and then passed
 360  * to basic_map_contains.
 361  */
 362 isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
 363         __isl_keep isl_point *point)
 364 {
 365         int i;
 366         struct isl_vec *vec;
 367         unsigned dim;
 368         isl_bool contains;
 369
 370         if (!bmap || !point)
 371                 return isl_bool_error;
 372         isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim),
 373                 return isl_bool_error);
 374         if (bmap->n_div == 0)
 375                 return isl_basic_map_contains(bmap, point->vec);
 376
 377         dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
 378         vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
 379         if (!vec)
 380                 return isl_bool_error;
 381
 382         isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
 383         for (i = 0; i < bmap->n_div; ++i) {
 384                 isl_seq_inner_product(bmap->div[i] + 1, vec->el,
 385                                         1 + dim + i, &vec->el[1+dim+i]);
 386                 isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
 387                                 bmap->div[i][0]);
 388         }
 389
 390         contains = isl_basic_map_contains(bmap, vec);
 391
 392         isl_vec_free(vec);
 393         return contains;
 394 }
 395
 396 isl_bool isl_map_contains_point(__isl_keep isl_map *map,
 397         __isl_keep isl_point *point)
 398 {
 399         int i;
 400         isl_bool found = isl_bool_false;
 401
 402         if (!map || !point)
 403                 return isl_bool_error;
 404
 405         map = isl_map_copy(map);
 406         map = isl_map_compute_divs(map);
 407         if (!map)
 408                 return isl_bool_error;
 409
 410         for (i = 0; i < map->n; ++i) {
 411                 found = isl_basic_map_contains_point(map->p[i], point);
 412                 if (found < 0)
 413                         goto error;
 414                 if (found)
 415                         break;
 416         }
 417         isl_map_free(map);
 418
 419         return found;
 420 error:
 421         isl_map_free(map);
 422         return isl_bool_error;
 423 }
 424
 425 isl_bool isl_set_contains_point(__isl_keep isl_set *set,
 426         __isl_keep isl_point *point)
 427 {
 428         return isl_map_contains_point(set_to_map(set), point);
 429 }
 430
 431 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
 432 {
 433         isl_basic_set *bset;
 434         isl_basic_set *model;
 435
 436         if (!pnt)
 437                 return NULL;
 438
 439         model = isl_basic_set_empty(isl_space_copy(pnt->dim));
 440         bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
 441         bset = isl_basic_set_from_underlying_set(bset, model);
 442         isl_point_free(pnt);
 443
 444         return bset;
 445 }
 446
 447 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
 448 {
 449         isl_basic_set *bset;
 450         bset = isl_basic_set_from_point(pnt);
 451         return isl_set_from_basic_set(bset);
 452 }
 453
 454 /* Construct a union set, containing the single element "pnt".
 455  * If "pnt" is void, then return an empty union set.
 456  */
 457 __isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
 458 {
 459         if (!pnt)
 460                 return NULL;
 461         if (isl_point_is_void(pnt)) {
 462                 isl_space *space;
 463
 464                 space = isl_point_get_space(pnt);
 465                 isl_point_free(pnt);
 466                 return isl_union_set_empty(space);
 467         }
 468
 469         return isl_union_set_from_set(isl_set_from_point(pnt));
 470 }
 471
 472 __isl_give isl_basic_set *isl_basic_set_box_from_points(
 473         __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
 474 {
 475         isl_basic_set *bset = NULL;
 476         unsigned total;
 477         int i;
 478         int k;
 479         isl_int t;
 480
 481         isl_int_init(t);
 482
 483         if (!pnt1 || !pnt2)
 484                 goto error;
 485
 486         isl_assert(pnt1->dim->ctx,
 487                         isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
 488
 489         if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
 490                 isl_space *dim = isl_space_copy(pnt1->dim);
 491                 isl_point_free(pnt1);
 492                 isl_point_free(pnt2);
 493                 isl_int_clear(t);
 494                 return isl_basic_set_empty(dim);
 495         }
 496         if (isl_point_is_void(pnt1)) {
 497                 isl_point_free(pnt1);
 498                 isl_int_clear(t);
 499                 return isl_basic_set_from_point(pnt2);
 500         }
 501         if (isl_point_is_void(pnt2)) {
 502                 isl_point_free(pnt2);
 503                 isl_int_clear(t);
 504                 return isl_basic_set_from_point(pnt1);
 505         }
 506
 507         total = isl_space_dim(pnt1->dim, isl_dim_all);
 508         bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
 509
 510         for (i = 0; i < total; ++i) {
 511                 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
 512                 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
 513
 514                 k = isl_basic_set_alloc_inequality(bset);
 515                 if (k < 0)
 516                         goto error;
 517                 isl_seq_clr(bset->ineq[k] + 1, total);
 518                 if (isl_int_is_pos(t)) {
 519                         isl_int_set_si(bset->ineq[k][1 + i], -1);
 520                         isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 521                 } else {
 522                         isl_int_set_si(bset->ineq[k][1 + i], 1);
 523                         isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 524                 }
 525                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
 526
 527                 k = isl_basic_set_alloc_inequality(bset);
 528                 if (k < 0)
 529                         goto error;
 530                 isl_seq_clr(bset->ineq[k] + 1, total);
 531                 if (isl_int_is_pos(t)) {
 532                         isl_int_set_si(bset->ineq[k][1 + i], 1);
 533                         isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 534                 } else {
 535                         isl_int_set_si(bset->ineq[k][1 + i], -1);
 536                         isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 537                 }
 538                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
 539         }
 540
 541         bset = isl_basic_set_finalize(bset);
 542
 543         isl_point_free(pnt1);
 544         isl_point_free(pnt2);
 545
 546         isl_int_clear(t);
 547
 548         return bset;
 549 error:
 550         isl_point_free(pnt1);
 551         isl_point_free(pnt2);
 552         isl_int_clear(t);
 553         isl_basic_set_free(bset);
 554         return NULL;
 555 }
 556
 557 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
 558         __isl_take isl_point *pnt2)
 559 {
 560         isl_basic_set *bset;
 561         bset = isl_basic_set_box_from_points(pnt1, pnt2);
 562         return isl_set_from_basic_set(bset);
 563 }
 564
 565 /* Print the coordinate at position "pos" of the point "pnt".
 566  */
 567 static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
 568         struct isl_print_space_data *data, unsigned pos)
 569 {
 570         isl_point *pnt = data->user;
 571
 572         p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
 573         if (!isl_int_is_one(pnt->vec->el[0])) {
 574                 p = isl_printer_print_str(p, "/");
 575                 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 576         }
 577
 578         return p;
 579 }
 580
 581 __isl_give isl_printer *isl_printer_print_point(
 582         __isl_take isl_printer *p, __isl_keep isl_point *pnt)
 583 {
 584         struct isl_print_space_data data = { 0 };
 585         int i;
 586         unsigned nparam;
 587
 588         if (!pnt)
 589                 return p;
 590         if (isl_point_is_void(pnt)) {
 591                 p = isl_printer_print_str(p, "void");
 592                 return p;
 593         }
 594
 595         nparam = isl_space_dim(pnt->dim, isl_dim_param);
 596         if (nparam > 0) {
 597                 p = isl_printer_print_str(p, "[");
 598                 for (i = 0; i < nparam; ++i) {
 599                         const char *name;
 600                         if (i)
 601                                 p = isl_printer_print_str(p, ", ");
 602                         name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
 603                         if (name) {
 604                                 p = isl_printer_print_str(p, name);
 605                                 p = isl_printer_print_str(p, " = ");
 606                         }
 607                         p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
 608                         if (!isl_int_is_one(pnt->vec->el[0])) {
 609                                 p = isl_printer_print_str(p, "/");
 610                                 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 611                         }
 612                 }
 613                 p = isl_printer_print_str(p, "]");
 614                 p = isl_printer_print_str(p, " -> ");
 615         }
 616         data.print_dim = &print_coordinate;
 617         data.user = pnt;
 618         p = isl_printer_print_str(p, "{ ");
 619         p = isl_print_space(pnt->dim, p, 0, &data);
 620         p = isl_printer_print_str(p, " }");
 621         return p;
 622 }