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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===-- llvm/ADT/CombinationGenerator.h ------------------------*- C++ -*--===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Combination generator.
///
/// Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following
/// combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}.
///
/// It is useful to think of input as vector-of-vectors, where the
/// outer vector is the variable space, and inner vector is choice space.
/// The number of choices for each variable can be different.
///
/// As for implementation, it is useful to think of this as a weird number,
/// where each digit (==variable) may have different base (==number of choices).
/// Thus modelling of 'produce next combination' is exactly analogous to the
/// incrementing of an number - increment lowest digit (pick next choice for the
/// variable), and if it wrapped to the beginning then increment next digit.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_COMBINATIONGENERATOR_H
#define LLVM_ADT_COMBINATIONGENERATOR_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallVector.h"
#include <cassert>
#include <cstring>
namespace llvm {
template <typename choice_type, typename choices_storage_type,
int variable_smallsize>
class CombinationGenerator {
template <typename T> struct WrappingIterator {
using value_type = T;
const ArrayRef<value_type> Range;
typename decltype(Range)::const_iterator Position;
// Rewind the tape, placing the position to again point at the beginning.
void rewind() { Position = Range.begin(); }
// Advance position forward, possibly wrapping to the beginning.
// Returns whether the wrap happened.
bool advance() {
++Position;
bool Wrapped = Position == Range.end();
if (Wrapped)
rewind();
return Wrapped;
}
// Get the value at which we are currently pointing.
const value_type &operator*() const { return *Position; }
WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) {
assert(!Range.empty() && "The range must not be empty.");
rewind();
}
};
const ArrayRef<choices_storage_type> VariablesChoices;
void performGeneration(
const function_ref<bool(ArrayRef<choice_type>)> Callback) const {
SmallVector<WrappingIterator<choice_type>, variable_smallsize>
VariablesState;
// 'increment' of the the whole VariablesState is defined identically to the
// increment of a number: starting from the least significant element,
// increment it, and if it wrapped, then propagate that carry by also
// incrementing next (more significant) element.
auto IncrementState =
[](MutableArrayRef<WrappingIterator<choice_type>> VariablesState)
-> bool {
for (WrappingIterator<choice_type> &Variable :
llvm::reverse(VariablesState)) {
bool Wrapped = Variable.advance();
if (!Wrapped)
return false; // There you go, next combination is ready.
// We have carry - increment more significant variable next..
}
return true; // MSB variable wrapped, no more unique combinations.
};
// Initialize the per-variable state to refer to the possible choices for
// that variable.
VariablesState.reserve(VariablesChoices.size());
for (ArrayRef<choice_type> VC : VariablesChoices)
VariablesState.emplace_back(VC);
// Temporary buffer to store each combination before performing Callback.
SmallVector<choice_type, variable_smallsize> CurrentCombination;
CurrentCombination.resize(VariablesState.size());
while (true) {
// Gather the currently-selected variable choices into a vector.
for (auto I : llvm::zip(VariablesState, CurrentCombination))
std::get<1>(I) = *std::get<0>(I);
// And pass the new combination into callback, as intended.
if (/*Abort=*/Callback(CurrentCombination))
return;
// And tick the state to next combination, which will be unique.
if (IncrementState(VariablesState))
return; // All combinations produced.
}
};
public:
CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_)
: VariablesChoices(VariablesChoices_) {
#ifndef NDEBUG
assert(!VariablesChoices.empty() && "There should be some variables.");
llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) {
assert(!VariableChoices.empty() &&
"There must always be some choice, at least a placeholder one.");
});
#endif
}
// How many combinations can we produce, max?
// This is at most how many times the callback will be called.
size_t numCombinations() const {
size_t NumVariants = 1;
for (ArrayRef<choice_type> VariableChoices : VariablesChoices)
NumVariants *= VariableChoices.size();
assert(NumVariants >= 1 &&
"We should always end up producing at least one combination");
return NumVariants;
}
// Actually perform exhaustive combination generation.
// Each result will be passed into the callback.
void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) {
performGeneration(Callback);
}
};
} // namespace llvm
#endif
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
