#853

Committed 19 Dec 2022 01:01AM UTC coverage: 86.287% (+0.4%) from 85.912%

Build # #853

Build Type

push

Committed by StellarBot

Commit Message

Merge #6109

6109: Modernize serialization module r=hkaiser a=hkaiser

- flyby separate serialization of Boost types

working towards https://github.com/STEllAR-GROUP/hpx/issues/5497

Co-authored-by: Hartmut Kaiser <hartmut.kaiser@gmail.com>

Run Details

53 of 53 new or added lines in 6 files covered. (100.0%)

173939 of 201582 relevant lines covered (86.29%)

1931657.12 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.19

/libs/core/algorithms/include/hpx/parallel/algorithms/set_union.hpp

//  Copyright (c) 2007-2022 Hartmut Kaiser
//
//  SPDX-License-Identifier: BSL-1.0
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

/// \file parallel/algorithms/set_union.hpp

#pragma once

#if defined(DOXYGEN)
namespace hpx {
    // clang-format off

    /// Constructs a sorted range beginning at dest consisting of all elements
    /// present in one or both sorted ranges [first1, last1) and
    /// [first2, last2). This algorithm expects both input ranges to be sorted
    /// with the given binary predicate \a pred. Executed according to the policy.
    ///
    /// \note   Complexity: At most 2*(N1 + N2 - 1) comparisons, where \a N1 is
    ///         the length of the first sequence and \a N2 is the length of the
    ///         second sequence.
    ///
    /// If some element is found \a m times in [first1, last1) and \a n times
    /// in [first2, last2), then all \a m elements will be copied from
    /// [first1, last1) to dest, preserving order, and then exactly
    /// std::max(n-m, 0) elements will be copied from [first2, last2) to dest,
    /// also preserving order.
    ///
    /// The resulting range cannot overlap with either of the input ranges.
    ///
    /// \tparam ExPolicy    The type of the execution policy to use (deduced).
    ///                     It describes the manner in which the execution
    ///                     of the algorithm may be parallelized and the manner
    ///                     in which it applies user-provided function objects.
    /// \tparam FwdIter1    The type of the source iterators used (deduced)
    ///                     representing the first sequence.
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam FwdIter2    The type of the source iterators used (deduced)
    ///                     representing the first sequence.
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam FwdIter3    The type of the iterator representing the
    ///                     destination range (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator or output iterator and sequential
    ///                     execution.
    /// \tparam Op          The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a set_union requires \a Pred to meet the
    ///                     requirements of \a CopyConstructible. This defaults
    ///                     to std::less<>
    ///
    /// \param policy       The execution policy to use for the scheduling of
    ///                     the iterations.
    /// \param first1       Refers to the beginning of the sequence of elements
    ///                     of the first range the algorithm will be applied to.
    /// \param last1        Refers to the end of the sequence of elements of
    ///                     the first range the algorithm will be applied to.
    /// \param first2       Refers to the beginning of the sequence of elements
    ///                     of the second range the algorithm will be applied to.
    /// \param last2        Refers to the end of the sequence of elements of
    ///                     the second range the algorithm will be applied to.
    /// \param dest         Refers to the beginning of the destination range.
    /// \param op           The binary predicate which returns true if the
    ///                     elements should be treated as equal. The signature
    ///                     of the predicate function should be equivalent to
    ///                     the following:
    ///                     \code
    ///                     bool pred(const Type1 &a, const Type1 &b);
    ///                     \endcode \n
    ///                     The signature does not need to have const &, but
    ///                     the function must not modify the objects passed to
    ///                     it. The type \a Type1 must be such
    ///                     that objects of type \a FwdIter can
    ///                     be dereferenced and then implicitly converted to
    ///                     \a Type1
    ///
    /// The application of function objects in parallel algorithm
    /// invoked with a sequential execution policy object execute in sequential
    /// order in the calling thread (\a sequenced_policy) or in a
    /// single new thread spawned from the current thread
    /// (for \a sequenced_task_policy).
    ///
    /// The application of function objects in parallel algorithm
    /// invoked with an execution policy object of type
    /// \a parallel_policy or \a parallel_task_policy are
    /// permitted to execute in an unordered fashion in unspecified
    /// threads, and indeterminately sequenced within each thread.
    ///
    /// \returns  The \a set_union algorithm returns a \a hpx::future<FwdIter3>
    ///           if the execution policy is of type
    ///           \a sequenced_task_policy or
    ///           \a parallel_task_policy and
    ///           returns \a FwdIter3 otherwise.
    ///           The \a set_union algorithm returns the output iterator to the
    ///           element in the destination range, one past the last element
    ///           copied.
    ///
    template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
        typename FwdIter3, typename Pred = hpx::parallel::v1::detail::less>
    typename hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter3>::type
    set_union(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1,
        FwdIter2 first2, FwdIter2 last2, FwdIter3 dest, Pred&& op = Pred());

