Line data    Source code

       1            0 : // Distributed under the MIT License.
       2              : // See LICENSE.txt for details.
       3              : 
       4              : #pragma once
       5              : 
       6              : #include <array>
       7              : #include <iterator>
       8              : #include <tuple>
       9              : #include <utility>
      10              : #include <vector>
      11              : 
      12              : // This implementation is from:
      13              : // https://stackoverflow.com/questions/16686942/how-to-iterate-over-two-stl-like-containers-cartesian-product
      14              : 
      15              : namespace detail {
      16              : 
      17              : // the lambda is fully bound with one element from each of the ranges
      18              : template <class Op>
      19              : void insert_tuples(Op op) {
      20              :   // evaluating the lambda will insert the currently bound tuple
      21              :   op();
      22              : }
      23              : 
      24              : // "peel off" the first range from the remaining tuple of ranges
      25              : template <class Op, class InputIterator1, class... InputIterator2>
      26              : void insert_tuples(Op op, std::pair<InputIterator1, InputIterator1> head,
      27              :                    std::pair<InputIterator2, InputIterator2>... tail) {
      28              :   // "peel off" the elements from the first of the remaining ranges
      29              :   // NOTE: the recursion will effectively generate the multiple nested for-loops
      30              :   for (auto it = head.first; it != head.second; ++it) {
      31              :     // bind the first free variable in the lambda, and
      32              :     // keep one free variable for each of the remaining ranges
      33              :     detail::insert_tuples(
      34              :         [&op, &it](InputIterator2... elems) { op(it, elems...); }, tail...);
      35              :   }
      36              : }
      37              : 
      38              : }  // namespace detail
      39              : 
      40              : /*!
      41              :  * \ingroup UtilitiesGroup
      42              :  * \brief Fill the `result` iterator with the Cartesian product of a sequence of
      43              :  * iterators
      44              :  *
      45              :  * The `result` will hold all possible combinations of the input iterators.
      46              :  * The last dimension varies fastest.
      47              :  */
      48              : template <class OutputIterator, class... InputIterator>
      49            1 : void cartesian_product(OutputIterator result,
      50              :                        std::pair<InputIterator, InputIterator>... dimensions) {
      51              :   detail::insert_tuples(
      52              :       [&result](InputIterator... elems) {
      53              :         *result++ = std::make_tuple(*elems...);
      54              :       },
      55              :       dimensions...);
      56              : }
      57              : 
      58              : /*!
      59              :  * \ingroup UtilitiesGroup
      60              :  * \brief The Cartesian product of a sequence of arrays
      61              :  *
      62              :  * Returns a `std::array` with all possible combinations of the input arrays.
      63              :  * The last dimension varies fastest.
      64              :  *
      65              :  * \example
      66              :  * Here's an example using this function to replace a nested for loop:
      67              :  * \snippet Test_Wedge3D.cpp cartesian_product_loop
      68              :  */
      69              : template <typename... Ts, size_t... Lens>
      70            1 : std::array<std::tuple<Ts...>, (... * Lens)> cartesian_product(
      71              :     const std::array<Ts, Lens>&... dimensions) {
      72              :   std::array<std::tuple<Ts...>, (... * Lens)> result{};
      73              :   cartesian_product(result.begin(),
      74              :                     std::make_pair(dimensions.begin(), dimensions.end())...);
      75              :   return result;
      76              : }
      77              : 
      78              : /*!
      79              :  * \ingroup UtilitiesGroup
      80              :  * \brief The Cartesian product of several containers
      81              :  *
      82              :  * Returns a `std::vector` with all possible combinations of the values of the
      83              :  * input containers. The value of the last container varies fastest.
      84              :  */
      85              : template <typename... Containers>
      86            1 : std::vector<std::tuple<typename Containers::value_type...>> cartesian_product(
      87              :     const Containers&... containers) {
      88              :   std::vector<std::tuple<typename Containers::value_type...>> result{};
      89              :   cartesian_product(
      90              :       std::back_inserter(result),
      91              :       std::make_pair(std::begin(containers), std::end(containers))...);
      92              :   return result;
      93              : }