-- 
cgit v1.2.3

From 0e17d3cc8b89fc9fae4f358bb6a8cedaeaff6f0b Mon Sep 17 00:00:00 2001
From: vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb>
Date: Thu, 14 Feb 2019 14:32:14 +0000
Subject: Fix of duplicated vertices in list. Modify dimension computation.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/simplex_tree_insert_duplicated_vertices_fix_vincent@4107 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: e6ac9ee4c9d34e59c07d9f5b16b13b5151608009
---
 src/Simplex_tree/include/gudhi/Simplex_tree.h    | 36 +++++++++-----
 src/Simplex_tree/test/simplex_tree_unit_test.cpp | 63 ++++++++++++++++++++++--
 2 files changed, 85 insertions(+), 14 deletions(-)

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 4b18651c..6bb42037 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -787,19 +787,22 @@ class Simplex_tree {
  private:
   /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted
   template<class ForwardVertexRange = std::initializer_list<Vertex_handle>>
-  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex, Filtration_value filt = 0) {
+  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex,
+                                                                     Filtration_value filt = 0) {
     auto first = std::begin(Nsimplex);
     auto last = std::end(Nsimplex);
     if (first == last)
       return { null_simplex(), true }; // FIXME: false would make more sense to me.
     GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order");
-    // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
-    dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(first, last)) - 1);
-    return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt);
+    return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt, 0);
   }
   // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
   template<class ForwardVertexIterator>
-  std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib, ForwardVertexIterator first, ForwardVertexIterator last, Filtration_value filt) {
+  std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
+                                                                         ForwardVertexIterator first,
+                                                                         ForwardVertexIterator last,
+                                                                         Filtration_value filt,
+                                                                         int dimension) {
     // An alternative strategy would be:
     // - try to find the complete simplex, if found (and low filtration) exit
     // - insert all the vertices at once in sib
@@ -811,19 +814,30 @@ class Simplex_tree {
     bool one_is_new = insertion_result.second;
     if (!one_is_new) {
       if (filtration(simplex_one) > filt) {
-	assign_filtration(simplex_one, filt);
+        assign_filtration(simplex_one, filt);
       } else {
-	// FIXME: this interface makes no sense, and it doesn't seem to be tested.
-	insertion_result.first = null_simplex();
+        // FIXME: this interface makes no sense, and it doesn't seem to be tested.
+        insertion_result.first = null_simplex();
       }
     }
-    if (++first == last) return insertion_result;
+    // Next iteration to avoid consecutive equal values
+    while ((vertex_one == *first) && (first < last)) {
+      ++first;
+    }
+    // End of insertion
+    if (first == last) {
+      dimension_ = (std::max)(dimension_, dimension);
+      return insertion_result;
+    }
     if (!has_children(simplex_one))
       // TODO: have special code here, we know we are building the whole subtree from scratch.
       simplex_one->second.assign_children(new Siblings(sib, vertex_one));
-    auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt);
+    ++dimension;
+    auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt, dimension);
     // No need to continue if the full simplex was already there with a low enough filtration value.
-    if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt);
+    if (res.first != null_simplex()) {
+      rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt, dimension);
+    }
     return res;
   }
 
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index b27bbce8..f2a5d54d 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -2,10 +2,11 @@
 #include <fstream>
 #include <string>
 #include <algorithm>
-#include <utility> // std::pair, std::make_pair
-#include <cmath> // float comparison
+#include <utility>  // std::pair, std::make_pair
+#include <cmath>  // float comparison
 #include <limits>
-#include <functional> // greater
+#include <functional>  // greater
+#include <tuple>  // std::tie
 
 #define BOOST_TEST_DYN_LINK
 #define BOOST_TEST_MODULE "simplex_tree"
@@ -921,3 +922,59 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_va
 
   BOOST_CHECK(st1 == st2);
 }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested_variants) {
+  std::cout << "********************************************************************" << std::endl;
+  std::cout << "TEST INSERT DUPLICATED VERTICES" << std::endl;
+  typeST st;
+
+  typename typeST::Simplex_handle sh;
+  bool success = false;
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({1});
+  BOOST_CHECK(success);
+  BOOST_CHECK(sh != st.null_simplex());
+  std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+  BOOST_CHECK(st.dimension(sh) == 0);
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 2});
+  BOOST_CHECK(success);
+  BOOST_CHECK(sh != st.null_simplex());
+  std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+  BOOST_CHECK(st.dimension(sh) == 0);
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({3, 3, 3});
+  BOOST_CHECK(success);
+  BOOST_CHECK(sh != st.null_simplex());
+  std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+  BOOST_CHECK(st.dimension(sh) == 0);
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({4, 4, 4, 4});
+  BOOST_CHECK(success);
+  BOOST_CHECK(sh != st.null_simplex());
+  std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+  BOOST_CHECK(st.dimension(sh) == 0);
+
+  std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+            << " - num_simplices = " << st.num_simplices() << std::endl;
+  BOOST_CHECK(st.dimension() == 0);
+  BOOST_CHECK(st.num_simplices() == st.num_vertices());
+
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 1, 1, 2});
+  BOOST_CHECK(success);
+  BOOST_CHECK(sh != st.null_simplex());
+  std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+  BOOST_CHECK(st.dimension(sh) == 1);
+
+  std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+            << " - num_simplices = " << st.num_simplices() << std::endl;
+  BOOST_CHECK(st.dimension() == 1);
+  BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1);
+
+  // Already inserted
+  std::tie(sh, success) = st.insert_simplex_and_subfaces({1, 2, 2, 1});
+  BOOST_CHECK(!success);
+  BOOST_CHECK(sh == st.null_simplex());
+
+  std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+            << " - num_simplices = " << st.num_simplices() << std::endl;
+  BOOST_CHECK(st.dimension() == 1);
+  BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1);
+
+}
-- 
cgit v1.2.3