    /// Constructs a sorted range beginning at dest consisting of all elements
    /// present in one or both sorted ranges [first1, last1) and
    /// [first2, last2). This algorithm expects both input ranges to be sorted
    /// with the given binary predicate \a pred. Executed according to the policy.
    ///
    /// \note   Complexity: At most 2*(N1 + N2 - 1) comparisons, where \a N1 is
    ///         the length of the first sequence and \a N2 is the length of the
    ///         second sequence.
    ///
    /// If some element is found \a m times in [first1, last1) and \a n times
    /// in [first2, last2), then all \a m elements will be copied from
    /// [first1, last1) to dest, preserving order, and then exactly
    /// std::max(n-m, 0) elements will be copied from [first2, last2) to dest,
    /// also preserving order.
    ///
    /// The resulting range cannot overlap with either of the input ranges.
    ///
    /// \tparam FwdIter1    The type of the source iterators used (deduced)
    ///                     representing the first sequence.
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam FwdIter2    The type of the source iterators used (deduced)
    ///                     representing the first sequence.
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator.
    /// \tparam FwdIter3    The type of the iterator representing the
    ///                     destination range (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     forward iterator or output iterator and sequential
    ///                     execution.
    /// \tparam Op          The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a set_union requires \a Pred to meet the
    ///                     requirements of \a CopyConstructible. This defaults
    ///                     to std::less<>
    ///
    /// \param first1       Refers to the beginning of the sequence of elements
    ///                     of the first range the algorithm will be applied to.
    /// \param last1        Refers to the end of the sequence of elements of
    ///                     the first range the algorithm will be applied to.
    /// \param first2       Refers to the beginning of the sequence of elements
    ///                     of the second range the algorithm will be applied to.
    /// \param last2        Refers to the end of the sequence of elements of
    ///                     the second range the algorithm will be applied to.
    /// \param dest         Refers to the beginning of the destination range.
    /// \param op           The binary predicate which returns true if the
    ///                     elements should be treated as equal. The signature
    ///                     of the predicate function should be equivalent to
    ///                     the following:
    ///                     \code
    ///                     bool pred(const Type1 &a, const Type1 &b);
    ///                     \endcode \n
    ///                     The signature does not need to have const &, but
    ///                     the function must not modify the objects passed to
    ///                     it. The type \a Type1 must be such
    ///                     that objects of type \a FwdIter can
    ///                     be dereferenced and then implicitly converted to
    ///                     \a Type1
    ///
    /// \returns  The \a set_union algorithm returns a \a FwdIter3.
    ///           The \a set_union algorithm returns the output iterator to the
    ///           element in the destination range, one past the last element
    ///           copied.
    ///
    template <typename FwdIter1, typename FwdIter2, typename FwdIter3,
        typename Pred = hpx::parallel::v1::detail::less>
    FwdIter3 set_union(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2,
        FwdIter2 last2, FwdIter3 dest, Pred&& op = Pred());

    // clang-format on
}    // namespace hpx

#else    // DOXYGEN

#include <hpx/config.hpp>
#include <hpx/concepts/concepts.hpp>
#include <hpx/functional/invoke.hpp>
#include <hpx/iterator_support/traits/is_iterator.hpp>
#include <hpx/parallel/util/detail/sender_util.hpp>

#include <hpx/execution/algorithms/detail/predicates.hpp>
#include <hpx/executors/execution_policy.hpp>
#include <hpx/parallel/algorithms/copy.hpp>
#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/detail/set_operation.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/projection_identity.hpp>
#include <hpx/parallel/util/result_types.hpp>

#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>

namespace hpx { namespace parallel { inline namespace v1 {
    ///////////////////////////////////////////////////////////////////////////
    // set_union
    namespace detail {

