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