+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first+n-1.
+ */
+static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
+ __isl_take isl_basic_map *bmap, unsigned first, unsigned n)
+{
+ int i;
+
+ if (n == 0)
+ return bmap;
+
+ bmap = isl_basic_map_cow(bmap);
+
+ if (!bmap)
+ return NULL;
+
+ for (i = bmap->n_eq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
+ continue;
+ isl_basic_map_drop_equality(bmap, i);
+ }
+
+ for (i = bmap->n_ineq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
+ continue;
+ isl_basic_map_drop_inequality(bmap, i);
+ }
+
+ return bmap;
+}
+
+/* Drop all constraints in bset that involve any of the dimensions
+ * first to first+n-1.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
+ __isl_take isl_basic_set *bset, unsigned first, unsigned n)
+{
+ return isl_basic_map_drop_constraints_involving(bset, first, n);
+}
+
+/* Drop all constraints in bmap that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ int i;
+ unsigned dim;
+
+ if (n == 0)
+ return isl_basic_map_set_to_empty(bmap);
+ bmap = isl_basic_map_cow(bmap);
+ if (!bmap)
+ return NULL;
+
+ dim = isl_basic_map_dim(bmap, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
+
+ first += isl_basic_map_offset(bmap, type) - 1;
+
+ for (i = bmap->n_eq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
+ continue;
+ isl_basic_map_drop_equality(bmap, i);
+ }
+
+ for (i = bmap->n_ineq - 1; i >= 0; --i) {
+ if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
+ continue;
+ isl_basic_map_drop_inequality(bmap, i);
+ }
+
+ return bmap;
+}
+
+/* Drop all constraints in bset that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_basic_map_drop_constraints_not_involving_dims(bset,
+ type, first, n);
+}
+
+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ unsigned dim;
+
+ if (!bmap)
+ return NULL;
+ if (n == 0)
+ return bmap;
+
+ dim = isl_basic_map_dim(bmap, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
+ "index out of bounds", return isl_basic_map_free(bmap));
+
+ bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
+ first += isl_basic_map_offset(bmap, type) - 1;
+ return isl_basic_map_drop_constraints_involving(bmap, first, n);
+}
+
+/* Drop all constraints in bset that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_basic_map_drop_constraints_involving_dims(bset,
+ type, first, n);
+}
+
+/* Drop all constraints in map that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_map *isl_map_drop_constraints_involving_dims(
+ __isl_take isl_map *map,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ int i;
+ unsigned dim;
+
+ if (!map)
+ return NULL;
+ if (n == 0)
+ return map;
+
+ dim = isl_map_dim(map, type);
+ if (first + n > dim || first + n < first)
+ isl_die(isl_map_get_ctx(map), isl_error_invalid,
+ "index out of bounds", return isl_map_free(map));
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_drop_constraints_involving_dims(
+ map->p[i], type, first, n);
+ if (!map->p[i])
+ return isl_map_free(map);
+ }
+
+ return map;
+}
+
+/* Drop all constraints in set that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_set *isl_set_drop_constraints_involving_dims(
+ __isl_take isl_set *set,
+ enum isl_dim_type type, unsigned first, unsigned n)
+{
+ return isl_map_drop_constraints_involving_dims(set, type, first, n);
+}
+
+/* Construct an initial underapproximatino of the hull of "bset"
+ * from "sample" and any of its adjacent points that also belong to "bset".
+ */
+static __isl_give isl_basic_set *initialize_hull(__isl_keep isl_basic_set *bset,
+ __isl_take isl_vec *sample)
+{
+ isl_basic_set *hull;
+
+ hull = isl_basic_set_from_vec(isl_vec_copy(sample));
+ hull = add_adjacent_points(hull, sample, bset);
+
+ return hull;
+}
+
+/* Look for all equalities satisfied by the integer points in bset,
+ * which is assumed to be bounded.
+ *
+ * The equalities are obtained by successively looking for
+ * a point that is affinely independent of the points found so far.
+ * In particular, for each equality satisfied by the points so far,
+ * we check if there is any point on a hyperplane parallel to the
+ * corresponding hyperplane shifted by at least one (in either direction).
+ */
+static struct isl_basic_set *uset_affine_hull_bounded(struct isl_basic_set *bset)
+{
+ struct isl_vec *sample = NULL;
+ struct isl_basic_set *hull;
+ struct isl_tab *tab = NULL;
+ unsigned dim;
+
+ if (isl_basic_set_plain_is_empty(bset))
+ return bset;
+
+ dim = isl_basic_set_n_dim(bset);
+
+ if (bset->sample && bset->sample->size == 1 + dim) {
+ int contains = isl_basic_set_contains(bset, bset->sample);
+ if (contains < 0)
+ goto error;
+ if (contains) {
+ if (dim == 0)
+ return bset;
+ sample = isl_vec_copy(bset->sample);
+ } else {
+ isl_vec_free(bset->sample);
+ bset->sample = NULL;
+ }
+ }
+
+ tab = isl_tab_from_basic_set(bset, 1);
+ if (!tab)
+ goto error;
+ if (tab->empty) {
+ isl_tab_free(tab);
+ isl_vec_free(sample);
+ return isl_basic_set_set_to_empty(bset);
+ }
+
+ if (!sample) {
+ struct isl_tab_undo *snap;
+ snap = isl_tab_snap(tab);
+ sample = isl_tab_sample(tab);
+ if (isl_tab_rollback(tab, snap) < 0)
+ goto error;
+ isl_vec_free(tab->bmap->sample);
+ tab->bmap->sample = isl_vec_copy(sample);
+ }
+
+ if (!sample)
+ goto error;
+ if (sample->size == 0) {
+ isl_tab_free(tab);
+ isl_vec_free(sample);
+ return isl_basic_set_set_to_empty(bset);
+ }
+
+ hull = initialize_hull(bset, sample);
+
+ hull = extend_affine_hull(tab, hull, bset);
+ isl_basic_set_free(bset);
+ isl_tab_free(tab);
+
+ return hull;
+error:
+ isl_vec_free(sample);
+ isl_tab_free(tab);
+ isl_basic_set_free(bset);
+ return NULL;
+}
+
+/* Given an unbounded tableau and an integer point satisfying the tableau,
+ * construct an initial affine hull containing the recession cone
+ * shifted to the given point.
+ *
+ * The unbounded directions are taken from the last rows of the basis,
+ * which is assumed to have been initialized appropriately.
+ */
+static __isl_give isl_basic_set *initial_hull(struct isl_tab *tab,
+ __isl_take isl_vec *vec)