isl_stream_next_token: treat "-0" as two tokens '-' and '0'
[isl.git] / isl_point.c
blob53419bee16d0ab988857e97f37a3ec9ad7c95115
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>
9 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
11 return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
14 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
16 return pnt ? isl_space_copy(pnt->dim) : NULL;
19 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
20 __isl_take isl_vec *vec)
22 struct isl_point *pnt;
24 if (!dim || !vec)
25 goto error;
27 if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
28 vec = isl_vec_cow(vec);
29 if (!vec)
30 goto error;
31 vec->size = 1 + isl_space_dim(dim, isl_dim_all);
34 pnt = isl_alloc_type(dim->ctx, struct isl_point);
35 if (!pnt)
36 goto error;
38 pnt->ref = 1;
39 pnt->dim = dim;
40 pnt->vec = vec;
42 return pnt;
43 error:
44 isl_space_free(dim);
45 isl_vec_free(vec);
46 return NULL;
49 __isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
51 isl_vec *vec;
53 if (!dim)
54 return NULL;
55 vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
56 if (!vec)
57 goto error;
58 isl_int_set_si(vec->el[0], 1);
59 isl_seq_clr(vec->el + 1, vec->size - 1);
60 return isl_point_alloc(dim, vec);
61 error:
62 isl_space_free(dim);
63 return NULL;
66 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
68 struct isl_point *pnt2;
70 if (!pnt)
71 return NULL;
72 pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
73 return pnt2;
76 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
78 struct isl_point *pnt2;
79 if (!pnt)
80 return NULL;
82 if (pnt->ref == 1)
83 return pnt;
85 pnt2 = isl_point_dup(pnt);
86 isl_point_free(pnt);
87 return pnt2;
90 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
92 if (!pnt)
93 return NULL;
95 pnt->ref++;
96 return pnt;
99 void isl_point_free(__isl_take isl_point *pnt)
101 if (!pnt)
102 return;
104 if (--pnt->ref > 0)
105 return;
107 isl_space_free(pnt->dim);
108 isl_vec_free(pnt->vec);
109 free(pnt);
112 __isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
114 if (!dim)
115 return NULL;
117 return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
120 int isl_point_is_void(__isl_keep isl_point *pnt)
122 if (!pnt)
123 return -1;
125 return pnt->vec->size == 0;
128 void isl_point_get_coordinate(__isl_keep isl_point *pnt,
129 enum isl_dim_type type, int pos, isl_int *v)
131 if (!pnt || isl_point_is_void(pnt))
132 return;
133 if (type == isl_dim_set)
134 pos += isl_space_dim(pnt->dim, isl_dim_param);
135 isl_int_set(*v, pnt->vec->el[1 + pos]);
138 __isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt,
139 enum isl_dim_type type, int pos, isl_int v)
141 if (!pnt || isl_point_is_void(pnt))
142 return pnt;
144 pnt = isl_point_cow(pnt);
145 if (!pnt)
146 return NULL;
147 pnt->vec = isl_vec_cow(pnt->vec);
148 if (!pnt->vec)
149 goto error;
151 if (type == isl_dim_set)
152 pos += isl_space_dim(pnt->dim, isl_dim_param);
154 isl_int_set(pnt->vec->el[1 + pos], v);
156 return pnt;
157 error:
158 isl_point_free(pnt);
159 return NULL;
162 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
163 enum isl_dim_type type, int pos, unsigned val)
165 if (!pnt || isl_point_is_void(pnt))
166 return pnt;
168 pnt = isl_point_cow(pnt);
169 if (!pnt)
170 return NULL;
171 pnt->vec = isl_vec_cow(pnt->vec);
172 if (!pnt->vec)
173 goto error;
175 if (type == isl_dim_set)
176 pos += isl_space_dim(pnt->dim, isl_dim_param);
178 isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
180 return pnt;
181 error:
182 isl_point_free(pnt);
183 return NULL;
186 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
187 enum isl_dim_type type, int pos, unsigned val)
189 if (!pnt || isl_point_is_void(pnt))
190 return pnt;
192 pnt = isl_point_cow(pnt);
193 if (!pnt)
194 return NULL;
195 pnt->vec = isl_vec_cow(pnt->vec);
196 if (!pnt->vec)
197 goto error;
199 if (type == isl_dim_set)
200 pos += isl_space_dim(pnt->dim, isl_dim_param);
202 isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
204 return pnt;
205 error:
206 isl_point_free(pnt);
207 return NULL;
210 struct isl_foreach_point {
211 struct isl_scan_callback callback;
212 int (*fn)(__isl_take isl_point *pnt, void *user);
213 void *user;
214 isl_space *dim;
217 static int foreach_point(struct isl_scan_callback *cb, __isl_take isl_vec *sample)
219 struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
220 isl_point *pnt;
222 pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
224 return fp->fn(pnt, fp->user);
227 int isl_set_foreach_point(__isl_keep isl_set *set,
228 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
230 struct isl_foreach_point fp = { { &foreach_point }, fn, user };
231 int i;
233 if (!set)
234 return -1;
236 fp.dim = isl_set_get_space(set);
237 if (!fp.dim)
238 return -1;
240 set = isl_set_copy(set);
241 set = isl_set_cow(set);
242 set = isl_set_make_disjoint(set);
243 set = isl_set_compute_divs(set);
244 if (!set)
245 goto error;
247 for (i = 0; i < set->n; ++i)
248 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
249 &fp.callback) < 0)
250 goto error;
252 isl_set_free(set);
253 isl_space_free(fp.dim);
255 return 0;
256 error:
257 isl_set_free(set);
258 isl_space_free(fp.dim);
259 return -1;
262 /* Return 1 if "bmap" contains the point "point".
263 * "bmap" is assumed to have known divs.
264 * The point is first extended with the divs and then passed
265 * to basic_map_contains.
267 int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
268 __isl_keep isl_point *point)
270 int i;
271 struct isl_vec *vec;
272 unsigned dim;
273 int contains;
275 if (!bmap || !point)
276 return -1;
277 isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim), return -1);
278 if (bmap->n_div == 0)
279 return isl_basic_map_contains(bmap, point->vec);
281 dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
282 vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
283 if (!vec)
284 return -1;
286 isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
287 for (i = 0; i < bmap->n_div; ++i) {
288 isl_seq_inner_product(bmap->div[i] + 1, vec->el,
289 1 + dim + i, &vec->el[1+dim+i]);
290 isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
291 bmap->div[i][0]);
294 contains = isl_basic_map_contains(bmap, vec);
296 isl_vec_free(vec);
297 return contains;
300 int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point)
302 int i;
303 int found = 0;
305 if (!map || !point)
306 return -1;
308 map = isl_map_copy(map);
309 map = isl_map_compute_divs(map);
310 if (!map)
311 return -1;
313 for (i = 0; i < map->n; ++i) {
314 found = isl_basic_map_contains_point(map->p[i], point);
315 if (found < 0)
316 goto error;
317 if (found)
318 break;
320 isl_map_free(map);
322 return found;
323 error:
324 isl_map_free(map);
325 return -1;
328 int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point)
330 return isl_map_contains_point((isl_map *)set, point);
333 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
335 isl_basic_set *bset;
336 isl_basic_set *model;
338 model = isl_basic_set_empty(isl_space_copy(pnt->dim));
339 bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
340 bset = isl_basic_set_from_underlying_set(bset, model);
341 isl_point_free(pnt);
343 return bset;
346 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
348 isl_basic_set *bset;
349 bset = isl_basic_set_from_point(pnt);
350 return isl_set_from_basic_set(bset);
353 __isl_give isl_basic_set *isl_basic_set_box_from_points(
354 __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
356 isl_basic_set *bset;
357 unsigned total;
358 int i;
359 int k;
360 isl_int t;
362 isl_int_init(t);
364 if (!pnt1 || !pnt2)
365 goto error;
367 isl_assert(pnt1->dim->ctx,
368 isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
370 if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
371 isl_space *dim = isl_space_copy(pnt1->dim);
372 isl_point_free(pnt1);
373 isl_point_free(pnt2);
374 isl_int_clear(t);
375 return isl_basic_set_empty(dim);
377 if (isl_point_is_void(pnt1)) {
378 isl_point_free(pnt1);
379 isl_int_clear(t);
380 return isl_basic_set_from_point(pnt2);
382 if (isl_point_is_void(pnt2)) {
383 isl_point_free(pnt2);
384 isl_int_clear(t);
385 return isl_basic_set_from_point(pnt1);
388 total = isl_space_dim(pnt1->dim, isl_dim_all);
389 bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
391 for (i = 0; i < total; ++i) {
392 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
393 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
395 k = isl_basic_set_alloc_inequality(bset);
396 if (k < 0)
397 goto error;
398 isl_seq_clr(bset->ineq[k] + 1, total);
399 if (isl_int_is_pos(t)) {
400 isl_int_set_si(bset->ineq[k][1 + i], -1);
401 isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
402 } else {
403 isl_int_set_si(bset->ineq[k][1 + i], 1);
404 isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
406 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
408 k = isl_basic_set_alloc_inequality(bset);
409 if (k < 0)
410 goto error;
411 isl_seq_clr(bset->ineq[k] + 1, total);
412 if (isl_int_is_pos(t)) {
413 isl_int_set_si(bset->ineq[k][1 + i], 1);
414 isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
415 } else {
416 isl_int_set_si(bset->ineq[k][1 + i], -1);
417 isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
419 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
422 bset = isl_basic_set_finalize(bset);
424 isl_point_free(pnt1);
425 isl_point_free(pnt2);
427 isl_int_clear(t);
429 return bset;
430 error:
431 isl_point_free(pnt1);
432 isl_point_free(pnt2);
433 isl_int_clear(t);
434 return NULL;
437 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
438 __isl_take isl_point *pnt2)
440 isl_basic_set *bset;
441 bset = isl_basic_set_box_from_points(pnt1, pnt2);
442 return isl_set_from_basic_set(bset);
445 __isl_give isl_printer *isl_printer_print_point(
446 __isl_take isl_printer *p, __isl_keep isl_point *pnt)
448 int i;
449 unsigned nparam;
450 unsigned dim;
452 if (!pnt)
453 return p;
454 if (isl_point_is_void(pnt)) {
455 p = isl_printer_print_str(p, "void");
456 return p;
459 nparam = isl_space_dim(pnt->dim, isl_dim_param);
460 dim = isl_space_dim(pnt->dim, isl_dim_set);
461 if (nparam > 0) {
462 p = isl_printer_print_str(p, "[");
463 for (i = 0; i < nparam; ++i) {
464 const char *name;
465 if (i)
466 p = isl_printer_print_str(p, ", ");
467 name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
468 if (name) {
469 p = isl_printer_print_str(p, name);
470 p = isl_printer_print_str(p, " = ");
472 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
473 if (!isl_int_is_one(pnt->vec->el[0])) {
474 p = isl_printer_print_str(p, "/");
475 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
478 p = isl_printer_print_str(p, "]");
479 p = isl_printer_print_str(p, " -> ");
481 p = isl_printer_print_str(p, "[");
482 for (i = 0; i < dim; ++i) {
483 if (i)
484 p = isl_printer_print_str(p, ", ");
485 p = isl_printer_print_isl_int(p, pnt->vec->el[1 + nparam + i]);
486 if (!isl_int_is_one(pnt->vec->el[0])) {
487 p = isl_printer_print_str(p, "/");
488 p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
491 p = isl_printer_print_str(p, "]");
492 return p;