isl_point.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  * Copyright 2015      Sven Verdoolaege
   5  * Copyright 2019,2022 Cerebras Systems
   6  *
   7  * Use of this software is governed by the MIT license
   8  *
   9  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  10  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  11  * 91893 Orsay, France
  12  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  13  * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
  14  * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
  15  */
  16
  17 #include <isl_map_private.h>
  18 #include <isl_point_private.h>
  19 #include <isl/set.h>
  20 #include <isl/union_set.h>
  21 #include <isl_sample.h>
  22 #include <isl_scan.h>
  23 #include <isl_seq.h>
  24 #include <isl_space_private.h>
  25 #include <isl_local_private.h>
  26 #include <isl_val_private.h>
  27 #include <isl_vec_private.h>
  28 #include <isl_output_private.h>
  29
  30 #include <set_to_map.c>
  31
  32 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
  33 {
  34         return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
  35 }
  36
  37 /* Return the space of "pnt".
  38  */
  39 __isl_keep isl_space *isl_point_peek_space(__isl_keep isl_point *pnt)
  40 {
  41         return pnt ? pnt->dim : NULL;
  42 }
  43
  44 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
  45 {
  46         return isl_space_copy(isl_point_peek_space(pnt));
  47 }
  48
  49 #undef TYPE1
  50 #define TYPE1           isl_basic_map
  51 #undef TYPE2
  52 #define TYPE2           isl_point
  53 #undef TYPE_PAIR
  54 #define TYPE_PAIR       isl_basic_map_point
  55
  56 static
  57 #include "isl_type_has_equal_space_templ.c"
  58 static
  59 #include "isl_type_check_equal_space_templ.c"
  60
  61 #undef TYPE
  62 #define TYPE isl_point
  63
  64 #include "isl_check_named_params_templ.c"
  65
  66 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *space,
  67         __isl_take isl_vec *vec)
  68 {
  69         struct isl_point *pnt;
  70         isl_size dim;
  71
  72         dim = isl_space_dim(space, isl_dim_all);
  73         if (dim < 0 || !vec)
  74                 goto error;
  75
  76         if (vec->size > 1 + dim) {
  77                 vec = isl_vec_cow(vec);
  78                 if (!vec)
  79                         goto error;
  80                 vec->size = 1 + dim;
  81         }
  82
  83         pnt = isl_alloc_type(space->ctx, struct isl_point);
  84         if (!pnt)
  85                 goto error;
  86
  87         pnt->ref = 1;
  88         pnt->dim = space;
  89         pnt->vec = vec;
  90
  91         return pnt;
  92 error:
  93         isl_space_free(space);
  94         isl_vec_free(vec);
  95         return NULL;
  96 }
  97
  98 __isl_give isl_point *isl_point_zero(__isl_take isl_space *space)
  99 {
 100         isl_vec *vec;
 101         isl_size dim;
 102
 103         dim = isl_space_dim(space, isl_dim_all);
 104         if (dim < 0)
 105                 goto error;
 106         vec = isl_vec_alloc(space->ctx, 1 + dim);
 107         if (!vec)
 108                 goto error;
 109         isl_int_set_si(vec->el[0], 1);
 110         isl_seq_clr(vec->el + 1, vec->size - 1);
 111         return isl_point_alloc(space, vec);
 112 error:
 113         isl_space_free(space);
 114         return NULL;
 115 }
 116
 117 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
 118 {
 119         struct isl_point *pnt2;
 120
 121         if (!pnt)
 122                 return NULL;
 123         pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
 124         return pnt2;
 125 }
 126
 127 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
 128 {
 129         struct isl_point *pnt2;
 130         if (!pnt)
 131                 return NULL;
 132
 133         if (pnt->ref == 1)
 134                 return pnt;
 135
 136         pnt2 = isl_point_dup(pnt);
 137         isl_point_free(pnt);
 138         return pnt2;
 139 }
 140
 141 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
 142 {
 143         if (!pnt)
 144                 return NULL;
 145
 146         pnt->ref++;
 147         return pnt;
 148 }
 149
 150 __isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
 151 {
 152         if (!pnt)
 153                 return NULL;
 154
 155         if (--pnt->ref > 0)
 156                 return NULL;
 157
 158         isl_space_free(pnt->dim);
 159         isl_vec_free(pnt->vec);
 160         free(pnt);
 161         return NULL;
 162 }
 163
 164 __isl_give isl_point *isl_point_void(__isl_take isl_space *space)
 165 {
 166         if (!space)
 167                 return NULL;
 168
 169         return isl_point_alloc(space, isl_vec_alloc(space->ctx, 0));
 170 }
 171
 172 isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
 173 {
 174         if (!pnt)
 175                 return isl_bool_error;
 176
 177         return isl_bool_ok(pnt->vec->size == 0);
 178 }
 179
 180 /* Return the space of "pnt".
 181  * This may be either a copy or the space itself
 182  * if there is only one reference to "pnt".
 183  * This allows the space to be modified inplace
 184  * if both the point and its space have only a single reference.
 185  * The caller is not allowed to modify "pnt" between this call and
 186  * a subsequent call to isl_point_restore_space.
 187  * The only exception is that isl_point_free can be called instead.
 188  */
 189 __isl_give isl_space *isl_point_take_space(__isl_keep isl_point *pnt)
 190 {
 191         isl_space *space;
 192
 193         if (!pnt)
 194                 return NULL;
 195         if (pnt->ref != 1)
 196                 return isl_point_get_space(pnt);
 197         space = pnt->dim;
 198         pnt->dim = NULL;
 199         return space;
 200 }
 201
 202 /* Set the space of "pnt" to "space", where the space of "pnt" may be missing
 203  * due to a preceding call to isl_point_take_space.
 204  * However, in this case, "pnt" only has a single reference and
 205  * then the call to isl_point_cow has no effect.
 206  */
 207 __isl_give isl_point *isl_point_restore_space(__isl_take isl_point *pnt,
 208         __isl_take isl_space *space)
 209 {
 210         if (!pnt || !space)
 211                 goto error;
 212
 213         if (pnt->dim == space) {
 214                 isl_space_free(space);
 215                 return pnt;
 216         }
 217
 218         pnt = isl_point_cow(pnt);
 219         if (!pnt)
 220                 goto error;
 221         isl_space_free(pnt->dim);
 222         pnt->dim = space;
 223
 224         return pnt;
 225 error:
 226         isl_point_free(pnt);
 227         isl_space_free(space);
 228         return NULL;
 229 }
 230
 231 /* Return the coordinate vector of "pnt".
 232  */
 233 __isl_keep isl_vec *isl_point_peek_vec(__isl_keep isl_point *pnt)
 234 {
 235         return pnt ? pnt->vec : NULL;
 236 }
 237
 238 /* Return a copy of the coordinate vector of "pnt".
 239  */
 240 __isl_give isl_vec *isl_point_get_vec(__isl_keep isl_point *pnt)
 241 {
 242         return isl_vec_copy(isl_point_peek_vec(pnt));
 243 }
 244
 245 /* Return the coordinate vector of "pnt".
 246  * This may be either a copy or the coordinate vector itself
 247  * if there is only one reference to "pnt".
 248  * This allows the coordinate vector to be modified inplace
 249  * if both the point and its coordinate vector have only a single reference.
 250  * The caller is not allowed to modify "pnt" between this call and
 251  * a subsequent call to isl_point_restore_vec.
 252  * The only exception is that isl_point_free can be called instead.
 253  */
 254 __isl_give isl_vec *isl_point_take_vec(__isl_keep isl_point *pnt)
 255 {
 256         isl_vec *vec;
 257
 258         if (!pnt)
 259                 return NULL;
 260         if (pnt->ref != 1)
 261                 return isl_point_get_vec(pnt);
 262         vec = pnt->vec;
 263         pnt->vec = NULL;
 264         return vec;
 265 }
 266
 267 /* Set the coordinate vector of "pnt" to "vec",
 268  * where the coordinate vector of "pnt" may be missing
 269  * due to a preceding call to isl_point_take_vec.
 270  * However, in this case, "pnt" only has a single reference and
 271  * then the call to isl_point_cow has no effect.
 272  */
 273 __isl_give isl_point *isl_point_restore_vec(__isl_take isl_point *pnt,
 274         __isl_take isl_vec *vec)
 275 {
 276         if (!pnt || !vec)
 277                 goto error;
 278
 279         if (pnt->vec == vec) {
 280                 isl_vec_free(vec);
 281                 return pnt;
 282         }
 283
 284         pnt = isl_point_cow(pnt);
 285         if (!pnt)
 286                 goto error;
 287         isl_vec_free(pnt->vec);
 288         pnt->vec = vec;
 289
 290         return pnt;
 291 error:
 292         isl_point_free(pnt);
 293         isl_vec_free(vec);
 294         return NULL;
 295 }
 296
 297 /* Return the number of variables of the given type.
 298  */
 299 static isl_size isl_point_dim(__isl_keep isl_point *pnt, enum isl_dim_type type)
 300 {
 301         return isl_space_dim(isl_point_peek_space(pnt), type);
 302 }
 303
 304 /* Return the position of the coordinates of the given type
 305  * within the sequence of coordinates of "pnt".
 306  */
 307 static isl_size isl_point_var_offset(__isl_keep isl_point *pnt,
 308         enum isl_dim_type type)
 309 {
 310         return pnt ? isl_space_offset(pnt->dim, type) : isl_size_error;
 311 }
 312
 313 /* Reorder the coordinates of "pnt" based on the given reordering.
 314  */
 315 static __isl_give isl_point *isl_point_reorder(__isl_take isl_point *pnt,
 316         __isl_take isl_reordering *r)
 317 {
 318         isl_vec *vec;
 319
 320         isl_space_free(isl_point_take_space(pnt));
 321         pnt = isl_point_restore_space(pnt, isl_reordering_get_space(r));
 322
 323         vec = isl_point_take_vec(pnt);
 324         vec = isl_vec_reorder(vec, 1, isl_reordering_copy(r));
 325         pnt = isl_point_restore_vec(pnt, vec);
 326
 327         return pnt;
 328 }
 329
 330 /* Align the parameters of "pnt" along those of "model".
 331  *
 332  * Note that "model" is not allowed to have any parameters
 333  * that do not already appear in "pnt" since "pnt" does not specify
 334  * any value for such parameters.
 335  */
 336 __isl_give isl_point *isl_point_align_params(__isl_take isl_point *pnt,
 337         __isl_take isl_space *model)
 338 {
 339         isl_space *space;
 340         isl_bool equal_params;
 341
 342         space = isl_point_peek_space(pnt);
 343         equal_params = isl_space_has_equal_params(space, model);
 344         if (equal_params < 0)
 345                 goto error;
 346         if (!equal_params) {
 347                 isl_reordering *r;
 348
 349                 r = isl_parameter_alignment_reordering(space, model);
 350                 if (!r)
 351                         goto error;
 352                 if (r->src_len != r->dst_len)
 353                         isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 354                                 "no value specified for some parameters",
 355                                 r = isl_reordering_free(r));
 356                 pnt = isl_point_reorder(pnt, r);
 357         }
 358
 359         isl_space_free(model);
 360         return pnt;
 361 error:
 362         isl_space_free(model);
 363         isl_point_free(pnt);
 364         return NULL;
 365 }
 366
 367 #undef TYPE
 368 #define TYPE    isl_point
 369 static
 370 #include "check_type_range_templ.c"
 371
 372 /* Return the value of coordinate "pos" of type "type" of "pnt".
 373  */
 374 __isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
 375         enum isl_dim_type type, int pos)
 376 {
 377         isl_ctx *ctx;
 378         isl_val *v;
 379         isl_size off;
 380
 381         if (!pnt)
 382                 return NULL;
 383
 384         ctx = isl_point_get_ctx(pnt);
 385         if (isl_point_is_void(pnt))
 386                 isl_die(ctx, isl_error_invalid,
 387                         "void point does not have coordinates", return NULL);
 388         if (isl_point_check_range(pnt, type, pos, 1) < 0)
 389                 return NULL;
 390
 391         off = isl_point_var_offset(pnt, type);
 392         if (off < 0)
 393                 return NULL;
 394         pos += off;
 395
 396         v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
 397                                                 pnt->vec->el[0]);
 398         return isl_val_normalize(v);
 399 }
 400
 401 /* Set all entries of "mv" to NaN.
 402  */
 403 static __isl_give isl_multi_val *set_nan(__isl_take isl_multi_val *mv)
 404 {
 405         int i;
 406         isl_size n;
 407         isl_val *v;
 408
 409         n = isl_multi_val_size(mv);
 410         if (n < 0)
 411                 return isl_multi_val_free(mv);
 412         v = isl_val_nan(isl_multi_val_get_ctx(mv));
 413         for (i = 0; i < n; ++i)
 414                 mv = isl_multi_val_set_at(mv, i, isl_val_copy(v));
 415         isl_val_free(v);
 416
 417         return mv;
 418 }
 419
 420 /* Return the values of the set dimensions of "pnt".
 421  * Return a sequence of NaNs in case of a void point.
 422  */
 423 __isl_give isl_multi_val *isl_point_get_multi_val(__isl_keep isl_point *pnt)
 424 {
 425         int i;
 426         isl_bool is_void;
 427         isl_size n;
 428         isl_multi_val *mv;
 429
 430         is_void = isl_point_is_void(pnt);
 431         if (is_void < 0)
 432                 return NULL;
 433
 434         mv = isl_multi_val_alloc(isl_point_get_space(pnt));
 435         if (is_void)
 436                 return set_nan(mv);
 437         n = isl_multi_val_size(mv);
 438         if (n < 0)
 439                 return isl_multi_val_free(mv);
 440         for (i = 0; i < n; ++i) {
 441                 isl_val *v;
 442
 443                 v = isl_point_get_coordinate_val(pnt, isl_dim_set, i);
 444                 mv = isl_multi_val_set_at(mv, i, v);
 445         }
 446
 447         return mv;
 448 }
 449
 450 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
 451  */
 452 __isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
 453         enum isl_dim_type type, int pos, __isl_take isl_val *v)
 454 {
 455         if (!pnt || !v)
 456                 goto error;
 457         if (isl_point_is_void(pnt))
 458                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 459                         "void point does not have coordinates", goto error);
 460         if (isl_point_check_range(pnt, type, pos, 1) < 0)
 461                 goto error;
 462         if (!isl_val_is_rat(v))
 463                 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 464                         "expecting rational value", goto error);
 465
 466         pos += isl_space_offset(isl_point_peek_space(pnt), type);
 467         if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
 468             isl_int_eq(pnt->vec->el[0], v->d)) {
 469                 isl_val_free(v);
 470                 return pnt;
 471         }
 472
 473         pnt = isl_point_cow(pnt);
 474         if (!pnt)
 475                 goto error;
 476         pnt->vec = isl_vec_cow(pnt->vec);
 477         if (!pnt->vec)
 478                 goto error;
 479
 480         if (isl_int_eq(pnt->vec->el[0], v->d)) {
 481                 isl_int_set(pnt->vec->el[1 + pos], v->n);
 482         } else if (isl_int_is_one(v->d)) {
 483                 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 484         } else {
 485                 isl_seq_scale(pnt->vec->el + 1,
 486                                 pnt->vec->el + 1, v->d, pnt->vec->size - 1);
 487                 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 488                 isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
 489                 pnt->vec = isl_vec_normalize(pnt->vec);
 490                 if (!pnt->vec)
 491                         goto error;
 492         }
 493
 494         isl_val_free(v);
 495         return pnt;
 496 error:
 497         isl_val_free(v);
 498         isl_point_free(pnt);
 499         return NULL;
 500 }
 501
 502 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
 503         enum isl_dim_type type, int pos, unsigned val)
 504 {
 505         isl_size off;
 506
 507         if (!pnt || isl_point_is_void(pnt))
 508                 return pnt;
 509
 510         pnt = isl_point_cow(pnt);
 511         if (!pnt)
 512                 return NULL;
 513         pnt->vec = isl_vec_cow(pnt->vec);
 514         if (!pnt->vec)
 515                 goto error;
 516
 517         off = isl_point_var_offset(pnt, type);
 518         if (off < 0)
 519                 goto error;
 520         pos += off;
 521
 522         isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 523
 524         return pnt;
 525 error:
 526         isl_point_free(pnt);
 527         return NULL;
 528 }
 529
 530 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
 531         enum isl_dim_type type, int pos, unsigned val)
 532 {
 533         isl_size off;
 534
 535         if (!pnt || isl_point_is_void(pnt))
 536                 return pnt;
 537
 538         pnt = isl_point_cow(pnt);
 539         if (!pnt)
 540                 return NULL;
 541         pnt->vec = isl_vec_cow(pnt->vec);
 542         if (!pnt->vec)
 543                 goto error;
 544
 545         off = isl_point_var_offset(pnt, type);
 546         if (off < 0)
 547                 goto error;
 548         pos += off;
 549
 550         isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 551
 552         return pnt;
 553 error:
 554         isl_point_free(pnt);
 555         return NULL;
 556 }
 557
 558 struct isl_foreach_point {
 559         struct isl_scan_callback callback;
 560         isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
 561         void *user;
 562         isl_space *dim;
 563 };
 564
 565 static isl_stat foreach_point(struct isl_scan_callback *cb,
 566         __isl_take isl_vec *sample)
 567 {
 568         struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
 569         isl_point *pnt;
 570
 571         pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
 572
 573         return fp->fn(pnt, fp->user);
 574 }
 575
 576 isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
 577         isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 578 {
 579         struct isl_foreach_point fp = { { &foreach_point }, fn, user };
 580         int i;
 581
 582         if (!set)
 583                 return isl_stat_error;
 584
 585         fp.dim = isl_set_get_space(set);
 586         if (!fp.dim)
 587                 return isl_stat_error;
 588
 589         set = isl_set_copy(set);
 590         set = isl_set_cow(set);
 591         set = isl_set_make_disjoint(set);
 592         set = isl_set_compute_divs(set);
 593         if (!set)
 594                 goto error;
 595
 596         for (i = 0; i < set->n; ++i)
 597                 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
 598                                         &fp.callback) < 0)
 599                         goto error;
 600
 601         isl_set_free(set);
 602         isl_space_free(fp.dim);
 603
 604         return isl_stat_ok;
 605 error:
 606         isl_set_free(set);
 607         isl_space_free(fp.dim);
 608         return isl_stat_error;
 609 }
 610
 611 /* Return 1 if "bmap" contains the point "point".
 612  * "bmap" is assumed to have known divs.
 613  * The point is first extended with the divs and then passed
 614  * to basic_map_contains.
 615  */
 616 isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
 617         __isl_keep isl_point *point)
 618 {
 619         isl_local *local;
 620         isl_vec *vec;
 621         isl_bool contains;
 622
 623         if (isl_basic_map_point_check_equal_space(bmap, point) < 0)
 624                 return isl_bool_error;
 625         if (bmap->n_div == 0)
 626                 return isl_basic_map_contains(bmap, point->vec);
 627
 628         local = isl_local_alloc_from_mat(isl_basic_map_get_divs(bmap));
 629         vec = isl_point_get_vec(point);
 630         vec = isl_local_extend_point_vec(local, vec);
 631         isl_local_free(local);
 632
 633         contains = isl_basic_map_contains(bmap, vec);
 634
 635         isl_vec_free(vec);
 636         return contains;
 637 }
 638
 639 isl_bool isl_map_contains_point(__isl_keep isl_map *map,
 640         __isl_keep isl_point *point)
 641 {
 642         int i;
 643         isl_bool found = isl_bool_false;
 644
 645         if (!map || !point)
 646                 return isl_bool_error;
 647
 648         map = isl_map_copy(map);
 649         map = isl_map_compute_divs(map);
 650         if (!map)
 651                 return isl_bool_error;
 652
 653         for (i = 0; i < map->n; ++i) {
 654                 found = isl_basic_map_contains_point(map->p[i], point);
 655                 if (found < 0)
 656                         goto error;
 657                 if (found)
 658                         break;
 659         }
 660         isl_map_free(map);
 661
 662         return found;
 663 error:
 664         isl_map_free(map);
 665         return isl_bool_error;
 666 }
 667
 668 isl_bool isl_set_contains_point(__isl_keep isl_set *set,
 669         __isl_keep isl_point *point)
 670 {
 671         return isl_map_contains_point(set_to_map(set), point);
 672 }
 673
 674 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
 675 {
 676         isl_basic_set *bset;
 677         isl_basic_set *model;
 678
 679         if (!pnt)
 680                 return NULL;
 681
 682         model = isl_basic_set_empty(isl_space_copy(pnt->dim));
 683         bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
 684         bset = isl_basic_set_from_underlying_set(bset, model);
 685         isl_point_free(pnt);
 686
 687         return bset;
 688 }
 689
 690 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
 691 {
 692         isl_basic_set *bset;
 693         bset = isl_basic_set_from_point(pnt);
 694         return isl_set_from_basic_set(bset);
 695 }
 696
 697 /* This function performs the same operation as isl_set_from_point,
 698  * but is considered as a function on an isl_point when exported.
 699  */
 700 __isl_give isl_set *isl_point_to_set(__isl_take isl_point *pnt)
 701 {
 702         return isl_set_from_point(pnt);
 703 }
 704
 705 /* Construct a union set, containing the single element "pnt".
 706  * If "pnt" is void, then return an empty union set.
 707  */
 708 __isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
 709 {
 710         if (!pnt)
 711                 return NULL;
 712         if (isl_point_is_void(pnt)) {
 713                 isl_space *space;
 714
 715                 space = isl_point_get_space(pnt);
 716                 isl_point_free(pnt);
 717                 return isl_union_set_empty(space);
 718         }
 719
 720         return isl_union_set_from_set(isl_set_from_point(pnt));
 721 }
 722
 723 __isl_give isl_basic_set *isl_basic_set_box_from_points(
 724         __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
 725 {
 726         isl_basic_set *bset = NULL;
 727         isl_size total;
 728         int i;
 729         int k;
 730         isl_int t;
 731
 732         isl_int_init(t);
 733
 734         if (!pnt1 || !pnt2)
 735                 goto error;
 736
 737         isl_assert(pnt1->dim->ctx,
 738                         isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
 739
 740         if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
 741                 isl_space *space = isl_space_copy(pnt1->dim);
 742                 isl_point_free(pnt1);
 743                 isl_point_free(pnt2);
 744                 isl_int_clear(t);
 745                 return isl_basic_set_empty(space);
 746         }
 747         if (isl_point_is_void(pnt1)) {
 748                 isl_point_free(pnt1);
 749                 isl_int_clear(t);
 750                 return isl_basic_set_from_point(pnt2);
 751         }
 752         if (isl_point_is_void(pnt2)) {
 753                 isl_point_free(pnt2);
 754                 isl_int_clear(t);
 755                 return isl_basic_set_from_point(pnt1);
 756         }
 757
 758         total = isl_point_dim(pnt1, isl_dim_all);
 759         if (total < 0)
 760                 goto error;
 761         bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
 762
 763         for (i = 0; i < total; ++i) {
 764                 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
 765                 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
 766
 767                 k = isl_basic_set_alloc_inequality(bset);
 768                 if (k < 0)
 769                         goto error;
 770                 isl_seq_clr(bset->ineq[k] + 1, total);
 771                 if (isl_int_is_pos(t)) {
 772                         isl_int_set_si(bset->ineq[k][1 + i], -1);
 773                         isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 774                 } else {
 775                         isl_int_set_si(bset->ineq[k][1 + i], 1);
 776                         isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 777                 }
 778                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
 779
 780                 k = isl_basic_set_alloc_inequality(bset);
 781                 if (k < 0)
 782                         goto error;
 783                 isl_seq_clr(bset->ineq[k] + 1, total);
 784                 if (isl_int_is_pos(t)) {
 785                         isl_int_set_si(bset->ineq[k][1 + i], 1);
 786                         isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 787                 } else {
 788                         isl_int_set_si(bset->ineq[k][1 + i], -1);
 789                         isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 790                 }
 791                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
 792         }
 793
 794         bset = isl_basic_set_finalize(bset);
 795
 796         isl_point_free(pnt1);
 797         isl_point_free(pnt2);
 798
 799         isl_int_clear(t);
 800
 801         return bset;
 802 error:
 803         isl_point_free(pnt1);
 804         isl_point_free(pnt2);
 805         isl_int_clear(t);
 806         isl_basic_set_free(bset);
 807         return NULL;
 808 }
 809
 810 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
 811         __isl_take isl_point *pnt2)
 812 {
 813         isl_basic_set *bset;
 814         bset = isl_basic_set_box_from_points(pnt1, pnt2);
 815         return isl_set_from_basic_set(bset);
 816 }
 817
 818 /* Print the coordinate at position "pos" of the point "pnt".
 819  */
 820 static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
 821         struct isl_print_space_data *data, unsigned pos)
 822 {
 823         isl_point *pnt = data->user;
 824
 825         pos += isl_space_offset(data->space, data->type);
 826         p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
 827         if (!isl_int_is_one(pnt->vec->el[0])) {
 828                 p = isl_printer_print_str(p, "/");
 829                 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 830         }
 831
 832         return p;
 833 }
 834
 835 __isl_give isl_printer *isl_printer_print_point(
 836         __isl_take isl_printer *p, __isl_keep isl_point *pnt)
 837 {
 838         struct isl_print_space_data data = { 0 };
 839         int i;
 840         isl_size nparam;
 841
 842         if (!pnt)
 843                 return p;
 844         if (isl_point_is_void(pnt)) {
 845                 p = isl_printer_print_str(p, "void");
 846                 return p;
 847         }
 848
 849         nparam = isl_point_dim(pnt, isl_dim_param);
 850         if (nparam < 0)
 851                 return isl_printer_free(p);
 852         if (nparam > 0) {
 853                 p = isl_printer_print_str(p, "[");
 854                 for (i = 0; i < nparam; ++i) {
 855                         const char *name;
 856                         if (i)
 857                                 p = isl_printer_print_str(p, ", ");
 858                         name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
 859                         if (name) {
 860                                 p = isl_printer_print_str(p, name);
 861                                 p = isl_printer_print_str(p, " = ");
 862                         }
 863                         p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
 864                         if (!isl_int_is_one(pnt->vec->el[0])) {
 865                                 p = isl_printer_print_str(p, "/");
 866                                 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 867                         }
 868                 }
 869                 p = isl_printer_print_str(p, "]");
 870                 p = isl_printer_print_str(p, " -> ");
 871         }
 872         data.print_dim = &print_coordinate;
 873         data.user = pnt;
 874         p = isl_printer_print_str(p, "{ ");
 875         p = isl_print_space(pnt->dim, p, 0, &data);
 876         p = isl_printer_print_str(p, " }");
 877         return p;
 878 }