#874

Committed 25 Jan 2023 02:55PM UTC coverage: 85.911% (+0.03%) from 85.883%

Build # #874

Build Type

push

Committed by StellarBot

Commit Message

Merge #6153

6153: Assign global ids to managed component instances that are locally resolvable r=hkaiser a=hkaiser

This will reduce contention while resolving global ids.

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

Run Details

61 of 61 new or added lines in 5 files covered. (100.0%)

173513 of 201968 relevant lines covered (85.91%)

2065249.0 hits per line

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

78.13

/libs/core/algorithms/include/hpx/parallel/algorithms/set_symmetric_difference.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_symmetric_difference.hpp

#pragma once

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

    /// Constructs a sorted range beginning at dest consisting of all elements
    /// present in either of the sorted ranges [first1, last1) and
    /// [first2, last2), but not in both of them are copied to the range
    /// beginning at \a dest. The resulting range is also sorted. 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), it will be copied to \a dest exactly std::abs(m-n)
    /// times. If m>n, then the last m-n of those elements are copied from
    /// [first1,last1), otherwise the last n-m elements are copied from
    /// [first2,last2). The resulting range cannot overlap with either of the
    /// input ranges.
    ///
    /// 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 Pred        The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a set_symmetric_difference 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_symmetric_difference 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_symmetric_difference 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>
    hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter3>::type
    set_symmetric_difference(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 either of the sorted ranges [first1, last1) and
    /// [first2, last2), but not in both of them are copied to the range
    /// beginning at \a dest. The resulting range is also sorted. This
    /// algorithm expects both input ranges to be sorted with the given binary
    /// predicate \a pred.
    ///
    /// \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), it will be copied to \a dest exactly std::abs(m-n)
    /// times. If m>n, then the last m-n of those elements are copied from
    /// [first1,last1), otherwise the last n-m elements are copied from
    /// [first2,last2). The resulting range cannot overlap with either of the
    /// input ranges.
    ///
    /// 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 Pred        The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a set_symmetric_difference 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_symmetric_difference algorithm returns a \a FwdIter3.
    ///           The \a set_symmetric_difference 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_symmetric_difference(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_symmetric_difference
    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_symmetric_difference(Iter1 first1, Sent1 last1,
            Iter2 first2, Sent2 last2, Iter3 dest, Comp&& comp, Proj1&& proj1,
            Proj2&& proj2)
        {
            while (first1 != last1)
            {
                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, value1, value2))
                {
                    *dest++ = *first1++;
                }
                else
                {
                    if (HPX_INVOKE(comp, value2, value1))
                    {
                        *dest++ = *first2;
                    }
                    else
                    {
                        ++first1;
                    }
                    ++first2;
                }
            }

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

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

            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_symmetric_difference(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_symmetric_difference(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_symmetric_difference
    inline constexpr struct set_symmetric_difference_t final
      : hpx::detail::tag_parallel_algorithm<set_symmetric_difference_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_symmetric_difference_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_symmetric_difference<
                    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_symmetric_difference_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,
                FwdIter2, FwdIter3>;

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

STEllAR-GROUP / hpx / #874

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