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
10isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
11{
12	return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
13}
14
15__isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
16{
17	return pnt ? isl_space_copy(pnt->dim) : NULL;
18}
19
20__isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
21	__isl_take isl_vec *vec)
22{
23	struct isl_point *pnt;
24
25	if (!dim || !vec)
26		goto error;
27
28	if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
29		vec = isl_vec_cow(vec);
30		if (!vec)
31			goto error;
32		vec->size = 1 + isl_space_dim(dim, isl_dim_all);
33	}
34
35	pnt = isl_alloc_type(dim->ctx, struct isl_point);
36	if (!pnt)
37		goto error;
38
39	pnt->ref = 1;
40	pnt->dim = dim;
41	pnt->vec = vec;
42
43	return pnt;
44error:
45	isl_space_free(dim);
46	isl_vec_free(vec);
47	return NULL;
48}
49
50__isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
51{
52	isl_vec *vec;
53
54	if (!dim)
55		return NULL;
56	vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
57	if (!vec)
58		goto error;
59	isl_int_set_si(vec->el[0], 1);
60	isl_seq_clr(vec->el + 1, vec->size - 1);
61	return isl_point_alloc(dim, vec);
62error:
63	isl_space_free(dim);
64	return NULL;
65}
66
67__isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
68{
69	struct isl_point *pnt2;
70
71	if (!pnt)
72		return NULL;
73	pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
74	return pnt2;
75}
76
77__isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
78{
79	struct isl_point *pnt2;
80	if (!pnt)
81		return NULL;
82
83	if (pnt->ref == 1)
84		return pnt;
85
86	pnt2 = isl_point_dup(pnt);
87	isl_point_free(pnt);
88	return pnt2;
89}
90
91__isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
92{
93	if (!pnt)
94		return NULL;
95
96	pnt->ref++;
97	return pnt;
98}
99
100void isl_point_free(__isl_take isl_point *pnt)
101{
102	if (!pnt)
103		return;
104
105	if (--pnt->ref > 0)
106		return;
107
108	isl_space_free(pnt->dim);
109	isl_vec_free(pnt->vec);
110	free(pnt);
111}
112
113__isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
114{
115	if (!dim)
116		return NULL;
117
118	return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
119}
120
121int isl_point_is_void(__isl_keep isl_point *pnt)
122{
123	if (!pnt)
124		return -1;
125
126	return pnt->vec->size == 0;
127}
128
129int isl_point_get_coordinate(__isl_keep isl_point *pnt,
130	enum isl_dim_type type, int pos, isl_int *v)
131{
132	if (!pnt || isl_point_is_void(pnt))
133		return -1;
134
135	if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
136		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
137			"position out of bounds", return -1);
138
139	if (type == isl_dim_set)
140		pos += isl_space_dim(pnt->dim, isl_dim_param);
141	isl_int_set(*v, pnt->vec->el[1 + pos]);
142
143	return 0;
144}
145
146/* Return the value of coordinate "pos" of type "type" of "pnt".
147 */
148__isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
149	enum isl_dim_type type, int pos)
150{
151	isl_ctx *ctx;
152	isl_val *v;
153
154	if (!pnt)
155		return NULL;
156
157	ctx = isl_point_get_ctx(pnt);
158	if (isl_point_is_void(pnt))
159		isl_die(ctx, isl_error_invalid,
160			"void point does not have coordinates", return NULL);
161	if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
162		isl_die(ctx, isl_error_invalid,
163			"position out of bounds", return NULL);
164
165	if (type == isl_dim_set)
166		pos += isl_space_dim(pnt->dim, isl_dim_param);
167
168	v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
169						pnt->vec->el[0]);
170	return isl_val_normalize(v);
171}
172
173__isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt,
174	enum isl_dim_type type, int pos, isl_int v)
175{
176	if (!pnt || isl_point_is_void(pnt))
177		return pnt;
178
179	pnt = isl_point_cow(pnt);
180	if (!pnt)
181		return NULL;
182	pnt->vec = isl_vec_cow(pnt->vec);
183	if (!pnt->vec)
184		goto error;
185
186	if (type == isl_dim_set)
187		pos += isl_space_dim(pnt->dim, isl_dim_param);
188
189	isl_int_set(pnt->vec->el[1 + pos], v);
190
191	return pnt;
192error:
193	isl_point_free(pnt);
194	return NULL;
195}
196
197/* Replace coordinate "pos" of type "type" of "pnt" by "v".
198 */
199__isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
200	enum isl_dim_type type, int pos, __isl_take isl_val *v)
201{
202	if (!pnt || !v)
203		goto error;
204	if (isl_point_is_void(pnt))
205		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
206			"void point does not have coordinates", goto error);
207	if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
208		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
209			"position out of bounds", goto error);
210	if (!isl_val_is_rat(v))
211		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
212			"expecting rational value", goto error);
213
214	if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
215	    isl_int_eq(pnt->vec->el[0], v->d)) {
216		isl_val_free(v);
217		return pnt;
218	}
219
220	pnt = isl_point_cow(pnt);
221	if (!pnt)
222		goto error;
223	pnt->vec = isl_vec_cow(pnt->vec);
224	if (!pnt->vec)
225		goto error;
226
227	if (isl_int_eq(pnt->vec->el[0], v->d)) {
228		isl_int_set(pnt->vec->el[1 + pos], v->n);
229	} else if (isl_int_is_one(v->d)) {
230		isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
231	} else {
232		isl_seq_scale(pnt->vec->el + 1,
233				pnt->vec->el + 1, v->d, pnt->vec->size - 1);
234		isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
235		isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
236		pnt->vec = isl_vec_normalize(pnt->vec);
237		if (!pnt->vec)
238			goto error;
239	}
240
241	isl_val_free(v);
242	return pnt;
243error:
244	isl_val_free(v);
245	isl_point_free(pnt);
246	return NULL;
247}
248
249__isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
250	enum isl_dim_type type, int pos, unsigned val)
251{
252	if (!pnt || isl_point_is_void(pnt))
253		return pnt;
254
255	pnt = isl_point_cow(pnt);
256	if (!pnt)
257		return NULL;
258	pnt->vec = isl_vec_cow(pnt->vec);
259	if (!pnt->vec)
260		goto error;
261
262	if (type == isl_dim_set)
263		pos += isl_space_dim(pnt->dim, isl_dim_param);
264
265	isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
266
267	return pnt;
268error:
269	isl_point_free(pnt);
270	return NULL;
271}
272
273__isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
274	enum isl_dim_type type, int pos, unsigned val)
275{
276	if (!pnt || isl_point_is_void(pnt))
277		return pnt;
278
279	pnt = isl_point_cow(pnt);
280	if (!pnt)
281		return NULL;
282	pnt->vec = isl_vec_cow(pnt->vec);
283	if (!pnt->vec)
284		goto error;
285
286	if (type == isl_dim_set)
287		pos += isl_space_dim(pnt->dim, isl_dim_param);
288
289	isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
290
291	return pnt;
292error:
293	isl_point_free(pnt);
294	return NULL;
295}
296
297struct isl_foreach_point {
298	struct isl_scan_callback callback;
299	int (*fn)(__isl_take isl_point *pnt, void *user);
300	void *user;
301	isl_space *dim;
302};
303
304static int foreach_point(struct isl_scan_callback *cb, __isl_take isl_vec *sample)
305{
306	struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
307	isl_point *pnt;
308
309	pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
310
311	return fp->fn(pnt, fp->user);
312}
313
314int isl_set_foreach_point(__isl_keep isl_set *set,
315	int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
316{
317	struct isl_foreach_point fp = { { &foreach_point }, fn, user };
318	int i;
319
320	if (!set)
321		return -1;
322
323	fp.dim = isl_set_get_space(set);
324	if (!fp.dim)
325		return -1;
326
327	set = isl_set_copy(set);
328	set = isl_set_cow(set);
329	set = isl_set_make_disjoint(set);
330	set = isl_set_compute_divs(set);
331	if (!set)
332		goto error;
333
334	for (i = 0; i < set->n; ++i)
335		if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
336					&fp.callback) < 0)
337			goto error;
338
339	isl_set_free(set);
340	isl_space_free(fp.dim);
341
342	return 0;
343error:
344	isl_set_free(set);
345	isl_space_free(fp.dim);
346	return -1;
347}
348
349/* Return 1 if "bmap" contains the point "point".
350 * "bmap" is assumed to have known divs.
351 * The point is first extended with the divs and then passed
352 * to basic_map_contains.
353 */
354int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
355	__isl_keep isl_point *point)
356{
357	int i;
358	struct isl_vec *vec;
359	unsigned dim;
360	int contains;
361
362	if (!bmap || !point)
363		return -1;
364	isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim), return -1);
365	if (bmap->n_div == 0)
366		return isl_basic_map_contains(bmap, point->vec);
367
368	dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
369	vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
370	if (!vec)
371		return -1;
372
373	isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
374	for (i = 0; i < bmap->n_div; ++i) {
375		isl_seq_inner_product(bmap->div[i] + 1, vec->el,
376					1 + dim + i, &vec->el[1+dim+i]);
377		isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
378				bmap->div[i][0]);
379	}
380
381	contains = isl_basic_map_contains(bmap, vec);
382
383	isl_vec_free(vec);
384	return contains;
385}
386
387int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point)
388{
389	int i;
390	int found = 0;
391
392	if (!map || !point)
393		return -1;
394
395	map = isl_map_copy(map);
396	map = isl_map_compute_divs(map);
397	if (!map)
398		return -1;
399
400	for (i = 0; i < map->n; ++i) {
401		found = isl_basic_map_contains_point(map->p[i], point);
402		if (found < 0)
403			goto error;
404		if (found)
405			break;
406	}
407	isl_map_free(map);
408
409	return found;
410error:
411	isl_map_free(map);
412	return -1;
413}
414
415int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point)
416{
417	return isl_map_contains_point((isl_map *)set, point);
418}
419
420__isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
421{
422	isl_basic_set *bset;
423	isl_basic_set *model;
424
425	if (!pnt)
426		return NULL;
427
428	model = isl_basic_set_empty(isl_space_copy(pnt->dim));
429	bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
430	bset = isl_basic_set_from_underlying_set(bset, model);
431	isl_point_free(pnt);
432
433	return bset;
434}
435
436__isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
437{
438	isl_basic_set *bset;
439	bset = isl_basic_set_from_point(pnt);
440	return isl_set_from_basic_set(bset);
441}
442
443__isl_give isl_basic_set *isl_basic_set_box_from_points(
444	__isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
445{
446	isl_basic_set *bset;
447	unsigned total;
448	int i;
449	int k;
450	isl_int t;
451
452	isl_int_init(t);
453
454	if (!pnt1 || !pnt2)
455		goto error;
456
457	isl_assert(pnt1->dim->ctx,
458			isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
459
460	if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
461		isl_space *dim = isl_space_copy(pnt1->dim);
462		isl_point_free(pnt1);
463		isl_point_free(pnt2);
464		isl_int_clear(t);
465		return isl_basic_set_empty(dim);
466	}
467	if (isl_point_is_void(pnt1)) {
468		isl_point_free(pnt1);
469		isl_int_clear(t);
470		return isl_basic_set_from_point(pnt2);
471	}
472	if (isl_point_is_void(pnt2)) {
473		isl_point_free(pnt2);
474		isl_int_clear(t);
475		return isl_basic_set_from_point(pnt1);
476	}
477
478	total = isl_space_dim(pnt1->dim, isl_dim_all);
479	bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
480
481	for (i = 0; i < total; ++i) {
482		isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
483		isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
484
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_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
492		} else {
493			isl_int_set_si(bset->ineq[k][1 + i], 1);
494			isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
495		}
496		isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
497
498		k = isl_basic_set_alloc_inequality(bset);
499		if (k < 0)
500			goto error;
501		isl_seq_clr(bset->ineq[k] + 1, total);
502		if (isl_int_is_pos(t)) {
503			isl_int_set_si(bset->ineq[k][1 + i], 1);
504			isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
505		} else {
506			isl_int_set_si(bset->ineq[k][1 + i], -1);
507			isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
508		}
509		isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
510	}
511
512	bset = isl_basic_set_finalize(bset);
513
514	isl_point_free(pnt1);
515	isl_point_free(pnt2);
516
517	isl_int_clear(t);
518
519	return bset;
520error:
521	isl_point_free(pnt1);
522	isl_point_free(pnt2);
523	isl_int_clear(t);
524	return NULL;
525}
526
527__isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
528	__isl_take isl_point *pnt2)
529{
530	isl_basic_set *bset;
531	bset = isl_basic_set_box_from_points(pnt1, pnt2);
532	return isl_set_from_basic_set(bset);
533}
534
535__isl_give isl_printer *isl_printer_print_point(
536	__isl_take isl_printer *p, __isl_keep isl_point *pnt)
537{
538	int i;
539	unsigned nparam;
540	unsigned dim;
541
542	if (!pnt)
543		return p;
544	if (isl_point_is_void(pnt)) {
545		p = isl_printer_print_str(p, "void");
546		return p;
547	}
548
549	nparam = isl_space_dim(pnt->dim, isl_dim_param);
550	dim = isl_space_dim(pnt->dim, isl_dim_set);
551	if (nparam > 0) {
552		p = isl_printer_print_str(p, "[");
553		for (i = 0; i < nparam; ++i) {
554			const char *name;
555			if (i)
556				p = isl_printer_print_str(p, ", ");
557			name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
558			if (name) {
559				p = isl_printer_print_str(p, name);
560				p = isl_printer_print_str(p, " = ");
561			}
562			p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
563			if (!isl_int_is_one(pnt->vec->el[0])) {
564				p = isl_printer_print_str(p, "/");
565				p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
566			}
567		}
568		p = isl_printer_print_str(p, "]");
569		p = isl_printer_print_str(p, " -> ");
570	}
571	p = isl_printer_print_str(p, "[");
572	for (i = 0; i < dim; ++i) {
573		if (i)
574			p = isl_printer_print_str(p, ", ");
575		p = isl_printer_print_isl_int(p, pnt->vec->el[1 + nparam + i]);
576		if (!isl_int_is_one(pnt->vec->el[0])) {
577			p = isl_printer_print_str(p, "/");
578			p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
579		}
580	}
581	p = isl_printer_print_str(p, "]");
582	return p;
583}
584