LLVM  15.0.0git
CombinationGenerator.h
Go to the documentation of this file.
1 //===-- llvm/ADT/CombinationGenerator.h ------------------------*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// Combination generator.
11 ///
12 /// Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following
13 /// combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}.
14 ///
15 /// It is useful to think of input as vector-of-vectors, where the
16 /// outer vector is the variable space, and inner vector is choice space.
17 /// The number of choices for each variable can be different.
18 ///
19 /// As for implementation, it is useful to think of this as a weird number,
20 /// where each digit (==variable) may have different base (==number of choices).
21 /// Thus modelling of 'produce next combination' is exactly analogous to the
22 /// incrementing of an number - increment lowest digit (pick next choice for the
23 /// variable), and if it wrapped to the beginning then increment next digit.
24 ///
25 //===----------------------------------------------------------------------===//
26 
27 #ifndef LLVM_ADT_COMBINATIONGENERATOR_H
28 #define LLVM_ADT_COMBINATIONGENERATOR_H
29 
30 #include "llvm/ADT/ArrayRef.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include <cassert>
34 #include <cstring>
35 
36 namespace llvm {
37 
38 template <typename choice_type, typename choices_storage_type,
39  int variable_smallsize>
41  template <typename T> struct WrappingIterator {
42  using value_type = T;
43 
44  const ArrayRef<value_type> Range;
45  typename decltype(Range)::const_iterator Position;
46 
47  // Rewind the tape, placing the position to again point at the beginning.
48  void rewind() { Position = Range.begin(); }
49 
50  // Advance position forward, possibly wrapping to the beginning.
51  // Returns whether the wrap happened.
52  bool advance() {
53  ++Position;
54  bool Wrapped = Position == Range.end();
55  if (Wrapped)
56  rewind();
57  return Wrapped;
58  }
59 
60  // Get the value at which we are currently pointing.
61  const value_type &operator*() const { return *Position; }
62 
63  WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) {
64  assert(!Range.empty() && "The range must not be empty.");
65  rewind();
66  }
67  };
68 
69  const ArrayRef<choices_storage_type> VariablesChoices;
70 
71  void performGeneration(
72  const function_ref<bool(ArrayRef<choice_type>)> Callback) const {
74  VariablesState;
75 
76  // 'increment' of the the whole VariablesState is defined identically to the
77  // increment of a number: starting from the least significant element,
78  // increment it, and if it wrapped, then propagate that carry by also
79  // incrementing next (more significant) element.
80  auto IncrementState =
82  -> bool {
83  for (WrappingIterator<choice_type> &Variable :
84  llvm::reverse(VariablesState)) {
85  bool Wrapped = Variable.advance();
86  if (!Wrapped)
87  return false; // There you go, next combination is ready.
88  // We have carry - increment more significant variable next..
89  }
90  return true; // MSB variable wrapped, no more unique combinations.
91  };
92 
93  // Initialize the per-variable state to refer to the possible choices for
94  // that variable.
95  VariablesState.reserve(VariablesChoices.size());
96  for (ArrayRef<choice_type> VC : VariablesChoices)
97  VariablesState.emplace_back(VC);
98 
99  // Temporary buffer to store each combination before performing Callback.
101  CurrentCombination.resize(VariablesState.size());
102 
103  while (true) {
104  // Gather the currently-selected variable choices into a vector.
105  for (auto I : llvm::zip(VariablesState, CurrentCombination))
106  std::get<1>(I) = *std::get<0>(I);
107  // And pass the new combination into callback, as intended.
108  if (/*Abort=*/Callback(CurrentCombination))
109  return;
110  // And tick the state to next combination, which will be unique.
111  if (IncrementState(VariablesState))
112  return; // All combinations produced.
113  }
114  };
115 
116 public:
118  : VariablesChoices(VariablesChoices_) {
119 #ifndef NDEBUG
120  assert(!VariablesChoices.empty() && "There should be some variables.");
121  llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) {
122  assert(!VariableChoices.empty() &&
123  "There must always be some choice, at least a placeholder one.");
124  });
125 #endif
126  }
127 
128  // How many combinations can we produce, max?
129  // This is at most how many times the callback will be called.
130  size_t numCombinations() const {
131  size_t NumVariants = 1;
132  for (ArrayRef<choice_type> VariableChoices : VariablesChoices)
133  NumVariants *= VariableChoices.size();
134  assert(NumVariants >= 1 &&
135  "We should always end up producing at least one combination");
136  return NumVariants;
137  }
138 
139  // Actually perform exhaustive combination generation.
140  // Each result will be passed into the callback.
141  void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) {
142  performGeneration(Callback);
143  }
144 };
145 
146 } // namespace llvm
147 
148 #endif
const_iterator
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
llvm::AArch64CC::VC
@ VC
Definition: AArch64BaseInfo.h:262
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:306
llvm::CombinationGenerator::generate
void generate(const function_ref< bool(ArrayRef< choice_type >)> Callback)
Definition: CombinationGenerator.h:141
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
STLFunctionalExtras.h
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1600
I
#define I(x, y, z)
Definition: MD5.cpp:58
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CombinationGenerator::numCombinations
size_t numCombinations() const
Definition: CombinationGenerator.h:130
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:766
llvm::CombinationGenerator
Definition: CombinationGenerator.h:40
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2126
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
SmallVector.h
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::CombinationGenerator::CombinationGenerator
CombinationGenerator(ArrayRef< choices_storage_type > VariablesChoices_)
Definition: CombinationGenerator.h:117