isl_tab: drop isl_ctx argument where not absolutely required

isl_mat: keep track of isl_ctx

isl_basic_set_sample: don't project out lineality space up front

For the pip based sampler, projecting out the lineality space
is part of isl_basic_set_skew_to_positive_orthant, so there is
no need for a separate projection step before the skewing.

For the gbr based sampler, there is no need to project out the lineality
space.  The lineality space will simply be part of the recession cone,
which is handled more efficiently than the projection.
In particular, for systems with many variables, the unimodular transformation
used in the projection may have very large coefficients, which in turn
leads to constraints with large coefficients.  Since there is no need
to do this projection, it is best to avoid it.

isl_basic_map_fix_pos: micro-optimization

move isl_basic_set_skew_to_positive_orthant to isl_sample.c

Also, replace independent_bounds in isl_sample.c by that
of isl_sample_piplib.c
The difference is that the latter returns affine bounds
rather than linear bounds and that it return the actual
bounds from the set rather than some linear combinations
of bounds.

It is usually better to use the original bounds as
the linearly transformed bounds may have bigger coefficients
and may therefore be more difficult to process.

isl_tab.c: fix typo in comment

isl_basic_set_sample: break early if sample found in basic_set_range

export isl_tab_sample_is_integer

isl_basic_set_sample: check sample stored by isl_basic_map_is_empty first

isl_basic_map_is_empty: remove stale sample

add isl_polyhedron_sample application

introduce generalized basis reduction based sampling

Also make gbr the default for computing sample integer points.
It may be a bit slower than pip on easy problems, but pip can
sometimes get into serious problems, especially in cases where
the given set does not contain any integer points.  The gbr
method performs much better in these cases.

add isl_seq_cdiv_q

isl_sample.c: interval_sample: drop redundant argument

isl_sample.c: clean up handling of lineality space

isl_sample.c: extract out sample_eq

isl_sample.c: interval_sample: handle equalities directly

isl_sample.c: extract out empty_sample

isl_sample.c: generalize point_sample to zero_sample

isl_tab: don't create new undo records during rollback

isl_tab_min: use general rollback mechanism

isl_tab: optionally save dual solution

isl_tab: add isl_tab_add_valid_eq

export isl_tab_alloc

add isl_int_le

privately export isl_basic_set_recession_cone

isl_convex_hull.c: add missing assignment

privately export isl_basic_set_lineality_space

isl_vec: keep track of isl_ctx

isl_coalesce.c: fix typo

update piplib for change in configure arguments

isl_basic_map_drop_redundant_divs: coalesce divs if possible

isl_basic_map_drop_redundant_divs: set div expression if obvious from constraints

isl_basic_map_drop_redundant_divs: drop more kinds of redundant divs

isl_map_compute_divs: drop obviously redundant divs first

isl_map_piplib.c: extremum_on: detect equalities first

In a map with several divs, there may be some that are
actually equal to each other (up to a constant).  Any
div present in the map will make the search for the
lexicographic maximum or minimum more difficult, so
we want to remove such duplicate divs before embarking
on the search.

This situation occurs especially during dependence
analysis (in an outside user of isl).  Perhaps it
would be best if the outside user would attempt
to remove duplicate divs instead of doing it
indiscriminately inside the library, but for now
it is easiest to just put it here.

isl_pip_basic_map_compute_divs: remove some equalities first

isl_pip_basic_map_compute_divs: separate out dimension games

We want to do some additional transformations on the input
set and it is easier to perform these transformations
with the existential variables considered as output variables.

isl_basic_set_preimage: handle divs in input

isl_input_omega.c: make variable_{free,new} static

isl_map.c: make add_divs static

isl_basic_map_simplify: detect div constraints while looking for duplicates

During the detection of duplicate constraints we also look for pairs
of opposite constraints and these can potentially be used to define
a div.

isl_basic_map_drop: properly handle dimensions of type isl_dim_div

add isl_int_mul_ui

add isl_seq_fdiv_q

add isl_seq_fdiv_r

isl_basic_map_detect_equalities: properly handle empty basic sets