        template <typename Iter1, typename Sent1, typename Iter2,
            typename Sent2, typename Iter3, typename Comp, typename Proj1,
            typename Proj2>
        constexpr util::in_in_out_result<Iter1, Iter2, Iter3>
        sequential_set_union(Iter1 first1, Sent1 last1, Iter2 first2,
            Sent2 last2, Iter3 dest, Comp&& comp, Proj1&& proj1, Proj2&& proj2)
        {
            for (; first1 != last1; ++dest)
            {
                if (first2 == last2)
                {
                    auto result = util::copy(first1, last1, dest);
                    return {result.in, first2, result.out};
                }

                auto&& value1 = HPX_INVOKE(proj1, *first1);
                auto&& value2 = HPX_INVOKE(proj2, *first2);

                if (HPX_INVOKE(comp, value2, value1))
                {
                    *dest = *first2++;
                }
                else
                {
                    *dest = *first1;
                    if (!HPX_INVOKE(comp, value1, value2))
                    {
                        ++first2;
                    }
                    ++first1;
                }
            }

            auto result = util::copy(first2, last2, dest);
            return {first1, result.in, result.out};
        }

        ///////////////////////////////////////////////////////////////////////
        template <typename Result>
        struct set_union : public detail::algorithm<set_union<Result>, Result>
        {
            set_union()
              : set_union::algorithm("set_union")
            {
            }

            template <typename ExPolicy, typename Iter1, typename Sent1,
                typename Iter2, typename Sent2, typename Iter3, typename F,
                typename Proj1, typename Proj2>
            static util::in_in_out_result<Iter1, Iter2, Iter3> sequential(
                ExPolicy, Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2,
                Iter3 dest, F&& f, Proj1&& proj1, Proj2&& proj2)
            {
                return sequential_set_union(first1, last1, first2, last2, dest,
                    HPX_FORWARD(F, f), HPX_FORWARD(Proj1, proj1),
                    HPX_FORWARD(Proj2, proj2));
            }

            template <typename ExPolicy, typename Iter1, typename Sent1,
                typename Iter2, typename Sent2, typename Iter3, typename F,
                typename Proj1, typename Proj2>
            static typename util::detail::algorithm_result<ExPolicy,
                util::in_in_out_result<Iter1, Iter2, Iter3>>::type
            parallel(ExPolicy&& policy, Iter1 first1, Sent1 last1, Iter2 first2,
                Sent2 last2, Iter3 dest, F&& f, Proj1&& proj1, Proj2&& proj2)
            {
                using difference_type1 =
                    typename std::iterator_traits<Iter1>::difference_type;
                using difference_type2 =
                    typename std::iterator_traits<Iter2>::difference_type;

                using result_type = util::in_in_out_result<Iter1, Iter2, Iter3>;

                if (first1 == last1)
                {
                    return util::detail::convert_to_result(
                        detail::copy<util::in_out_result<Iter2, Iter3>>().call(
                            HPX_FORWARD(ExPolicy, policy), first2, last2, dest),
                        [first1](util::in_out_result<Iter2, Iter3> const& p)
                            -> result_type {
                            return {first1, p.in, p.out};
                        });
                }

                if (first2 == last2)
                {
                    return util::detail::convert_to_result(
                        detail::copy<util::in_out_result<Iter1, Iter3>>().call(
                            HPX_FORWARD(ExPolicy, policy), first1, last1, dest),
                        [first2](util::in_out_result<Iter1, Iter3> const& p)
                            -> result_type {
                            return {p.in, first2, p.out};
                        });
                }

                using buffer_type = typename set_operations_buffer<Iter3>::type;
                using func_type = typename std::decay<F>::type;

                // calculate approximate destination index
                auto f1 = [](difference_type1 idx1,
                              difference_type2 idx2) -> difference_type1 {
                    return idx1 + idx2;
                };

                // perform required set operation for one chunk
                auto f2 = [proj1, proj2](Iter1 part_first1, Sent1 part_last1,
                              Iter2 part_first2, Sent2 part_last2,
                              buffer_type* dest, func_type const& f) {
                    return sequential_set_union(part_first1, part_last1,
                        part_first2, part_last2, dest, f, proj1, proj2);
                };

                return set_operation(HPX_FORWARD(ExPolicy, policy), first1,
                    last1, first2, last2, dest, HPX_FORWARD(F, f),
                    HPX_FORWARD(Proj1, proj1), HPX_FORWARD(Proj2, proj2),
                    HPX_MOVE(f1), HPX_MOVE(f2));
            }
        };
    }    // namespace detail
}}}      // namespace hpx::parallel::v1

namespace hpx {

