1 #include <isl_map_private.h>
2 #include <isl_point_private.h>
4 #include <isl/union_set.h>
5 #include <isl_sample.h>
8 #include <isl_space_private.h>
9 #include <isl_local_private.h>
10 #include <isl_val_private.h>
11 #include <isl_vec_private.h>
12 #include <isl_output_private.h>
14 #include <set_to_map.c>
16 isl_ctx
*isl_point_get_ctx(__isl_keep isl_point
*pnt
)
18 return pnt
? isl_space_get_ctx(pnt
->dim
) : NULL
;
21 /* Return the space of "pnt".
23 __isl_keep isl_space
*isl_point_peek_space(__isl_keep isl_point
*pnt
)
25 return pnt
? pnt
->dim
: NULL
;
28 __isl_give isl_space
*isl_point_get_space(__isl_keep isl_point
*pnt
)
30 return isl_space_copy(isl_point_peek_space(pnt
));
33 __isl_give isl_point
*isl_point_alloc(__isl_take isl_space
*space
,
34 __isl_take isl_vec
*vec
)
36 struct isl_point
*pnt
;
41 if (vec
->size
> 1 + isl_space_dim(space
, isl_dim_all
)) {
42 vec
= isl_vec_cow(vec
);
45 vec
->size
= 1 + isl_space_dim(space
, isl_dim_all
);
48 pnt
= isl_alloc_type(space
->ctx
, struct isl_point
);
58 isl_space_free(space
);
63 __isl_give isl_point
*isl_point_zero(__isl_take isl_space
*space
)
69 vec
= isl_vec_alloc(space
->ctx
, 1 + isl_space_dim(space
, isl_dim_all
));
72 isl_int_set_si(vec
->el
[0], 1);
73 isl_seq_clr(vec
->el
+ 1, vec
->size
- 1);
74 return isl_point_alloc(space
, vec
);
76 isl_space_free(space
);
80 __isl_give isl_point
*isl_point_dup(__isl_keep isl_point
*pnt
)
82 struct isl_point
*pnt2
;
86 pnt2
= isl_point_alloc(isl_space_copy(pnt
->dim
), isl_vec_copy(pnt
->vec
));
90 __isl_give isl_point
*isl_point_cow(__isl_take isl_point
*pnt
)
92 struct isl_point
*pnt2
;
99 pnt2
= isl_point_dup(pnt
);
104 __isl_give isl_point
*isl_point_copy(__isl_keep isl_point
*pnt
)
113 __isl_null isl_point
*isl_point_free(__isl_take isl_point
*pnt
)
121 isl_space_free(pnt
->dim
);
122 isl_vec_free(pnt
->vec
);
127 __isl_give isl_point
*isl_point_void(__isl_take isl_space
*space
)
132 return isl_point_alloc(space
, isl_vec_alloc(space
->ctx
, 0));
135 isl_bool
isl_point_is_void(__isl_keep isl_point
*pnt
)
138 return isl_bool_error
;
140 return pnt
->vec
->size
== 0;
143 /* Return the space of "pnt".
144 * This may be either a copy or the space itself
145 * if there is only one reference to "pnt".
146 * This allows the space to be modified inplace
147 * if both the point and its space have only a single reference.
148 * The caller is not allowed to modify "pnt" between this call and
149 * a subsequent call to isl_point_restore_space.
150 * The only exception is that isl_point_free can be called instead.
152 __isl_give isl_space
*isl_point_take_space(__isl_keep isl_point
*pnt
)
159 return isl_point_get_space(pnt
);
165 /* Set the space of "pnt" to "space", where the space of "pnt" may be missing
166 * due to a preceding call to isl_point_take_space.
167 * However, in this case, "pnt" only has a single reference and
168 * then the call to isl_point_cow has no effect.
170 __isl_give isl_point
*isl_point_restore_space(__isl_take isl_point
*pnt
,
171 __isl_take isl_space
*space
)
176 if (pnt
->dim
== space
) {
177 isl_space_free(space
);
181 pnt
= isl_point_cow(pnt
);
184 isl_space_free(pnt
->dim
);
190 isl_space_free(space
);
194 /* Return the coordinate vector of "pnt".
196 __isl_keep isl_vec
*isl_point_peek_vec(__isl_keep isl_point
*pnt
)
198 return pnt
? pnt
->vec
: NULL
;
201 /* Return a copy of the coordinate vector of "pnt".
203 __isl_give isl_vec
*isl_point_get_vec(__isl_keep isl_point
*pnt
)
205 return isl_vec_copy(isl_point_peek_vec(pnt
));
208 /* Return the coordinate vector of "pnt".
209 * This may be either a copy or the coordinate vector itself
210 * if there is only one reference to "pnt".
211 * This allows the coordinate vector to be modified inplace
212 * if both the point and its coordinate vector have only a single reference.
213 * The caller is not allowed to modify "pnt" between this call and
214 * a subsequent call to isl_point_restore_vec.
215 * The only exception is that isl_point_free can be called instead.
217 __isl_give isl_vec
*isl_point_take_vec(__isl_keep isl_point
*pnt
)
224 return isl_point_get_vec(pnt
);
230 /* Set the coordinate vector of "pnt" to "vec",
231 * where the coordinate vector of "pnt" may be missing
232 * due to a preceding call to isl_point_take_vec.
233 * However, in this case, "pnt" only has a single reference and
234 * then the call to isl_point_cow has no effect.
236 __isl_give isl_point
*isl_point_restore_vec(__isl_take isl_point
*pnt
,
237 __isl_take isl_vec
*vec
)
242 if (pnt
->vec
== vec
) {
247 pnt
= isl_point_cow(pnt
);
250 isl_vec_free(pnt
->vec
);
260 /* Return the value of coordinate "pos" of type "type" of "pnt".
262 __isl_give isl_val
*isl_point_get_coordinate_val(__isl_keep isl_point
*pnt
,
263 enum isl_dim_type type
, int pos
)
271 ctx
= isl_point_get_ctx(pnt
);
272 if (isl_point_is_void(pnt
))
273 isl_die(ctx
, isl_error_invalid
,
274 "void point does not have coordinates", return NULL
);
275 if (pos
< 0 || pos
>= isl_space_dim(pnt
->dim
, type
))
276 isl_die(ctx
, isl_error_invalid
,
277 "position out of bounds", return NULL
);
279 if (type
== isl_dim_set
)
280 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
282 v
= isl_val_rat_from_isl_int(ctx
, pnt
->vec
->el
[1 + pos
],
284 return isl_val_normalize(v
);
287 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
289 __isl_give isl_point
*isl_point_set_coordinate_val(__isl_take isl_point
*pnt
,
290 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
294 if (isl_point_is_void(pnt
))
295 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
296 "void point does not have coordinates", goto error
);
297 if (pos
< 0 || pos
>= isl_space_dim(pnt
->dim
, type
))
298 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
299 "position out of bounds", goto error
);
300 if (!isl_val_is_rat(v
))
301 isl_die(isl_point_get_ctx(pnt
), isl_error_invalid
,
302 "expecting rational value", goto error
);
304 if (isl_int_eq(pnt
->vec
->el
[1 + pos
], v
->n
) &&
305 isl_int_eq(pnt
->vec
->el
[0], v
->d
)) {
310 pnt
= isl_point_cow(pnt
);
313 pnt
->vec
= isl_vec_cow(pnt
->vec
);
317 if (isl_int_eq(pnt
->vec
->el
[0], v
->d
)) {
318 isl_int_set(pnt
->vec
->el
[1 + pos
], v
->n
);
319 } else if (isl_int_is_one(v
->d
)) {
320 isl_int_mul(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[0], v
->n
);
322 isl_seq_scale(pnt
->vec
->el
+ 1,
323 pnt
->vec
->el
+ 1, v
->d
, pnt
->vec
->size
- 1);
324 isl_int_mul(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[0], v
->n
);
325 isl_int_mul(pnt
->vec
->el
[0], pnt
->vec
->el
[0], v
->d
);
326 pnt
->vec
= isl_vec_normalize(pnt
->vec
);
339 __isl_give isl_point
*isl_point_add_ui(__isl_take isl_point
*pnt
,
340 enum isl_dim_type type
, int pos
, unsigned val
)
342 if (!pnt
|| isl_point_is_void(pnt
))
345 pnt
= isl_point_cow(pnt
);
348 pnt
->vec
= isl_vec_cow(pnt
->vec
);
352 if (type
== isl_dim_set
)
353 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
355 isl_int_add_ui(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[1 + pos
], val
);
363 __isl_give isl_point
*isl_point_sub_ui(__isl_take isl_point
*pnt
,
364 enum isl_dim_type type
, int pos
, unsigned val
)
366 if (!pnt
|| isl_point_is_void(pnt
))
369 pnt
= isl_point_cow(pnt
);
372 pnt
->vec
= isl_vec_cow(pnt
->vec
);
376 if (type
== isl_dim_set
)
377 pos
+= isl_space_dim(pnt
->dim
, isl_dim_param
);
379 isl_int_sub_ui(pnt
->vec
->el
[1 + pos
], pnt
->vec
->el
[1 + pos
], val
);
387 struct isl_foreach_point
{
388 struct isl_scan_callback callback
;
389 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
);
394 static isl_stat
foreach_point(struct isl_scan_callback
*cb
,
395 __isl_take isl_vec
*sample
)
397 struct isl_foreach_point
*fp
= (struct isl_foreach_point
*)cb
;
400 pnt
= isl_point_alloc(isl_space_copy(fp
->dim
), sample
);
402 return fp
->fn(pnt
, fp
->user
);
405 isl_stat
isl_set_foreach_point(__isl_keep isl_set
*set
,
406 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
408 struct isl_foreach_point fp
= { { &foreach_point
}, fn
, user
};
412 return isl_stat_error
;
414 fp
.dim
= isl_set_get_space(set
);
416 return isl_stat_error
;
418 set
= isl_set_copy(set
);
419 set
= isl_set_cow(set
);
420 set
= isl_set_make_disjoint(set
);
421 set
= isl_set_compute_divs(set
);
425 for (i
= 0; i
< set
->n
; ++i
)
426 if (isl_basic_set_scan(isl_basic_set_copy(set
->p
[i
]),
431 isl_space_free(fp
.dim
);
436 isl_space_free(fp
.dim
);
437 return isl_stat_error
;
440 /* Return 1 if "bmap" contains the point "point".
441 * "bmap" is assumed to have known divs.
442 * The point is first extended with the divs and then passed
443 * to basic_map_contains.
445 isl_bool
isl_basic_map_contains_point(__isl_keep isl_basic_map
*bmap
,
446 __isl_keep isl_point
*point
)
453 return isl_bool_error
;
454 isl_assert(bmap
->ctx
, isl_space_is_equal(bmap
->dim
, point
->dim
),
455 return isl_bool_error
);
456 if (bmap
->n_div
== 0)
457 return isl_basic_map_contains(bmap
, point
->vec
);
459 local
= isl_local_alloc_from_mat(isl_basic_map_get_divs(bmap
));
460 vec
= isl_point_get_vec(point
);
461 vec
= isl_local_extend_point_vec(local
, vec
);
462 isl_local_free(local
);
464 contains
= isl_basic_map_contains(bmap
, vec
);
470 isl_bool
isl_map_contains_point(__isl_keep isl_map
*map
,
471 __isl_keep isl_point
*point
)
474 isl_bool found
= isl_bool_false
;
477 return isl_bool_error
;
479 map
= isl_map_copy(map
);
480 map
= isl_map_compute_divs(map
);
482 return isl_bool_error
;
484 for (i
= 0; i
< map
->n
; ++i
) {
485 found
= isl_basic_map_contains_point(map
->p
[i
], point
);
496 return isl_bool_error
;
499 isl_bool
isl_set_contains_point(__isl_keep isl_set
*set
,
500 __isl_keep isl_point
*point
)
502 return isl_map_contains_point(set_to_map(set
), point
);
505 __isl_give isl_basic_set
*isl_basic_set_from_point(__isl_take isl_point
*pnt
)
508 isl_basic_set
*model
;
513 model
= isl_basic_set_empty(isl_space_copy(pnt
->dim
));
514 bset
= isl_basic_set_from_vec(isl_vec_copy(pnt
->vec
));
515 bset
= isl_basic_set_from_underlying_set(bset
, model
);
521 __isl_give isl_set
*isl_set_from_point(__isl_take isl_point
*pnt
)
524 bset
= isl_basic_set_from_point(pnt
);
525 return isl_set_from_basic_set(bset
);
528 /* Construct a union set, containing the single element "pnt".
529 * If "pnt" is void, then return an empty union set.
531 __isl_give isl_union_set
*isl_union_set_from_point(__isl_take isl_point
*pnt
)
535 if (isl_point_is_void(pnt
)) {
538 space
= isl_point_get_space(pnt
);
540 return isl_union_set_empty(space
);
543 return isl_union_set_from_set(isl_set_from_point(pnt
));
546 __isl_give isl_basic_set
*isl_basic_set_box_from_points(
547 __isl_take isl_point
*pnt1
, __isl_take isl_point
*pnt2
)
549 isl_basic_set
*bset
= NULL
;
560 isl_assert(pnt1
->dim
->ctx
,
561 isl_space_is_equal(pnt1
->dim
, pnt2
->dim
), goto error
);
563 if (isl_point_is_void(pnt1
) && isl_point_is_void(pnt2
)) {
564 isl_space
*dim
= isl_space_copy(pnt1
->dim
);
565 isl_point_free(pnt1
);
566 isl_point_free(pnt2
);
568 return isl_basic_set_empty(dim
);
570 if (isl_point_is_void(pnt1
)) {
571 isl_point_free(pnt1
);
573 return isl_basic_set_from_point(pnt2
);
575 if (isl_point_is_void(pnt2
)) {
576 isl_point_free(pnt2
);
578 return isl_basic_set_from_point(pnt1
);
581 total
= isl_space_dim(pnt1
->dim
, isl_dim_all
);
582 bset
= isl_basic_set_alloc_space(isl_space_copy(pnt1
->dim
), 0, 0, 2 * total
);
584 for (i
= 0; i
< total
; ++i
) {
585 isl_int_mul(t
, pnt1
->vec
->el
[1 + i
], pnt2
->vec
->el
[0]);
586 isl_int_submul(t
, pnt2
->vec
->el
[1 + i
], pnt1
->vec
->el
[0]);
588 k
= isl_basic_set_alloc_inequality(bset
);
591 isl_seq_clr(bset
->ineq
[k
] + 1, total
);
592 if (isl_int_is_pos(t
)) {
593 isl_int_set_si(bset
->ineq
[k
][1 + i
], -1);
594 isl_int_set(bset
->ineq
[k
][0], pnt1
->vec
->el
[1 + i
]);
596 isl_int_set_si(bset
->ineq
[k
][1 + i
], 1);
597 isl_int_neg(bset
->ineq
[k
][0], pnt1
->vec
->el
[1 + i
]);
599 isl_int_fdiv_q(bset
->ineq
[k
][0], bset
->ineq
[k
][0], pnt1
->vec
->el
[0]);
601 k
= isl_basic_set_alloc_inequality(bset
);
604 isl_seq_clr(bset
->ineq
[k
] + 1, total
);
605 if (isl_int_is_pos(t
)) {
606 isl_int_set_si(bset
->ineq
[k
][1 + i
], 1);
607 isl_int_neg(bset
->ineq
[k
][0], pnt2
->vec
->el
[1 + i
]);
609 isl_int_set_si(bset
->ineq
[k
][1 + i
], -1);
610 isl_int_set(bset
->ineq
[k
][0], pnt2
->vec
->el
[1 + i
]);
612 isl_int_fdiv_q(bset
->ineq
[k
][0], bset
->ineq
[k
][0], pnt2
->vec
->el
[0]);
615 bset
= isl_basic_set_finalize(bset
);
617 isl_point_free(pnt1
);
618 isl_point_free(pnt2
);
624 isl_point_free(pnt1
);
625 isl_point_free(pnt2
);
627 isl_basic_set_free(bset
);
631 __isl_give isl_set
*isl_set_box_from_points(__isl_take isl_point
*pnt1
,
632 __isl_take isl_point
*pnt2
)
635 bset
= isl_basic_set_box_from_points(pnt1
, pnt2
);
636 return isl_set_from_basic_set(bset
);
639 /* Print the coordinate at position "pos" of the point "pnt".
641 static __isl_give isl_printer
*print_coordinate(__isl_take isl_printer
*p
,
642 struct isl_print_space_data
*data
, unsigned pos
)
644 isl_point
*pnt
= data
->user
;
646 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[1 + pos
]);
647 if (!isl_int_is_one(pnt
->vec
->el
[0])) {
648 p
= isl_printer_print_str(p
, "/");
649 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[0]);
655 __isl_give isl_printer
*isl_printer_print_point(
656 __isl_take isl_printer
*p
, __isl_keep isl_point
*pnt
)
658 struct isl_print_space_data data
= { 0 };
664 if (isl_point_is_void(pnt
)) {
665 p
= isl_printer_print_str(p
, "void");
669 nparam
= isl_space_dim(pnt
->dim
, isl_dim_param
);
671 p
= isl_printer_print_str(p
, "[");
672 for (i
= 0; i
< nparam
; ++i
) {
675 p
= isl_printer_print_str(p
, ", ");
676 name
= isl_space_get_dim_name(pnt
->dim
, isl_dim_param
, i
);
678 p
= isl_printer_print_str(p
, name
);
679 p
= isl_printer_print_str(p
, " = ");
681 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[1 + i
]);
682 if (!isl_int_is_one(pnt
->vec
->el
[0])) {
683 p
= isl_printer_print_str(p
, "/");
684 p
= isl_printer_print_isl_int(p
, pnt
->vec
->el
[0]);
687 p
= isl_printer_print_str(p
, "]");
688 p
= isl_printer_print_str(p
, " -> ");
690 data
.print_dim
= &print_coordinate
;
692 p
= isl_printer_print_str(p
, "{ ");
693 p
= isl_print_space(pnt
->dim
, p
, 0, &data
);
694 p
= isl_printer_print_str(p
, " }");