Backmerge from trunk

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

Former-commit-id: 06624ae4ed4031c7bae56e0b8fa305a318b934bc

2 files changed, 65 insertions, 21 deletions

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index edb1d7c9..356deb3a 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -43,6 +43,7 @@
 #include <utility>
 #include <vector>
 #include <functional>  // for greater<>
+#include <initializer_list>
 
 namespace Gudhi {
 
@@ -81,15 +82,7 @@ namespace Gudhi {
  * @{
  */
 
-/// Model of SimplexTreeOptions.
-struct Simplex_tree_options_full_featured {
-  typedef linear_indexing_tag Indexing_tag;
-  typedef int Vertex_handle;
-  typedef double Filtration_value;
-  typedef int Simplex_key;
-  static const bool store_key = true;
-  static const bool store_filtration = true;
-};
+struct Simplex_tree_options_full_featured;
 
 /**
  * \brief Simplex Tree data structure for representing simplicial complexes.
@@ -535,7 +528,7 @@ class Simplex_tree {
    * The type InputVertexRange must be a range of <CODE>Vertex_handle</CODE>
    * on which we can call std::begin() function
    */
-  template<class InputVertexRange>
+  template<class InputVertexRange=std::initializer_list<Vertex_handle>>
   Simplex_handle find(const InputVertexRange & s) {
     auto first = std::begin(s);
     auto last = std::end(s);
@@ -571,9 +564,22 @@ class Simplex_tree {
   /** \brief Returns the Simplex_handle corresponding to the 0-simplex
    * representing the vertex with Vertex_handle v. */
   Simplex_handle find_vertex(Vertex_handle v) {
-    return root_.members_.begin() + v;
+    if (Options::contiguous_vertices) {
+      assert(contiguous_vertices());
+      return root_.members_.begin() + v;
+    } else {
+      return root_.members_.find(v);
+    }
+  }
+
+ public:
+  /** \private \brief Test if the vertices have contiguous numbering: 0, 1, etc.  */
+  bool contiguous_vertices() const {
+    if (root_.members_.empty()) return true;
+    if (root_.members_.begin()->first != 0) return false;
+    if (std::prev(root_.members_.end())->first != root_.members_.size()-1) return false;
+    return true;
   }
-  //{ return root_.members_.find(v); }
 
  private:
   /** \brief Inserts a simplex represented by a vector of vertex.
@@ -629,7 +635,7 @@ class Simplex_tree {
    *
    * The type InputVertexRange must be a range for which .begin() and
    * .end() return input iterators, with 'value_type' Vertex_handle. */
-  template<class InputVertexRange>
+  template<class InputVertexRange=std::initializer_list<Vertex_handle>>
   std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
                                                  Filtration_value filtration = 0) {
     auto first = std::begin(simplex);
@@ -658,7 +664,7 @@ class Simplex_tree {
    * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to
    * null_simplex.
    */
-  template<class InputVertexRange>
+  template<class InputVertexRange=std::initializer_list<Vertex_handle>>
   std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex,
                                    Filtration_value filtration = 0) {
     auto first = std::begin(Nsimplex);
@@ -1153,6 +1159,31 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
 
   return is;
 }
+
+/// Model of SimplexTreeOptions.
+struct Simplex_tree_options_full_featured {
+  typedef linear_indexing_tag Indexing_tag;
+  typedef int Vertex_handle;
+  typedef double Filtration_value;
+  typedef int 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. */
+struct Simplex_tree_options_fast_persistence {
+  typedef linear_indexing_tag Indexing_tag;
+  typedef int Vertex_handle;
+  typedef float Filtration_value;
+  typedef int Simplex_key;
+  static const bool store_key = true;
+  static const bool store_filtration = true;
+  static const bool contiguous_vertices = true;
+};
+
 /** @} */  // end defgroup simplex_tree
 
 }  // namespace Gudhi
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
index 372ef329..794060ee 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
@@ -99,12 +99,13 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
 
 // any end() iterator
   explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
-      : last_(st->null_vertex()),
-        sib_(NULL) {
+      : sib_(NULL),
+        sh_(st->null_simplex()) {
   }
 
   Simplex_tree_boundary_simplex_iterator(SimplexTree * st, Simplex_handle sh)
       : suffix_(),
+        sib_(st->self_siblings(sh)),
         st_(st) {
     last_ = sh->first;
     Siblings * sib = st->self_siblings(sh);
@@ -113,7 +114,7 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
     if (sib_ != NULL) {
       sh_ = sib_->find(next_);
     } else {
-      last_ = st->null_vertex();
+      sh_ = st->null_simplex();
     }  // vertex: == end()
   }
 
@@ -121,28 +122,40 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
   friend class boost::iterator_core_access;
 // valid when iterating along the SAME boundary.
   bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
-    return (sib_ == other.sib_ && last_ == other.last_);
+    return sh_ == other.sh_;
   }
 
   Simplex_handle const& dereference() const {
+    assert(sh_ != st_->null_simplex());
     return sh_;
   }
 
   void increment() {
     if (sib_ == NULL) {
-      last_ = st_->null_vertex();
+      sh_ = st_->null_simplex();
       return;
     }
 
     Siblings * for_sib = sib_;
-    for (auto rit = suffix_.rbegin(); rit != suffix_.rend(); ++rit) {
+    Siblings * new_sib = sib_->oncles();
+    auto rit = suffix_.rbegin();
+    if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr && rit != suffix_.rend()) {
+      // We reached the root, use a short-cut to find a vertex. We could also
+      // optimize finding the second vertex of a segment, but people are
+      // expected to call endpoints().
+      assert(st_->contiguous_vertices());
+      sh_ = for_sib->members_.begin()+*rit;
+      for_sib = sh_->second.children();
+      ++rit;
+    }
+    for (; rit != suffix_.rend(); ++rit) {
       sh_ = for_sib->find(*rit);
       for_sib = sh_->second.children();
     }
     sh_ = for_sib->find(last_);  // sh_ points to the right simplex now
     suffix_.push_back(next_);
     next_ = sib_->parent();
-    sib_ = sib_->oncles();
+    sib_ = new_sib;
   }
 
   // Most of the storage should be moved to the range, iterators should be light.