forked from ryanhaining/cppitertools
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcombinations.hpp
More file actions
111 lines (102 loc) · 3.83 KB
/
combinations.hpp
File metadata and controls
111 lines (102 loc) · 3.83 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
106
107
108
109
110
111
#ifndef COMBINATIONS_HPP
#define COMBINATIONS_HPP
#include "iterator_range.hpp"
#include <array>
#include <vector>
#include <type_traits>
#include <iterator>
#include <iostream>
namespace iter {
//Could try having antoher template for container to return (right now it's
//just an std::vector)
template <typename Container>
struct combinations_iter;
template <typename Container>
iterator_range<combinations_iter<Container>>
combinations(const Container & container, size_t N) {
auto begin = combinations_iter<Container>(container,N);
auto end = combinations_iter<Container>(container,N);
return
iterator_range<combinations_iter<Container>>(begin,end);
}
template <typename Container>
struct combinations_iter
{
private:
const Container & items;
std::vector<decltype(items.cbegin())> indicies;
bool not_done = true;
public:
//Holy shit look at this typedef
using item_t = typename
std::remove_const<
typename std::remove_reference<decltype(items.front())>::type>::type;
combinations_iter(const Container & i, size_t N) :
items(i),indicies(N)
{
if (N == 0) {
not_done = false;
return;
}
size_t inc = 0;
for (auto & iter : indicies) {
if (items.cbegin() + inc != items.cend()) {
iter = items.cbegin()+inc;
++inc;
}
else {
not_done = false;
break;
}
}
}
std::vector<item_t> operator*() const
{
std::vector<item_t> values;
for (auto i : indicies) {
values.push_back(*i);
}
return values;
}
combinations_iter &
operator++()
{
for (auto iter = indicies.rbegin(); iter != indicies.rend(); ++iter) {
++(*iter);
//what we have to check here is if the distance between the
//index and the end of indicies is >= the distance between
//the item and end of item
if ((*iter + std::distance(indicies.rbegin(),iter)) ==
items.cend()) {
if ( (iter + 1) != indicies.rend()) {
size_t inc = 1;
for (auto down = iter; down != indicies.rbegin()-1;--down) {
(*down) = (*(iter + 1)) + 1 + inc;
/*if (*down == items.cend()) {
iter = iter + 1;
}*/
++inc;
}
}
else {
not_done = false;
break;
}
}
else break;
//we break because none of the rest of the items need to
//be incremented
}
return *this;
}
bool operator !=(const combinations_iter &)
{
//because of the way this is done you have to start from the
//begining of the range and end at the end, you could break in
//the middle of the loop though, it's not different from the way
//that python's works
return not_done;
}
};
}
#endif //COMBINATIONS_HPP