Loading...
Searching...
No Matches
Permutahedral_representation_iterators.h
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Siargey Kachanovich
4 *
5 * Copyright (C) 2019 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef PERMUTAHEDRAL_REPRESENTATION_PERMUTAHEDRAL_REPRESENTATION_ITERATORS_H_
12#define PERMUTAHEDRAL_REPRESENTATION_PERMUTAHEDRAL_REPRESENTATION_ITERATORS_H_
13
14#include <gudhi/Permutahedral_representation/Size_range.h>
15#include <gudhi/Permutahedral_representation/Ordered_set_partition_iterator.h>
16#include <gudhi/Permutahedral_representation/Integer_combination_iterator.h>
17#include <gudhi/Permutahedral_representation/Combination_iterator.h>
18#include <gudhi/Permutahedral_representation/face_from_indices.h>
19#include <boost/iterator/iterator_facade.hpp>
20
21#include <vector>
22#include <iostream>
23#include <algorithm> // for std::find
24
25namespace Gudhi {
26
27namespace coxeter_triangulation {
28
38template <class Permutahedral_representation>
40 : public boost::iterator_facade<Vertex_iterator<Permutahedral_representation>,
41 typename Permutahedral_representation::Vertex const, boost::forward_traversal_tag> {
42 private:
43 friend class boost::iterator_core_access;
44
45 using Vertex = typename Permutahedral_representation::Vertex;
46 using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
47
48 using value_t = Vertex;
49
50 bool equal(Vertex_iterator const& other) const { return (is_end_ && other.is_end_); }
51
52 value_t const& dereference() const { return value_; }
53
54 void update_value() {
55 std::size_t d = value_.size();
56 for (auto i : *o_it_)
57 if (i != d)
58 value_[i]++;
59 else
60 for (std::size_t j = 0; j < d; j++) value_[j]--;
61 }
62
63 void increment() {
64 if (is_end_) return;
65 update_value();
66 if (++o_it_ == o_end_) is_end_ = true;
67 }
68
69 public:
71 : o_it_(simplex.partition().begin()),
72 o_end_(simplex.partition().end()),
73 value_(simplex.vertex()),
74 is_end_(o_it_ == o_end_) {}
75
76 Vertex_iterator() : is_end_(true) {}
77
78 private:
79 typename Ordered_partition::const_iterator o_it_, o_end_;
80 value_t value_;
81 bool is_end_;
82
83}; // Vertex_iterator
84
85/*---------------------------------------------------------------------------*/
90template <class Permutahedral_representation>
91class Face_iterator : public boost::iterator_facade<Face_iterator<Permutahedral_representation>,
92 Permutahedral_representation const, boost::forward_traversal_tag> {
94
95 private:
96 friend class boost::iterator_core_access;
97
98 using Vertex = typename Permutahedral_representation::Vertex;
99 using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
100
101 bool equal(Face_iterator const& other) const { return (is_end_ && other.is_end_); }
102
103 value_t const& dereference() const { return value_; }
104
105 void increment() {
106 if (++c_it_ == c_end_) {
107 is_end_ = true;
108 return;
109 }
110 update_value();
111 }
112
113 void update_value() {
114 // Combination *c_it_ is supposed to be sorted in increasing order
115 value_ = face_from_indices<Permutahedral_representation>(simplex_, *c_it_);
116 }
117
118 public:
119 Face_iterator(const Permutahedral_representation& simplex, const uint& k)
120 : simplex_(simplex),
121 k_(k),
122 l_(simplex.dimension()),
123 c_it_(l_ + 1, k_ + 1),
124 is_end_(k_ > l_),
125 value_({Vertex(simplex.vertex().size()), Ordered_partition(k + 1)}) {
126 update_value();
127 }
128
129 // Used for the creating an end iterator
130 Face_iterator() : is_end_(true) {}
131
132 private:
133 Permutahedral_representation simplex_; // Input simplex
134 uint k_;
135 uint l_; // Dimension of the input simplex
136 Combination_iterator c_it_, c_end_; // indicates the vertices in the current face
137
138 bool is_end_; // is true when the current permutation is the final one
139 value_t value_; // the dereference value
140
141}; // Face_iterator
142
143/*---------------------------------------------------------------------------*/
148template <class Permutahedral_representation>
150 : public boost::iterator_facade<Coface_iterator<Permutahedral_representation>, Permutahedral_representation const,
151 boost::forward_traversal_tag> {
153
154 private:
155 friend class boost::iterator_core_access;
156
157 using Vertex = typename Permutahedral_representation::Vertex;
158 using Ordered_partition = typename Permutahedral_representation::OrderedSetPartition;
159
160 bool equal(Coface_iterator const& other) const { return (is_end_ && other.is_end_); }
161
162 value_t const& dereference() const { return value_; }
163
164 void increment() {
165 uint i = 0;
166 for (; i < k_ + 1; i++) {
167 if (++(o_its_[i]) != o_end_) break;
168 }
169 if (i == k_ + 1) {
170 if (++i_it_ == i_end_) {
171 is_end_ = true;
172 return;
173 }
174 o_its_.clear();
175 for (uint j = 0; j < k_ + 1; j++)
176 o_its_.emplace_back(simplex_.partition()[j].size(), (*i_it_)[j] + 1);
177 } else
178 for (uint j = 0; j < i; j++) o_its_[j].reinitialize();
179 update_value();
180 }
181
182 void update_value() {
183 value_.vertex() = simplex_.vertex();
184 for (auto& p : value_.partition()) p.clear();
185 uint u_ = 0; // the part in o_its_[k_] that contains t_
186 for (; u_ <= (*i_it_)[k_]; u_++) {
187 auto range = (*o_its_[k_])[u_];
188 if (std::find(range.begin(), range.end(), t_) != range.end()) break;
189 }
190 uint i = 0;
191 for (uint j = u_ + 1; j <= (*i_it_)[k_]; j++, i++)
192 for (uint b : (*o_its_[k_])[j]) {
193 uint c = simplex_.partition()[k_][b];
194 value_.partition()[i].push_back(c);
195 value_.vertex()[c]--;
196 }
197 for (uint h = 0; h < k_; h++)
198 for (uint j = 0; j <= (*i_it_)[h]; j++, i++) {
199 for (uint b : (*o_its_[h])[j]) value_.partition()[i].push_back(simplex_.partition()[h][b]);
200 }
201 for (uint j = 0; j <= u_; j++, i++)
202 for (uint b : (*o_its_[k_])[j]) value_.partition()[i].push_back(simplex_.partition()[k_][b]);
203 // sort the values in each part (probably not needed)
204 for (auto& part : value_.partition()) std::sort(part.begin(), part.end());
205 }
206
207 public:
208 Coface_iterator(const Permutahedral_representation& simplex, const uint& l)
209 : simplex_(simplex),
210 d_(simplex.vertex().size()),
211 l_(l),
212 k_(simplex.dimension()),
213 i_it_(l_ - k_, k_ + 1, Size_range<Ordered_partition>(simplex.partition())),
214 is_end_(k_ > l_),
215 value_({Vertex(d_), Ordered_partition(l_ + 1)}) {
216 uint j = 0;
217 for (; j < simplex_.partition()[k_].size(); j++)
218 if (simplex_.partition()[k_][j] == d_) {
219 t_ = j;
220 break;
221 }
222 if (j == simplex_.partition()[k_].size()) {
223 std::cerr << "Coface iterator: the argument simplex is not a permutahedral representation\n";
224 is_end_ = true;
225 return;
226 }
227 for (uint i = 0; i < k_ + 1; i++)
228 o_its_.emplace_back(simplex_.partition()[i].size(), (*i_it_)[i] + 1);
229 update_value();
230 }
231
232 // Used for the creating an end iterator
233 Coface_iterator() : is_end_(true) {}
234
235 private:
236 Permutahedral_representation simplex_; // Input simplex
237 uint d_; // Ambient dimension
238 uint l_; // Dimension of the coface
239 uint k_; // Dimension of the input simplex
240 uint t_; // The position of d in simplex_.partition()[k_]
241 Integer_combination_iterator i_it_, i_end_; // indicates in how many parts each simplex_[i] is subdivided
242 std::vector<Ordered_set_partition_iterator> o_its_; // indicates subdivision for each simplex_[i]
243 Ordered_set_partition_iterator o_end_; // one end for all o_its_
244
245 bool is_end_; // is true when the current permutation is the final one
246 value_t value_; // the dereference value
247
248}; // Coface_iterator
249
252} // namespace coxeter_triangulation
253
254} // namespace Gudhi
255
256#endif
Iterator over the k-cofaces of a simplex given by its permutahedral representation.
Definition: Permutahedral_representation_iterators.h:151
Class that allows the user to generate combinations of k elements in a set of n elements....
Definition: Combination_iterator.h:28
Iterator over the k-faces of a simplex given by its permutahedral representation.
Definition: Permutahedral_representation_iterators.h:92
Class that allows the user to generate combinations of k elements in a set of n elements....
Definition: Integer_combination_iterator.h:29
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
A class that stores the permutahedral representation of a simplex in a Coxeter triangulation or a Fre...
Definition: Permutahedral_representation.h:38
Vertex & vertex()
Lexicographically-minimal vertex.
Definition: Permutahedral_representation.h:68
std::size_t dimension() const
Dimension of the simplex.
Definition: Permutahedral_representation.h:65
OrderedSetPartition & partition()
Ordered set partition.
Definition: Permutahedral_representation.h:74
Ordered_set_partition_ OrderedSetPartition
Type of the ordered partition.
Definition: Permutahedral_representation.h:46
Vertex_ Vertex
Type of the vertex.
Definition: Permutahedral_representation.h:43
Iterator over the vertices of a simplex represented by its permutahedral representation.
Definition: Permutahedral_representation_iterators.h:41