isl_point.c

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