algorithm.hpp

 
#ifndef UFO_EXECUTION_ALGORITHM_HPP
#define UFO_EXECUTION_ALGORITHM_HPP
 
// UFO
#include <ufo/execution/execution.hpp>
 
// STL
#include <algorithm>
#include <atomic>
#include <concepts>
#include <functional>
#include <iterator>
#include <mutex>
#include <ranges>
#include <utility>
 
namespace ufo
{
using execution::ExecutionPolicy;
/**************************************************************************************
|                                                                                     |
|                                      For each                                       |
|                                                                                     |
**************************************************************************************/
 
template <std::integral Index, class UnaryFunc, class Proj = std::identity>
constexpr UnaryFunc for_each(Index first, Index last, UnaryFunc f, Proj proj = {})
{
    for (; last != first; ++first) {
        std::invoke(f, std::invoke(proj, first));
    }
    return f;
}
 
template <ufo::execution::ExecutionPolicy T, std::integral Index, class UnaryFunc,
          class Proj = std::identity>
void for_each(T&& policy, Index first, Index last, UnaryFunc f, Proj proj = {})
{
    if constexpr (execution::STLBackend<T>) {
        auto r = std::views::iota(first, last) | std::views::transform(std::move(proj));
        std::for_each(execution::toSTL(std::forward<T>(policy)), std::ranges::begin(r),
                      std::ranges::end(r), f);
    }
#if defined(UFO_PAR_GCD)
    else if constexpr (execution::GCDBackend<T>) {
        dispatch_apply(static_cast<std::size_t>(last - first),
                       dispatch_get_global_queue(0, 0), ^(std::size_t i) {
                           std::invoke(f, std::invoke(proj, first + static_cast<Index>(i)));
                       });
    }
#endif
#if defined(UFO_PAR_TBB)
    else if constexpr (execution::TBBBackend<T>) {
        oneapi::tbb::parallel_for(
            first, last, [f, proj](Index i) { std::invoke(f, std::invoke(proj, i)); });
    }
#endif
    else if constexpr (execution::OMPBackend<T>) {
        auto s_first = static_cast<std::make_signed_t<Index>>(first);
        auto s_last  = static_cast<std::make_signed_t<Index>>(last);
#pragma omp parallel for
        for (auto i = s_first; i < s_last; ++i) {
            std::invoke(f, std::invoke(proj, static_cast<Index>(i)));
        }
    } else {
        std::unreachable();
    }
}
 
template <std::input_iterator InputIt, class UnaryFunc, class Proj = std::identity>
constexpr UnaryFunc for_each(InputIt first, InputIt last, UnaryFunc f, Proj proj = {})
{
    for (; first != last; ++first) {
        std::invoke(f, std::invoke(proj, *first));
    }
    return f;
}
 
template <ufo::execution::ExecutionPolicy T, std::random_access_iterator RandomIt,
          class UnaryFunc, class Proj = std::identity>
void for_each(T&& policy, RandomIt first, RandomIt last, UnaryFunc f, Proj proj = {})
{
    if constexpr (execution::STLBackend<T>) {
        for_each(
            std::forward<T>(policy), std::size_t{},
            static_cast<std::size_t>(std::distance(first, last)),
            [first, f, proj](std::size_t i) { std::invoke(f, std::invoke(proj, first[i])); });
    }
#if defined(UFO_PAR_GCD)
    else if constexpr (execution::GCDBackend<T>) {
        std::size_t s = static_cast<std::size_t>(std::distance(first, last));
        dispatch_apply(s, dispatch_get_global_queue(0, 0), ^(std::size_t i) {
            std::invoke(f, std::invoke(proj, first[i]));
        });
    }
#endif
#if defined(UFO_PAR_TBB)
    else if constexpr (execution::TBBBackend<T>) {
        // TODO: Benchmark against parallel_for_each
        std::size_t s = static_cast<std::size_t>(std::distance(first, last));
        oneapi::tbb::parallel_for(std::size_t{}, s, [first, f, proj](std::size_t i) {
            std::invoke(f, std::invoke(proj, first[i]));
        });
    }
#endif
    else if constexpr (execution::OMPBackend<T>) {
        auto s = static_cast<std::make_signed_t<std::size_t>>(std::distance(first, last));
#pragma omp parallel for
        for (auto i = static_cast<decltype(s)>(0); i < s; ++i) {
            std::invoke(f, std::invoke(proj, first[i]));
        }
    } else {
        std::unreachable();
    }
}
 
template <std::ranges::input_range Range, class UnaryFunc, class Proj = std::identity>
  requires(!ufo::execution::ExecutionPolicy<std::remove_cvref_t<Range>>)
constexpr std::ranges::for_each_result<std::ranges::iterator_t<Range>, UnaryFunc>
for_each(Range&& r, UnaryFunc f, Proj proj = {})
{
    return std::ranges::for_each(std::forward<Range>(r), std::move(f), std::move(proj));
}
 
template <ufo::execution::ExecutionPolicy T, std::ranges::random_access_range Range,
          class UnaryFunc, class Proj = std::identity>
void for_each(T&& policy, Range&& r, UnaryFunc f, Proj proj = {})
{
    ufo::for_each(std::forward<T>(policy), std::ranges::begin(r), std::ranges::end(r),
                  std::move(f), std::move(proj));
}
 
/**************************************************************************************
|                                                                                     |
|                                      Transform                                      |
|                                                                                     |
**************************************************************************************/
 
template <std::input_iterator InputIt, class OutputIt, class UnaryOp,
          class Proj = std::identity>
constexpr OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first,
                             UnaryOp unary_op, Proj proj = {})
{
    for (; first1 != last1; ++first1, ++d_first) {
        *d_first = std::invoke(unary_op, std::invoke(proj, *first1));
    }
    return d_first;
}
 
template <ufo::execution::ExecutionPolicy T, std::random_access_iterator RandomIt1,
          std::random_access_iterator RandomIt2, class UnaryOp,
          class Proj = std::identity>
  requires(!std::input_or_output_iterator<UnaryOp>)
 
RandomIt2 transform(T&& policy, RandomIt1 first1, RandomIt1 last1, RandomIt2 d_first,
                    UnaryOp unary_op, Proj proj = {})
{
    if constexpr (execution::STLBackend<T>) {
        std::transform(execution::toSTL(std::forward<T>(policy)), first1, last1, d_first,
                       [&unary_op, &proj](auto&& x) {
                           return std::invoke(unary_op,
                                              std::invoke(proj, std::forward<decltype(x)>(x)));
                       });
        return d_first + std::distance(first1, last1);
    } else {
        std::size_t s = static_cast<std::size_t>(std::distance(first1, last1));
        for_each(std::forward<T>(policy), std::size_t{}, s,
                 [first1, d_first, unary_op, proj](std::size_t i) {
                     d_first[i] = std::invoke(unary_op, std::invoke(proj, first1[i]));
                 });
 
        return d_first + s;
    }
}
 
template <std::ranges::input_range Range1, std::weakly_incrementable OutputIt,
          class UnaryOp, class Proj = std::identity>
  requires(
      !ufo::execution::ExecutionPolicy<std::remove_cvref_t<Range1>> &&
      std::indirectly_writable<
          OutputIt, std::indirect_result_t<
                        UnaryOp, std::projected<std::ranges::iterator_t<Range1>, Proj>>>)
constexpr std::ranges::unary_transform_result<std::ranges::iterator_t<Range1>, OutputIt>
transform(Range1&& r1, OutputIt d_first, UnaryOp unary_op, Proj proj = {})
{
    return std::ranges::transform(std::forward<Range1>(r1), d_first, unary_op,
                                  std::move(proj));
}
 
template <ufo::execution::ExecutionPolicy T, std::ranges::random_access_range Range1,
          std::random_access_iterator RandomIt2, class UnaryOp,
          class Proj = std::identity>
  requires(
      std::indirectly_writable<
          RandomIt2, std::indirect_result_t<
                         UnaryOp, std::projected<std::ranges::iterator_t<Range1>, Proj>>>)
RandomIt2 transform(T&& policy, Range1&& r1, RandomIt2 d_first, UnaryOp unary_op,
                    Proj proj = {})
{
    return ufo::transform(std::forward<T>(policy), std::ranges::begin(r1),
                          std::ranges::end(r1), d_first, std::move(unary_op),
                          std::move(proj));
}
 
template <std::input_iterator InputIt1, std::input_iterator InputIt2, class OutputIt,
          class BinaryOp, class Proj1 = std::identity, class Proj2 = std::identity>
constexpr OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                             OutputIt d_first, BinaryOp binary_op, Proj1 proj1 = {},
                             Proj2 proj2 = {})
{
    for (; first1 != last1; ++first1, ++first2, ++d_first) {
        *d_first =
            std::invoke(binary_op, std::invoke(proj1, *first1), std::invoke(proj2, *first2));
    }
    return d_first;
}
 
template <ufo::execution::ExecutionPolicy T, std::random_access_iterator RandomIt1,
          std::random_access_iterator RandomIt2, std::random_access_iterator RandomIt3,
          class BinaryOp, class Proj1 = std::identity, class Proj2 = std::identity>
RandomIt3 transform(T&& policy, RandomIt1 first1, RandomIt1 last1, RandomIt2 first2,
                    RandomIt3 d_first, BinaryOp binary_op, Proj1 proj1 = {},
                    Proj2 proj2 = {})
{
    if constexpr (execution::STLBackend<T>) {
        std::transform(execution::toSTL(std::forward<T>(policy)), first1, last1, first2,
                       d_first, [&binary_op, &proj1, &proj2](auto&& x, auto&& y) {
                           return std::invoke(binary_op,
                                              std::invoke(proj1, std::forward<decltype(x)>(x)),
                                              std::invoke(proj2, std::forward<decltype(y)>(y)));
                       });
        return d_first + std::distance(first1, last1);
    } else {
        std::size_t s = static_cast<std::size_t>(std::distance(first1, last1));
        for_each(std::forward<T>(policy), std::size_t{}, s,
                 [first1, first2, d_first, binary_op, proj1, proj2](std::size_t i) {
                     d_first[i] = std::invoke(binary_op, std::invoke(proj1, first1[i]),
                                              std::invoke(proj2, first2[i]));
                 });
 
        return d_first + s;
    }
}
 
template <std::ranges::input_range Range1, std::input_iterator InputIt2,
          std::weakly_incrementable OutputIt, class BinaryOp, class Proj1 = std::identity,
          class Proj2 = std::identity>
  requires(
      !ufo::execution::ExecutionPolicy<std::remove_cvref_t<Range1>> &&
      std::indirectly_writable<
          OutputIt, std::indirect_result_t<
                        BinaryOp, std::projected<std::ranges::iterator_t<Range1>, Proj1>,
                        std::projected<InputIt2, Proj2>>>)
constexpr std::ranges::binary_transform_result<std::ranges::iterator_t<Range1>, InputIt2,
                                               OutputIt>
transform(Range1&& r1, InputIt2 first2, OutputIt d_first, BinaryOp binary_op,
          Proj1 proj1 = {}, Proj2 proj2 = {})
{
    // std::ranges::transform for binary expects a range for the second input too.
    // But UFOMap provides an iterator. We can wrap it in an unbounded view if we know it's
    // safe, or just implement it manually. Actually, std::ranges::transform (binary)
    // doesn't have an iterator-based overload for the second range. So we implement it
    // manually to maintain the same interface.
    auto first1 = std::ranges::begin(r1);
    auto last1  = std::ranges::end(r1);
    for (; first1 != last1; ++first1, ++first2, ++d_first) {
        *d_first =
            std::invoke(binary_op, std::invoke(proj1, *first1), std::invoke(proj2, *first2));
    }
    return {std::move(first1), std::move(first2), std::move(d_first)};
}
 
template <ufo::execution::ExecutionPolicy T, std::ranges::random_access_range Range1,
          std::random_access_iterator RandomIt2, std::random_access_iterator RandomIt3,
          class BinaryOp, class Proj1 = std::identity, class Proj2 = std::identity>
  requires(
      std::indirectly_writable<
          RandomIt3, std::indirect_result_t<
                         BinaryOp, std::projected<std::ranges::iterator_t<Range1>, Proj1>,
                         std::projected<RandomIt2, Proj2>>>)
RandomIt3 transform(T&& policy, Range1&& r1, RandomIt2 first2, RandomIt3 d_first,
                    BinaryOp binary_op, Proj1 proj1 = {}, Proj2 proj2 = {})
{
    return ufo::transform(std::forward<T>(policy), std::ranges::begin(r1),
                          std::ranges::end(r1), first2, d_first, std::move(binary_op),
                          std::move(proj1), std::move(proj2));
}
/**************************************************************************************
|                                                                                     |
|                                       Reduce                                        |
|                                                                                     |
**************************************************************************************/
 
template <ufo::execution::ExecutionPolicy P, std::input_iterator InputIt, class T>
[[nodiscard]] T reduce(P&& policy, InputIt first, InputIt last, T init)
{
    if constexpr (execution::STLBackend<P>) {
        return std::reduce(execution::toSTL(std::forward<P>(policy)), first, last, init);
    } else {
        // Generic implementation using for_each
        // For parallel backends, we use a simple approach here for now.
        // A more efficient implementation would use backend-specific features.
        std::mutex m;
        for_each(std::forward<P>(policy), first, last, [&](auto const& x) {
            std::lock_guard lock(m);
            init = init + x;
        });
        return init;
    }
}
 
template <ufo::execution::ExecutionPolicy P, std::ranges::input_range Range, class T>
[[nodiscard]] T reduce(P&& policy, Range&& r, T init)
{
    return reduce(std::forward<P>(policy), std::ranges::begin(r), std::ranges::end(r),
                  std::move(init));
}
 
/**************************************************************************************
|                                                                                     |
|                                     Predicates                                      |
|                                                                                     |
**************************************************************************************/
 
template <ufo::execution::ExecutionPolicy P, std::input_iterator InputIt, class UnaryPred>
[[nodiscard]] bool any_of(P&& policy, InputIt first, InputIt last, UnaryPred p)
{
    if constexpr (execution::STLBackend<P>) {
        return std::any_of(execution::toSTL(std::forward<P>(policy)), first, last, p);
    } else {
        std::atomic<bool> found = false;
        for_each(std::forward<P>(policy), first, last, [&](auto const& x) {
            if (p(x)) {
                found = true;
            }
        });
        return found;
    }
}
 
template <ufo::execution::ExecutionPolicy P, std::ranges::input_range Range,
          class UnaryPred>
[[nodiscard]] bool any_of(P&& policy, Range&& r, UnaryPred p)
{
    return any_of(std::forward<P>(policy), std::ranges::begin(r), std::ranges::end(r),
                  std::move(p));
}
 
template <ufo::execution::ExecutionPolicy P, std::input_iterator InputIt, class UnaryPred>
[[nodiscard]] bool all_of(P&& policy, InputIt first, InputIt last, UnaryPred p)
{
    return !any_of(std::forward<P>(policy), first, last,
                   [&p](auto const& x) { return !p(x); });
}
 
template <ufo::execution::ExecutionPolicy P, std::ranges::input_range Range,
          class UnaryPred>
[[nodiscard]] bool all_of(P&& policy, Range&& r, UnaryPred p)
{
    return all_of(std::forward<P>(policy), std::ranges::begin(r), std::ranges::end(r),
                  std::move(p));
}
 
/**************************************************************************************
|                                                                                     |
|                                      Searching                                      |
|                                                                                     |
**************************************************************************************/
 
template <ufo::execution::ExecutionPolicy P, std::random_access_iterator RandomIt,
          class UnaryPred>
[[nodiscard]] RandomIt find_if(P&& policy, RandomIt first, RandomIt last, UnaryPred p)
{
    if constexpr (execution::STLBackend<P>) {
        return std::find_if(execution::toSTL(std::forward<P>(policy)), first, last, p);
    } else {
        std::atomic<std::size_t> min_idx =
            static_cast<std::size_t>(std::distance(first, last));
        for_each(std::forward<P>(policy), std::size_t{}, min_idx.load(), [&](std::size_t i) {
            if (p(first[i])) {
                std::size_t expected = min_idx.load();
                while (i < expected && !min_idx.compare_exchange_weak(expected, i)) {
                    // Keep trying
                }
            }
        });
        return first + min_idx.load();
    }
}
 
template <ufo::execution::ExecutionPolicy P, std::ranges::random_access_range Range,
          class UnaryPred>
[[nodiscard]] auto find_if(P&& policy, Range&& r, UnaryPred p)
{
    return find_if(std::forward<P>(policy), std::ranges::begin(r), std::ranges::end(r),
                   std::move(p));
}
 
/**************************************************************************************
|                                                                                     |
|                                      Counting                                       |
|                                                                                     |
**************************************************************************************/
 
template <ufo::execution::ExecutionPolicy P, std::input_iterator InputIt, class UnaryPred>
[[nodiscard]] std::size_t count_if(P&& policy, InputIt first, InputIt last, UnaryPred p)
{
    if constexpr (execution::STLBackend<P>) {
        return std::count_if(execution::toSTL(std::forward<P>(policy)), first, last, p);
    } else {
        std::atomic<std::size_t> count = 0;
        for_each(std::forward<P>(policy), first, last, [&](auto const& x) {
            if (p(x)) {
                ++count;
            }
        });
        return count.load();
    }
}
 
template <ufo::execution::ExecutionPolicy P, std::ranges::input_range Range,
          class UnaryPred>
[[nodiscard]] std::size_t count_if(P&& policy, Range&& r, UnaryPred p)
{
    return count_if(std::forward<P>(policy), std::ranges::begin(r), std::ranges::end(r),
                    std::move(p));
}
 
}  // namespace ufo
 
#endif  // UFO_EXECUTION_ALGORITHM_HPP