blob: 20a4a8ff9b916054abbb33616f7ab9893d9ceb64 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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
|
