1	/*
2	* Copyright 2010 INRIA Saclay
3	*
4	* Use of this software is governed by the MIT license
5	*
6	* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7	* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8	* 91893 Orsay, France
9	*/
10
11	#include <isl_map_private.h>
12	#include <isl_union_map_private.h>
13	#include <isl_polynomial_private.h>
14	#include <isl_point_private.h>
15	#include <isl_space_private.h>
16	#include <isl_lp_private.h>
17	#include <isl_seq.h>
18	#include <isl_mat_private.h>
19	#include <isl_val_private.h>
20	#include <isl_vec_private.h>
21	#include <isl_config.h>
22
23	#undef EL_BASE
24	#define EL_BASE pw_qpolynomial_fold
25
26	#include <isl_list_templ.c>
27
28	enum isl_fold isl_fold_type_negate(enum isl_fold type)
29	{
30	switch (type) {
31	case isl_fold_error:
32	return isl_fold_error;
33	case isl_fold_min:
34	return isl_fold_max;
35	case isl_fold_max:
36	return isl_fold_min;
37	case isl_fold_list:
38	return isl_fold_list;
39	}
40
41	isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort());
42	}
43
44	/* Construct a new reduction with the given type, domain space and
45	* list of polynomials.
46	*/
47	static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
48	enum isl_fold type, __isl_take isl_space *space,
49	__isl_take isl_qpolynomial_list *list)
50	{
51	isl_ctx *ctx;
52	isl_qpolynomial_fold *fold;
53
54	if (type < 0 || !space || !list)
55	goto error;
56
57	ctx = isl_space_get_ctx(space);
58	fold = isl_calloc_type(ctx, struct isl_qpolynomial_fold);
59	if (!fold)
60	goto error;
61
62	fold->ref = 1;
63	fold->type = type;
64	fold->dim = space;
65	fold->list = list;
66
67	return fold;
68	error:
69	isl_space_free(space);
70	isl_qpolynomial_list_free(list);
71	return NULL;
72	}
73
74	isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
75	{
76	return fold ? fold->dim->ctx : NULL;
77	}
78
79	/* Return the domain space of "fold".
80	*/
81	static __isl_keep isl_space *isl_qpolynomial_fold_peek_domain_space(
82	__isl_keep isl_qpolynomial_fold *fold)
83	{
84	return fold ? fold->dim : NULL;
85	}
86
87	__isl_give isl_space *isl_qpolynomial_fold_get_domain_space(
88	__isl_keep isl_qpolynomial_fold *fold)
89	{
90	return isl_space_copy(space: isl_qpolynomial_fold_peek_domain_space(fold));
91	}
92
93	/* Return the space of the domain of "fold".
94	* This may be either a copy or the space itself
95	* if there is only one reference to "fold".
96	* This allows the space to be modified inplace
97	* if both the expression and its space have only a single reference.
98	* The caller is not allowed to modify "fold" between this call and
99	* a subsequent call to isl_qpolynomial_fold_restore_domain_space.
100	* The only exception is that isl_qpolynomial_fold_free can be called instead.
101	*/
102	static __isl_give isl_space *isl_qpolynomial_fold_take_domain_space(
103	__isl_keep isl_qpolynomial_fold *fold)
104	{
105	isl_space *space;
106
107	if (!fold)
108	return NULL;
109	if (fold->ref != 1)
110	return isl_qpolynomial_fold_get_domain_space(fold);
111	space = fold->dim;
112	fold->dim = NULL;
113	return space;
114	}
115
116	/* Set the space of the domain of "fold" to "space",
117	* where the space of "fold" may be missing
118	* due to a preceding call to isl_qpolynomial_fold_take_domain_space.
119	* However, in this case, "fold" only has a single reference and
120	* then the call to isl_qpolynomial_fold_cow has no effect.
121	*/
122	static
123	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_restore_domain_space(
124	__isl_keep isl_qpolynomial_fold *fold, __isl_take isl_space *space)
125	{
126	if (!fold || !space)
127	goto error;
128
129	if (fold->dim == space) {
130	isl_space_free(space);
131	return fold;
132	}
133
134	fold = isl_qpolynomial_fold_cow(fold);
135	if (!fold)
136	goto error;
137	isl_space_free(space: fold->dim);
138	fold->dim = space;
139
140	return fold;
141	error:
142	isl_qpolynomial_fold_free(fold);
143	isl_space_free(space);
144	return NULL;
145	}
146
147	__isl_give isl_space *isl_qpolynomial_fold_get_space(
148	__isl_keep isl_qpolynomial_fold *fold)
149	{
150	isl_space *space;
151	if (!fold)
152	return NULL;
153	space = isl_space_copy(space: fold->dim);
154	space = isl_space_from_domain(space);
155	space = isl_space_add_dims(space, type: isl_dim_out, n: 1);
156	return space;
157	}
158
159	/* Return the list of polynomials in the reduction "fold".
160	*/
161	__isl_keep isl_qpolynomial_list *isl_qpolynomial_fold_peek_list(
162	__isl_keep isl_qpolynomial_fold *fold)
163	{
164	return fold ? fold->list : NULL;
165	}
166
167	/* Return a copy of the list of polynomials in the reduction "fold".
168	*/
169	static __isl_give isl_qpolynomial_list *isl_qpolynomial_fold_get_list(
170	__isl_keep isl_qpolynomial_fold *fold)
171	{
172	return isl_qpolynomial_list_copy(list: isl_qpolynomial_fold_peek_list(fold));
173	}
174
175	/* Return the list of polynomials of "fold".
176	* This may be either a copy or the list itself
177	* if there is only one reference to "fold".
178	* This allows the list to be modified inplace
179	* if both the expression and its list have only a single reference.
180	* The caller is not allowed to modify "fold" between this call and
181	* a subsequent call to isl_qpolynomial_fold_restore_list.
182	* The only exception is that isl_qpolynomial_fold_free can be called instead.
183	*/
184	static __isl_give isl_qpolynomial_list *isl_qpolynomial_fold_take_list(
185	__isl_keep isl_qpolynomial_fold *fold)
186	{
187	isl_qpolynomial_list *list;
188
189	if (!fold)
190	return NULL;
191	if (fold->ref != 1)
192	return isl_qpolynomial_fold_get_list(fold);
193	list = fold->list;
194	fold->list = NULL;
195	return list;
196	}
197
198	/* Set the space of the list of polynomials of "fold" to "space",
199	* where the list of polynomials of "fold" may be missing
200	* due to a preceding call to isl_qpolynomial_fold_take_list.
201	* However, in this case, "fold" only has a single reference and
202	* then the call to isl_qpolynomial_fold_cow has no effect.
203	*/
204	static __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_restore_list(
205	__isl_keep isl_qpolynomial_fold *fold,
206	__isl_take isl_qpolynomial_list *list)
207	{
208	if (!fold || !list)
209	goto error;
210
211	if (fold->list == list) {
212	isl_qpolynomial_list_free(list);
213	return fold;
214	}
215
216	fold = isl_qpolynomial_fold_cow(fold);
217	if (!fold)
218	goto error;
219	isl_qpolynomial_list_free(list: fold->list);
220	fold->list = list;
221
222	return fold;
223	error:
224	isl_qpolynomial_fold_free(fold);
225	isl_qpolynomial_list_free(list);
226	return NULL;
227	}
228
229	/* isl_qpolynomial_list_map callback that calls
230	* isl_qpolynomial_reset_domain_space on "qp".
231	*/
232	static __isl_give isl_qpolynomial *reset_domain_space(
233	__isl_take isl_qpolynomial *qp, void *user)
234	{
235	isl_space *space = user;
236
237	return isl_qpolynomial_reset_domain_space(qp, space: isl_space_copy(space));
238	}
239
240	/* Replace the domain space of "fold" by "space".
241	*
242	* Replace the domain space itself and that of all polynomials
243	* in the list.
244	*/
245	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space(
246	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space)
247	{
248	isl_qpolynomial_list *list;
249
250	list = isl_qpolynomial_fold_take_list(fold);
251	list = isl_qpolynomial_list_map(list, fn: &reset_domain_space, user: space);
252	fold = isl_qpolynomial_fold_restore_list(fold, list);
253
254	isl_space_free(space: isl_qpolynomial_fold_take_domain_space(fold));
255	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
256
257	return fold;
258	}
259
260	/* Reset the space of "fold". This function is called from isl_pw_templ.c
261	* and doesn't know if the space of an element object is represented
262	* directly or through its domain. It therefore passes along both.
263	*/
264	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain(
265	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space,
266	__isl_take isl_space *domain)
267	{
268	isl_space_free(space);
269	return isl_qpolynomial_fold_reset_domain_space(fold, space: domain);
270	}
271
272	/* Internal data structure for isl_qpolynomial_fold_*_dims
273	* representing their arguments.
274	*/
275	struct isl_fold_dims_data {
276	enum isl_dim_type type;
277	unsigned first;
278	unsigned n;
279	};
280
281	/* isl_qpolynomial_list_every callback that checks whether "qp"
282	* does not involve any dimensions in the given range.
283	*/
284	static isl_bool not_involved(__isl_keep isl_qpolynomial *qp, void *user)
285	{
286	struct isl_fold_dims_data *data = user;
287	isl_bool involves;
288
289	involves = isl_qpolynomial_involves_dims(qp, type: data->type,
290	first: data->first, n: data->n);
291	return isl_bool_not(b: involves);
292	}
293
294	/* Does "fold" involve any dimensions in the given range.
295	*
296	* It involves any of those dimensions if it is not the case
297	* that every polynomial in the reduction does not involve
298	* any of the dimensions.
299	*/
300	static isl_bool isl_qpolynomial_fold_involves_dims(
301	__isl_keep isl_qpolynomial_fold *fold,
302	enum isl_dim_type type, unsigned first, unsigned n)
303	{
304	struct isl_fold_dims_data data = { type, first, n };
305	isl_qpolynomial_list *list;
306	isl_bool not;
307
308	if (!fold)
309	return isl_bool_error;
310	if (n == 0)
311	return isl_bool_false;
312
313	list = isl_qpolynomial_fold_peek_list(fold);
314	not = isl_qpolynomial_list_every(list, test: &not_involved, user: &data);
315	return isl_bool_not(b: not);
316	}
317
318	/* Internal data structure for isl_qpolynomial_fold_set_dim_name
319	* representing its arguments.
320	*/
321	struct isl_fold_set_dim_name_data {
322	enum isl_dim_type type;
323	unsigned pos;
324	const char *s;
325	};
326
327	/* isl_qpolynomial_list_map callback for calling
328	* isl_qpolynomial_set_dim_name on "qp".
329	*/
330	static __isl_give isl_qpolynomial *set_dim_name(__isl_take isl_qpolynomial *qp,
331	void *user)
332	{
333	struct isl_fold_set_dim_name_data *data = user;
334
335	qp = isl_qpolynomial_set_dim_name(qp, type: data->type, pos: data->pos, s: data->s);
336	return qp;
337	}
338
339	/* Given a dimension type for an isl_qpolynomial_fold,
340	* return the corresponding type for the domain.
341	*/
342	static enum isl_dim_type domain_type(enum isl_dim_type type)
343	{
344	if (type == isl_dim_in)
345	return isl_dim_set;
346	return type;
347	}
348
349	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
350	__isl_take isl_qpolynomial_fold *fold,
351	enum isl_dim_type type, unsigned pos, const char *s)
352	{
353	struct isl_fold_set_dim_name_data data = { type, pos, s };
354	enum isl_dim_type set_type;
355	isl_space *space;
356	isl_qpolynomial_list *list;
357
358	list = isl_qpolynomial_fold_take_list(fold);
359	list = isl_qpolynomial_list_map(list, fn: &set_dim_name, user: &data);
360	fold = isl_qpolynomial_fold_restore_list(fold, list);
361
362	set_type = domain_type(type);
363	space = isl_qpolynomial_fold_take_domain_space(fold);
364	space = isl_space_set_dim_name(space, type: set_type, pos, name: s);
365	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
366
367	return fold;
368	}
369
370	/* isl_qpolynomial_list_map callback for calling
371	* isl_qpolynomial_drop_dims on "qp".
372	*/
373	static __isl_give isl_qpolynomial *drop_dims(__isl_take isl_qpolynomial *qp,
374	void *user)
375	{
376	struct isl_fold_dims_data *data = user;
377
378	qp = isl_qpolynomial_drop_dims(qp, type: data->type, first: data->first, n: data->n);
379	return qp;
380	}
381
382	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
383	__isl_take isl_qpolynomial_fold *fold,
384	enum isl_dim_type type, unsigned first, unsigned n)
385	{
386	struct isl_fold_dims_data data = { type, first, n };
387	enum isl_dim_type set_type;
388	isl_space *space;
389	isl_qpolynomial_list *list;
390
391	if (!fold)
392	return NULL;
393	if (n == 0)
394	return fold;
395
396	set_type = domain_type(type);
397
398	list = isl_qpolynomial_fold_take_list(fold);
399	list = isl_qpolynomial_list_map(list, fn: &drop_dims, user: &data);
400	fold = isl_qpolynomial_fold_restore_list(fold, list);
401
402	space = isl_qpolynomial_fold_take_domain_space(fold);
403	space = isl_space_drop_dims(space, type: set_type, first, num: n);
404	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
405
406	return fold;
407	}
408
409	/* isl_qpolynomial_list_map callback for calling
410	* isl_qpolynomial_insert_dims on "qp".
411	*/
412	static __isl_give isl_qpolynomial *insert_dims(__isl_take isl_qpolynomial *qp,
413	void *user)
414	{
415	struct isl_fold_dims_data *data = user;
416
417	qp = isl_qpolynomial_insert_dims(qp, type: data->type, first: data->first, n: data->n);
418	return qp;
419	}
420
421	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
422	__isl_take isl_qpolynomial_fold *fold,
423	enum isl_dim_type type, unsigned first, unsigned n)
424	{
425	struct isl_fold_dims_data data = { type, first, n };
426	enum isl_dim_type set_type;
427	isl_space *space;
428	isl_qpolynomial_list *list;
429
430	if (!fold)
431	return NULL;
432	if (n == 0 && !isl_space_is_named_or_nested(space: fold->dim, type))
433	return fold;
434
435	list = isl_qpolynomial_fold_take_list(fold);
436	list = isl_qpolynomial_list_map(list, fn: &insert_dims, user: &data);
437	fold = isl_qpolynomial_fold_restore_list(fold, list);
438
439	set_type = domain_type(type);
440	space = isl_qpolynomial_fold_take_domain_space(fold);
441	space = isl_space_insert_dims(space, type: set_type, pos: first, n);
442	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
443
444	return fold;
445	}
446
447	/* Determine the sign of the constant quasipolynomial "qp".
448	*
449	* Return
450	* -1 if qp <= 0
451	* 1 if qp >= 0
452	* 0 if unknown
453	*
454	* For qp == 0, we can return either -1 or 1. In practice, we return 1.
455	* For qp == NaN, the sign is undefined, so we return 0.
456	*/
457	static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
458	{
459	isl_poly_cst *cst;
460
461	if (isl_qpolynomial_is_nan(qp))
462	return 0;
463
464	cst = isl_poly_as_cst(poly: qp->poly);
465	if (!cst)
466	return 0;
467
468	return isl_int_sgn(cst->n) < 0 ? -1 : 1;
469	}
470
471	static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
472	__isl_keep isl_qpolynomial *qp)
473	{
474	enum isl_lp_result res;
475	isl_vec *aff;
476	isl_int opt;
477	int sgn = 0;
478
479	aff = isl_qpolynomial_extract_affine(qp);
480	if (!aff)
481	return 0;
482
483	isl_int_init(opt);
484
485	res = isl_set_solve_lp(set, max: 0, f: aff->el + 1, denom: aff->el[0],
486	opt: &opt, NULL, NULL);
487	if (res == isl_lp_error)
488	goto done;
489	if (res == isl_lp_empty ||
490	(res == isl_lp_ok && !isl_int_is_neg(opt))) {
491	sgn = 1;
492	goto done;
493	}
494
495	res = isl_set_solve_lp(set, max: 1, f: aff->el + 1, denom: aff->el[0],
496	opt: &opt, NULL, NULL);
497	if (res == isl_lp_ok && !isl_int_is_pos(opt))
498	sgn = -1;
499
500	done:
501	isl_int_clear(opt);
502	isl_vec_free(vec: aff);
503	return sgn;
504	}
505
506	/* Determine, if possible, the sign of the quasipolynomial "qp" on
507	* the domain "set".
508	*
509	* If qp is a constant, then the problem is trivial.
510	* If qp is linear, then we check if the minimum of the corresponding
511	* affine constraint is non-negative or if the maximum is non-positive.
512	*
513	* Otherwise, we check if the outermost variable "v" has a lower bound "l"
514	* in "set". If so, we write qp(v,v') as
515	*
516	* q(v,v') * (v - l) + r(v')
517	*
518	* if q(v,v') and r(v') have the same known sign, then the original
519	* quasipolynomial has the same sign as well.
520	*
521	* Return
522	* -1 if qp <= 0
523	* 1 if qp >= 0
524	* 0 if unknown
525	*/
526	static int isl_qpolynomial_sign(__isl_keep isl_set *set,
527	__isl_keep isl_qpolynomial *qp)
528	{
529	isl_size d;
530	int i;
531	isl_bool is;
532	isl_poly_rec *rec;
533	isl_vec *v;
534	isl_int l;
535	enum isl_lp_result res;
536	int sgn = 0;
537
538	is = isl_qpolynomial_is_cst(qp, NULL, NULL);
539	if (is < 0)
540	return 0;
541	if (is)
542	return isl_qpolynomial_cst_sign(qp);
543
544	is = isl_qpolynomial_is_affine(qp);
545	if (is < 0)
546	return 0;
547	if (is)
548	return isl_qpolynomial_aff_sign(set, qp);
549
550	if (qp->div->n_row > 0)
551	return 0;
552
553	rec = isl_poly_as_rec(poly: qp->poly);
554	if (!rec)
555	return 0;
556
557	d = isl_space_dim(space: qp->dim, type: isl_dim_all);
558	if (d < 0)
559	return 0;
560	v = isl_vec_alloc(ctx: set->ctx, size: 2 + d);
561	if (!v)
562	return 0;
563
564	isl_seq_clr(p: v->el + 1, len: 1 + d);
565	isl_int_set_si(v->el[0], 1);
566	isl_int_set_si(v->el[2 + qp->poly->var], 1);
567
568	isl_int_init(l);
569
570	res = isl_set_solve_lp(set, max: 0, f: v->el + 1, denom: v->el[0], opt: &l, NULL, NULL);
571	if (res == isl_lp_ok) {
572	isl_qpolynomial *min;
573	isl_qpolynomial *base;
574	isl_qpolynomial *r, *q;
575	isl_qpolynomial *t;
576
577	min = isl_qpolynomial_cst_on_domain(domain: isl_space_copy(space: qp->dim), v: l);
578	base = isl_qpolynomial_var_pow_on_domain(domain: isl_space_copy(space: qp->dim),
579	pos: qp->poly->var, power: 1);
580
581	r = isl_qpolynomial_alloc(space: isl_space_copy(space: qp->dim), n_div: 0,
582	poly: isl_poly_copy(poly: rec->p[rec->n - 1]));
583	q = isl_qpolynomial_copy(qp: r);
584
585	for (i = rec->n - 2; i >= 0; --i) {
586	r = isl_qpolynomial_mul(qp1: r, qp2: isl_qpolynomial_copy(qp: min));
587	t = isl_qpolynomial_alloc(space: isl_space_copy(space: qp->dim), n_div: 0,
588	poly: isl_poly_copy(poly: rec->p[i]));
589	r = isl_qpolynomial_add(qp1: r, qp2: t);
590	if (i == 0)
591	break;
592	q = isl_qpolynomial_mul(qp1: q, qp2: isl_qpolynomial_copy(qp: base));
593	q = isl_qpolynomial_add(qp1: q, qp2: isl_qpolynomial_copy(qp: r));
594	}
595
596	if (isl_qpolynomial_is_zero(qp: q))
597	sgn = isl_qpolynomial_sign(set, qp: r);
598	else if (isl_qpolynomial_is_zero(qp: r))
599	sgn = isl_qpolynomial_sign(set, qp: q);
600	else {
601	int sgn_q, sgn_r;
602	sgn_r = isl_qpolynomial_sign(set, qp: r);
603	sgn_q = isl_qpolynomial_sign(set, qp: q);
604	if (sgn_r == sgn_q)
605	sgn = sgn_r;
606	}
607
608	isl_qpolynomial_free(qp: min);
609	isl_qpolynomial_free(qp: base);
610	isl_qpolynomial_free(qp: q);
611	isl_qpolynomial_free(qp: r);
612	}
613
614	isl_int_clear(l);
615
616	isl_vec_free(vec: v);
617
618	return sgn;
619	}
620
621	/* Check that "fold1" and "fold2" have the same type.
622	*/
623	static isl_stat isl_qpolynomial_fold_check_equal_type(
624	__isl_keep isl_qpolynomial_fold *fold1,
625	__isl_keep isl_qpolynomial_fold *fold2)
626	{
627	enum isl_fold type1, type2;
628
629	type1 = isl_qpolynomial_fold_get_type(fold: fold1);
630	type2 = isl_qpolynomial_fold_get_type(fold: fold2);
631	if (type1 < 0 || type2 < 0)
632	return isl_stat_error;
633	if (type1 != type2)
634	isl_die(isl_qpolynomial_fold_get_ctx(fold1), isl_error_invalid,
635	"fold types don't match", return isl_stat_error);
636	return isl_stat_ok;
637	}
638
639	/* Check that "fold1" and "fold2" have the same (domain) space.
640	*/
641	static isl_stat isl_qpolynomial_fold_check_equal_space(
642	__isl_keep isl_qpolynomial_fold *fold1,
643	__isl_keep isl_qpolynomial_fold *fold2)
644	{
645	isl_bool equal;
646	isl_space *space1, *space2;
647
648	space1 = isl_qpolynomial_fold_peek_domain_space(fold: fold1);
649	space2 = isl_qpolynomial_fold_peek_domain_space(fold: fold2);
650	equal = isl_space_is_equal(space1, space2);
651	if (equal < 0)
652	return isl_stat_error;
653	if (!equal)
654	isl_die(isl_qpolynomial_fold_get_ctx(fold1), isl_error_invalid,
655	"spaces don't match", return isl_stat_error);
656	return isl_stat_ok;
657	}
658
659	/* Combine "list1" and "list2" into a single list, eliminating
660	* those elements of one list that are already covered by the other
661	* list on "set".
662	*
663	* "better" is the sign that the difference qp1 - qp2 needs to have for qp1
664	* to be covered by qp2.
665	*/
666	static __isl_give isl_qpolynomial_list *merge_lists(__isl_keep isl_set *set,
667	__isl_take isl_qpolynomial_list *list1,
668	__isl_take isl_qpolynomial_list *list2, int better)
669	{
670	int i, j;
671	isl_size n1, n2;
672
673	n1 = isl_qpolynomial_list_size(list: list1);
674	n2 = isl_qpolynomial_list_size(list: list2);
675	if (n1 < 0 || n2 < 0)
676	goto error;
677
678	for (i = n2 - 1; i >= 0; --i) {
679	for (j = n1 - 1; j >= 0; --j) {
680	isl_qpolynomial *qp1, *qp2, *d;
681	int sgn;
682	isl_bool equal;
683
684	qp1 = isl_qpolynomial_list_peek(list: list1, index: j);
685	qp2 = isl_qpolynomial_list_peek(list: list2, index: i);
686	equal = isl_qpolynomial_plain_is_equal(qp1, qp2);
687	if (equal < 0)
688	goto error;
689	if (equal)
690	break;
691	d = isl_qpolynomial_sub(
692	qp1: isl_qpolynomial_copy(qp: qp1),
693	qp2: isl_qpolynomial_copy(qp: qp2));
694	sgn = isl_qpolynomial_sign(set, qp: d);
695	isl_qpolynomial_free(qp: d);
696	if (sgn == 0)
697	continue;
698	if (sgn != better)
699	break;
700	list1 = isl_qpolynomial_list_drop(list: list1, first: j, n: 1);
701	n1--;
702	}
703	if (j < 0)
704	continue;
705	list2 = isl_qpolynomial_list_drop(list: list2, first: i, n: 1);
706	n2--;
707	}
708
709	return isl_qpolynomial_list_concat(list1, list2);
710	error:
711	isl_qpolynomial_list_free(list: list1);
712	isl_qpolynomial_list_free(list: list2);
713	return NULL;
714	}
715
716	/* Combine "fold1" and "fold2" into a single reduction, eliminating
717	* those elements of one reduction that are already covered by the other
718	* reduction on "set".
719	*
720	* If "fold1" or "fold2" is an empty reduction, then return
721	* the other reduction.
722	* If "fold1" or "fold2" is a NaN, then return this NaN.
723	*/
724	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
725	__isl_keep isl_set *set,
726	__isl_take isl_qpolynomial_fold *fold1,
727	__isl_take isl_qpolynomial_fold *fold2)
728	{
729	isl_qpolynomial_list *list1;
730	isl_qpolynomial_list *list2;
731	int better;
732
733	if (isl_qpolynomial_fold_check_equal_type(fold1, fold2) < 0)
734	goto error;
735	if (isl_qpolynomial_fold_check_equal_space(fold1, fold2) < 0)
736	goto error;
737
738	better = fold1->type == isl_fold_max ? -1 : 1;
739
740	if (isl_qpolynomial_fold_is_empty(fold: fold1) ||
741	isl_qpolynomial_fold_is_nan(fold: fold2)) {
742	isl_qpolynomial_fold_free(fold: fold1);
743	return fold2;
744	}
745
746	if (isl_qpolynomial_fold_is_empty(fold: fold2) ||
747	isl_qpolynomial_fold_is_nan(fold: fold1)) {
748	isl_qpolynomial_fold_free(fold: fold2);
749	return fold1;
750	}
751
752	list1 = isl_qpolynomial_fold_take_list(fold: fold1);
753	list2 = isl_qpolynomial_fold_take_list(fold: fold2);
754
755	list1 = merge_lists(set, list1, list2, better);
756
757	fold1 = isl_qpolynomial_fold_restore_list(fold: fold1, list: list1);
758	isl_qpolynomial_fold_free(fold: fold2);
759
760	return fold1;
761	error:
762	isl_qpolynomial_fold_free(fold: fold1);
763	isl_qpolynomial_fold_free(fold: fold2);
764	return NULL;
765	}
766
767	/* isl_qpolynomial_list_map callback for adding "qp2" to "qp".
768	*/
769	static __isl_give isl_qpolynomial *add_qpolynomial(
770	__isl_take isl_qpolynomial *qp, void *user)
771	{
772	isl_qpolynomial *qp2 = user;
773
774	return isl_qpolynomial_add(qp1: qp, qp2: isl_qpolynomial_copy(qp: qp2));
775	}
776
777	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
778	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
779	{
780	isl_qpolynomial_list *list;
781
782	if (!fold || !qp)
783	goto error;
784
785	if (isl_qpolynomial_is_zero(qp)) {
786	isl_qpolynomial_free(qp);
787	return fold;
788	}
789
790	list = isl_qpolynomial_fold_take_list(fold);
791	list = isl_qpolynomial_list_map(list, fn: &add_qpolynomial, user: qp);
792	fold = isl_qpolynomial_fold_restore_list(fold, list);
793
794	isl_qpolynomial_free(qp);
795	return fold;
796	error:
797	isl_qpolynomial_fold_free(fold);
798	isl_qpolynomial_free(qp);
799	return NULL;
800	}
801
802	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
803	__isl_keep isl_set *dom,
804	__isl_take isl_qpolynomial_fold *fold1,
805	__isl_take isl_qpolynomial_fold *fold2)
806	{
807	int i;
808	isl_size n1, n2;
809	isl_qpolynomial_fold *res = NULL;
810	isl_qpolynomial *qp;
811	isl_qpolynomial_list *list1, *list2;
812
813	if (!fold1 || !fold2)
814	goto error;
815
816	if (isl_qpolynomial_fold_is_empty(fold: fold1)) {
817	isl_qpolynomial_fold_free(fold: fold1);
818	return fold2;
819	}
820
821	if (isl_qpolynomial_fold_is_empty(fold: fold2)) {
822	isl_qpolynomial_fold_free(fold: fold2);
823	return fold1;
824	}
825
826	list1 = isl_qpolynomial_fold_peek_list(fold: fold1);
827	list2 = isl_qpolynomial_fold_peek_list(fold: fold2);
828	n1 = isl_qpolynomial_list_size(list: list1);
829	n2 = isl_qpolynomial_list_size(list: list2);
830	if (n1 < 0 || n2 < 0)
831	goto error;
832
833	if (n1 == 1 && n2 != 1)
834	return isl_qpolynomial_fold_add_on_domain(dom, fold1: fold2, fold2: fold1);
835
836	qp = isl_qpolynomial_list_get_at(list: list2, index: 0);
837	if (n2 == 1) {
838	res = isl_qpolynomial_fold_add_qpolynomial(fold: fold1, qp);
839	isl_qpolynomial_fold_free(fold: fold2);
840	return res;
841	}
842
843	res = isl_qpolynomial_fold_add_qpolynomial(
844	fold: isl_qpolynomial_fold_copy(fold: fold1), qp);
845
846	for (i = 1; i < n2; ++i) {
847	isl_qpolynomial_fold *res_i;
848
849	qp = isl_qpolynomial_list_get_at(list: list2, index: i);
850	res_i = isl_qpolynomial_fold_add_qpolynomial(
851	fold: isl_qpolynomial_fold_copy(fold: fold1), qp);
852	res = isl_qpolynomial_fold_fold_on_domain(set: dom, fold1: res, fold2: res_i);
853	}
854
855	isl_qpolynomial_fold_free(fold: fold1);
856	isl_qpolynomial_fold_free(fold: fold2);
857	return res;
858	error:
859	isl_qpolynomial_fold_free(fold: res);
860	isl_qpolynomial_fold_free(fold: fold1);
861	isl_qpolynomial_fold_free(fold: fold2);
862	return NULL;
863	}
864
865	/* isl_qpolynomial_list_map callback for calling
866	* isl_qpolynomial_substitute_equalities on "qp" and "eq".
867	*/
868	static __isl_give isl_qpolynomial *substitute_equalities(
869	__isl_take isl_qpolynomial *qp, void *user)
870	{
871	isl_basic_set *eq = user;
872
873	eq = isl_basic_set_copy(bset: eq);
874	return isl_qpolynomial_substitute_equalities(qp, eq);
875	}
876
877	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
878	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
879	{
880	isl_qpolynomial_list *list;
881
882	list = isl_qpolynomial_fold_take_list(fold);
883	list = isl_qpolynomial_list_map(list, fn: &substitute_equalities, user: eq);
884	fold = isl_qpolynomial_fold_restore_list(fold, list);
885
886	isl_basic_set_free(bset: eq);
887	return fold;
888	}
889
890	/* isl_qpolynomial_list_map callback for calling
891	* isl_qpolynomial_substitute_equalities on "qp" and "context".
892	*/
893	static __isl_give isl_qpolynomial *gist(__isl_take isl_qpolynomial *qp,
894	void *user)
895	{
896	isl_set *context = user;
897
898	return isl_qpolynomial_gist(qp, context: isl_set_copy(set: context));
899	}
900
901	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
902	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
903	{
904	isl_qpolynomial_list *list;
905
906	list = isl_qpolynomial_fold_take_list(fold);
907	list = isl_qpolynomial_list_map(list, fn: &gist, user: context);
908	fold = isl_qpolynomial_fold_restore_list(fold, list);
909
910	isl_set_free(set: context);
911	return fold;
912	}
913
914	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
915	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
916	{
917	isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
918	isl_set *dom_context = isl_set_universe(space);
919	dom_context = isl_set_intersect_params(set: dom_context, params: context);
920	return isl_qpolynomial_fold_gist(fold, context: dom_context);
921	}
922
923	/* Return a zero (i.e., empty) isl_qpolynomial_fold in the given space.
924	*
925	* This is a helper function for isl_pw_*_as_* that ensures a uniform
926	* interface over all piecewise types.
927	*/
928	static __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_zero_in_space(
929	__isl_take isl_space *space, enum isl_fold type)
930	{
931	return isl_qpolynomial_fold_empty(type, space: isl_space_domain(space));
932	}
933
934	#define isl_qpolynomial_fold_involves_nan isl_qpolynomial_fold_is_nan
935
936	#define HAS_TYPE
937
938	#undef PW
939	#define PW isl_pw_qpolynomial_fold
940	#undef BASE
941	#define BASE qpolynomial_fold
942	#undef EL_IS_ZERO
943	#define EL_IS_ZERO is_empty
944	#undef ZERO
945	#define ZERO zero
946	#undef IS_ZERO
947	#define IS_ZERO is_zero
948	#undef FIELD
949	#define FIELD fold
950	#undef DEFAULT_IS_ZERO
951	#define DEFAULT_IS_ZERO 1
952
953	#include <isl_pw_templ.c>
954	#include <isl_pw_add_disjoint_templ.c>
955	#include <isl_pw_eval.c>
956	#include <isl_pw_fix_templ.c>
957	#include <isl_pw_from_range_templ.c>
958	#include <isl_pw_insert_dims_templ.c>
959	#include <isl_pw_lift_templ.c>
960	#include <isl_pw_morph_templ.c>
961	#include <isl_pw_move_dims_templ.c>
962	#include <isl_pw_opt_templ.c>
963
964	#undef BASE
965	#define BASE pw_qpolynomial_fold
966
967	#include <isl_union_single.c>
968	#include <isl_union_eval.c>
969
970	/* Construct a new reduction of the given type and space
971	* with an empty list of polynomials.
972	*/
973	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
974	__isl_take isl_space *space)
975	{
976	isl_ctx *ctx;
977	isl_qpolynomial_list *list;
978
979	if (!space)
980	return NULL;
981	ctx = isl_space_get_ctx(space);
982	list = isl_qpolynomial_list_alloc(ctx, n: 0);
983	return qpolynomial_fold_alloc(type, space, list);
984	}
985
986	/* Construct a new reduction of the given type and
987	* a single given polynomial.
988	*/
989	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
990	enum isl_fold type, __isl_take isl_qpolynomial *qp)
991	{
992	isl_space *space;
993	isl_qpolynomial_list *list;
994
995	space = isl_qpolynomial_get_domain_space(qp);
996	list = isl_qpolynomial_list_from_qpolynomial(el: qp);
997	return qpolynomial_fold_alloc(type, space, list);
998	}
999
1000	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
1001	__isl_keep isl_qpolynomial_fold *fold)
1002	{
1003	if (!fold)
1004	return NULL;
1005
1006	fold->ref++;
1007	return fold;
1008	}
1009
1010	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
1011	__isl_keep isl_qpolynomial_fold *fold)
1012	{
1013	enum isl_fold type;
1014	isl_space *space;
1015	isl_qpolynomial_list *list;
1016
1017	type = isl_qpolynomial_fold_get_type(fold);
1018	space = isl_qpolynomial_fold_get_domain_space(fold);
1019	list = isl_qpolynomial_fold_get_list(fold);
1020	return qpolynomial_fold_alloc(type, space, list);
1021	}
1022
1023	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
1024	__isl_take isl_qpolynomial_fold *fold)
1025	{
1026	if (!fold)
1027	return NULL;
1028
1029	if (fold->ref == 1)
1030	return fold;
1031	fold->ref--;
1032	return isl_qpolynomial_fold_dup(fold);
1033	}
1034
1035	__isl_null isl_qpolynomial_fold *isl_qpolynomial_fold_free(
1036	__isl_take isl_qpolynomial_fold *fold)
1037	{
1038	if (!fold)
1039	return NULL;
1040	if (--fold->ref > 0)
1041	return NULL;
1042
1043	isl_qpolynomial_list_free(list: fold->list);
1044	isl_space_free(space: fold->dim);
1045	free(ptr: fold);
1046
1047	return NULL;
1048	}
1049
1050	isl_bool isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
1051	{
1052	isl_size n;
1053	isl_qpolynomial_list *list;
1054
1055	list = isl_qpolynomial_fold_peek_list(fold);
1056	n = isl_qpolynomial_list_size(list);
1057	if (n < 0)
1058	return isl_bool_error;
1059
1060	return isl_bool_ok(b: n == 0);
1061	}
1062
1063	/* Does "fold" represent max(NaN) or min(NaN)?
1064	*/
1065	isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold)
1066	{
1067	isl_size n;
1068	isl_qpolynomial *qp;
1069	isl_qpolynomial_list *list;
1070
1071	list = isl_qpolynomial_fold_peek_list(fold);
1072	n = isl_qpolynomial_list_size(list);
1073	if (n < 0)
1074	return isl_bool_error;
1075	if (n != 1)
1076	return isl_bool_false;
1077	qp = isl_qpolynomial_list_peek(list, index: 0);
1078	return isl_qpolynomial_is_nan(qp);
1079	}
1080
1081	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
1082	__isl_take isl_qpolynomial_fold *fold1,
1083	__isl_take isl_qpolynomial_fold *fold2)
1084	{
1085	isl_qpolynomial_list *list1, *list2;
1086
1087	if (isl_qpolynomial_fold_check_equal_type(fold1, fold2) < 0)
1088	goto error;
1089	if (isl_qpolynomial_fold_check_equal_space(fold1, fold2) < 0)
1090	goto error;
1091
1092	if (isl_qpolynomial_fold_is_empty(fold: fold1)) {
1093	isl_qpolynomial_fold_free(fold: fold1);
1094	return fold2;
1095	}
1096
1097	if (isl_qpolynomial_fold_is_empty(fold: fold2)) {
1098	isl_qpolynomial_fold_free(fold: fold2);
1099	return fold1;
1100	}
1101
1102	list1 = isl_qpolynomial_fold_take_list(fold: fold1);
1103	list2 = isl_qpolynomial_fold_take_list(fold: fold2);
1104	list1 = isl_qpolynomial_list_concat(list1, list2);
1105	fold1 = isl_qpolynomial_fold_restore_list(fold: fold1, list: list1);
1106	isl_qpolynomial_fold_free(fold: fold2);
1107
1108	return fold1;
1109	error:
1110	isl_qpolynomial_fold_free(fold: fold1);
1111	isl_qpolynomial_fold_free(fold: fold2);
1112	return NULL;
1113	}
1114
1115	__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
1116	__isl_take isl_pw_qpolynomial_fold *pw1,
1117	__isl_take isl_pw_qpolynomial_fold *pw2)
1118	{
1119	int i, j, n;
1120	struct isl_pw_qpolynomial_fold *res;
1121	isl_set *set;
1122
1123	if (!pw1 || !pw2)
1124	goto error;
1125
1126	isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
1127
1128	if (isl_pw_qpolynomial_fold_is_zero(pw: pw1)) {
1129	isl_pw_qpolynomial_fold_free(pw: pw1);
1130	return pw2;
1131	}
1132
1133	if (isl_pw_qpolynomial_fold_is_zero(pw: pw2)) {
1134	isl_pw_qpolynomial_fold_free(pw: pw2);
1135	return pw1;
1136	}
1137
1138	if (pw1->type != pw2->type)
1139	isl_die(pw1->dim->ctx, isl_error_invalid,
1140	"fold types don't match", goto error);
1141
1142	n = (pw1->n + 1) * (pw2->n + 1);
1143	res = isl_pw_qpolynomial_fold_alloc_size(space: isl_space_copy(space: pw1->dim),
1144	type: pw1->type, n);
1145
1146	for (i = 0; i < pw1->n; ++i) {
1147	set = isl_set_copy(set: pw1->p[i].set);
1148	for (j = 0; j < pw2->n; ++j) {
1149	struct isl_set *common;
1150	isl_qpolynomial_fold *sum;
1151	set = isl_set_subtract(set1: set,
1152	set2: isl_set_copy(set: pw2->p[j].set));
1153	common = isl_set_intersect(set1: isl_set_copy(set: pw1->p[i].set),
1154	set2: isl_set_copy(set: pw2->p[j].set));
1155	if (isl_set_plain_is_empty(set: common)) {
1156	isl_set_free(set: common);
1157	continue;
1158	}
1159
1160	sum = isl_qpolynomial_fold_fold_on_domain(set: common,
1161	fold1: isl_qpolynomial_fold_copy(fold: pw1->p[i].fold),
1162	fold2: isl_qpolynomial_fold_copy(fold: pw2->p[j].fold));
1163
1164	res = isl_pw_qpolynomial_fold_add_piece(pw: res, set: common, el: sum);
1165	}
1166	res = isl_pw_qpolynomial_fold_add_piece(pw: res, set,
1167	el: isl_qpolynomial_fold_copy(fold: pw1->p[i].fold));
1168	}
1169
1170	for (j = 0; j < pw2->n; ++j) {
1171	set = isl_set_copy(set: pw2->p[j].set);
1172	for (i = 0; i < pw1->n; ++i)
1173	set = isl_set_subtract(set1: set, set2: isl_set_copy(set: pw1->p[i].set));
1174	res = isl_pw_qpolynomial_fold_add_piece(pw: res, set,
1175	el: isl_qpolynomial_fold_copy(fold: pw2->p[j].fold));
1176	}
1177
1178	isl_pw_qpolynomial_fold_free(pw: pw1);
1179	isl_pw_qpolynomial_fold_free(pw: pw2);
1180
1181	return res;
1182	error:
1183	isl_pw_qpolynomial_fold_free(pw: pw1);
1184	isl_pw_qpolynomial_fold_free(pw: pw2);
1185	return NULL;
1186	}
1187
1188	__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1189	__isl_take isl_union_pw_qpolynomial_fold *u,
1190	__isl_take isl_pw_qpolynomial_fold *part)
1191	{
1192	struct isl_hash_table_entry *entry;
1193
1194	u = isl_union_pw_qpolynomial_fold_cow(u);
1195
1196	if (!part || !u)
1197	goto error;
1198	if (isl_space_check_equal_params(space1: part->dim, space2: u->space) < 0)
1199	goto error;
1200
1201	entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, space: part->dim, reserve: 1);
1202	if (!entry)
1203	goto error;
1204
1205	if (!entry->data)
1206	entry->data = part;
1207	else {
1208	entry->data = isl_pw_qpolynomial_fold_fold(pw1: entry->data,
1209	pw2: isl_pw_qpolynomial_fold_copy(pw: part));
1210	if (!entry->data)
1211	goto error;
1212	isl_pw_qpolynomial_fold_free(pw: part);
1213	}
1214
1215	return u;
1216	error:
1217	isl_pw_qpolynomial_fold_free(pw: part);
1218	isl_union_pw_qpolynomial_fold_free(u);
1219	return NULL;
1220	}
1221
1222	static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
1223	{
1224	isl_union_pw_qpolynomial_fold **u;
1225	u = (isl_union_pw_qpolynomial_fold **)user;
1226
1227	*u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(u: *u, part);
1228
1229	return isl_stat_ok;
1230	}
1231
1232	__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
1233	__isl_take isl_union_pw_qpolynomial_fold *u1,
1234	__isl_take isl_union_pw_qpolynomial_fold *u2)
1235	{
1236	u1 = isl_union_pw_qpolynomial_fold_cow(u: u1);
1237
1238	if (!u1 || !u2)
1239	goto error;
1240
1241	if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u: u2,
1242	fn: &fold_part, user: &u1) < 0)
1243	goto error;
1244
1245	isl_union_pw_qpolynomial_fold_free(u: u2);
1246
1247	return u1;
1248	error:
1249	isl_union_pw_qpolynomial_fold_free(u: u1);
1250	isl_union_pw_qpolynomial_fold_free(u: u2);
1251	return NULL;
1252	}
1253
1254	__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
1255	enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
1256	{
1257	int i;
1258	isl_pw_qpolynomial_fold *pwf;
1259
1260	if (!pwqp)
1261	return NULL;
1262
1263	pwf = isl_pw_qpolynomial_fold_alloc_size(space: isl_space_copy(space: pwqp->dim),
1264	type, n: pwqp->n);
1265
1266	for (i = 0; i < pwqp->n; ++i)
1267	pwf = isl_pw_qpolynomial_fold_add_piece(pw: pwf,
1268	set: isl_set_copy(set: pwqp->p[i].set),
1269	el: isl_qpolynomial_fold_alloc(type,
1270	qp: isl_qpolynomial_copy(qp: pwqp->p[i].qp)));
1271
1272	isl_pw_qpolynomial_free(pwqp);
1273
1274	return pwf;
1275	}
1276
1277	__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
1278	__isl_take isl_pw_qpolynomial_fold *pwf1,
1279	__isl_take isl_pw_qpolynomial_fold *pwf2)
1280	{
1281	return isl_pw_qpolynomial_fold_union_add_(pw1: pwf1, pw2: pwf2);
1282	}
1283
1284	/* Compare two quasi-polynomial reductions.
1285	*
1286	* Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater"
1287	* than "fold2" and 0 if they are equal.
1288	*/
1289	int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1,
1290	__isl_keep isl_qpolynomial_fold *fold2)
1291	{
1292	int i;
1293	isl_size n1, n2;
1294	isl_qpolynomial_list *list1, *list2;
1295
1296	if (fold1 == fold2)
1297	return 0;
1298	list1 = isl_qpolynomial_fold_peek_list(fold: fold1);
1299	list2 = isl_qpolynomial_fold_peek_list(fold: fold2);
1300	n1 = isl_qpolynomial_list_size(list: list1);
1301	n2 = isl_qpolynomial_list_size(list: list2);
1302	if (n1 < 0)
1303	return -1;
1304	if (n2 < 0)
1305	return 1;
1306
1307	if (n1 != n2)
1308	return n1 - n2;
1309
1310	for (i = 0; i < n1; ++i) {
1311	int cmp;
1312	isl_qpolynomial *qp1, *qp2;
1313
1314	qp1 = isl_qpolynomial_list_peek(list: list1, index: i);
1315	qp2 = isl_qpolynomial_list_peek(list: list2, index: i);
1316	cmp = isl_qpolynomial_plain_cmp(qp1, qp2);
1317	if (cmp != 0)
1318	return cmp;
1319	}
1320
1321	return 0;
1322	}
1323
1324	/* Are the lists "list1" and "list2", both consisting of "n" elements
1325	* obviously equal to each other?
1326	*/
1327	static isl_bool isl_qpolynomial_list_plain_is_equal(unsigned n,
1328	isl_qpolynomial_list *list1, isl_qpolynomial_list *list2)
1329	{
1330	int i;
1331
1332	for (i = 0; i < n; ++i) {
1333	isl_bool eq;
1334	isl_qpolynomial *qp1, *qp2;
1335
1336	qp1 = isl_qpolynomial_list_peek(list: list1, index: i);
1337	qp2 = isl_qpolynomial_list_peek(list: list2, index: i);
1338	eq = isl_qpolynomial_plain_is_equal(qp1, qp2);
1339	if (eq < 0 || !eq)
1340	return eq;
1341	}
1342
1343	return isl_bool_true;
1344	}
1345
1346	/* Wrapper around isl_qpolynomial_plain_cmp for use
1347	* as a isl_qpolynomial_list_sort callback.
1348	*/
1349	static int qpolynomial_cmp(__isl_keep isl_qpolynomial *a,
1350	__isl_keep isl_qpolynomial *b, void *user)
1351	{
1352	return isl_qpolynomial_plain_cmp(qp1: a, qp2: b);
1353	}
1354
1355	isl_bool isl_qpolynomial_fold_plain_is_equal(
1356	__isl_keep isl_qpolynomial_fold *fold1,
1357	__isl_keep isl_qpolynomial_fold *fold2)
1358	{
1359	isl_bool equal;
1360	isl_size n1, n2;
1361	isl_qpolynomial_list *list1, *list2;
1362
1363	list1 = isl_qpolynomial_fold_peek_list(fold: fold1);
1364	list2 = isl_qpolynomial_fold_peek_list(fold: fold2);
1365	n1 = isl_qpolynomial_list_size(list: list1);
1366	n2 = isl_qpolynomial_list_size(list: list2);
1367	if (n1 < 0 || n2 < 0)
1368	return isl_bool_error;
1369
1370	if (n1 != n2)
1371	return isl_bool_false;
1372
1373	list1 = isl_qpolynomial_list_copy(list: list1);
1374	list1 = isl_qpolynomial_list_sort(list: list1, cmp: &qpolynomial_cmp, NULL);
1375	list2 = isl_qpolynomial_list_copy(list: list2);
1376	list2 = isl_qpolynomial_list_sort(list: list2, cmp: &qpolynomial_cmp, NULL);
1377	equal = isl_qpolynomial_list_plain_is_equal(n: n1, list1, list2);
1378	isl_qpolynomial_list_free(list: list1);
1379	isl_qpolynomial_list_free(list: list2);
1380	return equal;
1381	}
1382
1383	__isl_give isl_val *isl_qpolynomial_fold_eval(
1384	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
1385	{
1386	isl_size n;
1387	isl_ctx *ctx;
1388	isl_val *v;
1389	isl_qpolynomial *qp;
1390	isl_qpolynomial_list *list;
1391
1392	if (!fold || !pnt)
1393	goto error;
1394	ctx = isl_point_get_ctx(pnt);
1395	isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
1396	isl_assert(pnt->dim->ctx,
1397	fold->type == isl_fold_max || fold->type == isl_fold_min,
1398	goto error);
1399
1400	list = isl_qpolynomial_fold_peek_list(fold);
1401	n = isl_qpolynomial_list_size(list);
1402	if (n < 0)
1403	goto error;
1404
1405	if (n == 0)
1406	v = isl_val_zero(ctx);
1407	else {
1408	int i;
1409
1410	qp = isl_qpolynomial_list_get_at(list, index: 0);
1411	v = isl_qpolynomial_eval(qp, pnt: isl_point_copy(pnt));
1412	for (i = 1; i < n; ++i) {
1413	isl_val *v_i;
1414
1415	qp = isl_qpolynomial_list_get_at(list, index: i);
1416	v_i = isl_qpolynomial_eval(qp, pnt: isl_point_copy(pnt));
1417	if (fold->type == isl_fold_max)
1418	v = isl_val_max(v1: v, v2: v_i);
1419	else
1420	v = isl_val_min(v1: v, v2: v_i);
1421	}
1422	}
1423	isl_qpolynomial_fold_free(fold);
1424	isl_point_free(pnt);
1425
1426	return v;
1427	error:
1428	isl_qpolynomial_fold_free(fold);
1429	isl_point_free(pnt);
1430	return NULL;
1431	}
1432
1433	size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
1434	{
1435	int i;
1436	size_t n = 0;
1437
1438	for (i = 0; i < pwf->n; ++i) {
1439	isl_size n_i;
1440	isl_qpolynomial_list *list;
1441
1442	list = isl_qpolynomial_fold_peek_list(fold: pwf->p[i].fold);
1443	n_i = isl_qpolynomial_list_size(list);
1444	if (n_i < 0)
1445	return isl_size_error;
1446
1447	n += n_i;
1448	}
1449
1450	return n;
1451	}
1452
1453	__isl_give isl_val *isl_qpolynomial_fold_opt_on_domain(
1454	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1455	{
1456	int i;
1457	isl_size n;
1458	isl_val *opt;
1459	isl_qpolynomial *qp;
1460	isl_qpolynomial_list *list;
1461
1462	list = isl_qpolynomial_fold_peek_list(fold);
1463	n = isl_qpolynomial_list_size(list);
1464	if (!set || n < 0)
1465	goto error;
1466
1467	if (n == 0) {
1468	opt = isl_val_zero(ctx: isl_set_get_ctx(set));
1469	isl_set_free(set);
1470	isl_qpolynomial_fold_free(fold);
1471	return opt;
1472	}
1473
1474	qp = isl_qpolynomial_list_get_at(list, index: 0);
1475	opt = isl_qpolynomial_opt_on_domain(qp, set: isl_set_copy(set), max);
1476	for (i = 1; i < n; ++i) {
1477	isl_val *opt_i;
1478
1479	qp = isl_qpolynomial_list_get_at(list, index: i);
1480	opt_i = isl_qpolynomial_opt_on_domain(qp,
1481	set: isl_set_copy(set), max);
1482	if (max)
1483	opt = isl_val_max(v1: opt, v2: opt_i);
1484	else
1485	opt = isl_val_min(v1: opt, v2: opt_i);
1486	}
1487
1488	isl_set_free(set);
1489	isl_qpolynomial_fold_free(fold);
1490
1491	return opt;
1492	error:
1493	isl_set_free(set);
1494	isl_qpolynomial_fold_free(fold);
1495	return NULL;
1496	}
1497
1498	/* Check whether for each quasi-polynomial in "fold2" there is
1499	* a quasi-polynomial in "fold1" that dominates it on "set".
1500	*/
1501	static isl_bool qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1502	__isl_keep isl_qpolynomial_fold *fold1,
1503	__isl_keep isl_qpolynomial_fold *fold2)
1504	{
1505	int i, j;
1506	int covers;
1507	isl_size n1, n2;
1508	isl_qpolynomial_list *list1, *list2;
1509
1510	list1 = isl_qpolynomial_fold_peek_list(fold: fold1);
1511	list2 = isl_qpolynomial_fold_peek_list(fold: fold2);
1512	n1 = isl_qpolynomial_list_size(list: list1);
1513	n2 = isl_qpolynomial_list_size(list: list2);
1514	if (!set || n1 < 0 || n2 < 0)
1515	return isl_bool_error;
1516
1517	covers = fold1->type == isl_fold_max ? 1 : -1;
1518
1519	for (i = 0; i < n2; ++i) {
1520	for (j = 0; j < n1; ++j) {
1521	isl_qpolynomial *qp1, *qp2, *d;
1522	int sgn;
1523
1524	qp1 = isl_qpolynomial_list_get_at(list: list1, index: j);
1525	qp2 = isl_qpolynomial_list_get_at(list: list2, index: i);
1526	d = isl_qpolynomial_sub(qp1, qp2);
1527	sgn = isl_qpolynomial_sign(set, qp: d);
1528	isl_qpolynomial_free(qp: d);
1529	if (sgn == covers)
1530	break;
1531	}
1532	if (j >= n1)
1533	return isl_bool_false;
1534	}
1535
1536	return isl_bool_true;
1537	}
1538
1539	/* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1540	* that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1541	* that of pwf2.
1542	*/
1543	isl_bool isl_pw_qpolynomial_fold_covers(
1544	__isl_keep isl_pw_qpolynomial_fold *pwf1,
1545	__isl_keep isl_pw_qpolynomial_fold *pwf2)
1546	{
1547	int i, j;
1548	isl_set *dom1, *dom2;
1549	isl_bool is_subset;
1550
1551	if (!pwf1 || !pwf2)
1552	return isl_bool_error;
1553
1554	if (pwf2->n == 0)
1555	return isl_bool_true;
1556	if (pwf1->n == 0)
1557	return isl_bool_false;
1558
1559	dom1 = isl_pw_qpolynomial_fold_domain(pw: isl_pw_qpolynomial_fold_copy(pw: pwf1));
1560	dom2 = isl_pw_qpolynomial_fold_domain(pw: isl_pw_qpolynomial_fold_copy(pw: pwf2));
1561	is_subset = isl_set_is_subset(set1: dom2, set2: dom1);
1562	isl_set_free(set: dom1);
1563	isl_set_free(set: dom2);
1564
1565	if (is_subset < 0 || !is_subset)
1566	return is_subset;
1567
1568	for (i = 0; i < pwf2->n; ++i) {
1569	for (j = 0; j < pwf1->n; ++j) {
1570	isl_bool is_empty;
1571	isl_set *common;
1572	isl_bool covers;
1573
1574	common = isl_set_intersect(set1: isl_set_copy(set: pwf1->p[j].set),
1575	set2: isl_set_copy(set: pwf2->p[i].set));
1576	is_empty = isl_set_is_empty(set: common);
1577	if (is_empty < 0 || is_empty) {
1578	isl_set_free(set: common);
1579	if (is_empty < 0)
1580	return isl_bool_error;
1581	continue;
1582	}
1583	covers = qpolynomial_fold_covers_on_domain(set: common,
1584	fold1: pwf1->p[j].fold, fold2: pwf2->p[i].fold);
1585	isl_set_free(set: common);
1586	if (covers < 0 || !covers)
1587	return covers;
1588	}
1589	}
1590
1591	return isl_bool_true;
1592	}
1593
1594	/* isl_qpolynomial_list_map callback that calls
1595	* isl_qpolynomial_morph_domain on "qp".
1596	*/
1597	static __isl_give isl_qpolynomial *morph_domain(
1598	__isl_take isl_qpolynomial *qp, void *user)
1599	{
1600	isl_morph *morph = user;
1601
1602	return isl_qpolynomial_morph_domain(qp, morph: isl_morph_copy(morph));
1603	}
1604
1605	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain(
1606	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1607	{
1608	isl_space *space;
1609	isl_qpolynomial_list *list;
1610
1611	space = isl_qpolynomial_fold_peek_domain_space(fold);
1612	if (isl_morph_check_applies(morph, space) < 0)
1613	goto error;
1614
1615	list = isl_qpolynomial_fold_take_list(fold);
1616	list = isl_qpolynomial_list_map(list, fn: &morph_domain, user: morph);
1617	fold = isl_qpolynomial_fold_restore_list(fold, list);
1618
1619	space = isl_morph_get_ran_space(morph);
1620	isl_space_free(space: isl_qpolynomial_fold_take_domain_space(fold));
1621	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
1622
1623	isl_morph_free(morph);
1624
1625	return fold;
1626	error:
1627	isl_qpolynomial_fold_free(fold);
1628	isl_morph_free(morph);
1629	return NULL;
1630	}
1631
1632	enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1633	{
1634	if (!fold)
1635	return isl_fold_error;
1636	return fold->type;
1637	}
1638
1639	/* Return the type of this piecewise quasipolynomial reduction.
1640	*/
1641	enum isl_fold isl_pw_qpolynomial_fold_get_type(
1642	__isl_keep isl_pw_qpolynomial_fold *pwf)
1643	{
1644	if (!pwf)
1645	return isl_fold_error;
1646	return pwf->type;
1647	}
1648
1649	enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1650	__isl_keep isl_union_pw_qpolynomial_fold *upwf)
1651	{
1652	if (!upwf)
1653	return isl_fold_error;
1654	return upwf->type;
1655	}
1656
1657	/* isl_qpolynomial_list_map callback that calls
1658	* isl_qpolynomial_lift on "qp".
1659	*/
1660	static __isl_give isl_qpolynomial *lift(__isl_take isl_qpolynomial *qp,
1661	void *user)
1662	{
1663	isl_space *space = user;
1664
1665	return isl_qpolynomial_lift(qp, space: isl_space_copy(space));
1666	}
1667
1668	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1669	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space)
1670	{
1671	isl_qpolynomial_list *list;
1672
1673	if (!fold || !space)
1674	goto error;
1675
1676	if (isl_space_is_equal(space1: fold->dim, space2: space)) {
1677	isl_space_free(space);
1678	return fold;
1679	}
1680
1681	list = isl_qpolynomial_fold_take_list(fold);
1682	list = isl_qpolynomial_list_map(list, fn: &lift, user: space);
1683	fold = isl_qpolynomial_fold_restore_list(fold, list);
1684
1685	isl_space_free(space: isl_qpolynomial_fold_take_domain_space(fold));
1686	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
1687
1688	return fold;
1689	error:
1690	isl_qpolynomial_fold_free(fold);
1691	isl_space_free(space);
1692	return NULL;
1693	}
1694
1695	isl_stat isl_qpolynomial_fold_foreach_qpolynomial(
1696	__isl_keep isl_qpolynomial_fold *fold,
1697	isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1698	{
1699	isl_qpolynomial_list *list;
1700
1701	list = isl_qpolynomial_fold_peek_list(fold);
1702	return isl_qpolynomial_list_foreach(list, fn, user);
1703	}
1704
1705	/* Internal data structure for isl_qpolynomial_fold_move_dims
1706	* representing its arguments.
1707	*/
1708	struct isl_fold_move_dims_data {
1709	enum isl_dim_type dst_type;
1710	unsigned dst_pos;
1711	enum isl_dim_type src_type;
1712	unsigned src_pos;
1713	unsigned n;
1714	};
1715
1716	/* isl_qpolynomial_list_map callback for calling
1717	* isl_qpolynomial_move_dims on "qp".
1718	*/
1719	static __isl_give isl_qpolynomial *move_dims(__isl_take isl_qpolynomial *qp,
1720	void *user)
1721	{
1722	struct isl_fold_move_dims_data *data = user;
1723
1724	qp = isl_qpolynomial_move_dims(qp, dst_type: data->dst_type, dst_pos: data->dst_pos,
1725	src_type: data->src_type, src_pos: data->src_pos, n: data->n);
1726	return qp;
1727	}
1728
1729	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1730	__isl_take isl_qpolynomial_fold *fold,
1731	enum isl_dim_type dst_type, unsigned dst_pos,
1732	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1733	{
1734	struct isl_fold_move_dims_data data =
1735	{ dst_type, dst_pos, src_type, src_pos, n };
1736	enum isl_dim_type set_src_type, set_dst_type;
1737	isl_space *space;
1738	isl_qpolynomial_list *list;
1739
1740	if (n == 0)
1741	return fold;
1742
1743	fold = isl_qpolynomial_fold_cow(fold);
1744	if (!fold)
1745	return NULL;
1746
1747	set_src_type = domain_type(type: src_type);
1748	set_dst_type = domain_type(type: dst_type);
1749
1750	list = isl_qpolynomial_fold_take_list(fold);
1751	list = isl_qpolynomial_list_map(list, fn: &move_dims, user: &data);
1752	fold = isl_qpolynomial_fold_restore_list(fold, list);
1753
1754	space = isl_qpolynomial_fold_take_domain_space(fold);
1755	space = isl_space_move_dims(space, dst_type: set_dst_type, dst_pos,
1756	src_type: set_src_type, src_pos, n);
1757	fold = isl_qpolynomial_fold_restore_domain_space(fold, space);
1758
1759	return fold;
1760	}
1761
1762	/* Internal data structure for isl_qpolynomial_fold_substitute
1763	* representing its arguments.
1764	*/
1765	struct isl_fold_substitute {
1766	enum isl_dim_type type;
1767	unsigned first;
1768	unsigned n;
1769	isl_qpolynomial **subs;
1770	};
1771
1772	/* isl_qpolynomial_list_map callback for calling
1773	* isl_qpolynomial_substitute on "qp".
1774	*/
1775	static __isl_give isl_qpolynomial *substitute(__isl_take isl_qpolynomial *qp,
1776	void *user)
1777	{
1778	struct isl_fold_substitute *data = user;
1779
1780	qp = isl_qpolynomial_substitute(qp,
1781	type: data->type, first: data->first, n: data->n, subs: data->subs);
1782	return qp;
1783	}
1784
1785	/* For each 0 <= i < "n", replace variable "first" + i of type "type"
1786	* in fold->qp[k] by subs[i].
1787	*/
1788	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1789	__isl_take isl_qpolynomial_fold *fold,
1790	enum isl_dim_type type, unsigned first, unsigned n,
1791	__isl_keep isl_qpolynomial **subs)
1792	{
1793	struct isl_fold_substitute data = { type, first, n, subs };
1794	isl_qpolynomial_list *list;
1795
1796	if (n == 0)
1797	return fold;
1798
1799	list = isl_qpolynomial_fold_take_list(fold);
1800	list = isl_qpolynomial_list_map(list, fn: &substitute, user: &data);
1801	fold = isl_qpolynomial_fold_restore_list(fold, list);
1802
1803	return fold;
1804	}
1805
1806	static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1807	{
1808	isl_pw_qpolynomial_fold *pwf;
1809	isl_union_pw_qpolynomial_fold **upwf;
1810	struct isl_hash_table_entry *entry;
1811
1812	upwf = (isl_union_pw_qpolynomial_fold **)user;
1813
1814	entry = isl_union_pw_qpolynomial_fold_find_part_entry(u: *upwf,
1815	space: pwqp->dim, reserve: 1);
1816	if (!entry)
1817	goto error;
1818
1819	pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type: (*upwf)->type, pwqp);
1820	if (!entry->data)
1821	entry->data = pwf;
1822	else {
1823	entry->data = isl_pw_qpolynomial_fold_add(pwf1: entry->data, pwf2: pwf);
1824	if (!entry->data)
1825	return isl_stat_error;
1826	if (isl_pw_qpolynomial_fold_is_zero(pw: entry->data))
1827	*upwf = isl_union_pw_qpolynomial_fold_remove_part_entry(
1828	u: *upwf, part_entry: entry);
1829	}
1830
1831	return isl_stat_ok;
1832	error:
1833	isl_pw_qpolynomial_free(pwqp);
1834	return isl_stat_error;
1835	}
1836
1837	__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1838	__isl_take isl_union_pw_qpolynomial_fold *upwf,
1839	__isl_take isl_union_pw_qpolynomial *upwqp)
1840	{
1841	upwf = isl_union_pw_qpolynomial_fold_align_params(u: upwf,
1842	model: isl_union_pw_qpolynomial_get_space(upwqp));
1843	upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1844	model: isl_union_pw_qpolynomial_fold_get_space(u: upwf));
1845
1846	upwf = isl_union_pw_qpolynomial_fold_cow(u: upwf);
1847	if (!upwf || !upwqp)
1848	goto error;
1849
1850	if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, fn: &add_pwqp,
1851	user: &upwf) < 0)
1852	goto error;
1853
1854	isl_union_pw_qpolynomial_free(upwqp);
1855
1856	return upwf;
1857	error:
1858	isl_union_pw_qpolynomial_fold_free(u: upwf);
1859	isl_union_pw_qpolynomial_free(upwqp);
1860	return NULL;
1861	}
1862
1863	static isl_bool join_compatible(__isl_keep isl_space *space1,
1864	__isl_keep isl_space *space2)
1865	{
1866	isl_bool m;
1867	m = isl_space_has_equal_params(space1, space2);
1868	if (m < 0 || !m)
1869	return m;
1870	return isl_space_tuple_is_equal(space1, type1: isl_dim_out,
1871	space2, type2: isl_dim_in);
1872	}
1873
1874	/* Compute the intersection of the range of the map and the domain
1875	* of the piecewise quasipolynomial reduction and then compute a bound
1876	* on the associated quasipolynomial reduction over all elements
1877	* in this intersection.
1878	*
1879	* We first introduce some unconstrained dimensions in the
1880	* piecewise quasipolynomial, intersect the resulting domain
1881	* with the wrapped map and the compute the sum.
1882	*/
1883	__isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1884	__isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1885	isl_bool *tight)
1886	{
1887	isl_ctx *ctx;
1888	isl_set *dom;
1889	isl_space *map_space;
1890	isl_space *pwf_space;
1891	isl_size n_in;
1892	isl_bool ok;
1893
1894	ctx = isl_map_get_ctx(map);
1895	if (!ctx)
1896	goto error;
1897
1898	map_space = isl_map_get_space(map);
1899	pwf_space = isl_pw_qpolynomial_fold_get_space(pw: pwf);
1900	ok = join_compatible(space1: map_space, space2: pwf_space);
1901	isl_space_free(space: map_space);
1902	isl_space_free(space: pwf_space);
1903	if (ok < 0)
1904	goto error;
1905	if (!ok)
1906	isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1907	goto error);
1908
1909	n_in = isl_map_dim(map, type: isl_dim_in);
1910	if (n_in < 0)
1911	goto error;
1912	pwf = isl_pw_qpolynomial_fold_insert_dims(pw: pwf, type: isl_dim_in, first: 0, n: n_in);
1913
1914	dom = isl_map_wrap(map);
1915	pwf = isl_pw_qpolynomial_fold_reset_domain_space(pw: pwf,
1916	domain: isl_set_get_space(set: dom));
1917
1918	pwf = isl_pw_qpolynomial_fold_intersect_domain(pw: pwf, context: dom);
1919	pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1920
1921	return pwf;
1922	error:
1923	isl_map_free(map);
1924	isl_pw_qpolynomial_fold_free(pw: pwf);
1925	return NULL;
1926	}
1927
1928	__isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1929	__isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1930	isl_bool *tight)
1931	{
1932	return isl_map_apply_pw_qpolynomial_fold(map: set, pwf, tight);
1933	}
1934
1935	struct isl_apply_fold_data {
1936	isl_union_pw_qpolynomial_fold *upwf;
1937	isl_union_pw_qpolynomial_fold *res;
1938	isl_map *map;
1939	isl_bool tight;
1940	};
1941
1942	static isl_stat pw_qpolynomial_fold_apply(
1943	__isl_take isl_pw_qpolynomial_fold *pwf, void *user)
1944	{
1945	isl_space *map_dim;
1946	isl_space *pwf_dim;
1947	struct isl_apply_fold_data *data = user;
1948	isl_bool ok;
1949
1950	map_dim = isl_map_get_space(map: data->map);
1951	pwf_dim = isl_pw_qpolynomial_fold_get_space(pw: pwf);
1952	ok = join_compatible(space1: map_dim, space2: pwf_dim);
1953	isl_space_free(space: map_dim);
1954	isl_space_free(space: pwf_dim);
1955
1956	if (ok < 0)
1957	return isl_stat_error;
1958	if (ok) {
1959	pwf = isl_map_apply_pw_qpolynomial_fold(map: isl_map_copy(map: data->map),
1960	pwf, tight: data->tight ? &data->tight : NULL);
1961	data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1962	u: data->res, part: pwf);
1963	} else
1964	isl_pw_qpolynomial_fold_free(pw: pwf);
1965
1966	return isl_stat_ok;
1967	}
1968
1969	static isl_stat map_apply(__isl_take isl_map *map, void *user)
1970	{
1971	struct isl_apply_fold_data *data = user;
1972	isl_stat r;
1973
1974	data->map = map;
1975	r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1976	u: data->upwf, fn: &pw_qpolynomial_fold_apply, user: data);
1977
1978	isl_map_free(map);
1979	return r;
1980	}
1981
1982	__isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1983	__isl_take isl_union_map *umap,
1984	__isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight)
1985	{
1986	isl_space *space;
1987	enum isl_fold type;
1988	struct isl_apply_fold_data data;
1989
1990	upwf = isl_union_pw_qpolynomial_fold_align_params(u: upwf,
1991	model: isl_union_map_get_space(umap));
1992	umap = isl_union_map_align_params(umap,
1993	model: isl_union_pw_qpolynomial_fold_get_space(u: upwf));
1994
1995	data.upwf = upwf;
1996	data.tight = tight ? isl_bool_true : isl_bool_false;
1997	space = isl_union_pw_qpolynomial_fold_get_space(u: upwf);
1998	type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1999	data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
2000	if (isl_union_map_foreach_map(umap, fn: &map_apply, user: &data) < 0)
2001	goto error;
2002
2003	isl_union_map_free(umap);
2004	isl_union_pw_qpolynomial_fold_free(u: upwf);
2005
2006	if (tight)
2007	*tight = data.tight;
2008
2009	return data.res;
2010	error:
2011	isl_union_map_free(umap);
2012	isl_union_pw_qpolynomial_fold_free(u: upwf);
2013	isl_union_pw_qpolynomial_fold_free(u: data.res);
2014	return NULL;
2015	}
2016
2017	__isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
2018	__isl_take isl_union_set *uset,
2019	__isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight)
2020	{
2021	return isl_union_map_apply_union_pw_qpolynomial_fold(umap: uset, upwf, tight);
2022	}
2023
2024	/* isl_qpolynomial_list_map callback for calling
2025	* isl_qpolynomial_realign_domain on "qp".
2026	*/
2027	static __isl_give isl_qpolynomial *realign_domain(
2028	__isl_take isl_qpolynomial *qp, void *user)
2029	{
2030	isl_reordering *r = user;
2031
2032	qp = isl_qpolynomial_realign_domain(qp, r: isl_reordering_copy(exp: r));
2033	return qp;
2034	}
2035
2036	/* Reorder the dimension of "fold" according to the given reordering.
2037	*/
2038	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
2039	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
2040	{
2041	isl_space *space;
2042	isl_qpolynomial_list *list;
2043
2044	list = isl_qpolynomial_fold_take_list(fold);
2045	list = isl_qpolynomial_list_map(list, fn: &realign_domain, user: r);
2046	fold = isl_qpolynomial_fold_restore_list(fold, list);
2047
2048	space = isl_reordering_get_space(r);
2049	fold = isl_qpolynomial_fold_reset_domain_space(fold, space);
2050
2051	isl_reordering_free(exp: r);
2052
2053	return fold;
2054	}
2055
2056	/* isl_qpolynomial_list_map callback for calling
2057	* isl_qpolynomial_mul_isl_int on "qp".
2058	*/
2059	static __isl_give isl_qpolynomial *mul_int(__isl_take isl_qpolynomial *qp,
2060	void *user)
2061	{
2062	isl_int *v = user;
2063
2064	qp = isl_qpolynomial_mul_isl_int(qp, v: *v);
2065	return qp;
2066	}
2067
2068	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
2069	__isl_take isl_qpolynomial_fold *fold, isl_int v)
2070	{
2071	isl_qpolynomial_list *list;
2072
2073	if (isl_int_is_one(v))
2074	return fold;
2075	if (fold && isl_int_is_zero(v)) {
2076	isl_qpolynomial_fold *zero;
2077	isl_space *space = isl_space_copy(space: fold->dim);
2078	zero = isl_qpolynomial_fold_empty(type: fold->type, space);
2079	isl_qpolynomial_fold_free(fold);
2080	return zero;
2081	}
2082
2083	fold = isl_qpolynomial_fold_cow(fold);
2084	if (!fold)
2085	return NULL;
2086
2087	if (isl_int_is_neg(v))
2088	fold->type = isl_fold_type_negate(type: fold->type);
2089
2090	list = isl_qpolynomial_fold_take_list(fold);
2091	list = isl_qpolynomial_list_map(list, fn: &mul_int, user: &v);
2092	fold = isl_qpolynomial_fold_restore_list(fold, list);
2093
2094	return fold;
2095	}
2096
2097	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
2098	__isl_take isl_qpolynomial_fold *fold, isl_int v)
2099	{
2100	return isl_qpolynomial_fold_mul_isl_int(fold, v);
2101	}
2102
2103	/* isl_qpolynomial_list_map callback for calling
2104	* isl_qpolynomial_scale_val on "qp".
2105	*/
2106	static __isl_give isl_qpolynomial *scale_val(__isl_take isl_qpolynomial *qp,
2107	void *user)
2108	{
2109	isl_val *v = user;
2110
2111	qp = isl_qpolynomial_scale_val(qp, v: isl_val_copy(v));
2112	return qp;
2113	}
2114
2115	/* Multiply "fold" by "v".
2116	*/
2117	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val(
2118	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
2119	{
2120	isl_qpolynomial_list *list;
2121
2122	if (!fold || !v)
2123	goto error;
2124
2125	if (isl_val_is_one(v)) {
2126	isl_val_free(v);
2127	return fold;
2128	}
2129	if (isl_val_is_zero(v)) {
2130	isl_qpolynomial_fold *zero;
2131	isl_space *space = isl_qpolynomial_fold_get_domain_space(fold);
2132	zero = isl_qpolynomial_fold_empty(type: fold->type, space);
2133	isl_qpolynomial_fold_free(fold);
2134	isl_val_free(v);
2135	return zero;
2136	}
2137	if (!isl_val_is_rat(v))
2138	isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
2139	"expecting rational factor", goto error);
2140
2141	fold = isl_qpolynomial_fold_cow(fold);
2142	if (!fold)
2143	goto error;
2144
2145	if (isl_val_is_neg(v))
2146	fold->type = isl_fold_type_negate(type: fold->type);
2147
2148	list = isl_qpolynomial_fold_take_list(fold);
2149	list = isl_qpolynomial_list_map(list, fn: &scale_val, user: v);
2150	fold = isl_qpolynomial_fold_restore_list(fold, list);
2151
2152	isl_val_free(v);
2153	return fold;
2154	error:
2155	isl_val_free(v);
2156	isl_qpolynomial_fold_free(fold);
2157	return NULL;
2158	}
2159
2160	/* Divide "fold" by "v".
2161	*/
2162	__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val(
2163	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v)
2164	{
2165	if (!fold || !v)
2166	goto error;
2167
2168	if (isl_val_is_one(v)) {
2169	isl_val_free(v);
2170	return fold;
2171	}
2172	if (!isl_val_is_rat(v))
2173	isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid,
2174	"expecting rational factor", goto error);
2175	if (isl_val_is_zero(v))
2176	isl_die(isl_val_get_ctx(v), isl_error_invalid,
2177	"cannot scale down by zero", goto error);
2178
2179	return isl_qpolynomial_fold_scale_val(fold, v: isl_val_inv(v));
2180	error:
2181	isl_val_free(v);
2182	isl_qpolynomial_fold_free(fold);
2183	return NULL;
2184	}
2185