add isl_basic_set_sample_bounded
[isl.git] / isl_constraint.c
blob7383988094bb458ff4d9402a18d8134f5a59aa66
1 #include <isl_constraint.h>
2 #include "isl_map_private.h"
4 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
6 return isl_basic_map_dim(c->bmap, type);
9 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
11 struct isl_dim *dim = c->bmap->dim;
12 switch (type) {
13 case isl_dim_param: return 1;
14 case isl_dim_in: return 1 + dim->nparam;
15 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
16 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
20 static unsigned basic_set_offset(struct isl_basic_set *bset,
21 enum isl_dim_type type)
23 struct isl_dim *dim = bset->dim;
24 switch (type) {
25 case isl_dim_param: return 1;
26 case isl_dim_in: return 1 + dim->nparam;
27 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
28 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
32 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
33 isl_int **line)
35 struct isl_constraint *constraint;
37 if (!bmap || !line)
38 goto error;
40 constraint = isl_alloc_type(bmap->ctx, struct isl_constraint);
41 if (!constraint)
42 goto error;
44 constraint->ctx = bmap->ctx;
45 isl_ctx_ref(constraint->ctx);
46 constraint->ref = 1;
47 constraint->bmap = bmap;
48 constraint->line = line;
50 return constraint;
51 error:
52 isl_basic_map_free(bmap);
53 return NULL;
56 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
57 isl_int **line)
59 return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
62 struct isl_constraint *isl_equality_alloc(struct isl_dim *dim)
64 struct isl_basic_map *bmap;
66 if (!dim)
67 return NULL;
69 bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
70 if (!bmap)
71 return NULL;
73 isl_basic_map_alloc_equality(bmap);
74 isl_seq_clr(bmap->eq[0], 1 + isl_basic_map_total_dim(bmap));
75 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
78 struct isl_constraint *isl_inequality_alloc(struct isl_dim *dim)
80 struct isl_basic_map *bmap;
82 if (!dim)
83 return NULL;
85 bmap = isl_basic_map_alloc_dim(dim, 0, 0, 1);
86 if (!bmap)
87 return NULL;
89 isl_basic_map_alloc_inequality(bmap);
90 isl_seq_clr(bmap->ineq[0], 1 + isl_basic_map_total_dim(bmap));
91 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
94 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
96 if (!c)
97 return NULL;
99 return isl_basic_map_constraint(isl_basic_map_copy(c->bmap), c->line);
102 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
104 if (!c)
105 return NULL;
107 if (c->ref == 1)
108 return c;
109 c->ref--;
110 return isl_constraint_dup(c);
113 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
115 if (!constraint)
116 return NULL;
118 constraint->ref++;
119 return constraint;
122 struct isl_constraint *isl_constraint_free(struct isl_constraint *c)
124 if (!c)
125 return;
127 if (--c->ref > 0)
128 return;
130 isl_basic_map_free(c->bmap);
131 isl_ctx_deref(c->ctx);
132 free(c);
135 struct isl_constraint *isl_basic_set_first_constraint(
136 struct isl_basic_set *bset)
138 struct isl_constraint *c;
140 if (!bset)
141 return NULL;
143 if (bset->n_eq > 0)
144 return isl_basic_set_constraint(bset, &bset->eq[0]);
146 if (bset->n_ineq > 0)
147 return isl_basic_set_constraint(bset, &bset->ineq[0]);
149 isl_basic_set_free(bset);
150 return NULL;
153 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
155 c = isl_constraint_cow(c);
156 if (c->line >= c->bmap->eq) {
157 c->line++;
158 if (c->line < c->bmap->eq + c->bmap->n_eq)
159 return c;
160 c->line = c->bmap->ineq;
161 } else
162 c->line++;
163 if (c->line < c->bmap->ineq + c->bmap->n_ineq)
164 return c;
165 isl_constraint_free(c);
166 return NULL;
169 int isl_constraint_is_equal(struct isl_constraint *constraint1,
170 struct isl_constraint *constraint2)
172 if (!constraint1 || !constraint2)
173 return 0;
174 return constraint1->bmap == constraint2->bmap &&
175 constraint1->line == constraint2->line;
178 struct isl_basic_map *isl_basic_map_add_constraint(
179 struct isl_basic_map *bmap, struct isl_constraint *constraint)
181 if (!bmap || !constraint)
182 goto error;
184 isl_assert(constraint->ctx,
185 isl_dim_equal(bmap->dim, constraint->bmap->dim), goto error);
187 bmap = isl_basic_map_intersect(bmap,
188 isl_basic_map_copy(constraint->bmap));
189 isl_constraint_free(constraint);
190 return bmap;
191 error:
192 isl_basic_map_free(bmap);
193 isl_constraint_free(constraint);
194 return NULL;
197 struct isl_basic_set *isl_basic_set_add_constraint(
198 struct isl_basic_set *bset, struct isl_constraint *constraint)
200 return (struct isl_basic_set *)
201 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
202 constraint);
205 struct isl_constraint *isl_constraint_add_div(struct isl_constraint *constraint,
206 struct isl_div *div, int *pos)
208 if (!constraint || !div)
209 goto error;
211 isl_assert(constraint->ctx,
212 isl_dim_equal(div->bmap->dim, constraint->bmap->dim), goto error);
213 isl_assert(constraint->ctx,
214 constraint->bmap->n_eq + constraint->bmap->n_ineq == 1, goto error);
216 constraint->bmap = isl_basic_map_cow(constraint->bmap);
217 constraint->bmap = isl_basic_map_extend_dim(constraint->bmap,
218 isl_dim_copy(constraint->bmap->dim), 1, 0, 0);
219 if (!constraint->bmap)
220 goto error;
221 constraint->line = &constraint->bmap->eq[0];
222 *pos = isl_basic_map_alloc_div(constraint->bmap);
223 if (*pos < 0)
224 goto error;
225 isl_seq_cpy(constraint->bmap->div[*pos], div->line[0],
226 1 + 1 + isl_basic_map_total_dim(constraint->bmap));
227 isl_div_free(div);
228 return constraint;
229 error:
230 isl_constraint_free(constraint);
231 isl_div_free(div);
232 return NULL;
235 int isl_constraint_dim(struct isl_constraint *constraint,
236 enum isl_dim_type type)
238 if (!constraint)
239 return -1;
240 return n(constraint, type);
243 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
245 if (!constraint)
246 return;
247 isl_int_set(*v, constraint->line[0][0]);
250 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
251 enum isl_dim_type type, int pos, isl_int *v)
253 if (!constraint)
254 return;
256 isl_assert(constraint->ctx, pos < n(constraint, type), return);
257 isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
260 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
262 if (!constraint)
263 return NULL;
265 isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
266 return NULL);
267 return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
270 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
272 if (!constraint)
273 return;
274 isl_int_set(constraint->line[0][0], v);
277 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
278 enum isl_dim_type type, int pos, isl_int v)
280 if (!constraint)
281 return;
283 isl_assert(constraint->ctx, pos < n(constraint, type), return);
284 isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
287 void isl_constraint_clear(struct isl_constraint *constraint)
289 struct isl_basic_set *bset;
290 unsigned total;
292 if (!constraint)
293 return;
294 total = isl_basic_map_total_dim(constraint->bmap);
295 isl_seq_clr(constraint->line[0], 1 + total);
298 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
300 unsigned total;
302 if (!constraint)
303 return NULL;
305 isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
306 goto error);
307 isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
308 total = isl_basic_map_total_dim(constraint->bmap);
309 isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
310 isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
311 ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
312 return constraint;
313 error:
314 isl_constraint_free(constraint);
315 return NULL;
318 int isl_constraint_is_equality(struct isl_constraint *constraint)
320 if (!constraint)
321 return -1;
322 return constraint->line >= constraint->bmap->eq;
326 struct isl_basic_set *isl_basic_set_from_constraint(
327 struct isl_constraint *constraint)
329 int k;
330 struct isl_basic_set *constraint_bset, *bset;
331 isl_int *c;
332 unsigned dim;
333 unsigned nparam;
334 unsigned total;
336 if (!constraint)
337 return NULL;
339 isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
341 constraint_bset = (struct isl_basic_set *)constraint->bmap;
342 bset = isl_basic_set_universe_like(constraint_bset);
343 bset = isl_basic_set_align_divs(bset, constraint_bset);
344 nparam = isl_basic_set_n_param(bset);
345 dim = isl_basic_set_n_dim(bset);
346 bset = isl_basic_set_cow(bset);
347 bset = isl_basic_set_extend(bset, nparam, dim, 0, 1, 1);
348 if (isl_constraint_is_equality(constraint)) {
349 k = isl_basic_set_alloc_equality(bset);
350 if (k < 0)
351 goto error;
352 c = bset->eq[k];
354 else {
355 k = isl_basic_set_alloc_inequality(bset);
356 if (k < 0)
357 goto error;
358 c = bset->ineq[k];
360 total = isl_basic_set_total_dim(bset);
361 isl_seq_cpy(c, constraint->line[0], 1 + total);
362 isl_constraint_free(constraint);
363 return bset;
364 error:
365 isl_constraint_free(constraint);
366 isl_basic_set_free(bset);
367 return NULL;
370 int isl_basic_set_has_defining_equality(
371 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
372 struct isl_constraint **c)
374 int i;
375 unsigned offset;
376 unsigned total;
378 if (!bset)
379 return -1;
380 offset = basic_set_offset(bset, type);
381 total = isl_basic_set_total_dim(bset);
382 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
383 for (i = 0; i < bset->n_eq; ++i)
384 if (!isl_int_is_zero(bset->eq[i][offset + pos]) &&
385 isl_seq_first_non_zero(bset->eq[i]+offset+pos+1,
386 1+total-offset-pos-1) == -1) {
387 *c= isl_basic_set_constraint(isl_basic_set_copy(bset),
388 &bset->eq[i]);
389 return 1;
391 return 0;
394 int isl_basic_set_has_defining_inequalities(
395 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
396 struct isl_constraint **lower,
397 struct isl_constraint **upper)
399 int i, j;
400 unsigned offset;
401 unsigned total;
402 isl_int m;
403 isl_int **lower_line, **upper_line;
405 if (!bset)
406 return -1;
407 offset = basic_set_offset(bset, type);
408 total = isl_basic_set_total_dim(bset);
409 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
410 isl_int_init(m);
411 for (i = 0; i < bset->n_ineq; ++i) {
412 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
413 continue;
414 if (isl_int_is_one(bset->ineq[i][offset + pos]))
415 continue;
416 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
417 continue;
418 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
419 1+total-offset-pos-1) != -1)
420 continue;
421 for (j = i + 1; j < bset->n_ineq; ++j) {
422 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
423 total))
424 continue;
425 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
426 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
427 continue;
429 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
430 lower_line = &bset->ineq[i];
431 upper_line = &bset->ineq[j];
432 } else {
433 lower_line = &bset->ineq[j];
434 upper_line = &bset->ineq[i];
436 *lower = isl_basic_set_constraint(
437 isl_basic_set_copy(bset), lower_line);
438 *upper = isl_basic_set_constraint(
439 isl_basic_set_copy(bset), upper_line);
440 isl_int_clear(m);
441 return 1;
444 *lower = NULL;
445 *upper = NULL;
446 isl_int_clear(m);
447 return 0;