isl_map_is_subset: break off as soon as difference is known to be non-empty

compute set difference using a backtracking algorithm

In particular, treat all basic maps in the minuend separately
and only subtract parts of the subtrahend that actually overlap
with the minuend.  Moreover, only use non-redundant constraints
when performing this subtraction.

Using only non-redundant constraints in overlapping parts
avoids the minuend being split in several parts unnecessarily.
Treating each basic map separately should help speed up
isl_map_is_subset in a subsequent commit.

isl_map_subtract.c: extract from isl_map.c

isl_tab: keep track of isl_basic_map instead of isl_basic_set

privately export isl_basic_map_contains

add isl_basic_map_add_ineq and isl_basic_map_add_eq

isl_tab_detect_redundant: return status instead of isl_tab *

isl_tab: add isl_tab_freeze_constraint

isl_tab_add_ineq and isl_tab_mark_empty: return status instead of isl_tab *

isl_tabs are not reference counted, so it's easier to deal with a status
than to have to keep track of whether the isl_tab may have been destroyed.

add missing AUTHORS file

isl_basic_set_swap_vars: re-gauss resulting bset

Many functions assume that their inputs have been gaussed.

add isl_basic_map_first_constraint

export isl_basic_map_lexmax

add isl_basic_set_lexmax

isl_map_drop_basic_map: consistently keep basic map argument

isl_tab: row is only (obviously) redundant if it does not depend on variables

Variables are not assumed to be nonnegative, but are only marked as being
nonnegative based on the constraints.  This nonnegativity can therefore
not be used to mark rows as being redundant as that could lead to
circular reasoning.

isl_basic_map_simplify: make sure to rerun Gauss when equality has been added

remove_duplicate_constraints failed to set the progress flag when
it replaces a pair of inequalities by an equality, resulting in
the result of isl_basic_map_simplify possibly not having the equalities
in the expected form.

isl_tab_basic_map_partial_lexopt: use context constraints when detecting equalities

The constraints of the context of the actual map may conspire to form
equalities and we generally want to detect as many equalities as possible.
Therefore, detect equalities in the intersection of the two
and add these equalities to the map.
Note that the equalities are now no longer detected in the map
itself, so we may have to detect equalities again later if
we are ever interested in the equalities of the map itself.

isl_tab_pip.c: ignore dead columns when checking integrality

The dead columns are zero, which means that it does not matter
that they may have a fractional coefficient.
Moreover, dead columns can't be used to pivot, so it is actually
wrong to take them into account.

isl_pip: optionally perform some check on the results

put options in a separate isl_options structure

add rudimentary argument parsing facility

isl_tab_compute_reduced_basis: handle empty tables

isl_basic_set_solve_ilp: handle obviously empty sets

isl_basic_set_solve_ilp: fix handling of sets with equalities

First, the input set should be protected from being modified,
and second, the test for whether a solution is requested was wrong.

add isl_set_remove

add isl_set_fix

add isl_basic_set_fix

extract isl_basic_set_scan from polytope_scan.c

isl_basic_map_simplify: avoid removal of div definitions in eliminate_divs_eq

isl_map.c: declare variable at start of code block

isl_basic_set_project_out: handle rational sets

For rational sets, projection boils down to (Fourier-Motzkin)
elimination, so just call isl_basic_set_remove.

add isl_basic_set_remove

isl_tab_pip: keep cache of partial solutions

This cache allows us to combine two partial solutions into a single
partial solution if they have the same mapping.  The domain of the
single partial solution is that before it was split to arrive at
the two domains of the two partial solutions.
In particular, this happens if it turns out there is no solution
in either part of the context.
It also happens when the initial set has existentially quantified
variables.  In this case, we only insist that these variables
have an integer value, but we don't care about the actual value.
The solutions in the two parts of the context may therefore still
agree on the remaining variables.

isl_tab_pip: don't free isl_sol on error condition

Instead, set a flag.  isl_sol is not reference counted, so it's better
not to destroy it along the way.

isl_tab: support generic undo records

add isl_mat_is_equal

isl_tab_pip.c: remove some code duplication between isl_map_add and isl_for_add

isl_map_is_subset: add special case for singleton maps

isl_map_compute_divs: skip computation if divs are known already

isl_map_is_subset: exploit another easy special case

add isl_map_fast_is_universe

add isl_set_size

mark some functions as requiring use of return value

isl_tab: improved error handling

isl_tab_pip.c: incrementally build recession cone of gbr context

When checking the feasibility of a constraint in the gbr context,
we compute a sample.  The first step of this computation builds
a recession cone since we need to know which directions are unbounded.
By incrementally building up the recession cone, we can avoid
the complete recomputation.  This is especially useful when
the context is/becomes bounded, since we can then avoid the
recession cone computation altogether.

