1 #include <isl_map_private.h>
2 #include <isl_point_private.h>
4 #include <isl_sample.h>
7 #include <isl_space_private.h>
8 #include <isl_val_private.h>
10 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
12 return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
15 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
17 return pnt ? isl_space_copy(pnt->dim) : NULL;
20 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
21 __isl_take isl_vec *vec)
23 struct isl_point *pnt;
28 if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
29 vec = isl_vec_cow(vec);
32 vec->size = 1 + isl_space_dim(dim, isl_dim_all);
35 pnt = isl_alloc_type(dim->ctx, struct isl_point);
50 __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
56 vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
59 isl_int_set_si(vec->el[0], 1);
60 isl_seq_clr(vec->el + 1, vec->size - 1);
61 return isl_point_alloc(dim, vec);
67 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
69 struct isl_point *pnt2;
73 pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
77 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
79 struct isl_point *pnt2;
86 pnt2 = isl_point_dup(pnt);
91 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
100 void isl_point_free(__isl_take isl_point *pnt)
108 isl_space_free(pnt->dim);
109 isl_vec_free(pnt->vec);
113 __isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
118 return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
121 int isl_point_is_void(__isl_keep isl_point *pnt)
126 return pnt->vec->size == 0;
129 int isl_point_get_coordinate(__isl_keep isl_point *pnt,
130 enum isl_dim_type type, int pos, isl_int *v)
132 if (!pnt || isl_point_is_void(pnt))
135 if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
136 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
137 "position out of bounds", return -1);
139 if (type == isl_dim_set)
140 pos += isl_space_dim(pnt->dim, isl_dim_param);
141 isl_int_set(*v, pnt->vec->el[1 + pos]);
146 __isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt,
147 enum isl_dim_type type, int pos, isl_int v)
149 if (!pnt || isl_point_is_void(pnt))
152 pnt = isl_point_cow(pnt);
155 pnt->vec = isl_vec_cow(pnt->vec);
159 if (type == isl_dim_set)
160 pos += isl_space_dim(pnt->dim, isl_dim_param);
162 isl_int_set(pnt->vec->el[1 + pos], v);
170 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
172 __isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
173 enum isl_dim_type type, int pos, __isl_take isl_val *v)
177 if (isl_point_is_void(pnt))
178 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
179 "void point does not have coordinates", goto error);
180 if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
181 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
182 "position out of bounds", goto error);
183 if (!isl_val_is_rat(v))
184 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
185 "expecting rational value", goto error);
187 if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
188 isl_int_eq(pnt->vec->el[0], v->d)) {
193 pnt = isl_point_cow(pnt);
196 pnt->vec = isl_vec_cow(pnt->vec);
200 if (isl_int_eq(pnt->vec->el[0], v->d)) {
201 isl_int_set(pnt->vec->el[1 + pos], v->n);
202 } else if (isl_int_is_one(v->d)) {
203 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
205 isl_seq_scale(pnt->vec->el + 1,
206 pnt->vec->el + 1, v->d, pnt->vec->size - 1);
207 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
208 isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
209 pnt->vec = isl_vec_normalize(pnt->vec);
222 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
223 enum isl_dim_type type, int pos, unsigned val)
225 if (!pnt || isl_point_is_void(pnt))
228 pnt = isl_point_cow(pnt);
231 pnt->vec = isl_vec_cow(pnt->vec);
235 if (type == isl_dim_set)
236 pos += isl_space_dim(pnt->dim, isl_dim_param);
238 isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
246 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
247 enum isl_dim_type type, int pos, unsigned val)
249 if (!pnt || isl_point_is_void(pnt))
252 pnt = isl_point_cow(pnt);
255 pnt->vec = isl_vec_cow(pnt->vec);
259 if (type == isl_dim_set)
260 pos += isl_space_dim(pnt->dim, isl_dim_param);
262 isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
270 struct isl_foreach_point {
271 struct isl_scan_callback callback;
272 int (*fn)(__isl_take isl_point *pnt, void *user);
277 static int foreach_point(struct isl_scan_callback *cb, __isl_take isl_vec *sample)
279 struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
282 pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
284 return fp->fn(pnt, fp->user);
287 int isl_set_foreach_point(__isl_keep isl_set *set,
288 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
290 struct isl_foreach_point fp = { { &foreach_point }, fn, user };
296 fp.dim = isl_set_get_space(set);
300 set = isl_set_copy(set);
301 set = isl_set_cow(set);
302 set = isl_set_make_disjoint(set);
303 set = isl_set_compute_divs(set);
307 for (i = 0; i < set->n; ++i)
308 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
313 isl_space_free(fp.dim);
318 isl_space_free(fp.dim);
322 /* Return 1 if "bmap" contains the point "point".
323 * "bmap" is assumed to have known divs.
324 * The point is first extended with the divs and then passed
325 * to basic_map_contains.
327 int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
328 __isl_keep isl_point *point)
337 isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim), return -1);
338 if (bmap->n_div == 0)
339 return isl_basic_map_contains(bmap, point->vec);
341 dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
342 vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
346 isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
347 for (i = 0; i < bmap->n_div; ++i) {
348 isl_seq_inner_product(bmap->div[i] + 1, vec->el,
349 1 + dim + i, &vec->el[1+dim+i]);
350 isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
354 contains = isl_basic_map_contains(bmap, vec);
360 int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point)
368 map = isl_map_copy(map);
369 map = isl_map_compute_divs(map);
373 for (i = 0; i < map->n; ++i) {
374 found = isl_basic_map_contains_point(map->p[i], point);
388 int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point)
390 return isl_map_contains_point((isl_map *)set, point);
393 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
396 isl_basic_set *model;
398 model = isl_basic_set_empty(isl_space_copy(pnt->dim));
399 bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
400 bset = isl_basic_set_from_underlying_set(bset, model);
406 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
409 bset = isl_basic_set_from_point(pnt);
410 return isl_set_from_basic_set(bset);
413 __isl_give isl_basic_set *isl_basic_set_box_from_points(
414 __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
427 isl_assert(pnt1->dim->ctx,
428 isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
430 if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
431 isl_space *dim = isl_space_copy(pnt1->dim);
432 isl_point_free(pnt1);
433 isl_point_free(pnt2);
435 return isl_basic_set_empty(dim);
437 if (isl_point_is_void(pnt1)) {
438 isl_point_free(pnt1);
440 return isl_basic_set_from_point(pnt2);
442 if (isl_point_is_void(pnt2)) {
443 isl_point_free(pnt2);
445 return isl_basic_set_from_point(pnt1);
448 total = isl_space_dim(pnt1->dim, isl_dim_all);
449 bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
451 for (i = 0; i < total; ++i) {
452 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
453 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
455 k = isl_basic_set_alloc_inequality(bset);
458 isl_seq_clr(bset->ineq[k] + 1, total);
459 if (isl_int_is_pos(t)) {
460 isl_int_set_si(bset->ineq[k][1 + i], -1);
461 isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
463 isl_int_set_si(bset->ineq[k][1 + i], 1);
464 isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
466 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
468 k = isl_basic_set_alloc_inequality(bset);
471 isl_seq_clr(bset->ineq[k] + 1, total);
472 if (isl_int_is_pos(t)) {
473 isl_int_set_si(bset->ineq[k][1 + i], 1);
474 isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
476 isl_int_set_si(bset->ineq[k][1 + i], -1);
477 isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
479 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
482 bset = isl_basic_set_finalize(bset);
484 isl_point_free(pnt1);
485 isl_point_free(pnt2);
491 isl_point_free(pnt1);
492 isl_point_free(pnt2);
497 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
498 __isl_take isl_point *pnt2)
501 bset = isl_basic_set_box_from_points(pnt1, pnt2);
502 return isl_set_from_basic_set(bset);
505 __isl_give isl_printer *isl_printer_print_point(
506 __isl_take isl_printer *p, __isl_keep isl_point *pnt)
514 if (isl_point_is_void(pnt)) {
515 p = isl_printer_print_str(p, "void");
519 nparam = isl_space_dim(pnt->dim, isl_dim_param);
520 dim = isl_space_dim(pnt->dim, isl_dim_set);
522 p = isl_printer_print_str(p, "[");
523 for (i = 0; i < nparam; ++i) {
526 p = isl_printer_print_str(p, ", ");
527 name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
529 p = isl_printer_print_str(p, name);
530 p = isl_printer_print_str(p, " = ");
532 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
533 if (!isl_int_is_one(pnt->vec->el[0])) {
534 p = isl_printer_print_str(p, "/");
535 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
538 p = isl_printer_print_str(p, "]");
539 p = isl_printer_print_str(p, " -> ");
541 p = isl_printer_print_str(p, "[");
542 for (i = 0; i < dim; ++i) {
544 p = isl_printer_print_str(p, ", ");
545 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + nparam + i]);
546 if (!isl_int_is_one(pnt->vec->el[0])) {
547 p = isl_printer_print_str(p, "/");
548 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
551 p = isl_printer_print_str(p, "]");