This repository was archived by the owner on Oct 29, 2020. It is now read-only.
forked from ryanhaining/cppitertools
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpermutations.hpp
More file actions
105 lines (86 loc) · 2.48 KB
/
Copy pathpermutations.hpp
File metadata and controls
105 lines (86 loc) · 2.48 KB
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
#ifndef ITER_PERMUTATIONS_HPP_
#define ITER_PERMUTATIONS_HPP_
#include "internal/iterator_wrapper.hpp"
#include "internal/iteratoriterator.hpp"
#include "internal/iterbase.hpp"
#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <utility>
#include <vector>
namespace iter {
namespace impl {
template <typename Container>
class Permuter;
using PermutationsFn = IterToolFn<Permuter>;
}
constexpr impl::PermutationsFn permutations{};
}
template <typename Container>
class iter::impl::Permuter {
private:
friend PermutationsFn;
Container container_;
using IndexVector = std::vector<IteratorWrapper<Container>>;
using Permutable = IterIterWrapper<IndexVector>;
Permuter(Container&& container)
: container_(std::forward<Container>(container)) {}
public:
Permuter(Permuter&&) = default;
class Iterator : public std::iterator<std::input_iterator_tag, Permutable> {
private:
static constexpr const int COMPLETE = -1;
static bool cmp_iters(IteratorWrapper<Container> lhs,
IteratorWrapper<Container> rhs) noexcept {
return *lhs < *rhs;
}
Permutable working_set_;
int steps_{};
public:
Iterator(IteratorWrapper<Container>&& sub_iter,
IteratorWrapper<Container>&& sub_end)
: steps_{sub_iter != sub_end ? 0 : COMPLETE} {
// done like this instead of using vector ctor with
// two iterators because that causes a substitution
// failure when the iterator is minimal
while (sub_iter != sub_end) {
working_set_.get().push_back(sub_iter);
++sub_iter;
}
std::sort(get_begin(working_set_.get()), get_end(working_set_.get()),
cmp_iters);
}
Permutable& operator*() {
return working_set_;
}
Permutable* operator->() {
return &working_set_;
}
Iterator& operator++() {
++steps_;
if (!std::next_permutation(get_begin(working_set_.get()),
get_end(working_set_.get()), cmp_iters)) {
steps_ = COMPLETE;
}
return *this;
}
Iterator operator++(int) {
auto ret = *this;
++*this;
return ret;
}
bool operator!=(const Iterator& other) const {
return !(*this == other);
}
bool operator==(const Iterator& other) const {
return steps_ == other.steps_;
}
};
Iterator begin() {
return {get_begin(container_), get_end(container_)};
}
Iterator end() {
return {get_end(container_), get_end(container_)};
}
};
#endif