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