| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // This file is part of INSTINCT, the INS Toolkit for Integrated | ||
| 2 | // Navigation Concepts and Training by the Institute of Navigation of | ||
| 3 | // the University of Stuttgart, Germany. | ||
| 4 | // | ||
| 5 | // This Source Code Form is subject to the terms of the Mozilla Public | ||
| 6 | // License, v. 2.0. If a copy of the MPL was not distributed with this | ||
| 7 | // file, You can obtain one at https://mozilla.org/MPL/2.0/. | ||
| 8 | |||
| 9 | /// @file CartesianProduct.hpp | ||
| 10 | /// @brief Algorithm iterating all combinations of a list | ||
| 11 | /// @author T. Topp (topp@ins.uni-stuttgart.de) | ||
| 12 | /// @date 2022-11-04 | ||
| 13 | /// | ||
| 14 | /// @note Original code by Jonathan Boccara from https://www.fluentcpp.com/2022/03/18/how-to-generate-all-the-combinations-from-several-collections/ | ||
| 15 | |||
| 16 | #pragma once | ||
| 17 | |||
| 18 | #include <algorithm> | ||
| 19 | #include <iostream> | ||
| 20 | #include <iterator> | ||
| 21 | #include <functional> | ||
| 22 | #include <string> | ||
| 23 | #include <type_traits> | ||
| 24 | #include <utility> | ||
| 25 | #include <vector> | ||
| 26 | #include <numeric> | ||
| 27 | |||
| 28 | namespace NAV | ||
| 29 | { | ||
| 30 | namespace CartesianProduct | ||
| 31 | { | ||
| 32 | |||
| 33 | namespace tuple_algos | ||
| 34 | { | ||
| 35 | |||
| 36 | /// @brief For-each implementation for tuples | ||
| 37 | /// @param[in] t The tuple | ||
| 38 | /// @param[in] f Function to call | ||
| 39 | template<class Tuple, class F, std::size_t... I> | ||
| 40 | 2 | F for_each_impl(Tuple&& t, F&& f, std::index_sequence<I...> /* seq */) | |
| 41 | { | ||
| 42 | 2 | return (void)std::initializer_list<int>{ (std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))), 0)... }, f; // NOLINT(bugprone-use-after-move,hicpp-invalid-access-moved) | |
| 43 | } | ||
| 44 | |||
| 45 | /// @brief For-each algorithm for tuples | ||
| 46 | /// @param[in] t The tuple | ||
| 47 | /// @param[in] f Function to call | ||
| 48 | /// @return Function return value | ||
| 49 | template<class F, class Tuple> | ||
| 50 | 2 | constexpr decltype(auto) for_each(Tuple&& t, F&& f) | |
| 51 | { | ||
| 52 | 2 | return for_each_impl(std::forward<Tuple>(t), std::forward<F>(f), | |
| 53 | 2 | std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{}); | |
| 54 | } | ||
| 55 | |||
| 56 | /// @brief Transform implementation for tuples | ||
| 57 | /// @param[in] t Tuple | ||
| 58 | /// @param[in] f Function to call | ||
| 59 | /// @return The transformed tuple | ||
| 60 | template<class Tuple, class F, std::size_t... Is> | ||
| 61 | 16 | auto transform_impl(Tuple&& t, F&& f, std::index_sequence<Is...> /* seq */) | |
| 62 | -> decltype(std::make_tuple(std::forward<F>(f)(std::get<Is>(std::forward<Tuple>(t)))...)) | ||
| 63 | { | ||
| 64 | 16 | return std::make_tuple(std::forward<F>(f)(std::get<Is>(std::forward<Tuple>(t)))...); // NOLINT(bugprone-use-after-move,hicpp-invalid-access-moved) | |
| 65 | } | ||
| 66 | |||
| 67 | // Alternative implementation, which however does not compile with msvc | ||
| 68 | // | ||
| 69 | // @brief Transform implementation for tuples | ||
| 70 | // @param[in] inputs Input tuple | ||
| 71 | // @param[in] function Function to call | ||
| 72 | // @return The transformed tuple | ||
| 73 | // template<typename... Ts, typename Function, size_t... Is> | ||
| 74 | // auto transform_impl(std::tuple<Ts...> const& inputs, Function function, std::index_sequence<Is...> /* seq */) | ||
| 75 | // { | ||
| 76 | // return std::tuple<std::result_of_t<Function(Ts)>...>{ function(std::get<Is>(inputs))... }; | ||
| 77 | // } | ||
| 78 | |||
| 79 | /// @brief Transform algorithm for tuples | ||
| 80 | /// @param[in] inputs Input tuple | ||
| 81 | /// @param[in] function Function to call | ||
| 82 | /// @return The transformed tuple | ||
| 83 | template<typename... Ts, typename Function> | ||
| 84 | 16 | auto transform(std::tuple<Ts...> const& inputs, Function function) | |
| 85 | { | ||
| 86 | 16 | return transform_impl(inputs, function, std::make_index_sequence<sizeof...(Ts)>{}); | |
| 87 | } | ||
| 88 | |||
| 89 | /// @brief Find_if for tuples | ||
| 90 | /// @param[in] tuple The tuple to search | ||
| 91 | /// @param[in] pred Predicate to use for finding | ||
| 92 | /// @return Index of the found entry | ||
| 93 | template<typename Tuple, typename Predicate> | ||
| 94 | 2 | size_t find_if(Tuple&& tuple, Predicate pred) | |
| 95 | { | ||
| 96 | 2 | size_t index = std::tuple_size<std::decay_t<Tuple>>::value; | |
| 97 | 2 | size_t currentIndex = 0; | |
| 98 | 2 | bool found = false; | |
| 99 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | for_each(tuple, [&](auto&& value) { |
| 100 |
3/6✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 12 times.
|
12 | if (!found && pred(value)) |
| 101 | { | ||
| 102 | ✗ | ++index = currentIndex; | |
| 103 | ✗ | found = true; | |
| 104 | } | ||
| 105 | 12 | ++currentIndex; | |
| 106 | }); | ||
| 107 | 2 | return index; | |
| 108 | } | ||
| 109 | |||
| 110 | /// @brief Any_of algorithm for tuples | ||
| 111 | /// @param[in] tuple The tuple to search | ||
| 112 | /// @param[in] pred Predicate to check for | ||
| 113 | /// @return True if any of the tuple entries fulfills the predicate | ||
| 114 | template<typename Tuple, typename Predicate> | ||
| 115 | 2 | bool any_of(Tuple&& tuple, Predicate pred) | |
| 116 | { | ||
| 117 | 2 | return find_if(tuple, pred) != std::tuple_size<std::decay_t<Tuple>>::value; | |
| 118 | } | ||
| 119 | } // namespace tuple_algos | ||
| 120 | |||
| 121 | /// @brief Dereference a tuple | ||
| 122 | /// @param[in] tuple Tuple to dereference | ||
| 123 | /// @return Dereferenced tuple values | ||
| 124 | template<typename... Ts> | ||
| 125 | 16 | auto dereference(std::tuple<Ts...> const& tuple) | |
| 126 | { | ||
| 127 | 112 | return tuple_algos::transform(tuple, [](auto&& element) -> decltype(auto) { return *element; }); | |
| 128 | } | ||
| 129 | |||
| 130 | /// @brief Helper struct to increment an iterator | ||
| 131 | template<size_t I> | ||
| 132 | struct increment_iterator | ||
| 133 | { | ||
| 134 | /// @brief Increments an iterator of tuples | ||
| 135 | /// @param[in] iterators The iterator to increment | ||
| 136 | /// @param[in] beginIterators Beginning of the Iterators | ||
| 137 | /// @param[in] endIterators End of the Iterators | ||
| 138 | template<typename... Iterators> | ||
| 139 | 120 | static void _(std::tuple<Iterators...>& iterators, std::tuple<Iterators...> const& beginIterators, std::tuple<Iterators...> const& endIterators) | |
| 140 | { | ||
| 141 | 120 | auto& it = std::get<I>(iterators); | |
| 142 | 120 | auto const begin = std::get<I>(beginIterators); | |
| 143 | 120 | auto const end = std::get<I>(endIterators); | |
| 144 | |||
| 145 | 120 | ++it; | |
| 146 | |||
| 147 |
2/2✓ Branch 1 taken 46 times.
✓ Branch 2 taken 14 times.
|
120 | if (it == end) |
| 148 | { | ||
| 149 | 92 | it = begin; | |
| 150 |
1/2✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
|
92 | increment_iterator<I - 1>::_(iterators, beginIterators, endIterators); |
| 151 | } | ||
| 152 | 120 | } | |
| 153 | }; | ||
| 154 | |||
| 155 | /// @brief Helper struct to increment an iterator | ||
| 156 | template<> | ||
| 157 | struct increment_iterator<0> | ||
| 158 | { | ||
| 159 | /// @brief Increments an iterator of tuples | ||
| 160 | /// @param[in] iterators The iterator to increment | ||
| 161 | template<typename... Iterators> | ||
| 162 | 2 | static void _(std::tuple<Iterators...>& iterators, std::tuple<Iterators...> const& /* beginIterators */, std::tuple<Iterators...> const& /* endIterators */) | |
| 163 | { | ||
| 164 | 2 | auto& it = std::get<0>(iterators); | |
| 165 | |||
| 166 | 2 | ++it; | |
| 167 | 2 | } | |
| 168 | }; | ||
| 169 | |||
| 170 | /// @brief Gets the next combination of the tuples of iterators | ||
| 171 | /// @param[in] iterators The iterator to get the next combination for | ||
| 172 | /// @param[in] beginIterators Beginning of the Iterators | ||
| 173 | /// @param[in] endIterators End of the Iterators | ||
| 174 | template<typename... Iterators> | ||
| 175 | 16 | void next_combination(std::tuple<Iterators...>& iterators, std::tuple<Iterators...> const& beginIterators, std::tuple<Iterators...> const& endIterators) | |
| 176 | { | ||
| 177 | 16 | constexpr auto N = sizeof...(Iterators); | |
| 178 | 16 | increment_iterator<N - 1>::_(iterators, beginIterators, endIterators); | |
| 179 | 16 | } | |
| 180 | |||
| 181 | /// @brief Calls the function on the tuple | ||
| 182 | /// @param[in] function Function to call | ||
| 183 | /// @param[in] tuple Tuple to pass as argument | ||
| 184 | template<typename Function, typename... Ts, size_t... Is> | ||
| 185 | void callFunction(Function function, std::tuple<Ts...> const& tuple, std::index_sequence<Is...> /* seq */) | ||
| 186 | { | ||
| 187 | function(std::get<Is>(tuple)...); | ||
| 188 | } | ||
| 189 | |||
| 190 | } // namespace CartesianProduct | ||
| 191 | |||
| 192 | /// @brief Calls a function on all combinations over ranges | ||
| 193 | /// @param[in] function Function to call. Needs one parameter for each range given. Type of the parameter must be equal to the range type. | ||
| 194 | /// @param[in] ranges Ranges to call the function on | ||
| 195 | template<typename Function, typename... Ranges> | ||
| 196 | 2 | void cartesian_product(Function function, Ranges const&... ranges) | |
| 197 | { | ||
| 198 | static_assert(sizeof...(Ranges) > 0, "There should be at least one range in cartesian_product."); | ||
| 199 |
1/2✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
|
14 | auto const hasEmptyRange = CartesianProduct::tuple_algos::any_of(std::forward_as_tuple(ranges...), [](auto&& range) { return range.size() == 0; }); |
| 200 | |||
| 201 |
1/2✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
|
2 | if (!hasEmptyRange) |
| 202 | { | ||
| 203 |
1/2✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
|
12 | auto const beginIterators = std::make_tuple(begin(ranges)...); |
| 204 |
1/2✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
|
12 | auto const endIterators = std::make_tuple(end(ranges)...); |
| 205 | |||
| 206 |
2/2✓ Branch 3 taken 16 times.
✓ Branch 4 taken 2 times.
|
18 | for (auto iterators = beginIterators; std::get<0>(iterators) != std::get<0>(endIterators); CartesianProduct::next_combination(iterators, beginIterators, endIterators)) |
| 207 | { | ||
| 208 |
3/6✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 16 times.
✗ Branch 8 not taken.
|
16 | std::apply(function, CartesianProduct::dereference(iterators)); |
| 209 | } | ||
| 210 | } | ||
| 211 | 2 | } | |
| 212 | |||
| 213 | /// @brief Calls a function on all combinations over ranges defined in an array, e.g. std::array<std::vector> | ||
| 214 | /// @param[in] function Function to call. Needs one parameter for each element in the array. Type of the parameter must be equal to the range type. | ||
| 215 | /// @param[in] list List of ranges to call the function on | ||
| 216 | template<typename SubList, size_t N, typename Function> | ||
| 217 | void cartesian_product(Function function, std::array<SubList, N> list) | ||
| 218 | { | ||
| 219 | std::apply([function](auto... xs) { cartesian_product(function, std::forward<decltype(xs)>(xs)...); }, list); | ||
| 220 | } | ||
| 221 | |||
| 222 | /// @brief Calls a function on all combinations over ranges defined in an array, e.g. std::array<std::vector>. | ||
| 223 | /// Instead of providing the list entry to the function, provides the index of it in the sub list. | ||
| 224 | /// @param[in] function Function to call. Needs one 'size_t' parameter for each element in the array | ||
| 225 | /// @param[in] list List of ranges to call the function on | ||
| 226 | template<typename SubList, size_t N, typename Function> | ||
| 227 | 2 | void cartesian_product_idx(Function function, std::array<SubList, N> list) | |
| 228 | { | ||
| 229 | 2 | std::array<std::vector<size_t>, N> indices; | |
| 230 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
|
28 | for (size_t i = 0; i < list.size(); i++) |
| 231 | { | ||
| 232 |
3/6✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 12 times.
✗ Branch 9 not taken.
|
12 | indices.at(i) = std::vector<size_t>(list.at(i).size()); |
| 233 |
2/4✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
|
12 | std::iota(indices.at(i).begin(), indices.at(i).end(), 0); |
| 234 | } | ||
| 235 | |||
| 236 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
4 | std::apply([function](const auto&... xs) { cartesian_product(function, std::forward<decltype(xs)>(xs)...); }, indices); |
| 237 | 2 | } | |
| 238 | |||
| 239 | } // namespace NAV | ||
| 240 |