Loading...
Searching...
No Matches
Permutahedral_representation_iterators.h
/* 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 {
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
/*---------------------------------------------------------------------------*/
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
/*---------------------------------------------------------------------------*/
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
Gudhi::coxeter_triangulation::Combination_iterator
Class that allows the user to generate combinations of k elements in a set of n elements....
Definition Combination_iterator.h:28
Gudhi::coxeter_triangulation::Integer_combination_iterator
Class that allows the user to generate combinations of k elements in a set of n elements....
Definition Integer_combination_iterator.h:29
Gudhi::coxeter_triangulation::Ordered_set_partition_iterator
Class that allows the user to generate set partitions of a set {0,...,n-1} in k parts.
Definition Ordered_set_partition_iterator.h:49
Gudhi::coxeter_triangulation::Permutahedral_representation
A class that stores the permutahedral representation of a simplex in a Coxeter triangulation or a Fre...
Definition Permutahedral_representation.h:38
Gudhi::coxeter_triangulation::Permutahedral_representation::vertex
Vertex & vertex()
Lexicographically-minimal vertex.
Definition Permutahedral_representation.h:68
Gudhi::coxeter_triangulation::Permutahedral_representation::dimension
std::size_t dimension() const
Dimension of the simplex.
Definition Permutahedral_representation.h:65
Gudhi::coxeter_triangulation::Permutahedral_representation::partition
OrderedSetPartition & partition()
Ordered set partition.
Definition Permutahedral_representation.h:74
Gudhi::coxeter_triangulation::Permutahedral_representation::OrderedSetPartition
Ordered_set_partition_ OrderedSetPartition
Type of the ordered partition.
Definition Permutahedral_representation.h:46
Gudhi::coxeter_triangulation::Permutahedral_representation::Vertex
Vertex_ Vertex
Type of the vertex.
Definition Permutahedral_representation.h:43
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14