    ///////////////////////////////////////////////////////////////////////////
    // CPO for hpx::set_union
    inline constexpr struct set_union_t final
      : hpx::detail::tag_parallel_algorithm<set_union_t>
    {
    private:
        // clang-format off
        template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
            typename FwdIter3, typename Pred = hpx::parallel::v1::detail::less,
            HPX_CONCEPT_REQUIRES_(
                hpx::is_execution_policy<ExPolicy>::value &&
                hpx::traits::is_iterator<FwdIter1>::value &&
                hpx::traits::is_iterator<FwdIter2>::value &&
                hpx::traits::is_iterator<FwdIter3>::value &&
                hpx::is_invocable_v<Pred,
                    typename std::iterator_traits<FwdIter1>::value_type,
                    typename std::iterator_traits<FwdIter2>::value_type
                >
            )>
        // clang-format on
        friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
            FwdIter3>::type
        tag_fallback_invoke(set_union_t, ExPolicy&& policy, FwdIter1 first1,
            FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, FwdIter3 dest,
            Pred&& op = Pred())
        {
            static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
                "Requires at least forward iterator.");
            static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
                "Requires at least forward iterator.");
            static_assert(hpx::traits::is_forward_iterator<FwdIter3>::value ||
                    (hpx::is_sequenced_execution_policy<ExPolicy>::value &&
                        hpx::traits::is_output_iterator<FwdIter3>::value),
                "Requires at least forward iterator or sequential execution.");

            using is_seq = std::integral_constant<bool,
                hpx::is_sequenced_execution_policy<ExPolicy>::value ||
                    !hpx::traits::is_random_access_iterator<FwdIter1>::value ||
                    !hpx::traits::is_random_access_iterator<FwdIter2>::value>;

            using result_type = hpx::parallel::util::in_in_out_result<FwdIter1,
                FwdIter2, FwdIter3>;

            return hpx::parallel::util::get_third_element(
                hpx::parallel::v1::detail::set_union<result_type>().call2(
                    HPX_FORWARD(ExPolicy, policy), is_seq(), first1, last1,
                    first2, last2, dest, HPX_FORWARD(Pred, op),
                    hpx::parallel::util::projection_identity(),
                    hpx::parallel::util::projection_identity()));
        }

        // clang-format off
        template <typename FwdIter1, typename FwdIter2, typename FwdIter3,
            typename Pred = hpx::parallel::v1::detail::less,
            HPX_CONCEPT_REQUIRES_(
                hpx::traits::is_iterator<FwdIter1>::value &&
                hpx::traits::is_iterator<FwdIter2>::value &&
                hpx::traits::is_iterator<FwdIter3>::value &&
                hpx::is_invocable_v<Pred,
                    typename std::iterator_traits<FwdIter1>::value_type,
                    typename std::iterator_traits<FwdIter2>::value_type
                >
            )>
        // clang-format on
        friend FwdIter3 tag_fallback_invoke(set_union_t, FwdIter1 first1,
            FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, FwdIter3 dest,
            Pred&& op = Pred())
        {
            static_assert((hpx::traits::is_input_iterator<FwdIter1>::value),
                "Requires at least input iterator.");
            static_assert((hpx::traits::is_input_iterator<FwdIter2>::value),
                "Requires at least input iterator.");
            static_assert((hpx::traits::is_output_iterator<FwdIter3>::value),
                "Requires at least output iterator.");

            using result_type = hpx::parallel::util::in_in_out_result<FwdIter1,
                FwdIter3, FwdIter3>;

            return hpx::parallel::util::get_third_element(
                hpx::parallel::v1::detail::set_union<result_type>().call(
                    hpx::execution::seq, first1, last1, first2, last2, dest,
                    HPX_FORWARD(Pred, op),
                    hpx::parallel::util::projection_identity(),
                    hpx::parallel::util::projection_identity()));
        }
    } set_union{};
}    // namespace hpx

#endif    // DOXYGEN

