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