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 the dimension specification
  72 of a B<map> as input.  An old call
  73 C<isl_map_identity(dim)> can be rewritten to
  74 C<isl_map_identity(isl_dim_map_from_set(dim))>.
  75
  76 =back
  77
  78 =head1 Installation
  79
  80 The source of C<isl> can be obtained either as a tarball
  81 or from the git repository.  Both are available from
  82 L<http://freshmeat.net/projects/isl/>.
  83 The installation process depends on how you obtained
  84 the source.
  85
  86 =head2 Installation from the git repository
  87
  88 =over
  89
  90 =item 1 Clone or update the repository
  91
  92 The first time the source is obtained, you need to clone
  93 the repository.
  94
  95         git clone git://repo.or.cz/isl.git
  96
  97 To obtain updates, you need to pull in the latest changes
  98
  99         git pull
 100
 101 =item 2 Generate C<configure>
 102
 103         ./autogen.sh
 104
 105 =back
 106
 107 After performing the above steps, continue
 108 with the L<Common installation instructions>.
 109
 110 =head2 Common installation instructions
 111
 112 =over
 113
 114 =item 1 Obtain C<GMP>
 115
 116 Building C<isl> requires C<GMP>, including its headers files.
 117 Your distribution may not provide these header files by default
 118 and you may need to install a package called C<gmp-devel> or something
 119 similar.  Alternatively, C<GMP> can be built from
 120 source, available from L<http://gmplib.org/>.
 121
 122 =item 2 Configure
 123
 124 C<isl> uses the standard C<autoconf> C<configure> script.
 125 To run it, just type
 126
 127         ./configure
 128
 129 optionally followed by some configure options.
 130 A complete list of options can be obtained by running
 131
 132         ./configure --help
 133
 134 Below we discuss some of the more common options.
 135
 136 C<isl> can optionally use C<piplib>, but no
 137 C<piplib> functionality is currently used by default.
 138 The C<--with-piplib> option can
 139 be used to specify which C<piplib>
 140 library to use, either an installed version (C<system>),
 141 an externally built version (C<build>)
 142 or no version (C<no>).  The option C<build> is mostly useful
 143 in C<configure> scripts of larger projects that bundle both C<isl>
 144 and C<piplib>.
 145
 146 =over
 147
 148 =item C<--prefix>
 149
 150 Installation prefix for C<isl>
 151
 152 =item C<--with-gmp-prefix>
 153
 154 Installation prefix for C<GMP> (architecture-independent files).
 155
 156 =item C<--with-gmp-exec-prefix>
 157
 158 Installation prefix for C<GMP> (architecture-dependent files).
 159
 160 =item C<--with-piplib>
 161
 162 Which copy of C<piplib> to use, either C<no> (default), C<system> or C<build>.
 163
 164 =item C<--with-piplib-prefix>
 165
 166 Installation prefix for C<system> C<piplib> (architecture-independent files).
 167
 168 =item C<--with-piplib-exec-prefix>
 169
 170 Installation prefix for C<system> C<piplib> (architecture-dependent files).
 171
 172 =item C<--with-piplib-builddir>
 173
 174 Location where C<build> C<piplib> was built.
 175
 176 =back
 177
 178 =item 3 Compile
 179
 180         make
 181
 182 =item 4 Install (optional)
 183
 184         make install
 185
 186 =back
 187
 188 =head1 Library
 189
 190 =head2 Initialization
 191
 192 All manipulations of integer sets and relations occur within
 193 the context of an C<isl_ctx>.
 194 A given C<isl_ctx> can only be used within a single thread.
 195 All arguments of a function are required to have been allocated
 196 within the same context.
 197 There are currently no functions available for moving an object
 198 from one C<isl_ctx> to another C<isl_ctx>.  This means that
 199 there is currently no way of safely moving an object from one
 200 thread to another, unless the whole C<isl_ctx> is moved.
 201
 202 An C<isl_ctx> can be allocated using C<isl_ctx_alloc> and
 203 freed using C<isl_ctx_free>.
 204 All objects allocated within an C<isl_ctx> should be freed
 205 before the C<isl_ctx> itself is freed.
 206
 207         isl_ctx *isl_ctx_alloc();
 208         void isl_ctx_free(isl_ctx *ctx);
 209
 210 =head2 Integers
 211
 212 All operations on integers, mainly the coefficients
 213 of the constraints describing the sets and relations,
 214 are performed in exact integer arithmetic using C<GMP>.
 215 However, to allow future versions of C<isl> to optionally
 216 support fixed integer arithmetic, all calls to C<GMP>
 217 are wrapped inside C<isl> specific macros.
 218 The basic type is C<isl_int> and the operations below
 219 are available on this type.
 220 The meanings of these operations are essentially the same
 221 as their C<GMP> C<mpz_> counterparts.
 222 As always with C<GMP> types, C<isl_int>s need to be
 223 initialized with C<isl_int_init> before they can be used
 224 and they need to be released with C<isl_int_clear>
 225 after the last use.
 226 The user should not assume that an C<isl_int> is represented
 227 as a C<mpz_t>, but should instead explicitly convert between
 228 C<mpz_t>s and C<isl_int>s using C<isl_int_set_gmp> and
 229 C<isl_int_get_gmp> whenever a C<mpz_t> is required.
 230
 231 =over
 232
 233 =item isl_int_init(i)
 234
 235 =item isl_int_clear(i)
 236
 237 =item isl_int_set(r,i)
 238
 239 =item isl_int_set_si(r,i)
 240
 241 =item isl_int_set_gmp(r,g)
 242
 243 =item isl_int_get_gmp(i,g)
 244
 245 =item isl_int_abs(r,i)
 246
 247 =item isl_int_neg(r,i)
 248
 249 =item isl_int_swap(i,j)
 250
 251 =item isl_int_swap_or_set(i,j)
 252
 253 =item isl_int_add_ui(r,i,j)
 254
 255 =item isl_int_sub_ui(r,i,j)
 256
 257 =item isl_int_add(r,i,j)
 258
 259 =item isl_int_sub(r,i,j)
 260
 261 =item isl_int_mul(r,i,j)
 262
 263 =item isl_int_mul_ui(r,i,j)
 264
 265 =item isl_int_addmul(r,i,j)
 266
 267 =item isl_int_submul(r,i,j)
 268
 269 =item isl_int_gcd(r,i,j)
 270
 271 =item isl_int_lcm(r,i,j)
 272
 273 =item isl_int_divexact(r,i,j)
 274
 275 =item isl_int_cdiv_q(r,i,j)
 276
 277 =item isl_int_fdiv_q(r,i,j)
 278
 279 =item isl_int_fdiv_r(r,i,j)
 280
 281 =item isl_int_fdiv_q_ui(r,i,j)
 282
 283 =item isl_int_read(r,s)
 284
 285 =item isl_int_print(out,i,width)
 286
 287 =item isl_int_sgn(i)
 288
 289 =item isl_int_cmp(i,j)
 290
 291 =item isl_int_cmp_si(i,si)
 292
 293 =item isl_int_eq(i,j)
 294
 295 =item isl_int_ne(i,j)
 296
 297 =item isl_int_lt(i,j)
 298
 299 =item isl_int_le(i,j)
 300
 301 =item isl_int_gt(i,j)
 302
 303 =item isl_int_ge(i,j)
 304
 305 =item isl_int_abs_eq(i,j)
 306
 307 =item isl_int_abs_ne(i,j)
 308
 309 =item isl_int_abs_lt(i,j)
 310
 311 =item isl_int_abs_gt(i,j)
 312
 313 =item isl_int_abs_ge(i,j)
 314
 315 =item isl_int_is_zero(i)
 316
 317 =item isl_int_is_one(i)
 318
 319 =item isl_int_is_negone(i)
 320
 321 =item isl_int_is_pos(i)
 322
 323 =item isl_int_is_neg(i)
 324
 325 =item isl_int_is_nonpos(i)
 326
 327 =item isl_int_is_nonneg(i)
 328
 329 =item isl_int_is_divisible_by(i,j)
 330
 331 =back
 332
 333 =head2 Sets and Relations
 334
 335 C<isl> uses six types of objects for representing sets and relations,
 336 C<isl_basic_set>, C<isl_basic_map>, C<isl_set>, C<isl_map>,
 337 C<isl_union_set> and C<isl_union_map>.
 338 C<isl_basic_set> and C<isl_basic_map> represent sets and relations that
 339 can be described as a conjunction of affine constraints, while
 340 C<isl_set> and C<isl_map> represent unions of
 341 C<isl_basic_set>s and C<isl_basic_map>s, respectively.
 342 However, all C<isl_basic_set>s or C<isl_basic_map>s in the union need
 343 to have the same dimension.  C<isl_union_set>s and C<isl_union_map>s
 344 represent unions of C<isl_set>s or C<isl_map>s of I<different> dimensions,
 345 where dimensions with different space names
 346 (see L<Dimension Specifications>) are considered different as well.
 347 The difference between sets and relations (maps) is that sets have
 348 one set of variables, while relations have two sets of variables,
 349 input variables and output variables.
 350
 351 =head2 Memory Management
 352
 353 Since a high-level operation on sets and/or relations usually involves
 354 several substeps and since the user is usually not interested in
 355 the intermediate results, most functions that return a new object
 356 will also release all the objects passed as arguments.
 357 If the user still wants to use one or more of these arguments
 358 after the function call, she should pass along a copy of the
 359 object rather than the object itself.
 360 The user is then responsible for make sure that the original
 361 object gets used somewhere else or is explicitly freed.
 362
 363 The arguments and return values of all documents functions are
 364 annotated to make clear which arguments are released and which
 365 arguments are preserved.  In particular, the following annotations
 366 are used
 367
 368 =over
 369
 370 =item C<__isl_give>
 371
 372 C<__isl_give> means that a new object is returned.
 373 The user should make sure that the returned pointer is
 374 used exactly once as a value for an C<__isl_take> argument.
 375 In between, it can be used as a value for as many
 376 C<__isl_keep> arguments as the user likes.
 377 There is one exception, and that is the case where the
 378 pointer returned is C<NULL>.  Is this case, the user
 379 is free to use it as an C<__isl_take> argument or not.
 380
 381 =item C<__isl_take>
 382
 383 C<__isl_take> means that the object the argument points to
 384 is taken over by the function and may no longer be used
 385 by the user as an argument to any other function.
 386 The pointer value must be one returned by a function
 387 returning an C<__isl_give> pointer.
 388 If the user passes in a C<NULL> value, then this will
 389 be treated as an error in the sense that the function will
 390 not perform its usual operation.  However, it will still
 391 make sure that all the the other C<__isl_take> arguments
 392 are released.
 393
 394 =item C<__isl_keep>
 395
 396 C<__isl_keep> means that the function will only use the object
 397 temporarily.  After the function has finished, the user
 398 can still use it as an argument to other functions.
 399 A C<NULL> value will be treated in the same way as
 400 a C<NULL> value for an C<__isl_take> argument.
 401
 402 =back
 403
 404 =head2 Dimension Specifications
 405
 406 Whenever a new set or relation is created from scratch,
 407 its dimension needs to be specified using an C<isl_dim>.
 408
 409         #include <isl/dim.h>
 410         __isl_give isl_dim *isl_dim_alloc(isl_ctx *ctx,
 411                 unsigned nparam, unsigned n_in, unsigned n_out);
 412         __isl_give isl_dim *isl_dim_set_alloc(isl_ctx *ctx,
 413                 unsigned nparam, unsigned dim);
 414         __isl_give isl_dim *isl_dim_copy(__isl_keep isl_dim *dim);
 415         void isl_dim_free(__isl_take isl_dim *dim);
 416         unsigned isl_dim_size(__isl_keep isl_dim *dim,
 417                 enum isl_dim_type type);
 418
 419 The dimension specification used for creating a set
 420 needs to be created using C<isl_dim_set_alloc>, while
 421 that for creating a relation
 422 needs to be created using C<isl_dim_alloc>.
 423 C<isl_dim_size> can be used
 424 to find out the number of dimensions of each type in
 425 a dimension specification, where type may be
 426 C<isl_dim_param>, C<isl_dim_in> (only for relations),
 427 C<isl_dim_out> (only for relations), C<isl_dim_set>
 428 (only for sets) or C<isl_dim_all>.
 429
 430 It is often useful to create objects that live in the
 431 same space as some other object.  This can be accomplished
 432 by creating the new objects
 433 (see L<Creating New Sets and Relations> or
 434 L<Creating New (Piecewise) Quasipolynomials>) based on the dimension
 435 specification of the original object.
 436
 437         #include <isl/set.h>
 438         __isl_give isl_dim *isl_basic_set_get_dim(
 439                 __isl_keep isl_basic_set *bset);
 440         __isl_give isl_dim *isl_set_get_dim(__isl_keep isl_set *set);
 441
 442         #include <isl/union_set.h>
 443         __isl_give isl_dim *isl_union_set_get_dim(
 444                 __isl_keep isl_union_set *uset);
 445
 446         #include <isl/map.h>
 447         __isl_give isl_dim *isl_basic_map_get_dim(
 448                 __isl_keep isl_basic_map *bmap);
 449         __isl_give isl_dim *isl_map_get_dim(__isl_keep isl_map *map);
 450
 451         #include <isl/union_map.h>
 452         __isl_give isl_dim *isl_union_map_get_dim(
 453                 __isl_keep isl_union_map *umap);
 454
 455         #include <isl/polynomial.h>
 456         __isl_give isl_dim *isl_qpolynomial_get_dim(
 457                 __isl_keep isl_qpolynomial *qp);
 458         __isl_give isl_dim *isl_pw_qpolynomial_get_dim(
 459                 __isl_keep isl_pw_qpolynomial *pwqp);
 460         __isl_give isl_dim *isl_union_pw_qpolynomial_get_dim(
 461                 __isl_keep isl_union_pw_qpolynomial *upwqp);
 462         __isl_give isl_dim *isl_union_pw_qpolynomial_fold_get_dim(
 463                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
 464
 465 The names of the individual dimensions may be set or read off
 466 using the following functions.
 467
 468         #include <isl/dim.h>
 469         __isl_give isl_dim *isl_dim_set_name(__isl_take isl_dim *dim,
 470                                  enum isl_dim_type type, unsigned pos,
 471                                  __isl_keep const char *name);
 472         __isl_keep const char *isl_dim_get_name(__isl_keep isl_dim *dim,
 473                                  enum isl_dim_type type, unsigned pos);
 474
 475 Note that C<isl_dim_get_name> returns a pointer to some internal
 476 data structure, so the result can only be used while the
 477 corresponding C<isl_dim> is alive.
 478 Also note that every function that operates on two sets or relations
 479 requires that both arguments have the same parameters.  This also
 480 means that if one of the arguments has named parameters, then the
 481 other needs to have named parameters too and the names need to match.
 482 Pairs of C<isl_union_set> and/or C<isl_union_map> arguments may
 483 have different parameters (as long as they are named), in which case
 484 the result will have as parameters the union of the parameters of
 485 the arguments.
 486
 487 The names of entire spaces may be set or read off
 488 using the following functions.
 489
 490         #include <isl/dim.h>
 491         __isl_give isl_dim *isl_dim_set_tuple_name(
 492                 __isl_take isl_dim *dim,
 493                 enum isl_dim_type type, const char *s);
 494         const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
 495                 enum isl_dim_type type);
 496
 497 The C<dim> argument needs to be one of C<isl_dim_in>, C<isl_dim_out>
 498 or C<isl_dim_set>.  As with C<isl_dim_get_name>,
 499 the C<isl_dim_get_tuple_name> function returns a pointer to some internal
 500 data structure.
 501 Binary operations require the corresponding spaces of their arguments
 502 to have the same name.
 503
 504 Spaces can be nested.  In particular, the domain of a set or
 505 the domain or range of a relation can be a nested relation.
 506 The following functions can be used to construct and deconstruct
 507 such nested dimension specifications.
 508
 509         #include <isl/dim.h>
 510         int isl_dim_is_wrapping(__isl_keep isl_dim *dim);
 511         __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim);
 512         __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim);
 513
 514 The input to C<isl_dim_is_wrapping> and C<isl_dim_unwrap> should
 515 be the dimension specification of a set, while that of
 516 C<isl_dim_wrap> should be the dimension specification of a relation.
 517 Conversely, the output of C<isl_dim_unwrap> is the dimension specification
 518 of a relation, while that of C<isl_dim_wrap> is the dimension specification
 519 of a set.
 520
 521 Dimension specifications can be created from other dimension
 522 specifications using the following functions.
 523
 524         __isl_give isl_dim *isl_dim_domain(__isl_take isl_dim *dim);
 525         __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim);
 526         __isl_give isl_dim *isl_dim_range(__isl_take isl_dim *dim);
 527         __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim);
 528         __isl_give isl_dim *isl_dim_reverse(__isl_take isl_dim *dim);
 529         __isl_give isl_dim *isl_dim_join(__isl_take isl_dim *left,
 530                 __isl_take isl_dim *right);
 531         __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
 532                 enum isl_dim_type type, unsigned pos, unsigned n);
 533         __isl_give isl_dim *isl_dim_add(__isl_take isl_dim *dim,
 534                 enum isl_dim_type type, unsigned n);
 535         __isl_give isl_dim *isl_dim_drop(__isl_take isl_dim *dim,
 536                 enum isl_dim_type type, unsigned first, unsigned n);
 537         __isl_give isl_dim *isl_dim_map_from_set(
 538                 __isl_take isl_dim *dim);
 539
 540 Note that if dimensions are added or removed from a space, then
 541 the name and the internal structure are lost.
 542
 543 =head2 Input and Output
 544
 545 C<isl> supports its own input/output format, which is similar
 546 to the C<Omega> format, but also supports the C<PolyLib> format
 547 in some cases.
 548
 549 =head3 C<isl> format
 550
 551 The C<isl> format is similar to that of C<Omega>, but has a different
 552 syntax for describing the parameters and allows for the definition
 553 of an existentially quantified variable as the integer division
 554 of an affine expression.
 555 For example, the set of integers C<i> between C<0> and C<n>
 556 such that C<i % 10 <= 6> can be described as
 557
 558         [n] -> { [i] : exists (a = [i/10] : 0 <= i and i <= n and
 559                                 i - 10 a <= 6) }
 560
 561 A set or relation can have several disjuncts, separated
 562 by the keyword C<or>.  Each disjunct is either a conjunction
 563 of constraints or a projection (C<exists>) of a conjunction
 564 of constraints.  The constraints are separated by the keyword
 565 C<and>.
 566
 567 =head3 C<PolyLib> format
 568
 569 If the represented set is a union, then the first line
 570 contains a single number representing the number of disjuncts.
 571 Otherwise, a line containing the number C<1> is optional.
 572
 573 Each disjunct is represented by a matrix of constraints.
 574 The first line contains two numbers representing
 575 the number of rows and columns,
 576 where the number of rows is equal to the number of constraints
 577 and the number of columns is equal to two plus the number of variables.
 578 The following lines contain the actual rows of the constraint matrix.
 579 In each row, the first column indicates whether the constraint
 580 is an equality (C<0>) or inequality (C<1>).  The final column
 581 corresponds to the constant term.
 582
 583 If the set is parametric, then the coefficients of the parameters
 584 appear in the last columns before the constant column.
 585 The coefficients of any existentially quantified variables appear
 586 between those of the set variables and those of the parameters.
 587
 588 =head3 Extended C<PolyLib> format
 589
 590 The extended C<PolyLib> format is nearly identical to the
 591 C<PolyLib> format.  The only difference is that the line
 592 containing the number of rows and columns of a constraint matrix
 593 also contains four additional numbers:
 594 the number of output dimensions, the number of input dimensions,
 595 the number of local dimensions (i.e., the number of existentially
 596 quantified variables) and the number of parameters.
 597 For sets, the number of ``output'' dimensions is equal
 598 to the number of set dimensions, while the number of ``input''
 599 dimensions is zero.
 600
 601 =head3 Input
 602
 603         #include <isl/set.h>
 604         __isl_give isl_basic_set *isl_basic_set_read_from_file(
 605                 isl_ctx *ctx, FILE *input, int nparam);
 606         __isl_give isl_basic_set *isl_basic_set_read_from_str(
 607                 isl_ctx *ctx, const char *str, int nparam);
 608         __isl_give isl_set *isl_set_read_from_file(isl_ctx *ctx,
 609                 FILE *input, int nparam);
 610         __isl_give isl_set *isl_set_read_from_str(isl_ctx *ctx,
 611                 const char *str, int nparam);
 612
 613         #include <isl/map.h>
 614         __isl_give isl_basic_map *isl_basic_map_read_from_file(
 615                 isl_ctx *ctx, FILE *input, int nparam);
 616         __isl_give isl_basic_map *isl_basic_map_read_from_str(
 617                 isl_ctx *ctx, const char *str, int nparam);
 618         __isl_give isl_map *isl_map_read_from_file(
 619                 struct isl_ctx *ctx, FILE *input, int nparam);
 620         __isl_give isl_map *isl_map_read_from_str(isl_ctx *ctx,
 621                 const char *str, int nparam);
 622
 623         #include <isl/union_set.h>
 624         __isl_give isl_union_set *isl_union_set_read_from_file(
 625                 isl_ctx *ctx, FILE *input);
 626         __isl_give isl_union_set *isl_union_set_read_from_str(
 627                 struct isl_ctx *ctx, const char *str);
 628
 629         #include <isl/union_map.h>
 630         __isl_give isl_union_map *isl_union_map_read_from_file(
 631                 isl_ctx *ctx, FILE *input);
 632         __isl_give isl_union_map *isl_union_map_read_from_str(
 633                 struct isl_ctx *ctx, const char *str);
 634
 635 The input format is autodetected and may be either the C<PolyLib> format
 636 or the C<isl> format.
 637 C<nparam> specifies how many of the final columns in
 638 the C<PolyLib> format correspond to parameters.
 639 If input is given in the C<isl> format, then the number
 640 of parameters needs to be equal to C<nparam>.
 641 If C<nparam> is negative, then any number of parameters
 642 is accepted in the C<isl> format and zero parameters
 643 are assumed in the C<PolyLib> format.
 644
 645 =head3 Output
 646
 647 Before anything can be printed, an C<isl_printer> needs to
 648 be created.
 649
 650         __isl_give isl_printer *isl_printer_to_file(isl_ctx *ctx,
 651                 FILE *file);
 652         __isl_give isl_printer *isl_printer_to_str(isl_ctx *ctx);
 653         void isl_printer_free(__isl_take isl_printer *printer);
 654         __isl_give char *isl_printer_get_str(
 655                 __isl_keep isl_printer *printer);
 656
 657 The behavior of the printer can be modified in various ways
 658
 659         __isl_give isl_printer *isl_printer_set_output_format(
 660                 __isl_take isl_printer *p, int output_format);
 661         __isl_give isl_printer *isl_printer_set_indent(
 662                 __isl_take isl_printer *p, int indent);
 663         __isl_give isl_printer *isl_printer_set_prefix(
 664                 __isl_take isl_printer *p, const char *prefix);
 665         __isl_give isl_printer *isl_printer_set_suffix(
 666                 __isl_take isl_printer *p, const char *suffix);
 667
 668 The C<output_format> may be either C<ISL_FORMAT_ISL>, C<ISL_FORMAT_OMEGA>,
 669 C<ISL_FORMAT_POLYLIB>, C<ISL_FORMAT_EXT_POLYLIB> or C<ISL_FORMAT_LATEX>
 670 and defaults to C<ISL_FORMAT_ISL>.
 671 Each line in the output is indented by C<indent> spaces
 672 (default: 0), prefixed by C<prefix> and suffixed by C<suffix>.
 673 In the C<PolyLib> format output,
 674 the coefficients of the existentially quantified variables
 675 appear between those of the set variables and those
 676 of the parameters.
 677
 678 To actually print something, use
 679
 680         #include <isl/set.h>
 681         __isl_give isl_printer *isl_printer_print_basic_set(
 682                 __isl_take isl_printer *printer,
 683                 __isl_keep isl_basic_set *bset);
 684         __isl_give isl_printer *isl_printer_print_set(
 685                 __isl_take isl_printer *printer,
 686                 __isl_keep isl_set *set);
 687
 688         #include <isl/map.h>
 689         __isl_give isl_printer *isl_printer_print_basic_map(
 690                 __isl_take isl_printer *printer,
 691                 __isl_keep isl_basic_map *bmap);
 692         __isl_give isl_printer *isl_printer_print_map(
 693                 __isl_take isl_printer *printer,
 694                 __isl_keep isl_map *map);
 695
 696         #include <isl/union_set.h>
 697         __isl_give isl_printer *isl_printer_print_union_set(
 698                 __isl_take isl_printer *p,
 699                 __isl_keep isl_union_set *uset);
 700
 701         #include <isl/union_map.h>
 702         __isl_give isl_printer *isl_printer_print_union_map(
 703                 __isl_take isl_printer *p,
 704                 __isl_keep isl_union_map *umap);
 705
 706 When called on a file printer, the following function flushes
 707 the file.  When called on a string printer, the buffer is cleared.
 708
 709         __isl_give isl_printer *isl_printer_flush(
 710                 __isl_take isl_printer *p);
 711
 712 =head2 Creating New Sets and Relations
 713
 714 C<isl> has functions for creating some standard sets and relations.
 715
 716 =over
 717
 718 =item * Empty sets and relations
 719
 720         __isl_give isl_basic_set *isl_basic_set_empty(
 721                 __isl_take isl_dim *dim);
 722         __isl_give isl_basic_map *isl_basic_map_empty(
 723                 __isl_take isl_dim *dim);
 724         __isl_give isl_set *isl_set_empty(
 725                 __isl_take isl_dim *dim);
 726         __isl_give isl_map *isl_map_empty(
 727                 __isl_take isl_dim *dim);
 728         __isl_give isl_union_set *isl_union_set_empty(
 729                 __isl_take isl_dim *dim);
 730         __isl_give isl_union_map *isl_union_map_empty(
 731                 __isl_take isl_dim *dim);
 732
 733 For C<isl_union_set>s and C<isl_union_map>s, the dimensions specification
 734 is only used to specify the parameters.
 735
 736 =item * Universe sets and relations
 737
 738         __isl_give isl_basic_set *isl_basic_set_universe(
 739                 __isl_take isl_dim *dim);
 740         __isl_give isl_basic_map *isl_basic_map_universe(
 741                 __isl_take isl_dim *dim);
 742         __isl_give isl_set *isl_set_universe(
 743                 __isl_take isl_dim *dim);
 744         __isl_give isl_map *isl_map_universe(
 745                 __isl_take isl_dim *dim);
 746
 747 The sets and relations constructed by the functions above
 748 contain all integer values, while those constructed by the
 749 functions below only contain non-negative values.
 750
 751         __isl_give isl_basic_set *isl_basic_set_nat_universe(
 752                 __isl_take isl_dim *dim);
 753         __isl_give isl_basic_map *isl_basic_map_nat_universe(
 754                 __isl_take isl_dim *dim);
 755         __isl_give isl_set *isl_set_nat_universe(
 756                 __isl_take isl_dim *dim);
 757         __isl_give isl_map *isl_map_nat_universe(
 758                 __isl_take isl_dim *dim);
 759
 760 =item * Identity relations
 761
 762         __isl_give isl_basic_map *isl_basic_map_identity(
 763                 __isl_take isl_dim *dim);
 764         __isl_give isl_map *isl_map_identity(
 765                 __isl_take isl_dim *dim);
 766
 767 The number of input and output dimensions in C<dim> needs
 768 to be the same.
 769
 770 =item * Lexicographic order
 771
 772         __isl_give isl_map *isl_map_lex_lt(
 773                 __isl_take isl_dim *set_dim);
 774         __isl_give isl_map *isl_map_lex_le(
 775                 __isl_take isl_dim *set_dim);
 776         __isl_give isl_map *isl_map_lex_gt(
 777                 __isl_take isl_dim *set_dim);
 778         __isl_give isl_map *isl_map_lex_ge(
 779                 __isl_take isl_dim *set_dim);
 780         __isl_give isl_map *isl_map_lex_lt_first(
 781                 __isl_take isl_dim *dim, unsigned n);
 782         __isl_give isl_map *isl_map_lex_le_first(
 783                 __isl_take isl_dim *dim, unsigned n);
 784         __isl_give isl_map *isl_map_lex_gt_first(
 785                 __isl_take isl_dim *dim, unsigned n);
 786         __isl_give isl_map *isl_map_lex_ge_first(
 787                 __isl_take isl_dim *dim, unsigned n);
 788
 789 The first four functions take a dimension specification for a B<set>
 790 and return relations that express that the elements in the domain
 791 are lexicographically less
 792 (C<isl_map_lex_lt>), less or equal (C<isl_map_lex_le>),
 793 greater (C<isl_map_lex_gt>) or greater or equal (C<isl_map_lex_ge>)
 794 than the elements in the range.
 795 The last four functions take a dimension specification for a map
 796 and return relations that express that the first C<n> dimensions
 797 in the domain are lexicographically less
 798 (C<isl_map_lex_lt_first>), less or equal (C<isl_map_lex_le_first>),
 799 greater (C<isl_map_lex_gt_first>) or greater or equal (C<isl_map_lex_ge_first>)
 800 than the first C<n> dimensions in the range.
 801
 802 =back
 803
 804 A basic set or relation can be converted to a set or relation
 805 using the following functions.
 806
 807         __isl_give isl_set *isl_set_from_basic_set(
 808                 __isl_take isl_basic_set *bset);
 809         __isl_give isl_map *isl_map_from_basic_map(
 810                 __isl_take isl_basic_map *bmap);
 811
 812 Sets and relations can be converted to union sets and relations
 813 using the following functions.
 814
 815         __isl_give isl_union_map *isl_union_map_from_map(
 816                 __isl_take isl_map *map);
 817         __isl_give isl_union_set *isl_union_set_from_set(
 818                 __isl_take isl_set *set);
 819
 820 Sets and relations can be copied and freed again using the following
 821 functions.
 822
 823         __isl_give isl_basic_set *isl_basic_set_copy(
 824                 __isl_keep isl_basic_set *bset);
 825         __isl_give isl_set *isl_set_copy(__isl_keep isl_set *set);
 826         __isl_give isl_union_set *isl_union_set_copy(
 827                 __isl_keep isl_union_set *uset);
 828         __isl_give isl_basic_map *isl_basic_map_copy(
 829                 __isl_keep isl_basic_map *bmap);
 830         __isl_give isl_map *isl_map_copy(__isl_keep isl_map *map);
 831         __isl_give isl_union_map *isl_union_map_copy(
 832                 __isl_keep isl_union_map *umap);
 833         void isl_basic_set_free(__isl_take isl_basic_set *bset);
 834         void isl_set_free(__isl_take isl_set *set);
 835         void isl_union_set_free(__isl_take isl_union_set *uset);
 836         void isl_basic_map_free(__isl_take isl_basic_map *bmap);
 837         void isl_map_free(__isl_take isl_map *map);
 838         void isl_union_map_free(__isl_take isl_union_map *umap);
 839
 840 Other sets and relations can be constructed by starting
 841 from a universe set or relation, adding equality and/or
 842 inequality constraints and then projecting out the
 843 existentially quantified variables, if any.
 844 Constraints can be constructed, manipulated and
 845 added to basic sets and relations using the following functions.
 846
 847         #include <isl/constraint.h>
 848         __isl_give isl_constraint *isl_equality_alloc(
 849                 __isl_take isl_dim *dim);
 850         __isl_give isl_constraint *isl_inequality_alloc(
 851                 __isl_take isl_dim *dim);
 852         void isl_constraint_set_constant(
 853                 __isl_keep isl_constraint *constraint, isl_int v);
 854         void isl_constraint_set_coefficient(
 855                 __isl_keep isl_constraint *constraint,
 856                 enum isl_dim_type type, int pos, isl_int v);
 857         __isl_give isl_basic_map *isl_basic_map_add_constraint(
 858                 __isl_take isl_basic_map *bmap,
 859                 __isl_take isl_constraint *constraint);
 860         __isl_give isl_basic_set *isl_basic_set_add_constraint(
 861                 __isl_take isl_basic_set *bset,
 862                 __isl_take isl_constraint *constraint);
 863
 864 For example, to create a set containing the even integers
 865 between 10 and 42, you would use the following code.
 866
 867         isl_int v;
 868         struct isl_dim *dim;
 869         struct isl_constraint *c;
 870         struct isl_basic_set *bset;
 871
 872         isl_int_init(v);
 873         dim = isl_dim_set_alloc(ctx, 0, 2);
 874         bset = isl_basic_set_universe(isl_dim_copy(dim));
 875
 876         c = isl_equality_alloc(isl_dim_copy(dim));
 877         isl_int_set_si(v, -1);
 878         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
 879         isl_int_set_si(v, 2);
 880         isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
 881         bset = isl_basic_set_add_constraint(bset, c);
 882
 883         c = isl_inequality_alloc(isl_dim_copy(dim));
 884         isl_int_set_si(v, -10);
 885         isl_constraint_set_constant(c, v);
 886         isl_int_set_si(v, 1);
 887         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
 888         bset = isl_basic_set_add_constraint(bset, c);
 889
 890         c = isl_inequality_alloc(dim);
 891         isl_int_set_si(v, 42);
 892         isl_constraint_set_constant(c, v);
 893         isl_int_set_si(v, -1);
 894         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
 895         bset = isl_basic_set_add_constraint(bset, c);
 896
 897         bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 1);
 898
 899         isl_int_clear(v);
 900
 901 Or, alternatively,
 902
 903         struct isl_basic_set *bset;
 904         bset = isl_basic_set_read_from_str(ctx,
 905                 "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}", -1);
 906
 907 A basic set or relation can also be constructed from two matrices
 908 describing the equalities and the inequalities.
 909
 910         __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices(
 911                 __isl_take isl_dim *dim,
 912                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
 913                 enum isl_dim_type c1,
 914                 enum isl_dim_type c2, enum isl_dim_type c3,
 915                 enum isl_dim_type c4);
 916         __isl_give isl_basic_map *isl_basic_map_from_constraint_matrices(
 917                 __isl_take isl_dim *dim,
 918                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
 919                 enum isl_dim_type c1,
 920                 enum isl_dim_type c2, enum isl_dim_type c3,
 921                 enum isl_dim_type c4, enum isl_dim_type c5);
 922
 923 The C<isl_dim_type> arguments indicate the order in which
 924 different kinds of variables appear in the input matrices
 925 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
 926 C<isl_dim_set> and C<isl_dim_div> for sets and
 927 of C<isl_dim_cst>, C<isl_dim_param>,
 928 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations.
 929
 930 =head2 Inspecting Sets and Relations
 931
 932 Usually, the user should not have to care about the actual constraints
 933 of the sets and maps, but should instead apply the abstract operations
 934 explained in the following sections.
 935 Occasionally, however, it may be required to inspect the individual
 936 coefficients of the constraints.  This section explains how to do so.
 937 In these cases, it may also be useful to have C<isl> compute
 938 an explicit representation of the existentially quantified variables.
 939
 940         __isl_give isl_set *isl_set_compute_divs(
 941                 __isl_take isl_set *set);
 942         __isl_give isl_map *isl_map_compute_divs(
 943                 __isl_take isl_map *map);
 944         __isl_give isl_union_set *isl_union_set_compute_divs(
 945                 __isl_take isl_union_set *uset);
 946         __isl_give isl_union_map *isl_union_map_compute_divs(
 947                 __isl_take isl_union_map *umap);
 948
 949 This explicit representation defines the existentially quantified
 950 variables as integer divisions of the other variables, possibly
 951 including earlier existentially quantified variables.
 952 An explicitly represented existentially quantified variable therefore
 953 has a unique value when the values of the other variables are known.
 954 If, furthermore, the same existentials, i.e., existentials
 955 with the same explicit representations, should appear in the
 956 same order in each of the disjuncts of a set or map, then the user should call
 957 either of the following functions.
 958
 959         __isl_give isl_set *isl_set_align_divs(
 960                 __isl_take isl_set *set);
 961         __isl_give isl_map *isl_map_align_divs(
 962                 __isl_take isl_map *map);
 963
 964 Alternatively, the existentially quantified variables can be removed
 965 using the following functions, which compute an overapproximation.
 966
 967         __isl_give isl_basic_set *isl_basic_set_remove_divs(
 968                 __isl_take isl_basic_set *bset);
 969         __isl_give isl_basic_map *isl_basic_map_remove_divs(
 970                 __isl_take isl_basic_map *bmap);
 971         __isl_give isl_set *isl_set_remove_divs(
 972                 __isl_take isl_set *set);
 973
 974 To iterate over all the sets or maps in a union set or map, use
 975
 976         int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 977                 int (*fn)(__isl_take isl_set *set, void *user),
 978                 void *user);
 979         int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
 980                 int (*fn)(__isl_take isl_map *map, void *user),
 981                 void *user);
 982
 983 The number of sets or maps in a union set or map can be obtained
 984 from
 985
 986         int isl_union_set_n_set(__isl_keep isl_union_set *uset);
 987         int isl_union_map_n_map(__isl_keep isl_union_map *umap);
 988
 989 To extract the set or map from a union with a given dimension
 990 specification, use
 991
 992         __isl_give isl_set *isl_union_set_extract_set(
 993                 __isl_keep isl_union_set *uset,
 994                 __isl_take isl_dim *dim);
 995         __isl_give isl_map *isl_union_map_extract_map(
 996                 __isl_keep isl_union_map *umap,
 997                 __isl_take isl_dim *dim);
 998
 999 To iterate over all the basic sets or maps in a set or map, use
