?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
generalize and export isl_map_to_basic_set
[isl.git] / isl_multi_templ.c
blob0596ebcaf3b0341a7c797f576c5b018198b4cd0d
1 /*
2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012-2013 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 */
10
11 #include <isl_space_private.h>
12 #include <isl/set.h>
13 #include <isl_reordering.h>
14
15 #define xCAT(A,B) A ## B
16 #define CAT(A,B) xCAT(A,B)
17 #undef EL
18 #define EL CAT(isl_,BASE)
19 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
20 #define FN(TYPE,NAME) xFN(TYPE,NAME)
21 #define xMULTI(BASE) isl_multi_ ## BASE
22 #define MULTI(BASE) xMULTI(BASE)
23 #define MULTI_NAME(BASE) "isl_multi_" #BASE
24 #define xLIST(EL) EL ## _list
25 #define LIST(EL) xLIST(EL)
26
27 isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
28 {
29 return multi ? isl_space_get_ctx(multi->space) : NULL;
30 }
31
32 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
33 {
34 return multi ? isl_space_copy(multi->space) : NULL;
35 }
36
37 __isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
38 __isl_keep MULTI(BASE) *multi)
39 {
40 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
41 }
42
43 __isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
44 {
45 isl_ctx *ctx;
46 int n;
47 MULTI(BASE) *multi;
48
49 if (!space)
50 return NULL;
51
52 ctx = isl_space_get_ctx(space);
53 n = isl_space_dim(space, isl_dim_out);
54 multi = isl_calloc(ctx, MULTI(BASE),
55 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
56 if (!multi)
57 goto error;
58
59 multi->space = space;
60 multi->n = n;
61 multi->ref = 1;
62 return multi;
63 error:
64 isl_space_free(space);
65 return NULL;
66 }
67
68 __isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
69 {
70 int i;
71 MULTI(BASE) *dup;
72
73 if (!multi)
74 return NULL;
75
76 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
77 if (!dup)
78 return NULL;
79
80 for (i = 0; i < multi->n; ++i)
81 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
82 FN(EL,copy)(multi->p[i]));
83
84 return dup;
85 }
86
87 __isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
88 {
89 if (!multi)
90 return NULL;
91
92 if (multi->ref == 1)
93 return multi;
94
95 multi->ref--;
96 return FN(MULTI(BASE),dup)(multi);
97 }
98
99 __isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
100 {
101 if (!multi)
102 return NULL;
103
104 multi->ref++;
105 return multi;
106 }
107
108 void *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
109 {
110 int i;
111
112 if (!multi)
113 return NULL;
114
115 if (--multi->ref > 0)
116 return NULL;
117
118 isl_space_free(multi->space);
119 for (i = 0; i < multi->n; ++i)
120 FN(EL,free)(multi->p[i]);
121 free(multi);
122
123 return NULL;
124 }
125
126 __isl_give MULTI(BASE) *FN(MULTI(BASE),insert_dims)(
127 __isl_take MULTI(BASE) *multi,
128 enum isl_dim_type type, unsigned first, unsigned n)
129 {
130 int i;
131
132 if (!multi)
133 return NULL;
134 if (type == isl_dim_out)
135 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
136 "cannot insert output/set dimensions",
137 return FN(MULTI(BASE),free)(multi));
138 if (n == 0 && !isl_space_is_named_or_nested(multi->space, type))
139 return multi;
140
141 multi = FN(MULTI(BASE),cow)(multi);
142 if (!multi)
143 return NULL;
144
145 multi->space = isl_space_insert_dims(multi->space, type, first, n);
146 if (!multi->space)
147 return FN(MULTI(BASE),free)(multi);
148
149 for (i = 0; i < multi->n; ++i) {
150 multi->p[i] = FN(EL,insert_dims)(multi->p[i], type, first, n);
151 if (!multi->p[i])
152 return FN(MULTI(BASE),free)(multi);
153 }
154
155 return multi;
156 }
157
158 __isl_give MULTI(BASE) *FN(MULTI(BASE),add_dims)(__isl_take MULTI(BASE) *multi,
159 enum isl_dim_type type, unsigned n)
160 {
161 unsigned pos;
162
163 pos = FN(MULTI(BASE),dim)(multi, type);
164
165 return FN(MULTI(BASE),insert_dims)(multi, type, pos, n);
166 }
167
168 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
169 enum isl_dim_type type)
170 {
171 return multi ? isl_space_dim(multi->space, type) : 0;
172 }
173
174 /* Return the position of the first dimension of "type" with id "id".
175 * Return -1 if there is no such dimension.
176 */
177 int FN(MULTI(BASE),find_dim_by_id)(__isl_keep MULTI(BASE) *multi,
178 enum isl_dim_type type, __isl_keep isl_id *id)
179 {
180 if (!multi)
181 return -1;
182 return isl_space_find_dim_by_id(multi->space, type, id);
183 }
184
185 /* Return the id of the given dimension.
186 */
187 __isl_give isl_id *FN(MULTI(BASE),get_dim_id)(__isl_keep MULTI(BASE) *multi,
188 enum isl_dim_type type, unsigned pos)
189 {
190 return multi ? isl_space_get_dim_id(multi->space, type, pos) : NULL;
191 }
192
193 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
194 __isl_take MULTI(BASE) *multi,
195 enum isl_dim_type type, unsigned pos, const char *s)
196 {
197 int i;
198
199 multi = FN(MULTI(BASE),cow)(multi);
200 if (!multi)
201 return NULL;
202
203 multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
204 if (!multi->space)
205 return FN(MULTI(BASE),free)(multi);
206
207 if (type == isl_dim_out)
208 return multi;
209 for (i = 0; i < multi->n; ++i) {
210 multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
211 if (!multi->p[i])
212 return FN(MULTI(BASE),free)(multi);
213 }
214
215 return multi;
216 }
217
218 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
219 enum isl_dim_type type)
220 {
221 return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
222 }
223
224 /* Does the specified tuple have an id?
225 */
226 int FN(MULTI(BASE),has_tuple_id)(__isl_keep MULTI(BASE) *multi,
227 enum isl_dim_type type)
228 {
229 return multi ? isl_space_has_tuple_id(multi->space, type) : -1;
230 }
231
232 /* Return the id of the specified tuple.
233 */
234 __isl_give isl_id *FN(MULTI(BASE),get_tuple_id)(__isl_keep MULTI(BASE) *multi,
235 enum isl_dim_type type)
236 {
237 return multi ? isl_space_get_tuple_id(multi->space, type) : NULL;
238 }
239
240 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
241 int pos)
242 {
243 isl_ctx *ctx;
244
245 if (!multi)
246 return NULL;
247 ctx = FN(MULTI(BASE),get_ctx)(multi);
248 if (pos < 0 || pos >= multi->n)
249 isl_die(ctx, isl_error_invalid,
250 "index out of bounds", return NULL);
251 return FN(EL,copy)(multi->p[pos]);
252 }
253
254 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
255 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
256 {
257 isl_space *multi_space = NULL;
258 isl_space *el_space = NULL;
259 int match;
260
261 multi = FN(MULTI(BASE),cow)(multi);
262 if (!multi || !el)
263 goto error;
264
265 multi_space = FN(MULTI(BASE),get_space)(multi);
266 match = FN(EL,matching_params)(el, multi_space);
267 if (match < 0)
268 goto error;
269 if (!match) {
270 multi = FN(MULTI(BASE),align_params)(multi,
271 FN(EL,get_space)(el));
272 isl_space_free(multi_space);
273 multi_space = FN(MULTI(BASE),get_space)(multi);
274 el = FN(EL,align_params)(el, isl_space_copy(multi_space));
275 }
276 if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
277 goto error;
278
279 if (pos < 0 || pos >= multi->n)
280 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
281 "index out of bounds", goto error);
282
283 FN(EL,free)(multi->p[pos]);
284 multi->p[pos] = el;
285
286 isl_space_free(multi_space);
287 isl_space_free(el_space);
288
289 return multi;
290 error:
291 FN(MULTI(BASE),free)(multi);
292 FN(EL,free)(el);
293 isl_space_free(multi_space);
294 isl_space_free(el_space);
295 return NULL;
296 }
297
298 /* Reset the space of "multi". This function is called from isl_pw_templ.c
299 * and doesn't know if the space of an element object is represented
300 * directly or through its domain. It therefore passes along both,
301 * which we pass along to the element function since we don't how
302 * that is represented either.
303 */
304 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
305 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
306 __isl_take isl_space *domain)
307 {
308 int i;
309
310 multi = FN(MULTI(BASE),cow)(multi);
311 if (!multi || !space || !domain)
312 goto error;
313
314 for (i = 0; i < multi->n; ++i) {
315 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
316 isl_space_copy(domain));
317 if (!multi->p[i])
318 goto error;
319 }
320 isl_space_free(domain);
321 isl_space_free(multi->space);
322 multi->space = space;
323
324 return multi;
325 error:
326 isl_space_free(domain);
327 isl_space_free(space);
328 FN(MULTI(BASE),free)(multi);
329 return NULL;
330 }
331
332 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
333 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
334 {
335 isl_space *space;
336
337 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
338 isl_space_copy(multi->space));
339 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
340 }
341
342 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
343 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
344 {
345 isl_space *domain;
346
347 domain = isl_space_domain(isl_space_copy(space));
348 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
349 }
350
351 /* Set the id of the given dimension of "multi" to "id".
352 */
353 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_id)(
354 __isl_take MULTI(BASE) *multi,
355 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
356 {
357 isl_space *space;
358
359 multi = FN(MULTI(BASE),cow)(multi);
360 if (!multi || !id)
361 goto error;
362
363 space = FN(MULTI(BASE),get_space)(multi);
364 space = isl_space_set_dim_id(space, type, pos, id);
365
366 return FN(MULTI(BASE),reset_space)(multi, space);
367 error:
368 isl_id_free(id);
369 FN(MULTI(BASE),free)(multi);
370 return NULL;
371 }
372
373 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
374 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
375 const char *s)
376 {
377 isl_space *space;
378
379 multi = FN(MULTI(BASE),cow)(multi);
380 if (!multi)
381 return NULL;
382
383 space = FN(MULTI(BASE),get_space)(multi);
384 space = isl_space_set_tuple_name(space, type, s);
385
386 return FN(MULTI(BASE),reset_space)(multi, space);
387 }
388
389 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
390 __isl_take MULTI(BASE) *multi, enum isl_dim_type type,
391 __isl_take isl_id *id)
392 {
393 isl_space *space;
394
395 multi = FN(MULTI(BASE),cow)(multi);
396 if (!multi)
397 return isl_id_free(id);
398
399 space = FN(MULTI(BASE),get_space)(multi);
400 space = isl_space_set_tuple_id(space, type, id);
401
402 return FN(MULTI(BASE),reset_space)(multi, space);
403 }
404
405 /* Drop the id on the specified tuple.
406 */
407 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_tuple_id)(
408 __isl_take MULTI(BASE) *multi, enum isl_dim_type type)
409 {
410 isl_space *space;
411
412 if (!multi)
413 return NULL;
414 if (!FN(MULTI(BASE),has_tuple_id)(multi, type))
415 return multi;
416
417 multi = FN(MULTI(BASE),cow)(multi);
418 if (!multi)
419 return NULL;
420
421 space = FN(MULTI(BASE),get_space)(multi);
422 space = isl_space_reset_tuple_id(space, type);
423
424 return FN(MULTI(BASE),reset_space)(multi, space);
425 }
426
427 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
428 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
429 {
430 int i;
431
432 multi = FN(MULTI(BASE),cow)(multi);
433 if (!multi || !exp)
434 goto error;
435
436 for (i = 0; i < multi->n; ++i) {
437 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
438 isl_reordering_copy(exp));
439 if (!multi->p[i])
440 goto error;
441 }
442
443 multi = FN(MULTI(BASE),reset_domain_space)(multi,
444 isl_space_copy(exp->dim));
445
446 isl_reordering_free(exp);
447 return multi;
448 error:
449 isl_reordering_free(exp);
450 FN(MULTI(BASE),free)(multi);
451 return NULL;
452 }
453
454 /* Align the parameters of "multi" to those of "model".
455 */
456 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
457 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
458 {
459 isl_ctx *ctx;
460
461 if (!multi || !model)
462 goto error;
463
464 ctx = isl_space_get_ctx(model);
465 if (!isl_space_has_named_params(model))
466 isl_die(ctx, isl_error_invalid,
467 "model has unnamed parameters", goto error);
468 if (!isl_space_has_named_params(multi->space))
469 isl_die(ctx, isl_error_invalid,
470 "input has unnamed parameters", goto error);
471 if (!isl_space_match(multi->space, isl_dim_param,
472 model, isl_dim_param)) {
473 isl_reordering *exp;
474
475 model = isl_space_params(model);
476 exp = isl_parameter_alignment_reordering(multi->space, model);
477 exp = isl_reordering_extend_space(exp,
478 FN(MULTI(BASE),get_domain_space)(multi));
479 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
480 }
481
482 isl_space_free(model);
483 return multi;
484 error:
485 isl_space_free(model);
486 FN(MULTI(BASE),free)(multi);
487 return NULL;
488 }
489
490 #if !defined(NO_GIST) || !defined(NO_INTERSECT_DOMAIN)
491 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
492 __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
493 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
494 __isl_take isl_set *set))
495 {
496 isl_ctx *ctx;
497
498 if (!multi || !set)
499 goto error;
500 if (isl_space_match(multi->space, isl_dim_param,
501 set->dim, isl_dim_param))
502 return fn(multi, set);
503 ctx = FN(MULTI(BASE),get_ctx)(multi);
504 if (!isl_space_has_named_params(multi->space) ||
505 !isl_space_has_named_params(set->dim))
506 isl_die(ctx, isl_error_invalid,
507 "unaligned unnamed parameters", goto error);
508 multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
509 set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
510 return fn(multi, set);
511 error:
512 FN(MULTI(BASE),free)(multi);
513 isl_set_free(set);
514 return NULL;
515 }
516 #endif
517
518 #ifndef NO_GIST
519 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
520 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
521 {
522 int i;
523
524 multi = FN(MULTI(BASE),cow)(multi);
525 if (!multi || !context)
526 goto error;
527
528 for (i = 0; i < multi->n; ++i) {
529 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
530 if (!multi->p[i])
531 goto error;
532 }
533
534 isl_set_free(context);
535 return multi;
536 error:
537 isl_set_free(context);
538 FN(MULTI(BASE),free)(multi);
539 return NULL;
540 }
541
542 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
543 __isl_take isl_set *context)
544 {
545 return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
546 &FN(MULTI(BASE),gist_aligned));
547 }
548
549 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
550 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
551 {
552 isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
553 isl_set *dom_context = isl_set_universe(space);
554 dom_context = isl_set_intersect_params(dom_context, context);
555 return FN(MULTI(BASE),gist)(multi, dom_context);
556 }
557 #endif
558
559 #ifndef NO_INTERSECT_DOMAIN
560 /* Transform the domain of "multi" by combining it with "domain"
561 * using "fn".
562 *
563 * The parameters of "multi" and "domain" are assumed to have been aligned.
564 */
565 __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_aligned)(
566 __isl_take MULTI(BASE) *multi, __isl_take isl_set *domain,
567 __isl_give EL *(*fn)(EL *el, __isl_take isl_set *set2))
568 {
569 int i;
570
571 if (!multi || !domain)
572 goto error;
573
574 if (multi->n == 0) {
575 isl_set_free(domain);
576 return multi;
577 }
578
579 multi = FN(MULTI(BASE),cow)(multi);
580 if (!multi)
581 goto error;
582
583 for (i = 0; i < multi->n; ++i) {
584 multi->p[i] = fn(multi->p[i], isl_set_copy(domain));
585 if (!multi->p[i])
586 goto error;
587 }
588
589 isl_set_free(domain);
590 return multi;
591 error:
592 isl_set_free(domain);
593 FN(MULTI(BASE),free)(multi);
594 return NULL;
595 }
596
597 /* Intersect the domain of "multi" with "domain".
598 *
599 * The parameters of "multi" and "domain" are assumed to have been aligned.
600 */
601 __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_domain_aligned)(
602 __isl_take MULTI(BASE) *multi, __isl_take isl_set *domain)
603 {
604 return FN(MULTI(BASE),intersect_aligned)(multi, domain,
605 &FN(EL,intersect_domain));
606 }
607
608 /* Intersect the domain of "multi" with "domain".
609 */
610 __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_domain)(
611 __isl_take MULTI(BASE) *multi, __isl_take isl_set *domain)
612 {
613 return FN(MULTI(BASE),align_params_multi_set_and)(multi, domain,
614 &FN(MULTI(BASE),intersect_domain_aligned));
615 }
616
617 /* Intersect the parameter domain of "multi" with "domain".
618 *
619 * The parameters of "multi" and "domain" are assumed to have been aligned.
620 */
621 __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_params_aligned)(
622 __isl_take MULTI(BASE) *multi, __isl_take isl_set *domain)
623 {
624 return FN(MULTI(BASE),intersect_aligned)(multi, domain,
625 &FN(EL,intersect_params));
626 }
627
628 /* Intersect the parameter domain of "multi" with "domain".
629 */
630 __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_params)(
631 __isl_take MULTI(BASE) *multi, __isl_take isl_set *domain)
632 {
633 return FN(MULTI(BASE),align_params_multi_set_and)(multi, domain,
634 &FN(MULTI(BASE),intersect_params_aligned));
635 }
636 #endif
637
638 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
639 __isl_take isl_space *space, __isl_take LIST(EL) *list)
640 {
641 int i;
642 int n;
643 isl_ctx *ctx;
644 MULTI(BASE) *multi;
645
646 if (!space || !list)
647 goto error;
648
649 ctx = isl_space_get_ctx(space);
650 n = FN(FN(LIST(EL),n),BASE)(list);
651 if (n != isl_space_dim(space, isl_dim_out))
652 isl_die(ctx, isl_error_invalid,
653 "invalid number of elements in list", goto error);
654
655 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
656 for (i = 0; i < n; ++i) {
657 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
658 FN(FN(LIST(EL),get),BASE)(list, i));
659 }
660
661 isl_space_free(space);
662 FN(LIST(EL),free)(list);
663 return multi;
664 error:
665 isl_space_free(space);
666 FN(LIST(EL),free)(list);
667 return NULL;
668 }
669
670 #ifndef NO_IDENTITY
671 /* Create a multi expression in the given space that maps each
672 * input dimension to the corresponding output dimension.
673 */
674 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
675 {
676 int i, n;
677 isl_local_space *ls;
678 MULTI(BASE) *multi;
679
680 if (!space)
681 return NULL;
682
683 if (isl_space_is_set(space))
684 isl_die(isl_space_get_ctx(space), isl_error_invalid,
685 "expecting map space", goto error);
686
687 n = isl_space_dim(space, isl_dim_out);
688 if (n != isl_space_dim(space, isl_dim_in))
689 isl_die(isl_space_get_ctx(space), isl_error_invalid,
690 "number of input and output dimensions needs to be "
691 "the same", goto error);
692
693 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
694
695 if (!n) {
696 isl_space_free(space);
697 return multi;
698 }
699
700 space = isl_space_domain(space);
701 ls = isl_local_space_from_space(space);
702
703 for (i = 0; i < n; ++i) {
704 EL *el;
705 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
706 isl_dim_set, i);
707 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
708 }
709
710 isl_local_space_free(ls);
711
712 return multi;
713 error:
714 isl_space_free(space);
715 return NULL;
716 }
717 #endif
718
719 /* Construct a multi expression in the given space with value zero in
720 * each of the output dimensions.
721 */
722 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
723 {
724 int n;
725 MULTI(BASE) *multi;
726
727 if (!space)
728 return NULL;
729
730 n = isl_space_dim(space , isl_dim_out);
731 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
732
733 if (!n)
734 isl_space_free(space);
735 else {
736 int i;
737 isl_local_space *ls;
738 EL *el;
739
740 space = isl_space_domain(space);
741 ls = isl_local_space_from_space(space);
742 el = FN(EL,zero_on_domain)(ls);
743
744 for (i = 0; i < n; ++i)
745 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
746 FN(EL,copy)(el));
747
748 FN(EL,free)(el);
749 }
750
751 return multi;
752 }
753
754 #ifndef NO_FROM_BASE
755 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
756 {
757 MULTI(BASE) *multi;
758
759 multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
760 multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
761
762 return multi;
763 }
764 #endif
765
766 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
767 __isl_take MULTI(BASE) *multi,
768 enum isl_dim_type type, unsigned first, unsigned n)
769 {
770 int i;
771 unsigned dim;
772
773 multi = FN(MULTI(BASE),cow)(multi);
774 if (!multi)
775 return NULL;
776
777 dim = FN(MULTI(BASE),dim)(multi, type);
778 if (first + n > dim || first + n < first)
779 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
780 "index out of bounds",
781 return FN(MULTI(BASE),cow)(multi));
782
783 multi->space = isl_space_drop_dims(multi->space, type, first, n);
784 if (!multi->space)
785 return FN(MULTI(BASE),cow)(multi);
786
787 if (type == isl_dim_out) {
788 for (i = 0; i < n; ++i)
789 FN(EL,free)(multi->p[first + i]);
790 for (i = first; i + n < multi->n; ++i)
791 multi->p[i] = multi->p[i + n];
792 multi->n -= n;
793
794 return multi;
795 }
796
797 for (i = 0; i < multi->n; ++i) {
798 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
799 if (!multi->p[i])
800 return FN(MULTI(BASE),cow)(multi);
801 }
802
803 return multi;
804 }
805
806 /* Align the parameters of "multi1" and "multi2" (if needed) and call "fn".
807 */
808 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_multi_and)(
809 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
810 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi1,
811 __isl_take MULTI(BASE) *multi2))
812 {
813 isl_ctx *ctx;
814
815 if (!multi1 || !multi2)
816 goto error;
817 if (isl_space_match(multi1->space, isl_dim_param,
818 multi2->space, isl_dim_param))
819 return fn(multi1, multi2);
820 ctx = FN(MULTI(BASE),get_ctx)(multi1);
821 if (!isl_space_has_named_params(multi1->space) ||
822 !isl_space_has_named_params(multi2->space))
823 isl_die(ctx, isl_error_invalid,
824 "unaligned unnamed parameters", goto error);
825 multi1 = FN(MULTI(BASE),align_params)(multi1,
826 FN(MULTI(BASE),get_space)(multi2));
827 multi2 = FN(MULTI(BASE),align_params)(multi2,
828 FN(MULTI(BASE),get_space)(multi1));
829 return fn(multi1, multi2);
830 error:
831 FN(MULTI(BASE),free)(multi1);
832 FN(MULTI(BASE),free)(multi2);
833 return NULL;
834 }
835
836 /* Given two MULTI(BASE)s A -> B and C -> D,
837 * construct a MULTI(BASE) (A * C) -> (B, D).
838 *
839 * The parameters are assumed to have been aligned.
840 */
841 static __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product_aligned)(
842 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
843 {
844 int i, n1, n2;
845 EL *el;
846 isl_space *space;
847 MULTI(BASE) *res;
848
849 if (!multi1 || !multi2)
850 goto error;
851
852 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
853 FN(MULTI(BASE),get_space)(multi2));
854 res = FN(MULTI(BASE),alloc)(space);
855
856 n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
857 n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
858
859 for (i = 0; i < n1; ++i) {
860 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
861 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
862 }
863
864 for (i = 0; i < n2; ++i) {
865 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
866 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
867 }
868
869 FN(MULTI(BASE),free)(multi1);
870 FN(MULTI(BASE),free)(multi2);
871 return res;
872 error:
873 FN(MULTI(BASE),free)(multi1);
874 FN(MULTI(BASE),free)(multi2);
875 return NULL;
876 }
877
878 /* Given two MULTI(BASE)s A -> B and C -> D,
879 * construct a MULTI(BASE) (A * C) -> (B, D).
880 */
881 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
882 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
883 {
884 return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
885 &FN(MULTI(BASE),range_product_aligned));
886 }
887
888 /* Given two MULTI(BASE)s A -> B and C -> D,
889 * construct a MULTI(BASE) [A -> C] -> [B -> D].
890 *
891 * The parameters are assumed to have been aligned.
892 */
893 __isl_give MULTI(BASE) *FN(MULTI(BASE),product_aligned)(
894 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
895 {
896 int i;
897 EL *el;
898 isl_space *space;
899 MULTI(BASE) *res;
900 int in1, in2, out1, out2;
901
902 in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
903 in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
904 out1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
905 out2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
906 space = isl_space_product(FN(MULTI(BASE),get_space)(multi1),
907 FN(MULTI(BASE),get_space)(multi2));
908 res = FN(MULTI(BASE),alloc)(isl_space_copy(space));
909 space = isl_space_domain(space);
910
911 for (i = 0; i < out1; ++i) {
912 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
913 el = FN(EL,insert_dims)(el, isl_dim_in, in1, in2);
914 el = FN(EL,reset_domain_space)(el, isl_space_copy(space));
915 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
916 }
917
918 for (i = 0; i < out2; ++i) {
919 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
920 el = FN(EL,insert_dims)(el, isl_dim_in, 0, in1);
921 el = FN(EL,reset_domain_space)(el, isl_space_copy(space));
922 res = FN(FN(MULTI(BASE),set),BASE)(res, out1 + i, el);
923 }
924
925 isl_space_free(space);
926 FN(MULTI(BASE),free)(multi1);
927 FN(MULTI(BASE),free)(multi2);
928 return res;
929 }
930
931 /* Given two MULTI(BASE)s A -> B and C -> D,
932 * construct a MULTI(BASE) [A -> C] -> [B -> D].
933 */
934 __isl_give MULTI(BASE) *FN(MULTI(BASE),product)(
935 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
936 {
937 return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
938 &FN(MULTI(BASE),product_aligned));
939 }
940
941 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
942 __isl_take MULTI(BASE) *multi)
943 {
944 if (!multi)
945 return NULL;
946
947 if (!multi->space->nested[1])
948 return multi;
949
950 multi = FN(MULTI(BASE),cow)(multi);
951 if (!multi)
952 return NULL;
953
954 multi->space = isl_space_flatten_range(multi->space);
955 if (!multi->space)
956 return FN(MULTI(BASE),free)(multi);
957
958 return multi;
959 }
960
961 /* Given two MULTI(BASE)s A -> B and C -> D,
962 * construct a MULTI(BASE) (A * C) -> [B -> D].
963 */
964 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
965 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
966 {
967 MULTI(BASE) *multi;
968
969 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
970 multi = FN(MULTI(BASE),flatten_range)(multi);
971 return multi;
972 }
973
974 /* Given two multi expressions, "multi1"
975 *
976 * [A] -> [B1 B2]
977 *
978 * where B2 starts at position "pos", and "multi2"
979 *
980 * [A] -> [D]
981 *
982 * return the multi expression
983 *
984 * [A] -> [B1 D B2]
985 */
986 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
987 __isl_take MULTI(BASE) *multi1, unsigned pos,
988 __isl_take MULTI(BASE) *multi2)
989 {
990 MULTI(BASE) *res;
991 unsigned dim;
992
993 if (!multi1 || !multi2)
994 goto error;
995
996 dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
997 if (pos > dim)
998 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
999 "index out of bounds", goto error);
1000
1001 res = FN(MULTI(BASE),copy)(multi1);
1002 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
1003 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
1004
1005 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
1006 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
1007
1008 return res;
1009 error:
1010 FN(MULTI(BASE),free)(multi1);
1011 FN(MULTI(BASE),free)(multi2);
1012 return NULL;
1013 }
1014
1015 /* Given two multi expressions, "multi1"
1016 *
1017 * [A1 A2] -> [B1 B2]
1018 *
1019 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
1020 * and "multi2"
1021 *
1022 * [C] -> [D]
1023 *
1024 * return the multi expression
1025 *
1026 * [A1 C A2] -> [B1 D B2]
1027 *
1028 * We first insert input dimensions to obtain
1029 *
1030 * [A1 C A2] -> [B1 B2]
1031 *
1032 * and
1033 *
1034 * [A1 C A2] -> [D]
1035 *
1036 * and then apply range_splice.
1037 */
1038 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
1039 __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
1040 __isl_take MULTI(BASE) *multi2)
1041 {
1042 unsigned n_in1;
1043 unsigned n_in2;
1044
1045 if (!multi1 || !multi2)
1046 goto error;
1047
1048 n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
1049 if (in_pos > n_in1)
1050 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
1051 "index out of bounds", goto error);
1052
1053 n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
1054
1055 multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
1056 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
1057 n_in1 - in_pos);
1058 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
1059
1060 return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
1061 error:
1062 FN(MULTI(BASE),free)(multi1);
1063 FN(MULTI(BASE),free)(multi2);
1064 return NULL;
1065 }
1066
1067 /* This function is currently only used from isl_aff.c
1068 */
1069 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
1070 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
1071 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
1072 __attribute__ ((unused));
1073
1074 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
1075 * return the result.
1076 */
1077 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
1078 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
1079 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
1080 {
1081 int i;
1082 isl_ctx *ctx;
1083
1084 multi1 = FN(MULTI(BASE),cow)(multi1);
1085 if (!multi1 || !multi2)
1086 goto error;
1087
1088 ctx = FN(MULTI(BASE),get_ctx)(multi1);
1089 if (!isl_space_is_equal(multi1->space, multi2->space))
1090 isl_die(ctx, isl_error_invalid,
1091 "spaces don't match", goto error);
1092
1093 for (i = 0; i < multi1->n; ++i) {
1094 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
1095 if (!multi1->p[i])
1096 goto error;
1097 }
1098
1099 FN(MULTI(BASE),free)(multi2);
1100 return multi1;
1101 error:
1102 FN(MULTI(BASE),free)(multi1);
1103 FN(MULTI(BASE),free)(multi2);
1104 return NULL;
1105 }
1106
1107 /* Multiply the elements of "multi" by "v" and return the result.
1108 */
1109 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_val)(__isl_take MULTI(BASE) *multi,
1110 __isl_take isl_val *v)
1111 {
1112 int i;
1113
1114 if (!multi || !v)
1115 goto error;
1116
1117 if (isl_val_is_one(v)) {
1118 isl_val_free(v);
1119 return multi;
1120 }
1121
1122 if (!isl_val_is_rat(v))
1123 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1124 "expecting rational factor", goto error);
1125
1126 multi = FN(MULTI(BASE),cow)(multi);
1127 if (!multi)
1128 return NULL;
1129
1130 for (i = 0; i < multi->n; ++i) {
1131 multi->p[i] = FN(EL,scale_val)(multi->p[i], isl_val_copy(v));
1132 if (!multi->p[i])
1133 goto error;
1134 }
1135
1136 isl_val_free(v);
1137 return multi;
1138 error:
1139 isl_val_free(v);
1140 return FN(MULTI(BASE),free)(multi);
1141 }
1142
1143 /* Multiply the elements of "multi" by the corresponding element of "mv"
1144 * and return the result.
1145 */
1146 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_multi_val)(
1147 __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
1148 {
1149 int i;
1150
1151 if (!multi || !mv)
1152 goto error;
1153
1154 if (!isl_space_tuple_match(multi->space, isl_dim_out,
1155 mv->space, isl_dim_set))
1156 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
1157 "spaces don't match", goto error);
1158
1159 multi = FN(MULTI(BASE),cow)(multi);
1160 if (!multi)
1161 return NULL;
1162
1163 for (i = 0; i < multi->n; ++i) {
1164 isl_val *v;
1165
1166 v = isl_multi_val_get_val(mv, i);
1167 multi->p[i] = FN(EL,scale_val)(multi->p[i], v);
1168 if (!multi->p[i])
1169 goto error;
1170 }
1171
1172 isl_multi_val_free(mv);
1173 return multi;
1174 error:
1175 isl_multi_val_free(mv);
1176 return FN(MULTI(BASE),free)(multi);
1177 }
1178
1179 /* Divide the elements of "multi" by the corresponding element of "mv"
1180 * and return the result.
1181 */
1182 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_down_multi_val)(
1183 __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
1184 {
1185 int i;
1186
1187 if (!multi || !mv)
1188 goto error;
1189
1190 if (!isl_space_tuple_match(multi->space, isl_dim_out,
1191 mv->space, isl_dim_set))
1192 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
1193 "spaces don't match", goto error);
1194
1195 multi = FN(MULTI(BASE),cow)(multi);
1196 if (!multi)
1197 return NULL;
1198
1199 for (i = 0; i < multi->n; ++i) {
1200 isl_val *v;
1201
1202 v = isl_multi_val_get_val(mv, i);
1203 multi->p[i] = FN(EL,scale_down_val)(multi->p[i], v);
1204 if (!multi->p[i])
1205 goto error;
1206 }
1207
1208 isl_multi_val_free(mv);
1209 return multi;
1210 error:
1211 isl_multi_val_free(mv);
1212 return FN(MULTI(BASE),free)(multi);
1213 }
1214
1215 #ifndef NO_MOVE_DIMS
1216 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "multi"
1217 * to dimensions of "dst_type" at "dst_pos".
1218 *
1219 * We only support moving input dimensions to parameters and vice versa.
1220 */
1221 __isl_give MULTI(BASE) *FN(MULTI(BASE),move_dims)(__isl_take MULTI(BASE) *multi,
1222 enum isl_dim_type dst_type, unsigned dst_pos,
1223 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1224 {
1225 int i;
1226
1227 if (!multi)
1228 return NULL;
1229
1230 if (n == 0 &&
1231 !isl_space_is_named_or_nested(multi->space, src_type) &&
1232 !isl_space_is_named_or_nested(multi->space, dst_type))
1233 return multi;
1234
1235 if (dst_type == isl_dim_out || src_type == isl_dim_out)
1236 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
1237 "cannot move output/set dimension",
1238 return FN(MULTI(BASE),free)(multi));
1239 if (dst_type == isl_dim_div || src_type == isl_dim_div)
1240 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
1241 "cannot move divs",
1242 return FN(MULTI(BASE),free)(multi));
1243 if (src_pos + n > isl_space_dim(multi->space, src_type))
1244 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
1245 "range out of bounds",
1246 return FN(MULTI(BASE),free)(multi));
1247 if (dst_type == src_type)
1248 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_unsupported,
1249 "moving dims within the same type not supported",
1250 return FN(MULTI(BASE),free)(multi));
1251
1252 multi = FN(MULTI(BASE),cow)(multi);
1253 if (!multi)
1254 return NULL;
1255
1256 multi->space = isl_space_move_dims(multi->space, dst_type, dst_pos,
1257 src_type, src_pos, n);
1258 if (!multi->space)
1259 return FN(MULTI(BASE),free)(multi);
1260
1261 for (i = 0; i < multi->n; ++i) {
1262 multi->p[i] = FN(EL,move_dims)(multi->p[i], dst_type, dst_pos,
1263 src_type, src_pos, n);
1264 if (!multi->p[i])
1265 return FN(MULTI(BASE),free)(multi);
1266 }
1267
1268 return multi;
1269 }
1270 #endif
1271
1272 /* Convert a multiple expression defined over a parameter domain
1273 * into one that is defined over a zero-dimensional set.
1274 */
1275 __isl_give MULTI(BASE) *FN(MULTI(BASE),from_range)(
1276 __isl_take MULTI(BASE) *multi)
1277 {
1278 isl_space *space;
1279
1280 if (!multi)
1281 return NULL;
1282 if (!isl_space_is_set(multi->space))
1283 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
1284 "not living in a set space",
1285 return FN(MULTI(BASE),free)(multi));
1286
1287 space = FN(MULTI(BASE),get_space)(multi);
1288 space = isl_space_from_range(space);
1289 multi = FN(MULTI(BASE),reset_space)(multi, space);
1290
1291 return multi;
1292 }
1293
1294 /* Are "multi1" and "multi2" obviously equal?
1295 */
1296 int FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
1297 __isl_keep MULTI(BASE) *multi2)
1298 {
1299 int i;
1300 int equal;
1301
1302 if (!multi1 || !multi2)
1303 return -1;
1304 if (multi1->n != multi2->n)
1305 return 0;
1306 equal = isl_space_is_equal(multi1->space, multi2->space);
1307 if (equal < 0 || !equal)
1308 return equal;
1309
1310 for (i = 0; i < multi1->n; ++i) {
1311 equal = FN(EL,plain_is_equal)(multi1->p[i], multi2->p[i]);
1312 if (equal < 0 || !equal)
1313 return equal;
1314 }
1315
1316 return 1;
1317 }
1318
1319 #ifndef NO_DOMAIN
1320 /* Return the shared domain of the elements of "multi".
1321 */
1322 __isl_give isl_set *FN(MULTI(BASE),domain)(__isl_take MULTI(BASE) *multi)
1323 {
1324 int i;
1325 isl_set *dom;
1326
1327 if (!multi)
1328 return NULL;
1329
1330 dom = isl_set_universe(FN(MULTI(BASE),get_domain_space)(multi));
1331 for (i = 0; i < multi->n; ++i) {
1332 isl_set *dom_i;
1333
1334 dom_i = FN(EL,domain)(FN(FN(MULTI(BASE),get),BASE)(multi, i));
1335 dom = isl_set_intersect(dom, dom_i);
1336 }
1337
1338 FN(MULTI(BASE),free)(multi);
1339 return dom;
1340 }
1341 #endif
Integer set library