1/*
2 * Copyright 2010      INRIA Saclay
3 * Copyright 2012      Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
9 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 */
12
13/* Function for computing the lexicographic optimum of a map
14 * in the form of either an isl_map or an isl_pw_multi_aff.
15 */
16
17#define xSF(TYPE,SUFFIX) TYPE ## SUFFIX
18#define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX)
19
20/* Given a basic map "bmap", compute the lexicographically minimal
21 * (or maximal) image element for each domain element in dom.
22 * Set *empty to those elements in dom that do not have an image element.
23 *
24 * We first make sure the basic sets in dom are disjoint and then
25 * simply collect the results over each of the basic sets separately.
26 * We could probably improve the efficiency a bit by moving the union
27 * domain down into the parametric integer programming.
28 */
29static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)(
30	__isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
31	__isl_give isl_set **empty, int max)
32{
33	int i;
34	TYPE *res;
35
36	dom = isl_set_make_disjoint(dom);
37	if (!dom)
38		goto error;
39
40	if (isl_set_plain_is_empty(dom)) {
41		isl_space *space = isl_basic_map_get_space(bmap);
42		if (empty)
43			*empty = dom;
44		else
45			isl_set_free(dom);
46		isl_basic_map_free(bmap);
47		return EMPTY(space);
48	}
49
50	res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap),
51			isl_basic_set_copy(dom->p[0]), empty, max);
52
53	for (i = 1; i < dom->n; ++i) {
54		TYPE *res_i;
55		isl_set *empty_i;
56
57		res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)(
58				isl_basic_map_copy(bmap),
59				isl_basic_set_copy(dom->p[i]), &empty_i, max);
60
61		res = ADD(res, res_i);
62		*empty = isl_set_union_disjoint(*empty, empty_i);
63	}
64
65	isl_set_free(dom);
66	isl_basic_map_free(bmap);
67	return res;
68error:
69	*empty = NULL;
70	isl_set_free(dom);
71	isl_basic_map_free(bmap);
72	return NULL;
73}
74
75static __isl_give TYPE *SF(isl_map_partial_lexopt_aligned,SUFFIX)(
76	__isl_take isl_map *map, __isl_take isl_set *dom,
77	__isl_give isl_set **empty, int max);
78
79/* Given a map "map", compute the lexicographically minimal
80 * (or maximal) image element for each domain element in dom.
81 * Set *empty to those elements in dom that do not have an image element.
82 *
83 * Align parameters if needed and then call isl_map_partial_lexopt_aligned.
84 */
85static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)(
86	__isl_take isl_map *map, __isl_take isl_set *dom,
87	__isl_give isl_set **empty, int max)
88{
89	if (!map || !dom)
90		goto error;
91	if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param))
92		return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom,
93								empty, max);
94	if (!isl_space_has_named_params(map->dim) ||
95	    !isl_space_has_named_params(dom->dim))
96		isl_die(map->ctx, isl_error_invalid,
97			"unaligned unnamed parameters", goto error);
98	map = isl_map_align_params(map, isl_map_get_space(dom));
99	dom = isl_map_align_params(dom, isl_map_get_space(map));
100	return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty, max);
101error:
102	if (empty)
103		*empty = NULL;
104	isl_set_free(dom);
105	isl_map_free(map);
106	return NULL;
107}
108
109__isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, int max)
110{
111	isl_set *dom = NULL;
112	isl_space *dom_space;
113
114	if (!map)
115		goto error;
116	dom_space = isl_space_domain(isl_space_copy(map->dim));
117	dom = isl_set_universe(dom_space);
118	return SF(isl_map_partial_lexopt,SUFFIX)(map, dom, NULL, max);
119error:
120	isl_map_free(map);
121	return NULL;
122}
123
124__isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map)
125{
126	return SF(isl_map_lexopt,SUFFIX)(map, 0);
127}
128
129__isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map)
130{
131	return SF(isl_map_lexopt,SUFFIX)(map, 1);
132}
133
134__isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set)
135{
136	return SF(isl_map_lexmin,SUFFIX)(set);
137}
138
139__isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set)
140{
141	return SF(isl_map_lexmax,SUFFIX)(set);
142}
143