Skip to content

Commit

Permalink
Fixing mismatch and reduce algorithms
Browse files Browse the repository at this point in the history
  • Loading branch information
@hkaiser
hkaiser committed Jun 28, 2017
1 parent 064178e commit 1616e86
Show file tree
Hide file tree
Showing 6 changed files with 181 additions and 110 deletions.
114 changes: 68 additions & 46 deletions hpx/parallel/algorithms/mismatch.hpp
View file
@@ -1,4 +1,4 @@
// Copyright (c) 2007-2016 Hartmut Kaiser
// Copyright (c) 2007-2017 Hartmut Kaiser
//
// 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)
Expand Down Expand Up @@ -33,10 +33,10 @@ namespace hpx { namespace parallel { inline namespace v1
namespace detail
{
/// \cond NOINTERNAL
template <typename InIter1, typename InIter2, typename F>
std::pair<InIter1, InIter2>
sequential_mismatch_binary(InIter1 first1, InIter1 last1,
InIter2 first2, InIter2 last2, F && f)
template <typename FwdIter1, typename FwdIter2, typename F>
std::pair<FwdIter1, FwdIter2>
sequential_mismatch_binary(FwdIter1 first1, FwdIter1 last1,
FwdIter2 first2, FwdIter2 last2, F && f)
{
while (first1 != last1 && first2 != last2 && f(*first1, *first2))
{
Expand All @@ -52,11 +52,11 @@ namespace hpx { namespace parallel { inline namespace v1
: mismatch_binary::algorithm("mismatch_binary")
{}

template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename F>
static T
sequential(ExPolicy, InIter1 first1, InIter1 last1,
InIter2 first2, InIter2 last2, F && f)
sequential(ExPolicy, FwdIter1 first1, FwdIter1 last1,
FwdIter2 first2, FwdIter2 last2, F && f)
{
return sequential_mismatch_binary(first1, last1, first2, last2,
std::forward<F>(f));
Expand All @@ -78,8 +78,8 @@ namespace hpx { namespace parallel { inline namespace v1
difference_type1;
difference_type1 count1 = std::distance(first1, last1);

// The specifcation of std::mismatch(_binary) states that if InIter1
// and InIter2 meet the requirements of RandomAccessIterator and
// The specifcation of std::mismatch(_binary) states that if FwdIter1
// and FwdIter2 meet the requirements of RandomAccessIterator and
// last1 - first1 != last2 - first2 then no applications of the
// predicate p are made.
//
Expand All @@ -104,7 +104,7 @@ namespace hpx { namespace parallel { inline namespace v1
std::forward<ExPolicy>(policy),
hpx::util::make_zip_iterator(first1, first2), count1, 1,
[f, tok](zip_iterator it, std::size_t part_count,
std::size_t base_idx) mutable
std::size_t base_idx) mutable -> void
{
util::loop_idx_n(
base_idx, it, part_count, tok,
Expand Down Expand Up @@ -139,23 +139,23 @@ namespace hpx { namespace parallel { inline namespace v1
/// [first2, last2), and false otherwise.
///
/// \note Complexity: At most min(last1 - first1, last2 - first2)
/// applications of the predicate \a f. If \a InIter1
/// and \a InIter2 meet the requirements of \a RandomAccessIterator
/// applications of the predicate \a f. If \a FwdIter1
/// and \a FwdIter2 meet the requirements of \a RandomAccessIterator
/// and (last1 - first1) != (last2 - first2) then no applications
/// of the predicate \a f are made.
///
/// \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 executes the assignments.
/// \tparam InIter1 The type of the source iterators used for the
/// \tparam FwdIter1 The type of the source iterators used for the
/// first range (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// \tparam InIter2 The type of the source iterators used for the
/// forward iterator.
/// \tparam FwdIter2 The type of the source iterators used for the
/// second range (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// forward iterator.
/// \tparam Pred The type of an optional function/function object to use.
/// Unlike its sequential form, the parallel
/// overload of \a mismatch requires \a Pred to meet the
Expand All @@ -182,7 +182,7 @@ namespace hpx { namespace parallel { inline namespace v1
/// The signature does not need to have const &, but
/// the function must not modify the objects passed to
/// it. The types \a Type1 and \a Type2 must be such
/// that objects of types \a InIter1 and \a InIter2 can
/// that objects of types \a FwdIter1 and \a FwdIter2 can
/// be dereferenced and then implicitly converted to
/// \a Type1 and \a Type2 respectively
///
Expand Down Expand Up @@ -210,31 +210,42 @@ namespace hpx { namespace parallel { inline namespace v1
/// two ranges are mismatch, otherwise it returns false.
/// If the length of the range [first1, last1) does not mismatch
/// the length of the range [first2, last2), it returns false.
template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename Pred = detail::equal_to>
inline typename std::enable_if<
execution::is_execution_policy<ExPolicy>::value,
typename util::detail::algorithm_result<
ExPolicy, std::pair<InIter1, InIter2>
ExPolicy, std::pair<FwdIter1, FwdIter2>
>::type
>::type
mismatch(ExPolicy&& policy, InIter1 first1, InIter1 last1,
InIter2 first2, InIter2 last2, Pred && op = Pred())
mismatch(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1,
FwdIter2 first2, FwdIter2 last2, Pred && op = Pred())
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
static_assert(
(hpx::traits::is_input_iterator<InIter1>::value),
(hpx::traits::is_input_iterator<FwdIter1>::value),
"Requires at least input iterator.");
static_assert(
(hpx::traits::is_input_iterator<InIter2>::value),
(hpx::traits::is_input_iterator<FwdIter2>::value),
"Requires at least input iterator.");

typedef std::integral_constant<bool,
execution::is_sequenced_execution_policy<ExPolicy>::value ||
!hpx::traits::is_forward_iterator<InIter1>::value ||
!hpx::traits::is_forward_iterator<InIter2>::value
!hpx::traits::is_forward_iterator<FwdIter1>::value ||
!hpx::traits::is_forward_iterator<FwdIter2>::value
> is_seq;
#else
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.");

typedef execution::is_sequenced_execution_policy<ExPolicy> is_seq;
#endif

typedef std::pair<InIter1, InIter2> result_type;
typedef std::pair<FwdIter1, FwdIter2> result_type;
return detail::mismatch_binary<result_type>().call(
std::forward<ExPolicy>(policy), is_seq(),
first1, last1, first2, last2, std::forward<Pred>(op));
Expand All @@ -252,11 +263,11 @@ namespace hpx { namespace parallel { inline namespace v1
: mismatch::algorithm("mismatch")
{}

template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename F>
static T
sequential(ExPolicy, InIter1 first1, InIter1 last1,
InIter2 first2, F && f)
sequential(ExPolicy, FwdIter1 first1, FwdIter1 last1,
FwdIter2 first2, F && f)
{
return std::mismatch(first1, last1, first2, std::forward<F>(f));
}
Expand Down Expand Up @@ -287,7 +298,7 @@ namespace hpx { namespace parallel { inline namespace v1
std::forward<ExPolicy>(policy),
hpx::util::make_zip_iterator(first1, first2), count, 1,
[f, tok](zip_iterator it, std::size_t part_count,
std::size_t base_idx) mutable
std::size_t base_idx) mutable -> void
{
util::loop_idx_n(
base_idx, it, part_count, tok,
Expand Down Expand Up @@ -326,14 +337,14 @@ namespace hpx { namespace parallel { inline namespace v1
/// It describes the manner in which the execution
/// of the algorithm may be parallelized and the manner
/// in which it executes the assignments.
/// \tparam InIter1 The type of the source iterators used for the
/// \tparam FwdIter1 The type of the source iterators used for the
/// first range (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// \tparam InIter2 The type of the source iterators used for the
/// forward iterator.
/// \tparam FwdIter2 The type of the source iterators used for the
/// second range (deduced).
/// This iterator type must meet the requirements of an
/// input iterator.
/// forward iterator.
/// \tparam Pred The type of an optional function/function object to use.
/// Unlike its sequential form, the parallel
/// overload of \a mismatch requires \a Pred to meet the
Expand All @@ -358,7 +369,7 @@ namespace hpx { namespace parallel { inline namespace v1
/// The signature does not need to have const &, but
/// the function must not modify the objects passed to
/// it. The types \a Type1 and \a Type2 must be such
/// that objects of types \a InIter1 and \a InIter2 can
/// that objects of types \a FwdIter1 and \a FwdIter2 can
/// be dereferenced and then implicitly converted to
/// \a Type1 and \a Type2 respectively
///
Expand All @@ -373,40 +384,51 @@ namespace hpx { namespace parallel { inline namespace v1
/// within each thread.
///
/// \returns The \a mismatch algorithm returns a
/// \a hpx::future<std::pair<InIter1, InIter2> > if the
/// \a hpx::future<std::pair<FwdIter1, FwdIter2> > if the
/// execution policy is of type
/// \a sequenced_task_policy or
/// \a parallel_task_policy and
/// returns \a std::pair<InIter1, InIter2> otherwise.
/// returns \a std::pair<FwdIter1, FwdIter2> otherwise.
/// The \a mismatch algorithm returns the first mismatching pair
/// of elements from two ranges: one defined by [first1, last1)
/// and another defined by [first2, last2).
///
template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename Pred = detail::equal_to>
inline typename std::enable_if<
execution::is_execution_policy<ExPolicy>::value,
typename util::detail::algorithm_result<
ExPolicy, std::pair<InIter1, InIter2>
ExPolicy, std::pair<FwdIter1, FwdIter2>
>::type
>::type
mismatch(ExPolicy&& policy, InIter1 first1, InIter1 last1, InIter2 first2,
mismatch(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1, FwdIter2 first2,
Pred && op = Pred())
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
static_assert(
(hpx::traits::is_input_iterator<InIter1>::value),
(hpx::traits::is_input_iterator<FwdIter1>::value),
"Requires at least input iterator.");
static_assert(
(hpx::traits::is_input_iterator<InIter2>::value),
(hpx::traits::is_input_iterator<FwdIter2>::value),
"Requires at least input iterator.");

typedef std::integral_constant<bool,
execution::is_sequenced_execution_policy<ExPolicy>::value ||
!hpx::traits::is_forward_iterator<InIter1>::value ||
!hpx::traits::is_forward_iterator<InIter2>::value
!hpx::traits::is_forward_iterator<FwdIter1>::value ||
!hpx::traits::is_forward_iterator<FwdIter2>::value
> is_seq;
#else
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.");

typedef execution::is_sequenced_execution_policy<ExPolicy> is_seq;
#endif

typedef std::pair<InIter1, InIter2> result_type;
typedef std::pair<FwdIter1, FwdIter2> result_type;
return detail::mismatch<result_type>().call(
std::forward<ExPolicy>(policy), is_seq(),
first1, last1, first2, std::forward<Pred>(op));
Expand Down

0 comments on commit 1616e86

Please sign in to comment.