isl_tab: privately export some functionality

isl_tab: store undo argument in a union for future extensions

add isl_basic_set_sample_bounded

privately export isl_basic_set_order_divs

isl_map_simplify.c: remove_dependent_vars: only remove definitions of divs

Don't remove the dependent divs themselves, because in particular
eliminate_divs_ineq does not expect any other divs to get removed.

isl_basic_map_compute_divs: use isl_basic_set_lexmin and move to isl_map.c

There is no need for the core of isl_basic_map_compute_divs to use any
piplib specific code.  We therefore move the code to isl_map.c so
that it can also be used on top of another PILP solver.

isl_pip_basic_map_compute_divs: don't turn divs into output dimensions

There is no practical reason why we should want to do this transformation
and removing it makes it possible to you use the standard interface
to pip in the next commit.

privately export isl_basic_map_swap_div

isl_{set,map}_add: don't add obviously empty basic sets/maps

combine isl_pip_basic_map_lex{min,max} into isl_pip_basic_map_lexopt

make piplib headers private

isl_mat: keep track of the actual number of columns in a row

We need this number to perform extensions after dropping columns.

isl_tab_pivot: fix typo that prevented normalization of rows

add isl_basic_set_positive_orthant

add isl_basic_set_partial_lex{min,max}

rename isl_basic_map_lex{min,max} to isl_basic_map_partial_lex{min,max}

add isl_basic_set_free_div

isl_set_dim: support isl_dim_all

isl_tab: store index of variable in undo record instead of pointer to variable

The row of variables might get reallocated between pushing the undo
record and performing the undo, invalidating the pointer.

add isl_{set,map}_grow

add isl_map_get_dim

add isl_basic_map_get_dim

add isl_tab_dup

export isl_mat_dup

isl_tab.c: mark_redundant: only mark variable nonneg if they weren't already

More imporantly, don't undo such a mark during rollback.

isl_tab.c: to_row: allow pivoting in arbitrary direction

While undoing the allocation of a row, we may be dealing with
a row that was unbounded in both directions and is now in a column.
To move the column back to a row, we just pivot using any non-zero entry.

isl_tab.c: simplify code by letting mark_empty return tab

add isl_seq_last_non_zero

isl_tab.c: simplify add_eq

isl_tab.c: extract allocate_con

privately export isl_basic_set_set_rational

configure.ac: explicitly set AC_CONFIG_AUX_DIR

Without it, libtool can apparently get confused about which
ltmain.sh to use.

convex_hull: coalesce set during facet computation

isl_map_coalesce: don't drop rational flag from result if set in input

isl_tab_cone_is_bounded: start over after computing sign_of_max

sign_of_max may have made some rows redundant and may therefore
invalidate the iteration over all non-redundant rows.

Problem reported by Uday Kumar <udayreddy@gmail.com>

isl_basic_set_dim_residue_class: only set *modulo to 0 when dimension is fixed

Before, when no residue class could be detected, *modulo was sometimes
set to 0 and sometimes to 1.  Now *modulo is always set to 1 in these
cases, except when the specified dimension has a fixed constant value,
in which case *modulo is set to 0 and *residue to the fixed value.

add isl_basic_set_fast_dim_is_fixed

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