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
102
103
104
105
106
107
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
|
