From f70cfbf0bba620b0e127a6c8c3acd501824f982e Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Fri, 4 Jun 2010 20:20:37 +0200
Subject: [PATCH] add isl_map_is_single_valued

---
 doc/user.pod      |  4 ++++
 include/isl_map.h |  1 +
 isl_map.c         | 26 ++++++++++++++++++++++++++
 isl_test.c        | 17 +++++++++++++++++
 4 files changed, 48 insertions(+)

diff --git a/doc/user.pod b/doc/user.pod
index ebbd94f..8925fc0 100644
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -824,6 +824,10 @@ is already known to be empty.
 	int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
 	int isl_set_fast_is_universe(__isl_keep isl_set *set);
 
+=item * Single-valuedness
+
+	int isl_map_is_single_valued(__isl_keep isl_map *map);
+
 =back
 
 =head3 Binary Properties
diff --git a/include/isl_map.h b/include/isl_map.h
index caa9983..2e0c3db 100644
--- a/include/isl_map.h
+++ b/include/isl_map.h
@@ -354,6 +354,7 @@ int isl_map_is_empty(__isl_keep isl_map *map);
 int isl_map_is_subset(__isl_keep isl_map *map1, __isl_keep isl_map *map2);
 int isl_map_is_strict_subset(__isl_keep isl_map *map1, __isl_keep isl_map *map2);
 int isl_map_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2);
+int isl_map_is_single_valued(__isl_keep isl_map *map);
 
 __isl_give isl_map *isl_map_make_disjoint(__isl_take isl_map *map);
 __isl_give isl_map *isl_basic_map_compute_divs(__isl_take isl_basic_map *bmap);
diff --git a/isl_map.c b/isl_map.c
index d221f21..c4c693a 100644
--- a/isl_map.c
+++ b/isl_map.c
@@ -6709,3 +6709,29 @@ int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
 	first += pos(bset->dim, type) - 1;
 	return isl_basic_set_vars_get_sign(bset, first, n, signs);
 }
+
+/* Check if the given map is single-valued.
+ * We simply compute
+ *
+ *	M \circ M^-1
+ *
+ * and check if the result is a subset of the identity mapping.
+ */
+int isl_map_is_single_valued(__isl_keep isl_map *map)
+{
+	isl_map *test;
+	isl_map *id;
+	int sv;
+
+	test = isl_map_reverse(isl_map_copy(map));
+	test = isl_map_apply_range(test, isl_map_copy(map));
+
+	id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
+
+	sv = isl_map_is_subset(test, id);
+
+	isl_map_free(test);
+	isl_map_free(id);
+
+	return sv;
+}
diff --git a/isl_test.c b/isl_test.c
index 0afdc8f..2ea953a 100644
--- a/isl_test.c
+++ b/isl_test.c
@@ -1259,6 +1259,22 @@ void test_dep(struct isl_ctx *ctx)
 	isl_flow_free(flow);
 }
 
+void test_sv(struct isl_ctx *ctx)
+{
+	const char *str;
+	isl_map *map;
+
+	str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 9 }";
+	map = isl_map_read_from_str(ctx, str, -1);
+	assert(isl_map_is_single_valued(map));
+	isl_map_free(map);
+
+	str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 10 }";
+	map = isl_map_read_from_str(ctx, str, -1);
+	assert(!isl_map_is_single_valued(map));
+	isl_map_free(map);
+}
+
 int main()
 {
 	struct isl_ctx *ctx;
@@ -1267,6 +1283,7 @@ int main()
 	assert(srcdir);
 
 	ctx = isl_ctx_alloc();
+	test_sv(ctx);
 	test_dep(ctx);
 	test_read(ctx);
 	test_construction(ctx);
-- 
2.7.4