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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#ifndef PYTHONIC_ITERTOOLS_COMBINATIONS_HPP
#define PYTHONIC_ITERTOOLS_COMBINATIONS_HPP
#include "pythonic/include/itertools/combinations.hpp"
#include "pythonic/types/dynamic_tuple.hpp"
#include "pythonic/utils/functor.hpp"
#include <numeric>
PYTHONIC_NS_BEGIN
namespace itertools
{
namespace details
{
template <class T>
template <class Iter>
combination_iterator<T>::combination_iterator(Iter &&pool, long r)
: pool(pool.begin(), pool.end()), indices(r), r(r),
stopped(r > long(this->pool.size()))
{
assert(r >= 0 && "r must be non-negative");
if (!stopped) {
std::iota(indices.begin(), indices.end(), 0);
result.insert(result.end(), this->pool.begin(), this->pool.begin() + r);
}
}
template <class T>
combination_iterator<T>::combination_iterator(bool) : stopped(true)
{
}
template <class T>
types::dynamic_tuple<typename T::value_type>
combination_iterator<T>::operator*() const
{
assert(!stopped && "! stopped");
return {result.begin(), result.end()};
}
template <class T>
combination_iterator<T> &combination_iterator<T>::operator++()
{
/* Scan indices right-to-left until finding one that is !
at its maximum (i + n - r). */
long i, n = pool.size();
for (i = r - 1; i >= 0 && indices[i] == i + n - r; i--)
;
/* If i is negative, then the indices are all at
their maximum value && we're done. */
if (i < 0)
stopped = true;
else {
/* Increment the current index which we know is ! at its
maximum. Then move back to the right setting each index
to its lowest possible value (one higher than the index
to its left -- this maintains the sort order invariant). */
indices[i]++;
for (long j = i + 1; j < r; j++)
indices[j] = indices[j - 1] + 1;
/* Update the result tuple for the new indices
starting with i, the leftmost index that changed */
for (; i < r; i++) {
result[i] = pool[indices[i]];
}
}
return *this;
}
template <class T>
bool
combination_iterator<T>::operator!=(combination_iterator const &other) const
{
assert(stopped || other.stopped);
return !(*this == other);
}
template <class T>
bool
combination_iterator<T>::operator==(combination_iterator const &other) const
{
assert(stopped || other.stopped);
return other.stopped == stopped;
}
template <class T>
bool
combination_iterator<T>::operator<(combination_iterator const &other) const
{
return stopped != other.stopped;
}
template <class T>
template <class Iter>
combination<T>::combination(Iter &&iter, long elts)
: iterator(std::forward<Iter>(iter), elts), num_elts(elts)
{
}
template <class T>
typename combination<T>::iterator const &combination<T>::begin() const
{
return *this;
}
template <class T>
typename combination<T>::iterator combination<T>::begin()
{
return *this;
}
template <class T>
typename combination<T>::iterator combination<T>::end() const
{
return {true};
}
} // namespace details
template <typename T0>
details::combination<
typename std::remove_cv<typename std::remove_reference<T0>::type>::type>
combinations(T0 &&iter, long num_elts)
{
return {std::forward<T0>(iter), num_elts};
}
} // namespace itertools
PYTHONIC_NS_END
#endif
|