isl_tab_pip.c: propagate some equalities from gbr context to main tableau

If a new equality in the context can be used to eliminate
a parameter in the main tableau, we perform the elimination
as this allows us to more easily determine the signs of rows
and it may avoid the introduction of some redundant integer
divisions.

isl_tab_pip.c: detect equalities in gbr context on each parametric cut

A new div that was introduced to express a parametric cut may,
within the current context, be an affine combination of other divs.
If so, we want to find these equalities as soon as possible
as this may allow us to more easily determine feasibility of
a constraint.

add isl_tab_detect_equalities

add isl_tab_set_initial_basis_with_cone

isl_tab_pip: use generalized basis reduction based context by default

isl_tab_pip: add generalized basis reduction based context handling

isl_tab_pip.c: extract out context handling

isl_tab_pip.c: add_div: use more reliable way to test whether div is nonneg

Before, we used the fact that if all parameters are non-negative,
then the big parameter is not used.
However, it is perfectly valid to have negative parameters and
still not use any big parameter.

isl_tab_basic_map_partial_lexopt: remove samples that are no longer useful

When we test an inequality in row_sign, it is useful to store any
samples found, so we can use them to speed up the computation
of future row signs.
However, when we return from a branch, then all the samples found
since we entered the branch all satisfy the constraints on that
branch and so they will not satisfy the constraints on any other
branch.  We therefore save the current number of samples when
we enter a branch and then discard all subsequently added samples
when we return from the branch.

isl_tab.c: extract out samples handling from isl_tab_pip.c

isl_affine_hull.c: uset_affine_hull_bounded: use tableaus to perform computation

isl_basic_map_detect_equalities: keep track of sample

isl_basic_map_detect_equalities: only compute recession cone once

Before, the recession cone was computed both during the computation
of the initial sample and then later again to project out this
recession cone.

isl_tab_sample: handle unbounded directions in initial basis

isl_tab_compute_reduced_basis: handle unbounded directions in initial basis

exploit equalities in isl_tab_sample

isl_tab: keep (in)equalities of bset (if any) in sync

isl_tab_sample: be more verbose about unbounded directions

separate out isl_tab_sample from sample_bounded

sample_bounded: reimplement to work directly on a tableau

In other words, adapt the implementation of isl_basic_set_samples
in polytope_scan.c
This avoids the reconstruction of tableaus and allows for a refactoring
that takes a tableau as input.

isl_tab_compute_reduced_basis: work with affine basis instead of linear basis

isl_tab_compute_reduced_basis: allow incremental computation

isl_polytope_scan: use isl_tab_from_basic_set

separate out isl_tab_reduced_basis from isl_basic_set_reduced_basis

This allows us to compute a reduced basis on a set given in tableau form.

basis_reduction_tab.c: use isl_tab_product to construct product tableau

Before, we would manually construct a tableau for the Cartesian
product of a set with itself.  Now, we first create a tableau
for the set and then construct the product tableau.
This should be more efficient and allows us to refactor
the code to pass in a tableau instead of a set.

add isl_tab_product

isl_basic_set_reduced_basis: fix value in directions with only one integer value

If two or more directions have a width that is smaller than one,
i.e., such that the only one integer value can be attained,
then the standard algorithm would still try to order these
directions.  However, if the first directions only admit one
value, then it doesn't matter in which order they are put.
We therefore keep track of such directions explicitly and
also set the value in the tableau to the fixed value, rather
than keeping the rational interval with only one integer value.

isl_basic_set_reduced_basis: fix up documentation

basis_reduction_tab.c: keep track of con_offset instead of n_ineq

This is a minor cosmetic change.

add isl_tab_add_eq

isl_tab_add_valid_eq: add special treatment for manifestly zero rows

isl_tab_extend_cons: check tab argument

rename isl_tab_detect_equalities to isl_tab_detect_implicit_equalities

isl_tab_from_recession_cone: take basic set instead of basic map as argument

isl_ilp.c: separate out solve_ilp_search

isl_sample.c: basic_set_sample: remember boundedness of basic set

add isl_polyhedron_detect_equalities test application

add isl_basic_set_detect_equalities

isl_tab_allocate_con: add extra assertion

isl_sample.c: basic_set_reduced: fix typo preventing use of gbr_only_first

isl_tab_basic_map_partial_lexopt: simplify result

privately export isl_basic_set_add_{in,}eq

privately export isl_basic_set_sample_with_cone

add isl_basic_set_underlying_set

isl_tab.c: close_row: push undo record for setting row to zero

add isl_mat_vec_inverse_product

add isl_mat_concat

add isl_int_divexact_ui

add isl_set_dim_residue_class

fix long standing bug in isl_mat_inverse_product

add isl_basic_map_foreach_lexmin

add isl_set_project_out

add isl_set_detect_equalities

add isl_set_foreach_basic_set