1	// Copyright (c) 2007-2022 Hartmut Kaiser
2	//
3	// SPDX-License-Identifier: BSL-1.0
4	// Distributed under the Boost Software License, Version 1.0. (See accompanying
5	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7	/// \file parallel/algorithms/set_union.hpp
8
9	#pragma once
10
11	#if defined(DOXYGEN)
12	namespace hpx {
13	// clang-format off
14
15	/// Constructs a sorted range beginning at dest consisting of all elements
16	/// present in one or both sorted ranges [first1, last1) and
17	/// [first2, last2). This algorithm expects both input ranges to be sorted
18	/// with the given binary predicate \a pred. Executed according to the policy.
19	///
20	/// \note Complexity: At most 2*(N1 + N2 - 1) comparisons, where \a N1 is
21	/// the length of the first sequence and \a N2 is the length of the
22	/// second sequence.
23	///
24	/// If some element is found \a m times in [first1, last1) and \a n times
25	/// in [first2, last2), then all \a m elements will be copied from
26	/// [first1, last1) to dest, preserving order, and then exactly
27	/// std::max(n-m, 0) elements will be copied from [first2, last2) to dest,
28	/// also preserving order.
29	///
30	/// The resulting range cannot overlap with either of the input ranges.
31	///
32	/// \tparam ExPolicy The type of the execution policy to use (deduced).
33	/// It describes the manner in which the execution
34	/// of the algorithm may be parallelized and the manner
35	/// in which it applies user-provided function objects.
36	/// \tparam FwdIter1 The type of the source iterators used (deduced)
37	/// representing the first sequence.
38	/// This iterator type must meet the requirements of a
39	/// forward iterator.
40	/// \tparam FwdIter2 The type of the source iterators used (deduced)
41	/// representing the first sequence.
42	/// This iterator type must meet the requirements of a
43	/// forward iterator.
44	/// \tparam FwdIter3 The type of the iterator representing the
45	/// destination range (deduced).
46	/// This iterator type must meet the requirements of a
47	/// forward iterator or output iterator and sequential
48	/// execution.
49	/// \tparam Op The type of an optional function/function object to use.
50	/// Unlike its sequential form, the parallel
51	/// overload of \a set_union requires \a Pred to meet the
52	/// requirements of \a CopyConstructible. This defaults
53	/// to std::less<>
54	///
55	/// \param policy The execution policy to use for the scheduling of
56	/// the iterations.
57	/// \param first1 Refers to the beginning of the sequence of elements
58	/// of the first range the algorithm will be applied to.
59	/// \param last1 Refers to the end of the sequence of elements of
60	/// the first range the algorithm will be applied to.
61	/// \param first2 Refers to the beginning of the sequence of elements
62	/// of the second range the algorithm will be applied to.
63	/// \param last2 Refers to the end of the sequence of elements of
64	/// the second range the algorithm will be applied to.
65	/// \param dest Refers to the beginning of the destination range.
66	/// \param op The binary predicate which returns true if the
67	/// elements should be treated as equal. The signature
68	/// of the predicate function should be equivalent to
69	/// the following:
70	/// \code
71	/// bool pred(const Type1 &a, const Type1 &b);
72	/// \endcode \n
73	/// The signature does not need to have const &, but
74	/// the function must not modify the objects passed to
75	/// it. The type \a Type1 must be such
76	/// that objects of type \a FwdIter can
77	/// be dereferenced and then implicitly converted to
78	/// \a Type1
79	///
80	/// The application of function objects in parallel algorithm
81	/// invoked with a sequential execution policy object execute in sequential
82	/// order in the calling thread (\a sequenced_policy) or in a
83	/// single new thread spawned from the current thread
84	/// (for \a sequenced_task_policy).
85	///
86	/// The application of function objects in parallel algorithm
87	/// invoked with an execution policy object of type
88	/// \a parallel_policy or \a parallel_task_policy are
89	/// permitted to execute in an unordered fashion in unspecified
90	/// threads, and indeterminately sequenced within each thread.
91	///
92	/// \returns The \a set_union algorithm returns a \a hpx::future<FwdIter3>
93	/// if the execution policy is of type
94	/// \a sequenced_task_policy or
95	/// \a parallel_task_policy and
96	/// returns \a FwdIter3 otherwise.
97	/// The \a set_union algorithm returns the output iterator to the
98	/// element in the destination range, one past the last element
99	/// copied.
100	///
101	template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
102	typename FwdIter3, typename Pred = hpx::parallel::v1::detail::less>
103	typename hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter3>::type
104	set_union(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1,
105	FwdIter2 first2, FwdIter2 last2, FwdIter3 dest, Pred&& op = Pred());
106
107	/// Constructs a sorted range beginning at dest consisting of all elements
108	/// present in one or both sorted ranges [first1, last1) and
109	/// [first2, last2). This algorithm expects both input ranges to be sorted
110	/// with the given binary predicate \a pred. Executed according to the policy.
111	///
112	/// \note Complexity: At most 2*(N1 + N2 - 1) comparisons, where \a N1 is
113	/// the length of the first sequence and \a N2 is the length of the
114	/// second sequence.
115	///
116	/// If some element is found \a m times in [first1, last1) and \a n times
117	/// in [first2, last2), then all \a m elements will be copied from
118	/// [first1, last1) to dest, preserving order, and then exactly
119	/// std::max(n-m, 0) elements will be copied from [first2, last2) to dest,
120	/// also preserving order.
121	///
122	/// The resulting range cannot overlap with either of the input ranges.
123	///
124	/// \tparam FwdIter1 The type of the source iterators used (deduced)
125	/// representing the first sequence.
126	/// This iterator type must meet the requirements of a
127	/// forward iterator.
128	/// \tparam FwdIter2 The type of the source iterators used (deduced)
129	/// representing the first sequence.
130	/// This iterator type must meet the requirements of a
131	/// forward iterator.
132	/// \tparam FwdIter3 The type of the iterator representing the
133	/// destination range (deduced).
134	/// This iterator type must meet the requirements of a
135	/// forward iterator or output iterator and sequential
136	/// execution.
137	/// \tparam Op The type of an optional function/function object to use.
138	/// Unlike its sequential form, the parallel
139	/// overload of \a set_union requires \a Pred to meet the
140	/// requirements of \a CopyConstructible. This defaults
141	/// to std::less<>
142	///
143	/// \param first1 Refers to the beginning of the sequence of elements
144	/// of the first range the algorithm will be applied to.
145	/// \param last1 Refers to the end of the sequence of elements of
146	/// the first range the algorithm will be applied to.
147	/// \param first2 Refers to the beginning of the sequence of elements
148	/// of the second range the algorithm will be applied to.
149	/// \param last2 Refers to the end of the sequence of elements of
150	/// the second range the algorithm will be applied to.
151	/// \param dest Refers to the beginning of the destination range.
152	/// \param op The binary predicate which returns true if the
153	/// elements should be treated as equal. The signature
154	/// of the predicate function should be equivalent to
155	/// the following:
156	/// \code
157	/// bool pred(const Type1 &a, const Type1 &b);
158	/// \endcode \n
159	/// The signature does not need to have const &, but
160	/// the function must not modify the objects passed to
161	/// it. The type \a Type1 must be such
162	/// that objects of type \a FwdIter can
163	/// be dereferenced and then implicitly converted to
164	/// \a Type1
165	///
166	/// \returns The \a set_union algorithm returns a \a FwdIter3.
167	/// The \a set_union algorithm returns the output iterator to the
168	/// element in the destination range, one past the last element
169	/// copied.
170	///
171	template <typename FwdIter1, typename FwdIter2, typename FwdIter3,
172	typename Pred = hpx::parallel::v1::detail::less>
173	FwdIter3 set_union(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2,
174	FwdIter2 last2, FwdIter3 dest, Pred&& op = Pred());
175
176	// clang-format on
177	} // namespace hpx
178
179	#else // DOXYGEN
180
181	#include <hpx/config.hpp>
182	#include <hpx/concepts/concepts.hpp>
183	#include <hpx/functional/invoke.hpp>
184	#include <hpx/iterator_support/traits/is_iterator.hpp>
185	#include <hpx/parallel/util/detail/sender_util.hpp>
186
187	#include <hpx/execution/algorithms/detail/predicates.hpp>
188	#include <hpx/executors/execution_policy.hpp>
189	#include <hpx/parallel/algorithms/copy.hpp>
190	#include <hpx/parallel/algorithms/detail/dispatch.hpp>
191	#include <hpx/parallel/algorithms/detail/set_operation.hpp>
192	#include <hpx/parallel/util/detail/algorithm_result.hpp>
193	#include <hpx/parallel/util/projection_identity.hpp>
194	#include <hpx/parallel/util/result_types.hpp>
195
196	#include <algorithm>
197	#include <iterator>
198	#include <type_traits>
199	#include <utility>
200
201	namespace hpx { namespace parallel { inline namespace v1 {
202	///////////////////////////////////////////////////////////////////////////
203	// set_union
204	namespace detail {
205
206	template <typename Iter1, typename Sent1, typename Iter2,
207	typename Sent2, typename Iter3, typename Comp, typename Proj1,
208	typename Proj2>
209	constexpr util::in_in_out_result<Iter1, Iter2, Iter3>
210	sequential_set_union(Iter1 first1, Sent1 last1, Iter2 first2,	116✔
211	Sent2 last2, Iter3 dest, Comp&& comp, Proj1&& proj1, Proj2&& proj2)
212	{
213	for (; first1 != last1; ++dest)	925,682✔
214	{
215	if (first2 == last2)	914,584✔
216	{
217	auto result = util::copy(first1, last1, dest);	37✔
218	return {result.in, first2, result.out};	37✔
219	}	×
220
221	auto&& value1 = HPX_INVOKE(proj1, *first1);	938,794✔
222	auto&& value2 = HPX_INVOKE(proj2, *first2);	938,794✔
223
224	if (HPX_INVOKE(comp, value2, value1))	938,794✔
225	{
226	dest = first2++;	469,361✔
227	}	469,361✔
228	else
229	{
230	dest = first1;	468,773✔
231	if (!HPX_INVOKE(comp, value1, value2))	468,773✔
232	{
233	++first2;	×
234	}	×
235	++first1;	469,285✔
236	}
237	}	925,566✔
238
239	auto result = util::copy(first2, last2, dest);	47✔
240	return {first1, result.in, result.out};	47✔
241	}	84✔
242
243	///////////////////////////////////////////////////////////////////////
244	template <typename Result>
245	struct set_union : public detail::algorithm<set_union<Result>, Result>
246	{
247	set_union()	88✔
248	: set_union::algorithm("set_union")	88✔
249	{	88✔
250	}	88✔
251
252	template <typename ExPolicy, typename Iter1, typename Sent1,
253	typename Iter2, typename Sent2, typename Iter3, typename F,
254	typename Proj1, typename Proj2>
255	static util::in_in_out_result<Iter1, Iter2, Iter3> sequential(	68✔
256	ExPolicy, Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2,
257	Iter3 dest, F&& f, Proj1&& proj1, Proj2&& proj2)
258	{
259	return sequential_set_union(first1, last1, first2, last2, dest,	104✔
260	HPX_FORWARD(F, f), HPX_FORWARD(Proj1, proj1),	68✔
261	HPX_FORWARD(Proj2, proj2));	68✔
262	}	32✔
263
264	template <typename ExPolicy, typename Iter1, typename Sent1,
265	typename Iter2, typename Sent2, typename Iter3, typename F,
266	typename Proj1, typename Proj2>
267	static typename util::detail::algorithm_result<ExPolicy,
268	util::in_in_out_result<Iter1, Iter2, Iter3>>::type
269	parallel(ExPolicy&& policy, Iter1 first1, Sent1 last1, Iter2 first2,	20✔
270	Sent2 last2, Iter3 dest, F&& f, Proj1&& proj1, Proj2&& proj2)
271	{
272	using difference_type1 =
273	typename std::iterator_traits<Iter1>::difference_type;
274	using difference_type2 =
275	typename std::iterator_traits<Iter2>::difference_type;
276
277	using result_type = util::in_in_out_result<Iter1, Iter2, Iter3>;
278
279	if (first1 == last1)	20✔
280	{
281	return util::detail::convert_to_result(	4✔
282	detail::copy<util::in_out_result<Iter2, Iter3>>().call(	×
283	HPX_FORWARD(ExPolicy, policy), first2, last2, dest),	×
284	[first1](util::in_out_result<Iter2, Iter3> const& p)	×
285	-> result_type {
286	return {first1, p.in, p.out};	×
287	});
288	}
289
290	if (first2 == last2)	20✔
291	{
292	return util::detail::convert_to_result(	×
293	detail::copy<util::in_out_result<Iter1, Iter3>>().call(	×
294	HPX_FORWARD(ExPolicy, policy), first1, last1, dest),	×
295	[first2](util::in_out_result<Iter1, Iter3> const& p)	×
296	-> result_type {
297	return {p.in, first2, p.out};	×
298	});
299	}
300
301	using buffer_type = typename set_operations_buffer<Iter3>::type;
302	using func_type = typename std::decay<F>::type;
303
304	// calculate approximate destination index
305	auto f1 = [](difference_type1 idx1,	68✔
306	difference_type2 idx2) -> difference_type1 {
307	return idx1 + idx2;	68✔
308	};
309
310	// perform required set operation for one chunk
311	auto f2 = [proj1, proj2](Iter1 part_first1, Sent1 part_last1,	68✔
312	Iter2 part_first2, Sent2 part_last2,
313	buffer_type* dest, func_type const& f) {
314	return sequential_set_union(part_first1, part_last1,	96✔
315	part_first2, part_last2, dest, f, proj1, proj2);	48✔
316	};	×
317
318	return set_operation(HPX_FORWARD(ExPolicy, policy), first1,	32✔
319	last1, first2, last2, dest, HPX_FORWARD(F, f),	20✔
320	HPX_FORWARD(Proj1, proj1), HPX_FORWARD(Proj2, proj2),	20✔
321	HPX_MOVE(f1), HPX_MOVE(f2));
322	}	20✔
323	};
324	} // namespace detail
325	}}} // namespace hpx::parallel::v1
326
327	namespace hpx {
328
329	///////////////////////////////////////////////////////////////////////////
330	// CPO for hpx::set_union
331	inline constexpr struct set_union_t final
332	: hpx::detail::tag_parallel_algorithm<set_union_t>
333	{
334	private:
335	// clang-format off
336	template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
337	typename FwdIter3, typename Pred = hpx::parallel::v1::detail::less,
338	HPX_CONCEPT_REQUIRES_(
339	hpx::is_execution_policy<ExPolicy>::value &&
340	hpx::traits::is_iterator<FwdIter1>::value &&
341	hpx::traits::is_iterator<FwdIter2>::value &&
342	hpx::traits::is_iterator<FwdIter3>::value &&
343	hpx::is_invocable_v<Pred,
344	typename std::iterator_traits<FwdIter1>::value_type,
345	typename std::iterator_traits<FwdIter2>::value_type
346	>
347	)>
348	// clang-format on
349	friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
350	FwdIter3>::type
351	tag_fallback_invoke(set_union_t, ExPolicy&& policy, FwdIter1 first1,	36✔
352	FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, FwdIter3 dest,
353	Pred&& op = Pred())
354	{
355	static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
356	"Requires at least forward iterator.");
357	static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
358	"Requires at least forward iterator.");
359	static_assert(hpx::traits::is_forward_iterator<FwdIter3>::value \|\|
360	(hpx::is_sequenced_execution_policy<ExPolicy>::value &&
361	hpx::traits::is_output_iterator<FwdIter3>::value),
362	"Requires at least forward iterator or sequential execution.");
363
364	using is_seq = std::integral_constant<bool,
365	hpx::is_sequenced_execution_policy<ExPolicy>::value \|\|
366	!hpx::traits::is_random_access_iterator<FwdIter1>::value \|\|
367	!hpx::traits::is_random_access_iterator<FwdIter2>::value>;
368
369	using result_type = hpx::parallel::util::in_in_out_result<FwdIter1,
370	FwdIter2, FwdIter3>;
371
372	return hpx::parallel::util::get_third_element(	36✔
373	hpx::parallel::v1::detail::set_union<result_type>().call2(	72✔
374	HPX_FORWARD(ExPolicy, policy), is_seq(), first1, last1,	28✔
375	first2, last2, dest, HPX_FORWARD(Pred, op),	28✔
376	hpx::parallel::util::projection_identity(),
377	hpx::parallel::util::projection_identity()));
378	}	×
379
380	// clang-format off
381	template <typename FwdIter1, typename FwdIter2, typename FwdIter3,
382	typename Pred = hpx::parallel::v1::detail::less,
383	HPX_CONCEPT_REQUIRES_(
384	hpx::traits::is_iterator<FwdIter1>::value &&
385	hpx::traits::is_iterator<FwdIter2>::value &&
386	hpx::traits::is_iterator<FwdIter3>::value &&
387	hpx::is_invocable_v<Pred,
388	typename std::iterator_traits<FwdIter1>::value_type,
389	typename std::iterator_traits<FwdIter2>::value_type
390	>
391	)>
392	// clang-format on
393	friend FwdIter3 tag_fallback_invoke(set_union_t, FwdIter1 first1,	8✔
394	FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, FwdIter3 dest,
395	Pred&& op = Pred())
396	{
397	static_assert((hpx::traits::is_input_iterator<FwdIter1>::value),
398	"Requires at least input iterator.");
399	static_assert((hpx::traits::is_input_iterator<FwdIter2>::value),
400	"Requires at least input iterator.");
401	static_assert((hpx::traits::is_output_iterator<FwdIter3>::value),
402	"Requires at least output iterator.");
403
404	using result_type = hpx::parallel::util::in_in_out_result<FwdIter1,
405	FwdIter3, FwdIter3>;
406
407	return hpx::parallel::util::get_third_element(	8✔
408	hpx::parallel::v1::detail::set_union<result_type>().call(	16✔
409	hpx::execution::seq, first1, last1, first2, last2, dest,
410	HPX_FORWARD(Pred, op),	4✔
411	hpx::parallel::util::projection_identity(),
412	hpx::parallel::util::projection_identity()));
413	}	×
414	} set_union{};
415	} // namespace hpx
416
417	#endif // DOXYGEN

STEllAR-GROUP / hpx / #853

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous