isl_simple_hull: check for empty/single-disjunct map _after_ detect_equalities
[isl.git] / isl_point.c
bloba78662fea9bc2f2feb319bb9f890db560b7f90d1
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>
12 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
14 return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
17 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
19 return pnt ? isl_space_copy(pnt->dim) : NULL;
22 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
23 __isl_take isl_vec *vec)
25 struct isl_point *pnt;
27 if (!dim || !vec)
28 goto error;
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);
37 pnt = isl_alloc_type(dim->ctx, struct isl_point);
38 if (!pnt)
39 goto error;
41 pnt->ref = 1;
42 pnt->dim = dim;
43 pnt->vec = vec;
45 return pnt;
46 error:
47 isl_space_free(dim);
48 isl_vec_free(vec);
49 return NULL;
52 __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
54 isl_vec *vec;
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;
69 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
71 struct isl_point *pnt2;
73 if (!pnt)
74 return NULL;
75 pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
76 return pnt2;
79 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
81 struct isl_point *pnt2;
82 if (!pnt)
83 return NULL;
85 if (pnt->ref == 1)
86 return pnt;
88 pnt2 = isl_point_dup(pnt);
89 isl_point_free(pnt);
90 return pnt2;
93 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
95 if (!pnt)
96 return NULL;
98 pnt->ref++;
99 return pnt;
102 void isl_point_free(__isl_take isl_point *pnt)
104 if (!pnt)
105 return;
107 if (--pnt->ref > 0)
108 return;
110 isl_space_free(pnt->dim);
111 isl_vec_free(pnt->vec);
112 free(pnt);
115 __isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
117 if (!dim)
118 return NULL;
120 return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
123 isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
125 if (!pnt)
126 return isl_bool_error;
128 return pnt->vec->size == 0;
131 int isl_point_get_coordinate(__isl_keep isl_point *pnt,
132 enum isl_dim_type type, int pos, isl_int *v)
134 if (!pnt || isl_point_is_void(pnt))
135 return -1;
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);
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]);
145 return 0;
148 /* Return the value of coordinate "pos" of type "type" of "pnt".
150 __isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
151 enum isl_dim_type type, int pos)
153 isl_ctx *ctx;
154 isl_val *v;
156 if (!pnt)
157 return NULL;
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);
167 if (type == isl_dim_set)
168 pos += isl_space_dim(pnt->dim, isl_dim_param);
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);
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)
178 if (!pnt || isl_point_is_void(pnt))
179 return pnt;
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;
188 if (type == isl_dim_set)
189 pos += isl_space_dim(pnt->dim, isl_dim_param);
191 isl_int_set(pnt->vec->el[1 + pos], v);
193 return pnt;
194 error:
195 isl_point_free(pnt);
196 return NULL;
199 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
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)
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);
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;
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;
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;
243 isl_val_free(v);
244 return pnt;
245 error:
246 isl_val_free(v);
247 isl_point_free(pnt);
248 return NULL;
251 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
252 enum isl_dim_type type, int pos, unsigned val)
254 if (!pnt || isl_point_is_void(pnt))
255 return pnt;
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;
264 if (type == isl_dim_set)
265 pos += isl_space_dim(pnt->dim, isl_dim_param);
267 isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
269 return pnt;
270 error:
271 isl_point_free(pnt);
272 return NULL;
275 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
276 enum isl_dim_type type, int pos, unsigned val)
278 if (!pnt || isl_point_is_void(pnt))
279 return pnt;
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;
288 if (type == isl_dim_set)
289 pos += isl_space_dim(pnt->dim, isl_dim_param);
291 isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
293 return pnt;
294 error:
295 isl_point_free(pnt);
296 return NULL;
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;
306 static isl_stat foreach_point(struct isl_scan_callback *cb,
307 __isl_take isl_vec *sample)
309 struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
310 isl_point *pnt;
312 pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
314 return fp->fn(pnt, fp->user);
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)
320 struct isl_foreach_point fp = { { &foreach_point }, fn, user };
321 int i;
323 if (!set)
324 return isl_stat_error;
326 fp.dim = isl_set_get_space(set);
327 if (!fp.dim)
328 return isl_stat_error;
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;
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;
342 isl_set_free(set);
343 isl_space_free(fp.dim);
345 return isl_stat_ok;
346 error:
347 isl_set_free(set);
348 isl_space_free(fp.dim);
349 return isl_stat_error;
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.
357 isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
358 __isl_keep isl_point *point)
360 int i;
361 struct isl_vec *vec;
362 unsigned dim;
363 isl_bool contains;
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);
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;
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]);
385 contains = isl_basic_map_contains(bmap, vec);
387 isl_vec_free(vec);
388 return contains;
391 int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point)
393 int i;
394 int found = 0;
396 if (!map || !point)
397 return -1;
399 map = isl_map_copy(map);
400 map = isl_map_compute_divs(map);
401 if (!map)
402 return -1;
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;
411 isl_map_free(map);
413 return found;
414 error:
415 isl_map_free(map);
416 return -1;
419 isl_bool isl_set_contains_point(__isl_keep isl_set *set,
420 __isl_keep isl_point *point)
422 return isl_map_contains_point((isl_map *)set, point);
425 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
427 isl_basic_set *bset;
428 isl_basic_set *model;
430 if (!pnt)
431 return NULL;
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);
438 return bset;
441 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
443 isl_basic_set *bset;
444 bset = isl_basic_set_from_point(pnt);
445 return isl_set_from_basic_set(bset);
448 __isl_give isl_basic_set *isl_basic_set_box_from_points(
449 __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
451 isl_basic_set *bset;
452 unsigned total;
453 int i;
454 int k;
455 isl_int t;
457 isl_int_init(t);
459 if (!pnt1 || !pnt2)
460 goto error;
462 isl_assert(pnt1->dim->ctx,
463 isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
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);
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);
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);
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);
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]);
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]);
501 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
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]);
514 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
517 bset = isl_basic_set_finalize(bset);
519 isl_point_free(pnt1);
520 isl_point_free(pnt2);
522 isl_int_clear(t);
524 return bset;
525 error:
526 isl_point_free(pnt1);
527 isl_point_free(pnt2);
528 isl_int_clear(t);
529 return NULL;
532 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
533 __isl_take isl_point *pnt2)
535 isl_basic_set *bset;
536 bset = isl_basic_set_box_from_points(pnt1, pnt2);
537 return isl_set_from_basic_set(bset);
540 __isl_give isl_printer *isl_printer_print_point(
541 __isl_take isl_printer *p, __isl_keep isl_point *pnt)
543 int i;
544 unsigned nparam;
545 unsigned dim;
547 if (!pnt)
548 return p;
549 if (isl_point_is_void(pnt)) {
550 p = isl_printer_print_str(p, "void");
551 return p;
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, " = ");
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]);
573 p = isl_printer_print_str(p, "]");
574 p = isl_printer_print_str(p, " -> ");
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]);
586 p = isl_printer_print_str(p, "]");
587 return p;