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>
9 #include <isl_vec_private.h>
11 isl_ctx
*isl_point_get_ctx(__isl_keep isl_point
*pnt
)
13 return pnt
? isl_space_get_ctx(pnt
->dim
) : NULL
;
16 __isl_give isl_space
*isl_point_get_space(__isl_keep isl_point
*pnt
)
18 return pnt
? isl_space_copy(pnt
->dim
) : NULL
;
21 __isl_give isl_point
*isl_point_alloc(__isl_take isl_space
*dim
,
22 __isl_take isl_vec
*vec
)
24 struct isl_point
*pnt
;
29 if (vec
->size
> 1 + isl_space_dim(dim
, isl_dim_all
)) {
30 vec
= isl_vec_cow(vec
);
33 vec
->size
= 1 + isl_space_dim(dim
, isl_dim_all
);
36 pnt
= isl_alloc_type(dim
->ctx
, struct isl_point
);
51 __isl_give isl_point
*isl_point_zero(__isl_take isl_space
*dim
)
57 vec
= isl_vec_alloc(dim
->ctx
, 1 + isl_space_dim(dim
, isl_dim_all
));
60 isl_int_set_si(vec
->el
[0], 1);
61 isl_seq_clr(vec
->el
+ 1, vec
->size
- 1);
62 return isl_point_alloc(dim
, vec
);
68 __isl_give isl_point
*isl_point_dup(__isl_keep isl_point
*pnt
)
70 struct isl_point
*pnt2
;
74 pnt2
= isl_point_alloc(isl_space_copy(pnt
->dim
), isl_vec_copy(pnt
->vec
));
78 __isl_give isl_point
*isl_point_cow(__isl_take isl_point
*pnt
)
80 struct isl_point
*pnt2
;
87 pnt2
= isl_point_dup(pnt
);
92 __isl_give isl_point
*isl_point_copy(__isl_keep isl_point
*pnt
)
101 void isl_point_free(__isl_take isl_point
*pnt
)
109 isl_space_free(pnt
->dim
);
110 isl_vec_free(pnt
->vec
);
114 __isl_give isl_point
*isl_point_void(__isl_take isl_space
*dim
)
119 return isl_point_alloc(dim
, isl_vec_alloc(dim
->ctx
, 0));
122 int isl_point_is_void(__isl_keep isl_point
*pnt
)
127 return pnt
->vec
->size
== 0;
130 int isl_point_get_coordinate(__isl_keep isl_point
*pnt
,
131 enum isl_dim_type type
, int pos
, isl_int
*v
)
133 if (!pnt
|| isl_point_is_void(pnt
))
136 if (pos
< 0 || pos
>= isl_space_dim(pnt
->dim
, type
))
137 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
138 "position out of bounds", return -1);
140 if (type
== isl_dim_set
)
141 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
142 isl_int_set(*v
, pnt
->vec
->el
[1 + pos
]);
147 /* Return the value of coordinate "pos" of type "type" of "pnt".
149 __isl_give isl_val
*isl_point_get_coordinate_val(__isl_keep isl_point
*pnt
,
150 enum isl_dim_type type
, int pos
)
158 ctx
= isl_point_get_ctx(pnt
);
159 if (isl_point_is_void(pnt
))
160 isl_die(ctx
, isl_error_invalid
,
161 "void point does not have coordinates", return NULL
);
162 if (pos
< 0 || pos
>= isl_space_dim(pnt
->dim
, type
))
163 isl_die(ctx
, isl_error_invalid
,
164 "position out of bounds", return NULL
);
166 if (type
== isl_dim_set
)
167 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
169 v
= isl_val_rat_from_isl_int(ctx
, pnt
->vec
->el
[1 + pos
],
171 return isl_val_normalize(v
);
174 __isl_give isl_point
*isl_point_set_coordinate(__isl_take isl_point
*pnt
,
175 enum isl_dim_type type
, int pos
, isl_int v
)
177 if (!pnt
|| isl_point_is_void(pnt
))
180 pnt
= isl_point_cow(pnt
);
183 pnt
->vec
= isl_vec_cow(pnt
->vec
);
187 if (type
== isl_dim_set
)
188 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
190 isl_int_set(pnt
->vec
->el
[1 + pos
], v
);
198 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
200 __isl_give isl_point
*isl_point_set_coordinate_val(__isl_take isl_point
*pnt
,
201 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
205 if (isl_point_is_void(pnt
))
206 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
207 "void point does not have coordinates", goto error
);
208 if (pos
< 0 || pos
>= isl_space_dim(pnt
->dim
, type
))
209 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
210 "position out of bounds", goto error
);
211 if (!isl_val_is_rat(v
))
212 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
213 "expecting rational value", goto error
);
215 if (isl_int_eq(pnt
->vec
->el
[1 + pos
], v
->n
) &&
216 isl_int_eq(pnt
->vec
->el
[0], v
->d
)) {
221 pnt
= isl_point_cow(pnt
);
224 pnt
->vec
= isl_vec_cow(pnt
->vec
);
228 if (isl_int_eq(pnt
->vec
->el
[0], v
->d
)) {
229 isl_int_set(pnt
->vec
->el
[1 + pos
], v
->n
);
230 } else if (isl_int_is_one(v
->d
)) {
231 isl_int_mul(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[0], v
->n
);
233 isl_seq_scale(pnt
->vec
->el
+ 1,
234 pnt
->vec
->el
+ 1, v
->d
, pnt
->vec
->size
- 1);
235 isl_int_mul(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[0], v
->n
);
236 isl_int_mul(pnt
->vec
->el
[0], pnt
->vec
->el
[0], v
->d
);
237 pnt
->vec
= isl_vec_normalize(pnt
->vec
);
250 __isl_give isl_point
*isl_point_add_ui(__isl_take isl_point
*pnt
,
251 enum isl_dim_type type
, int pos
, unsigned val
)
253 if (!pnt
|| isl_point_is_void(pnt
))
256 pnt
= isl_point_cow(pnt
);
259 pnt
->vec
= isl_vec_cow(pnt
->vec
);
263 if (type
== isl_dim_set
)
264 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
266 isl_int_add_ui(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[1 + pos
], val
);
274 __isl_give isl_point
*isl_point_sub_ui(__isl_take isl_point
*pnt
,
275 enum isl_dim_type type
, int pos
, unsigned val
)
277 if (!pnt
|| isl_point_is_void(pnt
))
280 pnt
= isl_point_cow(pnt
);
283 pnt
->vec
= isl_vec_cow(pnt
->vec
);
287 if (type
== isl_dim_set
)
288 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
290 isl_int_sub_ui(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[1 + pos
], val
);
298 struct isl_foreach_point
{
299 struct isl_scan_callback callback
;
300 int (*fn
)(__isl_take isl_point
*pnt
, void *user
);
305 static int foreach_point(struct isl_scan_callback
*cb
, __isl_take isl_vec
*sample
)
307 struct isl_foreach_point
*fp
= (struct isl_foreach_point
*)cb
;
310 pnt
= isl_point_alloc(isl_space_copy(fp
->dim
), sample
);
312 return fp
->fn(pnt
, fp
->user
);
315 int isl_set_foreach_point(__isl_keep isl_set
*set
,
316 int (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
318 struct isl_foreach_point fp
= { { &foreach_point
}, fn
, user
};
324 fp
.dim
= isl_set_get_space(set
);
328 set
= isl_set_copy(set
);
329 set
= isl_set_cow(set
);
330 set
= isl_set_make_disjoint(set
);
331 set
= isl_set_compute_divs(set
);
335 for (i
= 0; i
< set
->n
; ++i
)
336 if (isl_basic_set_scan(isl_basic_set_copy(set
->p
[i
]),
341 isl_space_free(fp
.dim
);
346 isl_space_free(fp
.dim
);
350 /* Return 1 if "bmap" contains the point "point".
351 * "bmap" is assumed to have known divs.
352 * The point is first extended with the divs and then passed
353 * to basic_map_contains.
355 int isl_basic_map_contains_point(__isl_keep isl_basic_map
*bmap
,
356 __isl_keep isl_point
*point
)
365 isl_assert(bmap
->ctx
, isl_space_is_equal(bmap
->dim
, point
->dim
), return -1);
366 if (bmap
->n_div
== 0)
367 return isl_basic_map_contains(bmap
, point
->vec
);
369 dim
= isl_basic_map_total_dim(bmap
) - bmap
->n_div
;
370 vec
= isl_vec_alloc(bmap
->ctx
, 1 + dim
+ bmap
->n_div
);
374 isl_seq_cpy(vec
->el
, point
->vec
->el
, point
->vec
->size
);
375 for (i
= 0; i
< bmap
->n_div
; ++i
) {
376 isl_seq_inner_product(bmap
->div
[i
] + 1, vec
->el
,
377 1 + dim
+ i
, &vec
->el
[1+dim
+i
]);
378 isl_int_fdiv_q(vec
->el
[1+dim
+i
], vec
->el
[1+dim
+i
],
382 contains
= isl_basic_map_contains(bmap
, vec
);
388 int isl_map_contains_point(__isl_keep isl_map
*map
, __isl_keep isl_point
*point
)
396 map
= isl_map_copy(map
);
397 map
= isl_map_compute_divs(map
);
401 for (i
= 0; i
< map
->n
; ++i
) {
402 found
= isl_basic_map_contains_point(map
->p
[i
], point
);
416 int isl_set_contains_point(__isl_keep isl_set
*set
, __isl_keep isl_point
*point
)
418 return isl_map_contains_point((isl_map
*)set
, point
);
421 __isl_give isl_basic_set
*isl_basic_set_from_point(__isl_take isl_point
*pnt
)
424 isl_basic_set
*model
;
426 model
= isl_basic_set_empty(isl_space_copy(pnt
->dim
));
427 bset
= isl_basic_set_from_vec(isl_vec_copy(pnt
->vec
));
428 bset
= isl_basic_set_from_underlying_set(bset
, model
);
434 __isl_give isl_set
*isl_set_from_point(__isl_take isl_point
*pnt
)
437 bset
= isl_basic_set_from_point(pnt
);
438 return isl_set_from_basic_set(bset
);
441 __isl_give isl_basic_set
*isl_basic_set_box_from_points(
442 __isl_take isl_point
*pnt1
, __isl_take isl_point
*pnt2
)
455 isl_assert(pnt1
->dim
->ctx
,
456 isl_space_is_equal(pnt1
->dim
, pnt2
->dim
), goto error
);
458 if (isl_point_is_void(pnt1
) && isl_point_is_void(pnt2
)) {
459 isl_space
*dim
= isl_space_copy(pnt1
->dim
);
460 isl_point_free(pnt1
);
461 isl_point_free(pnt2
);
463 return isl_basic_set_empty(dim
);
465 if (isl_point_is_void(pnt1
)) {
466 isl_point_free(pnt1
);
468 return isl_basic_set_from_point(pnt2
);
470 if (isl_point_is_void(pnt2
)) {
471 isl_point_free(pnt2
);
473 return isl_basic_set_from_point(pnt1
);
476 total
= isl_space_dim(pnt1
->dim
, isl_dim_all
);
477 bset
= isl_basic_set_alloc_space(isl_space_copy(pnt1
->dim
), 0, 0, 2 * total
);
479 for (i
= 0; i
< total
; ++i
) {
480 isl_int_mul(t
, pnt1
->vec
->el
[1 + i
], pnt2
->vec
->el
[0]);
481 isl_int_submul(t
, pnt2
->vec
->el
[1 + i
], pnt1
->vec
->el
[0]);
483 k
= isl_basic_set_alloc_inequality(bset
);
486 isl_seq_clr(bset
->ineq
[k
] + 1, total
);
487 if (isl_int_is_pos(t
)) {
488 isl_int_set_si(bset
->ineq
[k
][1 + i
], -1);
489 isl_int_set(bset
->ineq
[k
][0], pnt1
->vec
->el
[1 + i
]);
491 isl_int_set_si(bset
->ineq
[k
][1 + i
], 1);
492 isl_int_neg(bset
->ineq
[k
][0], pnt1
->vec
->el
[1 + i
]);
494 isl_int_fdiv_q(bset
->ineq
[k
][0], bset
->ineq
[k
][0], pnt1
->vec
->el
[0]);
496 k
= isl_basic_set_alloc_inequality(bset
);
499 isl_seq_clr(bset
->ineq
[k
] + 1, total
);
500 if (isl_int_is_pos(t
)) {
501 isl_int_set_si(bset
->ineq
[k
][1 + i
], 1);
502 isl_int_neg(bset
->ineq
[k
][0], pnt2
->vec
->el
[1 + i
]);
504 isl_int_set_si(bset
->ineq
[k
][1 + i
], -1);
505 isl_int_set(bset
->ineq
[k
][0], pnt2
->vec
->el
[1 + i
]);
507 isl_int_fdiv_q(bset
->ineq
[k
][0], bset
->ineq
[k
][0], pnt2
->vec
->el
[0]);
510 bset
= isl_basic_set_finalize(bset
);
512 isl_point_free(pnt1
);
513 isl_point_free(pnt2
);
519 isl_point_free(pnt1
);
520 isl_point_free(pnt2
);
525 __isl_give isl_set
*isl_set_box_from_points(__isl_take isl_point
*pnt1
,
526 __isl_take isl_point
*pnt2
)
529 bset
= isl_basic_set_box_from_points(pnt1
, pnt2
);
530 return isl_set_from_basic_set(bset
);
533 __isl_give isl_printer
*isl_printer_print_point(
534 __isl_take isl_printer
*p
, __isl_keep isl_point
*pnt
)
542 if (isl_point_is_void(pnt
)) {
543 p
= isl_printer_print_str(p
, "void");
547 nparam
= isl_space_dim(pnt
->dim
, isl_dim_param
);
548 dim
= isl_space_dim(pnt
->dim
, isl_dim_set
);
550 p
= isl_printer_print_str(p
, "[");
551 for (i
= 0; i
< nparam
; ++i
) {
554 p
= isl_printer_print_str(p
, ", ");
555 name
= isl_space_get_dim_name(pnt
->dim
, isl_dim_param
, i
);
557 p
= isl_printer_print_str(p
, name
);
558 p
= isl_printer_print_str(p
, " = ");
560 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[1 + i
]);
561 if (!isl_int_is_one(pnt
->vec
->el
[0])) {
562 p
= isl_printer_print_str(p
, "/");
563 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[0]);
566 p
= isl_printer_print_str(p
, "]");
567 p
= isl_printer_print_str(p
, " -> ");
569 p
= isl_printer_print_str(p
, "[");
570 for (i
= 0; i
< dim
; ++i
) {
572 p
= isl_printer_print_str(p
, ", ");
573 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[1 + nparam
+ i
]);
574 if (!isl_int_is_one(pnt
->vec
->el
[0])) {
575 p
= isl_printer_print_str(p
, "/");
576 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[0]);
579 p
= isl_printer_print_str(p
, "]");