document isl_basic_map_set_tuple_name
[platform/upstream/isl.git] / doc / user.pod
1 =head1 Introduction
2
3 C<isl> is a thread-safe C library for manipulating
4 sets and relations of integer points bounded by affine constraints.
5 The descriptions of the sets and relations may involve
6 both parameters and existentially quantified variables.
7 All computations are performed in exact integer arithmetic
8 using C<GMP>.
9 The C<isl> library offers functionality that is similar
10 to that offered by the C<Omega> and C<Omega+> libraries,
11 but the underlying algorithms are in most cases completely different.
12
13 The library is by no means complete and some fairly basic
14 functionality is still missing.
15 Still, even in its current form, the library has been successfully
16 used as a backend polyhedral library for the polyhedral
17 scanner C<CLooG> and as part of an equivalence checker of
18 static affine programs.
19 For bug reports, feature requests and questions,
20 visit the the discussion group at
21 L<http://groups.google.com/group/isl-development>.
22
23 =head2 Backward Incompatible Changes
24
25 =head3 Changes since isl-0.02
26
27 =over
28
29 =item * The old printing functions have been deprecated
30 and replaced by C<isl_printer> functions, see L<Input and Output>.
31
32 =item * Most functions related to dependence analysis have acquired
33 an extra C<must> argument.  To obtain the old behavior, this argument
34 should be given the value 1.  See L<Dependence Analysis>.
35
36 =back
37
38 =head3 Changes since isl-0.03
39
40 =over
41
42 =item * The function C<isl_pw_qpolynomial_fold_add> has been
43 renamed to C<isl_pw_qpolynomial_fold_fold>.
44 Similarly, C<isl_union_pw_qpolynomial_fold_add> has been
45 renamed to C<isl_union_pw_qpolynomial_fold_fold>.
46
47 =back
48
49 =head3 Changes since isl-0.04
50
51 =over
52
53 =item * All header files have been renamed from C<isl_header.h>
54 to C<isl/header.h>.
55
56 =back
57
58 =head3 Changes since isl-0.05
59
60 =over
61
62 =item * The functions C<isl_printer_print_basic_set> and
63 C<isl_printer_print_basic_map> no longer print a newline.
64
65 =item * The functions C<isl_flow_get_no_source>
66 and C<isl_union_map_compute_flow> now return
67 the accesses for which no source could be found instead of
68 the iterations where those accesses occur.
69
70 =item * The functions C<isl_basic_map_identity> and
71 C<isl_map_identity> now take a B<map> space as input.  An old call
72 C<isl_map_identity(space)> can be rewritten to
73 C<isl_map_identity(isl_space_map_from_set(space))>.
74
75 =item * The function C<isl_map_power> no longer takes
76 a parameter position as input.  Instead, the exponent
77 is now expressed as the domain of the resulting relation.
78
79 =back
80
81 =head3 Changes since isl-0.06
82
83 =over
84
85 =item * The format of C<isl_printer_print_qpolynomial>'s
86 C<ISL_FORMAT_ISL> output has changed.
87 Use C<ISL_FORMAT_C> to obtain the old output.
88
89 =item * The C<*_fast_*> functions have been renamed to C<*_plain_*>.
90 Some of the old names have been kept for backward compatibility,
91 but they will be removed in the future.
92
93 =back
94
95 =head3 Changes since isl-0.07
96
97 =over
98
99 =item * The function C<isl_pw_aff_max> has been renamed to
100 C<isl_pw_aff_union_max>.
101 Similarly, the function C<isl_pw_aff_add> has been renamed to
102 C<isl_pw_aff_union_add>.
103
104 =item * The C<isl_dim> type has been renamed to C<isl_space>
105 along with the associated functions.
106 Some of the old names have been kept for backward compatibility,
107 but they will be removed in the future.
108
109 =item * Spaces of maps, sets and parameter domains are now
110 treated differently.  The distinction between map spaces and set spaces
111 has always been made on a conceptual level, but proper use of such spaces
112 was never checked.  Furthermore, up until isl-0.07 there was no way
113 of explicitly creating a parameter space.  These can now be created
114 directly using C<isl_space_params_alloc> or from other spaces using
115 C<isl_space_params>.
116
117 =item * The space in which C<isl_aff>, C<isl_pw_aff>, C<isl_qpolynomial>,
118 C<isl_pw_qpolynomial>, C<isl_qpolynomial_fold> and C<isl_pw_qpolynomial_fold>
119 objects live is now a map space
120 instead of a set space.  This means, for example, that the dimensions
121 of the domain of an C<isl_aff> are now considered to be of type
122 C<isl_dim_in> instead of C<isl_dim_set>.  Extra functions have been
123 added to obtain the domain space.  Some of the constructors still
124 take a domain space and have therefore been renamed.
125
126 =item * The functions C<isl_equality_alloc> and C<isl_inequality_alloc>
127 now take an C<isl_local_space> instead of an C<isl_space>.
128 An C<isl_local_space> can be created from an C<isl_space>
129 using C<isl_local_space_from_space>.
130
131 =item * The C<isl_div> type has been removed.  Functions that used
132 to return an C<isl_div> now return an C<isl_aff>.
133 Note that the space of an C<isl_aff> is that of relation.
134 When replacing a call to C<isl_div_get_coefficient> by a call to
135 C<isl_aff_get_coefficient> any C<isl_dim_set> argument needs
136 to be replaced by C<isl_dim_in>.
137 A call to C<isl_aff_from_div> can be replaced by a call
138 to C<isl_aff_floor>.
139 A call to C<isl_qpolynomial_div(div)> call be replaced by
140 the nested call
141
142         isl_qpolynomial_from_aff(isl_aff_floor(div))
143
144 The function C<isl_constraint_div> has also been renamed
145 to C<isl_constraint_get_div>.
146
147 =item * The C<nparam> argument has been removed from
148 C<isl_map_read_from_str> and similar functions.
149 When reading input in the original PolyLib format,
150 the result will have no parameters.
151 If parameters are expected, the caller may want to perform
152 dimension manipulation on the result.
153
154 =back
155
156 =head1 Installation
157
158 The source of C<isl> can be obtained either as a tarball
159 or from the git repository.  Both are available from
160 L<http://freshmeat.net/projects/isl/>.
161 The installation process depends on how you obtained
162 the source.
163
164 =head2 Installation from the git repository
165
166 =over
167
168 =item 1 Clone or update the repository
169
170 The first time the source is obtained, you need to clone
171 the repository.
172
173         git clone git://repo.or.cz/isl.git
174
175 To obtain updates, you need to pull in the latest changes
176
177         git pull
178
179 =item 2 Generate C<configure>
180
181         ./autogen.sh
182
183 =back
184
185 After performing the above steps, continue
186 with the L<Common installation instructions>.
187
188 =head2 Common installation instructions
189
190 =over
191
192 =item 1 Obtain C<GMP>
193
194 Building C<isl> requires C<GMP>, including its headers files.
195 Your distribution may not provide these header files by default
196 and you may need to install a package called C<gmp-devel> or something
197 similar.  Alternatively, C<GMP> can be built from
198 source, available from L<http://gmplib.org/>.
199
200 =item 2 Configure
201
202 C<isl> uses the standard C<autoconf> C<configure> script.
203 To run it, just type
204
205         ./configure
206
207 optionally followed by some configure options.
208 A complete list of options can be obtained by running
209
210         ./configure --help
211
212 Below we discuss some of the more common options.
213
214 C<isl> can optionally use C<piplib>, but no
215 C<piplib> functionality is currently used by default.
216 The C<--with-piplib> option can
217 be used to specify which C<piplib>
218 library to use, either an installed version (C<system>),
219 an externally built version (C<build>)
220 or no version (C<no>).  The option C<build> is mostly useful
221 in C<configure> scripts of larger projects that bundle both C<isl>
222 and C<piplib>.
223
224 =over
225
226 =item C<--prefix>
227
228 Installation prefix for C<isl>
229
230 =item C<--with-gmp-prefix>
231
232 Installation prefix for C<GMP> (architecture-independent files).
233
234 =item C<--with-gmp-exec-prefix>
235
236 Installation prefix for C<GMP> (architecture-dependent files).
237
238 =item C<--with-piplib>
239
240 Which copy of C<piplib> to use, either C<no> (default), C<system> or C<build>.
241
242 =item C<--with-piplib-prefix>
243
244 Installation prefix for C<system> C<piplib> (architecture-independent files).
245
246 =item C<--with-piplib-exec-prefix>
247
248 Installation prefix for C<system> C<piplib> (architecture-dependent files).
249
250 =item C<--with-piplib-builddir>
251
252 Location where C<build> C<piplib> was built.
253
254 =back
255
256 =item 3 Compile
257
258         make
259
260 =item 4 Install (optional)
261
262         make install
263
264 =back
265
266 =head1 Library
267
268 =head2 Initialization
269
270 All manipulations of integer sets and relations occur within
271 the context of an C<isl_ctx>.
272 A given C<isl_ctx> can only be used within a single thread.
273 All arguments of a function are required to have been allocated
274 within the same context.
275 There are currently no functions available for moving an object
276 from one C<isl_ctx> to another C<isl_ctx>.  This means that
277 there is currently no way of safely moving an object from one
278 thread to another, unless the whole C<isl_ctx> is moved.
279
280 An C<isl_ctx> can be allocated using C<isl_ctx_alloc> and
281 freed using C<isl_ctx_free>.
282 All objects allocated within an C<isl_ctx> should be freed
283 before the C<isl_ctx> itself is freed.
284
285         isl_ctx *isl_ctx_alloc();
286         void isl_ctx_free(isl_ctx *ctx);
287
288 =head2 Integers
289
290 All operations on integers, mainly the coefficients
291 of the constraints describing the sets and relations,
292 are performed in exact integer arithmetic using C<GMP>.
293 However, to allow future versions of C<isl> to optionally
294 support fixed integer arithmetic, all calls to C<GMP>
295 are wrapped inside C<isl> specific macros.
296 The basic type is C<isl_int> and the operations below
297 are available on this type.
298 The meanings of these operations are essentially the same
299 as their C<GMP> C<mpz_> counterparts.
300 As always with C<GMP> types, C<isl_int>s need to be
301 initialized with C<isl_int_init> before they can be used
302 and they need to be released with C<isl_int_clear>
303 after the last use.
304 The user should not assume that an C<isl_int> is represented
305 as a C<mpz_t>, but should instead explicitly convert between
306 C<mpz_t>s and C<isl_int>s using C<isl_int_set_gmp> and
307 C<isl_int_get_gmp> whenever a C<mpz_t> is required.
308
309 =over
310
311 =item isl_int_init(i)
312
313 =item isl_int_clear(i)
314
315 =item isl_int_set(r,i)
316
317 =item isl_int_set_si(r,i)
318
319 =item isl_int_set_gmp(r,g)
320
321 =item isl_int_get_gmp(i,g)
322
323 =item isl_int_abs(r,i)
324
325 =item isl_int_neg(r,i)
326
327 =item isl_int_swap(i,j)
328
329 =item isl_int_swap_or_set(i,j)
330
331 =item isl_int_add_ui(r,i,j)
332
333 =item isl_int_sub_ui(r,i,j)
334
335 =item isl_int_add(r,i,j)
336
337 =item isl_int_sub(r,i,j)
338
339 =item isl_int_mul(r,i,j)
340
341 =item isl_int_mul_ui(r,i,j)
342
343 =item isl_int_addmul(r,i,j)
344
345 =item isl_int_submul(r,i,j)
346
347 =item isl_int_gcd(r,i,j)
348
349 =item isl_int_lcm(r,i,j)
350
351 =item isl_int_divexact(r,i,j)
352
353 =item isl_int_cdiv_q(r,i,j)
354
355 =item isl_int_fdiv_q(r,i,j)
356
357 =item isl_int_fdiv_r(r,i,j)
358
359 =item isl_int_fdiv_q_ui(r,i,j)
360
361 =item isl_int_read(r,s)
362
363 =item isl_int_print(out,i,width)
364
365 =item isl_int_sgn(i)
366
367 =item isl_int_cmp(i,j)
368
369 =item isl_int_cmp_si(i,si)
370
371 =item isl_int_eq(i,j)
372
373 =item isl_int_ne(i,j)
374
375 =item isl_int_lt(i,j)
376
377 =item isl_int_le(i,j)
378
379 =item isl_int_gt(i,j)
380
381 =item isl_int_ge(i,j)
382
383 =item isl_int_abs_eq(i,j)
384
385 =item isl_int_abs_ne(i,j)
386
387 =item isl_int_abs_lt(i,j)
388
389 =item isl_int_abs_gt(i,j)
390
391 =item isl_int_abs_ge(i,j)
392
393 =item isl_int_is_zero(i)
394
395 =item isl_int_is_one(i)
396
397 =item isl_int_is_negone(i)
398
399 =item isl_int_is_pos(i)
400
401 =item isl_int_is_neg(i)
402
403 =item isl_int_is_nonpos(i)
404
405 =item isl_int_is_nonneg(i)
406
407 =item isl_int_is_divisible_by(i,j)
408
409 =back
410
411 =head2 Sets and Relations
412
413 C<isl> uses six types of objects for representing sets and relations,
414 C<isl_basic_set>, C<isl_basic_map>, C<isl_set>, C<isl_map>,
415 C<isl_union_set> and C<isl_union_map>.
416 C<isl_basic_set> and C<isl_basic_map> represent sets and relations that
417 can be described as a conjunction of affine constraints, while
418 C<isl_set> and C<isl_map> represent unions of
419 C<isl_basic_set>s and C<isl_basic_map>s, respectively.
420 However, all C<isl_basic_set>s or C<isl_basic_map>s in the union need
421 to live in the same space.  C<isl_union_set>s and C<isl_union_map>s
422 represent unions of C<isl_set>s or C<isl_map>s in I<different> spaces,
423 where spaces are considered different if they have a different number
424 of dimensions and/or different names (see L<"Spaces">).
425 The difference between sets and relations (maps) is that sets have
426 one set of variables, while relations have two sets of variables,
427 input variables and output variables.
428
429 =head2 Memory Management
430
431 Since a high-level operation on sets and/or relations usually involves
432 several substeps and since the user is usually not interested in
433 the intermediate results, most functions that return a new object
434 will also release all the objects passed as arguments.
435 If the user still wants to use one or more of these arguments
436 after the function call, she should pass along a copy of the
437 object rather than the object itself.
438 The user is then responsible for making sure that the original
439 object gets used somewhere else or is explicitly freed.
440
441 The arguments and return values of all documented functions are
442 annotated to make clear which arguments are released and which
443 arguments are preserved.  In particular, the following annotations
444 are used
445
446 =over
447
448 =item C<__isl_give>
449
450 C<__isl_give> means that a new object is returned.
451 The user should make sure that the returned pointer is
452 used exactly once as a value for an C<__isl_take> argument.
453 In between, it can be used as a value for as many
454 C<__isl_keep> arguments as the user likes.
455 There is one exception, and that is the case where the
456 pointer returned is C<NULL>.  Is this case, the user
457 is free to use it as an C<__isl_take> argument or not.
458
459 =item C<__isl_take>
460
461 C<__isl_take> means that the object the argument points to
462 is taken over by the function and may no longer be used
463 by the user as an argument to any other function.
464 The pointer value must be one returned by a function
465 returning an C<__isl_give> pointer.
466 If the user passes in a C<NULL> value, then this will
467 be treated as an error in the sense that the function will
468 not perform its usual operation.  However, it will still
469 make sure that all the other C<__isl_take> arguments
470 are released.
471
472 =item C<__isl_keep>
473
474 C<__isl_keep> means that the function will only use the object
475 temporarily.  After the function has finished, the user
476 can still use it as an argument to other functions.
477 A C<NULL> value will be treated in the same way as
478 a C<NULL> value for an C<__isl_take> argument.
479
480 =back
481
482 =head2 Identifiers
483
484 Identifiers are used to identify both individual dimensions
485 and tuples of dimensions.  They consist of a name and an optional
486 pointer.  Identifiers with the same name but different pointer values
487 are considered to be distinct.
488 Identifiers can be constructed, copied, freed, inspected and printed
489 using the following functions.
490
491         #include <isl/id.h>
492         __isl_give isl_id *isl_id_alloc(isl_ctx *ctx,
493                 __isl_keep const char *name, void *user);
494         __isl_give isl_id *isl_id_copy(isl_id *id);
495         void *isl_id_free(__isl_take isl_id *id);
496
497         isl_ctx *isl_id_get_ctx(__isl_keep isl_id *id);
498         void *isl_id_get_user(__isl_keep isl_id *id);
499         __isl_keep const char *isl_id_get_name(__isl_keep isl_id *id);
500
501         __isl_give isl_printer *isl_printer_print_id(
502                 __isl_take isl_printer *p, __isl_keep isl_id *id);
503
504 Note that C<isl_id_get_name> returns a pointer to some internal
505 data structure, so the result can only be used while the
506 corresponding C<isl_id> is alive.
507
508 =head2 Spaces
509
510 Whenever a new set or relation is created from scratch,
511 the space in which it lives needs to be specified using an C<isl_space>.
512
513         #include <isl/space.h>
514         __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
515                 unsigned nparam, unsigned n_in, unsigned n_out);
516         __isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx,
517                 unsigned nparam);
518         __isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,
519                 unsigned nparam, unsigned dim);
520         __isl_give isl_space *isl_space_copy(__isl_keep isl_space *space);
521         void isl_space_free(__isl_take isl_space *space);
522         unsigned isl_space_dim(__isl_keep isl_space *space,
523                 enum isl_dim_type type);
524
525 The space used for creating a parameter domain
526 needs to be created using C<isl_space_params_alloc>.
527 For other sets, the space
528 needs to be created using C<isl_space_set_alloc>, while
529 for a relation, the space
530 needs to be created using C<isl_space_alloc>.
531 C<isl_space_dim> can be used
532 to find out the number of dimensions of each type in
533 a space, where type may be
534 C<isl_dim_param>, C<isl_dim_in> (only for relations),
535 C<isl_dim_out> (only for relations), C<isl_dim_set>
536 (only for sets) or C<isl_dim_all>.
537
538 To check whether a given space is that of a set or a map
539 or whether it is a parameter space, use these functions:
540
541         #include <isl/space.h>
542         int isl_space_is_params(__isl_keep isl_space *space);
543         int isl_space_is_set(__isl_keep isl_space *space);
544
545 It is often useful to create objects that live in the
546 same space as some other object.  This can be accomplished
547 by creating the new objects
548 (see L<Creating New Sets and Relations> or
549 L<Creating New (Piecewise) Quasipolynomials>) based on the space
550 of the original object.
551
552         #include <isl/set.h>
553         __isl_give isl_space *isl_basic_set_get_space(
554                 __isl_keep isl_basic_set *bset);
555         __isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set);
556
557         #include <isl/union_set.h>
558         __isl_give isl_space *isl_union_set_get_space(
559                 __isl_keep isl_union_set *uset);
560
561         #include <isl/map.h>
562         __isl_give isl_space *isl_basic_map_get_space(
563                 __isl_keep isl_basic_map *bmap);
564         __isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map);
565
566         #include <isl/union_map.h>
567         __isl_give isl_space *isl_union_map_get_space(
568                 __isl_keep isl_union_map *umap);
569
570         #include <isl/constraint.h>
571         __isl_give isl_space *isl_constraint_get_space(
572                 __isl_keep isl_constraint *constraint);
573
574         #include <isl/polynomial.h>
575         __isl_give isl_space *isl_qpolynomial_get_domain_space(
576                 __isl_keep isl_qpolynomial *qp);
577         __isl_give isl_space *isl_qpolynomial_get_space(
578                 __isl_keep isl_qpolynomial *qp);
579         __isl_give isl_space *isl_qpolynomial_fold_get_space(
580                 __isl_keep isl_qpolynomial_fold *fold);
581         __isl_give isl_space *isl_pw_qpolynomial_get_domain_space(
582                 __isl_keep isl_pw_qpolynomial *pwqp);
583         __isl_give isl_space *isl_pw_qpolynomial_get_space(
584                 __isl_keep isl_pw_qpolynomial *pwqp);
585         __isl_give isl_space *isl_pw_qpolynomial_fold_get_domain_space(
586                 __isl_keep isl_pw_qpolynomial_fold *pwf);
587         __isl_give isl_space *isl_pw_qpolynomial_fold_get_space(
588                 __isl_keep isl_pw_qpolynomial_fold *pwf);
589         __isl_give isl_space *isl_union_pw_qpolynomial_get_space(
590                 __isl_keep isl_union_pw_qpolynomial *upwqp);
591         __isl_give isl_space *isl_union_pw_qpolynomial_fold_get_space(
592                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
593
594         #include <isl/aff.h>
595         __isl_give isl_space *isl_aff_get_domain_space(
596                 __isl_keep isl_aff *aff);
597         __isl_give isl_space *isl_aff_get_space(
598                 __isl_keep isl_aff *aff);
599         __isl_give isl_space *isl_pw_aff_get_domain_space(
600                 __isl_keep isl_pw_aff *pwaff);
601         __isl_give isl_space *isl_pw_aff_get_space(
602                 __isl_keep isl_pw_aff *pwaff);
603         __isl_give isl_space *isl_multi_aff_get_space(
604                 __isl_keep isl_multi_aff *maff);
605         __isl_give isl_space *isl_pw_multi_aff_get_domain_space(
606                 __isl_keep isl_pw_multi_aff *pma);
607         __isl_give isl_space *isl_pw_multi_aff_get_space(
608                 __isl_keep isl_pw_multi_aff *pma);
609
610         #include <isl/point.h>
611         __isl_give isl_space *isl_point_get_space(
612                 __isl_keep isl_point *pnt);
613
614 The identifiers or names of the individual dimensions may be set or read off
615 using the following functions.
616
617         #include <isl/space.h>
618         __isl_give isl_space *isl_space_set_dim_id(
619                 __isl_take isl_space *space,
620                 enum isl_dim_type type, unsigned pos,
621                 __isl_take isl_id *id);
622         int isl_space_has_dim_id(__isl_keep isl_space *space,
623                 enum isl_dim_type type, unsigned pos);
624         __isl_give isl_id *isl_space_get_dim_id(
625                 __isl_keep isl_space *space,
626                 enum isl_dim_type type, unsigned pos);
627         __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,
628                                  enum isl_dim_type type, unsigned pos,
629                                  __isl_keep const char *name);
630         __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,
631                                  enum isl_dim_type type, unsigned pos);
632
633 Note that C<isl_space_get_name> returns a pointer to some internal
634 data structure, so the result can only be used while the
635 corresponding C<isl_space> is alive.
636 Also note that every function that operates on two sets or relations
637 requires that both arguments have the same parameters.  This also
638 means that if one of the arguments has named parameters, then the
639 other needs to have named parameters too and the names need to match.
640 Pairs of C<isl_set>, C<isl_map>, C<isl_union_set> and/or C<isl_union_map>
641 arguments may have different parameters (as long as they are named),
642 in which case the result will have as parameters the union of the parameters of
643 the arguments.
644
645 Given the identifier or name of a dimension (typically a parameter),
646 its position can be obtained from the following function.
647
648         #include <isl/space.h>
649         int isl_space_find_dim_by_id(__isl_keep isl_space *space,
650                 enum isl_dim_type type, __isl_keep isl_id *id);
651         int isl_space_find_dim_by_name(__isl_keep isl_space *space,
652                 enum isl_dim_type type, const char *name);
653
654 The identifiers or names of entire spaces may be set or read off
655 using the following functions.
656
657         #include <isl/space.h>
658         __isl_give isl_space *isl_space_set_tuple_id(
659                 __isl_take isl_space *space,
660                 enum isl_dim_type type, __isl_take isl_id *id);
661         __isl_give isl_space *isl_space_reset_tuple_id(
662                 __isl_take isl_space *space, enum isl_dim_type type);
663         int isl_space_has_tuple_id(__isl_keep isl_space *space,
664                 enum isl_dim_type type);
665         __isl_give isl_id *isl_space_get_tuple_id(
666                 __isl_keep isl_space *space, enum isl_dim_type type);
667         __isl_give isl_space *isl_space_set_tuple_name(
668                 __isl_take isl_space *space,
669                 enum isl_dim_type type, const char *s);
670         const char *isl_space_get_tuple_name(__isl_keep isl_space *space,
671                 enum isl_dim_type type);
672
673 The C<type> argument needs to be one of C<isl_dim_in>, C<isl_dim_out>
674 or C<isl_dim_set>.  As with C<isl_space_get_name>,
675 the C<isl_space_get_tuple_name> function returns a pointer to some internal
676 data structure.
677 Binary operations require the corresponding spaces of their arguments
678 to have the same name.
679
680 Spaces can be nested.  In particular, the domain of a set or
681 the domain or range of a relation can be a nested relation.
682 The following functions can be used to construct and deconstruct
683 such nested spaces.
684
685         #include <isl/space.h>
686         int isl_space_is_wrapping(__isl_keep isl_space *space);
687         __isl_give isl_space *isl_space_wrap(__isl_take isl_space *space);
688         __isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space);
689
690 The input to C<isl_space_is_wrapping> and C<isl_space_unwrap> should
691 be the space of a set, while that of
692 C<isl_space_wrap> should be the space of a relation.
693 Conversely, the output of C<isl_space_unwrap> is the space
694 of a relation, while that of C<isl_space_wrap> is the space of a set.
695
696 Spaces can be created from other spaces
697 using the following functions.
698
699         __isl_give isl_space *isl_space_domain(__isl_take isl_space *space);
700         __isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space);
701         __isl_give isl_space *isl_space_range(__isl_take isl_space *space);
702         __isl_give isl_space *isl_space_from_range(__isl_take isl_space *space);
703         __isl_give isl_space *isl_space_params(
704                 __isl_take isl_space *space);
705         __isl_give isl_space *isl_space_set_from_params(
706                 __isl_take isl_space *space);
707         __isl_give isl_space *isl_space_reverse(__isl_take isl_space *space);
708         __isl_give isl_space *isl_space_join(__isl_take isl_space *left,
709                 __isl_take isl_space *right);
710         __isl_give isl_space *isl_space_align_params(
711                 __isl_take isl_space *space1, __isl_take isl_space *space2)
712         __isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,
713                 enum isl_dim_type type, unsigned pos, unsigned n);
714         __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,
715                 enum isl_dim_type type, unsigned n);
716         __isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,
717                 enum isl_dim_type type, unsigned first, unsigned n);
718         __isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,
719                 enum isl_dim_type dst_type, unsigned dst_pos,
720                 enum isl_dim_type src_type, unsigned src_pos,
721                 unsigned n);
722         __isl_give isl_space *isl_space_map_from_set(
723                 __isl_take isl_space *space);
724         __isl_give isl_space *isl_space_zip(__isl_take isl_space *space);
725
726 Note that if dimensions are added or removed from a space, then
727 the name and the internal structure are lost.
728
729 =head2 Local Spaces
730
731 A local space is essentially a space with
732 zero or more existentially quantified variables.
733 The local space of a basic set or relation can be obtained
734 using the following functions.
735
736         #include <isl/set.h>
737         __isl_give isl_local_space *isl_basic_set_get_local_space(
738                 __isl_keep isl_basic_set *bset);
739
740         #include <isl/map.h>
741         __isl_give isl_local_space *isl_basic_map_get_local_space(
742                 __isl_keep isl_basic_map *bmap);
743
744 A new local space can be created from a space using
745
746         #include <isl/local_space.h>
747         __isl_give isl_local_space *isl_local_space_from_space(
748                 __isl_take isl_space *space);
749
750 They can be inspected, modified, copied and freed using the following functions.
751
752         #include <isl/local_space.h>
753         isl_ctx *isl_local_space_get_ctx(
754                 __isl_keep isl_local_space *ls);
755         int isl_local_space_is_set(__isl_keep isl_local_space *ls);
756         int isl_local_space_dim(__isl_keep isl_local_space *ls,
757                 enum isl_dim_type type);
758         const char *isl_local_space_get_dim_name(
759                 __isl_keep isl_local_space *ls,
760                 enum isl_dim_type type, unsigned pos);
761         __isl_give isl_local_space *isl_local_space_set_dim_name(
762                 __isl_take isl_local_space *ls,
763                 enum isl_dim_type type, unsigned pos, const char *s);
764         __isl_give isl_local_space *isl_local_space_set_dim_id(
765                 __isl_take isl_local_space *ls,
766                 enum isl_dim_type type, unsigned pos,
767                 __isl_take isl_id *id);
768         __isl_give isl_space *isl_local_space_get_space(
769                 __isl_keep isl_local_space *ls);
770         __isl_give isl_aff *isl_local_space_get_div(
771                 __isl_keep isl_local_space *ls, int pos);
772         __isl_give isl_local_space *isl_local_space_copy(
773                 __isl_keep isl_local_space *ls);
774         void *isl_local_space_free(__isl_take isl_local_space *ls);
775
776 Two local spaces can be compared using
777
778         int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
779                 __isl_keep isl_local_space *ls2);
780
781 Local spaces can be created from other local spaces
782 using the following functions.
783
784         __isl_give isl_local_space *isl_local_space_domain(
785                 __isl_take isl_local_space *ls);
786         __isl_give isl_local_space *isl_local_space_from_domain(
787                 __isl_take isl_local_space *ls);
788         __isl_give isl_local_space *isl_local_space_intersect(
789                 __isl_take isl_local_space *ls1,
790                 __isl_take isl_local_space *ls2);
791         __isl_give isl_local_space *isl_local_space_add_dims(
792                 __isl_take isl_local_space *ls,
793                 enum isl_dim_type type, unsigned n);
794         __isl_give isl_local_space *isl_local_space_insert_dims(
795                 __isl_take isl_local_space *ls,
796                 enum isl_dim_type type, unsigned first, unsigned n);
797         __isl_give isl_local_space *isl_local_space_drop_dims(
798                 __isl_take isl_local_space *ls,
799                 enum isl_dim_type type, unsigned first, unsigned n);
800
801 =head2 Input and Output
802
803 C<isl> supports its own input/output format, which is similar
804 to the C<Omega> format, but also supports the C<PolyLib> format
805 in some cases.
806
807 =head3 C<isl> format
808
809 The C<isl> format is similar to that of C<Omega>, but has a different
810 syntax for describing the parameters and allows for the definition
811 of an existentially quantified variable as the integer division
812 of an affine expression.
813 For example, the set of integers C<i> between C<0> and C<n>
814 such that C<i % 10 <= 6> can be described as
815
816         [n] -> { [i] : exists (a = [i/10] : 0 <= i and i <= n and
817                                 i - 10 a <= 6) }
818
819 A set or relation can have several disjuncts, separated
820 by the keyword C<or>.  Each disjunct is either a conjunction
821 of constraints or a projection (C<exists>) of a conjunction
822 of constraints.  The constraints are separated by the keyword
823 C<and>.
824
825 =head3 C<PolyLib> format
826
827 If the represented set is a union, then the first line
828 contains a single number representing the number of disjuncts.
829 Otherwise, a line containing the number C<1> is optional.
830
831 Each disjunct is represented by a matrix of constraints.
832 The first line contains two numbers representing
833 the number of rows and columns,
834 where the number of rows is equal to the number of constraints
835 and the number of columns is equal to two plus the number of variables.
836 The following lines contain the actual rows of the constraint matrix.
837 In each row, the first column indicates whether the constraint
838 is an equality (C<0>) or inequality (C<1>).  The final column
839 corresponds to the constant term.
840
841 If the set is parametric, then the coefficients of the parameters
842 appear in the last columns before the constant column.
843 The coefficients of any existentially quantified variables appear
844 between those of the set variables and those of the parameters.
845
846 =head3 Extended C<PolyLib> format
847
848 The extended C<PolyLib> format is nearly identical to the
849 C<PolyLib> format.  The only difference is that the line
850 containing the number of rows and columns of a constraint matrix
851 also contains four additional numbers:
852 the number of output dimensions, the number of input dimensions,
853 the number of local dimensions (i.e., the number of existentially
854 quantified variables) and the number of parameters.
855 For sets, the number of ``output'' dimensions is equal
856 to the number of set dimensions, while the number of ``input''
857 dimensions is zero.
858
859 =head3 Input
860
861         #include <isl/set.h>
862         __isl_give isl_basic_set *isl_basic_set_read_from_file(
863                 isl_ctx *ctx, FILE *input);
864         __isl_give isl_basic_set *isl_basic_set_read_from_str(
865                 isl_ctx *ctx, const char *str);
866         __isl_give isl_set *isl_set_read_from_file(isl_ctx *ctx,
867                 FILE *input);
868         __isl_give isl_set *isl_set_read_from_str(isl_ctx *ctx,
869                 const char *str);
870
871         #include <isl/map.h>
872         __isl_give isl_basic_map *isl_basic_map_read_from_file(
873                 isl_ctx *ctx, FILE *input);
874         __isl_give isl_basic_map *isl_basic_map_read_from_str(
875                 isl_ctx *ctx, const char *str);
876         __isl_give isl_map *isl_map_read_from_file(
877                 isl_ctx *ctx, FILE *input);
878         __isl_give isl_map *isl_map_read_from_str(isl_ctx *ctx,
879                 const char *str);
880
881         #include <isl/union_set.h>
882         __isl_give isl_union_set *isl_union_set_read_from_file(
883                 isl_ctx *ctx, FILE *input);
884         __isl_give isl_union_set *isl_union_set_read_from_str(
885                 isl_ctx *ctx, const char *str);
886
887         #include <isl/union_map.h>
888         __isl_give isl_union_map *isl_union_map_read_from_file(
889                 isl_ctx *ctx, FILE *input);
890         __isl_give isl_union_map *isl_union_map_read_from_str(
891                 isl_ctx *ctx, const char *str);
892
893 The input format is autodetected and may be either the C<PolyLib> format
894 or the C<isl> format.
895
896 =head3 Output
897
898 Before anything can be printed, an C<isl_printer> needs to
899 be created.
900
901         __isl_give isl_printer *isl_printer_to_file(isl_ctx *ctx,
902                 FILE *file);
903         __isl_give isl_printer *isl_printer_to_str(isl_ctx *ctx);
904         void isl_printer_free(__isl_take isl_printer *printer);
905         __isl_give char *isl_printer_get_str(
906                 __isl_keep isl_printer *printer);
907
908 The behavior of the printer can be modified in various ways
909
910         __isl_give isl_printer *isl_printer_set_output_format(
911                 __isl_take isl_printer *p, int output_format);
912         __isl_give isl_printer *isl_printer_set_indent(
913                 __isl_take isl_printer *p, int indent);
914         __isl_give isl_printer *isl_printer_indent(
915                 __isl_take isl_printer *p, int indent);
916         __isl_give isl_printer *isl_printer_set_prefix(
917                 __isl_take isl_printer *p, const char *prefix);
918         __isl_give isl_printer *isl_printer_set_suffix(
919                 __isl_take isl_printer *p, const char *suffix);
920
921 The C<output_format> may be either C<ISL_FORMAT_ISL>, C<ISL_FORMAT_OMEGA>,
922 C<ISL_FORMAT_POLYLIB>, C<ISL_FORMAT_EXT_POLYLIB> or C<ISL_FORMAT_LATEX>
923 and defaults to C<ISL_FORMAT_ISL>.
924 Each line in the output is indented by C<indent> (set by
925 C<isl_printer_set_indent>) spaces
926 (default: 0), prefixed by C<prefix> and suffixed by C<suffix>.
927 In the C<PolyLib> format output,
928 the coefficients of the existentially quantified variables
929 appear between those of the set variables and those
930 of the parameters.
931 The function C<isl_printer_indent> increases the indentation
932 by the specified amount (which may be negative).
933
934 To actually print something, use
935
936         #include <isl/set.h>
937         __isl_give isl_printer *isl_printer_print_basic_set(
938                 __isl_take isl_printer *printer,
939                 __isl_keep isl_basic_set *bset);
940         __isl_give isl_printer *isl_printer_print_set(
941                 __isl_take isl_printer *printer,
942                 __isl_keep isl_set *set);
943
944         #include <isl/map.h>
945         __isl_give isl_printer *isl_printer_print_basic_map(
946                 __isl_take isl_printer *printer,
947                 __isl_keep isl_basic_map *bmap);
948         __isl_give isl_printer *isl_printer_print_map(
949                 __isl_take isl_printer *printer,
950                 __isl_keep isl_map *map);
951
952         #include <isl/union_set.h>
953         __isl_give isl_printer *isl_printer_print_union_set(
954                 __isl_take isl_printer *p,
955                 __isl_keep isl_union_set *uset);
956
957         #include <isl/union_map.h>
958         __isl_give isl_printer *isl_printer_print_union_map(
959                 __isl_take isl_printer *p,
960                 __isl_keep isl_union_map *umap);
961
962 When called on a file printer, the following function flushes
963 the file.  When called on a string printer, the buffer is cleared.
964
965         __isl_give isl_printer *isl_printer_flush(
966                 __isl_take isl_printer *p);
967
968 =head2 Creating New Sets and Relations
969
970 C<isl> has functions for creating some standard sets and relations.
971
972 =over
973
974 =item * Empty sets and relations
975
976         __isl_give isl_basic_set *isl_basic_set_empty(
977                 __isl_take isl_space *space);
978         __isl_give isl_basic_map *isl_basic_map_empty(
979                 __isl_take isl_space *space);
980         __isl_give isl_set *isl_set_empty(
981                 __isl_take isl_space *space);
982         __isl_give isl_map *isl_map_empty(
983                 __isl_take isl_space *space);
984         __isl_give isl_union_set *isl_union_set_empty(
985                 __isl_take isl_space *space);
986         __isl_give isl_union_map *isl_union_map_empty(
987                 __isl_take isl_space *space);
988
989 For C<isl_union_set>s and C<isl_union_map>s, the space
990 is only used to specify the parameters.
991
992 =item * Universe sets and relations
993
994         __isl_give isl_basic_set *isl_basic_set_universe(
995                 __isl_take isl_space *space);
996         __isl_give isl_basic_map *isl_basic_map_universe(
997                 __isl_take isl_space *space);
998         __isl_give isl_set *isl_set_universe(
999                 __isl_take isl_space *space);
1000         __isl_give isl_map *isl_map_universe(
1001                 __isl_take isl_space *space);
1002         __isl_give isl_union_set *isl_union_set_universe(
1003                 __isl_take isl_union_set *uset);
1004         __isl_give isl_union_map *isl_union_map_universe(
1005                 __isl_take isl_union_map *umap);
1006
1007 The sets and relations constructed by the functions above
1008 contain all integer values, while those constructed by the
1009 functions below only contain non-negative values.
1010
1011         __isl_give isl_basic_set *isl_basic_set_nat_universe(
1012                 __isl_take isl_space *space);
1013         __isl_give isl_basic_map *isl_basic_map_nat_universe(
1014                 __isl_take isl_space *space);
1015         __isl_give isl_set *isl_set_nat_universe(
1016                 __isl_take isl_space *space);
1017         __isl_give isl_map *isl_map_nat_universe(
1018                 __isl_take isl_space *space);
1019
1020 =item * Identity relations
1021
1022         __isl_give isl_basic_map *isl_basic_map_identity(
1023                 __isl_take isl_space *space);
1024         __isl_give isl_map *isl_map_identity(
1025                 __isl_take isl_space *space);
1026
1027 The number of input and output dimensions in C<space> needs
1028 to be the same.
1029
1030 =item * Lexicographic order
1031
1032         __isl_give isl_map *isl_map_lex_lt(
1033                 __isl_take isl_space *set_space);
1034         __isl_give isl_map *isl_map_lex_le(
1035                 __isl_take isl_space *set_space);
1036         __isl_give isl_map *isl_map_lex_gt(
1037                 __isl_take isl_space *set_space);
1038         __isl_give isl_map *isl_map_lex_ge(
1039                 __isl_take isl_space *set_space);
1040         __isl_give isl_map *isl_map_lex_lt_first(
1041                 __isl_take isl_space *space, unsigned n);
1042         __isl_give isl_map *isl_map_lex_le_first(
1043                 __isl_take isl_space *space, unsigned n);
1044         __isl_give isl_map *isl_map_lex_gt_first(
1045                 __isl_take isl_space *space, unsigned n);
1046         __isl_give isl_map *isl_map_lex_ge_first(
1047                 __isl_take isl_space *space, unsigned n);
1048
1049 The first four functions take a space for a B<set>
1050 and return relations that express that the elements in the domain
1051 are lexicographically less
1052 (C<isl_map_lex_lt>), less or equal (C<isl_map_lex_le>),
1053 greater (C<isl_map_lex_gt>) or greater or equal (C<isl_map_lex_ge>)
1054 than the elements in the range.
1055 The last four functions take a space for a map
1056 and return relations that express that the first C<n> dimensions
1057 in the domain are lexicographically less
1058 (C<isl_map_lex_lt_first>), less or equal (C<isl_map_lex_le_first>),
1059 greater (C<isl_map_lex_gt_first>) or greater or equal (C<isl_map_lex_ge_first>)
1060 than the first C<n> dimensions in the range.
1061
1062 =back
1063
1064 A basic set or relation can be converted to a set or relation
1065 using the following functions.
1066
1067         __isl_give isl_set *isl_set_from_basic_set(
1068                 __isl_take isl_basic_set *bset);
1069         __isl_give isl_map *isl_map_from_basic_map(
1070                 __isl_take isl_basic_map *bmap);
1071
1072 Sets and relations can be converted to union sets and relations
1073 using the following functions.
1074
1075         __isl_give isl_union_map *isl_union_map_from_map(
1076                 __isl_take isl_map *map);
1077         __isl_give isl_union_set *isl_union_set_from_set(
1078                 __isl_take isl_set *set);
1079
1080 The inverse conversions below can only be used if the input
1081 union set or relation is known to contain elements in exactly one
1082 space.
1083
1084         __isl_give isl_set *isl_set_from_union_set(
1085                 __isl_take isl_union_set *uset);
1086         __isl_give isl_map *isl_map_from_union_map(
1087                 __isl_take isl_union_map *umap);
1088
1089 A zero-dimensional set can be constructed on a given parameter domain
1090 using the following function.
1091
1092         __isl_give isl_set *isl_set_from_params(
1093                 __isl_take isl_set *set);
1094
1095 Sets and relations can be copied and freed again using the following
1096 functions.
1097
1098         __isl_give isl_basic_set *isl_basic_set_copy(
1099                 __isl_keep isl_basic_set *bset);
1100         __isl_give isl_set *isl_set_copy(__isl_keep isl_set *set);
1101         __isl_give isl_union_set *isl_union_set_copy(
1102                 __isl_keep isl_union_set *uset);
1103         __isl_give isl_basic_map *isl_basic_map_copy(
1104                 __isl_keep isl_basic_map *bmap);
1105         __isl_give isl_map *isl_map_copy(__isl_keep isl_map *map);
1106         __isl_give isl_union_map *isl_union_map_copy(
1107                 __isl_keep isl_union_map *umap);
1108         void isl_basic_set_free(__isl_take isl_basic_set *bset);
1109         void isl_set_free(__isl_take isl_set *set);
1110         void *isl_union_set_free(__isl_take isl_union_set *uset);
1111         void isl_basic_map_free(__isl_take isl_basic_map *bmap);
1112         void isl_map_free(__isl_take isl_map *map);
1113         void *isl_union_map_free(__isl_take isl_union_map *umap);
1114
1115 Other sets and relations can be constructed by starting
1116 from a universe set or relation, adding equality and/or
1117 inequality constraints and then projecting out the
1118 existentially quantified variables, if any.
1119 Constraints can be constructed, manipulated and
1120 added to (or removed from) (basic) sets and relations
1121 using the following functions.
1122
1123         #include <isl/constraint.h>
1124         __isl_give isl_constraint *isl_equality_alloc(
1125                 __isl_take isl_local_space *ls);
1126         __isl_give isl_constraint *isl_inequality_alloc(
1127                 __isl_take isl_local_space *ls);
1128         __isl_give isl_constraint *isl_constraint_set_constant(
1129                 __isl_take isl_constraint *constraint, isl_int v);
1130         __isl_give isl_constraint *isl_constraint_set_constant_si(
1131                 __isl_take isl_constraint *constraint, int v);
1132         __isl_give isl_constraint *isl_constraint_set_coefficient(
1133                 __isl_take isl_constraint *constraint,
1134                 enum isl_dim_type type, int pos, isl_int v);
1135         __isl_give isl_constraint *isl_constraint_set_coefficient_si(
1136                 __isl_take isl_constraint *constraint,
1137                 enum isl_dim_type type, int pos, int v);
1138         __isl_give isl_basic_map *isl_basic_map_add_constraint(
1139                 __isl_take isl_basic_map *bmap,
1140                 __isl_take isl_constraint *constraint);
1141         __isl_give isl_basic_set *isl_basic_set_add_constraint(
1142                 __isl_take isl_basic_set *bset,
1143                 __isl_take isl_constraint *constraint);
1144         __isl_give isl_map *isl_map_add_constraint(
1145                 __isl_take isl_map *map,
1146                 __isl_take isl_constraint *constraint);
1147         __isl_give isl_set *isl_set_add_constraint(
1148                 __isl_take isl_set *set,
1149                 __isl_take isl_constraint *constraint);
1150         __isl_give isl_basic_set *isl_basic_set_drop_constraint(
1151                 __isl_take isl_basic_set *bset,
1152                 __isl_take isl_constraint *constraint);
1153
1154 For example, to create a set containing the even integers
1155 between 10 and 42, you would use the following code.
1156
1157         isl_space *space;
1158         isl_local_space *ls;
1159         isl_constraint *c;
1160         isl_basic_set *bset;
1161
1162         space = isl_space_set_alloc(ctx, 0, 2);
1163         bset = isl_basic_set_universe(isl_space_copy(space));
1164         ls = isl_local_space_from_space(space);
1165
1166         c = isl_equality_alloc(isl_local_space_copy(ls));
1167         c = isl_constraint_set_coefficient_si(c, isl_dim_set, 0, -1);
1168         c = isl_constraint_set_coefficient_si(c, isl_dim_set, 1, 2);
1169         bset = isl_basic_set_add_constraint(bset, c);
1170
1171         c = isl_inequality_alloc(isl_local_space_copy(ls));
1172         c = isl_constraint_set_constant_si(c, -10);
1173         c = isl_constraint_set_coefficient_si(c, isl_dim_set, 0, 1);
1174         bset = isl_basic_set_add_constraint(bset, c);
1175
1176         c = isl_inequality_alloc(ls);
1177         c = isl_constraint_set_constant_si(c, 42);
1178         c = isl_constraint_set_coefficient_si(c, isl_dim_set, 0, -1);
1179         bset = isl_basic_set_add_constraint(bset, c);
1180
1181         bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 1);
1182
1183 Or, alternatively,
1184
1185         isl_basic_set *bset;
1186         bset = isl_basic_set_read_from_str(ctx,
1187                 "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}");
1188
1189 A basic set or relation can also be constructed from two matrices
1190 describing the equalities and the inequalities.
1191
1192         __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices(
1193                 __isl_take isl_space *space,
1194                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
1195                 enum isl_dim_type c1,
1196                 enum isl_dim_type c2, enum isl_dim_type c3,
1197                 enum isl_dim_type c4);
1198         __isl_give isl_basic_map *isl_basic_map_from_constraint_matrices(
1199                 __isl_take isl_space *space,
1200                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
1201                 enum isl_dim_type c1,
1202                 enum isl_dim_type c2, enum isl_dim_type c3,
1203                 enum isl_dim_type c4, enum isl_dim_type c5);
1204
1205 The C<isl_dim_type> arguments indicate the order in which
1206 different kinds of variables appear in the input matrices
1207 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1208 C<isl_dim_set> and C<isl_dim_div> for sets and
1209 of C<isl_dim_cst>, C<isl_dim_param>,
1210 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations.
1211
1212 A (basic) set or relation can also be constructed from a (piecewise)
1213 (multiple) affine expression
1214 or a list of affine expressions
1215 (See L<"Piecewise Quasi Affine Expressions"> and
1216 L<"Piecewise Multiple Quasi Affine Expressions">).
1217
1218         __isl_give isl_basic_map *isl_basic_map_from_aff(
1219                 __isl_take isl_aff *aff);
1220         __isl_give isl_set *isl_set_from_pw_aff(
1221                 __isl_take isl_pw_aff *pwaff);
1222         __isl_give isl_map *isl_map_from_pw_aff(
1223                 __isl_take isl_pw_aff *pwaff);
1224         __isl_give isl_basic_map *isl_basic_map_from_aff_list(
1225                 __isl_take isl_space *domain_space,
1226                 __isl_take isl_aff_list *list);
1227         __isl_give isl_basic_map *isl_basic_map_from_multi_aff(
1228                 __isl_take isl_multi_aff *maff)
1229         __isl_give isl_set *isl_set_from_pw_multi_aff(
1230                 __isl_take isl_pw_multi_aff *pma);
1231         __isl_give isl_map *isl_map_from_pw_multi_aff(
1232                 __isl_take isl_pw_multi_aff *pma);
1233
1234 The C<domain_dim> argument describes the domain of the resulting
1235 basic relation.  It is required because the C<list> may consist
1236 of zero affine expressions.
1237
1238 =head2 Inspecting Sets and Relations
1239
1240 Usually, the user should not have to care about the actual constraints
1241 of the sets and maps, but should instead apply the abstract operations
1242 explained in the following sections.
1243 Occasionally, however, it may be required to inspect the individual
1244 coefficients of the constraints.  This section explains how to do so.
1245 In these cases, it may also be useful to have C<isl> compute
1246 an explicit representation of the existentially quantified variables.
1247
1248         __isl_give isl_set *isl_set_compute_divs(
1249                 __isl_take isl_set *set);
1250         __isl_give isl_map *isl_map_compute_divs(
1251                 __isl_take isl_map *map);
1252         __isl_give isl_union_set *isl_union_set_compute_divs(
1253                 __isl_take isl_union_set *uset);
1254         __isl_give isl_union_map *isl_union_map_compute_divs(
1255                 __isl_take isl_union_map *umap);
1256
1257 This explicit representation defines the existentially quantified
1258 variables as integer divisions of the other variables, possibly
1259 including earlier existentially quantified variables.
1260 An explicitly represented existentially quantified variable therefore
1261 has a unique value when the values of the other variables are known.
1262 If, furthermore, the same existentials, i.e., existentials
1263 with the same explicit representations, should appear in the
1264 same order in each of the disjuncts of a set or map, then the user should call
1265 either of the following functions.
1266
1267         __isl_give isl_set *isl_set_align_divs(
1268                 __isl_take isl_set *set);
1269         __isl_give isl_map *isl_map_align_divs(
1270                 __isl_take isl_map *map);
1271
1272 Alternatively, the existentially quantified variables can be removed
1273 using the following functions, which compute an overapproximation.
1274
1275         __isl_give isl_basic_set *isl_basic_set_remove_divs(
1276                 __isl_take isl_basic_set *bset);
1277         __isl_give isl_basic_map *isl_basic_map_remove_divs(
1278                 __isl_take isl_basic_map *bmap);
1279         __isl_give isl_set *isl_set_remove_divs(
1280                 __isl_take isl_set *set);
1281         __isl_give isl_map *isl_map_remove_divs(
1282                 __isl_take isl_map *map);
1283
1284 To iterate over all the sets or maps in a union set or map, use
1285
1286         int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
1287                 int (*fn)(__isl_take isl_set *set, void *user),
1288                 void *user);
1289         int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
1290                 int (*fn)(__isl_take isl_map *map, void *user),
1291                 void *user);
1292
1293 The number of sets or maps in a union set or map can be obtained
1294 from
1295
1296         int isl_union_set_n_set(__isl_keep isl_union_set *uset);
1297         int isl_union_map_n_map(__isl_keep isl_union_map *umap);
1298
1299 To extract the set or map in a given space from a union, use
1300
1301         __isl_give isl_set *isl_union_set_extract_set(
1302                 __isl_keep isl_union_set *uset,
1303                 __isl_take isl_space *space);
1304         __isl_give isl_map *isl_union_map_extract_map(
1305                 __isl_keep isl_union_map *umap,
1306                 __isl_take isl_space *space);
1307
1308 To iterate over all the basic sets or maps in a set or map, use
1309
1310         int isl_set_foreach_basic_set(__isl_keep isl_set *set,
1311                 int (*fn)(__isl_take isl_basic_set *bset, void *user),
1312                 void *user);
1313         int isl_map_foreach_basic_map(__isl_keep isl_map *map,
1314                 int (*fn)(__isl_take isl_basic_map *bmap, void *user),
1315                 void *user);
1316
1317 The callback function C<fn> should return 0 if successful and
1318 -1 if an error occurs.  In the latter case, or if any other error
1319 occurs, the above functions will return -1.
1320
1321 It should be noted that C<isl> does not guarantee that
1322 the basic sets or maps passed to C<fn> are disjoint.
1323 If this is required, then the user should call one of
1324 the following functions first.
1325
1326         __isl_give isl_set *isl_set_make_disjoint(
1327                 __isl_take isl_set *set);
1328         __isl_give isl_map *isl_map_make_disjoint(
1329                 __isl_take isl_map *map);
1330
1331 The number of basic sets in a set can be obtained
1332 from
1333
1334         int isl_set_n_basic_set(__isl_keep isl_set *set);
1335
1336 To iterate over the constraints of a basic set or map, use
1337
1338         #include <isl/constraint.h>
1339
1340         int isl_basic_map_foreach_constraint(
1341                 __isl_keep isl_basic_map *bmap,
1342                 int (*fn)(__isl_take isl_constraint *c, void *user),
1343                 void *user);
1344         void *isl_constraint_free(__isl_take isl_constraint *c);
1345
1346 Again, the callback function C<fn> should return 0 if successful and
1347 -1 if an error occurs.  In the latter case, or if any other error
1348 occurs, the above functions will return -1.
1349 The constraint C<c> represents either an equality or an inequality.
1350 Use the following function to find out whether a constraint
1351 represents an equality.  If not, it represents an inequality.
1352
1353         int isl_constraint_is_equality(
1354                 __isl_keep isl_constraint *constraint);
1355
1356 The coefficients of the constraints can be inspected using
1357 the following functions.
1358
1359         void isl_constraint_get_constant(
1360                 __isl_keep isl_constraint *constraint, isl_int *v);
1361         void isl_constraint_get_coefficient(
1362                 __isl_keep isl_constraint *constraint,
1363                 enum isl_dim_type type, int pos, isl_int *v);
1364         int isl_constraint_involves_dims(
1365                 __isl_keep isl_constraint *constraint,
1366                 enum isl_dim_type type, unsigned first, unsigned n);
1367
1368 The explicit representations of the existentially quantified
1369 variables can be inspected using the following function.
1370 Note that the user is only allowed to use this function
1371 if the inspected set or map is the result of a call
1372 to C<isl_set_compute_divs> or C<isl_map_compute_divs>.
1373 The existentially quantified variable is equal to the floor
1374 of the returned affine expression.  The affine expression
1375 itself can be inspected using the functions in
1376 L<"Piecewise Quasi Affine Expressions">.
1377
1378         __isl_give isl_aff *isl_constraint_get_div(
1379                 __isl_keep isl_constraint *constraint, int pos);
1380
1381 To obtain the constraints of a basic set or map in matrix
1382 form, use the following functions.
1383
1384         __isl_give isl_mat *isl_basic_set_equalities_matrix(
1385                 __isl_keep isl_basic_set *bset,
1386                 enum isl_dim_type c1, enum isl_dim_type c2,
1387                 enum isl_dim_type c3, enum isl_dim_type c4);
1388         __isl_give isl_mat *isl_basic_set_inequalities_matrix(
1389                 __isl_keep isl_basic_set *bset,
1390                 enum isl_dim_type c1, enum isl_dim_type c2,
1391                 enum isl_dim_type c3, enum isl_dim_type c4);
1392         __isl_give isl_mat *isl_basic_map_equalities_matrix(
1393                 __isl_keep isl_basic_map *bmap,
1394                 enum isl_dim_type c1,
1395                 enum isl_dim_type c2, enum isl_dim_type c3,
1396                 enum isl_dim_type c4, enum isl_dim_type c5);
1397         __isl_give isl_mat *isl_basic_map_inequalities_matrix(
1398                 __isl_keep isl_basic_map *bmap,
1399                 enum isl_dim_type c1,
1400                 enum isl_dim_type c2, enum isl_dim_type c3,
1401                 enum isl_dim_type c4, enum isl_dim_type c5);
1402
1403 The C<isl_dim_type> arguments dictate the order in which
1404 different kinds of variables appear in the resulting matrix
1405 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1406 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div>.
1407
1408 The number of parameters, input, output or set dimensions can
1409 be obtained using the following functions.
1410
1411         unsigned isl_basic_set_dim(__isl_keep isl_basic_set *bset,
1412                 enum isl_dim_type type);
1413         unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
1414                 enum isl_dim_type type);
1415         unsigned isl_set_dim(__isl_keep isl_set *set,
1416                 enum isl_dim_type type);
1417         unsigned isl_map_dim(__isl_keep isl_map *map,
1418                 enum isl_dim_type type);
1419
1420 To check whether the description of a set or relation depends
1421 on one or more given dimensions, it is not necessary to iterate over all
1422 constraints.  Instead the following functions can be used.
1423
1424         int isl_basic_set_involves_dims(
1425                 __isl_keep isl_basic_set *bset,
1426                 enum isl_dim_type type, unsigned first, unsigned n);
1427         int isl_set_involves_dims(__isl_keep isl_set *set,
1428                 enum isl_dim_type type, unsigned first, unsigned n);
1429         int isl_basic_map_involves_dims(
1430                 __isl_keep isl_basic_map *bmap,
1431                 enum isl_dim_type type, unsigned first, unsigned n);
1432         int isl_map_involves_dims(__isl_keep isl_map *map,
1433                 enum isl_dim_type type, unsigned first, unsigned n);
1434
1435 Similarly, the following functions can be used to check whether
1436 a given dimension is involved in any lower or upper bound.
1437
1438         int isl_set_dim_has_lower_bound(__isl_keep isl_set *set,
1439                 enum isl_dim_type type, unsigned pos);
1440         int isl_set_dim_has_upper_bound(__isl_keep isl_set *set,
1441                 enum isl_dim_type type, unsigned pos);
1442
1443 The identifiers or names of the domain and range spaces of a set
1444 or relation can be read off or set using the following functions.
1445
1446         __isl_give isl_set *isl_set_set_tuple_id(
1447                 __isl_take isl_set *set, __isl_take isl_id *id);
1448         __isl_give isl_set *isl_set_reset_tuple_id(
1449                 __isl_take isl_set *set);
1450         int isl_set_has_tuple_id(__isl_keep isl_set *set);
1451         __isl_give isl_id *isl_set_get_tuple_id(
1452                 __isl_keep isl_set *set);
1453         __isl_give isl_map *isl_map_set_tuple_id(
1454                 __isl_take isl_map *map, enum isl_dim_type type,
1455                 __isl_take isl_id *id);
1456         __isl_give isl_map *isl_map_reset_tuple_id(
1457                 __isl_take isl_map *map, enum isl_dim_type type);
1458         int isl_map_has_tuple_id(__isl_keep isl_map *map,
1459                 enum isl_dim_type type);
1460         __isl_give isl_id *isl_map_get_tuple_id(
1461                 __isl_keep isl_map *map, enum isl_dim_type type);
1462
1463         const char *isl_basic_set_get_tuple_name(
1464                 __isl_keep isl_basic_set *bset);
1465         __isl_give isl_basic_set *isl_basic_set_set_tuple_name(
1466                 __isl_take isl_basic_set *set, const char *s);
1467         const char *isl_set_get_tuple_name(
1468                 __isl_keep isl_set *set);
1469         const char *isl_basic_map_get_tuple_name(
1470                 __isl_keep isl_basic_map *bmap,
1471                 enum isl_dim_type type);
1472         __isl_give isl_basic_map *isl_basic_map_set_tuple_name(
1473                 __isl_take isl_basic_map *bmap,
1474                 enum isl_dim_type type, const char *s);
1475         const char *isl_map_get_tuple_name(
1476                 __isl_keep isl_map *map,
1477                 enum isl_dim_type type);
1478
1479 As with C<isl_space_get_tuple_name>, the value returned points to
1480 an internal data structure.
1481 The identifiers, positions or names of individual dimensions can be
1482 read off using the following functions.
1483
1484         __isl_give isl_set *isl_set_set_dim_id(
1485                 __isl_take isl_set *set, enum isl_dim_type type,
1486                 unsigned pos, __isl_take isl_id *id);
1487         int isl_set_has_dim_id(__isl_keep isl_set *set,
1488                 enum isl_dim_type type, unsigned pos);
1489         __isl_give isl_id *isl_set_get_dim_id(
1490                 __isl_keep isl_set *set, enum isl_dim_type type,
1491                 unsigned pos);
1492         int isl_basic_map_has_dim_id(
1493                 __isl_keep isl_basic_map *bmap,
1494                 enum isl_dim_type type, unsigned pos);
1495         __isl_give isl_map *isl_map_set_dim_id(
1496                 __isl_take isl_map *map, enum isl_dim_type type,
1497                 unsigned pos, __isl_take isl_id *id);
1498         int isl_map_has_dim_id(__isl_keep isl_map *map,
1499                 enum isl_dim_type type, unsigned pos);
1500         __isl_give isl_id *isl_map_get_dim_id(
1501                 __isl_keep isl_map *map, enum isl_dim_type type,
1502                 unsigned pos);
1503
1504         int isl_set_find_dim_by_id(__isl_keep isl_set *set,
1505                 enum isl_dim_type type, __isl_keep isl_id *id);
1506         int isl_map_find_dim_by_id(__isl_keep isl_map *map,
1507                 enum isl_dim_type type, __isl_keep isl_id *id);
1508         int isl_map_find_dim_by_name(__isl_keep isl_map *map,
1509                 enum isl_dim_type type, const char *name);
1510
1511         const char *isl_constraint_get_dim_name(
1512                 __isl_keep isl_constraint *constraint,
1513                 enum isl_dim_type type, unsigned pos);
1514         const char *isl_basic_set_get_dim_name(
1515                 __isl_keep isl_basic_set *bset,
1516                 enum isl_dim_type type, unsigned pos);
1517         const char *isl_set_get_dim_name(
1518                 __isl_keep isl_set *set,
1519                 enum isl_dim_type type, unsigned pos);
1520         const char *isl_basic_map_get_dim_name(
1521                 __isl_keep isl_basic_map *bmap,
1522                 enum isl_dim_type type, unsigned pos);
1523         const char *isl_map_get_dim_name(
1524                 __isl_keep isl_map *map,
1525                 enum isl_dim_type type, unsigned pos);
1526
1527 These functions are mostly useful to obtain the identifiers, positions
1528 or names of the parameters.  Identifiers of individual dimensions are
1529 essentially only useful for printing.  They are ignored by all other
1530 operations and may not be preserved across those operations.
1531
1532 =head2 Properties
1533
1534 =head3 Unary Properties
1535
1536 =over
1537
1538 =item * Emptiness
1539
1540 The following functions test whether the given set or relation
1541 contains any integer points.  The ``plain'' variants do not perform
1542 any computations, but simply check if the given set or relation
1543 is already known to be empty.
1544
1545         int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset);
1546         int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset);
1547         int isl_set_plain_is_empty(__isl_keep isl_set *set);
1548         int isl_set_is_empty(__isl_keep isl_set *set);
1549         int isl_union_set_is_empty(__isl_keep isl_union_set *uset);
1550         int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap);
1551         int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap);
1552         int isl_map_plain_is_empty(__isl_keep isl_map *map);
1553         int isl_map_is_empty(__isl_keep isl_map *map);
1554         int isl_union_map_is_empty(__isl_keep isl_union_map *umap);
1555
1556 =item * Universality
1557
1558         int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset);
1559         int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
1560         int isl_set_plain_is_universe(__isl_keep isl_set *set);
1561
1562 =item * Single-valuedness
1563
1564         int isl_map_is_single_valued(__isl_keep isl_map *map);
1565         int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap);
1566
1567 =item * Injectivity
1568
1569         int isl_map_plain_is_injective(__isl_keep isl_map *map);
1570         int isl_map_is_injective(__isl_keep isl_map *map);
1571         int isl_union_map_plain_is_injective(
1572                 __isl_keep isl_union_map *umap);
1573         int isl_union_map_is_injective(
1574                 __isl_keep isl_union_map *umap);
1575
1576 =item * Bijectivity
1577
1578         int isl_map_is_bijective(__isl_keep isl_map *map);
1579         int isl_union_map_is_bijective(__isl_keep isl_union_map *umap);
1580
1581 =item * Position
1582
1583         int isl_basic_map_plain_is_fixed(
1584                 __isl_keep isl_basic_map *bmap,
1585                 enum isl_dim_type type, unsigned pos,
1586                 isl_int *val);
1587         int isl_set_plain_is_fixed(__isl_keep isl_set *set,
1588                 enum isl_dim_type type, unsigned pos,
1589                 isl_int *val);
1590         int isl_map_plain_is_fixed(__isl_keep isl_map *map,
1591                 enum isl_dim_type type, unsigned pos,
1592                 isl_int *val);
1593
1594 Check if the relation obviously lies on a hyperplane where the given dimension
1595 has a fixed value and if so, return that value in C<*val>.
1596
1597 =item * Space
1598
1599 To check whether a set is a parameter domain, use this function:
1600
1601         int isl_set_is_params(__isl_keep isl_set *set);
1602         int isl_union_set_is_params(
1603                 __isl_keep isl_union_set *uset);
1604
1605 =item * Wrapping
1606
1607 The following functions check whether the domain of the given
1608 (basic) set is a wrapped relation.
1609
1610         int isl_basic_set_is_wrapping(
1611                 __isl_keep isl_basic_set *bset);
1612         int isl_set_is_wrapping(__isl_keep isl_set *set);
1613
1614 =item * Internal Product
1615
1616         int isl_basic_map_can_zip(
1617                 __isl_keep isl_basic_map *bmap);
1618         int isl_map_can_zip(__isl_keep isl_map *map);
1619
1620 Check whether the product of domain and range of the given relation
1621 can be computed,
1622 i.e., whether both domain and range are nested relations.
1623
1624 =back
1625
1626 =head3 Binary Properties
1627
1628 =over
1629
1630 =item * Equality
1631
1632         int isl_set_plain_is_equal(__isl_keep isl_set *set1,
1633                 __isl_keep isl_set *set2);
1634         int isl_set_is_equal(__isl_keep isl_set *set1,
1635                 __isl_keep isl_set *set2);
1636         int isl_union_set_is_equal(
1637                 __isl_keep isl_union_set *uset1,
1638                 __isl_keep isl_union_set *uset2);
1639         int isl_basic_map_is_equal(
1640                 __isl_keep isl_basic_map *bmap1,
1641                 __isl_keep isl_basic_map *bmap2);
1642         int isl_map_is_equal(__isl_keep isl_map *map1,
1643                 __isl_keep isl_map *map2);
1644         int isl_map_plain_is_equal(__isl_keep isl_map *map1,
1645                 __isl_keep isl_map *map2);
1646         int isl_union_map_is_equal(
1647                 __isl_keep isl_union_map *umap1,
1648                 __isl_keep isl_union_map *umap2);
1649
1650 =item * Disjointness
1651
1652         int isl_set_plain_is_disjoint(__isl_keep isl_set *set1,
1653                 __isl_keep isl_set *set2);
1654
1655 =item * Subset
1656
1657         int isl_set_is_subset(__isl_keep isl_set *set1,
1658                 __isl_keep isl_set *set2);
1659         int isl_set_is_strict_subset(
1660                 __isl_keep isl_set *set1,
1661                 __isl_keep isl_set *set2);
1662         int isl_union_set_is_subset(
1663                 __isl_keep isl_union_set *uset1,
1664                 __isl_keep isl_union_set *uset2);
1665         int isl_union_set_is_strict_subset(
1666                 __isl_keep isl_union_set *uset1,
1667                 __isl_keep isl_union_set *uset2);
1668         int isl_basic_map_is_subset(
1669                 __isl_keep isl_basic_map *bmap1,
1670                 __isl_keep isl_basic_map *bmap2);
1671         int isl_basic_map_is_strict_subset(
1672                 __isl_keep isl_basic_map *bmap1,
1673                 __isl_keep isl_basic_map *bmap2);
1674         int isl_map_is_subset(
1675                 __isl_keep isl_map *map1,
1676                 __isl_keep isl_map *map2);
1677         int isl_map_is_strict_subset(
1678                 __isl_keep isl_map *map1,
1679                 __isl_keep isl_map *map2);
1680         int isl_union_map_is_subset(
1681                 __isl_keep isl_union_map *umap1,
1682                 __isl_keep isl_union_map *umap2);
1683         int isl_union_map_is_strict_subset(
1684                 __isl_keep isl_union_map *umap1,
1685                 __isl_keep isl_union_map *umap2);
1686
1687 =back
1688
1689 =head2 Unary Operations
1690
1691 =over
1692
1693 =item * Complement
1694
1695         __isl_give isl_set *isl_set_complement(
1696                 __isl_take isl_set *set);
1697
1698 =item * Inverse map
1699
1700         __isl_give isl_basic_map *isl_basic_map_reverse(
1701                 __isl_take isl_basic_map *bmap);
1702         __isl_give isl_map *isl_map_reverse(
1703                 __isl_take isl_map *map);
1704         __isl_give isl_union_map *isl_union_map_reverse(
1705                 __isl_take isl_union_map *umap);
1706
1707 =item * Projection
1708
1709         __isl_give isl_basic_set *isl_basic_set_project_out(
1710                 __isl_take isl_basic_set *bset,
1711                 enum isl_dim_type type, unsigned first, unsigned n);
1712         __isl_give isl_basic_map *isl_basic_map_project_out(
1713                 __isl_take isl_basic_map *bmap,
1714                 enum isl_dim_type type, unsigned first, unsigned n);
1715         __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
1716                 enum isl_dim_type type, unsigned first, unsigned n);
1717         __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
1718                 enum isl_dim_type type, unsigned first, unsigned n);
1719         __isl_give isl_basic_set *isl_basic_set_params(
1720                 __isl_take isl_basic_set *bset);
1721         __isl_give isl_basic_set *isl_basic_map_domain(
1722                 __isl_take isl_basic_map *bmap);
1723         __isl_give isl_basic_set *isl_basic_map_range(
1724                 __isl_take isl_basic_map *bmap);
1725         __isl_give isl_set *isl_set_params(__isl_take isl_set *set);
1726         __isl_give isl_set *isl_map_params(__isl_take isl_map *map);
1727         __isl_give isl_set *isl_map_domain(
1728                 __isl_take isl_map *bmap);
1729         __isl_give isl_set *isl_map_range(
1730                 __isl_take isl_map *map);
1731         __isl_give isl_set *isl_union_set_params(
1732                 __isl_take isl_union_set *uset);
1733         __isl_give isl_set *isl_union_map_params(
1734                 __isl_take isl_union_map *umap);
1735         __isl_give isl_union_set *isl_union_map_domain(
1736                 __isl_take isl_union_map *umap);
1737         __isl_give isl_union_set *isl_union_map_range(
1738                 __isl_take isl_union_map *umap);
1739
1740         __isl_give isl_basic_map *isl_basic_map_domain_map(
1741                 __isl_take isl_basic_map *bmap);
1742         __isl_give isl_basic_map *isl_basic_map_range_map(
1743                 __isl_take isl_basic_map *bmap);
1744         __isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map);
1745         __isl_give isl_map *isl_map_range_map(__isl_take isl_map *map);
1746         __isl_give isl_union_map *isl_union_map_domain_map(
1747                 __isl_take isl_union_map *umap);
1748         __isl_give isl_union_map *isl_union_map_range_map(
1749                 __isl_take isl_union_map *umap);
1750
1751 The functions above construct a (basic, regular or union) relation
1752 that maps (a wrapped version of) the input relation to its domain or range.
1753
1754 =item * Elimination
1755
1756         __isl_give isl_set *isl_set_eliminate(
1757                 __isl_take isl_set *set, enum isl_dim_type type,
1758                 unsigned first, unsigned n);
1759         __isl_give isl_basic_map *isl_basic_map_eliminate(
1760                 __isl_take isl_basic_map *bmap,
1761                 enum isl_dim_type type,
1762                 unsigned first, unsigned n);
1763
1764 Eliminate the coefficients for the given dimensions from the constraints,
1765 without removing the dimensions.
1766
1767 =item * Slicing
1768
1769         __isl_give isl_basic_set *isl_basic_set_fix(
1770                 __isl_take isl_basic_set *bset,
1771                 enum isl_dim_type type, unsigned pos,
1772                 isl_int value);
1773         __isl_give isl_basic_set *isl_basic_set_fix_si(
1774                 __isl_take isl_basic_set *bset,
1775                 enum isl_dim_type type, unsigned pos, int value);
1776         __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
1777                 enum isl_dim_type type, unsigned pos,
1778                 isl_int value);
1779         __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
1780                 enum isl_dim_type type, unsigned pos, int value);
1781         __isl_give isl_basic_map *isl_basic_map_fix_si(
1782                 __isl_take isl_basic_map *bmap,
1783                 enum isl_dim_type type, unsigned pos, int value);
1784         __isl_give isl_map *isl_map_fix_si(__isl_take isl_map *map,
1785                 enum isl_dim_type type, unsigned pos, int value);
1786
1787 Intersect the set or relation with the hyperplane where the given
1788 dimension has the fixed given value.
1789
1790         __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
1791                 __isl_take isl_basic_map *bmap,
1792                 enum isl_dim_type type, unsigned pos, int value);
1793         __isl_give isl_set *isl_set_lower_bound_si(
1794                 __isl_take isl_set *set,
1795                 enum isl_dim_type type, unsigned pos, int value);
1796         __isl_give isl_map *isl_map_lower_bound_si(
1797                 __isl_take isl_map *map,
1798                 enum isl_dim_type type, unsigned pos, int value);
1799         __isl_give isl_set *isl_set_upper_bound_si(
1800                 __isl_take isl_set *set,
1801                 enum isl_dim_type type, unsigned pos, int value);
1802         __isl_give isl_map *isl_map_upper_bound_si(
1803                 __isl_take isl_map *map,
1804                 enum isl_dim_type type, unsigned pos, int value);
1805
1806 Intersect the set or relation with the half-space where the given
1807 dimension has a value bounded the fixed given value.
1808
1809         __isl_give isl_set *isl_set_equate(__isl_take isl_set *set,
1810                 enum isl_dim_type type1, int pos1,
1811                 enum isl_dim_type type2, int pos2);
1812         __isl_give isl_map *isl_map_equate(__isl_take isl_map *map,
1813                 enum isl_dim_type type1, int pos1,
1814                 enum isl_dim_type type2, int pos2);
1815
1816 Intersect the set or relation with the hyperplane where the given
1817 dimensions are equal to each other.
1818
1819         __isl_give isl_map *isl_map_oppose(__isl_take isl_map *map,
1820                 enum isl_dim_type type1, int pos1,
1821                 enum isl_dim_type type2, int pos2);
1822
1823 Intersect the relation with the hyperplane where the given
1824 dimensions have opposite values.
1825
1826 =item * Identity
1827
1828         __isl_give isl_map *isl_set_identity(
1829                 __isl_take isl_set *set);
1830         __isl_give isl_union_map *isl_union_set_identity(
1831                 __isl_take isl_union_set *uset);
1832
1833 Construct an identity relation on the given (union) set.
1834
1835 =item * Deltas
1836
1837         __isl_give isl_basic_set *isl_basic_map_deltas(
1838                 __isl_take isl_basic_map *bmap);
1839         __isl_give isl_set *isl_map_deltas(__isl_take isl_map *map);
1840         __isl_give isl_union_set *isl_union_map_deltas(
1841                 __isl_take isl_union_map *umap);
1842
1843 These functions return a (basic) set containing the differences
1844 between image elements and corresponding domain elements in the input.
1845
1846         __isl_give isl_basic_map *isl_basic_map_deltas_map(
1847                 __isl_take isl_basic_map *bmap);
1848         __isl_give isl_map *isl_map_deltas_map(
1849                 __isl_take isl_map *map);
1850         __isl_give isl_union_map *isl_union_map_deltas_map(
1851                 __isl_take isl_union_map *umap);
1852
1853 The functions above construct a (basic, regular or union) relation
1854 that maps (a wrapped version of) the input relation to its delta set.
1855
1856 =item * Coalescing
1857
1858 Simplify the representation of a set or relation by trying
1859 to combine pairs of basic sets or relations into a single
1860 basic set or relation.
1861
1862         __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set);
1863         __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map);
1864         __isl_give isl_union_set *isl_union_set_coalesce(
1865                 __isl_take isl_union_set *uset);
1866         __isl_give isl_union_map *isl_union_map_coalesce(
1867                 __isl_take isl_union_map *umap);
1868
1869 =item * Detecting equalities
1870
1871         __isl_give isl_basic_set *isl_basic_set_detect_equalities(
1872                 __isl_take isl_basic_set *bset);
1873         __isl_give isl_basic_map *isl_basic_map_detect_equalities(
1874                 __isl_take isl_basic_map *bmap);
1875         __isl_give isl_set *isl_set_detect_equalities(
1876                 __isl_take isl_set *set);
1877         __isl_give isl_map *isl_map_detect_equalities(
1878                 __isl_take isl_map *map);
1879         __isl_give isl_union_set *isl_union_set_detect_equalities(
1880                 __isl_take isl_union_set *uset);
1881         __isl_give isl_union_map *isl_union_map_detect_equalities(
1882                 __isl_take isl_union_map *umap);
1883
1884 Simplify the representation of a set or relation by detecting implicit
1885 equalities.
1886
1887 =item * Removing redundant constraints
1888
1889         __isl_give isl_basic_set *isl_basic_set_remove_redundancies(
1890                 __isl_take isl_basic_set *bset);
1891         __isl_give isl_set *isl_set_remove_redundancies(
1892                 __isl_take isl_set *set);
1893         __isl_give isl_basic_map *isl_basic_map_remove_redundancies(
1894                 __isl_take isl_basic_map *bmap);
1895         __isl_give isl_map *isl_map_remove_redundancies(
1896                 __isl_take isl_map *map);
1897
1898 =item * Convex hull
1899
1900         __isl_give isl_basic_set *isl_set_convex_hull(
1901                 __isl_take isl_set *set);
1902         __isl_give isl_basic_map *isl_map_convex_hull(
1903                 __isl_take isl_map *map);
1904
1905 If the input set or relation has any existentially quantified
1906 variables, then the result of these operations is currently undefined.
1907
1908 =item * Simple hull
1909
1910         __isl_give isl_basic_set *isl_set_simple_hull(
1911                 __isl_take isl_set *set);
1912         __isl_give isl_basic_map *isl_map_simple_hull(
1913                 __isl_take isl_map *map);
1914         __isl_give isl_union_map *isl_union_map_simple_hull(
1915                 __isl_take isl_union_map *umap);
1916
1917 These functions compute a single basic set or relation
1918 that contains the whole input set or relation.
1919 In particular, the output is described by translates
1920 of the constraints describing the basic sets or relations in the input.
1921
1922 =begin latex
1923
1924 (See \autoref{s:simple hull}.)
1925
1926 =end latex
1927
1928 =item * Affine hull
1929
1930         __isl_give isl_basic_set *isl_basic_set_affine_hull(
1931                 __isl_take isl_basic_set *bset);
1932         __isl_give isl_basic_set *isl_set_affine_hull(
1933                 __isl_take isl_set *set);
1934         __isl_give isl_union_set *isl_union_set_affine_hull(
1935                 __isl_take isl_union_set *uset);
1936         __isl_give isl_basic_map *isl_basic_map_affine_hull(
1937                 __isl_take isl_basic_map *bmap);
1938         __isl_give isl_basic_map *isl_map_affine_hull(
1939                 __isl_take isl_map *map);
1940         __isl_give isl_union_map *isl_union_map_affine_hull(
1941                 __isl_take isl_union_map *umap);
1942
1943 In case of union sets and relations, the affine hull is computed
1944 per space.
1945
1946 =item * Polyhedral hull
1947
1948         __isl_give isl_basic_set *isl_set_polyhedral_hull(
1949                 __isl_take isl_set *set);
1950         __isl_give isl_basic_map *isl_map_polyhedral_hull(
1951                 __isl_take isl_map *map);
1952         __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1953                 __isl_take isl_union_set *uset);
1954         __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1955                 __isl_take isl_union_map *umap);
1956
1957 These functions compute a single basic set or relation
1958 not involving any existentially quantified variables
1959 that contains the whole input set or relation.
1960 In case of union sets and relations, the polyhedral hull is computed
1961 per space.
1962
1963 =item * Optimization
1964
1965         #include <isl/ilp.h>
1966         enum isl_lp_result isl_basic_set_max(
1967                 __isl_keep isl_basic_set *bset,
1968                 __isl_keep isl_aff *obj, isl_int *opt)
1969         enum isl_lp_result isl_set_min(__isl_keep isl_set *set,
1970                 __isl_keep isl_aff *obj, isl_int *opt);
1971         enum isl_lp_result isl_set_max(__isl_keep isl_set *set,
1972                 __isl_keep isl_aff *obj, isl_int *opt);
1973
1974 Compute the minimum or maximum of the integer affine expression C<obj>
1975 over the points in C<set>, returning the result in C<opt>.
1976 The return value may be one of C<isl_lp_error>,
1977 C<isl_lp_ok>, C<isl_lp_unbounded> or C<isl_lp_empty>.
1978
1979 =item * Parametric optimization
1980
1981         __isl_give isl_pw_aff *isl_set_dim_min(
1982                 __isl_take isl_set *set, int pos);
1983         __isl_give isl_pw_aff *isl_set_dim_max(
1984                 __isl_take isl_set *set, int pos);
1985         __isl_give isl_pw_aff *isl_map_dim_max(
1986                 __isl_take isl_map *map, int pos);
1987
1988 Compute the minimum or maximum of the given set or output dimension
1989 as a function of the parameters (and input dimensions), but independently
1990 of the other set or output dimensions.
1991 For lexicographic optimization, see L<"Lexicographic Optimization">.
1992
1993 =item * Dual
1994
1995 The following functions compute either the set of (rational) coefficient
1996 values of valid constraints for the given set or the set of (rational)
1997 values satisfying the constraints with coefficients from the given set.
1998 Internally, these two sets of functions perform essentially the
1999 same operations, except that the set of coefficients is assumed to
2000 be a cone, while the set of values may be any polyhedron.
2001 The current implementation is based on the Farkas lemma and
2002 Fourier-Motzkin elimination, but this may change or be made optional
2003 in future.  In particular, future implementations may use different
2004 dualization algorithms or skip the elimination step.
2005
2006         __isl_give isl_basic_set *isl_basic_set_coefficients(
2007                 __isl_take isl_basic_set *bset);
2008         __isl_give isl_basic_set *isl_set_coefficients(
2009                 __isl_take isl_set *set);
2010         __isl_give isl_union_set *isl_union_set_coefficients(
2011                 __isl_take isl_union_set *bset);
2012         __isl_give isl_basic_set *isl_basic_set_solutions(
2013                 __isl_take isl_basic_set *bset);
2014         __isl_give isl_basic_set *isl_set_solutions(
2015                 __isl_take isl_set *set);
2016         __isl_give isl_union_set *isl_union_set_solutions(
2017                 __isl_take isl_union_set *bset);
2018
2019 =item * Power
2020
2021         __isl_give isl_map *isl_map_power(__isl_take isl_map *map,
2022                 int *exact);
2023         __isl_give isl_union_map *isl_union_map_power(
2024                 __isl_take isl_union_map *umap, int *exact);
2025
2026 Compute a parametric representation for all positive powers I<k> of C<map>.
2027 The result maps I<k> to a nested relation corresponding to the
2028 I<k>th power of C<map>.
2029 The result may be an overapproximation.  If the result is known to be exact,
2030 then C<*exact> is set to C<1>.
2031
2032 =item * Transitive closure
2033
2034         __isl_give isl_map *isl_map_transitive_closure(
2035                 __isl_take isl_map *map, int *exact);
2036         __isl_give isl_union_map *isl_union_map_transitive_closure(
2037                 __isl_take isl_union_map *umap, int *exact);
2038
2039 Compute the transitive closure of C<map>.
2040 The result may be an overapproximation.  If the result is known to be exact,
2041 then C<*exact> is set to C<1>.
2042
2043 =item * Reaching path lengths
2044
2045         __isl_give isl_map *isl_map_reaching_path_lengths(
2046                 __isl_take isl_map *map, int *exact);
2047
2048 Compute a relation that maps each element in the range of C<map>
2049 to the lengths of all paths composed of edges in C<map> that
2050 end up in the given element.
2051 The result may be an overapproximation.  If the result is known to be exact,
2052 then C<*exact> is set to C<1>.
2053 To compute the I<maximal> path length, the resulting relation
2054 should be postprocessed by C<isl_map_lexmax>.
2055 In particular, if the input relation is a dependence relation
2056 (mapping sources to sinks), then the maximal path length corresponds
2057 to the free schedule.
2058 Note, however, that C<isl_map_lexmax> expects the maximum to be
2059 finite, so if the path lengths are unbounded (possibly due to
2060 the overapproximation), then you will get an error message.
2061
2062 =item * Wrapping
2063
2064         __isl_give isl_basic_set *isl_basic_map_wrap(
2065                 __isl_take isl_basic_map *bmap);
2066         __isl_give isl_set *isl_map_wrap(
2067                 __isl_take isl_map *map);
2068         __isl_give isl_union_set *isl_union_map_wrap(
2069                 __isl_take isl_union_map *umap);
2070         __isl_give isl_basic_map *isl_basic_set_unwrap(
2071                 __isl_take isl_basic_set *bset);
2072         __isl_give isl_map *isl_set_unwrap(
2073                 __isl_take isl_set *set);
2074         __isl_give isl_union_map *isl_union_set_unwrap(
2075                 __isl_take isl_union_set *uset);
2076
2077 =item * Flattening
2078
2079 Remove any internal structure of domain (and range) of the given
2080 set or relation.  If there is any such internal structure in the input,
2081 then the name of the space is also removed.
2082
2083         __isl_give isl_basic_set *isl_basic_set_flatten(
2084                 __isl_take isl_basic_set *bset);
2085         __isl_give isl_set *isl_set_flatten(
2086                 __isl_take isl_set *set);
2087         __isl_give isl_basic_map *isl_basic_map_flatten_domain(
2088                 __isl_take isl_basic_map *bmap);
2089         __isl_give isl_basic_map *isl_basic_map_flatten_range(
2090                 __isl_take isl_basic_map *bmap);
2091         __isl_give isl_map *isl_map_flatten_range(
2092                 __isl_take isl_map *map);
2093         __isl_give isl_map *isl_map_flatten_domain(
2094                 __isl_take isl_map *map);
2095         __isl_give isl_basic_map *isl_basic_map_flatten(
2096                 __isl_take isl_basic_map *bmap);
2097         __isl_give isl_map *isl_map_flatten(
2098                 __isl_take isl_map *map);
2099
2100         __isl_give isl_map *isl_set_flatten_map(
2101                 __isl_take isl_set *set);
2102
2103 The function above constructs a relation
2104 that maps the input set to a flattened version of the set.
2105
2106 =item * Lifting
2107
2108 Lift the input set to a space with extra dimensions corresponding
2109 to the existentially quantified variables in the input.
2110 In particular, the result lives in a wrapped map where the domain
2111 is the original space and the range corresponds to the original
2112 existentially quantified variables.
2113
2114         __isl_give isl_basic_set *isl_basic_set_lift(
2115                 __isl_take isl_basic_set *bset);
2116         __isl_give isl_set *isl_set_lift(
2117                 __isl_take isl_set *set);
2118         __isl_give isl_union_set *isl_union_set_lift(
2119                 __isl_take isl_union_set *uset);
2120
2121 Given a local space that contains the existentially quantified
2122 variables of a set, a basic relation that, when applied to
2123 a basic set, has essentially the same effect as C<isl_basic_set_lift>,
2124 can be constructed using the following function.
2125
2126         #include <isl/local_space.h>
2127         __isl_give isl_basic_map *isl_local_space_lifting(
2128                 __isl_take isl_local_space *ls);
2129
2130 =item * Internal Product
2131
2132         __isl_give isl_basic_map *isl_basic_map_zip(
2133                 __isl_take isl_basic_map *bmap);
2134         __isl_give isl_map *isl_map_zip(
2135                 __isl_take isl_map *map);
2136         __isl_give isl_union_map *isl_union_map_zip(
2137                 __isl_take isl_union_map *umap);
2138
2139 Given a relation with nested relations for domain and range,
2140 interchange the range of the domain with the domain of the range.
2141
2142 =item * Aligning parameters
2143
2144         __isl_give isl_set *isl_set_align_params(
2145                 __isl_take isl_set *set,
2146                 __isl_take isl_space *model);
2147         __isl_give isl_map *isl_map_align_params(
2148                 __isl_take isl_map *map,
2149                 __isl_take isl_space *model);
2150
2151 Change the order of the parameters of the given set or relation
2152 such that the first parameters match those of C<model>.
2153 This may involve the introduction of extra parameters.
2154 All parameters need to be named.
2155
2156 =item * Dimension manipulation
2157
2158         __isl_give isl_set *isl_set_add_dims(
2159                 __isl_take isl_set *set,
2160                 enum isl_dim_type type, unsigned n);
2161         __isl_give isl_map *isl_map_add_dims(
2162                 __isl_take isl_map *map,
2163                 enum isl_dim_type type, unsigned n);
2164         __isl_give isl_set *isl_set_insert_dims(
2165                 __isl_take isl_set *set,
2166                 enum isl_dim_type type, unsigned pos, unsigned n);
2167         __isl_give isl_map *isl_map_insert_dims(
2168                 __isl_take isl_map *map,
2169                 enum isl_dim_type type, unsigned pos, unsigned n);
2170         __isl_give isl_basic_set *isl_basic_set_move_dims(
2171                 __isl_take isl_basic_set *bset,
2172                 enum isl_dim_type dst_type, unsigned dst_pos,
2173                 enum isl_dim_type src_type, unsigned src_pos,
2174                 unsigned n);
2175         __isl_give isl_basic_map *isl_basic_map_move_dims(
2176                 __isl_take isl_basic_map *bmap,
2177                 enum isl_dim_type dst_type, unsigned dst_pos,
2178                 enum isl_dim_type src_type, unsigned src_pos,
2179                 unsigned n);
2180         __isl_give isl_set *isl_set_move_dims(
2181                 __isl_take isl_set *set,
2182                 enum isl_dim_type dst_type, unsigned dst_pos,
2183                 enum isl_dim_type src_type, unsigned src_pos,
2184                 unsigned n);
2185         __isl_give isl_map *isl_map_move_dims(
2186                 __isl_take isl_map *map,
2187                 enum isl_dim_type dst_type, unsigned dst_pos,
2188                 enum isl_dim_type src_type, unsigned src_pos,
2189                 unsigned n);
2190
2191 It is usually not advisable to directly change the (input or output)
2192 space of a set or a relation as this removes the name and the internal
2193 structure of the space.  However, the above functions can be useful
2194 to add new parameters, assuming
2195 C<isl_set_align_params> and C<isl_map_align_params>
2196 are not sufficient.
2197
2198 =back
2199
2200 =head2 Binary Operations
2201
2202 The two arguments of a binary operation not only need to live
2203 in the same C<isl_ctx>, they currently also need to have
2204 the same (number of) parameters.
2205
2206 =head3 Basic Operations
2207
2208 =over
2209
2210 =item * Intersection
2211
2212         __isl_give isl_basic_set *isl_basic_set_intersect_params(
2213                 __isl_take isl_basic_set *bset1,
2214                 __isl_take isl_basic_set *bset2);
2215         __isl_give isl_basic_set *isl_basic_set_intersect(
2216                 __isl_take isl_basic_set *bset1,
2217                 __isl_take isl_basic_set *bset2);
2218         __isl_give isl_set *isl_set_intersect_params(
2219                 __isl_take isl_set *set,
2220                 __isl_take isl_set *params);
2221         __isl_give isl_set *isl_set_intersect(
2222                 __isl_take isl_set *set1,
2223                 __isl_take isl_set *set2);
2224         __isl_give isl_union_set *isl_union_set_intersect_params(
2225                 __isl_take isl_union_set *uset,
2226                 __isl_take isl_set *set);
2227         __isl_give isl_union_map *isl_union_map_intersect_params(
2228                 __isl_take isl_union_map *umap,
2229                 __isl_take isl_set *set);
2230         __isl_give isl_union_set *isl_union_set_intersect(
2231                 __isl_take isl_union_set *uset1,
2232                 __isl_take isl_union_set *uset2);
2233         __isl_give isl_basic_map *isl_basic_map_intersect_domain(
2234                 __isl_take isl_basic_map *bmap,
2235                 __isl_take isl_basic_set *bset);
2236         __isl_give isl_basic_map *isl_basic_map_intersect_range(
2237                 __isl_take isl_basic_map *bmap,
2238                 __isl_take isl_basic_set *bset);
2239         __isl_give isl_basic_map *isl_basic_map_intersect(
2240                 __isl_take isl_basic_map *bmap1,
2241                 __isl_take isl_basic_map *bmap2);
2242         __isl_give isl_map *isl_map_intersect_params(
2243                 __isl_take isl_map *map,
2244                 __isl_take isl_set *params);
2245         __isl_give isl_map *isl_map_intersect_domain(
2246                 __isl_take isl_map *map,
2247                 __isl_take isl_set *set);
2248         __isl_give isl_map *isl_map_intersect_range(
2249                 __isl_take isl_map *map,
2250                 __isl_take isl_set *set);
2251         __isl_give isl_map *isl_map_intersect(
2252                 __isl_take isl_map *map1,
2253                 __isl_take isl_map *map2);
2254         __isl_give isl_union_map *isl_union_map_intersect_domain(
2255                 __isl_take isl_union_map *umap,
2256                 __isl_take isl_union_set *uset);
2257         __isl_give isl_union_map *isl_union_map_intersect_range(
2258                 __isl_take isl_union_map *umap,
2259                 __isl_take isl_union_set *uset);
2260         __isl_give isl_union_map *isl_union_map_intersect(
2261                 __isl_take isl_union_map *umap1,
2262                 __isl_take isl_union_map *umap2);
2263
2264 =item * Union
2265
2266         __isl_give isl_set *isl_basic_set_union(
2267                 __isl_take isl_basic_set *bset1,
2268                 __isl_take isl_basic_set *bset2);
2269         __isl_give isl_map *isl_basic_map_union(
2270                 __isl_take isl_basic_map *bmap1,
2271                 __isl_take isl_basic_map *bmap2);
2272         __isl_give isl_set *isl_set_union(
2273                 __isl_take isl_set *set1,
2274                 __isl_take isl_set *set2);
2275         __isl_give isl_map *isl_map_union(
2276                 __isl_take isl_map *map1,
2277                 __isl_take isl_map *map2);
2278         __isl_give isl_union_set *isl_union_set_union(
2279                 __isl_take isl_union_set *uset1,
2280                 __isl_take isl_union_set *uset2);
2281         __isl_give isl_union_map *isl_union_map_union(
2282                 __isl_take isl_union_map *umap1,
2283                 __isl_take isl_union_map *umap2);
2284
2285 =item * Set difference
2286
2287         __isl_give isl_set *isl_set_subtract(
2288                 __isl_take isl_set *set1,
2289                 __isl_take isl_set *set2);
2290         __isl_give isl_map *isl_map_subtract(
2291                 __isl_take isl_map *map1,
2292                 __isl_take isl_map *map2);
2293         __isl_give isl_map *isl_map_subtract_domain(
2294                 __isl_take isl_map *map,
2295                 __isl_take isl_set *dom);
2296         __isl_give isl_map *isl_map_subtract_range(
2297                 __isl_take isl_map *map,
2298                 __isl_take isl_set *dom);
2299         __isl_give isl_union_set *isl_union_set_subtract(
2300                 __isl_take isl_union_set *uset1,
2301                 __isl_take isl_union_set *uset2);
2302         __isl_give isl_union_map *isl_union_map_subtract(
2303                 __isl_take isl_union_map *umap1,
2304                 __isl_take isl_union_map *umap2);
2305
2306 =item * Application
2307
2308         __isl_give isl_basic_set *isl_basic_set_apply(
2309                 __isl_take isl_basic_set *bset,
2310                 __isl_take isl_basic_map *bmap);
2311         __isl_give isl_set *isl_set_apply(
2312                 __isl_take isl_set *set,
2313                 __isl_take isl_map *map);
2314         __isl_give isl_union_set *isl_union_set_apply(
2315                 __isl_take isl_union_set *uset,
2316                 __isl_take isl_union_map *umap);
2317         __isl_give isl_basic_map *isl_basic_map_apply_domain(
2318                 __isl_take isl_basic_map *bmap1,
2319                 __isl_take isl_basic_map *bmap2);
2320         __isl_give isl_basic_map *isl_basic_map_apply_range(
2321                 __isl_take isl_basic_map *bmap1,
2322                 __isl_take isl_basic_map *bmap2);
2323         __isl_give isl_map *isl_map_apply_domain(
2324                 __isl_take isl_map *map1,
2325                 __isl_take isl_map *map2);
2326         __isl_give isl_union_map *isl_union_map_apply_domain(
2327                 __isl_take isl_union_map *umap1,
2328                 __isl_take isl_union_map *umap2);
2329         __isl_give isl_map *isl_map_apply_range(
2330                 __isl_take isl_map *map1,
2331                 __isl_take isl_map *map2);
2332         __isl_give isl_union_map *isl_union_map_apply_range(
2333                 __isl_take isl_union_map *umap1,
2334                 __isl_take isl_union_map *umap2);
2335
2336 =item * Cartesian Product
2337
2338         __isl_give isl_set *isl_set_product(
2339                 __isl_take isl_set *set1,
2340                 __isl_take isl_set *set2);
2341         __isl_give isl_union_set *isl_union_set_product(
2342                 __isl_take isl_union_set *uset1,
2343                 __isl_take isl_union_set *uset2);
2344         __isl_give isl_basic_map *isl_basic_map_domain_product(
2345                 __isl_take isl_basic_map *bmap1,
2346                 __isl_take isl_basic_map *bmap2);
2347         __isl_give isl_basic_map *isl_basic_map_range_product(
2348                 __isl_take isl_basic_map *bmap1,
2349                 __isl_take isl_basic_map *bmap2);
2350         __isl_give isl_map *isl_map_domain_product(
2351                 __isl_take isl_map *map1,
2352                 __isl_take isl_map *map2);
2353         __isl_give isl_map *isl_map_range_product(
2354                 __isl_take isl_map *map1,
2355                 __isl_take isl_map *map2);
2356         __isl_give isl_union_map *isl_union_map_range_product(
2357                 __isl_take isl_union_map *umap1,
2358                 __isl_take isl_union_map *umap2);
2359         __isl_give isl_map *isl_map_product(
2360                 __isl_take isl_map *map1,
2361                 __isl_take isl_map *map2);
2362         __isl_give isl_union_map *isl_union_map_product(
2363                 __isl_take isl_union_map *umap1,
2364                 __isl_take isl_union_map *umap2);
2365
2366 The above functions compute the cross product of the given
2367 sets or relations.  The domains and ranges of the results
2368 are wrapped maps between domains and ranges of the inputs.
2369 To obtain a ``flat'' product, use the following functions
2370 instead.
2371
2372         __isl_give isl_basic_set *isl_basic_set_flat_product(
2373                 __isl_take isl_basic_set *bset1,
2374                 __isl_take isl_basic_set *bset2);
2375         __isl_give isl_set *isl_set_flat_product(
2376                 __isl_take isl_set *set1,
2377                 __isl_take isl_set *set2);
2378         __isl_give isl_basic_map *isl_basic_map_flat_range_product(
2379                 __isl_take isl_basic_map *bmap1,
2380                 __isl_take isl_basic_map *bmap2);
2381         __isl_give isl_map *isl_map_flat_domain_product(
2382                 __isl_take isl_map *map1,
2383                 __isl_take isl_map *map2);
2384         __isl_give isl_map *isl_map_flat_range_product(
2385                 __isl_take isl_map *map1,
2386                 __isl_take isl_map *map2);
2387         __isl_give isl_union_map *isl_union_map_flat_range_product(
2388                 __isl_take isl_union_map *umap1,
2389                 __isl_take isl_union_map *umap2);
2390         __isl_give isl_basic_map *isl_basic_map_flat_product(
2391                 __isl_take isl_basic_map *bmap1,
2392                 __isl_take isl_basic_map *bmap2);
2393         __isl_give isl_map *isl_map_flat_product(
2394                 __isl_take isl_map *map1,
2395                 __isl_take isl_map *map2);
2396
2397 =item * Simplification
2398
2399         __isl_give isl_basic_set *isl_basic_set_gist(
2400                 __isl_take isl_basic_set *bset,
2401                 __isl_take isl_basic_set *context);
2402         __isl_give isl_set *isl_set_gist(__isl_take isl_set *set,
2403                 __isl_take isl_set *context);
2404         __isl_give isl_set *isl_set_gist_params(
2405                 __isl_take isl_set *set,
2406                 __isl_take isl_set *context);
2407         __isl_give isl_union_set *isl_union_set_gist(
2408                 __isl_take isl_union_set *uset,
2409                 __isl_take isl_union_set *context);
2410         __isl_give isl_union_set *isl_union_set_gist_params(
2411                 __isl_take isl_union_set *uset,
2412                 __isl_take isl_set *set);
2413         __isl_give isl_basic_map *isl_basic_map_gist(
2414                 __isl_take isl_basic_map *bmap,
2415                 __isl_take isl_basic_map *context);
2416         __isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
2417                 __isl_take isl_map *context);
2418         __isl_give isl_map *isl_map_gist_params(
2419                 __isl_take isl_map *map,
2420                 __isl_take isl_set *context);
2421         __isl_give isl_map *isl_map_gist_domain(
2422                 __isl_take isl_map *map,
2423                 __isl_take isl_set *context);
2424         __isl_give isl_map *isl_map_gist_range(
2425                 __isl_take isl_map *map,
2426                 __isl_take isl_set *context);
2427         __isl_give isl_union_map *isl_union_map_gist(
2428                 __isl_take isl_union_map *umap,
2429                 __isl_take isl_union_map *context);
2430         __isl_give isl_union_map *isl_union_map_gist_params(
2431                 __isl_take isl_union_map *umap,
2432                 __isl_take isl_set *set);
2433         __isl_give isl_union_map *isl_union_map_gist_domain(
2434                 __isl_take isl_union_map *umap,
2435                 __isl_take isl_union_set *uset);
2436
2437 The gist operation returns a set or relation that has the
2438 same intersection with the context as the input set or relation.
2439 Any implicit equality in the intersection is made explicit in the result,
2440 while all inequalities that are redundant with respect to the intersection
2441 are removed.
2442 In case of union sets and relations, the gist operation is performed
2443 per space.
2444
2445 =back
2446
2447 =head3 Lexicographic Optimization
2448
2449 Given a (basic) set C<set> (or C<bset>) and a zero-dimensional domain C<dom>,
2450 the following functions
2451 compute a set that contains the lexicographic minimum or maximum
2452 of the elements in C<set> (or C<bset>) for those values of the parameters
2453 that satisfy C<dom>.
2454 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
2455 that contains the parameter values in C<dom> for which C<set> (or C<bset>)
2456 has no elements.
2457 In other words, the union of the parameter values
2458 for which the result is non-empty and of C<*empty>
2459 is equal to C<dom>.
2460
2461         __isl_give isl_set *isl_basic_set_partial_lexmin(
2462                 __isl_take isl_basic_set *bset,
2463                 __isl_take isl_basic_set *dom,
2464                 __isl_give isl_set **empty);
2465         __isl_give isl_set *isl_basic_set_partial_lexmax(
2466                 __isl_take isl_basic_set *bset,
2467                 __isl_take isl_basic_set *dom,
2468                 __isl_give isl_set **empty);
2469         __isl_give isl_set *isl_set_partial_lexmin(
2470                 __isl_take isl_set *set, __isl_take isl_set *dom,
2471                 __isl_give isl_set **empty);
2472         __isl_give isl_set *isl_set_partial_lexmax(
2473                 __isl_take isl_set *set, __isl_take isl_set *dom,
2474                 __isl_give isl_set **empty);
2475
2476 Given a (basic) set C<set> (or C<bset>), the following functions simply
2477 return a set containing the lexicographic minimum or maximum
2478 of the elements in C<set> (or C<bset>).
2479 In case of union sets, the optimum is computed per space.
2480
2481         __isl_give isl_set *isl_basic_set_lexmin(
2482                 __isl_take isl_basic_set *bset);
2483         __isl_give isl_set *isl_basic_set_lexmax(
2484                 __isl_take isl_basic_set *bset);
2485         __isl_give isl_set *isl_set_lexmin(
2486                 __isl_take isl_set *set);
2487         __isl_give isl_set *isl_set_lexmax(
2488                 __isl_take isl_set *set);
2489         __isl_give isl_union_set *isl_union_set_lexmin(
2490                 __isl_take isl_union_set *uset);
2491         __isl_give isl_union_set *isl_union_set_lexmax(
2492                 __isl_take isl_union_set *uset);
2493
2494 Given a (basic) relation C<map> (or C<bmap>) and a domain C<dom>,
2495 the following functions
2496 compute a relation that maps each element of C<dom>
2497 to the single lexicographic minimum or maximum
2498 of the elements that are associated to that same
2499 element in C<map> (or C<bmap>).
2500 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
2501 that contains the elements in C<dom> that do not map
2502 to any elements in C<map> (or C<bmap>).
2503 In other words, the union of the domain of the result and of C<*empty>
2504 is equal to C<dom>.
2505
2506         __isl_give isl_map *isl_basic_map_partial_lexmax(
2507                 __isl_take isl_basic_map *bmap,
2508                 __isl_take isl_basic_set *dom,
2509                 __isl_give isl_set **empty);
2510         __isl_give isl_map *isl_basic_map_partial_lexmin(
2511                 __isl_take isl_basic_map *bmap,
2512                 __isl_take isl_basic_set *dom,
2513                 __isl_give isl_set **empty);
2514         __isl_give isl_map *isl_map_partial_lexmax(
2515                 __isl_take isl_map *map, __isl_take isl_set *dom,
2516                 __isl_give isl_set **empty);
2517         __isl_give isl_map *isl_map_partial_lexmin(
2518                 __isl_take isl_map *map, __isl_take isl_set *dom,
2519                 __isl_give isl_set **empty);
2520
2521 Given a (basic) map C<map> (or C<bmap>), the following functions simply
2522 return a map mapping each element in the domain of
2523 C<map> (or C<bmap>) to the lexicographic minimum or maximum
2524 of all elements associated to that element.
2525 In case of union relations, the optimum is computed per space.
2526
2527         __isl_give isl_map *isl_basic_map_lexmin(
2528                 __isl_take isl_basic_map *bmap);
2529         __isl_give isl_map *isl_basic_map_lexmax(
2530                 __isl_take isl_basic_map *bmap);
2531         __isl_give isl_map *isl_map_lexmin(
2532                 __isl_take isl_map *map);
2533         __isl_give isl_map *isl_map_lexmax(
2534                 __isl_take isl_map *map);
2535         __isl_give isl_union_map *isl_union_map_lexmin(
2536                 __isl_take isl_union_map *umap);
2537         __isl_give isl_union_map *isl_union_map_lexmax(
2538                 __isl_take isl_union_map *umap);
2539
2540 The following functions return their result in the form of
2541 a piecewise multi-affine expression
2542 (See L<"Piecewise Multiple Quasi Affine Expressions">),
2543 but are otherwise equivalent to the corresponding functions
2544 returning a basic set or relation.
2545
2546         __isl_give isl_pw_multi_aff *
2547         isl_basic_map_lexmin_pw_multi_aff(
2548                 __isl_take isl_basic_map *bmap);
2549         __isl_give isl_pw_multi_aff *
2550         isl_basic_set_partial_lexmin_pw_multi_aff(
2551                 __isl_take isl_basic_set *bset,
2552                 __isl_take isl_basic_set *dom,
2553                 __isl_give isl_set **empty);
2554         __isl_give isl_pw_multi_aff *
2555         isl_basic_set_partial_lexmax_pw_multi_aff(
2556                 __isl_take isl_basic_set *bset,
2557                 __isl_take isl_basic_set *dom,
2558                 __isl_give isl_set **empty);
2559         __isl_give isl_pw_multi_aff *
2560         isl_basic_map_partial_lexmin_pw_multi_aff(
2561                 __isl_take isl_basic_map *bmap,
2562                 __isl_take isl_basic_set *dom,
2563                 __isl_give isl_set **empty);
2564         __isl_give isl_pw_multi_aff *
2565         isl_basic_map_partial_lexmax_pw_multi_aff(
2566                 __isl_take isl_basic_map *bmap,
2567                 __isl_take isl_basic_set *dom,
2568                 __isl_give isl_set **empty);
2569
2570 =head2 Lists
2571
2572 Lists are defined over several element types, including
2573 C<isl_aff>, C<isl_pw_aff>, C<isl_basic_set> and C<isl_set>.
2574 Here we take lists of C<isl_set>s as an example.
2575 Lists can be created, copied and freed using the following functions.
2576
2577         #include <isl/list.h>
2578         __isl_give isl_set_list *isl_set_list_from_set(
2579                 __isl_take isl_set *el);
2580         __isl_give isl_set_list *isl_set_list_alloc(
2581                 isl_ctx *ctx, int n);
2582         __isl_give isl_set_list *isl_set_list_copy(
2583                 __isl_keep isl_set_list *list);
2584         __isl_give isl_set_list *isl_set_list_add(
2585                 __isl_take isl_set_list *list,
2586                 __isl_take isl_set *el);
2587         __isl_give isl_set_list *isl_set_list_concat(
2588                 __isl_take isl_set_list *list1,
2589                 __isl_take isl_set_list *list2);
2590         void *isl_set_list_free(__isl_take isl_set_list *list);
2591
2592 C<isl_set_list_alloc> creates an empty list with a capacity for
2593 C<n> elements.  C<isl_set_list_from_set> creates a list with a single
2594 element.
2595
2596 Lists can be inspected using the following functions.
2597
2598         #include <isl/list.h>
2599         isl_ctx *isl_set_list_get_ctx(__isl_keep isl_set_list *list);
2600         int isl_set_list_n_set(__isl_keep isl_set_list *list);
2601         __isl_give isl_set *isl_set_list_get_set(
2602                 __isl_keep isl_set_list *list, int index);
2603         int isl_set_list_foreach(__isl_keep isl_set_list *list,
2604                 int (*fn)(__isl_take isl_set *el, void *user),
2605                 void *user);
2606
2607 Lists can be printed using
2608
2609         #include <isl/list.h>
2610         __isl_give isl_printer *isl_printer_print_set_list(
2611                 __isl_take isl_printer *p,
2612                 __isl_keep isl_set_list *list);
2613
2614 =head2 Matrices
2615
2616 Matrices can be created, copied and freed using the following functions.
2617
2618         #include <isl/mat.h>
2619         __isl_give isl_mat *isl_mat_alloc(isl_ctx *ctx,
2620                 unsigned n_row, unsigned n_col);
2621         __isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat);
2622         void isl_mat_free(__isl_take isl_mat *mat);
2623
2624 Note that the elements of a newly created matrix may have arbitrary values.
2625 The elements can be changed and inspected using the following functions.
2626
2627         isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat);
2628         int isl_mat_rows(__isl_keep isl_mat *mat);
2629         int isl_mat_cols(__isl_keep isl_mat *mat);
2630         int isl_mat_get_element(__isl_keep isl_mat *mat,
2631                 int row, int col, isl_int *v);
2632         __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat,
2633                 int row, int col, isl_int v);
2634         __isl_give isl_mat *isl_mat_set_element_si(__isl_take isl_mat *mat,
2635                 int row, int col, int v);
2636
2637 C<isl_mat_get_element> will return a negative value if anything went wrong.
2638 In that case, the value of C<*v> is undefined.
2639
2640 The following function can be used to compute the (right) inverse
2641 of a matrix, i.e., a matrix such that the product of the original
2642 and the inverse (in that order) is a multiple of the identity matrix.
2643 The input matrix is assumed to be of full row-rank.
2644
2645         __isl_give isl_mat *isl_mat_right_inverse(__isl_take isl_mat *mat);
2646
2647 The following function can be used to compute the (right) kernel
2648 (or null space) of a matrix, i.e., a matrix such that the product of
2649 the original and the kernel (in that order) is the zero matrix.
2650
2651         __isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat);
2652
2653 =head2 Piecewise Quasi Affine Expressions
2654
2655 The zero quasi affine expression on a given domain can be created using
2656
2657         __isl_give isl_aff *isl_aff_zero_on_domain(
2658                 __isl_take isl_local_space *ls);
2659
2660 Note that the space in which the resulting object lives is a map space
2661 with the given space as domain and a one-dimensional range.
2662
2663 An empty piecewise quasi affine expression (one with no cells)
2664 or a piecewise quasi affine expression with a single cell can
2665 be created using the following functions.
2666
2667         #include <isl/aff.h>
2668         __isl_give isl_pw_aff *isl_pw_aff_empty(
2669                 __isl_take isl_space *space);
2670         __isl_give isl_pw_aff *isl_pw_aff_alloc(
2671                 __isl_take isl_set *set, __isl_take isl_aff *aff);
2672         __isl_give isl_pw_aff *isl_pw_aff_from_aff(
2673                 __isl_take isl_aff *aff);
2674
2675 Quasi affine expressions can be copied and freed using
2676
2677         #include <isl/aff.h>
2678         __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff);
2679         void *isl_aff_free(__isl_take isl_aff *aff);
2680
2681         __isl_give isl_pw_aff *isl_pw_aff_copy(
2682                 __isl_keep isl_pw_aff *pwaff);
2683         void *isl_pw_aff_free(__isl_take isl_pw_aff *pwaff);
2684
2685 A (rational) bound on a dimension can be extracted from an C<isl_constraint>
2686 using the following function.  The constraint is required to have
2687 a non-zero coefficient for the specified dimension.
2688
2689         #include <isl/constraint.h>
2690         __isl_give isl_aff *isl_constraint_get_bound(
2691                 __isl_keep isl_constraint *constraint,
2692                 enum isl_dim_type type, int pos);
2693
2694 The entire affine expression of the constraint can also be extracted
2695 using the following function.
2696
2697         #include <isl/constraint.h>
2698         __isl_give isl_aff *isl_constraint_get_aff(
2699                 __isl_keep isl_constraint *constraint);
2700
2701 Conversely, an equality constraint equating
2702 the affine expression to zero or an inequality constraint enforcing
2703 the affine expression to be non-negative, can be constructed using
2704
2705         __isl_give isl_constraint *isl_equality_from_aff(
2706                 __isl_take isl_aff *aff);
2707         __isl_give isl_constraint *isl_inequality_from_aff(
2708                 __isl_take isl_aff *aff);
2709
2710 The expression can be inspected using
2711
2712         #include <isl/aff.h>
2713         isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff);
2714         int isl_aff_dim(__isl_keep isl_aff *aff,
2715                 enum isl_dim_type type);
2716         __isl_give isl_local_space *isl_aff_get_domain_local_space(
2717                 __isl_keep isl_aff *aff);
2718         __isl_give isl_local_space *isl_aff_get_local_space(
2719                 __isl_keep isl_aff *aff);
2720         const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
2721                 enum isl_dim_type type, unsigned pos);
2722         const char *isl_pw_aff_get_dim_name(
2723                 __isl_keep isl_pw_aff *pa,
2724                 enum isl_dim_type type, unsigned pos);
2725         __isl_give isl_id *isl_pw_aff_get_dim_id(
2726                 __isl_keep isl_pw_aff *pa,
2727                 enum isl_dim_type type, unsigned pos);
2728         int isl_aff_get_constant(__isl_keep isl_aff *aff,
2729                 isl_int *v);
2730         int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
2731                 enum isl_dim_type type, int pos, isl_int *v);
2732         int isl_aff_get_denominator(__isl_keep isl_aff *aff,
2733                 isl_int *v);
2734         __isl_give isl_aff *isl_aff_get_div(
2735                 __isl_keep isl_aff *aff, int pos);
2736
2737         int isl_pw_aff_foreach_piece(__isl_keep isl_pw_aff *pwaff,
2738                 int (*fn)(__isl_take isl_set *set,
2739                           __isl_take isl_aff *aff,
2740                           void *user), void *user);
2741
2742         int isl_aff_is_cst(__isl_keep isl_aff *aff);
2743         int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff);
2744
2745         int isl_aff_involves_dims(__isl_keep isl_aff *aff,
2746                 enum isl_dim_type type, unsigned first, unsigned n);
2747         int isl_pw_aff_involves_dims(__isl_keep isl_pw_aff *pwaff,
2748                 enum isl_dim_type type, unsigned first, unsigned n);
2749
2750         isl_ctx *isl_pw_aff_get_ctx(__isl_keep isl_pw_aff *pwaff);
2751         unsigned isl_pw_aff_dim(__isl_keep isl_pw_aff *pwaff,
2752                 enum isl_dim_type type);
2753         int isl_pw_aff_is_empty(__isl_keep isl_pw_aff *pwaff);
2754
2755 It can be modified using
2756
2757         #include <isl/aff.h>
2758         __isl_give isl_pw_aff *isl_pw_aff_set_tuple_id(
2759                 __isl_take isl_pw_aff *pwaff,
2760                 enum isl_dim_type type, __isl_take isl_id *id);
2761         __isl_give isl_aff *isl_aff_set_dim_name(
2762                 __isl_take isl_aff *aff, enum isl_dim_type type,
2763                 unsigned pos, const char *s);
2764         __isl_give isl_aff *isl_aff_set_dim_id(
2765                 __isl_take isl_aff *aff, enum isl_dim_type type,
2766                 unsigned pos, __isl_take isl_id *id);
2767         __isl_give isl_pw_aff *isl_pw_aff_set_dim_id(
2768                 __isl_take isl_pw_aff *pma,
2769                 enum isl_dim_type type, unsigned pos,
2770                 __isl_take isl_id *id);
2771         __isl_give isl_aff *isl_aff_set_constant(
2772                 __isl_take isl_aff *aff, isl_int v);
2773         __isl_give isl_aff *isl_aff_set_constant_si(
2774                 __isl_take isl_aff *aff, int v);
2775         __isl_give isl_aff *isl_aff_set_coefficient(
2776                 __isl_take isl_aff *aff,
2777                 enum isl_dim_type type, int pos, isl_int v);
2778         __isl_give isl_aff *isl_aff_set_coefficient_si(
2779                 __isl_take isl_aff *aff,
2780                 enum isl_dim_type type, int pos, int v);
2781         __isl_give isl_aff *isl_aff_set_denominator(
2782                 __isl_take isl_aff *aff, isl_int v);
2783
2784         __isl_give isl_aff *isl_aff_add_constant(
2785                 __isl_take isl_aff *aff, isl_int v);
2786         __isl_give isl_aff *isl_aff_add_constant_si(
2787                 __isl_take isl_aff *aff, int v);
2788         __isl_give isl_aff *isl_aff_add_coefficient(
2789                 __isl_take isl_aff *aff,
2790                 enum isl_dim_type type, int pos, isl_int v);
2791         __isl_give isl_aff *isl_aff_add_coefficient_si(
2792                 __isl_take isl_aff *aff,
2793                 enum isl_dim_type type, int pos, int v);
2794
2795         __isl_give isl_aff *isl_aff_insert_dims(
2796                 __isl_take isl_aff *aff,
2797                 enum isl_dim_type type, unsigned first, unsigned n);
2798         __isl_give isl_pw_aff *isl_pw_aff_insert_dims(
2799                 __isl_take isl_pw_aff *pwaff,
2800                 enum isl_dim_type type, unsigned first, unsigned n);
2801         __isl_give isl_aff *isl_aff_add_dims(
2802                 __isl_take isl_aff *aff,
2803                 enum isl_dim_type type, unsigned n);
2804         __isl_give isl_pw_aff *isl_pw_aff_add_dims(
2805                 __isl_take isl_pw_aff *pwaff,
2806                 enum isl_dim_type type, unsigned n);
2807         __isl_give isl_aff *isl_aff_drop_dims(
2808                 __isl_take isl_aff *aff,
2809                 enum isl_dim_type type, unsigned first, unsigned n);
2810         __isl_give isl_pw_aff *isl_pw_aff_drop_dims(
2811                 __isl_take isl_pw_aff *pwaff,
2812                 enum isl_dim_type type, unsigned first, unsigned n);
2813
2814 Note that the C<set_constant> and C<set_coefficient> functions
2815 set the I<numerator> of the constant or coefficient, while
2816 C<add_constant> and C<add_coefficient> add an integer value to
2817 the possibly rational constant or coefficient.
2818
2819 To check whether an affine expressions is obviously zero
2820 or obviously equal to some other affine expression, use
2821
2822         #include <isl/aff.h>
2823         int isl_aff_plain_is_zero(__isl_keep isl_aff *aff);
2824         int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1,
2825                 __isl_keep isl_aff *aff2);
2826         int isl_pw_aff_plain_is_equal(
2827                 __isl_keep isl_pw_aff *pwaff1,
2828                 __isl_keep isl_pw_aff *pwaff2);
2829
2830 Operations include
2831
2832         #include <isl/aff.h>
2833         __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
2834                 __isl_take isl_aff *aff2);
2835         __isl_give isl_pw_aff *isl_pw_aff_add(
2836                 __isl_take isl_pw_aff *pwaff1,
2837                 __isl_take isl_pw_aff *pwaff2);
2838         __isl_give isl_pw_aff *isl_pw_aff_min(
2839                 __isl_take isl_pw_aff *pwaff1,
2840                 __isl_take isl_pw_aff *pwaff2);
2841         __isl_give isl_pw_aff *isl_pw_aff_max(
2842                 __isl_take isl_pw_aff *pwaff1,
2843                 __isl_take isl_pw_aff *pwaff2);
2844         __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
2845                 __isl_take isl_aff *aff2);
2846         __isl_give isl_pw_aff *isl_pw_aff_sub(
2847                 __isl_take isl_pw_aff *pwaff1,
2848                 __isl_take isl_pw_aff *pwaff2);
2849         __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff);
2850         __isl_give isl_pw_aff *isl_pw_aff_neg(
2851                 __isl_take isl_pw_aff *pwaff);
2852         __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff);
2853         __isl_give isl_pw_aff *isl_pw_aff_ceil(
2854                 __isl_take isl_pw_aff *pwaff);
2855         __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff);
2856         __isl_give isl_pw_aff *isl_pw_aff_floor(
2857                 __isl_take isl_pw_aff *pwaff);
2858         __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff,
2859                 isl_int mod);
2860         __isl_give isl_pw_aff *isl_pw_aff_mod(
2861                 __isl_take isl_pw_aff *pwaff, isl_int mod);
2862         __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff,
2863                 isl_int f);
2864         __isl_give isl_pw_aff *isl_pw_aff_scale(
2865                 __isl_take isl_pw_aff *pwaff, isl_int f);
2866         __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff,
2867                 isl_int f);
2868         __isl_give isl_aff *isl_aff_scale_down_ui(
2869                 __isl_take isl_aff *aff, unsigned f);
2870         __isl_give isl_pw_aff *isl_pw_aff_scale_down(
2871                 __isl_take isl_pw_aff *pwaff, isl_int f);
2872
2873         __isl_give isl_pw_aff *isl_pw_aff_list_min(
2874                 __isl_take isl_pw_aff_list *list);
2875         __isl_give isl_pw_aff *isl_pw_aff_list_max(
2876                 __isl_take isl_pw_aff_list *list);
2877
2878         __isl_give isl_pw_aff *isl_pw_aff_coalesce(
2879                 __isl_take isl_pw_aff *pwqp);
2880
2881         __isl_give isl_pw_aff *isl_pw_aff_align_params(
2882                 __isl_take isl_pw_aff *pwaff,
2883                 __isl_take isl_space *model);
2884
2885         __isl_give isl_aff *isl_aff_gist_params(
2886                 __isl_take isl_aff *aff,
2887                 __isl_take isl_set *context);
2888         __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
2889                 __isl_take isl_set *context);
2890         __isl_give isl_pw_aff *isl_pw_aff_gist_params(
2891                 __isl_take isl_pw_aff *pwaff,
2892                 __isl_take isl_set *context);
2893         __isl_give isl_pw_aff *isl_pw_aff_gist(
2894                 __isl_take isl_pw_aff *pwaff,
2895                 __isl_take isl_set *context);
2896
2897         __isl_give isl_set *isl_pw_aff_domain(
2898                 __isl_take isl_pw_aff *pwaff);
2899         __isl_give isl_pw_aff *isl_pw_aff_intersect_domain(
2900                 __isl_take isl_pw_aff *pa,
2901                 __isl_take isl_set *set);
2902         __isl_give isl_pw_aff *isl_pw_aff_intersect_params(
2903                 __isl_take isl_pw_aff *pa,
2904                 __isl_take isl_set *set);
2905
2906         __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
2907                 __isl_take isl_aff *aff2);
2908         __isl_give isl_pw_aff *isl_pw_aff_mul(
2909                 __isl_take isl_pw_aff *pwaff1,
2910                 __isl_take isl_pw_aff *pwaff2);
2911
2912 When multiplying two affine expressions, at least one of the two needs
2913 to be a constant.
2914
2915         #include <isl/aff.h>
2916         __isl_give isl_basic_set *isl_aff_le_basic_set(
2917                 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2);
2918         __isl_give isl_basic_set *isl_aff_ge_basic_set(
2919                 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2);
2920         __isl_give isl_set *isl_pw_aff_eq_set(
2921                 __isl_take isl_pw_aff *pwaff1,
2922                 __isl_take isl_pw_aff *pwaff2);
2923         __isl_give isl_set *isl_pw_aff_ne_set(
2924                 __isl_take isl_pw_aff *pwaff1,
2925                 __isl_take isl_pw_aff *pwaff2);
2926         __isl_give isl_set *isl_pw_aff_le_set(
2927                 __isl_take isl_pw_aff *pwaff1,
2928                 __isl_take isl_pw_aff *pwaff2);
2929         __isl_give isl_set *isl_pw_aff_lt_set(
2930                 __isl_take isl_pw_aff *pwaff1,
2931                 __isl_take isl_pw_aff *pwaff2);
2932         __isl_give isl_set *isl_pw_aff_ge_set(
2933                 __isl_take isl_pw_aff *pwaff1,
2934                 __isl_take isl_pw_aff *pwaff2);
2935         __isl_give isl_set *isl_pw_aff_gt_set(
2936                 __isl_take isl_pw_aff *pwaff1,
2937                 __isl_take isl_pw_aff *pwaff2);
2938
2939         __isl_give isl_set *isl_pw_aff_list_eq_set(
2940                 __isl_take isl_pw_aff_list *list1,
2941                 __isl_take isl_pw_aff_list *list2);
2942         __isl_give isl_set *isl_pw_aff_list_ne_set(
2943                 __isl_take isl_pw_aff_list *list1,
2944                 __isl_take isl_pw_aff_list *list2);
2945         __isl_give isl_set *isl_pw_aff_list_le_set(
2946                 __isl_take isl_pw_aff_list *list1,
2947                 __isl_take isl_pw_aff_list *list2);
2948         __isl_give isl_set *isl_pw_aff_list_lt_set(
2949                 __isl_take isl_pw_aff_list *list1,
2950                 __isl_take isl_pw_aff_list *list2);
2951         __isl_give isl_set *isl_pw_aff_list_ge_set(
2952                 __isl_take isl_pw_aff_list *list1,
2953                 __isl_take isl_pw_aff_list *list2);
2954         __isl_give isl_set *isl_pw_aff_list_gt_set(
2955                 __isl_take isl_pw_aff_list *list1,
2956                 __isl_take isl_pw_aff_list *list2);
2957
2958 The function C<isl_aff_ge_basic_set> returns a basic set
2959 containing those elements in the shared space
2960 of C<aff1> and C<aff2> where C<aff1> is greater than or equal to C<aff2>.
2961 The function C<isl_aff_ge_set> returns a set
2962 containing those elements in the shared domain
2963 of C<pwaff1> and C<pwaff2> where C<pwaff1> is greater than or equal to C<pwaff2>.
2964 The functions operating on C<isl_pw_aff_list> apply the corresponding
2965 C<isl_pw_aff> function to each pair of elements in the two lists.
2966
2967         #include <isl/aff.h>
2968         __isl_give isl_set *isl_pw_aff_nonneg_set(
2969                 __isl_take isl_pw_aff *pwaff);
2970         __isl_give isl_set *isl_pw_aff_zero_set(
2971                 __isl_take isl_pw_aff *pwaff);
2972         __isl_give isl_set *isl_pw_aff_non_zero_set(
2973                 __isl_take isl_pw_aff *pwaff);
2974
2975 The function C<isl_pw_aff_nonneg_set> returns a set
2976 containing those elements in the domain
2977 of C<pwaff> where C<pwaff> is non-negative.
2978
2979         #include <isl/aff.h>
2980         __isl_give isl_pw_aff *isl_pw_aff_cond(
2981                 __isl_take isl_set *cond,
2982                 __isl_take isl_pw_aff *pwaff_true,
2983                 __isl_take isl_pw_aff *pwaff_false);
2984
2985 The function C<isl_pw_aff_cond> performs a conditional operator
2986 and returns an expression that is equal to C<pwaff_true>
2987 for elements in C<cond> and equal to C<pwaff_false> for elements
2988 not in C<cond>.
2989
2990         #include <isl/aff.h>
2991         __isl_give isl_pw_aff *isl_pw_aff_union_min(
2992                 __isl_take isl_pw_aff *pwaff1,
2993                 __isl_take isl_pw_aff *pwaff2);
2994         __isl_give isl_pw_aff *isl_pw_aff_union_max(
2995                 __isl_take isl_pw_aff *pwaff1,
2996                 __isl_take isl_pw_aff *pwaff2);
2997         __isl_give isl_pw_aff *isl_pw_aff_union_add(
2998                 __isl_take isl_pw_aff *pwaff1,
2999                 __isl_take isl_pw_aff *pwaff2);
3000
3001 The function C<isl_pw_aff_union_max> computes a piecewise quasi-affine
3002 expression with a domain that is the union of those of C<pwaff1> and
3003 C<pwaff2> and such that on each cell, the quasi-affine expression is
3004 the maximum of those of C<pwaff1> and C<pwaff2>.  If only one of
3005 C<pwaff1> or C<pwaff2> is defined on a given cell, then the
3006 associated expression is the defined one.
3007
3008 An expression can be read from input using
3009
3010         #include <isl/aff.h>
3011         __isl_give isl_aff *isl_aff_read_from_str(
3012                 isl_ctx *ctx, const char *str);
3013         __isl_give isl_pw_aff *isl_pw_aff_read_from_str(
3014                 isl_ctx *ctx, const char *str);
3015
3016 An expression can be printed using
3017
3018         #include <isl/aff.h>
3019         __isl_give isl_printer *isl_printer_print_aff(
3020                 __isl_take isl_printer *p, __isl_keep isl_aff *aff);
3021
3022         __isl_give isl_printer *isl_printer_print_pw_aff(
3023                 __isl_take isl_printer *p,
3024                 __isl_keep isl_pw_aff *pwaff);
3025
3026 =head2 Piecewise Multiple Quasi Affine Expressions
3027
3028 An C<isl_multi_aff> object represents a sequence of
3029 zero or more affine expressions, all defined on the same domain space.
3030
3031 An C<isl_multi_aff> can be constructed from a C<isl_aff_list> using the
3032 following function.
3033
3034         #include <isl/aff.h>
3035         __isl_give isl_multi_aff *isl_multi_aff_from_aff_list(
3036                 __isl_take isl_space *space,
3037                 __isl_take isl_aff_list *list);
3038
3039 An empty piecewise multiple quasi affine expression (one with no cells) or
3040 a piecewise multiple quasi affine expression with a single cell can
3041 be created using the following functions.
3042
3043         #include <isl/aff.h>
3044         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_empty(
3045                 __isl_take isl_space *space);
3046         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_alloc(
3047                 __isl_take isl_set *set,
3048                 __isl_take isl_multi_aff *maff);
3049
3050 A piecewise multiple quasi affine expression can also be initialized
3051 from an C<isl_set> or C<isl_map>, provided the C<isl_set> is a singleton
3052 and the C<isl_map> is single-valued.
3053
3054         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(
3055                 __isl_take isl_set *set);
3056         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(
3057                 __isl_take isl_map *map);
3058
3059 Multiple quasi affine expressions can be copied and freed using
3060
3061         #include <isl/aff.h>
3062         __isl_give isl_multi_aff *isl_multi_aff_copy(
3063                 __isl_keep isl_multi_aff *maff);
3064         void *isl_multi_aff_free(__isl_take isl_multi_aff *maff);
3065
3066         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_copy(
3067                 __isl_keep isl_pw_multi_aff *pma);
3068         void *isl_pw_multi_aff_free(
3069                 __isl_take isl_pw_multi_aff *pma);
3070
3071 The expression can be inspected using
3072
3073         #include <isl/aff.h>
3074         isl_ctx *isl_multi_aff_get_ctx(
3075                 __isl_keep isl_multi_aff *maff);
3076         isl_ctx *isl_pw_multi_aff_get_ctx(
3077                 __isl_keep isl_pw_multi_aff *pma);
3078         unsigned isl_multi_aff_dim(__isl_keep isl_multi_aff *maff,
3079                 enum isl_dim_type type);
3080         unsigned isl_pw_multi_aff_dim(
3081                 __isl_keep isl_pw_multi_aff *pma,
3082                 enum isl_dim_type type);
3083         __isl_give isl_aff *isl_multi_aff_get_aff(
3084                 __isl_keep isl_multi_aff *multi, int pos);
3085         const char *isl_pw_multi_aff_get_dim_name(
3086                 __isl_keep isl_pw_multi_aff *pma,
3087                 enum isl_dim_type type, unsigned pos);
3088         __isl_give isl_id *isl_pw_multi_aff_get_dim_id(
3089                 __isl_keep isl_pw_multi_aff *pma,
3090                 enum isl_dim_type type, unsigned pos);
3091         const char *isl_multi_aff_get_tuple_name(
3092                 __isl_keep isl_multi_aff *multi,
3093                 enum isl_dim_type type);
3094         const char *isl_pw_multi_aff_get_tuple_name(
3095                 __isl_keep isl_pw_multi_aff *pma,
3096                 enum isl_dim_type type);
3097         int isl_pw_multi_aff_has_tuple_id(
3098                 __isl_keep isl_pw_multi_aff *pma,
3099                 enum isl_dim_type type);
3100         __isl_give isl_id *isl_pw_multi_aff_get_tuple_id(
3101                 __isl_keep isl_pw_multi_aff *pma,
3102                 enum isl_dim_type type);
3103
3104         int isl_pw_multi_aff_foreach_piece(
3105                 __isl_keep isl_pw_multi_aff *pma,
3106                 int (*fn)(__isl_take isl_set *set,
3107                             __isl_take isl_multi_aff *maff,
3108                             void *user), void *user);
3109
3110 It can be modified using
3111
3112         #include <isl/aff.h>
3113         __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
3114                 __isl_take isl_multi_aff *maff,
3115                 enum isl_dim_type type, unsigned pos, const char *s);
3116         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_tuple_id(
3117                 __isl_take isl_pw_multi_aff *pma,
3118                 enum isl_dim_type type, __isl_take isl_id *id);
3119
3120 To check whether two multiple affine expressions are
3121 obviously equal to each other, use
3122
3123         int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
3124                 __isl_keep isl_multi_aff *maff2);
3125         int isl_pw_multi_aff_plain_is_equal(
3126                 __isl_keep isl_pw_multi_aff *pma1,
3127                 __isl_keep isl_pw_multi_aff *pma2);
3128
3129 Operations include
3130
3131         #include <isl/aff.h>
3132         __isl_give isl_multi_aff *isl_multi_aff_add(
3133                 __isl_take isl_multi_aff *maff1,
3134                 __isl_take isl_multi_aff *maff2);
3135         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
3136                 __isl_take isl_pw_multi_aff *pma1,
3137                 __isl_take isl_pw_multi_aff *pma2);
3138         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
3139                 __isl_take isl_pw_multi_aff *pma1,
3140                 __isl_take isl_pw_multi_aff *pma2);
3141         __isl_give isl_multi_aff *isl_multi_aff_scale(
3142                 __isl_take isl_multi_aff *maff,
3143                 isl_int f);
3144         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_intersect_params(
3145                 __isl_take isl_pw_multi_aff *pma,
3146                 __isl_take isl_set *set);
3147         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_intersect_domain(
3148                 __isl_take isl_pw_multi_aff *pma,
3149                 __isl_take isl_set *set);
3150         __isl_give isl_multi_aff *isl_multi_aff_lift(
3151                 __isl_take isl_multi_aff *maff,
3152                 __isl_give isl_local_space **ls);
3153         __isl_give isl_multi_aff *isl_multi_aff_gist_params(
3154                 __isl_take isl_multi_aff *maff,
3155                 __isl_take isl_set *context);
3156         __isl_give isl_multi_aff *isl_multi_aff_gist(
3157                 __isl_take isl_multi_aff *maff,
3158                 __isl_take isl_set *context);
3159         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_gist_params(
3160                 __isl_take isl_pw_multi_aff *pma,
3161                 __isl_take isl_set *set);
3162         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_gist(
3163                 __isl_take isl_pw_multi_aff *pma,
3164                 __isl_take isl_set *set);
3165
3166 If the C<ls> argument of C<isl_multi_aff_lift> is not C<NULL>,
3167 then it is assigned the local space that lies at the basis of
3168 the lifting applied.
3169
3170 An expression can be read from input using
3171
3172         #include <isl/aff.h>
3173         __isl_give isl_multi_aff *isl_multi_aff_read_from_str(
3174                 isl_ctx *ctx, const char *str);
3175         __isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(
3176                 isl_ctx *ctx, const char *str);
3177
3178 An expression can be printed using
3179
3180         #include <isl/aff.h>
3181         __isl_give isl_printer *isl_printer_print_multi_aff(
3182                 __isl_take isl_printer *p,
3183                 __isl_keep isl_multi_aff *maff);
3184         __isl_give isl_printer *isl_printer_print_pw_multi_aff(
3185                 __isl_take isl_printer *p,
3186                 __isl_keep isl_pw_multi_aff *pma);
3187
3188 =head2 Points
3189
3190 Points are elements of a set.  They can be used to construct
3191 simple sets (boxes) or they can be used to represent the
3192 individual elements of a set.
3193 The zero point (the origin) can be created using
3194
3195         __isl_give isl_point *isl_point_zero(__isl_take isl_space *space);
3196
3197 The coordinates of a point can be inspected, set and changed
3198 using
3199
3200         int isl_point_get_coordinate(__isl_keep isl_point *pnt,
3201                 enum isl_dim_type type, int pos, isl_int *v);
3202         __isl_give isl_point *isl_point_set_coordinate(
3203                 __isl_take isl_point *pnt,
3204                 enum isl_dim_type type, int pos, isl_int v);
3205
3206         __isl_give isl_point *isl_point_add_ui(
3207                 __isl_take isl_point *pnt,
3208                 enum isl_dim_type type, int pos, unsigned val);
3209         __isl_give isl_point *isl_point_sub_ui(
3210                 __isl_take isl_point *pnt,
3211                 enum isl_dim_type type, int pos, unsigned val);
3212
3213 Other properties can be obtained using
3214
3215         isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt);
3216
3217 Points can be copied or freed using
3218
3219         __isl_give isl_point *isl_point_copy(
3220                 __isl_keep isl_point *pnt);
3221         void isl_point_free(__isl_take isl_point *pnt);
3222
3223 A singleton set can be created from a point using
3224
3225         __isl_give isl_basic_set *isl_basic_set_from_point(
3226                 __isl_take isl_point *pnt);
3227         __isl_give isl_set *isl_set_from_point(
3228                 __isl_take isl_point *pnt);
3229
3230 and a box can be created from two opposite extremal points using
3231
3232         __isl_give isl_basic_set *isl_basic_set_box_from_points(
3233                 __isl_take isl_point *pnt1,
3234                 __isl_take isl_point *pnt2);
3235         __isl_give isl_set *isl_set_box_from_points(
3236                 __isl_take isl_point *pnt1,
3237                 __isl_take isl_point *pnt2);
3238
3239 All elements of a B<bounded> (union) set can be enumerated using
3240 the following functions.
3241
3242         int isl_set_foreach_point(__isl_keep isl_set *set,
3243                 int (*fn)(__isl_take isl_point *pnt, void *user),
3244                 void *user);
3245         int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
3246                 int (*fn)(__isl_take isl_point *pnt, void *user),
3247                 void *user);
3248
3249 The function C<fn> is called for each integer point in
3250 C<set> with as second argument the last argument of
3251 the C<isl_set_foreach_point> call.  The function C<fn>
3252 should return C<0> on success and C<-1> on failure.
3253 In the latter case, C<isl_set_foreach_point> will stop
3254 enumerating and return C<-1> as well.
3255 If the enumeration is performed successfully and to completion,
3256 then C<isl_set_foreach_point> returns C<0>.
3257
3258 To obtain a single point of a (basic) set, use
3259
3260         __isl_give isl_point *isl_basic_set_sample_point(
3261                 __isl_take isl_basic_set *bset);
3262         __isl_give isl_point *isl_set_sample_point(
3263                 __isl_take isl_set *set);
3264
3265 If C<set> does not contain any (integer) points, then the
3266 resulting point will be ``void'', a property that can be
3267 tested using
3268
3269         int isl_point_is_void(__isl_keep isl_point *pnt);
3270
3271 =head2 Piecewise Quasipolynomials
3272
3273 A piecewise quasipolynomial is a particular kind of function that maps
3274 a parametric point to a rational value.
3275 More specifically, a quasipolynomial is a polynomial expression in greatest
3276 integer parts of affine expressions of parameters and variables.
3277 A piecewise quasipolynomial is a subdivision of a given parametric
3278 domain into disjoint cells with a quasipolynomial associated to
3279 each cell.  The value of the piecewise quasipolynomial at a given
3280 point is the value of the quasipolynomial associated to the cell
3281 that contains the point.  Outside of the union of cells,
3282 the value is assumed to be zero.
3283 For example, the piecewise quasipolynomial
3284
3285         [n] -> { [x] -> ((1 + n) - x) : x <= n and x >= 0 }
3286
3287 maps C<x> to C<1 + n - x> for values of C<x> between C<0> and C<n>.
3288 A given piecewise quasipolynomial has a fixed domain dimension.
3289 Union piecewise quasipolynomials are used to contain piecewise quasipolynomials
3290 defined over different domains.
3291 Piecewise quasipolynomials are mainly used by the C<barvinok>
3292 library for representing the number of elements in a parametric set or map.
3293 For example, the piecewise quasipolynomial above represents
3294 the number of points in the map
3295
3296         [n] -> { [x] -> [y] : x,y >= 0 and 0 <= x + y <= n }
3297
3298 =head3 Input and Output
3299
3300 Piecewise quasipolynomials can be read from input using
3301
3302         __isl_give isl_union_pw_qpolynomial *
3303         isl_union_pw_qpolynomial_read_from_str(
3304                 isl_ctx *ctx, const char *str);
3305
3306 Quasipolynomials and piecewise quasipolynomials can be printed
3307 using the following functions.
3308
3309         __isl_give isl_printer *isl_printer_print_qpolynomial(
3310                 __isl_take isl_printer *p,
3311                 __isl_keep isl_qpolynomial *qp);
3312
3313         __isl_give isl_printer *isl_printer_print_pw_qpolynomial(
3314                 __isl_take isl_printer *p,
3315                 __isl_keep isl_pw_qpolynomial *pwqp);
3316
3317         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial(
3318                 __isl_take isl_printer *p,
3319                 __isl_keep isl_union_pw_qpolynomial *upwqp);
3320
3321 The output format of the printer
3322 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
3323 For C<isl_printer_print_union_pw_qpolynomial>, only C<ISL_FORMAT_ISL>
3324 is supported.
3325 In case of printing in C<ISL_FORMAT_C>, the user may want
3326 to set the names of all dimensions
3327
3328         __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
3329                 __isl_take isl_qpolynomial *qp,
3330                 enum isl_dim_type type, unsigned pos,
3331                 const char *s);
3332         __isl_give isl_pw_qpolynomial *
3333         isl_pw_qpolynomial_set_dim_name(
3334                 __isl_take isl_pw_qpolynomial *pwqp,
3335                 enum isl_dim_type type, unsigned pos,
3336                 const char *s);
3337
3338 =head3 Creating New (Piecewise) Quasipolynomials
3339
3340 Some simple quasipolynomials can be created using the following functions.
3341 More complicated quasipolynomials can be created by applying
3342 operations such as addition and multiplication
3343 on the resulting quasipolynomials
3344
3345         __isl_give isl_qpolynomial *isl_qpolynomial_zero_on_domain(
3346                 __isl_take isl_space *domain);
3347         __isl_give isl_qpolynomial *isl_qpolynomial_one_on_domain(
3348                 __isl_take isl_space *domain);
3349         __isl_give isl_qpolynomial *isl_qpolynomial_infty_on_domain(
3350                 __isl_take isl_space *domain);
3351         __isl_give isl_qpolynomial *isl_qpolynomial_neginfty_on_domain(
3352                 __isl_take isl_space *domain);
3353         __isl_give isl_qpolynomial *isl_qpolynomial_nan_on_domain(
3354                 __isl_take isl_space *domain);
3355         __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
3356                 __isl_take isl_space *domain,
3357                 const isl_int n, const isl_int d);
3358         __isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain(
3359                 __isl_take isl_space *domain,
3360                 enum isl_dim_type type, unsigned pos);
3361         __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(
3362                 __isl_take isl_aff *aff);
3363
3364 Note that the space in which a quasipolynomial lives is a map space
3365 with a one-dimensional range.  The C<domain> argument in some of
3366 the functions above corresponds to the domain of this map space.
3367
3368 The zero piecewise quasipolynomial or a piecewise quasipolynomial
3369 with a single cell can be created using the following functions.
3370 Multiple of these single cell piecewise quasipolynomials can
3371 be combined to create more complicated piecewise quasipolynomials.
3372
3373         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_zero(
3374                 __isl_take isl_space *space);
3375         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_alloc(
3376                 __isl_take isl_set *set,
3377                 __isl_take isl_qpolynomial *qp);
3378         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
3379                 __isl_take isl_qpolynomial *qp);
3380         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff(
3381                 __isl_take isl_pw_aff *pwaff);
3382
3383         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_zero(
3384                 __isl_take isl_space *space);
3385         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_from_pw_qpolynomial(
3386                 __isl_take isl_pw_qpolynomial *pwqp);
3387         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add_pw_qpolynomial(
3388                 __isl_take isl_union_pw_qpolynomial *upwqp,
3389                 __isl_take isl_pw_qpolynomial *pwqp);
3390
3391 Quasipolynomials can be copied and freed again using the following
3392 functions.
3393
3394         __isl_give isl_qpolynomial *isl_qpolynomial_copy(
3395                 __isl_keep isl_qpolynomial *qp);
3396         void *isl_qpolynomial_free(__isl_take isl_qpolynomial *qp);
3397
3398         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_copy(
3399                 __isl_keep isl_pw_qpolynomial *pwqp);
3400         void *isl_pw_qpolynomial_free(
3401                 __isl_take isl_pw_qpolynomial *pwqp);
3402
3403         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_copy(
3404                 __isl_keep isl_union_pw_qpolynomial *upwqp);
3405         void isl_union_pw_qpolynomial_free(
3406                 __isl_take isl_union_pw_qpolynomial *upwqp);
3407
3408 =head3 Inspecting (Piecewise) Quasipolynomials
3409
3410 To iterate over all piecewise quasipolynomials in a union
3411 piecewise quasipolynomial, use the following function
3412
3413         int isl_union_pw_qpolynomial_foreach_pw_qpolynomial(
3414                 __isl_keep isl_union_pw_qpolynomial *upwqp,
3415                 int (*fn)(__isl_take isl_pw_qpolynomial *pwqp, void *user),
3416                 void *user);
3417
3418 To extract the piecewise quasipolynomial in a given space from a union, use
3419
3420         __isl_give isl_pw_qpolynomial *
3421         isl_union_pw_qpolynomial_extract_pw_qpolynomial(
3422                 __isl_keep isl_union_pw_qpolynomial *upwqp,
3423                 __isl_take isl_space *space);
3424
3425 To iterate over the cells in a piecewise quasipolynomial,
3426 use either of the following two functions
3427
3428         int isl_pw_qpolynomial_foreach_piece(
3429                 __isl_keep isl_pw_qpolynomial *pwqp,
3430                 int (*fn)(__isl_take isl_set *set,
3431                           __isl_take isl_qpolynomial *qp,
3432                           void *user), void *user);
3433         int isl_pw_qpolynomial_foreach_lifted_piece(
3434                 __isl_keep isl_pw_qpolynomial *pwqp,
3435                 int (*fn)(__isl_take isl_set *set,
3436                           __isl_take isl_qpolynomial *qp,
3437                           void *user), void *user);
3438
3439 As usual, the function C<fn> should return C<0> on success
3440 and C<-1> on failure.  The difference between
3441 C<isl_pw_qpolynomial_foreach_piece> and
3442 C<isl_pw_qpolynomial_foreach_lifted_piece> is that
3443 C<isl_pw_qpolynomial_foreach_lifted_piece> will first
3444 compute unique representations for all existentially quantified
3445 variables and then turn these existentially quantified variables
3446 into extra set variables, adapting the associated quasipolynomial
3447 accordingly.  This means that the C<set> passed to C<fn>
3448 will not have any existentially quantified variables, but that
3449 the dimensions of the sets may be different for different
3450 invocations of C<fn>.
3451
3452 To iterate over all terms in a quasipolynomial,
3453 use
3454
3455         int isl_qpolynomial_foreach_term(
3456                 __isl_keep isl_qpolynomial *qp,
3457                 int (*fn)(__isl_take isl_term *term,
3458                           void *user), void *user);
3459
3460 The terms themselves can be inspected and freed using
3461 these functions
3462
3463         unsigned isl_term_dim(__isl_keep isl_term *term,
3464                 enum isl_dim_type type);
3465         void isl_term_get_num(__isl_keep isl_term *term,
3466                 isl_int *n);
3467         void isl_term_get_den(__isl_keep isl_term *term,
3468                 isl_int *d);
3469         int isl_term_get_exp(__isl_keep isl_term *term,
3470                 enum isl_dim_type type, unsigned pos);
3471         __isl_give isl_aff *isl_term_get_div(
3472                 __isl_keep isl_term *term, unsigned pos);
3473         void isl_term_free(__isl_take isl_term *term);
3474
3475 Each term is a product of parameters, set variables and
3476 integer divisions.  The function C<isl_term_get_exp>
3477 returns the exponent of a given dimensions in the given term.
3478 The C<isl_int>s in the arguments of C<isl_term_get_num>
3479 and C<isl_term_get_den> need to have been initialized
3480 using C<isl_int_init> before calling these functions.
3481
3482 =head3 Properties of (Piecewise) Quasipolynomials
3483
3484 To check whether a quasipolynomial is actually a constant,
3485 use the following function.
3486
3487         int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
3488                 isl_int *n, isl_int *d);
3489
3490 If C<qp> is a constant and if C<n> and C<d> are not C<NULL>
3491 then the numerator and denominator of the constant
3492 are returned in C<*n> and C<*d>, respectively.
3493
3494 To check whether two union piecewise quasipolynomials are
3495 obviously equal, use
3496
3497         int isl_union_pw_qpolynomial_plain_is_equal(
3498                 __isl_keep isl_union_pw_qpolynomial *upwqp1,
3499                 __isl_keep isl_union_pw_qpolynomial *upwqp2);
3500
3501 =head3 Operations on (Piecewise) Quasipolynomials
3502
3503         __isl_give isl_qpolynomial *isl_qpolynomial_scale(
3504                 __isl_take isl_qpolynomial *qp, isl_int v);
3505         __isl_give isl_qpolynomial *isl_qpolynomial_neg(
3506                 __isl_take isl_qpolynomial *qp);
3507         __isl_give isl_qpolynomial *isl_qpolynomial_add(
3508                 __isl_take isl_qpolynomial *qp1,
3509                 __isl_take isl_qpolynomial *qp2);
3510         __isl_give isl_qpolynomial *isl_qpolynomial_sub(
3511                 __isl_take isl_qpolynomial *qp1,
3512                 __isl_take isl_qpolynomial *qp2);
3513         __isl_give isl_qpolynomial *isl_qpolynomial_mul(
3514                 __isl_take isl_qpolynomial *qp1,
3515                 __isl_take isl_qpolynomial *qp2);
3516         __isl_give isl_qpolynomial *isl_qpolynomial_pow(
3517                 __isl_take isl_qpolynomial *qp, unsigned exponent);
3518
3519         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
3520                 __isl_take isl_pw_qpolynomial *pwqp1,
3521                 __isl_take isl_pw_qpolynomial *pwqp2);
3522         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
3523                 __isl_take isl_pw_qpolynomial *pwqp1,
3524                 __isl_take isl_pw_qpolynomial *pwqp2);
3525         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_disjoint(
3526                 __isl_take isl_pw_qpolynomial *pwqp1,
3527                 __isl_take isl_pw_qpolynomial *pwqp2);
3528         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
3529                 __isl_take isl_pw_qpolynomial *pwqp);
3530         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
3531                 __isl_take isl_pw_qpolynomial *pwqp1,
3532                 __isl_take isl_pw_qpolynomial *pwqp2);
3533         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow(
3534                 __isl_take isl_pw_qpolynomial *pwqp, unsigned exponent);
3535
3536         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add(
3537                 __isl_take isl_union_pw_qpolynomial *upwqp1,
3538                 __isl_take isl_union_pw_qpolynomial *upwqp2);
3539         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
3540                 __isl_take isl_union_pw_qpolynomial *upwqp1,
3541                 __isl_take isl_union_pw_qpolynomial *upwqp2);
3542         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
3543                 __isl_take isl_union_pw_qpolynomial *upwqp1,
3544                 __isl_take isl_union_pw_qpolynomial *upwqp2);
3545
3546         __isl_give isl_qpolynomial *isl_pw_qpolynomial_eval(
3547                 __isl_take isl_pw_qpolynomial *pwqp,
3548                 __isl_take isl_point *pnt);
3549
3550         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_eval(
3551                 __isl_take isl_union_pw_qpolynomial *upwqp,
3552                 __isl_take isl_point *pnt);
3553
3554         __isl_give isl_set *isl_pw_qpolynomial_domain(
3555                 __isl_take isl_pw_qpolynomial *pwqp);
3556         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_intersect_domain(
3557                 __isl_take isl_pw_qpolynomial *pwpq,
3558                 __isl_take isl_set *set);
3559         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_intersect_params(
3560                 __isl_take isl_pw_qpolynomial *pwpq,
3561                 __isl_take isl_set *set);
3562
3563         __isl_give isl_union_set *isl_union_pw_qpolynomial_domain(
3564                 __isl_take isl_union_pw_qpolynomial *upwqp);
3565         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_intersect_domain(
3566                 __isl_take isl_union_pw_qpolynomial *upwpq,
3567                 __isl_take isl_union_set *uset);
3568         __isl_give isl_union_pw_qpolynomial *
3569         isl_union_pw_qpolynomial_intersect_params(
3570                 __isl_take isl_union_pw_qpolynomial *upwpq,
3571                 __isl_take isl_set *set);
3572
3573         __isl_give isl_qpolynomial *isl_qpolynomial_align_params(
3574                 __isl_take isl_qpolynomial *qp,
3575                 __isl_take isl_space *model);
3576
3577         __isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params(
3578                 __isl_take isl_qpolynomial *qp);
3579         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_project_domain_on_params(
3580                 __isl_take isl_pw_qpolynomial *pwqp);
3581
3582         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_coalesce(
3583                 __isl_take isl_union_pw_qpolynomial *upwqp);
3584
3585         __isl_give isl_qpolynomial *isl_qpolynomial_gist_params(
3586                 __isl_take isl_qpolynomial *qp,
3587                 __isl_take isl_set *context);
3588         __isl_give isl_qpolynomial *isl_qpolynomial_gist(
3589                 __isl_take isl_qpolynomial *qp,
3590                 __isl_take isl_set *context);
3591
3592         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist_params(
3593                 __isl_take isl_pw_qpolynomial *pwqp,
3594                 __isl_take isl_set *context);
3595         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist(
3596                 __isl_take isl_pw_qpolynomial *pwqp,
3597                 __isl_take isl_set *context);
3598
3599         __isl_give isl_union_pw_qpolynomial *
3600         isl_union_pw_qpolynomial_gist_params(
3601                 __isl_take isl_union_pw_qpolynomial *upwqp,
3602                 __isl_take isl_set *context);
3603         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_gist(
3604                 __isl_take isl_union_pw_qpolynomial *upwqp,
3605                 __isl_take isl_union_set *context);
3606
3607 The gist operation applies the gist operation to each of
3608 the cells in the domain of the input piecewise quasipolynomial.
3609 The context is also exploited
3610 to simplify the quasipolynomials associated to each cell.
3611
3612         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
3613                 __isl_take isl_pw_qpolynomial *pwqp, int sign);
3614         __isl_give isl_union_pw_qpolynomial *
3615         isl_union_pw_qpolynomial_to_polynomial(
3616                 __isl_take isl_union_pw_qpolynomial *upwqp, int sign);
3617
3618 Approximate each quasipolynomial by a polynomial.  If C<sign> is positive,
3619 the polynomial will be an overapproximation.  If C<sign> is negative,
3620 it will be an underapproximation.  If C<sign> is zero, the approximation
3621 will lie somewhere in between.
3622
3623 =head2 Bounds on Piecewise Quasipolynomials and Piecewise Quasipolynomial Reductions
3624
3625 A piecewise quasipolynomial reduction is a piecewise
3626 reduction (or fold) of quasipolynomials.
3627 In particular, the reduction can be maximum or a minimum.
3628 The objects are mainly used to represent the result of
3629 an upper or lower bound on a quasipolynomial over its domain,
3630 i.e., as the result of the following function.
3631
3632         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
3633                 __isl_take isl_pw_qpolynomial *pwqp,
3634                 enum isl_fold type, int *tight);
3635
3636         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
3637                 __isl_take isl_union_pw_qpolynomial *upwqp,
3638                 enum isl_fold type, int *tight);
3639
3640 The C<type> argument may be either C<isl_fold_min> or C<isl_fold_max>.
3641 If C<tight> is not C<NULL>, then C<*tight> is set to C<1>
3642 is the returned bound is known be tight, i.e., for each value
3643 of the parameters there is at least
3644 one element in the domain that reaches the bound.
3645 If the domain of C<pwqp> is not wrapping, then the bound is computed
3646 over all elements in that domain and the result has a purely parametric
3647 domain.  If the domain of C<pwqp> is wrapping, then the bound is
3648 computed over the range of the wrapped relation.  The domain of the
3649 wrapped relation becomes the domain of the result.
3650
3651 A (piecewise) quasipolynomial reduction can be copied or freed using the
3652 following functions.
3653
3654         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
3655                 __isl_keep isl_qpolynomial_fold *fold);
3656         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_copy(
3657                 __isl_keep isl_pw_qpolynomial_fold *pwf);
3658         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_copy(
3659                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
3660         void isl_qpolynomial_fold_free(
3661                 __isl_take isl_qpolynomial_fold *fold);
3662         void *isl_pw_qpolynomial_fold_free(
3663                 __isl_take isl_pw_qpolynomial_fold *pwf);
3664         void isl_union_pw_qpolynomial_fold_free(
3665                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
3666
3667 =head3 Printing Piecewise Quasipolynomial Reductions
3668
3669 Piecewise quasipolynomial reductions can be printed
3670 using the following function.
3671
3672         __isl_give isl_printer *isl_printer_print_pw_qpolynomial_fold(
3673                 __isl_take isl_printer *p,
3674                 __isl_keep isl_pw_qpolynomial_fold *pwf);
3675         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial_fold(
3676                 __isl_take isl_printer *p,
3677                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
3678
3679 For C<isl_printer_print_pw_qpolynomial_fold>,
3680 output format of the printer
3681 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
3682 For C<isl_printer_print_union_pw_qpolynomial_fold>,
3683 output format of the printer
3684 needs to be set to C<ISL_FORMAT_ISL>.
3685 In case of printing in C<ISL_FORMAT_C>, the user may want
3686 to set the names of all dimensions
3687
3688         __isl_give isl_pw_qpolynomial_fold *
3689         isl_pw_qpolynomial_fold_set_dim_name(
3690                 __isl_take isl_pw_qpolynomial_fold *pwf,
3691                 enum isl_dim_type type, unsigned pos,
3692                 const char *s);
3693
3694 =head3 Inspecting (Piecewise) Quasipolynomial Reductions
3695
3696 To iterate over all piecewise quasipolynomial reductions in a union
3697 piecewise quasipolynomial reduction, use the following function
3698
3699         int isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
3700                 __isl_keep isl_union_pw_qpolynomial_fold *upwf,
3701                 int (*fn)(__isl_take isl_pw_qpolynomial_fold *pwf,
3702                             void *user), void *user);
3703
3704 To iterate over the cells in a piecewise quasipolynomial reduction,
3705 use either of the following two functions
3706
3707         int isl_pw_qpolynomial_fold_foreach_piece(
3708                 __isl_keep isl_pw_qpolynomial_fold *pwf,
3709                 int (*fn)(__isl_take isl_set *set,
3710                           __isl_take isl_qpolynomial_fold *fold,
3711                           void *user), void *user);
3712         int isl_pw_qpolynomial_fold_foreach_lifted_piece(
3713                 __isl_keep isl_pw_qpolynomial_fold *pwf,
3714                 int (*fn)(__isl_take isl_set *set,
3715                           __isl_take isl_qpolynomial_fold *fold,
3716                           void *user), void *user);
3717
3718 See L<Inspecting (Piecewise) Quasipolynomials> for an explanation
3719 of the difference between these two functions.
3720
3721 To iterate over all quasipolynomials in a reduction, use
3722
3723         int isl_qpolynomial_fold_foreach_qpolynomial(
3724                 __isl_keep isl_qpolynomial_fold *fold,
3725                 int (*fn)(__isl_take isl_qpolynomial *qp,
3726                           void *user), void *user);
3727
3728 =head3 Properties of Piecewise Quasipolynomial Reductions
3729
3730 To check whether two union piecewise quasipolynomial reductions are
3731 obviously equal, use
3732
3733         int isl_union_pw_qpolynomial_fold_plain_is_equal(
3734                 __isl_keep isl_union_pw_qpolynomial_fold *upwf1,
3735                 __isl_keep isl_union_pw_qpolynomial_fold *upwf2);
3736
3737 =head3 Operations on Piecewise Quasipolynomial Reductions
3738
3739         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
3740                 __isl_take isl_qpolynomial_fold *fold, isl_int v);
3741
3742         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
3743                 __isl_take isl_pw_qpolynomial_fold *pwf1,
3744                 __isl_take isl_pw_qpolynomial_fold *pwf2);
3745
3746         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
3747                 __isl_take isl_pw_qpolynomial_fold *pwf1,
3748                 __isl_take isl_pw_qpolynomial_fold *pwf2);
3749
3750         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
3751                 __isl_take isl_union_pw_qpolynomial_fold *upwf1,
3752                 __isl_take isl_union_pw_qpolynomial_fold *upwf2);
3753
3754         __isl_give isl_qpolynomial *isl_pw_qpolynomial_fold_eval(
3755                 __isl_take isl_pw_qpolynomial_fold *pwf,
3756                 __isl_take isl_point *pnt);
3757
3758         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_fold_eval(
3759                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3760                 __isl_take isl_point *pnt);
3761
3762         __isl_give isl_pw_qpolynomial_fold *
3763         sl_pw_qpolynomial_fold_intersect_params(
3764                 __isl_take isl_pw_qpolynomial_fold *pwf,
3765                 __isl_take isl_set *set);
3766
3767         __isl_give isl_union_set *isl_union_pw_qpolynomial_fold_domain(
3768                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
3769         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_intersect_domain(
3770                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3771                 __isl_take isl_union_set *uset);
3772         __isl_give isl_union_pw_qpolynomial_fold *
3773         isl_union_pw_qpolynomial_fold_intersect_params(
3774                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3775                 __isl_take isl_set *set);
3776
3777         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_project_domain_on_params(
3778                 __isl_take isl_pw_qpolynomial_fold *pwf);
3779
3780         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_coalesce(
3781                 __isl_take isl_pw_qpolynomial_fold *pwf);
3782
3783         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_coalesce(
3784                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
3785
3786         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
3787                 __isl_take isl_qpolynomial_fold *fold,
3788                 __isl_take isl_set *context);
3789         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
3790                 __isl_take isl_qpolynomial_fold *fold,
3791                 __isl_take isl_set *context);
3792
3793         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_gist(
3794                 __isl_take isl_pw_qpolynomial_fold *pwf,
3795                 __isl_take isl_set *context);
3796         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_gist_params(
3797                 __isl_take isl_pw_qpolynomial_fold *pwf,
3798                 __isl_take isl_set *context);
3799
3800         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_gist(
3801                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3802                 __isl_take isl_union_set *context);
3803         __isl_give isl_union_pw_qpolynomial_fold *
3804         isl_union_pw_qpolynomial_fold_gist_params(
3805                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3806                 __isl_take isl_set *context);
3807
3808 The gist operation applies the gist operation to each of
3809 the cells in the domain of the input piecewise quasipolynomial reduction.
3810 In future, the operation will also exploit the context
3811 to simplify the quasipolynomial reductions associated to each cell.
3812
3813         __isl_give isl_pw_qpolynomial_fold *
3814         isl_set_apply_pw_qpolynomial_fold(
3815                 __isl_take isl_set *set,
3816                 __isl_take isl_pw_qpolynomial_fold *pwf,
3817                 int *tight);
3818         __isl_give isl_pw_qpolynomial_fold *
3819         isl_map_apply_pw_qpolynomial_fold(
3820                 __isl_take isl_map *map,
3821                 __isl_take isl_pw_qpolynomial_fold *pwf,
3822                 int *tight);
3823         __isl_give isl_union_pw_qpolynomial_fold *
3824         isl_union_set_apply_union_pw_qpolynomial_fold(
3825                 __isl_take isl_union_set *uset,
3826                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3827                 int *tight);
3828         __isl_give isl_union_pw_qpolynomial_fold *
3829         isl_union_map_apply_union_pw_qpolynomial_fold(
3830                 __isl_take isl_union_map *umap,
3831                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
3832                 int *tight);
3833
3834 The functions taking a map
3835 compose the given map with the given piecewise quasipolynomial reduction.
3836 That is, compute a bound (of the same type as C<pwf> or C<upwf> itself)
3837 over all elements in the intersection of the range of the map
3838 and the domain of the piecewise quasipolynomial reduction
3839 as a function of an element in the domain of the map.
3840 The functions taking a set compute a bound over all elements in the
3841 intersection of the set and the domain of the
3842 piecewise quasipolynomial reduction.
3843
3844 =head2 Dependence Analysis
3845
3846 C<isl> contains specialized functionality for performing
3847 array dataflow analysis.  That is, given a I<sink> access relation
3848 and a collection of possible I<source> access relations,
3849 C<isl> can compute relations that describe
3850 for each iteration of the sink access, which iteration
3851 of which of the source access relations was the last
3852 to access the same data element before the given iteration
3853 of the sink access.
3854 The resulting dependence relations map source iterations
3855 to the corresponding sink iterations.
3856 To compute standard flow dependences, the sink should be
3857 a read, while the sources should be writes.
3858 If any of the source accesses are marked as being I<may>
3859 accesses, then there will be a dependence from the last
3860 I<must> access B<and> from any I<may> access that follows
3861 this last I<must> access.
3862 In particular, if I<all> sources are I<may> accesses,
3863 then memory based dependence analysis is performed.
3864 If, on the other hand, all sources are I<must> accesses,
3865 then value based dependence analysis is performed.
3866
3867         #include <isl/flow.h>
3868
3869         typedef int (*isl_access_level_before)(void *first, void *second);
3870
3871         __isl_give isl_access_info *isl_access_info_alloc(
3872                 __isl_take isl_map *sink,
3873                 void *sink_user, isl_access_level_before fn,
3874                 int max_source);
3875         __isl_give isl_access_info *isl_access_info_add_source(
3876                 __isl_take isl_access_info *acc,
3877                 __isl_take isl_map *source, int must,
3878                 void *source_user);
3879         void isl_access_info_free(__isl_take isl_access_info *acc);
3880
3881         __isl_give isl_flow *isl_access_info_compute_flow(
3882                 __isl_take isl_access_info *acc);
3883
3884         int isl_flow_foreach(__isl_keep isl_flow *deps,
3885                 int (*fn)(__isl_take isl_map *dep, int must,
3886                           void *dep_user, void *user),
3887                 void *user);
3888         __isl_give isl_map *isl_flow_get_no_source(
3889                 __isl_keep isl_flow *deps, int must);
3890         void isl_flow_free(__isl_take isl_flow *deps);
3891
3892 The function C<isl_access_info_compute_flow> performs the actual
3893 dependence analysis.  The other functions are used to construct
3894 the input for this function or to read off the output.
3895
3896 The input is collected in an C<isl_access_info>, which can
3897 be created through a call to C<isl_access_info_alloc>.
3898 The arguments to this functions are the sink access relation
3899 C<sink>, a token C<sink_user> used to identify the sink
3900 access to the user, a callback function for specifying the
3901 relative order of source and sink accesses, and the number
3902 of source access relations that will be added.
3903 The callback function has type C<int (*)(void *first, void *second)>.
3904 The function is called with two user supplied tokens identifying
3905 either a source or the sink and it should return the shared nesting
3906 level and the relative order of the two accesses.
3907 In particular, let I<n> be the number of loops shared by
3908 the two accesses.  If C<first> precedes C<second> textually,
3909 then the function should return I<2 * n + 1>; otherwise,
3910 it should return I<2 * n>.
3911 The sources can be added to the C<isl_access_info> by performing
3912 (at most) C<max_source> calls to C<isl_access_info_add_source>.
3913 C<must> indicates whether the source is a I<must> access
3914 or a I<may> access.  Note that a multi-valued access relation
3915 should only be marked I<must> if every iteration in the domain
3916 of the relation accesses I<all> elements in its image.
3917 The C<source_user> token is again used to identify
3918 the source access.  The range of the source access relation
3919 C<source> should have the same dimension as the range
3920 of the sink access relation.
3921 The C<isl_access_info_free> function should usually not be
3922 called explicitly, because it is called implicitly by
3923 C<isl_access_info_compute_flow>.
3924
3925 The result of the dependence analysis is collected in an
3926 C<isl_flow>.  There may be elements of
3927 the sink access for which no preceding source access could be
3928 found or for which all preceding sources are I<may> accesses.
3929 The relations containing these elements can be obtained through
3930 calls to C<isl_flow_get_no_source>, the first with C<must> set
3931 and the second with C<must> unset.
3932 In the case of standard flow dependence analysis,
3933 with the sink a read and the sources I<must> writes,
3934 the first relation corresponds to the reads from uninitialized
3935 array elements and the second relation is empty.
3936 The actual flow dependences can be extracted using
3937 C<isl_flow_foreach>.  This function will call the user-specified
3938 callback function C<fn> for each B<non-empty> dependence between
3939 a source and the sink.  The callback function is called
3940 with four arguments, the actual flow dependence relation
3941 mapping source iterations to sink iterations, a boolean that
3942 indicates whether it is a I<must> or I<may> dependence, a token
3943 identifying the source and an additional C<void *> with value
3944 equal to the third argument of the C<isl_flow_foreach> call.
3945 A dependence is marked I<must> if it originates from a I<must>
3946 source and if it is not followed by any I<may> sources.
3947
3948 After finishing with an C<isl_flow>, the user should call
3949 C<isl_flow_free> to free all associated memory.
3950
3951 A higher-level interface to dependence analysis is provided
3952 by the following function.
3953
3954         #include <isl/flow.h>
3955
3956         int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
3957                 __isl_take isl_union_map *must_source,
3958                 __isl_take isl_union_map *may_source,
3959                 __isl_take isl_union_map *schedule,
3960                 __isl_give isl_union_map **must_dep,
3961                 __isl_give isl_union_map **may_dep,
3962                 __isl_give isl_union_map **must_no_source,
3963                 __isl_give isl_union_map **may_no_source);
3964
3965 The arrays are identified by the tuple names of the ranges
3966 of the accesses.  The iteration domains by the tuple names
3967 of the domains of the accesses and of the schedule.
3968 The relative order of the iteration domains is given by the
3969 schedule.  The relations returned through C<must_no_source>
3970 and C<may_no_source> are subsets of C<sink>.
3971 Any of C<must_dep>, C<may_dep>, C<must_no_source>
3972 or C<may_no_source> may be C<NULL>, but a C<NULL> value for
3973 any of the other arguments is treated as an error.
3974
3975 =head2 Scheduling
3976
3977 B<The functionality described in this section is fairly new
3978 and may be subject to change.>
3979
3980 The following function can be used to compute a schedule
3981 for a union of domains.  The generated schedule respects
3982 all C<validity> dependences.  That is, all dependence distances
3983 over these dependences in the scheduled space are lexicographically
3984 positive.  The generated schedule schedule also tries to minimize
3985 the dependence distances over C<proximity> dependences.
3986 Moreover, it tries to obtain sequences (bands) of schedule dimensions
3987 for groups of domains where the dependence distances have only
3988 non-negative values.
3989 The algorithm used to construct the schedule is similar to that
3990 of C<Pluto>.
3991
3992         #include <isl/schedule.h>
3993         __isl_give isl_schedule *isl_union_set_compute_schedule(
3994                 __isl_take isl_union_set *domain,
3995                 __isl_take isl_union_map *validity,
3996                 __isl_take isl_union_map *proximity);
3997         void *isl_schedule_free(__isl_take isl_schedule *sched);
3998
3999 A mapping from the domains to the scheduled space can be obtained
4000 from an C<isl_schedule> using the following function.
4001
4002         __isl_give isl_union_map *isl_schedule_get_map(
4003                 __isl_keep isl_schedule *sched);
4004
4005 A representation of the schedule can be printed using
4006          
4007         __isl_give isl_printer *isl_printer_print_schedule(
4008                 __isl_take isl_printer *p,
4009                 __isl_keep isl_schedule *schedule);
4010
4011 A representation of the schedule as a forest of bands can be obtained
4012 using the following function.
4013
4014         __isl_give isl_band_list *isl_schedule_get_band_forest(
4015                 __isl_keep isl_schedule *schedule);
4016
4017 The list can be manipulated as explained in L<"Lists">.
4018 The bands inside the list can be copied and freed using the following
4019 functions.
4020
4021         #include <isl/band.h>
4022         __isl_give isl_band *isl_band_copy(
4023                 __isl_keep isl_band *band);
4024         void *isl_band_free(__isl_take isl_band *band);
4025
4026 Each band contains zero or more scheduling dimensions.
4027 These are referred to as the members of the band.
4028 The section of the schedule that corresponds to the band is
4029 referred to as the partial schedule of the band.
4030 For those nodes that participate in a band, the outer scheduling
4031 dimensions form the prefix schedule, while the inner scheduling
4032 dimensions form the suffix schedule.
4033 That is, if we take a cut of the band forest, then the union of
4034 the concatenations of the prefix, partial and suffix schedules of
4035 each band in the cut is equal to the entire schedule (modulo
4036 some possible padding at the end with zero scheduling dimensions).
4037 The properties of a band can be inspected using the following functions.
4038
4039         #include <isl/band.h>
4040         isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band);
4041
4042         int isl_band_has_children(__isl_keep isl_band *band);
4043         __isl_give isl_band_list *isl_band_get_children(
4044                 __isl_keep isl_band *band);
4045
4046         __isl_give isl_union_map *isl_band_get_prefix_schedule(
4047                 __isl_keep isl_band *band);
4048         __isl_give isl_union_map *isl_band_get_partial_schedule(
4049                 __isl_keep isl_band *band);
4050         __isl_give isl_union_map *isl_band_get_suffix_schedule(
4051                 __isl_keep isl_band *band);
4052
4053         int isl_band_n_member(__isl_keep isl_band *band);
4054         int isl_band_member_is_zero_distance(
4055                 __isl_keep isl_band *band, int pos);
4056
4057 Note that a scheduling dimension is considered to be ``zero
4058 distance'' if it does not carry any proximity dependences
4059 within its band.
4060 That is, if the dependence distances of the proximity
4061 dependences are all zero in that direction (for fixed
4062 iterations of outer bands).
4063
4064 A representation of the band can be printed using
4065
4066         #include <isl/band.h>
4067         __isl_give isl_printer *isl_printer_print_band(
4068                 __isl_take isl_printer *p,
4069                 __isl_keep isl_band *band);
4070
4071 =head3 Options
4072
4073         #include <isl/schedule.h>
4074         int isl_options_set_schedule_outer_zero_distance(
4075                 isl_ctx *ctx, int val);
4076         int isl_options_get_schedule_outer_zero_distance(
4077                 isl_ctx *ctx);
4078
4079 =over
4080
4081 =item * schedule_outer_zero_distance
4082
4083 It this option is set, then we try to construct schedules
4084 where the outermost scheduling dimension in each band
4085 results in a zero dependence distance over the proximity
4086 dependences.
4087
4088 =back
4089
4090 =head2 Parametric Vertex Enumeration
4091
4092 The parametric vertex enumeration described in this section
4093 is mainly intended to be used internally and by the C<barvinok>
4094 library.
4095
4096         #include <isl/vertices.h>
4097         __isl_give isl_vertices *isl_basic_set_compute_vertices(
4098                 __isl_keep isl_basic_set *bset);
4099
4100 The function C<isl_basic_set_compute_vertices> performs the
4101 actual computation of the parametric vertices and the chamber
4102 decomposition and store the result in an C<isl_vertices> object.
4103 This information can be queried by either iterating over all
4104 the vertices or iterating over all the chambers or cells
4105 and then iterating over all vertices that are active on the chamber.
4106
4107         int isl_vertices_foreach_vertex(
4108                 __isl_keep isl_vertices *vertices,
4109                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
4110                 void *user);
4111
4112         int isl_vertices_foreach_cell(
4113                 __isl_keep isl_vertices *vertices,
4114                 int (*fn)(__isl_take isl_cell *cell, void *user),
4115                 void *user);
4116         int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
4117                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
4118                 void *user);
4119
4120 Other operations that can be performed on an C<isl_vertices> object are
4121 the following.
4122
4123         isl_ctx *isl_vertices_get_ctx(
4124                 __isl_keep isl_vertices *vertices);
4125         int isl_vertices_get_n_vertices(
4126                 __isl_keep isl_vertices *vertices);
4127         void isl_vertices_free(__isl_take isl_vertices *vertices);
4128
4129 Vertices can be inspected and destroyed using the following functions.
4130
4131         isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
4132         int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
4133         __isl_give isl_basic_set *isl_vertex_get_domain(
4134                 __isl_keep isl_vertex *vertex);
4135         __isl_give isl_basic_set *isl_vertex_get_expr(
4136                 __isl_keep isl_vertex *vertex);
4137         void isl_vertex_free(__isl_take isl_vertex *vertex);
4138
4139 C<isl_vertex_get_expr> returns a singleton parametric set describing
4140 the vertex, while C<isl_vertex_get_domain> returns the activity domain
4141 of the vertex.
4142 Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
4143 B<rational> basic sets, so they should mainly be used for inspection
4144 and should not be mixed with integer sets.
4145
4146 Chambers can be inspected and destroyed using the following functions.
4147
4148         isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
4149         __isl_give isl_basic_set *isl_cell_get_domain(
4150                 __isl_keep isl_cell *cell);
4151         void isl_cell_free(__isl_take isl_cell *cell);
4152
4153 =head1 Applications
4154
4155 Although C<isl> is mainly meant to be used as a library,
4156 it also contains some basic applications that use some
4157 of the functionality of C<isl>.
4158 The input may be specified in either the L<isl format>
4159 or the L<PolyLib format>.
4160
4161 =head2 C<isl_polyhedron_sample>
4162
4163 C<isl_polyhedron_sample> takes a polyhedron as input and prints
4164 an integer element of the polyhedron, if there is any.
4165 The first column in the output is the denominator and is always
4166 equal to 1.  If the polyhedron contains no integer points,
4167 then a vector of length zero is printed.
4168
4169 =head2 C<isl_pip>
4170
4171 C<isl_pip> takes the same input as the C<example> program
4172 from the C<piplib> distribution, i.e., a set of constraints
4173 on the parameters, a line containing only -1 and finally a set
4174 of constraints on a parametric polyhedron.
4175 The coefficients of the parameters appear in the last columns
4176 (but before the final constant column).
4177 The output is the lexicographic minimum of the parametric polyhedron.
4178 As C<isl> currently does not have its own output format, the output
4179 is just a dump of the internal state.
4180
4181 =head2 C<isl_polyhedron_minimize>
4182
4183 C<isl_polyhedron_minimize> computes the minimum of some linear
4184 or affine objective function over the integer points in a polyhedron.
4185 If an affine objective function
4186 is given, then the constant should appear in the last column.
4187
4188 =head2 C<isl_polytope_scan>
4189
4190 Given a polytope, C<isl_polytope_scan> prints
4191 all integer points in the polytope.