Merge 3 billions of simplices bug fix into the trunk

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

Former-commit-id: 837260d9c45b827e3bcf5cea6bf8164760e24844

7 files changed, 70 insertions, 11 deletions

diff --git a/src/Persistent_cohomology/example/plain_homology.cpp b/src/Persistent_cohomology/example/plain_homology.cpp
index 2156ffd9..ae82c817 100644
--- a/src/Persistent_cohomology/example/plain_homology.cpp
+++ b/src/Persistent_cohomology/example/plain_homology.cpp
@@ -25,6 +25,7 @@
 
 #include <iostream>
 #include <vector>
+#include <cstdint>  // for std::uint8_t
 
 using namespace Gudhi;
 
@@ -39,6 +40,8 @@ struct MyOptions : Simplex_tree_options_full_featured {
   static const bool store_key = true;
   // I have few vertices
   typedef short Vertex_handle;
+  // Maximum number of simplices to compute persistence is 2^8 - 1 = 255. One is reserved for null_key
+  typedef std::uint8_t Simplex_key;
 };
 typedef Simplex_tree<MyOptions> ST;
 
diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
index a7d1e463..b31df6a4 100644
--- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
+++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
@@ -41,6 +41,7 @@
 #include <tuple>
 #include <algorithm>
 #include <string>
