boost/hana/partition.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::partition`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_PARTITION_HPP
0011 #define BOOST_HANA_PARTITION_HPP
0012
0013 #include <boost/hana/fwd/partition.hpp>
0014
0015 #include <boost/hana/at.hpp>
0016 #include <boost/hana/concept/sequence.hpp>
0017 #include <boost/hana/config.hpp>
0018 #include <boost/hana/core/dispatch.hpp>
0019 #include <boost/hana/core/make.hpp>
0020 #include <boost/hana/detail/algorithm.hpp>
0021 #include <boost/hana/detail/array.hpp>
0022 #include <boost/hana/detail/decay.hpp>
0023 #include <boost/hana/detail/nested_by.hpp> // required by fwd decl
0024 #include <boost/hana/pair.hpp>
0025 #include <boost/hana/unpack.hpp>
0026
0027 #include <cstddef>
0028 #include <utility>
0029
0030
0031 namespace boost { namespace hana {
0032     //! @cond
0033     template <typename Xs, typename Pred>
0034     constexpr auto partition_t::operator()(Xs&& xs, Pred&& pred) const {
0035         using S = typename hana::tag_of<Xs>::type;
0036         using Partition = BOOST_HANA_DISPATCH_IF(partition_impl<S>,
0037             hana::Sequence<S>::value
0038         );
0039
0040     #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
0041         static_assert(hana::Sequence<S>::value,
0042         "hana::partition(xs, pred) requires 'xs' to be a Sequence");
0043     #endif
0044
0045         return Partition::apply(static_cast<Xs&&>(xs), static_cast<Pred&&>(pred));
0046     }
0047     //! @endcond
0048
0049     namespace detail {
0050         template <bool ...B>
0051         struct partition_indices {
0052             static constexpr detail::array<bool, sizeof...(B)> results{{B...}};
0053             static constexpr std::size_t left_size =
0054                 detail::count(results.begin(), results.end(), true);
0055             static constexpr std::size_t right_size = sizeof...(B) - left_size;
0056
0057             static constexpr auto compute_left() {
0058                 detail::array<std::size_t, left_size> indices{};
0059                 std::size_t* left = &indices[0];
0060                 for (std::size_t i = 0; i < sizeof...(B); ++i)
0061                     if (results[i])
0062                         *left++ = i;
0063                 return indices;
0064             }
0065
0066             static constexpr auto compute_right() {
0067                 detail::array<std::size_t, right_size> indices{};
0068                 std::size_t* right = &indices[0];
0069                 for (std::size_t i = 0; i < sizeof...(B); ++i)
0070                     if (!results[i])
0071                         *right++ = i;
0072                 return indices;
0073             }
0074
0075             static constexpr auto left_indices = compute_left();
0076             static constexpr auto right_indices = compute_right();
0077
0078             template <typename S, typename Xs, std::size_t ...l, std::size_t ...r>
0079             static constexpr auto apply(Xs&& xs, std::index_sequence<l...>,
0080                                                  std::index_sequence<r...>)
0081             {
0082                 return hana::make<hana::pair_tag>(
0083                     hana::make<S>(hana::at_c<left_indices[l]>(static_cast<Xs&&>(xs))...),
0084                     hana::make<S>(hana::at_c<right_indices[r]>(static_cast<Xs&&>(xs))...)
0085                 );
0086             }
0087         };
0088
0089         template <typename Pred>
0090         struct deduce_partition_indices {
0091             template <typename ...Xs>
0092             auto operator()(Xs&& ...xs) const -> detail::partition_indices<
0093                 static_cast<bool>(detail::decay<
0094                     decltype(std::declval<Pred>()(static_cast<Xs&&>(xs)))
0095                 >::type::value)...
0096             > { return {}; }
0097         };
0098     }
0099
0100     template <typename S, bool condition>
0101     struct partition_impl<S, when<condition>> : default_ {
0102         template <typename Xs, typename Pred>
0103         static constexpr auto apply(Xs&& xs, Pred&&) {
0104             using Indices = decltype(hana::unpack(
0105                 static_cast<Xs&&>(xs), detail::deduce_partition_indices<Pred&&>{}
0106             ));
0107             return Indices::template apply<S>(
0108                 static_cast<Xs&&>(xs),
0109                 std::make_index_sequence<Indices::left_size>{},
0110                 std::make_index_sequence<Indices::right_size>{}
0111             );
0112         }
0113     };
0114 }} // end namespace boost::hana
0115
0116 #endif // !BOOST_HANA_PARTITION_HPP