diff options
Diffstat (limited to 'src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h')
-rw-r--r-- | src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h | 254 |
1 files changed, 254 insertions, 0 deletions
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..db145741 --- /dev/null +++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Permutahedral_representation_iterators.h @@ -0,0 +1,254 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * 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> // for std::find + +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> { + private: + friend class boost::iterator_core_access; + + using Vertex = typename Permutahedral_representation::Vertex; + using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition; + + using value_t = Vertex; + + 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) {} + + private: + 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> { + using value_t = Permutahedral_representation; + + private: + 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) {} + + private: + 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> { + using value_t = Permutahedral_representation; + + private: + 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(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(simplex_.partition()[i].size(), (*i_it_)[i] + 1); + update_value(); + } + + // Used for the creating an end iterator + Coface_iterator() : is_end_(true) {} + + private: + 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 |