From e6676dce1b5faa2c61707968e1e0588e5c47edbf Mon Sep 17 00:00:00 2001
From: ROUVREAU Vincent <vincent.rouvreau@inria.fr>
Date: Thu, 27 Jun 2019 17:47:58 +0200
Subject: code review: test if first!=last before dereferencing first

---
 src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 80d8dfb9..519703e6 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -821,7 +821,7 @@ class Simplex_tree {
       }
     }
     // Next iteration to avoid consecutive equal values
-    while ((vertex_one == *first) && (first < last)) {
+    while ((first < last) && (vertex_one == *first)) {
       ++first;
     }
     // End of insertion
-- 
cgit v1.2.3


From 6aee9ea232820f3fefd3cfd8d194834c4ed9fd22 Mon Sep 17 00:00:00 2001
From: ROUVREAU Vincent <vincent.rouvreau@inria.fr>
Date: Thu, 27 Jun 2019 18:45:50 +0200
Subject: Code review : call std::unique right after std::sort. Repetition has
 been removed

---
 src/Simplex_tree/include/gudhi/Simplex_tree.h | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 519703e6..9d6e50c6 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -775,27 +775,18 @@ class Simplex_tree {
     std::vector<Vertex_handle> copy;
     copy.clear();
     copy.insert(copy.end(), first, last);
-    std::sort(std::begin(copy), std::end(copy));
+    std::sort(copy.begin(), copy.end());
+    auto last_unique = std::unique(copy.begin(), copy.end());
+    copy.erase(last_unique, copy.end());
     GUDHI_CHECK_code(
       for (Vertex_handle v : copy)
         GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
     )
 
-    return insert_simplex_and_subfaces_sorted(copy, filtration);
+    return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration, 0);
   }
 
  private:
-  /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted
-  template<class ForwardVertexRange = std::initializer_list<Vertex_handle>>
-  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex,
-                                                                     Filtration_value filt = 0) {
-    auto first = std::begin(Nsimplex);
-    auto last = std::end(Nsimplex);
-    if (first == last)
-      return { null_simplex(), true }; // FIXME: false would make more sense to me.
-    GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order");
-    return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt, 0);
-  }
   // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
   template<class ForwardVertexIterator>
   std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
-- 
cgit v1.2.3


From 4b5f5c47e681a92f85d390cc5763f39a033ba354 Mon Sep 17 00:00:00 2001
From: ROUVREAU Vincent <vincent.rouvreau@inria.fr>
Date: Fri, 28 Jun 2019 16:11:49 +0200
Subject: We can now roll back rec_insert_simplex_and_subfaces_sorted and
 dimension computation

---
 src/Simplex_tree/include/gudhi/Simplex_tree.h | 28 +++++++++------------------
 1 file changed, 9 insertions(+), 19 deletions(-)

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 9d6e50c6..f1697955 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -782,18 +782,19 @@ class Simplex_tree {
       for (Vertex_handle v : copy)
         GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
     )
+    // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
+    dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
 
-    return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration, 0);
+    return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
   }
 
  private:
   // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
   template<class ForwardVertexIterator>
   std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
-                                                                         ForwardVertexIterator first,
-                                                                         ForwardVertexIterator last,
-                                                                         Filtration_value filt,
-                                                                         int dimension) {
+  	                                                                     ForwardVertexIterator first,
+  	                                                                     ForwardVertexIterator last,
+  	                                                                     Filtration_value filt) {
     // An alternative strategy would be:
     // - try to find the complete simplex, if found (and low filtration) exit
     // - insert all the vertices at once in sib
@@ -811,24 +812,13 @@ class Simplex_tree {
         insertion_result.first = null_simplex();
       }
     }
-    // Next iteration to avoid consecutive equal values
-    while ((first < last) && (vertex_one == *first)) {
-      ++first;
-    }
-    // End of insertion
-    if (first == last) {
-      dimension_ = (std::max)(dimension_, dimension);
-      return insertion_result;
-    }
+    if (++first == last) return insertion_result;
     if (!has_children(simplex_one))
       // TODO: have special code here, we know we are building the whole subtree from scratch.
       simplex_one->second.assign_children(new Siblings(sib, vertex_one));
-    ++dimension;
-    auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt, dimension);
+    auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt);
     // No need to continue if the full simplex was already there with a low enough filtration value.
-    if (res.first != null_simplex()) {
-      rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt, dimension);
-    }
+    if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt);
     return res;
   }
 
-- 
cgit v1.2.3


From 642c4d7dcfca0d28bfed72448bc03502228af6da Mon Sep 17 00:00:00 2001
From: ROUVREAU Vincent <vincent.rouvreau@inria.fr>
Date: Fri, 28 Jun 2019 17:12:26 +0200
Subject: Code review: Keep the comment that returning true is strange

---
 src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index f1697955..f7bb720c 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -765,7 +765,7 @@ class Simplex_tree {
     auto last = std::end(Nsimplex);
 
     if (first == last)
-      return { null_simplex(), true };  // ----->>
+      return { null_simplex(), true }; // FIXME: false would make more sense to me.
 
     // Copy before sorting
     // Thread local is not available on XCode version < V.8 - It will slow down computation
-- 
cgit v1.2.3