Skip to content

Commit

Permalink
Fixing is_partitioned, minmax_element, lexicographical_compare algori…
Browse files Browse the repository at this point in the history 
…thms/is_heap.hpp

- flyby: add return types to lambdas
  • Loading branch information
@hkaiser
hkaiser committed Jun 27, 2017
1 parent 83a63e8 commit 064178e
Show file tree
Hide file tree
Showing 8 changed files with 113 additions and 66 deletions.
9 changes: 6 additions & 3 deletions hpx/parallel/algorithms/is_heap.hpp
View file
Expand Up @@ -64,13 +64,16 @@ namespace hpx { namespace parallel { inline namespace v1
call_with_index(
std::forward<ExPolicy>(policy), second, count, 1,
[tok, first, comp](RandIter it,
std::size_t part_size, std::size_t base_idx) mutable
std::size_t part_size, std::size_t base_idx
) mutable -> void
{
util::loop_idx_n(
base_idx, it, part_size, tok,
[&tok, first, &comp](type const& v, std::size_t i)
[&tok, first, &comp](
type const& v, std::size_t i
) -> void
{
if (comp(*(first + i / 2), v))
if (hpx::util::invoke(comp, *(first + i / 2), v))
tok.cancel(0);
});
},
Expand Down
51 changes: 30 additions & 21 deletions hpx/parallel/algorithms/is_partitioned.hpp
View file
@@ -1,4 +1,5 @@
// Copyright (c) 2015 Daniel Bourgeois
// Copyright (c) 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 All @@ -11,14 +12,15 @@
#include <hpx/config.hpp>
#include <hpx/lcos/future.hpp>
#include <hpx/traits/is_iterator.hpp>
#include <hpx/util/invoke.hpp>
#include <hpx/util/unused.hpp>

#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/execution_policy.hpp>
#include <hpx/parallel/util/cancellation_token.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/loop.hpp>
#include <hpx/parallel/util/partitioner.hpp>
#include <hpx/util/unused.hpp>

#include <algorithm>
#include <cstddef>
Expand All @@ -40,16 +42,17 @@ namespace hpx { namespace parallel { inline namespace v1
{
std::vector<hpx::future<bool> >::iterator first = res.begin();
std::vector<hpx::future<bool> >::iterator last = res.end();
while (first!=last && first->get())
while (first != last && first->get())
{
++first;
}
if (first != last)
{
++first;
while(first != last)
while (first != last)
{
if(first->get()) return false;
if (first->get())
return false;
++first;
}
}
Expand All @@ -66,12 +69,9 @@ namespace hpx { namespace parallel { inline namespace v1

template<typename ExPolicy, typename Pred>
static bool
sequential(ExPolicy, Iter first, Iter last,
Pred && pred)
sequential(ExPolicy, Iter first, Iter last, Pred && pred)
{
return std::is_partitioned(first,
last,
std::forward<Pred>(pred));
return std::is_partitioned(first, last, std::forward<Pred>(pred));
}

template <typename ExPolicy, typename Pred>
Expand All @@ -95,16 +95,17 @@ namespace hpx { namespace parallel { inline namespace v1
{
HPX_UNUSED(policy);

bool fst_bool = pred(*part_begin);
bool fst_bool = hpx::util::invoke(pred, *part_begin);
if (part_count == 1)
return fst_bool;

util::loop_n<ExPolicy>(
++part_begin, --part_count, tok,
[&fst_bool, &pred, &tok](Iter const& a) {
if (fst_bool != pred(*a))
[&fst_bool, &pred, &tok](Iter const& a) -> void
{
if (fst_bool != hpx::util::invoke(pred, *a))
{
if(fst_bool)
if (fst_bool)
fst_bool = false;
else
tok.cancel();
Expand Down Expand Up @@ -136,9 +137,9 @@ 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 InIter The type of the source iterators used for the
/// \tparam FwdIter The type of the source iterators used for the
/// This iterator type must meet the requirements of a
/// input iterator.
/// forward iterator.
/// \param policy The execution policy to use for the scheduling of
/// the iterations.
/// \param first Refers to the beginning of the sequence of elements
Expand All @@ -155,7 +156,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 type \a Type must be such that objects of
/// types \a InIter can be dereferenced and then
/// types \a FwdIter can be dereferenced and then
/// implicitly converted to Type.
///
/// The predicate operations in the parallel \a is_partitioned algorithm invoked
Expand All @@ -177,23 +178,31 @@ namespace hpx { namespace parallel { inline namespace v1
/// false. If the range [first, last) contains less than two
/// elements, the function is always true.
///
template <typename ExPolicy, typename InIter, typename Pred>
template <typename ExPolicy, typename FwdIter, typename Pred>
inline typename std::enable_if<
execution::is_execution_policy<ExPolicy>::value,
typename util::detail::algorithm_result<ExPolicy, bool>::type
>::type
is_partitioned(ExPolicy && policy, InIter first, InIter last, Pred && pred)
is_partitioned(ExPolicy && policy, FwdIter first, FwdIter last, Pred && pred)
{
#if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT)
static_assert(
(hpx::traits::is_input_iterator<InIter>::value),
(hpx::traits::is_input_iterator<FwdIter>::value),
"Requires at least input iterator.");

typedef std::integral_constant<bool,
execution::is_sequenced_execution_policy<ExPolicy>::value ||
!hpx::traits::is_forward_iterator<InIter>::value
!hpx::traits::is_forward_iterator<FwdIter>::value
> is_seq;
#else
static_assert(
(hpx::traits::is_forward_iterator<FwdIter>::value),
"Requires at least forward iterator.");

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

return detail::is_partitioned<InIter>().call(
return detail::is_partitioned<FwdIter>().call(
std::forward<ExPolicy>(policy), is_seq(), first, last,
std::forward<Pred>(pred));
}
Expand Down
23 changes: 11 additions & 12 deletions hpx/parallel/algorithms/is_sorted.hpp
View file
Expand Up @@ -76,7 +76,7 @@ namespace hpx { namespace parallel { inline namespace v1
FwdIter trail = part_begin++;
util::loop_n<ExPolicy>(
part_begin, part_size - 1,
[&trail, &tok, &pred](FwdIter it)
[&trail, &tok, &pred](FwdIter it) -> void
{
if (hpx::util::invoke(pred, *it, *trail++))
{
Expand All @@ -90,7 +90,7 @@ namespace hpx { namespace parallel { inline namespace v1

if (!tok.was_cancelled() && trail != last)
{
return !pred(*trail, *i);
return !hpx::util::invoke(pred, *trail, *i);
}
return !tok.was_cancelled();
};
Expand All @@ -102,7 +102,7 @@ namespace hpx { namespace parallel { inline namespace v1
{
return std::all_of(
boost::begin(results), boost::end(results),
[](hpx::future<bool>& val)
[](hpx::future<bool>& val) -> bool
{
return val.get();
});
Expand Down Expand Up @@ -203,11 +203,9 @@ namespace hpx { namespace parallel { inline namespace v1

template<typename ExPolicy, typename Pred>
static FwdIter
sequential(ExPolicy, FwdIter first, FwdIter last,
Pred && pred)
sequential(ExPolicy, FwdIter first, FwdIter last, Pred && pred)
{
return std::is_sorted_until(first, last,
std::forward<Pred>(pred));
return std::is_sorted_until(first, last, std::forward<Pred>(pred));
}

template <typename ExPolicy, typename Pred>
Expand All @@ -228,20 +226,21 @@ namespace hpx { namespace parallel { inline namespace v1
if (count <= 1)
return result::get(std::move(last));


util::cancellation_token<difference_type> tok(count);
return util::partitioner<ExPolicy, FwdIter, void>::
call_with_index(
std::forward<ExPolicy>(policy), first, count, 1,
[tok, pred, last](FwdIter part_begin, std::size_t part_size,
std::size_t base_idx) mutable
std::size_t base_idx) mutable -> void
{
FwdIter trail = part_begin++;
util::loop_idx_n(++base_idx, part_begin,
part_size - 1, tok,
[&trail, &tok, &pred](reference& v, std::size_t ind)
[&trail, &tok, &pred](
reference& v, std::size_t ind
) -> void
{
if (pred(v, *trail++))
if (hpx::util::invoke(pred, v, *trail++))
{
tok.cancel(ind);
}
Expand All @@ -254,7 +253,7 @@ namespace hpx { namespace parallel { inline namespace v1
if (!tok.was_cancelled(base_idx + part_size)
&& trail != last)
{
if (pred(*trail, *i))
if (hpx::util::invoke(pred, *trail, *i))
{
tok.cancel(base_idx + part_size);
}
Expand Down
54 changes: 34 additions & 20 deletions hpx/parallel/algorithms/lexicographical_compare.hpp
View file
@@ -1,4 +1,5 @@
// Copyright (c) 2014 Grant Mercer
// Copyright (c) 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 All @@ -10,6 +11,7 @@

#include <hpx/config.hpp>
#include <hpx/traits/is_iterator.hpp>
#include <hpx/util/invoke.hpp>

#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/detail/predicates.hpp>
Expand All @@ -36,17 +38,17 @@ namespace hpx { namespace parallel { inline namespace v1
{
/// \cond NOINTERNAL
struct lexicographical_compare
: public detail::algorithm<lexicographical_compare, bool>
: public detail::algorithm<lexicographical_compare, bool>
{
lexicographical_compare()
: lexicographical_compare::algorithm("lexicographical_compare")
{}

template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename Pred>
static bool
sequential(ExPolicy, InIter1 first1, InIter1 last1, InIter2 first2,
InIter2 last2, Pred && pred)
sequential(ExPolicy, FwdIter1 first1, FwdIter1 last1, FwdIter2 first2,
FwdIter2 last2, Pred && pred)
{
return std::lexicographical_compare(first1, last1, first2, last2, pred);
}
Expand Down Expand Up @@ -86,15 +88,16 @@ namespace hpx { namespace parallel { inline namespace v1
std::forward<ExPolicy>(policy),
make_zip_iterator(first1, first2), count, 1,
[pred, 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,
[&pred, &tok](reference t, std::size_t i)
[&pred, &tok](reference t, std::size_t i) -> void
{
using hpx::util::get;
if (pred(get<0>(t), get<1>(t)) ||
pred(get<1>(t), get<0>(t)))
using hpx::util::invoke;
if (invoke(pred, get<0>(t), get<1>(t)) ||
invoke(pred, get<1>(t), get<0>(t)))
{
tok.cancel(i);
}
Expand All @@ -108,7 +111,7 @@ namespace hpx { namespace parallel { inline namespace v1
std::advance(first2, mismatched);

if (first1 != last1 && first2 != last2)
return pred(*first1, *first2);
return hpx::util::invoke(pred, *first1, *first2);

return first2 != last2;
});
Expand All @@ -129,14 +132,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 lexicographical_compare requires \a Pred to
Expand Down Expand Up @@ -192,27 +195,38 @@ namespace hpx { namespace parallel { inline namespace v1
/// it returns false.
/// range [first2, last2), it returns false.
///
template <typename ExPolicy, typename InIter1, typename InIter2,
template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
typename Pred = detail::less>
inline typename std::enable_if<
execution::is_execution_policy<ExPolicy>::value,
typename util::detail::algorithm_result<ExPolicy, bool>::type
>::type
lexicographical_compare(ExPolicy && policy, InIter1 first1, InIter1 last1,
InIter2 first2, InIter2 last2, Pred && pred = Pred())
lexicographical_compare(ExPolicy && policy, FwdIter1 first1, FwdIter1 last1,
FwdIter2 first2, FwdIter2 last2, Pred && pred = 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

return detail::lexicographical_compare().call(
std::forward<ExPolicy>(policy), is_seq(),
Expand Down

0 comments on commit 064178e

Please sign in to comment.