Moved into trunk

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

4 files changed, 554 insertions, 0 deletions

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
new file mode 100644
index 00000000..6441a80a
--- /dev/null
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
@@ -0,0 +1,287 @@
+ /*    This file is part of the Gudhi Library. The Gudhi library 
+  *    (Geometric Understanding in Higher Dimensions) is a generic C++ 
+  *    library for computational topology.
+  *
+  *    Author(s):       Clément Maria
+  *
+  *    Copyright (C) 2014  INRIA Sophia Antipolis-Méditerranée (France)
+  *
+  *    This program is free software: you can redistribute it and/or modify
+  *    it under the terms of the GNU General Public License as published by
+  *    the Free Software Foundation, either version 3 of the License, or
+  *    (at your option) any later version.
+  *
+  *    This program is distributed in the hope that it will be useful,
+  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  *    GNU General Public License for more details.
+  *
+  *    You should have received a copy of the GNU General Public License
+  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+  */
+
+#ifndef SIMPLEX_TREE_ITERATORS_H
+#define SIMPLEX_TREE_ITERATORS_H
+
+#include "boost/iterator/iterator_facade.hpp"
+
+namespace Gudhi{
+
+/* \addtogroup simplex_tree
+  * Iterators and range types for the Simplex_tree.
+  * @{
+  */
+
+/* \brief Iterator over the vertices of a simplex
+  * in a SimplexTree.
+  *
+  * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
+template < class SimplexTree >
+class Simplex_tree_simplex_vertex_iterator 
+: public boost::iterator_facade < Simplex_tree_simplex_vertex_iterator < SimplexTree >
+                                , typename SimplexTree::Vertex_handle const
+                                , boost::forward_traversal_tag
+                                , typename SimplexTree::Vertex_handle const
+                                >
+{
+public:
+  typedef typename SimplexTree::Simplex_handle Simplex_handle;
+  typedef typename SimplexTree::Siblings       Siblings;
+  typedef typename SimplexTree::Vertex_handle  Vertex_handle;
+
+  Simplex_tree_simplex_vertex_iterator (SimplexTree * st) :   //any end() iterator
+  sib_(NULL), v_(st->null_vertex()) {}
+
+  Simplex_tree_simplex_vertex_iterator( SimplexTree *  st,
+                                        Simplex_handle sh) :
+  sib_(st->self_siblings(sh)),
+  v_(sh->first)    {}
+
+private:
+  friend class boost::iterator_core_access;
+
+  bool equal (Simplex_tree_simplex_vertex_iterator const &other) const
+  { return sib_ == other.sib_ && v_ == other.v_; }
+
+  Vertex_handle const& dereference() const { return v_; }
+
+  void increment () { v_ = sib_->parent(); sib_ = sib_->oncles();}
+
+  Siblings *    sib_;
+  Vertex_handle        v_;
+};
+
+/*---------------------------------------------------------------------------*/
+/* \brief Iterator over the simplices of the boundary of a
+  *  simplex.
+  *
+  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
+template < class SimplexTree >
+class Simplex_tree_boundary_simplex_iterator 
+: public boost::iterator_facade < Simplex_tree_boundary_simplex_iterator< SimplexTree >
+                                , typename SimplexTree::Simplex_handle const
+                                , boost::forward_traversal_tag
+                                >
+{
+public:
+  typedef typename SimplexTree::Simplex_handle  Simplex_handle;
+  typedef typename SimplexTree::Vertex_handle   Vertex_handle;
+  typedef typename SimplexTree::Siblings        Siblings;
+
+// any end() iterator
+  Simplex_tree_boundary_simplex_iterator(SimplexTree * st) :
+  last_(st->null_vertex()), sib_(NULL) {}
+
+  Simplex_tree_boundary_simplex_iterator ( SimplexTree *  st,
+                                           Simplex_handle sh ) :
+  suffix_(), st_(st)
+  { 
+    last_          = sh->first;
+    Siblings * sib = st->self_siblings(sh);
+    next_          = sib->parent();
+    sib_           = sib->oncles();       /* \todo check if NULL*/
+    if(sib_ != NULL) { sh_ = sib_->find(next_); }
+    else { last_ = st->null_vertex(); } // vertex: == end()
+  }
+
+private:
+  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_);}
+
+  Simplex_handle const& dereference () const  { return sh_; }
+
+  void increment()
+  { 
+    if(sib_ == NULL) { last_ = st_->null_vertex(); return; }
+    
+    Siblings * for_sib = sib_;
+    for(typename std::vector< Vertex_handle >::reverse_iterator rit = suffix_.rbegin();
+      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();
+  }
+
+  Vertex_handle                   last_   ; //last vertex of the simplex
+  Vertex_handle                   next_   ; //next vertex to push in suffix_
+  std::vector< Vertex_handle >    suffix_ ;
+  Siblings *                      sib_    ; //where the next search will start from
+  Simplex_handle                  sh_     ; //current Simplex_handle in the boundary
+  SimplexTree *                   st_     ; //simplex containing the simplicial complex
+};
+/*---------------------------------------------------------------------------*/
+/* \brief Iterator over the simplices of a simplicial complex.
+  *
+  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
+template < class SimplexTree >
+class Simplex_tree_complex_simplex_iterator 
+: public boost::iterator_facade < Simplex_tree_complex_simplex_iterator< SimplexTree >
+                                , typename SimplexTree::Simplex_handle const 
+                                , boost::forward_traversal_tag
+                                >
+{
+public:
+  typedef typename SimplexTree::Simplex_handle Simplex_handle;
+  typedef typename SimplexTree::Siblings       Siblings;
+  typedef typename SimplexTree::Vertex_handle  Vertex_handle;
+
+//any end() iterator
+  Simplex_tree_complex_simplex_iterator() : st_(NULL) {}
+
+  Simplex_tree_complex_simplex_iterator(SimplexTree * st) :
+  st_(st) 
+  {
+    if(st == NULL || st->root() == NULL || st->root()->members().empty())  { st_ = NULL; }
+    else
+   {
+    sh_ = st->root()->members().begin();
+    sib_ = st->root();
+    while(st->has_children(sh_)) 
+      { sib_ = sh_->second.children();
+        sh_ = sib_->members().begin(); }
+    }
+  }
+private:
+  friend class boost::iterator_core_access;
+
+// valid when iterating along the SAME boundary.
+  bool equal (Simplex_tree_complex_simplex_iterator const& other) const
+  {
+    if(other.st_ == NULL) { return (st_ == NULL); }
+    if(st_ == NULL) { return false; }
+    return (&(sh_->second) == &(other.sh_->second));
+  }
+
+  Simplex_handle const& dereference () const { return sh_; }
+
+// Depth first traversal.
+  void increment ()
+  {
+    ++sh_;
+    if(sh_ == sib_->members().end())
+    {
+      if(sib_->oncles() == NULL) { st_ = NULL; return; } //reach the end
+      sh_ = sib_->oncles()->members().find(sib_->parent());
+      sib_ = sib_->oncles();    
+      return; 
+    }
+    while(st_->has_children(sh_)) 
+    {
+     sib_ = sh_->second.children();
+     sh_ = sib_->members().begin(); 
+    }
+  }
+
+  Simplex_handle     sh_;
+  Siblings *         sib_;
+  SimplexTree *      st_;
+};
+
+/* \brief Iterator over the simplices of the skeleton of a given
+  * dimension of the simplicial complex.
+  *
+  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
+template < class SimplexTree >
+class Simplex_tree_skeleton_simplex_iterator 
+: public boost::iterator_facade < Simplex_tree_skeleton_simplex_iterator< SimplexTree >
+                                , typename SimplexTree::Simplex_handle const 
+                                , boost::forward_traversal_tag
+                                >
+{
+public:
+  typedef typename SimplexTree::Simplex_handle Simplex_handle;
+  typedef typename SimplexTree::Siblings       Siblings;
+  typedef typename SimplexTree::Vertex_handle  Vertex_handle;
+
+//any end() iterator
+  Simplex_tree_skeleton_simplex_iterator() : st_(NULL) {}
+
+  Simplex_tree_skeleton_simplex_iterator( SimplexTree * st
+                                        , int dim_skel ) 
+  : st_(st) 
+  , dim_skel_(dim_skel)
+  , curr_dim_(0)
+  {
+    if(st == NULL || st->root() == NULL || st->root()->members().empty())  { st_ = NULL; }
+    else
+   {
+    sh_ = st->root()->members().begin();
+    sib_ = st->root();
+    while(st->has_children(sh_) && curr_dim_ < dim_skel_) 
+      { sib_ = sh_->second.children();
+        sh_ = sib_->members().begin();
+        ++curr_dim_; }
+    }
+  }
+private:
+  friend class boost::iterator_core_access;
+
+// valid when iterating along the SAME boundary.
+  bool equal (Simplex_tree_skeleton_simplex_iterator const& other) const
+  {
+    if(other.st_ == NULL) { return (st_ == NULL); }
+    if(st_ == NULL)       { return false; }
+    return (&(sh_->second) == &(other.sh_->second));
+  }
+
+  Simplex_handle const& dereference () const { return sh_; }
+
+// Depth first traversal of the skeleton.
+  void increment ()
+  {
+    ++sh_;
+    if(sh_ == sib_->members().end())
+    {
+      if(sib_->oncles() == NULL) { st_ = NULL; return; } //reach the end
+      sh_ = sib_->oncles()->members().find(sib_->parent());
+      sib_ = sib_->oncles();
+      --curr_dim_;    
+      return; 
+    }
+    while(st_->has_children(sh_) && curr_dim_ < dim_skel_) 
+    {
+     sib_ = sh_->second.children();
+     sh_ = sib_->members().begin(); 
+     ++curr_dim_;
+    }
+  }
+
+  Simplex_handle     sh_;
+  Siblings *         sib_;
+  SimplexTree *      st_;
+  int                dim_skel_;
+  int                curr_dim_;
+};
+
+/* @} */ //end addtogroup simplex_tree
+
+}  // namespace GUDHI
+
+#endif // SIMPLEX_TREE_ITERATORS_H
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h
new file mode 100644
index 00000000..91f4ef75
--- /dev/null
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h
@@ -0,0 +1,104 @@
+ /*    This file is part of the Gudhi Library. The Gudhi library 
+  *    (Geometric Understanding in Higher Dimensions) is a generic C++ 
+  *    library for computational topology.
+  *
+  *    Author(s):       Clément Maria
+  *
+  *    Copyright (C) 2014  INRIA Sophia Antipolis-Méditerranée (France)
+  *
+  *    This program is free software: you can redistribute it and/or modify
+  *    it under the terms of the GNU General Public License as published by
+  *    the Free Software Foundation, either version 3 of the License, or
+  *    (at your option) any later version.
+  *
+  *    This program is distributed in the hope that it will be useful,
+  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  *    GNU General Public License for more details.
+  *
+  *    You should have received a copy of the GNU General Public License
+  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+  */
+
+#ifndef GUDHI_SIMPLEX_TREE_NODE_EXPLICIT_STORAGE_H
+#define GUDHI_SIMPLEX_TREE_NODE_EXPLICIT_STORAGE_H
+
+#include <vector>
+#include <iostream>
+
+namespace Gudhi{
+
+/* \addtogroup simplex_tree
+  * Represents a node of a Simplex_tree.
+  * @{
+  */
+
+/*
+ * \brief Node of a simplex tree with filtration value
+ * and simplex key.
+ *
+ * It stores explicitely its own filtration value and its own Simplex_key.
+ */
+template < class SimplexTree > 
+class Simplex_tree_node_explicit_storage {
+  public:
+//  friend SimplexTree;
+
+  typedef typename SimplexTree::Siblings         Siblings;
+  typedef typename SimplexTree::Filtration_value Filtration_value;
+  typedef typename SimplexTree::Simplex_key      Simplex_key;
+
+  //private:
+  //friend class Simplex_tree; 
+  // Default constructor.
+  Simplex_tree_node_explicit_storage() :
+  children_(NULL),
+  simplex_key_(-1),
+  filtration_(0) {}
+
+  Simplex_tree_node_explicit_storage(Siblings * sib,
+                                     Filtration_value filtration) :
+  children_(sib),
+  simplex_key_(-1),
+  filtration_(filtration) {}
+
+
+  void assign_key(Simplex_key key) { simplex_key_ = key; }
+
+  /*
+   * Return true if the node has children,
+   * false otherwise.
+   */
+  //bool has_children(Vertex label)
+  //{ //if(children_ == NULL)             return false; //for root simplices
+  //  return (children_->parent() == label);}
+  /*
+   * Assign a children to the node
+   */
+  void assign_children (Siblings * children) { children_ = children; }
+  /*
+   *
+   */
+  void assign_filtration(double filtration_value) { filtration_ = filtration_value; }
+  
+  Filtration_value filtration() { return filtration_; }
+
+  /* Careful -> has_children() must be true*/
+  Siblings * children() { return children_; }
+  
+  Simplex_key key() { return simplex_key_; }
+  
+private:
+   Siblings *              children_;
+  
+  // Data attached to simplex, explicit storage
+  Simplex_key             simplex_key_;
+  Filtration_value        filtration_;   //value in the filtration
+  
+};
+
+/* @} */ //end addtogroup simplex_tree
+
+}  // namespace GUDHI
+
+#endif // GUDHI_SIMPLEX_TREE_NODE_EXPLICIT_STORAGE_H
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
new file mode 100644
index 00000000..6db0d80a
--- /dev/null
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
@@ -0,0 +1,129 @@
+ /*    This file is part of the Gudhi Library. The Gudhi library 
+  *    (Geometric Understanding in Higher Dimensions) is a generic C++ 
+  *    library for computational topology.
+  *
+  *    Author(s):       Clément Maria
+  *
+  *    Copyright (C) 2014  INRIA Sophia Antipolis-Méditerranée (France)
+  *
+  *    This program is free software: you can redistribute it and/or modify
+  *    it under the terms of the GNU General Public License as published by
+  *    the Free Software Foundation, either version 3 of the License, or
+  *    (at your option) any later version.
+  *
+  *    This program is distributed in the hope that it will be useful,
+  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  *    GNU General Public License for more details.
+  *
+  *    You should have received a copy of the GNU General Public License
+  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+  */
+
+#ifndef GUDHI_SIMPLEX_TREE_SIBLINGS
+#define GUDHI_SIMPLEX_TREE_SIBLINGS
+
+#include "boost/container/flat_map.hpp"
+#include "Simplex_tree_node_explicit_storage.h"
+
+namespace Gudhi{
+
+/* \addtogroup simplex_tree
+  * Represents a set of node of a Simplex_tree that share the same parent.
+  * @{
+  */
+
+/* \brief Data structure to store a set of nodes in a SimplexTree sharing
+ * the same parent node.*/
+template < class SimplexTree
+         , class MapContainer >
+class Simplex_tree_siblings {
+// private:
+//  friend SimplexTree;
+public:
+  template < class T > friend class Simplex_tree_simplex_vertex_iterator  ; 
+  template < class T > friend class Simplex_tree_boundary_simplex_iterator;
+  template < class T > friend class Simplex_tree_complex_simplex_iterator ;
+  template < class T > friend class Simplex_tree_skeleton_simplex_iterator;
+
+  typedef typename SimplexTree::Vertex_handle     Vertex_handle;
+  typedef typename SimplexTree::Filtration_value  Filtration_value;
+  typedef typename SimplexTree::Node              Node;
+  typedef MapContainer                            Dictionary;
+  typedef typename MapContainer::iterator         Dictionary_it;
+
+  /* Default constructor.*/
+  Simplex_tree_siblings() 
+  : oncles_(NULL)
+  , parent_(-1)
+  , members_() {}
+  
+  /* Constructor with values.*/
+  Simplex_tree_siblings(Simplex_tree_siblings  * oncles,
+                        Vertex_handle            parent )
+  : oncles_(oncles)
+  , parent_(parent)
+  , members_() {}
+  
+  /* \brief Constructor with initialized set of members.
+    *
+    * 'members' must be sorted and unique.*/
+  Simplex_tree_siblings(Simplex_tree_siblings *                           oncles,
+                        Vertex_handle                                     parent,
+                        std::vector< std::pair< Vertex_handle, Node > > & members) 
+  : oncles_ ( oncles )
+  , parent_ ( parent )
+  , members_ ( boost::container::ordered_unique_range
+             , members.begin()
+             , members.end() )
+  {
+    for(auto map_it = members_.begin();
+        map_it != members_.end(); map_it++)
+    {  map_it->second.assign_children(this);  }
+  }
+  
+  /*
+   * \brief Inserts a Node in the set of siblings nodes.
+   *
+   * If already present, assigns the minimal filtration value 
+   * between input filtration_value and the value already 
+   * present in the node.
+   */
+  void insert ( Vertex_handle     v
+              , Filtration_value  filtration_value )
+  {
+    typename Dictionary::iterator sh = members_.find(v);
+    if(sh != members_.end() &&  sh->second.filtration() > filtration_value)
+    { sh->second.assign_filtration(filtration_value);
+      return; }
+    if(sh == members_.end()) 
+    {  members_.insert(std::pair< Vertex_handle, Node >( v, Node(this,filtration_value) )); 
+      return; }
+  }
+
+  typename Dictionary::iterator find( Vertex_handle v )
+  { return members_.find(v); }
+  
+  Simplex_tree_siblings * oncles()
+  {  return oncles_;  }
+  
+  Vertex_handle parent()
+  {  return parent_;  }
+  
+  Dictionary & members()
+  { return members_; }
+  
+  size_t size() { return members_.size(); }
+
+
+  Simplex_tree_siblings        * oncles_  ;
+  Vertex_handle                  parent_  ;
+  Dictionary                     members_ ;
+  
+};
+
+/* @} */ //end addtogroup simplex_tree
+
+}  // namespace GUDHI
+
+#endif // GUDHI_SIMPLEX_TREE_SIBLINGS
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h
new file mode 100644
index 00000000..165d166d
--- /dev/null
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h
@@ -0,0 +1,34 @@
+ /*    This file is part of the Gudhi Library. The Gudhi library 
+  *    (Geometric Understanding in Higher Dimensions) is a generic C++ 
+  *    library for computational topology.
+  *
+  *    Author(s):       Clément Maria
+  *
+  *    Copyright (C) 2014  INRIA Sophia Antipolis-Méditerranée (France)
+  *
+  *    This program is free software: you can redistribute it and/or modify
+  *    it under the terms of the GNU General Public License as published by
+  *    the Free Software Foundation, either version 3 of the License, or
+  *    (at your option) any later version.
+  *
+  *    This program is distributed in the hope that it will be useful,
+  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  *    GNU General Public License for more details.
+  *
+  *    You should have received a copy of the GNU General Public License
+  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+  */
+
+namespace Gudhi{
+
+/** \brief Tag for a linear ordering of simplices. 
+  *
+  * \implements IndexingTag
+  */
+  struct linear_indexing_tag {};
+
+/* \brief Tag for a zigzag ordering of simplices. */
+//  struct zigzag_indexing_tag {};
+
+}  // namespace GUDHI