+#include <stdexcept>  // for std::out_of_range
 
 namespace Gudhi {
 
@@ -89,6 +90,7 @@ class Persistent_cohomology {
    *
    * @param[in] cpx Complex for which the persistent homology is computed.
    * cpx is a model of FilteredComplex
+   * @exception std::out_of_range In case the number of simplices is more than Simplex_key type numeric limit.
    */
   explicit Persistent_cohomology(Complex_ds& cpx)
       : cpx_(&cpx),
@@ -106,6 +108,10 @@ class Persistent_cohomology {
         interval_length_policy(&cpx, 0),
         column_pool_(),  // memory pools for the CAM
         cell_pool_() {
+    if (cpx_->num_simplices() > std::numeric_limits<Simplex_key>::max()) {
+      // num_simplices must be strictly lower than the limit, because a value is reserved for null_key.
+      throw std::out_of_range ("The number of simplices is more than Simplex_key type numeric limit.");
+    }
     Simplex_key idx_fil = 0;
     for (auto sh : cpx_->filtration_simplex_range()) {
       cpx_->assign_key(sh, idx_fil);
diff --git a/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp b/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp
index a4e00b45..40221005 100644
--- a/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp
+++ b/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp
@@ -12,7 +12,7 @@
 #include "gudhi/Simplex_tree.h"
 #include "gudhi/Persistent_cohomology.h"
 
-struct MyOptions : Gudhi::Simplex_tree_options_full_featured {
+struct MiniSTOptions : Gudhi::Simplex_tree_options_full_featured {
   // Implicitly use 0 as filtration value for all simplices
   static const bool store_filtration = false;
   // The persistence algorithm needs this
@@ -21,7 +21,7 @@ struct MyOptions : Gudhi::Simplex_tree_options_full_featured {
   typedef short Vertex_handle;
 };
 
-using Mini_simplex_tree = Gudhi::Simplex_tree<MyOptions>;
+using Mini_simplex_tree = Gudhi::Simplex_tree<MiniSTOptions>;
 using Mini_st_persistence =
     Gudhi::persistent_cohomology::Persistent_cohomology<Mini_simplex_tree, Gudhi::persistent_cohomology::Field_Zp>;
 
diff --git a/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp b/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp
index 5c54ed5f..6efd749e 100644
--- a/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp
+++ b/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp
@@ -4,6 +4,7 @@
 #include <utility> // std::pair, std::make_pair
 #include <cmath> // float comparison
 #include <limits>
+#include <cstdint>  // for std::uint8_t
 
 #define BOOST_TEST_DYN_LINK
 #define BOOST_TEST_MODULE "persistent_cohomology"
@@ -172,3 +173,45 @@ BOOST_AUTO_TEST_CASE( rips_persistent_cohomology_single_field_dim_5 )
 // std::string str_rips_persistence = test_rips_persistence(6, 0);
 // TODO(VR): division by zero
 // std::string str_rips_persistence = test_rips_persistence(0, 0);
+
+/** SimplexTree minimal options to test the limits.
+ * 
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint8_t>::max()<\CODE> = 256.*/
+struct MiniSTOptions {
+  typedef linear_indexing_tag Indexing_tag;
+  typedef short Vertex_handle;
+  typedef double Filtration_value;
+  // Maximum number of simplices to compute persistence is 2^8 - 1 = 255. One is reserved for null_key
+  typedef std::uint8_t Simplex_key;
+  static const bool store_key = true;
+  static const bool store_filtration = false;
+  static const bool contiguous_vertices = false;
+};
+
+using Mini_simplex_tree = Gudhi::Simplex_tree<MiniSTOptions>;
+using Mini_st_persistence =
+    Gudhi::persistent_cohomology::Persistent_cohomology<Mini_simplex_tree, Gudhi::persistent_cohomology::Field_Zp>;
+
+BOOST_AUTO_TEST_CASE( persistence_constructor_exception )
+{
+  Mini_simplex_tree st;
+
+  // To make number of simplices = 255
+  const short simplex_0[] = {0, 1, 2, 3, 4, 5, 6, 7};
+  st.insert_simplex_and_subfaces(simplex_0);
+  // FIXME: Remove this line
+  st.set_dimension(8);
+
+  // Sort the simplices in the order of the filtration
+  st.initialize_filtration();
+
+  BOOST_CHECK(st.num_simplices() <= std::numeric_limits<MiniSTOptions::Simplex_key>::max());
+  // Class for homology computation
+  BOOST_CHECK_NO_THROW(Mini_st_persistence pcoh(st));
+
+  st.insert_simplex({8});
+  BOOST_CHECK(st.num_simplices() > std::numeric_limits<MiniSTOptions::Simplex_key>::max());
+  // Class for homology computation
+  BOOST_CHECK_THROW(Mini_st_persistence pcoh2(st), std::out_of_range);
+
+}
diff --git a/src/Simplex_tree/concept/SimplexKey.h b/src/Simplex_tree/concept/SimplexKey.h
index 7fdbdd84..9fbed401 100644
--- a/src/Simplex_tree/concept/SimplexKey.h
+++ b/src/Simplex_tree/concept/SimplexKey.h
@@ -22,7 +22,7 @@
 
  /** \brief Key type used as simplex identifier.
   *
-  * Must be a signed integer type.
+  * Must be an integer type.
   */
  struct SimplexKey {};
  
diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h
index d072cf34..89acdc18 100644
--- a/src/Simplex_tree/concept/SimplexTreeOptions.h
+++ b/src/Simplex_tree/concept/SimplexTreeOptions.h
@@ -31,7 +31,7 @@ struct SimplexTreeOptions {
   typedef VertexHandle Vertex_handle;
   /// Must be comparable with operator<.
   typedef FiltrationValue Filtration_value;
-  /// Must be a signed integer type.
+  /// Must be an integer type.
   typedef SimplexKey Simplex_key;
   /// If true, each simplex has extra storage for one `Simplex_key`. Necessary for `Persistent_cohomology`.
   static const bool store_key;
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 65ead001..fa9c0800 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -48,6 +48,7 @@
 #include <limits>  // Inf
 #include <initializer_list>
 #include <algorithm>  // for std::max
+#include <cstdint>  // for std::uint32_t
 
 namespace Gudhi {
 /** \defgroup simplex_tree Filtered Complexes
@@ -109,7 +110,7 @@ class Simplex_tree {
   typedef typename Options::Filtration_value Filtration_value;
   /** \brief Key associated to each simplex.
    *
-   * Must be a signed integer type. */
+   * Must be an integer type. */
   typedef typename Options::Simplex_key Simplex_key;
   /** \brief Type for the vertex handle.
    *
@@ -1297,25 +1298,31 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
   return is;
 }
 
-/// Model of SimplexTreeOptions.
+/** Model of SimplexTreeOptions.
+ * 
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint32_t>::max()</CODE>
+ * (about 4 billions of simplices). */
 struct Simplex_tree_options_full_featured {
   typedef linear_indexing_tag Indexing_tag;
   typedef int Vertex_handle;
   typedef double Filtration_value;
-  typedef int Simplex_key;
+  typedef std::uint32_t Simplex_key;
   static const bool store_key = true;
   static const bool store_filtration = true;
   static const bool contiguous_vertices = false;
 };
 
-/** Model of SimplexTreeOptions, faster than
-  `Simplex_tree_options_full_featured` but note the unsafe
-  `contiguous_vertices` option. */
+/** Model of SimplexTreeOptions, faster than `Simplex_tree_options_full_featured` but note the unsafe
+ * `contiguous_vertices` option.
+ * 
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint32_t>::max()</CODE>
+ * (about 4 billions of simplices). */
+
 struct Simplex_tree_options_fast_persistence {
   typedef linear_indexing_tag Indexing_tag;
   typedef int Vertex_handle;
   typedef float Filtration_value;
-  typedef int Simplex_key;
+  typedef std::uint32_t Simplex_key;
   static const bool store_key = true;
   static const bool store_filtration = true;
   static const bool contiguous_vertices = true;