Added the files from the coxeter branch

9 files changed, 1123 insertions, 0 deletions

diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Combination_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Combination_iterator.h
new file mode 100644
index 00000000..20a4a8ff
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Combination_iterator.h
@@ -0,0 +1,101 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_COMBINATION_ITERATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_COMBINATION_ITERATOR_H_
+
+#include <vector>
+#include <boost/range/iterator_range.hpp>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+typedef unsigned uint;
+
+/** \brief Class that allows the user to generate combinations of 
+ *   k elements in a set of n elements.
+ *  Based on the algorithm by Mifsud.
+*/
+class Combination_iterator : public boost::iterator_facade< Combination_iterator,
+							    std::vector<uint> const,
+							    boost::forward_traversal_tag> {
+  typedef std::vector<uint> value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+  
+  bool equal(Combination_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    if (value_[0] == n_ - k_) {
+      is_end_ = true;
+      return;
+    }
+    uint j = k_ - 1;
+    if (value_[j] < n_ - 1) {
+      value_[j]++;
+      return;
+    }
+    for (; j > 0; --j)
+      if (value_[j-1] < n_ - k_ + j-1) {
+	value_[j-1]++;
+	for (uint s = j; s < k_; s++)
+	  value_[s] = value_[j-1] + s - (j-1);
+	return;
+      }
+  }
+
+public:
+  
+  Combination_iterator(const uint& n, const uint& k)
+    :
+    value_(k),
+    is_end_(n == 0),
+    n_(n),
+    k_(k)
+  {
+    for (uint i = 0; i < k; ++i)
+      value_[i] = i;
+  }
+
+  // Used for the creating an end iterator
+  Combination_iterator() : is_end_(true), n_(0), k_(0) {}
+
+  void reinitialize() {
+    if (n_ > 0) {
+      is_end_ = false;
+      for (uint i = 0; i < n_; ++i)
+      value_[i] = i;
+    }
+  }
+  
+protected:
+  value_t value_; // the dereference value
+  bool is_end_;   // is true when the current permutation is the final one 
+
+  uint n_;
+  uint k_;
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Integer_combination_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Integer_combination_iterator.h
new file mode 100644
index 00000000..47eb8b98
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Integer_combination_iterator.h
@@ -0,0 +1,128 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_INTEGER_COMBINATION_ITERATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_INTEGER_COMBINATION_ITERATOR_H_
+
+#include <vector>
+#include <boost/range/iterator_range.hpp>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+typedef unsigned uint;
+
+/** \brief Class that allows the user to generate combinations of 
+ *   k elements in a set of n elements.
+ *  Based on the algorithm by Mifsud.
+*/
+class Integer_combination_iterator : public boost::iterator_facade< Integer_combination_iterator,
+								    std::vector<uint> const,
+								    boost::forward_traversal_tag> {
+  typedef std::vector<uint> value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+  
+  bool equal(Integer_combination_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    uint j1 = 0;
+    uint s = 0;
+    while (value_[j1] == 0 && j1 < k_)
+      j1++;
+    uint j2 = j1+1;
+    while (value_[j2] == bounds_[j2]) {
+      if (bounds_[j2] != 0) {
+	s += value_[j1];
+	value_[j1] = 0;
+	j1 = j2;
+      }
+      j2++;
+    }
+    if (j2 >= k_) {
+      is_end_ = true;
+      return;
+    }
+    s += value_[j1] - 1;
+    value_[j1] = 0;
+    value_[j2]++;
+    uint i = 0;
+    while (s >= bounds_[i]) {
+      value_[i] = bounds_[i];
+      s -= bounds_[i];
+      i++;
+    }
+    value_[i++] = s;
+  }
+
+public:
+
+  template <class Bound_range>
+  Integer_combination_iterator(const uint& n, const uint& k, const Bound_range& bounds)
+    :
+    value_(k+2),
+    is_end_(n == 0 || k == 0),
+    n_(n),
+    k_(k)
+  {
+    bounds_.reserve(k+2);
+    uint sum_radices = 0;
+    for (auto b: bounds) {
+      bounds_.push_back(b);
+      sum_radices += b;      
+    }
+    bounds_.push_back(2);
+    bounds_.push_back(1);
+    if (n > sum_radices) {
+      is_end_ = true;
+      return;
+    }
+    uint i = 0;
+    uint s = n;
+    while (s >= bounds_[i]) {
+      value_[i] = bounds_[i];
+      s -= bounds_[i];
+      i++;
+    }
+    value_[i++] = s;
+
+    while (i < k_)
+      value_[i++] = 0;    
+    value_[k] = 1;
+    value_[k+1] = 0;
+  }
+
+  // Used for the creating an end iterator
+  Integer_combination_iterator() : is_end_(true), n_(0), k_(0) {}
+  
+protected:
+  value_t value_; // the dereference value
+  bool is_end_;   // is true when the current integer combination is the final one 
+
+  uint n_;
+  uint k_;
+  std::vector<uint> bounds_;
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Ordered_set_partition_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Ordered_set_partition_iterator.h
new file mode 100644
index 00000000..55c32664
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Ordered_set_partition_iterator.h
@@ -0,0 +1,108 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_ORDERED_SET_PARTITION_ITERATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_ORDERED_SET_PARTITION_ITERATOR_H_
+
+#include <vector>
+#include <limits>
+#include <gudhi/Permutahedral_representation/Permutation_iterator.h>
+#include <gudhi/Permutahedral_representation/Set_partition_iterator.h>
+#include <boost/range/iterator_range.hpp>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+typedef unsigned uint;
+
+/** \brief Class that represents an ordered set partition of a set {0,...,n-1} in k parts as
+ *         a pair of an unordered set partition given in lexicographic order and
+ *         a permutation of the parts.
+ */
+struct Ordered_set_partition {
+  Set_partition_iterator s_it_;
+  Permutation_iterator p_it_;
+
+  // Ordered_set_partition(const Set_partition_iterator& s_it, const Permutation_iterator& p_it)
+  //   : s_it_(s_it), p_it_(p_it) {}
+  
+  const std::vector<uint> operator[](const uint& i) const {
+    return (*s_it_)[(*p_it_)[i]];
+  }
+  
+  std::size_t size() const {
+    return s_it_->size();
+  }
+  
+};
+
+/** \brief Class that allows the user to generate set partitions of a set {0,...,n-1} in k parts.
+ *   
+*/
+class Ordered_set_partition_iterator : public boost::iterator_facade< Ordered_set_partition_iterator,
+								      Ordered_set_partition const,
+								      boost::forward_traversal_tag> {
+  typedef Ordered_set_partition value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+
+  bool equal(Ordered_set_partition_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    if (++value_.p_it_ == p_end_) {
+      if (++value_.s_it_ == s_end_) {
+	is_end_ = true;
+	return;
+      }
+      else
+	value_.p_it_.reinitialize();
+    }
+  }
+  
+public:
+  
+  Ordered_set_partition_iterator(const uint& n, const uint& k)
+    :
+    value_({Set_partition_iterator(n,k), Permutation_iterator(k)}),
+    is_end_(n == 0)
+  {
+  }
+
+  // Used for the creating an end iterator
+  Ordered_set_partition_iterator() : is_end_(true) {}
+
+  void reinitialize() {
+    is_end_ = false;
+    value_.p_it_.reinitialize();
+    value_.s_it_.reinitialize();
+  }
+  
+protected:
+  Set_partition_iterator s_end_; // Set partition iterator and the corresponding end iterator
+  Permutation_iterator p_end_; // Permutation iterator and the corresponding end iterator
+  value_t value_;         // the dereference value
+  bool is_end_;   // is true when the current permutation is the final one 
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h
new file mode 100644
index 00000000..4528ef20
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h
@@ -0,0 +1,288 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_PERMUTAHEDRAL_REPRESENTATION_ITERATORS_H_
+#define PERMUTAHEDRAL_REPRESENTATION_PERMUTAHEDRAL_REPRESENTATION_ITERATORS_H_
+
+#include <gudhi/Permutahedral_representation/Size_range.h>
+#include <gudhi/Permutahedral_representation/Ordered_set_partition_iterator.h>
+#include <gudhi/Permutahedral_representation/Integer_combination_iterator.h>
+#include <gudhi/Permutahedral_representation/Combination_iterator.h>
+#include <gudhi/Permutahedral_representation/face_from_indices.h>
+#include <boost/iterator/iterator_facade.hpp>
+
+#include <vector>
+#include <iostream>
+#include <algorithm>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+/* \addtogroup coxeter_triangulation
+ * Iterator types for Permutahedral_representation
+ * @{
+ */
+
+/* \brief Iterator over the vertices of a simplex
+ * represented by its permutahedral representation.
+ *
+ * Forward iterator, 'value_type' is Permutahedral_representation::Vertex.*/
+template <class Permutahedral_representation>
+class Vertex_iterator : public boost::iterator_facade< Vertex_iterator<Permutahedral_representation>,
+						       typename Permutahedral_representation::Vertex const,
+						       boost::forward_traversal_tag> {
+protected:
+  friend class boost::iterator_core_access;
+
+  using Vertex = typename Permutahedral_representation::Vertex;
+  using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
+
+  typedef Vertex value_t;
+
+  
+  bool equal(Vertex_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void update_value() {
+    std::size_t d = value_.size();
+    for (auto i: *o_it_)
+      if (i != d)
+	value_[i]++;
+      else
+	for (std::size_t j = 0; j < d; j++)
+	  value_[j]--;
+  }
+		       
+  void increment() {
+    if (is_end_)
+      return;
+    update_value();
+    if (++o_it_ == o_end_)
+      is_end_ = true;
+  }
+
+public:  
+  Vertex_iterator(const Permutahedral_representation& simplex)
+    :
+    o_it_(simplex.partition().begin()),
+    o_end_(simplex.partition().end()),
+    value_(simplex.vertex()),
+    is_end_(o_it_ == o_end_)
+  {}
+
+  Vertex_iterator() : is_end_(true) {}
+  
+  
+protected:
+  typename Ordered_partition::const_iterator o_it_, o_end_; 
+  value_t value_;
+  bool is_end_;
+
+}; // Vertex_iterator
+
+/*---------------------------------------------------------------------------*/
+/* \brief Iterator over the k-faces of a simplex
+ *  given by its permutahedral representation.
+ *
+ * Forward iterator, value_type is Permutahedral_representation. */
+template <class Permutahedral_representation>
+class Face_iterator : public boost::iterator_facade< Face_iterator<Permutahedral_representation>,
+						     Permutahedral_representation const,
+						     boost::forward_traversal_tag> {
+  typedef Permutahedral_representation value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+
+  using Vertex = typename Permutahedral_representation::Vertex;
+  using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
+
+  bool equal(Face_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    if (++c_it_ == c_end_) {
+      is_end_ = true;
+      return;
+    }
+    update_value();
+  }
+
+  void update_value() {
+    // Combination *c_it_ is supposed to be sorted in increasing order
+    value_ = face_from_indices<Permutahedral_representation>(simplex_, *c_it_);
+  }
+  
+public:
+  
+  Face_iterator(const Permutahedral_representation& simplex, const uint& k)
+    : simplex_(simplex),
+      k_(k),
+      l_(simplex.dimension()),
+      c_it_(l_+1, k_+1),
+      is_end_(k_ > l_),
+      value_({Vertex(simplex.vertex().size()), Ordered_partition(k+1)})
+  {
+    update_value();
+  }
+
+  // Used for the creating an end iterator
+  Face_iterator() : is_end_(true) {}
+  
+protected:
+  Permutahedral_representation simplex_; // Input simplex
+  uint k_;
+  uint l_; // Dimension of the input simplex
+  Combination_iterator c_it_, c_end_; // indicates the vertices in the current face
+
+  bool is_end_;   // is true when the current permutation is the final one
+  value_t value_; // the dereference value
+
+}; // Face_iterator
+
+/*---------------------------------------------------------------------------*/
+/* \brief Iterator over the k-cofaces of a simplex
+ *  given by its permutahedral representation.
+ *
+ * Forward iterator, value_type is Permutahedral_representation. */
+template <class Permutahedral_representation>
+class Coface_iterator : public boost::iterator_facade< Coface_iterator<Permutahedral_representation>,
+						       Permutahedral_representation const,
+						       boost::forward_traversal_tag> {
+  typedef Permutahedral_representation value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+
+  using Vertex = typename Permutahedral_representation::Vertex;
+  using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
+
+  bool equal(Coface_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    uint i = 0;
+    for (; i < k_+1; i++) {
+      if (++(o_its_[i]) != o_end_)
+	break;
+    }
+    if (i == k_+1) {
+      if (++i_it_ == i_end_) {
+	is_end_ = true;
+	return;
+      }
+      o_its_.clear();
+      for (uint j = 0; j < k_ + 1; j++)
+	o_its_.emplace_back(Ordered_set_partition_iterator(simplex_.partition()[j].size(), (*i_it_)[j]+1));
+    }
+    else
+      for (uint j = 0; j < i; j++)
+	o_its_[j].reinitialize();
+    update_value();
+  }
+
+  void update_value() {
+    value_.vertex() = simplex_.vertex();
+    for (auto& p: value_.partition())
+      p.clear();
+    uint u_ = 0; // the part in o_its_[k_] that contains t_
+    for (; u_ <= (*i_it_)[k_]; u_++) {
+      auto range = (*o_its_[k_])[u_];
+      if (std::find(range.begin(), range.end(), t_) != range.end())
+	break;
+    }
+    uint i = 0;
+    for (uint j = u_+1; j <= (*i_it_)[k_]; j++, i++)
+      for (uint b: (*o_its_[k_])[j]) {
+	uint c = simplex_.partition()[k_][b];
+        value_.partition()[i].push_back(c);
+	value_.vertex()[c]--;
+      }
+    for (uint h = 0; h < k_; h++)
+      for (uint j = 0; j <= (*i_it_)[h]; j++, i++) {
+	for (uint b: (*o_its_[h])[j])
+	  value_.partition()[i].push_back(simplex_.partition()[h][b]);
+      }
+    for (uint j = 0; j <= u_; j++, i++)
+      for (uint b: (*o_its_[k_])[j])
+	value_.partition()[i].push_back(simplex_.partition()[k_][b]);
+    // sort the values in each part (probably not needed)
+    for (auto& part: value_.partition())
+      std::sort(part.begin(), part.end());
+  }
+  
+public:
+  
+  Coface_iterator(const Permutahedral_representation& simplex, const uint& l)
+    : simplex_(simplex),
+      d_(simplex.vertex().size()),
+      l_(l),
+      k_(simplex.dimension()),
+      i_it_(l_-k_ , k_+1, Size_range<Ordered_partition>(simplex.partition())),
+      is_end_(k_ > l_),
+      value_({Vertex(d_), Ordered_partition(l_+1)})
+  {
+    uint j = 0;
+    for (; j < simplex_.partition()[k_].size(); j++)
+      if (simplex_.partition()[k_][j] == d_) {
+	t_ = j;
+	break;
+      }
+    if (j == simplex_.partition()[k_].size()) {
+      std::cerr << "Coface iterator: the argument simplex is not a permutahedral representation\n";
+      is_end_ = true;
+      return;
+    }
+    for (uint i = 0; i < k_+1; i++)
+      o_its_.emplace_back(Ordered_set_partition_iterator(simplex_.partition()[i].size(), (*i_it_)[i]+1));
+    update_value();
+  }
+
+  // Used for the creating an end iterator
+  Coface_iterator() : is_end_(true) {}
+  
+protected:
+  Permutahedral_representation simplex_; // Input simplex
+  uint d_; // Ambient dimension
+  uint l_; // Dimension of the coface
+  uint k_; // Dimension of the input simplex
+  uint t_; // The position of d in simplex_.partition()[k_]
+  Integer_combination_iterator i_it_, i_end_; // indicates in how many parts each simplex_[i] is subdivided
+  std::vector<Ordered_set_partition_iterator> o_its_; // indicates subdivision for each simplex_[i]
+  Ordered_set_partition_iterator o_end_;      // one end for all o_its_
+
+  bool is_end_;   // is true when the current permutation is the final one
+  value_t value_; // the dereference value
+
+}; // Coface_iterator
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+  
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h
new file mode 100644
index 00000000..7cf6158b
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutation_iterator.h
@@ -0,0 +1,137 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_PERMUTATION_ITERATOR_H_
+
+#include <vector>
+#include <boost/range/iterator_range.hpp>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+typedef unsigned uint;
+
+/** \brief Class that allows the user to generate permutations.
+ *   Based on the optimization of the Heap's algorithm by Sedgewick.
+*/
+class Permutation_iterator : public boost::iterator_facade< Permutation_iterator,
+							    std::vector<uint> const,
+							    boost::forward_traversal_tag> {
+  typedef std::vector<uint> value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+
+  bool equal(Permutation_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void swap_two_indices(std::size_t i, std::size_t j) {
+    uint t = value_[i];
+    value_[i] = value_[j];
+    value_[j] = t;
+  }
+  
+  void elementary_increment() {
+    uint j = 0;
+    while (d_[j] == j+1) {
+      d_[j] = 0;
+      ++j;
+    }
+    if (j == n_ - 1) {
+      is_end_ = true;
+      return;
+    }
+    uint k = j+1;
+    uint x = (k%2 ? d_[j] : 0);
+    swap_two_indices(k, x);
+    ++d_[j];
+  }
+
+  void elementary_increment_optim_3() {
+    if (ct_ != 0) {
+      --ct_;
+      swap_two_indices(1 + (ct_%2), 0);
+    }
+    else {
+      ct_ = 5;
+      uint j = 2;
+      while (d_[j] == j+1) {
+	d_[j] = 0;
+	++j;
+      }
+      if (j == n_ - 1) {
+	is_end_ = true;
+	return;
+      }
+      uint k = j+1;
+      uint x = (k%2 ? d_[j] : 0);
+      swap_two_indices(k, x);
+      ++d_[j];
+    }
+  }
+    
+  void increment() {
+    if (optim_3_)
+      elementary_increment_optim_3();
+    else
+      elementary_increment();      
+  }
+
+public:
+  
+  Permutation_iterator(const uint& n)
+    :
+    value_(n),
+    is_end_(n == 0),
+    optim_3_(n >= 3),
+    n_(n),
+    d_(n),
+    ct_(5)
+  {
+    for (uint i = 0; i < n; ++i) {
+      value_[i] = i;
+      d_[i] = 0;
+    }
+    if (n > 0)
+      d_[n-1] = -1;
+  }
+
+  // Used for the creating an end iterator
+  Permutation_iterator() : is_end_(true), n_(0) {}
+
+  void reinitialize() {
+    if (n_ > 0)
+      is_end_ = false;
+  }
+  
+protected:
+  value_t value_; // the dereference value
+  bool is_end_;   // is true when the current permutation is the final one 
+  bool optim_3_;  // true if n>=3. for n >= 3, the algorithm is optimized
+
+  uint n_;
+  std::vector<uint> d_; // mix radix digits with radix [2 3 4 ... n-1 (sentinel=-1)]
+  uint ct_;             // counter with values in {0,...,5} used in the n>=3 optimization.
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h
new file mode 100644
index 00000000..46f67752
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Set_partition_iterator.h
@@ -0,0 +1,137 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_SET_PARTITION_ITERATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_SET_PARTITION_ITERATOR_H_
+
+#include <vector>
+#include <limits>
+#include <boost/range/iterator_range.hpp>
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+typedef unsigned uint;
+
+/** \brief Class that allows the user to generate set partitions of a set {0,...,n-1} in k parts.
+ *   
+*/
+class Set_partition_iterator : public boost::iterator_facade< Set_partition_iterator,
+							      std::vector<std::vector<uint> > const,
+							      boost::forward_traversal_tag> {
+  typedef std::vector<std::vector<uint> > value_t;
+  
+protected:
+  friend class boost::iterator_core_access;
+
+  bool equal(Set_partition_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  value_t const& dereference() const {
+    return value_;
+  }
+
+  void update_value() {
+    for (uint i = 0; i < k_; i++)
+      value_[i].clear();
+    for (uint i = 0; i < n_; i++)
+      value_[rgs_[i]].push_back(i);
+  }
+  
+  void increment() {
+    if (k_ <= 1) {
+      is_end_ = true;
+      return;
+    }
+    uint i = n_ - 1;
+    while (rgs_[i] + 1 > max_[i] ||
+	   rgs_[i] + 1 >= k_)
+      i--;
+    if (i == 0) {
+      is_end_ = true;
+      return;
+    }
+    rgs_[i]++;
+    uint mm = max_[i];
+    mm += (rgs_[i] >= mm);
+    max_[i+1] = mm;
+    while (++i < n_) {
+      rgs_[i] = 0;
+      max_[i+1] = mm;
+    }
+    uint p = k_;
+    if (mm < p)
+      do {
+	max_[i] = p;
+	--i;
+	--p;
+	rgs_[i] = p;
+      } while (max_[i] < p);
+    update_value();
+  }
+  
+public:
+  
+  Set_partition_iterator(const uint& n, const uint& k)
+    :
+    value_(k),
+    rgs_(n, 0),
+    max_(n+1),
+    is_end_(n == 0),
+    n_(n),
+    k_(k)
+  {
+    max_[0] = std::numeric_limits<uint>::max();
+    for (uint i = 0; i <= n-k; ++i)
+      value_[0].push_back(i);
+    for (uint i = n-k+1, j = 1; i < n; ++i, ++j) {
+      rgs_[i] = j;
+      value_[j].push_back(i);
+    }
+    for (uint i = 1; i <= n; i++)
+      max_[i] = rgs_[i-1] + 1;
+    update_value();
+  }
+
+  // Used for creating an end iterator
+  Set_partition_iterator() : is_end_(true), n_(0), k_(0) {}
+
+  void reinitialize() {
+    if (n_ > 0)
+      is_end_ = false;
+    for (uint i = 0; i <= n_-k_; ++i)
+      rgs_[i] = 0;
+    for (uint i = n_-k_+1, j = 1; i < n_; ++i, ++j)
+      rgs_[i] = j;
+    for (uint i = 1; i <= n_; i++)
+      max_[i] = rgs_[i-1] + 1;
+    update_value();
+  }
+  
+protected:
+  value_t value_;         // the dereference value
+  std::vector<uint> rgs_; // restricted growth string
+  std::vector<uint> max_; // max_[i] = max(rgs_[0],...,rgs[i-1]) + 1
+  bool is_end_;   // is true when the current permutation is the final one 
+
+  uint n_;
+  uint k_;
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Simplex_comparator.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Simplex_comparator.h
new file mode 100644
index 00000000..5b3c29e9
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Simplex_comparator.h
@@ -0,0 +1,64 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_SIMPLEX_COMPARATOR_H_
+#define PERMUTAHEDRAL_REPRESENTATION_SIMPLEX_COMPARATOR_H_
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+/** \class Simplex_comparator 
+ *  \brief A comparator class for Permutahedral_representation.
+ *   The comparison is in lexicographic order first on
+ *   vertices and then on ordered partitions with sorted parts.
+ *   The lexicographic order forces that any face is larger than
+ *   a coface.
+ *
+ *  \tparam Permutahdral_representation_ Needs to be 
+ *   Permutahedral_representation<Vertex_, Ordered_set_partition_>
+ *
+ *  \ingroup coxeter_triangulation
+ */
+template <class Permutahedral_representation_>
+struct Simplex_comparator {
+
+  /** \brief Comparison between two permutahedral representations.
+   *  Both permutahedral representations need to be valid and
+   *  the vertices of both permutahedral representations need to be of the same size.
+   */
+  bool operator() (const Permutahedral_representation_& lhs,
+		   const Permutahedral_representation_& rhs) const {
+    if (lhs.vertex() < rhs.vertex())
+      return true;
+    if (lhs.vertex() > rhs.vertex())
+      return false;
+    
+    if (lhs.partition().size() > rhs.partition().size())
+      return true;
+    if (lhs.partition().size() < rhs.partition().size())
+      return false;
+    
+    if (lhs.partition() < rhs.partition())
+      return true;
+    if (lhs.partition() > rhs.partition())
+      return false;
+    
+    return false;
+  }
+};
+
+} // namespace coxeter_triangulation 
+
+} // namespace Gudhi
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h
new file mode 100644
index 00000000..dd9c20dc
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h
@@ -0,0 +1,89 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_SIZE_RANGE_H_
+#define PERMUTAHEDRAL_REPRESENTATION_SIZE_RANGE_H_
+
+#include <boost/range/iterator_range.hpp>
+#include <cstdlib>         // std::size_t
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+/** \brief Auxillary iterator class for sizes of parts in an ordered set partition.
+ */
+template <class T_it>
+class Size_iterator : public boost::iterator_facade< Size_iterator<T_it>,
+						     std::size_t const,
+						     boost::forward_traversal_tag> {
+  friend class boost::iterator_core_access;
+
+protected:
+  bool equal(Size_iterator const& other) const {
+    return (is_end_ && other.is_end_);
+  }
+
+  std::size_t const& dereference() const {
+    return value_;
+  }
+
+  void increment() {
+    if (++t_it_ == t_end_) {
+      is_end_ = true;
+      return;
+    }
+    value_ = t_it_->size()-1;
+  }
+
+public:
+
+  Size_iterator(const T_it& t_begin, const T_it& t_end)
+    : t_it_(t_begin), t_end_(t_end), is_end_(t_begin == t_end) {
+    if (!is_end_)
+      value_ = t_it_->size()-1;
+  }
+
+protected:
+  T_it t_it_, t_end_;
+  bool is_end_;
+  std::size_t value_;
+};
+
+template <class T>
+class Size_range {
+  const T& t_;
+
+public:
+  typedef Size_iterator<typename T::const_iterator> iterator;
+  
+  Size_range(const T& t) : t_(t) {}
+  
+  std::size_t operator[](std::size_t i) const {
+    return t_[i].size()-1;
+  }
+
+  iterator begin() const {
+    return iterator(t_.begin(), t_.end());
+  }
+
+  iterator end() const {
+    return iterator(t_.end(), t_.end());
+  }
+
+};
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+#endif
diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/face_from_indices.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/face_from_indices.h
new file mode 100644
index 00000000..461a01e7
--- /dev/null
+++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/face_from_indices.h
@@ -0,0 +1,71 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PERMUTAHEDRAL_REPRESENTATION_FACE_FROM_INDICES_H_
+#define PERMUTAHEDRAL_REPRESENTATION_FACE_FROM_INDICES_H_
+
+namespace Gudhi {
+
+namespace coxeter_triangulation {
+
+ /** \brief Computes the permutahedral representation of a face of a given simplex
+  *  and a range of the vertex indices that compose the face.
+  *
+  * \tparam Permutahedral_representation has to be Permutahedral_representation
+  * \tparam Index_range is a range of unsigned integers taking values in 0,...,k,
+  * where k is the dimension of the simplex simplex.
+  *
+  * @param[in] simplex Input simplex.
+  * @param[in] indices Input range of indices.
+  */
+template <class Permutahedral_representation,
+	  class Index_range>
+Permutahedral_representation face_from_indices(const Permutahedral_representation& simplex,
+					       const Index_range& indices) {
+  using range_index = typename Index_range::value_type;
+  using Ordered_set_partition = typename Permutahedral_representation::OrderedSetPartition;
+  using Part = typename Ordered_set_partition::value_type;
+  using part_index = typename Part::value_type;
+  Permutahedral_representation value;
+  std::size_t d = simplex.vertex().size();
+  value.vertex() = simplex.vertex();
+  std::size_t k = indices.size()-1;
+  value.partition().resize(k+1);
+  std::size_t l = simplex.partition().size()-1;
+  for (std::size_t h = 1; h < k+1; h++)
+    for (range_index i = indices[h-1]; i < indices[h]; i++)
+      for (part_index j: simplex.partition()[i])
+	value.partition()[h-1].push_back(j);
+  for (range_index i = indices[k]; i < l+1; i++)
+    for (part_index j: simplex.partition()[i])
+      value.partition()[k].push_back(j);
+  for (range_index i = 0; i < indices[0]; i++)
+    for (part_index j: simplex.partition()[i]) {
+      if (j != d)
+	value.vertex()[j]++;
+      else
+	for (std::size_t l = 0; l < d; l++)
+	  value.vertex()[l]--;
+      value.partition()[k].push_back(j);
+    }
+  // sort the values in each part (probably not needed)
+  for (auto& part: value.partition())
+    std::sort(part.begin(), part.end());
+  return value;
+}
+
+} // namespace coxeter_triangulation
+
+} // namespace Gudhi
+
+
+#endif