isl_input.c: obj_read: extract out obj_read_disjuncts
[isl.git] / isl_point.c
blob2d5b306b57737733df7a1115eeeda8a03310b0ce
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>
13 #include <set_to_map.c>
15 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
17 return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
20 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
22 return pnt ? isl_space_copy(pnt->dim) : NULL;
25 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
26 __isl_take isl_vec *vec)
28 struct isl_point *pnt;
30 if (!dim || !vec)
31 goto error;
33 if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
34 vec = isl_vec_cow(vec);
35 if (!vec)
36 goto error;
37 vec->size = 1 + isl_space_dim(dim, isl_dim_all);
40 pnt = isl_alloc_type(dim->ctx, struct isl_point);
41 if (!pnt)
42 goto error;
44 pnt->ref = 1;
45 pnt->dim = dim;
46 pnt->vec = vec;
48 return pnt;
49 error:
50 isl_space_free(dim);
51 isl_vec_free(vec);
52 return NULL;
55 __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
57 isl_vec *vec;
59 if (!dim)
60 return NULL;
61 vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
62 if (!vec)
63 goto error;
64 isl_int_set_si(vec->el[0], 1);
65 isl_seq_clr(vec->el + 1, vec->size - 1);
66 return isl_point_alloc(dim, vec);
67 error:
68 isl_space_free(dim);
69 return NULL;
72 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
74 struct isl_point *pnt2;
76 if (!pnt)
77 return NULL;
78 pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
79 return pnt2;
82 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
84 struct isl_point *pnt2;
85 if (!pnt)
86 return NULL;
88 if (pnt->ref == 1)
89 return pnt;
91 pnt2 = isl_point_dup(pnt);
92 isl_point_free(pnt);
93 return pnt2;
96 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
98 if (!pnt)
99 return NULL;
101 pnt->ref++;
102 return pnt;
105 __isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
107 if (!pnt)
108 return NULL;
110 if (--pnt->ref > 0)
111 return NULL;
113 isl_space_free(pnt->dim);
114 isl_vec_free(pnt->vec);
115 free(pnt);
116 return NULL;
119 __isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
121 if (!dim)
122 return NULL;
124 return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
127 isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
129 if (!pnt)
130 return isl_bool_error;
132 return pnt->vec->size == 0;
135 /* Return the value of coordinate "pos" of type "type" of "pnt".
137 __isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
138 enum isl_dim_type type, int pos)
140 isl_ctx *ctx;
141 isl_val *v;
143 if (!pnt)
144 return NULL;
146 ctx = isl_point_get_ctx(pnt);
147 if (isl_point_is_void(pnt))
148 isl_die(ctx, isl_error_invalid,
149 "void point does not have coordinates", return NULL);
150 if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
151 isl_die(ctx, isl_error_invalid,
152 "position out of bounds", return NULL);
154 if (type == isl_dim_set)
155 pos += isl_space_dim(pnt->dim, isl_dim_param);
157 v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
158 pnt->vec->el[0]);
159 return isl_val_normalize(v);
162 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
164 __isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
165 enum isl_dim_type type, int pos, __isl_take isl_val *v)
167 if (!pnt || !v)
168 goto error;
169 if (isl_point_is_void(pnt))
170 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
171 "void point does not have coordinates", goto error);
172 if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
173 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
174 "position out of bounds", goto error);
175 if (!isl_val_is_rat(v))
176 isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
177 "expecting rational value", goto error);
179 if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
180 isl_int_eq(pnt->vec->el[0], v->d)) {
181 isl_val_free(v);
182 return pnt;
185 pnt = isl_point_cow(pnt);
186 if (!pnt)
187 goto error;
188 pnt->vec = isl_vec_cow(pnt->vec);
189 if (!pnt->vec)
190 goto error;
192 if (isl_int_eq(pnt->vec->el[0], v->d)) {
193 isl_int_set(pnt->vec->el[1 + pos], v->n);
194 } else if (isl_int_is_one(v->d)) {
195 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
196 } else {
197 isl_seq_scale(pnt->vec->el + 1,
198 pnt->vec->el + 1, v->d, pnt->vec->size - 1);
199 isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
200 isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
201 pnt->vec = isl_vec_normalize(pnt->vec);
202 if (!pnt->vec)
203 goto error;
206 isl_val_free(v);
207 return pnt;
208 error:
209 isl_val_free(v);
210 isl_point_free(pnt);
211 return NULL;
214 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
215 enum isl_dim_type type, int pos, unsigned val)
217 if (!pnt || isl_point_is_void(pnt))
218 return pnt;
220 pnt = isl_point_cow(pnt);
221 if (!pnt)
222 return NULL;
223 pnt->vec = isl_vec_cow(pnt->vec);
224 if (!pnt->vec)
225 goto error;
227 if (type == isl_dim_set)
228 pos += isl_space_dim(pnt->dim, isl_dim_param);
230 isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
232 return pnt;
233 error:
234 isl_point_free(pnt);
235 return NULL;
238 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
239 enum isl_dim_type type, int pos, unsigned val)
241 if (!pnt || isl_point_is_void(pnt))
242 return pnt;
244 pnt = isl_point_cow(pnt);
245 if (!pnt)
246 return NULL;
247 pnt->vec = isl_vec_cow(pnt->vec);
248 if (!pnt->vec)
249 goto error;
251 if (type == isl_dim_set)
252 pos += isl_space_dim(pnt->dim, isl_dim_param);
254 isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
256 return pnt;
257 error:
258 isl_point_free(pnt);
259 return NULL;
262 struct isl_foreach_point {
263 struct isl_scan_callback callback;
264 isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
265 void *user;
266 isl_space *dim;
269 static isl_stat foreach_point(struct isl_scan_callback *cb,
270 __isl_take isl_vec *sample)
272 struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
273 isl_point *pnt;
275 pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
277 return fp->fn(pnt, fp->user);
280 isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
281 isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
283 struct isl_foreach_point fp = { { &foreach_point }, fn, user };
284 int i;
286 if (!set)
287 return isl_stat_error;
289 fp.dim = isl_set_get_space(set);
290 if (!fp.dim)
291 return isl_stat_error;
293 set = isl_set_copy(set);
294 set = isl_set_cow(set);
295 set = isl_set_make_disjoint(set);
296 set = isl_set_compute_divs(set);
297 if (!set)
298 goto error;
300 for (i = 0; i < set->n; ++i)
301 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
302 &fp.callback) < 0)
303 goto error;
305 isl_set_free(set);
306 isl_space_free(fp.dim);
308 return isl_stat_ok;
309 error:
310 isl_set_free(set);
311 isl_space_free(fp.dim);
312 return isl_stat_error;
315 /* Return 1 if "bmap" contains the point "point".
316 * "bmap" is assumed to have known divs.
317 * The point is first extended with the divs and then passed
318 * to basic_map_contains.
320 isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
321 __isl_keep isl_point *point)
323 int i;
324 struct isl_vec *vec;
325 unsigned dim;
326 isl_bool contains;
328 if (!bmap || !point)
329 return isl_bool_error;
330 isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim),
331 return isl_bool_error);
332 if (bmap->n_div == 0)
333 return isl_basic_map_contains(bmap, point->vec);
335 dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
336 vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
337 if (!vec)
338 return isl_bool_error;
340 isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
341 for (i = 0; i < bmap->n_div; ++i) {
342 isl_seq_inner_product(bmap->div[i] + 1, vec->el,
343 1 + dim + i, &vec->el[1+dim+i]);
344 isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
345 bmap->div[i][0]);
348 contains = isl_basic_map_contains(bmap, vec);
350 isl_vec_free(vec);
351 return contains;
354 isl_bool isl_map_contains_point(__isl_keep isl_map *map,
355 __isl_keep isl_point *point)
357 int i;
358 isl_bool found = isl_bool_false;
360 if (!map || !point)
361 return isl_bool_error;
363 map = isl_map_copy(map);
364 map = isl_map_compute_divs(map);
365 if (!map)
366 return isl_bool_error;
368 for (i = 0; i < map->n; ++i) {
369 found = isl_basic_map_contains_point(map->p[i], point);
370 if (found < 0)
371 goto error;
372 if (found)
373 break;
375 isl_map_free(map);
377 return found;
378 error:
379 isl_map_free(map);
380 return isl_bool_error;
383 isl_bool isl_set_contains_point(__isl_keep isl_set *set,
384 __isl_keep isl_point *point)
386 return isl_map_contains_point(set_to_map(set), point);
389 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
391 isl_basic_set *bset;
392 isl_basic_set *model;
394 if (!pnt)
395 return NULL;
397 model = isl_basic_set_empty(isl_space_copy(pnt->dim));
398 bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
399 bset = isl_basic_set_from_underlying_set(bset, model);
400 isl_point_free(pnt);
402 return bset;
405 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
407 isl_basic_set *bset;
408 bset = isl_basic_set_from_point(pnt);
409 return isl_set_from_basic_set(bset);
412 /* Construct a union set, containing the single element "pnt".
413 * If "pnt" is void, then return an empty union set.
415 __isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
417 if (!pnt)
418 return NULL;
419 if (isl_point_is_void(pnt)) {
420 isl_space *space;
422 space = isl_point_get_space(pnt);
423 isl_point_free(pnt);
424 return isl_union_set_empty(space);
427 return isl_union_set_from_set(isl_set_from_point(pnt));
430 __isl_give isl_basic_set *isl_basic_set_box_from_points(
431 __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
433 isl_basic_set *bset = NULL;
434 unsigned total;
435 int i;
436 int k;
437 isl_int t;
439 isl_int_init(t);
441 if (!pnt1 || !pnt2)
442 goto error;
444 isl_assert(pnt1->dim->ctx,
445 isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
447 if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
448 isl_space *dim = isl_space_copy(pnt1->dim);
449 isl_point_free(pnt1);
450 isl_point_free(pnt2);
451 isl_int_clear(t);
452 return isl_basic_set_empty(dim);
454 if (isl_point_is_void(pnt1)) {
455 isl_point_free(pnt1);
456 isl_int_clear(t);
457 return isl_basic_set_from_point(pnt2);
459 if (isl_point_is_void(pnt2)) {
460 isl_point_free(pnt2);
461 isl_int_clear(t);
462 return isl_basic_set_from_point(pnt1);
465 total = isl_space_dim(pnt1->dim, isl_dim_all);
466 bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
468 for (i = 0; i < total; ++i) {
469 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
470 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
472 k = isl_basic_set_alloc_inequality(bset);
473 if (k < 0)
474 goto error;
475 isl_seq_clr(bset->ineq[k] + 1, total);
476 if (isl_int_is_pos(t)) {
477 isl_int_set_si(bset->ineq[k][1 + i], -1);
478 isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
479 } else {
480 isl_int_set_si(bset->ineq[k][1 + i], 1);
481 isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
483 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
485 k = isl_basic_set_alloc_inequality(bset);
486 if (k < 0)
487 goto error;
488 isl_seq_clr(bset->ineq[k] + 1, total);
489 if (isl_int_is_pos(t)) {
490 isl_int_set_si(bset->ineq[k][1 + i], 1);
491 isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
492 } else {
493 isl_int_set_si(bset->ineq[k][1 + i], -1);
494 isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
496 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
499 bset = isl_basic_set_finalize(bset);
501 isl_point_free(pnt1);
502 isl_point_free(pnt2);
504 isl_int_clear(t);
506 return bset;
507 error:
508 isl_point_free(pnt1);
509 isl_point_free(pnt2);
510 isl_int_clear(t);
511 isl_basic_set_free(bset);
512 return NULL;
515 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
516 __isl_take isl_point *pnt2)
518 isl_basic_set *bset;
519 bset = isl_basic_set_box_from_points(pnt1, pnt2);
520 return isl_set_from_basic_set(bset);
523 /* Print the coordinate at position "pos" of the point "pnt".
525 static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
526 struct isl_print_space_data *data, unsigned pos)
528 isl_point *pnt = data->user;
530 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
531 if (!isl_int_is_one(pnt->vec->el[0])) {
532 p = isl_printer_print_str(p, "/");
533 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
536 return p;
539 __isl_give isl_printer *isl_printer_print_point(
540 __isl_take isl_printer *p, __isl_keep isl_point *pnt)
542 struct isl_print_space_data data = { 0 };
543 int i;
544 unsigned nparam;
546 if (!pnt)
547 return p;
548 if (isl_point_is_void(pnt)) {
549 p = isl_printer_print_str(p, "void");
550 return p;
553 nparam = isl_space_dim(pnt->dim, isl_dim_param);
554 if (nparam > 0) {
555 p = isl_printer_print_str(p, "[");
556 for (i = 0; i < nparam; ++i) {
557 const char *name;
558 if (i)
559 p = isl_printer_print_str(p, ", ");
560 name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
561 if (name) {
562 p = isl_printer_print_str(p, name);
563 p = isl_printer_print_str(p, " = ");
565 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
566 if (!isl_int_is_one(pnt->vec->el[0])) {
567 p = isl_printer_print_str(p, "/");
568 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
571 p = isl_printer_print_str(p, "]");
572 p = isl_printer_print_str(p, " -> ");
574 data.print_dim = &print_coordinate;
575 data.user = pnt;
576 p = isl_printer_print_str(p, "{ ");
577 p = isl_print_space(pnt->dim, p, 0, &data);
578 p = isl_printer_print_str(p, " }");
579 return p;