isl_input.c: fix memory deallocation problem on missing operator

add dependence analysis

add isl_map_{partial_,}lexopt

add private isl_{set,map}_make_disjoint

basis_reduction_templ.c: fix typo in comment

isl_tab_pip.c: find_solutions: break when context becomes empty

Normally, find_solutions: always operates on a non-empty context.
However, when we discover a pure-parametric cut in the main
tableau, the result of adding this cut to the context may be
an empty context.  In this case, we need to break out off the
main loop, because most code assumes the context is non-empty.

isl_dim_equal: don't require names of input and output variables to match

isl_dim_map: properly duplicate names

isl_dim_drop: properly adjust length of names array

doc: a bit more on integers

doc: describe input/output formats

doc: fix typo

add isl_cat test application

add omega output

add isl output

isl_test: use isl_set_read_from_str

add isl_set_read_from_str

add isl_map_read_from_str

isl_map_read_from_file: allow unions in isl format input

isl_basic_map_read: read definitions of existential variables

privately export isl_basic_map_add_div_constraints

isl_basic_map_read: read affine constraint as two affine expressions + operator

isl_input.c: optionally read parameters from input

tokenizer: accept "and" keyword

export isl_map_read_from_file

export isl_basic_map_read_from_str

drop redundant input_format argument from reading functions

isl_input.c: merge functions for reading PolyLib and omega-like input

isl_input_omega.c: accept PolyLib input

isl_input_omega.c: prepare for reading parametric unions

isl_input_omega.c: finalize and simplify resulting basic map

isl_input_omega.c: fix check for memory allocation error

isl_stream_next_token: skip comment lines

isl_tab_basic_map_partial_lexopt: properly handle empty input map

In particular, when no empty set is requested (i.e., empty == NULL),
then we shouldn't try to add the context to the empty set.

isl_basic_map_set_to_empty: remove sample (if any)

add isl_set_fast_is_empty

properly remove piplib submodule

309036c (add copyright statements) accidentally removed the piplib submodule.
Removing the piplib submodule was not a bad idea since we don't really need it
anymore, but it should be done properly.

isl_basic_map_update_from_tab: re-gauss resulting bmap

Many functions assume that their inputs have been gaussed.

ax_submodule.m4: don't let --with-module conflict with --with-module-prefix=

add isl_set_follows_at

isl_basic_set_compare_at: compute result in terms of maximal (integral) difference

Computing the maximal instead of the minimal difference will allow
us to reuse much of the code in isl_basic_set_follows_at later.
Since we only need the sign of the optimum, we don't really need
the exact value.

isl_tab_pip.c: add cuts for all non-integer coordinates in lexmin context

The lexmin context applies basically the same algorithm that is
used in the main tableau to the context tableau.
In particular, each cut that is added is immediately used to move
to a lexico-greater point.
It was reported by François Galea, who was working on the implementation
of parametric integer programming in PPL, that first adding cuts
for all non-integer coordinates results in a significant speed
improvement on at least one example.
This patch implements the same idea and results in a similar improvement
on the same example.

isl_basic_map_gist: don't drop equalities from context

The context isn't cowed, so this dropping of equalities would
be visible to the caller.  Instead, drop the equalities after
duplicating the context.

isl_convex_hull.c: initial_facet_constraint: drop all redundant bounds on face

While constructing an initial facet, we may end up with an intermediate
face that makes some of the as yet unconsidered bounds redundant.
Remove all of them, instead of only those that happen to vanish.

isl_convex_hull.c: is_independent_bound: normalize bounds

isl_convex_hull.c: extend: check hull argument

isl_mat_right_inverse: be more verbose on error condition

isl_constraint_dup: make sure line refers to equation in constraint's bmap

add copyright statements

remove functions for converting between isl and PolyLib

These functions could be seen as being derived work from PolyLib
and would therefore infect the whole library with the GPLv2 license.
They will be moved into a separate isl-polylib library.

isl_tab_solve_lp: invert optimal value back when computing maximum

A maximum is computed by computing the minimum of the opposite objective
function.  The maximal value is then the opposite of the computed value.

isl_map_intersect: add special case for adding a single constraint

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.