If we find out during the computation of the equalities in
the basic map that it was empty, then there is no point in
trying to add any equalities we may have found.

isl_basic_map_is_empty: explicitly mark basic sets determined to be empty

isl_map.c: order_divs: swap with correct div

The bug in the original code could result in a div being swapped
with itself, in turn resulting in an infinite loop.

isl_map_coalesce: remove extra divs introduced by isl_map_align_divs

add isl_map_coalesce

add isl_set_product

export isl_map_dim

isl_map_convex_hull: handle unbounded, but pointed, case using wrapping

The case where the convex hull may be unbounded (but still pointed)
cannot be handled directly using wrapping.  However, by changing
the homogeneous direction, we can in such cases always transform
the input polyhedra to polytopes, compute the hull and then transform back.

Since we already handle the case where the convex hull may not be
pointed, we can now handle all cases using wrapping.
The convex_hull_pair_elim function is therefore no longer used.
We leave it in, because we may want to allow the user to choose
in future which convex hull algorithm to use.

privately export isl_mat_unimodular_complete

isl_tab.c: add isl_tab_get_sample_value

isl_map_convex_hull: avoid introducing lineality spaces in convex hull of pairs

add two more convex hull test cases

isl_map_convex_hull: remove lineality space if any before computing convex hull

add isl_basic_set_is_universe

add isl_set_get_dim

isl_convex_hull.c: update wrap_facet to the fact we only apply it on polytopes

isl_convex_hull.c: fix typo in comment

isl_coalesce.c: fix typo in comment

isl_tab.c: fix typo in comment

configure.in: set AC_CONFIG_MACRO_DIR

add isl_basic_set_get_dim

isl_basic_map_gist: normalize divs (if any) in context

isl_basic_map_simplify: remove duplicate divs before dropping divs

The equalities on the duplicate but separate divs may
entail additional equalities among the variables that we do
not want to ignore.

add isl_basic_set_div

change calling convention of isl_basic_map_div

isl_map_simplify.c: uset_gist: break early if there are no inequalities

isl_map_simplify.c: uset_gist: break early if intersection is empty

add isl_basic_set_fast_is_empty

update piplib to 1.4.0

isl_tab.c: store number of equalities among the constraints in tableau

Before, we would check the bmap to figure out how many equalities we
had added, but there was at least one instance where we didn't actually
store the equalities in the tableau, leading to problems if any additional
equalities would be found in the tableau.

isl_mat_extend: properly extend matrices with reordered rows

isl_map_gist: handle some special cases

add isl_map_universe

add isl_basic_map_fast_is_empty

isl_basic_map_gist: replace by new version based on tableaus

The new version should be a little bit more efficient because
it only constructs a single tableau.

More importantly, the new version keeps better track of the original
constraints and never introduces an inequality constraint in the result
that did not appear in the input.
This is especially important in the presence of divs.
Throught variable compression, the original version would sometimes
translate constraints that did not involve any divs into constraints
that did involve divs.

isl_map_simplify.c: compute_elimination_index: don't assume equalities are in order

add isl_map_implicit_equalities

add isl_basic_set_free_equality

isl_map_convex_hull: mark result as not having any implicit equalities

convex_hull: coalesce set first

add isl_set_coalesce

isl_input_omega.c: basic_map_read: accept "+" in constraints

add isl_basic_set_alloc_div

add isl_set_align_divs

uset_affine_hull: ignore directions in affine hull of recession cone

isl_basic_map_implicit_equalities: perform Gaussian elimination on result

isl_affine_hull.c: outside_point: check for obvious candidate first

privately export isl_basic_set_contains

isl_ctx: add negone

isl_vec_dump: handle NULL vec

isl_affine_hull.c: extract uset_affine_hull

isl_mat_transpose: handle non-rectangular matrices

isl_map_simple_hull: compute affine hull before aligning divs

Computing the affine hull may change the internal representation.
In particular, it may simplify div constraints that are added
during the alignment to constraints that did not appear in the
original set and we do not want to introduce such constraints
in the simple hull.

isl_map_simple_hull: mark result as not having any implicit equalities