1000
1001         int isl_set_foreach_basic_set(__isl_keep isl_set *set,
1002                 int (*fn)(__isl_take isl_basic_set *bset, void *user),
1003                 void *user);
1004         int isl_map_foreach_basic_map(__isl_keep isl_map *map,
1005                 int (*fn)(__isl_take isl_basic_map *bmap, void *user),
1006                 void *user);
1007
1008 The callback function C<fn> should return 0 if successful and
1009 -1 if an error occurs.  In the latter case, or if any other error
1010 occurs, the above functions will return -1.
1011
1012 It should be noted that C<isl> does not guarantee that
1013 the basic sets or maps passed to C<fn> are disjoint.
1014 If this is required, then the user should call one of
1015 the following functions first.
1016
1017         __isl_give isl_set *isl_set_make_disjoint(
1018                 __isl_take isl_set *set);
1019         __isl_give isl_map *isl_map_make_disjoint(
1020                 __isl_take isl_map *map);
1021
1022 The number of basic sets in a set can be obtained
1023 from
1024
1025         int isl_set_n_basic_set(__isl_keep isl_set *set);
1026
1027 To iterate over the constraints of a basic set or map, use
1028
1029         #include <isl/constraint.h>
1030
1031         int isl_basic_map_foreach_constraint(
1032                 __isl_keep isl_basic_map *bmap,
1033                 int (*fn)(__isl_take isl_constraint *c, void *user),
1034                 void *user);
1035         void isl_constraint_free(struct isl_constraint *c);
1036
1037 Again, the callback function C<fn> should return 0 if successful and
1038 -1 if an error occurs.  In the latter case, or if any other error
1039 occurs, the above functions will return -1.
1040 The constraint C<c> represents either an equality or an inequality.
1041 Use the following function to find out whether a constraint
1042 represents an equality.  If not, it represents an inequality.
1043
1044         int isl_constraint_is_equality(
1045                 __isl_keep isl_constraint *constraint);
1046
1047 The coefficients of the constraints can be inspected using
1048 the following functions.
1049
1050         void isl_constraint_get_constant(
1051                 __isl_keep isl_constraint *constraint, isl_int *v);
1052         void isl_constraint_get_coefficient(
1053                 __isl_keep isl_constraint *constraint,
1054                 enum isl_dim_type type, int pos, isl_int *v);
1055
1056 The explicit representations of the existentially quantified
1057 variables can be inspected using the following functions.
1058 Note that the user is only allowed to use these functions
1059 if the inspected set or map is the result of a call
1060 to C<isl_set_compute_divs> or C<isl_map_compute_divs>.
1061
1062         __isl_give isl_div *isl_constraint_div(
1063                 __isl_keep isl_constraint *constraint, int pos);
1064         void isl_div_get_constant(__isl_keep isl_div *div,
1065                 isl_int *v);
1066         void isl_div_get_denominator(__isl_keep isl_div *div,
1067                 isl_int *v);
1068         void isl_div_get_coefficient(__isl_keep isl_div *div,
1069                 enum isl_dim_type type, int pos, isl_int *v);
1070
1071 To obtain the constraints of a basic set or map in matrix
1072 form, use the following functions.
1073
1074         __isl_give isl_mat *isl_basic_set_equalities_matrix(
1075                 __isl_keep isl_basic_set *bset,
1076                 enum isl_dim_type c1, enum isl_dim_type c2,
1077                 enum isl_dim_type c3, enum isl_dim_type c4);
1078         __isl_give isl_mat *isl_basic_set_inequalities_matrix(
1079                 __isl_keep isl_basic_set *bset,
1080                 enum isl_dim_type c1, enum isl_dim_type c2,
1081                 enum isl_dim_type c3, enum isl_dim_type c4);
1082         __isl_give isl_mat *isl_basic_map_equalities_matrix(
1083                 __isl_keep isl_basic_map *bmap,
1084                 enum isl_dim_type c1,
1085                 enum isl_dim_type c2, enum isl_dim_type c3,
1086                 enum isl_dim_type c4, enum isl_dim_type c5);
1087         __isl_give isl_mat *isl_basic_map_inequalities_matrix(
1088                 __isl_keep isl_basic_map *bmap,
1089                 enum isl_dim_type c1,
1090                 enum isl_dim_type c2, enum isl_dim_type c3,
1091                 enum isl_dim_type c4, enum isl_dim_type c5);
1092
1093 The C<isl_dim_type> arguments dictate the order in which
1094 different kinds of variables appear in the resulting matrix
1095 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1096 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div>.
1097
1098 The names of the domain and range spaces of a set or relation can be
1099 read off using the following functions.
1100
1101         const char *isl_basic_set_get_tuple_name(
1102                 __isl_keep isl_basic_set *bset);
1103         const char *isl_set_get_tuple_name(
1104                 __isl_keep isl_set *set);
1105         const char *isl_basic_map_get_tuple_name(
1106                 __isl_keep isl_basic_map *bmap,
1107                 enum isl_dim_type type);
1108         const char *isl_map_get_tuple_name(
1109                 __isl_keep isl_map *map,
1110                 enum isl_dim_type type);
1111
1112 As with C<isl_dim_get_tuple_name>, the value returned points to
1113 an internal data structure.
1114 The names of individual dimensions can be read off using
1115 the following functions.
1116
1117         const char *isl_constraint_get_dim_name(
1118                 __isl_keep isl_constraint *constraint,
1119                 enum isl_dim_type type, unsigned pos);
1120         const char *isl_basic_set_get_dim_name(
1121                 __isl_keep isl_basic_set *bset,
1122                 enum isl_dim_type type, unsigned pos);
1123         const char *isl_set_get_dim_name(
1124                 __isl_keep isl_set *set,
1125                 enum isl_dim_type type, unsigned pos);
1126         const char *isl_basic_map_get_dim_name(
1127                 __isl_keep isl_basic_map *bmap,
1128                 enum isl_dim_type type, unsigned pos);
1129         const char *isl_map_get_dim_name(
1130                 __isl_keep isl_map *map,
1131                 enum isl_dim_type type, unsigned pos);
1132
1133 These functions are mostly useful to obtain the names
1134 of the parameters.
1135
1136 =head2 Properties
1137
1138 =head3 Unary Properties
1139
1140 =over
1141
1142 =item * Emptiness
1143
1144 The following functions test whether the given set or relation
1145 contains any integer points.  The ``fast'' variants do not perform
1146 any computations, but simply check if the given set or relation
1147 is already known to be empty.
1148
1149         int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset);
1150         int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset);
1151         int isl_set_is_empty(__isl_keep isl_set *set);
1152         int isl_union_set_is_empty(__isl_keep isl_union_set *uset);
1153         int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap);
1154         int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap);
1155         int isl_map_fast_is_empty(__isl_keep isl_map *map);
1156         int isl_map_is_empty(__isl_keep isl_map *map);
1157         int isl_union_map_is_empty(__isl_keep isl_union_map *umap);
1158
1159 =item * Universality
1160
1161         int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset);
1162         int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
1163         int isl_set_fast_is_universe(__isl_keep isl_set *set);
1164
1165 =item * Single-valuedness
1166
1167         int isl_map_is_single_valued(__isl_keep isl_map *map);
1168
1169 =item * Bijectivity
1170
1171         int isl_map_is_bijective(__isl_keep isl_map *map);
1172
1173 =item * Wrapping
1174
1175 The followning functions check whether the domain of the given
1176 (basic) set is a wrapped relation.
1177
1178         int isl_basic_set_is_wrapping(
1179                 __isl_keep isl_basic_set *bset);
1180         int isl_set_is_wrapping(__isl_keep isl_set *set);
1181
1182 =back
1183
1184 =head3 Binary Properties
1185
1186 =over
1187
1188 =item * Equality
1189
1190         int isl_set_fast_is_equal(__isl_keep isl_set *set1,
1191                 __isl_keep isl_set *set2);
1192         int isl_set_is_equal(__isl_keep isl_set *set1,
1193                 __isl_keep isl_set *set2);
1194         int isl_union_set_is_equal(
1195                 __isl_keep isl_union_set *uset1,
1196                 __isl_keep isl_union_set *uset2);
1197         int isl_basic_map_is_equal(
1198                 __isl_keep isl_basic_map *bmap1,
1199                 __isl_keep isl_basic_map *bmap2);
1200         int isl_map_is_equal(__isl_keep isl_map *map1,
1201                 __isl_keep isl_map *map2);
1202         int isl_map_fast_is_equal(__isl_keep isl_map *map1,
1203                 __isl_keep isl_map *map2);
1204         int isl_union_map_is_equal(
1205                 __isl_keep isl_union_map *umap1,
1206                 __isl_keep isl_union_map *umap2);
1207
1208 =item * Disjointness
1209
1210         int isl_set_fast_is_disjoint(__isl_keep isl_set *set1,
1211                 __isl_keep isl_set *set2);
1212
1213 =item * Subset
1214
1215         int isl_set_is_subset(__isl_keep isl_set *set1,
1216                 __isl_keep isl_set *set2);
1217         int isl_set_is_strict_subset(
1218                 __isl_keep isl_set *set1,
1219                 __isl_keep isl_set *set2);
1220         int isl_union_set_is_subset(
1221                 __isl_keep isl_union_set *uset1,
1222                 __isl_keep isl_union_set *uset2);
1223         int isl_union_set_is_strict_subset(
1224                 __isl_keep isl_union_set *uset1,
1225                 __isl_keep isl_union_set *uset2);
1226         int isl_basic_map_is_subset(
1227                 __isl_keep isl_basic_map *bmap1,
1228                 __isl_keep isl_basic_map *bmap2);
1229         int isl_basic_map_is_strict_subset(
1230                 __isl_keep isl_basic_map *bmap1,
1231                 __isl_keep isl_basic_map *bmap2);
1232         int isl_map_is_subset(
1233                 __isl_keep isl_map *map1,
1234                 __isl_keep isl_map *map2);
1235         int isl_map_is_strict_subset(
1236                 __isl_keep isl_map *map1,
1237                 __isl_keep isl_map *map2);
1238         int isl_union_map_is_subset(
1239                 __isl_keep isl_union_map *umap1,
1240                 __isl_keep isl_union_map *umap2);
1241         int isl_union_map_is_strict_subset(
1242                 __isl_keep isl_union_map *umap1,
1243                 __isl_keep isl_union_map *umap2);
1244
1245 =back
1246
1247 =head2 Unary Operations
1248
1249 =over
1250
1251 =item * Complement
1252
1253         __isl_give isl_set *isl_set_complement(
1254                 __isl_take isl_set *set);
1255
1256 =item * Inverse map
1257
1258         __isl_give isl_basic_map *isl_basic_map_reverse(
1259                 __isl_take isl_basic_map *bmap);
1260         __isl_give isl_map *isl_map_reverse(
1261                 __isl_take isl_map *map);
1262         __isl_give isl_union_map *isl_union_map_reverse(
1263                 __isl_take isl_union_map *umap);
1264
1265 =item * Projection
1266
1267         __isl_give isl_basic_set *isl_basic_set_project_out(
1268                 __isl_take isl_basic_set *bset,
1269                 enum isl_dim_type type, unsigned first, unsigned n);
1270         __isl_give isl_basic_map *isl_basic_map_project_out(
1271                 __isl_take isl_basic_map *bmap,
1272                 enum isl_dim_type type, unsigned first, unsigned n);
1273         __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
1274                 enum isl_dim_type type, unsigned first, unsigned n);
1275         __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
1276                 enum isl_dim_type type, unsigned first, unsigned n);
1277         __isl_give isl_basic_set *isl_basic_map_domain(
1278                 __isl_take isl_basic_map *bmap);
1279         __isl_give isl_basic_set *isl_basic_map_range(
1280                 __isl_take isl_basic_map *bmap);
1281         __isl_give isl_set *isl_map_domain(
1282                 __isl_take isl_map *bmap);
1283         __isl_give isl_set *isl_map_range(
1284                 __isl_take isl_map *map);
1285         __isl_give isl_union_set *isl_union_map_domain(
1286                 __isl_take isl_union_map *umap);
1287         __isl_give isl_union_set *isl_union_map_range(
1288                 __isl_take isl_union_map *umap);
1289
1290         __isl_give isl_basic_map *isl_basic_map_domain_map(
1291                 __isl_take isl_basic_map *bmap);
1292         __isl_give isl_basic_map *isl_basic_map_range_map(
1293                 __isl_take isl_basic_map *bmap);
1294         __isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map);
1295         __isl_give isl_map *isl_map_range_map(__isl_take isl_map *map);
1296         __isl_give isl_union_map *isl_union_map_domain_map(
1297                 __isl_take isl_union_map *umap);
1298         __isl_give isl_union_map *isl_union_map_range_map(
1299                 __isl_take isl_union_map *umap);
1300
1301 The functions above construct a (basic, regular or union) relation
1302 that maps (a wrapped version of) the input relation to its domain or range.
1303
1304 =item * Identity
1305
1306         __isl_give isl_map *isl_set_identity(
1307                 __isl_take isl_set *set);
1308         __isl_give isl_union_map *isl_union_set_identity(
1309                 __isl_take isl_union_set *uset);
1310
1311 Construct an identity relation on the given (union) set.
1312
1313 =item * Deltas
1314
1315         __isl_give isl_basic_set *isl_basic_map_deltas(
1316                 __isl_take isl_basic_map *bmap);
1317         __isl_give isl_set *isl_map_deltas(__isl_take isl_map *map);
1318         __isl_give isl_union_set *isl_union_map_deltas(
1319                 __isl_take isl_union_map *umap);
1320
1321 These functions return a (basic) set containing the differences
1322 between image elements and corresponding domain elements in the input.
1323
1324 =item * Coalescing
1325
1326 Simplify the representation of a set or relation by trying
1327 to combine pairs of basic sets or relations into a single
1328 basic set or relation.
1329
1330         __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set);
1331         __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map);
1332         __isl_give isl_union_set *isl_union_set_coalesce(
1333                 __isl_take isl_union_set *uset);
1334         __isl_give isl_union_map *isl_union_map_coalesce(
1335                 __isl_take isl_union_map *umap);
1336
1337 =item * Detecting equalities
1338
1339         __isl_give isl_basic_set *isl_basic_set_detect_equalities(
1340                 __isl_take isl_basic_set *bset);
1341         __isl_give isl_basic_map *isl_basic_map_detect_equalities(
1342                 __isl_take isl_basic_map *bmap);
1343         __isl_give isl_set *isl_set_detect_equalities(
1344                 __isl_take isl_set *set);
1345         __isl_give isl_map *isl_map_detect_equalities(
1346                 __isl_take isl_map *map);
1347         __isl_give isl_union_set *isl_union_set_detect_equalities(
1348                 __isl_take isl_union_set *uset);
1349         __isl_give isl_union_map *isl_union_map_detect_equalities(
1350                 __isl_take isl_union_map *umap);
1351
1352 Simplify the representation of a set or relation by detecting implicit
1353 equalities.
1354
1355 =item * Convex hull
1356
1357         __isl_give isl_basic_set *isl_set_convex_hull(
1358                 __isl_take isl_set *set);
1359         __isl_give isl_basic_map *isl_map_convex_hull(
1360                 __isl_take isl_map *map);
1361
1362 If the input set or relation has any existentially quantified
1363 variables, then the result of these operations is currently undefined.
1364
1365 =item * Simple hull
1366
1367         __isl_give isl_basic_set *isl_set_simple_hull(
1368                 __isl_take isl_set *set);
1369         __isl_give isl_basic_map *isl_map_simple_hull(
1370                 __isl_take isl_map *map);
1371         __isl_give isl_union_map *isl_union_map_simple_hull(
1372                 __isl_take isl_union_map *umap);
1373
1374 These functions compute a single basic set or relation
1375 that contains the whole input set or relation.
1376 In particular, the output is described by translates
1377 of the constraints describing the basic sets or relations in the input.
1378
1379 =begin latex
1380
1381 (See \autoref{s:simple hull}.)
1382
1383 =end latex
1384
1385 =item * Affine hull
1386
1387         __isl_give isl_basic_set *isl_basic_set_affine_hull(
1388                 __isl_take isl_basic_set *bset);
1389         __isl_give isl_basic_set *isl_set_affine_hull(
1390                 __isl_take isl_set *set);
1391         __isl_give isl_union_set *isl_union_set_affine_hull(
1392                 __isl_take isl_union_set *uset);
1393         __isl_give isl_basic_map *isl_basic_map_affine_hull(
1394                 __isl_take isl_basic_map *bmap);
1395         __isl_give isl_basic_map *isl_map_affine_hull(
1396                 __isl_take isl_map *map);
1397         __isl_give isl_union_map *isl_union_map_affine_hull(
1398                 __isl_take isl_union_map *umap);
1399
1400 In case of union sets and relations, the affine hull is computed
1401 per space.
1402
1403 =item * Polyhedral hull
1404
1405         __isl_give isl_basic_set *isl_set_polyhedral_hull(
1406                 __isl_take isl_set *set);
1407         __isl_give isl_basic_map *isl_map_polyhedral_hull(
1408                 __isl_take isl_map *map);
1409         __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1410                 __isl_take isl_union_set *uset);
1411         __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1412                 __isl_take isl_union_map *umap);
1413
1414 These functions compute a single basic set or relation
1415 not involving any existentially quantified variables
1416 that contains the whole input set or relation.
1417 In case of union sets and relations, the polyhedral hull is computed
1418 per space.
1419
1420 =item * Power
1421
1422         __isl_give isl_map *isl_map_power(__isl_take isl_map *map,
1423                 unsigned param, int *exact);
1424
1425 Compute a parametric representation for all positive powers I<k> of C<map>.
1426 The power I<k> is equated to the parameter at position C<param>.
1427 The result may be an overapproximation.  If the result is exact,
1428 then C<*exact> is set to C<1>.
1429 The current implementation only produces exact results for particular
1430 cases of piecewise translations (i.e., piecewise uniform dependences).
1431
1432 =item * Transitive closure
1433
1434         __isl_give isl_map *isl_map_transitive_closure(
1435                 __isl_take isl_map *map, int *exact);
1436         __isl_give isl_union_map *isl_union_map_transitive_closure(
1437                 __isl_take isl_union_map *umap, int *exact);
1438
1439 Compute the transitive closure of C<map>.
1440 The result may be an overapproximation.  If the result is known to be exact,
1441 then C<*exact> is set to C<1>.
1442 The current implementation only produces exact results for particular
1443 cases of piecewise translations (i.e., piecewise uniform dependences).
1444
1445 =item * Reaching path lengths
1446
1447         __isl_give isl_map *isl_map_reaching_path_lengths(
1448                 __isl_take isl_map *map, int *exact);
1449
1450 Compute a relation that maps each element in the range of C<map>
1451 to the lengths of all paths composed of edges in C<map> that
1452 end up in the given element.
1453 The result may be an overapproximation.  If the result is known to be exact,
1454 then C<*exact> is set to C<1>.
1455 To compute the I<maximal> path length, the resulting relation
1456 should be postprocessed by C<isl_map_lexmax>.
1457 In particular, if the input relation is a dependence relation
1458 (mapping sources to sinks), then the maximal path length corresponds
1459 to the free schedule.
1460 Note, however, that C<isl_map_lexmax> expects the maximum to be
1461 finite, so if the path lengths are unbounded (possibly due to
1462 the overapproximation), then you will get an error message.
1463
1464 =item * Wrapping
1465
1466         __isl_give isl_basic_set *isl_basic_map_wrap(
1467                 __isl_take isl_basic_map *bmap);
1468         __isl_give isl_set *isl_map_wrap(
1469                 __isl_take isl_map *map);
1470         __isl_give isl_union_set *isl_union_map_wrap(
1471                 __isl_take isl_union_map *umap);
1472         __isl_give isl_basic_map *isl_basic_set_unwrap(
1473                 __isl_take isl_basic_set *bset);
1474         __isl_give isl_map *isl_set_unwrap(
1475                 __isl_take isl_set *set);
1476         __isl_give isl_union_map *isl_union_set_unwrap(
1477                 __isl_take isl_union_set *uset);
1478
1479 =item * Flattening
1480
1481 Remove any internal structure of domain (and range) of the given
1482 set or relation.  If there is any such internal structure in the input,
1483 then the name of the space is also removed.
1484
1485         __isl_give isl_basic_set *isl_basic_set_flatten(
1486                 __isl_take isl_basic_set *bset);
1487         __isl_give isl_set *isl_set_flatten(
1488                 __isl_take isl_set *set);
1489         __isl_give isl_basic_map *isl_basic_map_flatten(
1490                 __isl_take isl_basic_map *bmap);
1491         __isl_give isl_map *isl_map_flatten(
1492                 __isl_take isl_map *map);
1493
1494         __isl_give isl_map *isl_set_flatten_map(
1495                 __isl_take isl_set *set);
1496
1497 The function above constructs a relation
1498 that maps the input set to a flattened version of the set.
1499
1500 =item * Dimension manipulation
1501
1502         __isl_give isl_set *isl_set_add_dims(
1503                 __isl_take isl_set *set,
1504                 enum isl_dim_type type, unsigned n);
1505         __isl_give isl_map *isl_map_add_dims(
1506                 __isl_take isl_map *map,
1507                 enum isl_dim_type type, unsigned n);
1508
1509 It is usually not advisable to directly change the (input or output)
1510 space of a set or a relation as this removes the name and the internal
1511 structure of the space.  However, the above functions can be useful
1512 to add new parameters.
1513
1514 =back
1515
1516 =head2 Binary Operations
1517
1518 The two arguments of a binary operation not only need to live
1519 in the same C<isl_ctx>, they currently also need to have
1520 the same (number of) parameters.
1521
1522 =head3 Basic Operations
1523
1524 =over
1525
1526 =item * Intersection
1527
1528         __isl_give isl_basic_set *isl_basic_set_intersect(
1529                 __isl_take isl_basic_set *bset1,
1530                 __isl_take isl_basic_set *bset2);
1531         __isl_give isl_set *isl_set_intersect(
1532                 __isl_take isl_set *set1,
1533                 __isl_take isl_set *set2);
1534         __isl_give isl_union_set *isl_union_set_intersect(
1535                 __isl_take isl_union_set *uset1,
1536                 __isl_take isl_union_set *uset2);
1537         __isl_give isl_basic_map *isl_basic_map_intersect_domain(
1538                 __isl_take isl_basic_map *bmap,
1539                 __isl_take isl_basic_set *bset);
1540         __isl_give isl_basic_map *isl_basic_map_intersect_range(
1541                 __isl_take isl_basic_map *bmap,
1542                 __isl_take isl_basic_set *bset);
1543         __isl_give isl_basic_map *isl_basic_map_intersect(
1544                 __isl_take isl_basic_map *bmap1,
1545                 __isl_take isl_basic_map *bmap2);
1546         __isl_give isl_map *isl_map_intersect_domain(
1547                 __isl_take isl_map *map,
1548                 __isl_take isl_set *set);
1549         __isl_give isl_map *isl_map_intersect_range(
1550                 __isl_take isl_map *map,
1551                 __isl_take isl_set *set);
1552         __isl_give isl_map *isl_map_intersect(
1553                 __isl_take isl_map *map1,
1554                 __isl_take isl_map *map2);
1555         __isl_give isl_union_map *isl_union_map_intersect_domain(
1556                 __isl_take isl_union_map *umap,
1557                 __isl_take isl_union_set *uset);
1558         __isl_give isl_union_map *isl_union_map_intersect_range(
1559                 __isl_take isl_union_map *umap,
1560                 __isl_take isl_union_set *uset);
1561         __isl_give isl_union_map *isl_union_map_intersect(
1562                 __isl_take isl_union_map *umap1,
1563                 __isl_take isl_union_map *umap2);
1564
1565 =item * Union
1566
1567         __isl_give isl_set *isl_basic_set_union(
1568                 __isl_take isl_basic_set *bset1,
1569                 __isl_take isl_basic_set *bset2);
1570         __isl_give isl_map *isl_basic_map_union(
1571                 __isl_take isl_basic_map *bmap1,
1572                 __isl_take isl_basic_map *bmap2);
1573         __isl_give isl_set *isl_set_union(
1574                 __isl_take isl_set *set1,
1575                 __isl_take isl_set *set2);
1576         __isl_give isl_map *isl_map_union(
1577                 __isl_take isl_map *map1,
1578                 __isl_take isl_map *map2);
1579         __isl_give isl_union_set *isl_union_set_union(
1580                 __isl_take isl_union_set *uset1,
1581                 __isl_take isl_union_set *uset2);
1582         __isl_give isl_union_map *isl_union_map_union(
1583                 __isl_take isl_union_map *umap1,
1584                 __isl_take isl_union_map *umap2);
1585
1586 =item * Set difference
1587
1588         __isl_give isl_set *isl_set_subtract(
1589                 __isl_take isl_set *set1,
1590                 __isl_take isl_set *set2);
1591         __isl_give isl_map *isl_map_subtract(
1592                 __isl_take isl_map *map1,
1593                 __isl_take isl_map *map2);
1594         __isl_give isl_union_set *isl_union_set_subtract(
1595                 __isl_take isl_union_set *uset1,
1596                 __isl_take isl_union_set *uset2);
1597         __isl_give isl_union_map *isl_union_map_subtract(
1598                 __isl_take isl_union_map *umap1,
1599                 __isl_take isl_union_map *umap2);
1600
1601 =item * Application
1602
1603         __isl_give isl_basic_set *isl_basic_set_apply(
1604                 __isl_take isl_basic_set *bset,
1605                 __isl_take isl_basic_map *bmap);
1606         __isl_give isl_set *isl_set_apply(
1607                 __isl_take isl_set *set,
1608                 __isl_take isl_map *map);
1609         __isl_give isl_union_set *isl_union_set_apply(
1610                 __isl_take isl_union_set *uset,
1611                 __isl_take isl_union_map *umap);
1612         __isl_give isl_basic_map *isl_basic_map_apply_domain(
1613                 __isl_take isl_basic_map *bmap1,
1614                 __isl_take isl_basic_map *bmap2);
1615         __isl_give isl_basic_map *isl_basic_map_apply_range(
1616                 __isl_take isl_basic_map *bmap1,
1617                 __isl_take isl_basic_map *bmap2);
1618         __isl_give isl_map *isl_map_apply_domain(
1619                 __isl_take isl_map *map1,
1620                 __isl_take isl_map *map2);
1621         __isl_give isl_union_map *isl_union_map_apply_domain(
1622                 __isl_take isl_union_map *umap1,
1623                 __isl_take isl_union_map *umap2);
1624         __isl_give isl_map *isl_map_apply_range(
1625                 __isl_take isl_map *map1,
1626                 __isl_take isl_map *map2);
1627         __isl_give isl_union_map *isl_union_map_apply_range(
1628                 __isl_take isl_union_map *umap1,
1629                 __isl_take isl_union_map *umap2);
1630
1631 =item * Cartesian Product
1632
1633         __isl_give isl_set *isl_set_product(
1634                 __isl_take isl_set *set1,
1635                 __isl_take isl_set *set2);
1636         __isl_give isl_union_set *isl_union_set_product(
1637                 __isl_take isl_union_set *uset1,
1638                 __isl_take isl_union_set *uset2);
1639         __isl_give isl_basic_map *isl_basic_map_range_product(
1640                 __isl_take isl_basic_map *bmap1,
1641                 __isl_take isl_basic_map *bmap2);
1642         __isl_give isl_map *isl_map_range_product(
1643                 __isl_take isl_map *map1,
1644                 __isl_take isl_map *map2);
1645         __isl_give isl_union_map *isl_union_map_range_product(
1646                 __isl_take isl_union_map *umap1,
1647                 __isl_take isl_union_map *umap2);
1648         __isl_give isl_map *isl_map_product(
1649                 __isl_take isl_map *map1,
1650                 __isl_take isl_map *map2);
1651         __isl_give isl_union_map *isl_union_map_product(
1652                 __isl_take isl_union_map *umap1,
1653                 __isl_take isl_union_map *umap2);
1654
1655 The above functions compute the cross product of the given
1656 sets or relations.  The domains and ranges of the results
1657 are wrapped maps between domains and ranges of the inputs.
1658 To obtain a ``flat'' product, use the following functions
1659 instead.
1660
1661         __isl_give isl_basic_set *isl_basic_set_flat_product(
1662                 __isl_take isl_basic_set *bset1,
1663                 __isl_take isl_basic_set *bset2);
1664         __isl_give isl_set *isl_set_flat_product(
1665                 __isl_take isl_set *set1,
1666                 __isl_take isl_set *set2);
1667         __isl_give isl_basic_map *isl_basic_map_flat_product(
1668                 __isl_take isl_basic_map *bmap1,
1669                 __isl_take isl_basic_map *bmap2);
1670         __isl_give isl_map *isl_map_flat_product(
1671                 __isl_take isl_map *map1,
1672                 __isl_take isl_map *map2);
1673
1674 =item * Simplification
1675
1676         __isl_give isl_basic_set *isl_basic_set_gist(
1677                 __isl_take isl_basic_set *bset,
1678                 __isl_take isl_basic_set *context);
1679         __isl_give isl_set *isl_set_gist(__isl_take isl_set *set,
1680                 __isl_take isl_set *context);
1681         __isl_give isl_union_set *isl_union_set_gist(
1682                 __isl_take isl_union_set *uset,
1683                 __isl_take isl_union_set *context);
1684         __isl_give isl_basic_map *isl_basic_map_gist(
1685                 __isl_take isl_basic_map *bmap,
1686                 __isl_take isl_basic_map *context);
1687         __isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
1688                 __isl_take isl_map *context);
1689         __isl_give isl_union_map *isl_union_map_gist(
1690                 __isl_take isl_union_map *umap,
1691                 __isl_take isl_union_map *context);
1692
1693 The gist operation returns a set or relation that has the
1694 same intersection with the context as the input set or relation.
1695 Any implicit equality in the intersection is made explicit in the result,
1696 while all inequalities that are redundant with respect to the intersection
1697 are removed.
1698 In case of union sets and relations, the gist operation is performed
1699 per space.
1700
1701 =back
1702
1703 =head3 Lexicographic Optimization
1704
1705 Given a (basic) set C<set> (or C<bset>) and a zero-dimensional domain C<dom>,
1706 the following functions
1707 compute a set that contains the lexicographic minimum or maximum
1708 of the elements in C<set> (or C<bset>) for those values of the parameters
1709 that satisfy C<dom>.
1710 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
1711 that contains the parameter values in C<dom> for which C<set> (or C<bset>)
1712 has no elements.
1713 In other words, the union of the parameter values
1714 for which the result is non-empty and of C<*empty>
1715 is equal to C<dom>.
1716
1717         __isl_give isl_set *isl_basic_set_partial_lexmin(
1718                 __isl_take isl_basic_set *bset,
1719                 __isl_take isl_basic_set *dom,
1720                 __isl_give isl_set **empty);
1721         __isl_give isl_set *isl_basic_set_partial_lexmax(
1722                 __isl_take isl_basic_set *bset,
1723                 __isl_take isl_basic_set *dom,
1724                 __isl_give isl_set **empty);
1725         __isl_give isl_set *isl_set_partial_lexmin(
1726                 __isl_take isl_set *set, __isl_take isl_set *dom,
1727                 __isl_give isl_set **empty);
1728         __isl_give isl_set *isl_set_partial_lexmax(
1729                 __isl_take isl_set *set, __isl_take isl_set *dom,
1730                 __isl_give isl_set **empty);
1731
1732 Given a (basic) set C<set> (or C<bset>), the following functions simply
1733 return a set containing the lexicographic minimum or maximum
1734 of the elements in C<set> (or C<bset>).
1735 In case of union sets, the optimum is computed per space.
1736
1737         __isl_give isl_set *isl_basic_set_lexmin(
1738                 __isl_take isl_basic_set *bset);
1739         __isl_give isl_set *isl_basic_set_lexmax(
1740                 __isl_take isl_basic_set *bset);
1741         __isl_give isl_set *isl_set_lexmin(
1742                 __isl_take isl_set *set);
1743         __isl_give isl_set *isl_set_lexmax(
1744                 __isl_take isl_set *set);
1745         __isl_give isl_union_set *isl_union_set_lexmin(
1746                 __isl_take isl_union_set *uset);
1747         __isl_give isl_union_set *isl_union_set_lexmax(
1748                 __isl_take isl_union_set *uset);
1749
1750 Given a (basic) relation C<map> (or C<bmap>) and a domain C<dom>,
1751 the following functions
1752 compute a relation that maps each element of C<dom>
1753 to the single lexicographic minimum or maximum
1754 of the elements that are associated to that same
1755 element in C<map> (or C<bmap>).
1756 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
1757 that contains the elements in C<dom> that do not map
1758 to any elements in C<map> (or C<bmap>).
1759 In other words, the union of the domain of the result and of C<*empty>
1760 is equal to C<dom>.
1761
1762         __isl_give isl_map *isl_basic_map_partial_lexmax(
1763                 __isl_take isl_basic_map *bmap,
1764                 __isl_take isl_basic_set *dom,
1765                 __isl_give isl_set **empty);
1766         __isl_give isl_map *isl_basic_map_partial_lexmin(
1767                 __isl_take isl_basic_map *bmap,
1768                 __isl_take isl_basic_set *dom,
1769                 __isl_give isl_set **empty);
1770         __isl_give isl_map *isl_map_partial_lexmax(
1771                 __isl_take isl_map *map, __isl_take isl_set *dom,
1772                 __isl_give isl_set **empty);
1773         __isl_give isl_map *isl_map_partial_lexmin(
1774                 __isl_take isl_map *map, __isl_take isl_set *dom,
1775                 __isl_give isl_set **empty);
1776
1777 Given a (basic) map C<map> (or C<bmap>), the following functions simply
1778 return a map mapping each element in the domain of
1779 C<map> (or C<bmap>) to the lexicographic minimum or maximum
1780 of all elements associated to that element.
1781 In case of union relations, the optimum is computed per space.
1782
1783         __isl_give isl_map *isl_basic_map_lexmin(
1784                 __isl_take isl_basic_map *bmap);
1785         __isl_give isl_map *isl_basic_map_lexmax(
1786                 __isl_take isl_basic_map *bmap);
1787         __isl_give isl_map *isl_map_lexmin(
1788                 __isl_take isl_map *map);
1789         __isl_give isl_map *isl_map_lexmax(
1790                 __isl_take isl_map *map);
1791         __isl_give isl_union_map *isl_union_map_lexmin(
1792                 __isl_take isl_union_map *umap);
1793         __isl_give isl_union_map *isl_union_map_lexmax(
1794                 __isl_take isl_union_map *umap);
1795
1796 =head2 Matrices
1797
1798 Matrices can be created, copied and freed using the following functions.
1799
1800         #include <isl/mat.h>
1801         __isl_give isl_mat *isl_mat_alloc(struct isl_ctx *ctx,
1802                 unsigned n_row, unsigned n_col);
1803         __isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat);
1804         void isl_mat_free(__isl_take isl_mat *mat);
1805
1806 Note that the elements of a newly created matrix may have arbitrary values.
1807 The elements can be changed and inspected using the following functions.
1808
1809         int isl_mat_rows(__isl_keep isl_mat *mat);
1810         int isl_mat_cols(__isl_keep isl_mat *mat);
1811         int isl_mat_get_element(__isl_keep isl_mat *mat,
1812                 int row, int col, isl_int *v);
1813         __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat,
1814                 int row, int col, isl_int v);
1815
1816 C<isl_mat_get_element> will return a negative value if anything went wrong.
1817 In that case, the value of C<*v> is undefined.
1818
1819 The following function can be used to compute the (right) inverse
1820 of a matrix, i.e., a matrix such that the product of the original
1821 and the inverse (in that order) is a multiple of the identity matrix.
1822 The input matrix is assumed to be of full row-rank.
1823
1824         __isl_give isl_mat *isl_mat_right_inverse(__isl_take isl_mat *mat);
1825
1826 The following function can be used to compute the (right) kernel
1827 (or null space) of a matrix, i.e., a matrix such that the product of
1828 the original and the kernel (in that order) is the zero matrix.
1829
1830         __isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat);
1831
1832 =head2 Points
1833
1834 Points are elements of a set.  They can be used to construct
1835 simple sets (boxes) or they can be used to represent the
1836 individual elements of a set.
1837 The zero point (the origin) can be created using
1838
1839         __isl_give isl_point *isl_point_zero(__isl_take isl_dim *dim);
1840
1841 The coordinates of a point can be inspected, set and changed
1842 using
1843
1844         void isl_point_get_coordinate(__isl_keep isl_point *pnt,
1845                 enum isl_dim_type type, int pos, isl_int *v);
1846         __isl_give isl_point *isl_point_set_coordinate(
1847                 __isl_take isl_point *pnt,
1848                 enum isl_dim_type type, int pos, isl_int v);
1849
1850         __isl_give isl_point *isl_point_add_ui(
1851                 __isl_take isl_point *pnt,
1852                 enum isl_dim_type type, int pos, unsigned val);
1853         __isl_give isl_point *isl_point_sub_ui(
1854                 __isl_take isl_point *pnt,
1855                 enum isl_dim_type type, int pos, unsigned val);
1856
1857 Points can be copied or freed using
1858
1859         __isl_give isl_point *isl_point_copy(
1860                 __isl_keep isl_point *pnt);
1861         void isl_point_free(__isl_take isl_point *pnt);
1862
1863 A singleton set can be created from a point using
1864
1865         __isl_give isl_basic_set *isl_basic_set_from_point(
1866                 __isl_take isl_point *pnt);
1867         __isl_give isl_set *isl_set_from_point(
1868                 __isl_take isl_point *pnt);
1869
1870 and a box can be created from two opposite extremal points using
1871
1872         __isl_give isl_basic_set *isl_basic_set_box_from_points(
1873                 __isl_take isl_point *pnt1,
1874                 __isl_take isl_point *pnt2);
1875         __isl_give isl_set *isl_set_box_from_points(
1876                 __isl_take isl_point *pnt1,
1877                 __isl_take isl_point *pnt2);
1878
1879 All elements of a B<bounded> (union) set can be enumerated using
1880 the following functions.
1881
1882         int isl_set_foreach_point(__isl_keep isl_set *set,
1883                 int (*fn)(__isl_take isl_point *pnt, void *user),
1884                 void *user);
1885         int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
1886                 int (*fn)(__isl_take isl_point *pnt, void *user),
1887                 void *user);
1888
1889 The function C<fn> is called for each integer point in
1890 C<set> with as second argument the last argument of
1891 the C<isl_set_foreach_point> call.  The function C<fn>
1892 should return C<0> on success and C<-1> on failure.
1893 In the latter case, C<isl_set_foreach_point> will stop
1894 enumerating and return C<-1> as well.
1895 If the enumeration is performed successfully and to completion,
1896 then C<isl_set_foreach_point> returns C<0>.
1897
1898 To obtain a single point of a (basic) set, use
1899
1900         __isl_give isl_point *isl_basic_set_sample_point(
1901                 __isl_take isl_basic_set *bset);
1902         __isl_give isl_point *isl_set_sample_point(
1903                 __isl_take isl_set *set);
1904
1905 If C<set> does not contain any (integer) points, then the
1906 resulting point will be ``void'', a property that can be
1907 tested using
1908
1909         int isl_point_is_void(__isl_keep isl_point *pnt);
1910
1911 =head2 Piecewise Quasipolynomials
1912
1913 A piecewise quasipolynomial is a particular kind of function that maps
1914 a parametric point to a rational value.
1915 More specifically, a quasipolynomial is a polynomial expression in greatest
1916 integer parts of affine expressions of parameters and variables.
1917 A piecewise quasipolynomial is a subdivision of a given parametric
1918 domain into disjoint cells with a quasipolynomial associated to
1919 each cell.  The value of the piecewise quasipolynomial at a given
1920 point is the value of the quasipolynomial associated to the cell
1921 that contains the point.  Outside of the union of cells,
1922 the value is assumed to be zero.
1923 For example, the piecewise quasipolynomial
1924
1925         [n] -> { [x] -> ((1 + n) - x) : x <= n and x >= 0 }
1926
1927 maps C<x> to C<1 + n - x> for values of C<x> between C<0> and C<n>.
1928 A given piecewise quasipolynomial has a fixed domain dimension.
1929 Union piecewise quasipolynomials are used to contain piecewise quasipolynomials
1930 defined over different domains.
1931 Piecewise quasipolynomials are mainly used by the C<barvinok>
1932 library for representing the number of elements in a parametric set or map.
1933 For example, the piecewise quasipolynomial above represents
1934 the number of points in the map
1935
1936         [n] -> { [x] -> [y] : x,y >= 0 and 0 <= x + y <= n }
1937
1938 =head3 Printing (Piecewise) Quasipolynomials
1939
1940 Quasipolynomials and piecewise quasipolynomials can be printed
1941 using the following functions.
1942
1943         __isl_give isl_printer *isl_printer_print_qpolynomial(
1944                 __isl_take isl_printer *p,
1945                 __isl_keep isl_qpolynomial *qp);
1946
1947         __isl_give isl_printer *isl_printer_print_pw_qpolynomial(
1948                 __isl_take isl_printer *p,
1949                 __isl_keep isl_pw_qpolynomial *pwqp);
1950
1951         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial(
1952                 __isl_take isl_printer *p,
1953                 __isl_keep isl_union_pw_qpolynomial *upwqp);
1954
1955 The output format of the printer
1956 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
1957 For C<isl_printer_print_union_pw_qpolynomial>, only C<ISL_FORMAT_ISL>
1958 is supported.
1959 In case of printing in C<ISL_FORMAT_C>, the user may want
1960 to set the names of all dimensions
1961
1962         __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
1963                 __isl_take isl_qpolynomial *qp,
1964                 enum isl_dim_type type, unsigned pos,
1965                 const char *s);
1966         __isl_give isl_pw_qpolynomial *
1967         isl_pw_qpolynomial_set_dim_name(
1968                 __isl_take isl_pw_qpolynomial *pwqp,
1969                 enum isl_dim_type type, unsigned pos,
1970                 const char *s);
1971
1972 =head3 Creating New (Piecewise) Quasipolynomials
1973
1974 Some simple quasipolynomials can be created using the following functions.
1975 More complicated quasipolynomials can be created by applying
1976 operations such as addition and multiplication
1977 on the resulting quasipolynomials
1978
1979         __isl_give isl_qpolynomial *isl_qpolynomial_zero(
1980                 __isl_take isl_dim *dim);
1981         __isl_give isl_qpolynomial *isl_qpolynomial_one(
1982                 __isl_take isl_dim *dim);
1983         __isl_give isl_qpolynomial *isl_qpolynomial_infty(
1984                 __isl_take isl_dim *dim);
1985         __isl_give isl_qpolynomial *isl_qpolynomial_neginfty(
1986                 __isl_take isl_dim *dim);
1987         __isl_give isl_qpolynomial *isl_qpolynomial_nan(
1988                 __isl_take isl_dim *dim);
1989         __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(
1990                 __isl_take isl_dim *dim,
1991                 const isl_int n, const isl_int d);
1992         __isl_give isl_qpolynomial *isl_qpolynomial_div(
1993                 __isl_take isl_div *div);
1994         __isl_give isl_qpolynomial *isl_qpolynomial_var(
1995                 __isl_take isl_dim *dim,
1996                 enum isl_dim_type type, unsigned pos);
1997
1998 The zero piecewise quasipolynomial or a piecewise quasipolynomial
1999 with a single cell can be created using the following functions.
2000 Multiple of these single cell piecewise quasipolynomials can
2001 be combined to create more complicated piecewise quasipolynomials.
2002
2003         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_zero(
2004                 __isl_take isl_dim *dim);
2005         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_alloc(
2006                 __isl_take isl_set *set,
2007                 __isl_take isl_qpolynomial *qp);
2008
2009         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_zero(
2010                 __isl_take isl_dim *dim);
2011         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_from_pw_qpolynomial(
2012                 __isl_take isl_pw_qpolynomial *pwqp);
2013         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add_pw_qpolynomial(
2014                 __isl_take isl_union_pw_qpolynomial *upwqp,
2015                 __isl_take isl_pw_qpolynomial *pwqp);
2016
2017 Quasipolynomials can be copied and freed again using the following
2018 functions.
2019
2020         __isl_give isl_qpolynomial *isl_qpolynomial_copy(
2021                 __isl_keep isl_qpolynomial *qp);
2022         void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp);
2023
2024         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_copy(
2025                 __isl_keep isl_pw_qpolynomial *pwqp);
2026         void isl_pw_qpolynomial_free(
2027                 __isl_take isl_pw_qpolynomial *pwqp);
2028
2029         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_copy(
2030                 __isl_keep isl_union_pw_qpolynomial *upwqp);
2031         void isl_union_pw_qpolynomial_free(
2032                 __isl_take isl_union_pw_qpolynomial *upwqp);
2033
2034 =head3 Inspecting (Piecewise) Quasipolynomials
2035
2036 To iterate over all piecewise quasipolynomials in a union
2037 piecewise quasipolynomial, use the following function
2038
2039         int isl_union_pw_qpolynomial_foreach_pw_qpolynomial(
2040                 __isl_keep isl_union_pw_qpolynomial *upwqp,
2041                 int (*fn)(__isl_take isl_pw_qpolynomial *pwqp, void *user),
2042                 void *user);
2043
2044 To extract the piecewise quasipolynomial from a union with a given dimension
2045 specification, use
2046
2047         __isl_give isl_pw_qpolynomial *
2048         isl_union_pw_qpolynomial_extract_pw_qpolynomial(
2049                 __isl_keep isl_union_pw_qpolynomial *upwqp,
2050                 __isl_take isl_dim *dim);
2051
2052 To iterate over the cells in a piecewise quasipolynomial,
2053 use either of the following two functions
2054
2055         int isl_pw_qpolynomial_foreach_piece(
2056                 __isl_keep isl_pw_qpolynomial *pwqp,
2057                 int (*fn)(__isl_take isl_set *set,
2058                           __isl_take isl_qpolynomial *qp,
2059                           void *user), void *user);
2060         int isl_pw_qpolynomial_foreach_lifted_piece(
2061                 __isl_keep isl_pw_qpolynomial *pwqp,
2062                 int (*fn)(__isl_take isl_set *set,
2063                           __isl_take isl_qpolynomial *qp,
2064                           void *user), void *user);
2065
2066 As usual, the function C<fn> should return C<0> on success
2067 and C<-1> on failure.  The difference between
2068 C<isl_pw_qpolynomial_foreach_piece> and
2069 C<isl_pw_qpolynomial_foreach_lifted_piece> is that
2070 C<isl_pw_qpolynomial_foreach_lifted_piece> will first
2071 compute unique representations for all existentially quantified
2072 variables and then turn these existentially quantified variables
2073 into extra set variables, adapting the associated quasipolynomial
2074 accordingly.  This means that the C<set> passed to C<fn>
2075 will not have any existentially quantified variables, but that
2076 the dimensions of the sets may be different for different
2077 invocations of C<fn>.
2078
2079 To iterate over all terms in a quasipolynomial,
2080 use
2081
2082         int isl_qpolynomial_foreach_term(
2083                 __isl_keep isl_qpolynomial *qp,
2084                 int (*fn)(__isl_take isl_term *term,
2085                           void *user), void *user);
2086
2087 The terms themselves can be inspected and freed using
2088 these functions
2089
2090         unsigned isl_term_dim(__isl_keep isl_term *term,
2091                 enum isl_dim_type type);
2092         void isl_term_get_num(__isl_keep isl_term *term,
2093                 isl_int *n);
2094         void isl_term_get_den(__isl_keep isl_term *term,
2095                 isl_int *d);
2096         int isl_term_get_exp(__isl_keep isl_term *term,
2097                 enum isl_dim_type type, unsigned pos);
2098         __isl_give isl_div *isl_term_get_div(
2099                 __isl_keep isl_term *term, unsigned pos);
2100         void isl_term_free(__isl_take isl_term *term);
2101
2102 Each term is a product of parameters, set variables and
2103 integer divisions.  The function C<isl_term_get_exp>
2104 returns the exponent of a given dimensions in the given term.
2105 The C<isl_int>s in the arguments of C<isl_term_get_num>
2106 and C<isl_term_get_den> need to have been initialized
2107 using C<isl_int_init> before calling these functions.
2108
2109 =head3 Properties of (Piecewise) Quasipolynomials
2110
2111 To check whether a quasipolynomial is actually a constant,
2112 use the following function.
2113
2114         int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
2115                 isl_int *n, isl_int *d);
2116
2117 If C<qp> is a constant and if C<n> and C<d> are not C<NULL>
2118 then the numerator and denominator of the constant
2119 are returned in C<*n> and C<*d>, respectively.
2120
2121 =head3 Operations on (Piecewise) Quasipolynomials
2122
2123         __isl_give isl_qpolynomial *isl_qpolynomial_neg(
2124                 __isl_take isl_qpolynomial *qp);
2125         __isl_give isl_qpolynomial *isl_qpolynomial_add(
2126                 __isl_take isl_qpolynomial *qp1,
2127                 __isl_take isl_qpolynomial *qp2);
2128         __isl_give isl_qpolynomial *isl_qpolynomial_sub(
2129                 __isl_take isl_qpolynomial *qp1,
2130                 __isl_take isl_qpolynomial *qp2);
2131         __isl_give isl_qpolynomial *isl_qpolynomial_mul(
2132                 __isl_take isl_qpolynomial *qp1,
2133                 __isl_take isl_qpolynomial *qp2);
2134         __isl_give isl_qpolynomial *isl_qpolynomial_pow(
2135                 __isl_take isl_qpolynomial *qp, unsigned exponent);
2136
2137         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
2138                 __isl_take isl_pw_qpolynomial *pwqp1,
2139                 __isl_take isl_pw_qpolynomial *pwqp2);
2140         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
2141                 __isl_take isl_pw_qpolynomial *pwqp1,
2142                 __isl_take isl_pw_qpolynomial *pwqp2);
2143         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_disjoint(
2144                 __isl_take isl_pw_qpolynomial *pwqp1,
2145                 __isl_take isl_pw_qpolynomial *pwqp2);
2146         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
2147                 __isl_take isl_pw_qpolynomial *pwqp);
2148         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
2149                 __isl_take isl_pw_qpolynomial *pwqp1,
2150                 __isl_take isl_pw_qpolynomial *pwqp2);
2151
2152         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add(
2153                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2154                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2155         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
2156                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2157                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2158         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
2159                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2160                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2161
2162         __isl_give isl_qpolynomial *isl_pw_qpolynomial_eval(
2163                 __isl_take isl_pw_qpolynomial *pwqp,
2164                 __isl_take isl_point *pnt);
2165
2166         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_eval(
2167                 __isl_take isl_union_pw_qpolynomial *upwqp,
2168                 __isl_take isl_point *pnt);
2169
2170         __isl_give isl_set *isl_pw_qpolynomial_domain(
2171                 __isl_take isl_pw_qpolynomial *pwqp);
2172         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_intersect_domain(
2173                 __isl_take isl_pw_qpolynomial *pwpq,
2174                 __isl_take isl_set *set);
2175
2176         __isl_give isl_union_set *isl_union_pw_qpolynomial_domain(
2177                 __isl_take isl_union_pw_qpolynomial *upwqp);
2178         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_intersect_domain(
2179                 __isl_take isl_union_pw_qpolynomial *upwpq,
2180                 __isl_take isl_union_set *uset);
2181
2182         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_coalesce(
2183                 __isl_take isl_union_pw_qpolynomial *upwqp);
2184
2185         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist(
2186                 __isl_take isl_pw_qpolynomial *pwqp,
2187                 __isl_take isl_set *context);
2188
2189         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_gist(
2190                 __isl_take isl_union_pw_qpolynomial *upwqp,
2191                 __isl_take isl_union_set *context);
2192
2193 The gist operation applies the gist operation to each of
2194 the cells in the domain of the input piecewise quasipolynomial.
2195 The context is also exploited
2196 to simplify the quasipolynomials associated to each cell.
2197
2198         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
2199                 __isl_take isl_pw_qpolynomial *pwqp, int sign);
2200         __isl_give isl_union_pw_qpolynomial *
2201         isl_union_pw_qpolynomial_to_polynomial(
2202                 __isl_take isl_union_pw_qpolynomial *upwqp, int sign);
2203
2204 Approximate each quasipolynomial by a polynomial.  If C<sign> is positive,
2205 the polynomial will be an overapproximation.  If C<sign> is negative,
2206 it will be an underapproximation.  If C<sign> is zero, the approximation
2207 will lie somewhere in between.
2208
2209 =head2 Bounds on Piecewise Quasipolynomials and Piecewise Quasipolynomial Reductions
2210
2211 A piecewise quasipolynomial reduction is a piecewise
2212 reduction (or fold) of quasipolynomials.
2213 In particular, the reduction can be maximum or a minimum.
2214 The objects are mainly used to represent the result of
2215 an upper or lower bound on a quasipolynomial over its domain,
2216 i.e., as the result of the following function.
2217
2218         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
2219                 __isl_take isl_pw_qpolynomial *pwqp,
2220                 enum isl_fold type, int *tight);
2221
2222         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
2223                 __isl_take isl_union_pw_qpolynomial *upwqp,
2224                 enum isl_fold type, int *tight);
2225
2226 The C<type> argument may be either C<isl_fold_min> or C<isl_fold_max>.
2227 If C<tight> is not C<NULL>, then C<*tight> is set to C<1>
2228 is the returned bound is known be tight, i.e., for each value
2229 of the parameters there is at least
2230 one element in the domain that reaches the bound.
2231 If the domain of C<pwqp> is not wrapping, then the bound is computed
2232 over all elements in that domain and the result has a purely parametric
2233 domain.  If the domain of C<pwqp> is wrapping, then the bound is
2234 computed over the range of the wrapped relation.  The domain of the
2235 wrapped relation becomes the domain of the result.
2236
2237 A (piecewise) quasipolynomial reduction can be copied or freed using the
2238 following functions.
2239
2240         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
2241                 __isl_keep isl_qpolynomial_fold *fold);
2242         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_copy(
2243                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2244         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_copy(
2245                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2246         void isl_qpolynomial_fold_free(
2247                 __isl_take isl_qpolynomial_fold *fold);
2248         void isl_pw_qpolynomial_fold_free(
2249                 __isl_take isl_pw_qpolynomial_fold *pwf);
2250         void isl_union_pw_qpolynomial_fold_free(
2251                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2252
2253 =head3 Printing Piecewise Quasipolynomial Reductions
2254
2255 Piecewise quasipolynomial reductions can be printed
2256 using the following function.
2257
2258         __isl_give isl_printer *isl_printer_print_pw_qpolynomial_fold(
2259                 __isl_take isl_printer *p,
2260                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2261         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial_fold(
2262                 __isl_take isl_printer *p,
2263                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2264
2265 For C<isl_printer_print_pw_qpolynomial_fold>,
2266 output format of the printer
2267 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
2268 For C<isl_printer_print_union_pw_qpolynomial_fold>,
2269 output format of the printer
2270 needs to be set to C<ISL_FORMAT_ISL>.
2271 In case of printing in C<ISL_FORMAT_C>, the user may want
2272 to set the names of all dimensions
2273
2274         __isl_give isl_pw_qpolynomial_fold *
2275         isl_pw_qpolynomial_fold_set_dim_name(
2276                 __isl_take isl_pw_qpolynomial_fold *pwf,
2277                 enum isl_dim_type type, unsigned pos,
2278                 const char *s);
2279
2280 =head3 Inspecting (Piecewise) Quasipolynomial Reductions
2281
2282 To iterate over all piecewise quasipolynomial reductions in a union
2283 piecewise quasipolynomial reduction, use the following function
2284
2285         int isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
2286                 __isl_keep isl_union_pw_qpolynomial_fold *upwf,
2287                 int (*fn)(__isl_take isl_pw_qpolynomial_fold *pwf,
2288                             void *user), void *user);
2289
2290 To iterate over the cells in a piecewise quasipolynomial reduction,
2291 use either of the following two functions
2292
2293         int isl_pw_qpolynomial_fold_foreach_piece(
2294                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2295                 int (*fn)(__isl_take isl_set *set,
2296                           __isl_take isl_qpolynomial_fold *fold,
2297                           void *user), void *user);
2298         int isl_pw_qpolynomial_fold_foreach_lifted_piece(
2299                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2300                 int (*fn)(__isl_take isl_set *set,
2301                           __isl_take isl_qpolynomial_fold *fold,
2302                           void *user), void *user);
2303
2304 See L<Inspecting (Piecewise) Quasipolynomials> for an explanation
2305 of the difference between these two functions.
2306
2307 To iterate over all quasipolynomials in a reduction, use
2308
2309         int isl_qpolynomial_fold_foreach_qpolynomial(
2310                 __isl_keep isl_qpolynomial_fold *fold,
2311                 int (*fn)(__isl_take isl_qpolynomial *qp,
2312                           void *user), void *user);
2313
2314 =head3 Operations on Piecewise Quasipolynomial Reductions
2315
2316         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
2317                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2318                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2319
2320         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
2321                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2322                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2323
2324         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
2325                 __isl_take isl_union_pw_qpolynomial_fold *upwf1,
2326                 __isl_take isl_union_pw_qpolynomial_fold *upwf2);
2327
2328         __isl_give isl_qpolynomial *isl_pw_qpolynomial_fold_eval(
2329                 __isl_take isl_pw_qpolynomial_fold *pwf,
2330                 __isl_take isl_point *pnt);
2331
2332         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_fold_eval(
2333                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2334                 __isl_take isl_point *pnt);
2335
2336         __isl_give isl_union_set *isl_union_pw_qpolynomial_fold_domain(
2337                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2338         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_intersect_domain(
2339                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2340                 __isl_take isl_union_set *uset);
2341
2342         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_coalesce(
2343                 __isl_take isl_pw_qpolynomial_fold *pwf);
2344
2345         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_coalesce(
2346                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2347
2348         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_gist(
2349                 __isl_take isl_pw_qpolynomial_fold *pwf,
2350                 __isl_take isl_set *context);
2351
2352         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_gist(
2353                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2354                 __isl_take isl_union_set *context);
2355
2356 The gist operation applies the gist operation to each of
2357 the cells in the domain of the input piecewise quasipolynomial reduction.
2358 In future, the operation will also exploit the context
2359 to simplify the quasipolynomial reductions associated to each cell.
2360
2361         __isl_give isl_pw_qpolynomial_fold *
2362         isl_set_apply_pw_qpolynomial_fold(
2363                 __isl_take isl_set *set,
2364                 __isl_take isl_pw_qpolynomial_fold *pwf,
2365                 int *tight);
2366         __isl_give isl_pw_qpolynomial_fold *
2367         isl_map_apply_pw_qpolynomial_fold(
2368                 __isl_take isl_map *map,
2369                 __isl_take isl_pw_qpolynomial_fold *pwf,
2370                 int *tight);
2371         __isl_give isl_union_pw_qpolynomial_fold *
2372         isl_union_set_apply_union_pw_qpolynomial_fold(
2373                 __isl_take isl_union_set *uset,
2374                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2375                 int *tight);
2376         __isl_give isl_union_pw_qpolynomial_fold *
2377         isl_union_map_apply_union_pw_qpolynomial_fold(
2378                 __isl_take isl_union_map *umap,
2379                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2380                 int *tight);
2381
2382 The functions taking a map
2383 compose the given map with the given piecewise quasipolynomial reduction.
2384 That is, compute a bound (of the same type as C<pwf> or C<upwf> itself)
2385 over all elements in the intersection of the range of the map
2386 and the domain of the piecewise quasipolynomial reduction
2387 as a function of an element in the domain of the map.
2388 The functions taking a set compute a bound over all elements in the
2389 intersection of the set and the domain of the
2390 piecewise quasipolynomial reduction.
2391
2392 =head2 Dependence Analysis
2393
2394 C<isl> contains specialized functionality for performing
2395 array dataflow analysis.  That is, given a I<sink> access relation
2396 and a collection of possible I<source> access relations,
2397 C<isl> can compute relations that describe
2398 for each iteration of the sink access, which iteration
2399 of which of the source access relations was the last
2400 to access the same data element before the given iteration
2401 of the sink access.
2402 To compute standard flow dependences, the sink should be
2403 a read, while the sources should be writes.
2404 If any of the source accesses are marked as being I<may>
2405 accesses, then there will be a dependence to the last
2406 I<must> access B<and> to any I<may> access that follows
2407 this last I<must> access.
2408 In particular, if I<all> sources are I<may> accesses,
2409 then memory based dependence analysis is performed.
2410 If, on the other hand, all sources are I<must> accesses,
2411 then value based dependence analysis is performed.
2412
2413         #include <isl/flow.h>
2414
2415         typedef int (*isl_access_level_before)(void *first, void *second);
2416
2417         __isl_give isl_access_info *isl_access_info_alloc(
2418                 __isl_take isl_map *sink,
2419                 void *sink_user, isl_access_level_before fn,
2420                 int max_source);
2421         __isl_give isl_access_info *isl_access_info_add_source(
2422                 __isl_take isl_access_info *acc,
2423                 __isl_take isl_map *source, int must,
2424                 void *source_user);
2425         void isl_access_info_free(__isl_take isl_access_info *acc);
2426
2427         __isl_give isl_flow *isl_access_info_compute_flow(
2428                 __isl_take isl_access_info *acc);
2429
2430         int isl_flow_foreach(__isl_keep isl_flow *deps,
2431                 int (*fn)(__isl_take isl_map *dep, int must,
2432                           void *dep_user, void *user),
2433                 void *user);
2434         __isl_give isl_map *isl_flow_get_no_source(
2435                 __isl_keep isl_flow *deps, int must);
2436         void isl_flow_free(__isl_take isl_flow *deps);
2437
2438 The function C<isl_access_info_compute_flow> performs the actual
2439 dependence analysis.  The other functions are used to construct
2440 the input for this function or to read off the output.
2441
2442 The input is collected in an C<isl_access_info>, which can
2443 be created through a call to C<isl_access_info_alloc>.
2444 The arguments to this functions are the sink access relation
2445 C<sink>, a token C<sink_user> used to identify the sink
2446 access to the user, a callback function for specifying the
2447 relative order of source and sink accesses, and the number
2448 of source access relations that will be added.
2449 The callback function has type C<int (*)(void *first, void *second)>.
2450 The function is called with two user supplied tokens identifying
2451 either a source or the sink and it should return the shared nesting
2452 level and the relative order of the two accesses.
2453 In particular, let I<n> be the number of loops shared by
2454 the two accesses.  If C<first> precedes C<second> textually,
2455 then the function should return I<2 * n + 1>; otherwise,
2456 it should return I<2 * n>.
2457 The sources can be added to the C<isl_access_info> by performing
2458 (at most) C<max_source> calls to C<isl_access_info_add_source>.
2459 C<must> indicates whether the source is a I<must> access
2460 or a I<may> access.  Note that a multi-valued access relation
2461 should only be marked I<must> if every iteration in the domain
2462 of the relation accesses I<all> elements in its image.
2463 The C<source_user> token is again used to identify
2464 the source access.  The range of the source access relation
2465 C<source> should have the same dimension as the range
2466 of the sink access relation.
2467 The C<isl_access_info_free> function should usually not be
2468 called explicitly, because it is called implicitly by
2469 C<isl_access_info_compute_flow>.
2470
2471 The result of the dependence analysis is collected in an
2472 C<isl_flow>.  There may be elements of
2473 the sink access for which no preceding source access could be
2474 found or for which all preceding sources are I<may> accesses.
2475 The relations containing these elements can be obtained through
2476 calls to C<isl_flow_get_no_source>, the first with C<must> set
2477 and the second with C<must> unset.
2478 In the case of standard flow dependence analysis,
2479 with the sink a read and the sources I<must> writes,
2480 the first relation corresponds to the reads from uninitialized
2481 array elements and the second relation is empty.
2482 The actual flow dependences can be extracted using
2483 C<isl_flow_foreach>.  This function will call the user-specified
2484 callback function C<fn> for each B<non-empty> dependence between
2485 a source and the sink.  The callback function is called
2486 with four arguments, the actual flow dependence relation
2487 mapping source iterations to sink iterations, a boolean that
2488 indicates whether it is a I<must> or I<may> dependence, a token
2489 identifying the source and an additional C<void *> with value
2490 equal to the third argument of the C<isl_flow_foreach> call.
2491 A dependence is marked I<must> if it originates from a I<must>
2492 source and if it is not followed by any I<may> sources.
2493
2494 After finishing with an C<isl_flow>, the user should call
2495 C<isl_flow_free> to free all associated memory.
2496
2497 A higher-level interface to dependence analysis is provided
2498 by the following function.
2499
2500         #include <isl/flow.h>
2501
2502         int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
2503                 __isl_take isl_union_map *must_source,
2504                 __isl_take isl_union_map *may_source,
2505                 __isl_take isl_union_map *schedule,
2506                 __isl_give isl_union_map **must_dep,
2507                 __isl_give isl_union_map **may_dep,
2508                 __isl_give isl_union_map **must_no_source,
2509                 __isl_give isl_union_map **may_no_source);
2510
2511 The arrays are identified by the tuple names of the ranges
2512 of the accesses.  The iteration domains by the tuple names
2513 of the domains of the accesses and of the schedule.
2514 The relative order of the iteration domains is given by the
2515 schedule.  The relations returned through C<must_no_source>
2516 and C<may_no_source> are subsets of C<sink>.
2517 Any of C<must_dep>, C<may_dep>, C<must_no_source>
2518 or C<may_no_source> may be C<NULL>, but a C<NULL> value for
2519 any of the other arguments is treated as an error.
2520
2521 =head2 Parametric Vertex Enumeration
2522
2523 The parametric vertex enumeration described in this section
2524 is mainly intended to be used internally and by the C<barvinok>
2525 library.
2526
2527         #include <isl/vertices.h>
2528         __isl_give isl_vertices *isl_basic_set_compute_vertices(
2529                 __isl_keep isl_basic_set *bset);
2530
2531 The function C<isl_basic_set_compute_vertices> performs the
2532 actual computation of the parametric vertices and the chamber
2533 decomposition and store the result in an C<isl_vertices> object.
2534 This information can be queried by either iterating over all
2535 the vertices or iterating over all the chambers or cells
2536 and then iterating over all vertices that are active on the chamber.
2537
2538         int isl_vertices_foreach_vertex(
2539                 __isl_keep isl_vertices *vertices,
2540                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
2541                 void *user);
2542
2543         int isl_vertices_foreach_cell(
2544                 __isl_keep isl_vertices *vertices,
2545                 int (*fn)(__isl_take isl_cell *cell, void *user),
2546                 void *user);
2547         int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
2548                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
2549                 void *user);
2550
2551 Other operations that can be performed on an C<isl_vertices> object are
2552 the following.
2553
2554         isl_ctx *isl_vertices_get_ctx(
2555                 __isl_keep isl_vertices *vertices);
2556         int isl_vertices_get_n_vertices(
2557                 __isl_keep isl_vertices *vertices);
2558         void isl_vertices_free(__isl_take isl_vertices *vertices);
2559
2560 Vertices can be inspected and destroyed using the following functions.
2561
2562         isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
2563         int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
2564         __isl_give isl_basic_set *isl_vertex_get_domain(
2565                 __isl_keep isl_vertex *vertex);
2566         __isl_give isl_basic_set *isl_vertex_get_expr(
2567                 __isl_keep isl_vertex *vertex);
2568         void isl_vertex_free(__isl_take isl_vertex *vertex);
2569
2570 C<isl_vertex_get_expr> returns a singleton parametric set describing
2571 the vertex, while C<isl_vertex_get_domain> returns the activity domain
2572 of the vertex.
2573 Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
2574 B<rational> basic sets, so they should mainly be used for inspection
2575 and should not be mixed with integer sets.
2576
2577 Chambers can be inspected and destroyed using the following functions.
2578
2579         isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
2580         __isl_give isl_basic_set *isl_cell_get_domain(
2581                 __isl_keep isl_cell *cell);
2582         void isl_cell_free(__isl_take isl_cell *cell);
2583
2584 =head1 Applications
2585
2586 Although C<isl> is mainly meant to be used as a library,
2587 it also contains some basic applications that use some
2588 of the functionality of C<isl>.
2589 The input may be specified in either the L<isl format>
2590 or the L<PolyLib format>.
2591
2592 =head2 C<isl_polyhedron_sample>
2593
2594 C<isl_polyhedron_sample> takes a polyhedron as input and prints
2595 an integer element of the polyhedron, if there is any.
2596 The first column in the output is the denominator and is always
2597 equal to 1.  If the polyhedron contains no integer points,
2598 then a vector of length zero is printed.
2599
2600 =head2 C<isl_pip>
2601
2602 C<isl_pip> takes the same input as the C<example> program
2603 from the C<piplib> distribution, i.e., a set of constraints
2604 on the parameters, a line containing only -1 and finally a set
2605 of constraints on a parametric polyhedron.
2606 The coefficients of the parameters appear in the last columns
2607 (but before the final constant column).
2608 The output is the lexicographic minimum of the parametric polyhedron.
2609 As C<isl> currently does not have its own output format, the output
2610 is just a dump of the internal state.
2611
2612 =head2 C<isl_polyhedron_minimize>
2613
2614 C<isl_polyhedron_minimize> computes the minimum of some linear
2615 or affine objective function over the integer points in a polyhedron.
2616 If an affine objective function
2617 is given, then the constant should appear in the last column.
2618
2619 =head2 C<isl_polytope_scan>
2620
2621 Given a polytope, C<isl_polytope_scan> prints
2622 all integer points in the polytope.
2623
2624 =head1 C<isl-polylib>
2625
2626 The C<isl-polylib> library provides the following functions for converting
2627 between C<isl> objects and C<PolyLib> objects.
2628 The library is distributed separately for licensing reasons.
2629
2630         #include <isl_set_polylib.h>
2631         __isl_give isl_basic_set *isl_basic_set_new_from_polylib(
2632                 Polyhedron *P, __isl_take isl_dim *dim);
2633         Polyhedron *isl_basic_set_to_polylib(
2634                 __isl_keep isl_basic_set *bset);
2635         __isl_give isl_set *isl_set_new_from_polylib(Polyhedron *D,
2636                 __isl_take isl_dim *dim);
2637         Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set);
2638
2639         #include <isl_map_polylib.h>
2640         __isl_give isl_basic_map *isl_basic_map_new_from_polylib(
2641                 Polyhedron *P, __isl_take isl_dim *dim);
2642         __isl_give isl_map *isl_map_new_from_polylib(Polyhedron *D,
2643                 __isl_take isl_dim *dim);
2644         Polyhedron *isl_basic_map_to_polylib(
2645                 __isl_keep isl_basic_map *bmap);
2646         Polyhedron *isl_map_to_polylib(__isl_keep isl_map *map);