Skip to content

Qwen3.8-Flash-Next on any consumer hardware: one-click install for Windows / Linux. Strata inference engine, OpenAI/Anthropic API on localhost, optional image input.

C++
122 KB
Raw Blame
//==---- algorithm.h ------------------------------*- C++ -*----------------==//
//
// Copyright (C) Intel Corporation
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// See https://llvm.org/LICENSE.txt for license information.
//
//===----------------------------------------------------------------------===//

#ifndef __DPCT_ALGORITHM_H__
#define __DPCT_ALGORITHM_H__

#include <oneapi/dpl/algorithm>
#include <oneapi/dpl/execution>
#include <oneapi/dpl/numeric>

#include "functional.h"
#include "iterators.h"
#include "vector.h"

namespace dpct {

namespace internal {
// This function is ported from oneDPL with the check for an FPGA policy
// removed. This function should be used to wrap a provided policy when multiple
// oneDPL calls are made to ensure unique kernel names.
template <template <typename> class NewKernelName, typename Policy>
auto make_wrapped_policy(Policy &&policy)
    -> decltype(oneapi::dpl::execution::make_device_policy<
                NewKernelName<typename ::std::decay_t<Policy>::kernel_name>>(
        ::std::forward<Policy>(policy))) {
  return oneapi::dpl::execution::make_device_policy<
      NewKernelName<typename ::std::decay_t<Policy>::kernel_name>>(
      ::std::forward<Policy>(policy));
}

template <typename Name> class partition_call1;

template <typename Name> class partition_call2;

template <typename Name> class copy_before_partition;

template <typename Name> class reverse_partition;

template <typename Name> class copy_call1;

template <typename Name> class copy_call2;

}; // namespace internal


template <typename Policy, typename Iter1, typename Iter2, typename Pred,
          typename T>
void replace_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p,
                const T &new_value) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  std::transform(
      std::forward<Policy>(policy), first, last, mask, first,
      internal::replace_if_fun<typename std::iterator_traits<Iter1>::value_type,
                               Pred>(p, new_value));
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Pred, typename T>
Iter3 replace_copy_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
                      Iter3 result, Pred p, const T &new_value) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  return std::transform(
      std::forward<Policy>(policy), first, last, mask, result,
      internal::replace_if_fun<typename std::iterator_traits<Iter3>::value_type,
                               Pred>(p, new_value));
}

template <typename Policy, typename Iter1, typename Iter2, typename Pred>
internal::enable_if_hetero_execution_policy<Policy, Iter1>
remove_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using oneapi::dpl::make_zip_iterator;
  using policy_type = typename std::decay<Policy>::type;
  using internal::__buffer;
  using ValueType = typename std::iterator_traits<Iter1>::value_type;

  __buffer<ValueType> _tmp(std::distance(first, last));

  auto end = std::copy_if(
      policy, make_zip_iterator(first, mask),
      make_zip_iterator(last, mask + std::distance(first, last)),
      make_zip_iterator(_tmp.get(), oneapi::dpl::discard_iterator()),
      internal::negate_predicate_key_fun<Pred>(p));
  return std::copy(std::forward<Policy>(policy), _tmp.get(),
                   std::get<0>(end.base()), first);
}

template <typename Policy, typename Iter1, typename Iter2, typename Pred>
typename std::enable_if<!internal::is_hetero_execution_policy<
                            typename std::decay<Policy>::type>::value,
                        Iter1>::type
remove_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using oneapi::dpl::make_zip_iterator;
  using policy_type = typename std::decay<Policy>::type;
  using ValueType = typename std::iterator_traits<Iter1>::value_type;

  std::vector<ValueType> _tmp(std::distance(first, last));

  auto end = std::copy_if(
      policy, make_zip_iterator(first, mask),
      make_zip_iterator(last, mask + std::distance(first, last)),
      make_zip_iterator(_tmp.begin(), oneapi::dpl::discard_iterator()),
      internal::negate_predicate_key_fun<Pred>(p));
  return std::copy(policy, _tmp.begin(), std::get<0>(end.base()), first);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Pred>
Iter3 remove_copy_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
                     Iter3 result, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using oneapi::dpl::make_zip_iterator;
  auto ret_val = std::remove_copy_if(
      std::forward<Policy>(policy), make_zip_iterator(first, mask),
      make_zip_iterator(last, mask + std::distance(first, last)),
      make_zip_iterator(result, oneapi::dpl::discard_iterator()),
      internal::predicate_key_fun<Pred>(p));
  return std::get<0>(ret_val.base());
}

template <class Policy, class Iter1, class Iter2, class BinaryPred>
std::pair<Iter1, Iter2> unique(Policy &&policy, Iter1 keys_first,
                               Iter1 keys_last, Iter2 values_first,
                               BinaryPred binary_pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::unique(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first, values_first),
      oneapi::dpl::make_zip_iterator(
          keys_last, values_first + std::distance(keys_first, keys_last)),
      internal::compare_key_fun<BinaryPred>(binary_pred));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_first, values_first), ret_val);
  return std::make_pair(keys_first + n1, values_first + n1);
}

template <class Policy, class Iter1, class Iter2>
std::pair<Iter1, Iter2> unique(Policy &&policy, Iter1 keys_first,
                               Iter1 keys_last, Iter2 values_first) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using T = typename std::iterator_traits<Iter1>::value_type;
  return unique(std::forward<Policy>(policy), keys_first, keys_last,
                values_first, std::equal_to<T>());
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class BinaryPred>
std::pair<Iter3, Iter4> unique_copy(Policy &&policy, Iter1 keys_first,
                                    Iter1 keys_last, Iter2 values_first,
                                    Iter3 keys_result, Iter4 values_result,
                                    BinaryPred binary_pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::unique_copy(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first, values_first),
      oneapi::dpl::make_zip_iterator(
          keys_last, values_first + std::distance(keys_first, keys_last)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::unique_fun<BinaryPred>(binary_pred));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4>
std::pair<Iter3, Iter4> unique_copy(Policy &&policy, Iter1 keys_first,
                                    Iter1 keys_last, Iter2 values_first,
                                    Iter3 keys_result, Iter4 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using T = typename std::iterator_traits<Iter1>::value_type;
  auto comp = std::equal_to<T>();
  return unique_copy(std::forward<Policy>(policy), keys_first, keys_last,
                     values_first, keys_result, values_result, comp);
}

template <typename Policy, typename Iter, typename Pred>
Iter partition_point(Policy &&policy, Iter first, Iter last, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter>::iterator_category,
                   std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  return std::find_if_not(std::forward<Policy>(policy), first, last, p);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Pred>
Iter3 copy_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
              Iter3 result, Pred pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::copy_if(
      std::forward<Policy>(policy), oneapi::dpl::make_zip_iterator(first, mask),
      oneapi::dpl::make_zip_iterator(last, mask + std::distance(first, last)),
      oneapi::dpl::make_zip_iterator(result, oneapi::dpl::discard_iterator()),
      internal::predicate_key_fun<Pred>(pred));
  return std::get<0>(ret_val.base());
}

template <class Policy, class Iter1, class Iter2, class UnaryOperation,
          class Pred>
Iter2 transform_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 result,
                   UnaryOperation unary_op, Pred pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using T = typename std::iterator_traits<Iter1>::value_type;
  const auto n = std::distance(first, last);
  std::for_each(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(first, result),
      oneapi::dpl::make_zip_iterator(first, result) + n,
      internal::transform_if_fun<T, Pred, UnaryOperation>(pred, unary_op));
  return result + n;
}

template <class Policy, class Iter1, class Iter2, class Iter3,
          class UnaryOperation, class Pred>
Iter3 transform_if(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
                   Iter3 result, UnaryOperation unary_op, Pred pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using T = typename std::iterator_traits<Iter1>::value_type;
  using Ref1 = typename std::iterator_traits<Iter1>::reference;
  using Ref2 = typename std::iterator_traits<Iter2>::reference;
  const auto n = std::distance(first, last);
  std::for_each(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(first, mask, result),
      oneapi::dpl::make_zip_iterator(first, mask, result) + n,
      internal::transform_if_unary_zip_mask_fun<T, Pred, UnaryOperation>(
          pred, unary_op));
  return result + n;
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class BinaryOperation, class Pred>
Iter4 transform_if(Policy &&policy, Iter1 first1, Iter1 last1, Iter2 first2,
                   Iter3 mask, Iter4 result, BinaryOperation binary_op,
                   Pred pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  const auto n = std::distance(first1, last1);
  using ZipIterator =
      typename oneapi::dpl::zip_iterator<Iter1, Iter2, Iter3, Iter4>;
  using T = typename std::iterator_traits<ZipIterator>::value_type;
  std::for_each(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(first1, first2, mask, result),
      oneapi::dpl::make_zip_iterator(last1, first2 + n, mask + n, result + n),
      internal::transform_if_zip_mask_fun<T, Pred, BinaryOperation>(pred,
                                                                    binary_op));
  return result + n;
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename OutputIter>
void scatter(Policy &&policy, InputIter1 first, InputIter1 last, InputIter2 map,
             OutputIter result) {
  static_assert(
      std::is_same<typename std::iterator_traits<InputIter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter2>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<OutputIter>::iterator_category,
              std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  oneapi::dpl::copy(policy, first, last,
                    oneapi::dpl::make_permutation_iterator(result, map));
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename OutputIter>
OutputIter gather(Policy &&policy, InputIter1 map_first, InputIter1 map_last,
                  InputIter2 input_first, OutputIter result) {
  static_assert(
      std::is_same<typename std::iterator_traits<InputIter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter2>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<OutputIter>::iterator_category,
              std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto perm_begin =
      oneapi::dpl::make_permutation_iterator(input_first, map_first);
  const int n = ::std::distance(map_first, map_last);

  return oneapi::dpl::copy(policy, perm_begin, perm_begin + n, result);
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename InputIter3, typename OutputIter, typename Predicate>
void scatter_if(Policy &&policy, InputIter1 first, InputIter1 last,
                InputIter2 map, InputIter3 mask, OutputIter result,
                Predicate pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<InputIter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter2>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter3>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<OutputIter>::iterator_category,
              std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  dpct::transform_if(
      ::std::forward<Policy>(policy), first, last, mask,
      oneapi::dpl::make_permutation_iterator(result, map),
      [=](auto &&v) { return v; }, [=](auto &&m) { return pred(m); });
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename InputIter3, typename OutputIter>
void scatter_if(Policy &&policy, InputIter1 first, InputIter1 last,
                InputIter2 map, InputIter3 mask, OutputIter result) {
  scatter_if(::std::forward<Policy>(policy), first, last, map, mask, result,
             internal::no_op_fun());
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename InputIter3, typename OutputIter, typename Predicate>
OutputIter gather_if(Policy &&policy, InputIter1 map_first, InputIter1 map_last,
                     InputIter2 mask, InputIter3 input_first, OutputIter result,
                     Predicate pred) {
  static_assert(
      std::is_same<typename std::iterator_traits<InputIter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter2>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<InputIter3>::iterator_category,
              std::random_access_iterator_tag>::value &&
          std::is_same<
              typename std::iterator_traits<OutputIter>::iterator_category,
              std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto perm_begin =
      oneapi::dpl::make_permutation_iterator(input_first, map_first);
  const int n = std::distance(map_first, map_last);

  return dpct::transform_if(
      ::std::forward<Policy>(policy), perm_begin, perm_begin + n, mask, result,
      [=](auto &&v) { return v; }, [=](auto &&m) { return pred(m); });
}

template <typename Policy, typename InputIter1, typename InputIter2,
          typename InputIter3, typename OutputIter>
OutputIter gather_if(Policy &&policy, InputIter1 map_first, InputIter1 map_last,
                     InputIter2 mask, InputIter3 input_first,
                     OutputIter result) {
  return gather_if(::std::forward<Policy>(policy), map_first, map_last, mask,
                   input_first, result, internal::no_op_fun());
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Iter5, typename Iter6>
std::pair<Iter5, Iter6>
merge(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1, Iter2 keys_first2,
      Iter2 keys_last2, Iter3 values_first1, Iter4 values_first2,
      Iter5 keys_result, Iter6 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto n1 = std::distance(keys_first1, keys_last1);
  auto n2 = std::distance(keys_first2, keys_last2);
  std::merge(std::forward<Policy>(policy),
             oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
             oneapi::dpl::make_zip_iterator(keys_last1, values_first1 + n1),
             oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
             oneapi::dpl::make_zip_iterator(keys_last2, values_first2 + n2),
             oneapi::dpl::make_zip_iterator(keys_result, values_result),
             internal::compare_key_fun<>());
  return std::make_pair(keys_result + n1 + n2, values_result + n1 + n2);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Iter5, typename Iter6, typename Comp>
std::pair<Iter5, Iter6>
merge(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1, Iter2 keys_first2,
      Iter2 keys_last2, Iter3 values_first1, Iter4 values_first2,
      Iter5 keys_result, Iter6 values_result, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto n1 = std::distance(keys_first1, keys_last1);
  auto n2 = std::distance(keys_first2, keys_last2);
  std::merge(std::forward<Policy>(policy),
             oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
             oneapi::dpl::make_zip_iterator(keys_last1, values_first1 + n1),
             oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
             oneapi::dpl::make_zip_iterator(keys_last2, values_first2 + n2),
             oneapi::dpl::make_zip_iterator(keys_result, values_result),
             internal::compare_key_fun<Comp>(comp));
  return std::make_pair(keys_result + n1 + n2, values_result + n1 + n2);
}

template <class Policy, class Iter, class T>
void iota(Policy &&policy, Iter first, Iter last, T init, T step) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter>::iterator_category,
                   std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using DiffSize = typename std::iterator_traits<Iter>::difference_type;
  std::transform(
      std::forward<Policy>(policy), oneapi::dpl::counting_iterator<DiffSize>(0),
      oneapi::dpl::counting_iterator<DiffSize>(std::distance(first, last)),
      first, internal::sequence_fun<T>(init, step));
}

template <class Policy, class Iter, class T>
void iota(Policy &&policy, Iter first, Iter last, T init) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter>::iterator_category,
                   std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  iota(std::forward<Policy>(policy), first, last, init, T(1));
}

template <class Policy, class Iter>
void iota(Policy &&policy, Iter first, Iter last) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter>::iterator_category,
                   std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using DiffSize = typename std::iterator_traits<Iter>::difference_type;
  iota(std::forward<Policy>(policy), first, last, DiffSize(0), DiffSize(1));
}

template <class Policy, class Iter1, class Iter2, class Comp>
void sort(Policy &&policy, Iter1 keys_first, Iter1 keys_last,
          Iter2 values_first, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  oneapi::dpl::sort_by_key(std::forward<Policy>(policy), keys_first, keys_last,
                           values_first, comp);
}

template <class Policy, class Iter1, class Iter2>
void sort(Policy &&policy, Iter1 keys_first, Iter1 keys_last,
          Iter2 values_first) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  sort(std::forward<Policy>(policy), keys_first, keys_last, values_first,
       internal::__less());
}

template <class Policy, class Iter1, class Iter2, class Comp>
void stable_sort(Policy &&policy, Iter1 keys_first, Iter1 keys_last,
                 Iter2 values_first, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  oneapi::dpl::stable_sort_by_key(std::forward<Policy>(policy), keys_first,
                                  keys_last, values_first, comp);
}

template <class Policy, class Iter1, class Iter2>
void stable_sort(Policy &&policy, Iter1 keys_first, Iter1 keys_last,
                 Iter2 values_first) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  stable_sort(std::forward<Policy>(policy), keys_first, keys_last, values_first,
              internal::__less());
}

template <class Policy, class Iter, class Operator>
void for_each_index(Policy &&policy, Iter first, Iter last, Operator unary_op) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter>::iterator_category,
                   std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  using DiffSize = typename std::iterator_traits<Iter>::difference_type;
  std::transform(
      std::forward<Policy>(policy), oneapi::dpl::counting_iterator<DiffSize>(0),
      oneapi::dpl::counting_iterator<DiffSize>(std::distance(first, last)),
      first, unary_op);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5>
std::pair<Iter4, Iter5>
set_intersection(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
                 Iter2 keys_first2, Iter2 keys_last2, Iter3 values_first1,
                 Iter4 keys_result, Iter5 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_intersection(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2,
                                     oneapi::dpl::discard_iterator()),
      oneapi::dpl::make_zip_iterator(keys_last2,
                                     oneapi::dpl::discard_iterator()),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<>());
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Comp>
std::pair<Iter4, Iter5>
set_intersection(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
                 Iter2 keys_first2, Iter2 keys_last2, Iter3 values_first1,
                 Iter4 keys_result, Iter5 values_result, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_intersection(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2,
                                     oneapi::dpl::discard_iterator()),
      oneapi::dpl::make_zip_iterator(keys_last2,
                                     oneapi::dpl::discard_iterator()),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<Comp>(comp));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6>
std::pair<Iter5, Iter6>
set_symmetric_difference(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
                         Iter2 keys_first2, Iter2 keys_last2,
                         Iter3 values_first1, Iter4 values_first2,
                         Iter5 keys_result, Iter6 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_symmetric_difference(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<>());
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6, class Comp>
std::pair<Iter5, Iter6>
set_symmetric_difference(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
                         Iter2 keys_first2, Iter2 keys_last2,
                         Iter3 values_first1, Iter4 values_first2,
                         Iter5 keys_result, Iter6 values_result, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_symmetric_difference(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<Comp>(comp));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6>
std::pair<Iter5, Iter6>
set_difference(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
               Iter2 keys_first2, Iter2 keys_last2, Iter3 values_first1,
               Iter4 values_first2, Iter5 keys_result, Iter6 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_difference(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<>());
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6, class Comp>
std::pair<Iter5, Iter6> set_difference(Policy &&policy, Iter1 keys_first1,
                                       Iter1 keys_last1, Iter2 keys_first2,
                                       Iter2 keys_last2, Iter3 values_first1,
                                       Iter4 values_first2, Iter5 keys_result,
                                       Iter6 values_result, Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_difference(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<Comp>(comp));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6>
internal::enable_if_execution_policy<Policy, std::pair<Iter5, Iter6>>
set_union(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
          Iter2 keys_first2, Iter2 keys_last2, Iter3 values_first1,
          Iter4 values_first2, Iter5 keys_result, Iter6 values_result) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_union(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<>());
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <class Policy, class Iter1, class Iter2, class Iter3, class Iter4,
          class Iter5, class Iter6, class Comp>
internal::enable_if_execution_policy<Policy, std::pair<Iter5, Iter6>>
set_union(Policy &&policy, Iter1 keys_first1, Iter1 keys_last1,
          Iter2 keys_first2, Iter2 keys_last2, Iter3 values_first1,
          Iter4 values_first2, Iter5 keys_result, Iter6 values_result,
          Comp comp) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter5>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter6>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::set_union(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(keys_first1, values_first1),
      oneapi::dpl::make_zip_iterator(
          keys_last1, values_first1 + std::distance(keys_first1, keys_last1)),
      oneapi::dpl::make_zip_iterator(keys_first2, values_first2),
      oneapi::dpl::make_zip_iterator(
          keys_last2, values_first2 + std::distance(keys_first2, keys_last2)),
      oneapi::dpl::make_zip_iterator(keys_result, values_result),
      internal::compare_key_fun<Comp>(comp));
  auto n1 = std::distance(
      oneapi::dpl::make_zip_iterator(keys_result, values_result), ret_val);
  return std::make_pair(keys_result + n1, values_result + n1);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Pred>
internal::enable_if_execution_policy<Policy, std::pair<Iter3, Iter4>>
stable_partition_copy(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
                      Iter3 out_true, Iter4 out_false, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  auto ret_val = std::partition_copy(
      std::forward<Policy>(policy), oneapi::dpl::make_zip_iterator(first, mask),
      oneapi::dpl::make_zip_iterator(last, mask + std::distance(first, last)),
      oneapi::dpl::make_zip_iterator(out_true, oneapi::dpl::discard_iterator()),
      oneapi::dpl::make_zip_iterator(out_false,
                                     oneapi::dpl::discard_iterator()),
      internal::predicate_key_fun<Pred>(p));
  return std::make_pair(std::get<0>(ret_val.first.base()),
                        std::get<0>(ret_val.second.base()));
}

template <typename Policy, typename Iter1, typename Iter3, typename Iter4,
          typename Pred>
internal::enable_if_execution_policy<Policy, std::pair<Iter3, Iter4>>
stable_partition_copy(Policy &&policy, Iter1 first, Iter1 last, Iter3 out_true,
                      Iter4 out_false, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  return std::partition_copy(std::forward<Policy>(policy), first, last,
                             out_true, out_false, p);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Pred>
internal::enable_if_execution_policy<Policy, std::pair<Iter3, Iter4>>
partition_copy(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask,
               Iter3 out_true, Iter4 out_false, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter3>::iterator_category,
                       std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter4>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  return stable_partition_copy(std::forward<Policy>(policy), first, last, mask,
                               out_true, out_false, p);
}

template <typename Policy, typename Iter1, typename Iter2, typename Pred>
internal::enable_if_hetero_execution_policy<Policy, Iter1>
stable_partition(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  typedef typename std::decay<Policy>::type policy_type;
  auto _partition_call1 =
      internal::make_wrapped_policy<internal::partition_call1>(policy);
  auto _copy_call1 =
      internal::make_wrapped_policy<internal::copy_call1>(policy);
  auto _copy_call2 = internal::make_wrapped_policy<internal::copy_call2>(
      std::forward<Policy>(policy));
  using _IterValueT = typename std::iterator_traits<Iter1>::value_type;

  auto _n = std::distance(first, last);
  internal::__buffer<_IterValueT> _tmp1(_n);
  internal::__buffer<_IterValueT> _tmp2(_n);

  auto _tmp1_first = _tmp1.get();
  auto _tmp2_first = _tmp2.get();

  auto _end_pair =
      stable_partition_copy(std::move(_partition_call1), first, last, mask,
                            _tmp1_first, _tmp2_first, p);
  auto _first_part_end = std::copy(std::move(_copy_call1), _tmp1_first,
                                   std::get<0>(_end_pair), first);
  std::copy(std::move(_copy_call2), _tmp2_first, std::get<1>(_end_pair),
            _first_part_end);

  return _first_part_end;
}

template <typename Policy, typename Iter1, typename Iter2, typename Pred>
typename std::enable_if<!internal::is_hetero_execution_policy<
                            typename std::decay<Policy>::type>::value,
                        Iter1>::type
stable_partition(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  typedef typename std::decay<Policy>::type policy_type;
  std::vector<typename std::iterator_traits<Iter1>::value_type> _tmp(
      std::distance(first, last));

  std::copy(policy, mask, mask + std::distance(first, last), _tmp.begin());

  auto ret_val = std::stable_partition(
      std::forward<Policy>(policy),
      oneapi::dpl::make_zip_iterator(first, _tmp.begin()),
      oneapi::dpl::make_zip_iterator(last,
                                     _tmp.begin() + std::distance(first, last)),
      internal::predicate_key_fun<Pred>(p));
  return std::get<0>(ret_val.base());
}

template <typename Policy, typename Iter1, typename Iter2, typename Pred>
internal::enable_if_execution_policy<Policy, Iter1>
partition(Policy &&policy, Iter1 first, Iter1 last, Iter2 mask, Pred p) {
  static_assert(
      std::is_same<typename std::iterator_traits<Iter1>::iterator_category,
                   std::random_access_iterator_tag>::value &&
          std::is_same<typename std::iterator_traits<Iter2>::iterator_category,
                       std::random_access_iterator_tag>::value,
      "Iterators passed to algorithms must be random-access iterators.");
  return stable_partition(std::forward<Policy>(policy), first, last, mask, p);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value &&
                          dpct::internal::is_iterator<Iter3>::value &&
                          dpct::internal::is_iterator<Iter4>::value>
sort_pairs(Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
           Iter4 values_out, ::std::int64_t n, bool descending = false,
           int begin_bit = 0,
           int end_bit =
               sizeof(typename ::std::iterator_traits<Iter1>::value_type) * 8);

template <typename Policy, typename Iter1, typename Iter2>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value>
sort_keys(Policy &&policy, Iter1 keys_in, Iter2 keys_out, ::std::int64_t n,
          bool descending = false, int begin_bit = 0,
          int end_bit =
              sizeof(typename ::std::iterator_traits<Iter1>::value_type) * 8);

namespace internal {

// Transforms key to a specific bit range and sorts the transformed key
template <typename Policy, typename Iter1, typename Iter2,
          typename TransformedKeyT>
inline void transform_and_sort(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                               ::std::int64_t n, bool descending, int begin_bit,
                               int end_bit) {
  using key_t_value_t = typename std::iterator_traits<Iter1>::value_type;
  auto trans_key =
      translate_key<key_t_value_t, TransformedKeyT>(begin_bit, end_bit);

  // Use of the comparison operator that is not simply std::greater() or
  // std::less() will result in
  //  not using radix sort which will cost some performance.  However, this is
  //  necessary to provide the transformation of the key to the bitrange
  //  desired.
  auto partial_sort_with_comp = [&](const auto &comp) {
    return oneapi::dpl::partial_sort_copy(
        std::forward<Policy>(policy), keys_in, keys_in + n, keys_out,
        keys_out + n, [=](const auto a, const auto b) {
          return comp(trans_key(a), trans_key(b));
        });
  };
  if (descending)
    partial_sort_with_comp(::std::greater<TransformedKeyT>());
  else
    partial_sort_with_comp(::std::less<TransformedKeyT>());
}

template <typename Policy, typename Iter1, typename Iter2>
inline void sort_only(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                      ::std::int64_t n, bool descending) {
  using key_t_value_t = typename ::std::iterator_traits<Iter1>::value_type;

  if constexpr (::std::is_floating_point<key_t_value_t>::value) {
    if (descending) {
      // Comparison operator that is not std::greater() ensures stability of
      // -0.0 and 0.0
      // at the cost of some performance because radix sort will not be used.
      auto comp_descending = [=](const auto a, const auto b) { return a > b; };

      oneapi::dpl::partial_sort_copy(::std::forward<Policy>(policy), keys_in,
                                     keys_in + n, keys_out, keys_out + n,
                                     comp_descending);
    } else {
      // Comparison operator that is not std::less() ensures stability of -0.0
      // and 0.0
      // at the cost of some performance because radix sort will not be used.
      auto comp_ascending = [=](const auto a, const auto b) { return a < b; };

      oneapi::dpl::partial_sort_copy(::std::forward<Policy>(policy), keys_in,
                                     keys_in + n, keys_out, keys_out + n,
                                     comp_ascending);
    }
  } else {
    if (descending) {
      oneapi::dpl::partial_sort_copy(::std::forward<Policy>(policy), keys_in,
                                     keys_in + n, keys_out, keys_out + n,
                                     ::std::greater<key_t_value_t>());
    } else {

      oneapi::dpl::partial_sort_copy(::std::forward<Policy>(policy), keys_in,
                                     keys_in + n, keys_out, keys_out + n);
    }
  }
}

// Transforms key from a pair to a specific bit range and sorts the pairs by the
// transformed key
template <typename Policy, typename Iter1, typename Iter2,
          typename TransformedKeyT, typename Iter3, typename Iter4>
inline void
transform_and_sort_pairs(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                         Iter3 values_in, Iter4 values_out, ::std::int64_t n,
                         bool descending, int begin_bit, int end_bit) {
  using key_t_value_t = typename std::iterator_traits<Iter1>::value_type;
  auto zip_input = oneapi::dpl::zip_iterator(keys_in, values_in);
  auto zip_output = oneapi::dpl::zip_iterator(keys_out, values_out);
  auto trans_key =
      translate_key<key_t_value_t, TransformedKeyT>(begin_bit, end_bit);

  // Use of the comparison operator that is not simply std::greater() or
  // std::less() will result in
  //  not using radix sort which will cost some performance.  However, this is
  //  necessary to provide the transformation of the key to the bitrange desired
  //  and also to select the key from the zipped pair.
  auto load_val = [=](const auto a) { return trans_key(std::get<0>(a)); };

  auto partial_sort_with_comp = [&](const auto &comp) {
    return oneapi::dpl::partial_sort_copy(
        std::forward<Policy>(policy), zip_input, zip_input + n, zip_output,
        zip_output + n, [=](const auto a, const auto b) {
          return comp(load_val(a), load_val(b));
        });
  };
  if (descending)
    partial_sort_with_comp(::std::greater<key_t_value_t>());
  else
    partial_sort_with_comp(::std::less<key_t_value_t>());
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4>
inline void sort_only_pairs(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                            Iter3 values_in, Iter4 values_out, ::std::int64_t n,
                            bool descending) {
  using key_t_value_t = typename ::std::iterator_traits<Iter1>::value_type;
  auto zip_input = oneapi::dpl::zip_iterator(keys_in, values_in);
  auto zip_output = oneapi::dpl::zip_iterator(keys_out, values_out);

  // Use of the comparison operator that is not simply std::greater() or
  // std::less() will result in
  //  not using radix sort which will cost some performance.  However, this is
  //  necessary to select the key from the zipped pair.
  auto load_val = [=](const auto a) { return std::get<0>(a); };

  auto partial_sort_with_comp = [&](const auto &comp) {
    return oneapi::dpl::partial_sort_copy(
        std::forward<Policy>(policy), zip_input, zip_input + n, zip_output,
        zip_output + n, [=](const auto a, const auto b) {
          return comp(load_val(a), load_val(b));
        });
  };
  if (descending)
    partial_sort_with_comp(::std::greater<key_t_value_t>());
  else
    partial_sort_with_comp(::std::less<key_t_value_t>());
}

// overload for Iter2 != std::nullptr_t
template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4>
typename ::std::enable_if<!::std::is_null_pointer<Iter2>::value>::type
sort_pairs_impl(Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
                Iter4 values_out, ::std::int64_t n, bool descending,
                int begin_bit, int end_bit) {
  using key_t_value_t = typename ::std::iterator_traits<Iter1>::value_type;

  int clipped_begin_bit = (::std::max)(begin_bit, 0);
  int clipped_end_bit =
      (::std::min)((::std::uint64_t)end_bit, sizeof(key_t_value_t) * 8);
  int num_bytes = (clipped_end_bit - clipped_begin_bit - 1) / 8 + 1;

  auto transform_and_sort_pairs_f = [&](auto x) {
    using T = typename ::std::decay_t<decltype(x)>;
    internal::transform_and_sort_pairs<decltype(policy), Iter1, Iter2, T, Iter3,
                                       Iter4>(
        ::std::forward<Policy>(policy), keys_in, keys_out, values_in,
        values_out, n, descending, clipped_begin_bit, clipped_end_bit);
  };

  if (clipped_end_bit - clipped_begin_bit == sizeof(key_t_value_t) * 8) {
    internal::sort_only_pairs(::std::forward<Policy>(policy), keys_in, keys_out,
                              values_in, values_out, n, descending);
  } else if (num_bytes == 1) {
    transform_and_sort_pairs_f.template operator()<uint8_t>(0);
  } else if (num_bytes == 2) {
    transform_and_sort_pairs_f.template operator()<uint16_t>(0);
  } else if (num_bytes <= 4) {
    transform_and_sort_pairs_f.template operator()<uint32_t>(0);
  } else // if (num_bytes <= 8)
  {
    transform_and_sort_pairs_f.template operator()<::std::uint64_t>(0);
  }
}

// overload for Iter2 == std::nullptr_t
template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4>
typename ::std::enable_if<::std::is_null_pointer<Iter2>::value>::type
sort_pairs_impl(Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
                Iter4 values_out, ::std::int64_t n, bool descending,
                int begin_bit, int end_bit) {
  // create temporary keys_out to discard, memory footprint could be improved by
  // a specialized iterator with a single
  // unchanging dummy Iter1 element
  using key_t_value_t = typename std::iterator_traits<Iter1>::value_type;
  sycl::buffer<key_t_value_t, 1> temp_keys_out{sycl::range<1>(n)};
  internal::sort_pairs_impl(std::forward<Policy>(policy), keys_in,
                            oneapi::dpl::begin(temp_keys_out), values_in,
                            values_out, n, descending, begin_bit, end_bit);
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Iter5>
inline void segmented_sort_pairs_by_parallel_sorts(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter4 values_in,
    Iter3 values_out, ::std::int64_t n, ::std::int64_t nsegments,
    Iter5 begin_offsets, Iter5 end_offsets, bool descending = false,
    int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  using offset_type = typename ::std::iterator_traits<Iter5>::value_type;
  ::std::vector<offset_type> host_accessible_offset_starts(nsegments);
  ::std::vector<offset_type> host_accessible_offset_ends(nsegments);
  // make offsets accessible on host
  ::std::copy(policy, begin_offsets, begin_offsets + nsegments,
              host_accessible_offset_starts.begin());
  ::std::copy(policy, end_offsets, end_offsets + nsegments,
              host_accessible_offset_ends.begin());

  for (::std::uint64_t i = 0; i < nsegments; i++) {
    ::std::uint64_t segment_begin = host_accessible_offset_starts[i];
    ::std::uint64_t segment_end =
        (::std::min)(n, (::std::int64_t)host_accessible_offset_ends[i]);
    if (segment_begin < segment_end) {
      ::dpct::sort_pairs(
          policy, keys_in + segment_begin, keys_out + segment_begin,
          values_in + segment_begin, values_out + segment_begin,
          segment_end - segment_begin, descending, begin_bit, end_bit);
    }
  }
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline void segmented_sort_keys_by_parallel_sorts(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, ::std::int64_t n,
    ::std::int64_t nsegments, Iter3 begin_offsets, Iter3 end_offsets,
    bool descending = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  using offset_type = typename ::std::iterator_traits<Iter3>::value_type;
  ::std::vector<offset_type> host_accessible_offset_starts(nsegments);
  ::std::vector<offset_type> host_accessible_offset_ends(nsegments);
  // make offsets accessible on host
  ::std::copy(policy, begin_offsets, begin_offsets + nsegments,
              host_accessible_offset_starts.begin());
  ::std::copy(policy, end_offsets, end_offsets + nsegments,
              host_accessible_offset_ends.begin());

  for (::std::uint64_t i = 0; i < nsegments; i++) {
    ::std::uint64_t segment_begin = host_accessible_offset_starts[i];
    ::std::uint64_t segment_end =
        (::std::min)(n, (::std::int64_t)host_accessible_offset_ends[i]);
    if (segment_begin < segment_end) {
      ::dpct::sort_keys(policy, keys_in + segment_begin,
                        keys_out + segment_begin, segment_end - segment_begin,
                        descending, begin_bit, end_bit);
    }
  }
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Iter5>
inline void segmented_sort_pairs_by_parallel_for_of_sorts(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
    Iter4 values_out, ::std::int64_t n, ::std::int64_t nsegments,
    Iter5 begin_offsets, Iter5 end_offsets, bool descending = false,
    int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  policy.queue().submit([&](sycl::handler &cgh) {
    cgh.parallel_for(nsegments, [=](sycl::id<1> i) {
      ::std::uint64_t segment_begin = begin_offsets[i];
      ::std::uint64_t segment_end =
          (::std::min)(n, (::std::int64_t)end_offsets[i]);
      if (segment_begin == segment_end) {
        return;
      }
      ::dpct::sort_pairs(::std::execution::seq, keys_in + segment_begin,
                         keys_out + segment_begin, values_in + segment_begin,
                         values_out + segment_begin,
                         segment_end - segment_begin, descending, begin_bit,
                         end_bit);
    });
  });
  policy.queue().wait();
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline void segmented_sort_keys_by_parallel_for_of_sorts(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, ::std::int64_t n,
    ::std::int64_t nsegments, Iter3 begin_offsets, Iter3 end_offsets,
    bool descending = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  policy.queue().submit([&](sycl::handler &cgh) {
    cgh.parallel_for(nsegments, [=](sycl::id<1> i) {
      ::std::uint64_t segment_begin = begin_offsets[i];
      ::std::uint64_t segment_end =
          (::std::min)(n, (::std::int64_t)end_offsets[i]);
      if (segment_begin == segment_end) {
        return;
      }
      ::dpct::sort_keys(::std::execution::seq, keys_in + segment_begin,
                        keys_out + segment_begin, segment_end - segment_begin,
                        descending, begin_bit, end_bit);
    });
  });
  policy.queue().wait();
}

template <typename Policy, typename OffsetIteratorT>
inline void mark_segments(Policy &&policy, OffsetIteratorT begin_offsets,
                          OffsetIteratorT end_offsets, ::std::int64_t n,
                          ::std::int64_t nsegments,
                          sycl::buffer<::std::size_t, 1> segments) {

  ::std::size_t work_group_size =
      policy.queue()
          .get_device()
          .template get_info<sycl::info::device::max_work_group_size>();

  auto sg_sizes = policy.queue()
                      .get_device()
                      .template get_info<sycl::info::device::sub_group_sizes>();
  ::std::size_t sub_group_size = sg_sizes.empty() ? 0 : sg_sizes.back();

  float avg_seg_size = (float)n / (float)nsegments;
  if (avg_seg_size > work_group_size) {
    // If average segment size is larger than workgroup, use workgroup to
    // coordinate to mark segments
    policy.queue()
        .submit([&](sycl::handler &h) {
          auto segments_acc = segments.get_access<sycl::access_mode::write>(h);
          h.parallel_for(work_group_size, ([=](sycl::id<1> id) {
                           for (::std::size_t seg = 0; seg < nsegments; seg++) {
                             ::std::size_t i = begin_offsets[seg];
                             ::std::size_t end = end_offsets[seg];
                             while (i + id < end) {
                               segments_acc[i + id] = seg;
                               i += work_group_size;
                             }
                           }
                         }));
        })
        .wait();
  } else if (sub_group_size > 0 && avg_seg_size > sub_group_size / 2) {
    // If average segment size is larger than half a subgroup, use subgroup to
    // coordinate to mark segments
    policy.queue()
        .submit([&](sycl::handler &h) {
          auto segments_acc = segments.get_access<sycl::access_mode::write>(h);
          h.parallel_for(
              sycl::nd_range<1>{work_group_size, work_group_size},
              ([=](sycl::nd_item<1> item) {
                auto sub_group = item.get_sub_group();
                ::std::size_t num_subgroups =
                    sub_group.get_group_range().size();
                ::std::size_t local_size = sub_group.get_local_range().size();

                ::std::size_t sub_group_id = sub_group.get_group_id();
                while (sub_group_id < nsegments) {
                  ::std::size_t subgroup_local_id = sub_group.get_local_id();
                  ::std::size_t i = begin_offsets[sub_group_id];
                  ::std::size_t end = end_offsets[sub_group_id];
                  while (i + subgroup_local_id < end) {
                    segments_acc[i + subgroup_local_id] = sub_group_id;
                    i += local_size;
                  }
                  sub_group_id += num_subgroups;
                }
              }));
        })
        .wait();
  } else {
    // If average segment size is small as compared to subgroup, use single
    // work item to mark each segment
    policy.queue()
        .submit([&](sycl::handler &h) {
          auto segments_acc = segments.get_access<sycl::access_mode::write>(h);
          h.parallel_for(nsegments, ([=](sycl::id<1> seg) {
                           for (::std::size_t i = begin_offsets[seg];
                                i < end_offsets[seg]; i++) {
                             segments_acc[i] = seg;
                           }
                         }));
        })
        .wait();
  }
}

// The dpl_histogram namespace contains a temporary preview of an upcoming
// oneDPL histogram API.  This namespace will be removed and replaced with
// corresponding calls to oneapi::dpl::histogram()
namespace dpl_histogram {

template <typename T1, typename T2>
constexpr inline auto __ceiling_div(const T1 &number, const T2 &divisor) {
  return (number - 1) / divisor + 1;
}

template <typename T1, bool _IsFloatingPoint>
struct __evenly_divided_binhash_impl {};

template <typename T>
struct __evenly_divided_binhash_impl<T, /* is_floating_point = */ true> {
  T __minimum;
  ::std::uint32_t __num_bins;
  T __scale;
  T __maximum;
  __evenly_divided_binhash_impl(const T &min, const T &max,
                                const ::std::uint32_t &num_bins)
      : __minimum(min), __maximum(max), __num_bins(num_bins),
        __scale(T(num_bins) / (max - min)) {}
  template <typename T2> std::uint32_t operator()(T2 &&value) const {
    return ::std::uint32_t((::std::forward<T2>(value) - __minimum) * __scale);
  }

  template <typename T2> bool is_valid(const T2 &value) const {
    return value >= __minimum && value < __maximum;
  }
};

// non floating point type
template <typename T>
struct __evenly_divided_binhash_impl<T, /* is_floating_point= */ false> {
  T __minimum;
  ::std::uint32_t __num_bins;
  T __range_size;
  __evenly_divided_binhash_impl(const T &min, const T &max,
                                const ::std::uint32_t &num_bins)
      : __minimum(min), __num_bins(num_bins), __range_size(max - min) {}
  template <typename T2>::std::uint32_t operator()(T2 &&value) const {
    return ::std::uint32_t(
        ((::std::uint64_t(::std::forward<T2>(value)) - __minimum) *
         ::std::uint64_t(__num_bins)) /
        __range_size);
  }

  template <typename T2> bool is_valid(const T2 &value) const {
    return value >= __minimum && value < __minimum + __range_size;
  }
};

template <typename T1>
using __evenly_divided_binhash =
    __evenly_divided_binhash_impl<T1, ::std::is_floating_point_v<T1>>;

template <typename Range> struct __custom_range_binhash {
  Range __boundaries;
  __custom_range_binhash(Range boundaries) : __boundaries(boundaries) {}

  template <typename T>::std::uint32_t operator()(T &&value) const {
    return (::std::upper_bound(__boundaries.begin(), __boundaries.end(),
                               ::std::forward<T>(value)) -
            __boundaries.begin()) -
           1;
  }

  template <typename T2> bool is_valid(const T2 &value) const {
    return value >= __boundaries[0] &&
           value < __boundaries[__boundaries.size() - 1];
  }
};

template <typename HistAccessor, typename OffsetT, typename Size>
inline void __clear_wglocal_histograms(const HistAccessor &local_histogram,
                                       const OffsetT &offset,
                                       const Size &num_bins,
                                       const sycl::nd_item<1> &self_item) {
  ::std::uint32_t gSize = self_item.get_local_range()[0];
  ::std::uint32_t self_lidx = self_item.get_local_id(0);
  ::std::uint8_t factor = __ceiling_div(num_bins, gSize);
  ::std::uint8_t k;
  _DPCT_PRAGMA_UNROLL
  for (k = 0; k < factor - 1; k++) {
    local_histogram[offset + gSize * k + self_lidx] = 0;
  }
  if (gSize * k + self_lidx < num_bins) {
    local_histogram[offset + gSize * k + self_lidx] = 0;
  }
  self_item.barrier(sycl::access::fence_space::local_space);
}

template <typename BinIdxType, typename Iter1, typename HistReg,
          typename BinFunc>
inline void __accum_local_register_iter(const Iter1 &in_acc,
                                        const ::std::size_t &index,
                                        HistReg *histogram, BinFunc func) {
  const auto &x = in_acc[index];
  if (func.is_valid(x)) {
    BinIdxType c = func(x);
    histogram[c]++;
  }
}

template <typename BinIdxType, sycl::access::address_space AddressSpace,
          typename Iter1, typename HistAccessor, typename OffsetT,
          typename BinFunc>
inline void __accum_local_atomics_iter(const Iter1 &in_acc,
                                       const ::std::size_t &index,
                                       const HistAccessor &wg_local_histogram,
                                       const OffsetT &offset, BinFunc func) {
  using __histo_value_type = typename HistAccessor::value_type;
  const auto &x = in_acc[index];
  if (func.is_valid(x)) {
    BinIdxType c = func(x);
    sycl::atomic_ref<__histo_value_type, sycl::memory_order::relaxed,
                     sycl::memory_scope::work_group, AddressSpace>
        local_bin(wg_local_histogram[offset + c]);
    local_bin++;
  }
}

template <typename BinType, typename HistAccessorIn, typename OffsetT,
          typename HistAccessorOut, typename Size>
inline void __reduce_out_histograms(const HistAccessorIn &in_histogram,
                                    const OffsetT &offset,
                                    const HistAccessorOut &out_histogram,
                                    const Size &num_bins,
                                    const sycl::nd_item<1> &self_item) {
  ::std::uint32_t gSize = self_item.get_local_range()[0];
  ::std::uint32_t self_lidx = self_item.get_local_id(0);
  ::std::uint8_t factor = __ceiling_div(num_bins, gSize);
  ::std::uint8_t k;

  _DPCT_PRAGMA_UNROLL
  for (k = 0; k < factor - 1; k++) {
    sycl::atomic_ref<BinType, sycl::memory_order::relaxed,
                     sycl::memory_scope::device,
                     sycl::access::address_space::global_space>
        global_bin(out_histogram[gSize * k + self_lidx]);
    global_bin += in_histogram[offset + gSize * k + self_lidx];
  }
  if (gSize * k + self_lidx < num_bins) {
    sycl::atomic_ref<BinType, sycl::memory_order::relaxed,
                     sycl::memory_scope::device,
                     sycl::access::address_space::global_space>
        global_bin(out_histogram[gSize * k + self_lidx]);
    global_bin += in_histogram[offset + gSize * k + self_lidx];
  }
}

template <::std::uint16_t ItersPerWorkItem, ::std::uint8_t BinsPerWorkItem,
          typename BinType, typename Policy, typename Range1, typename Range2,
          typename Size, typename IdxHashFunc, typename... Range3>
inline void __histogram_general_registers_local_reduction(
    Policy &&policy, ::std::uint16_t work_group_size, Range1 &&input,
    Range2 &&bins, const Size &num_bins, IdxHashFunc func,
    Range3 &&...opt_range) {
  const ::std::size_t N = input.size();
  using __local_histogram_type = ::std::uint32_t;
  using __private_histogram_type = ::std::uint16_t;

  ::std::size_t segments = __ceiling_div(N, work_group_size * ItersPerWorkItem);
  auto e = policy.queue().submit([&](auto &h) {
    // Temporary use of stable non-public API from oneDPL,  this function will
    // be replaced with oneDPL call in an upcoming release.
    oneapi::dpl::__ranges::__require_access(h, input, bins, opt_range...);
    sycl::local_accessor<__local_histogram_type, 1> local_histogram(
        sycl::range(num_bins), h);
    h.parallel_for(
        sycl::nd_range<1>(segments * work_group_size, work_group_size),
        [=](sycl::nd_item<1> __self_item) {
          using __bin_idx_type = ::std::uint8_t;
          const ::std::size_t __self_lidx = __self_item.get_local_id(0);
          const ::std::size_t __wgroup_idx = __self_item.get_group(0);
          const ::std::size_t __seg_start =
              work_group_size * ItersPerWorkItem * __wgroup_idx;

          __clear_wglocal_histograms(local_histogram, 0, num_bins, __self_item);
          __private_histogram_type histogram[BinsPerWorkItem];
          _DPCT_PRAGMA_UNROLL
          for (::std::uint8_t k = 0; k < BinsPerWorkItem; k++) {
            histogram[k] = 0;
          }

          if (__seg_start + work_group_size * ItersPerWorkItem < N) {
            _DPCT_PRAGMA_UNROLL
            for (::std::uint8_t idx = 0; idx < ItersPerWorkItem; idx++) {
              __accum_local_register_iter<__bin_idx_type>(
                  input, __seg_start + idx * work_group_size + __self_lidx,
                  histogram, func);
            }
          } else {
            _DPCT_PRAGMA_UNROLL
            for (::std::uint8_t idx = 0; idx < ItersPerWorkItem; idx++) {
              ::std::size_t __val_idx =
                  __seg_start + idx * work_group_size + __self_lidx;
              if (__val_idx < N) {
                __accum_local_register_iter<__bin_idx_type>(input, __val_idx,
                                                            histogram, func);
              }
            }
          }

          _DPCT_PRAGMA_UNROLL
          for (::std::uint8_t k = 0; k < num_bins; k++) {
            sycl::atomic_ref<__local_histogram_type,
                             sycl::memory_order::relaxed,
                             sycl::memory_scope::work_group,
                             sycl::access::address_space::local_space>
                local_bin(local_histogram[k]);
            local_bin += histogram[k];
          }

          __self_item.barrier(sycl::access::fence_space::local_space);

          __reduce_out_histograms<BinType>(local_histogram, 0, bins, num_bins,
                                           __self_item);
        });
  });
  e.wait();
}

template <::std::uint16_t ItersPerWorkItem, typename BinType, typename Policy,
          typename Range1, typename Range2, typename Size, typename IdxHashFunc,
          typename... Range3>
inline void __histogram_general_local_atomics(Policy &&policy,
                                              ::std::uint16_t work_group_size,
                                              Range1 &&input, Range2 &&bins,
                                              const Size &num_bins,
                                              IdxHashFunc func,
                                              Range3 &&...opt_range) {
  const ::std::size_t N = input.size();
  ::std::size_t segments = __ceiling_div(N, work_group_size * ItersPerWorkItem);
  auto e = policy.queue().submit([&](auto &h) {
    // Temporary use of stable non-public API from oneDPL,  this function will
    // be replaced with oneDPL call in an upcoming release.
    oneapi::dpl::__ranges::__require_access(h, input, bins, opt_range...);
    sycl::local_accessor<::std::uint32_t, 1> local_histogram(
        sycl::range(num_bins), h);
    h.parallel_for(
        sycl::nd_range<1>(segments * work_group_size, work_group_size),
        [=](sycl::nd_item<1> __self_item) {
          using __bin_idx_type = ::std::uint16_t;
          constexpr auto __atomic_address_space =
              sycl::access::address_space::local_space;
          const ::std::size_t __self_lidx = __self_item.get_local_id(0);
          const ::std::uint32_t __wgroup_idx = __self_item.get_group(0);
          const ::std::size_t __seg_start =
              work_group_size * __wgroup_idx * ItersPerWorkItem;

          __clear_wglocal_histograms(local_histogram, 0, num_bins, __self_item);

          if (__seg_start + work_group_size * ItersPerWorkItem < N) {
            _DPCT_PRAGMA_UNROLL
            for (::std::uint8_t idx = 0; idx < ItersPerWorkItem; idx++) {
              __accum_local_atomics_iter<__bin_idx_type,
                                         __atomic_address_space>(
                  input, __seg_start + idx * work_group_size + __self_lidx,
                  local_histogram, 0, func);
            }
          } else {
            _DPCT_PRAGMA_UNROLL
            for (::std::uint8_t idx = 0; idx < ItersPerWorkItem; idx++) {
              ::std::size_t __val_idx =
                  __seg_start + idx * work_group_size + __self_lidx;
              if (__val_idx < N) {
                __accum_local_atomics_iter<__bin_idx_type,
                                           __atomic_address_space>(
                    input, __val_idx, local_histogram, 0, func);
              }
            }
          }
          __self_item.barrier(sycl::access::fence_space::local_space);

          __reduce_out_histograms<BinType>(local_histogram, 0, bins, num_bins,
                                           __self_item);
        });
  });

  e.wait();
}

template <::std::uint16_t __min_iters_per_work_item, typename BinType,
          typename Policy, typename Range1, typename Range2, typename Size,
          typename IdxHashFunc, typename... Range3>
inline void __histogram_general_private_global_atomics(
    Policy &&policy, ::std::uint16_t work_group_size, Range1 &&input,
    Range2 &&bins, const Size &num_bins, IdxHashFunc func,
    Range3 &&...opt_range) {

  const ::std::size_t N = input.size();
  auto __global_mem_size =
      policy.queue()
          .get_device()
          .template get_info<sycl::info::device::global_mem_size>();
  const ::std::size_t max_segments = (::std::min)(
      __global_mem_size / (num_bins * sizeof(BinType)),
      __ceiling_div(N, work_group_size * __min_iters_per_work_item));
  const ::std::size_t iters_per_work_item =
      __ceiling_div(N, max_segments * work_group_size);
  ::std::size_t segments =
      __ceiling_div(N, work_group_size * iters_per_work_item);

  sycl::buffer<BinType, 1> private_histograms(
      sycl::range<1>(segments * num_bins));

  auto e = policy.queue().submit([&](auto &h) {
    // Temporary use of stable non-public API from oneDPL,  this function will
    // be replaced with oneDPL call in an upcoming release.
    oneapi::dpl::__ranges::__require_access(h, input, bins, opt_range...);
    sycl::accessor hacc_private(private_histograms, h, sycl::read_write,
                                sycl::no_init);
    h.parallel_for(
        sycl::nd_range<1>(segments * work_group_size, work_group_size),
        [=](sycl::nd_item<1> __self_item) {
          using __bin_idx_type = ::std::uint32_t;
          constexpr auto __atomic_address_space =
              sycl::access::address_space::global_space;
          const ::std::size_t __self_lidx = __self_item.get_local_id(0);
          const ::std::size_t __wgroup_idx = __self_item.get_group(0);
          const ::std::size_t __seg_start =
              work_group_size * iters_per_work_item * __wgroup_idx;

          __clear_wglocal_histograms(hacc_private, __wgroup_idx * num_bins,
                                     num_bins, __self_item);
          if (__seg_start + work_group_size * iters_per_work_item < N) {
            for (::std::size_t idx = 0; idx < iters_per_work_item; idx++) {
              __accum_local_atomics_iter<__bin_idx_type,
                                         __atomic_address_space>(
                  input, __seg_start + idx * work_group_size + __self_lidx,
                  hacc_private, __wgroup_idx * num_bins, func);
            }
          } else {
            for (::std::size_t idx = 0; idx < iters_per_work_item; idx++) {
              ::std::size_t __val_idx =
                  __seg_start + idx * work_group_size + __self_lidx;
              if (__val_idx < N) {
                __accum_local_atomics_iter<__bin_idx_type,
                                           __atomic_address_space>(
                    input, __val_idx, hacc_private, __wgroup_idx * num_bins,
                    func);
              }
            }
          }
          __self_item.barrier(sycl::access::fence_space::local_space);

          __reduce_out_histograms<BinType>(hacc_private,
                                           __wgroup_idx * num_bins, bins,
                                           num_bins, __self_item);
        });
  });
  e.wait();
}

template <typename Policy, typename Iter1, typename Iter2, typename Size,
          typename IdxHashFunc, typename... Range>
inline Iter2
__histogram_general_select_best(Policy &&policy, Iter1 first, Iter1 last,
                                Iter2 histogram_first, const Size &num_bins,
                                IdxHashFunc func, Range &&...opt_range) {
  using __histo_value_type = typename ::std::iterator_traits<Iter2>::value_type;
  auto __local_mem_size =
      policy.queue()
          .get_device()
          .template get_info<sycl::info::device::local_mem_size>();
  constexpr ::std::uint8_t __max_registers = 16;

  // Temporary use of stable non-public API from oneDPL,  this function will be
  // replaced with oneDPL call in an upcoming release.
  auto keep_bins = oneapi::dpl::__ranges::__get_sycl_range<
      oneapi::dpl::__par_backend_hetero::access_mode::write, Iter2>();
  auto bins_buf = keep_bins(histogram_first, histogram_first + num_bins);

  oneapi::dpl::fill(policy, bins_buf.all_view().begin(),
                    bins_buf.all_view().end(), __histo_value_type(0));
  auto N = last - first;
  if (N > 0) {
    // Temporary use of stable non-public API from oneDPL,  this function will
    // be replaced with oneDPL call in an upcoming release.
    auto keep_input = oneapi::dpl::__ranges::__get_sycl_range<
        oneapi::dpl::__par_backend_hetero::access_mode::read, Iter1>();
    auto input_buf = keep_input(first, last);

    ::std::size_t max_work_group_size =
        policy.queue()
            .get_device()
            .template get_info<sycl::info::device::max_work_group_size>();
    ::std::size_t work_group_size =
        (::std::min)(max_work_group_size, ::std::size_t(1024));

    if (num_bins < __max_registers) {

      // If bins fit into registers, use register private accumulation
      __histogram_general_registers_local_reduction<32, 16, __histo_value_type>(
          ::std::forward<Policy>(policy), work_group_size, input_buf.all_view(),
          bins_buf.all_view(), num_bins, func,
          ::std::forward<Range...>(opt_range)...);
    } else if (num_bins * sizeof(__histo_value_type) < __local_mem_size) {
      // If bins fit into SLM, use local atomics

      // Experimentally determined iters per work-item
      if (N <= 524288) {
        __histogram_general_local_atomics<4, __histo_value_type>(
            ::std::forward<Policy>(policy), work_group_size,
            input_buf.all_view(), bins_buf.all_view(), num_bins, func,
            ::std::forward<Range...>(opt_range)...);
      } else {
        __histogram_general_local_atomics<32, __histo_value_type>(
            ::std::forward<Policy>(policy), work_group_size,
            input_buf.all_view(), bins_buf.all_view(), num_bins, func,
            ::std::forward<Range...>(opt_range)...);
      }
    } else // Otherwise, use global atomics (private copies per workgroup)
    {
      // Experimentally determined iters per work-item
      if (N <= 524288) {
        __histogram_general_private_global_atomics<4, __histo_value_type>(
            ::std::forward<Policy>(policy), work_group_size,
            input_buf.all_view(), bins_buf.all_view(), num_bins, func,
            ::std::forward<Range...>(opt_range)...);
      } else {
        __histogram_general_private_global_atomics<32, __histo_value_type>(
            ::std::forward<Policy>(policy), work_group_size,
            input_buf.all_view(), bins_buf.all_view(), num_bins, func,
            ::std::forward<Range...>(opt_range)...);
      }
    }
  }
  return histogram_first + num_bins;
}

template <typename Policy, typename Iter1, typename Iter2, typename Size,
          typename T>
inline ::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
        dpct::internal::is_iterator<Iter2>::value &&
        internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value,
    Iter2>
histogram(Policy &&policy, Iter1 first, Iter1 last, Iter2 histogram_first,
          const Size &num_bins, const T &first_bin_min_val,
          const T &last_bin_max_val) {
  return __histogram_general_select_best(
      ::std::forward<Policy>(policy), first, last, histogram_first, num_bins,
      __evenly_divided_binhash<T>(first_bin_min_val, last_bin_max_val,
                                  num_bins));
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline ::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
        dpct::internal::is_iterator<Iter2>::value &&
        dpct::internal::is_iterator<Iter3>::value &&
        internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value,
    Iter2>
histogram(Policy &&policy, Iter1 first, Iter1 last, Iter2 histogram_first,
          Iter3 boundary_first, Iter3 boundary_last) {
  // Temporary use of stable non-public API from oneDPL,  this function will be
  // replaced with oneDPL call in an upcoming release.
  auto keep_boundaries = oneapi::dpl::__ranges::__get_sycl_range<
      oneapi::dpl::__par_backend_hetero::access_mode::read, Iter3>();
  auto boundary_buf = keep_boundaries(boundary_first, boundary_last);

  return __histogram_general_select_best(
      ::std::forward<Policy>(policy), first, last, histogram_first,
      (boundary_last - boundary_first) - 1,
      __custom_range_binhash{boundary_buf.all_view()}, boundary_buf.all_view());
}
} // end namespace dpl_histogram

} // end namespace internal

// Evenly Divided Histogram of a 1-D array
template <typename Policy, typename Iter1, typename Iter2, typename T,
          typename Size>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
histogram_even(Policy &&policy, Iter1 d_samples, Iter2 d_histogram,
               int num_levels, T lower_level, T upper_level, Size num_samples) {
  internal::dpl_histogram::histogram(::std::forward<Policy>(policy), d_samples,
                                     d_samples + num_samples, d_histogram,
                                     num_levels - 1, lower_level, upper_level);
}

// Evenly Divided Histogram of a 2-D ROI in a flattened 2-D array
template <typename Policy, typename Iter1, typename Iter2, typename T,
          typename OffsetT>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
histogram_even_roi(Policy &&policy, Iter1 d_samples, Iter2 d_histogram,
                   int num_levels, T lower_level, T upper_level,
                   OffsetT num_row_samples, OffsetT num_rows,
                   ::std::size_t row_stride_bytes) {
  return histogram_even(
      ::std::forward<Policy>(policy),
      oneapi::dpl::permutation_iterator(
          d_samples,
          internal::__roi_2d_index_functor(
              num_row_samples,
              row_stride_bytes /
                  sizeof(typename ::std::iterator_traits<Iter1>::value_type))),
      d_histogram, num_levels, lower_level, upper_level,
      num_row_samples * num_rows);
}

// Evenly Divided Multi-Channel Histogram of a 1-D array
template <int NumChannels, int NumActiveChannels, typename Policy,
          typename Iter1, typename Iter2, typename T, typename Size>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
multi_histogram_even(Policy &&policy, Iter1 d_samples,
                     Iter2 d_histogram[NumActiveChannels],
                     int num_levels[NumActiveChannels],
                     T lower_level[NumActiveChannels],
                     T upper_level[NumActiveChannels], Size num_pixels) {
  for (int active_channel = 0; active_channel < NumActiveChannels;
       active_channel++) {
    histogram_even(
        policy,
        oneapi::dpl::permutation_iterator(
            d_samples,
            internal::__interleaved_index_functor(NumChannels, active_channel)),
        d_histogram[active_channel], num_levels[active_channel],
        lower_level[active_channel], upper_level[active_channel], num_pixels);
  }
}

// Evenly Divided Multi-Channel Histogram of a 2-D ROI in a flattened 2-D array
template <int NumChannels, int NumActiveChannels, typename Policy,
          typename Iter1, typename Iter2, typename T, typename OffsetT>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
multi_histogram_even_roi(Policy &&policy, Iter1 d_samples,
                         Iter2 d_histogram[NumActiveChannels],
                         int num_levels[NumActiveChannels],
                         T lower_level[NumActiveChannels],
                         T upper_level[NumActiveChannels],
                         OffsetT num_row_samples, OffsetT num_rows,
                         ::std::size_t row_stride_bytes) {
  for (int active_channel = 0; active_channel < NumActiveChannels;
       active_channel++) {
    histogram_even(
        policy,
        oneapi::dpl::permutation_iterator(
            d_samples,
            internal::__composition_functor(
                internal::__roi_2d_index_functor(
                    num_row_samples,
                    row_stride_bytes /
                        (NumChannels * sizeof(typename ::std::iterator_traits<
                                              Iter1>::value_type))),
                internal::__interleaved_index_functor(NumChannels,
                                                      active_channel))),
        d_histogram[active_channel], num_levels[active_channel],
        lower_level[active_channel], upper_level[active_channel],
        num_row_samples * num_rows);
  }
}

// Custom Range Histogram of a 1-D array
template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Size>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    dpct::internal::is_iterator<Iter3>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
histogram_range(Policy &&policy, Iter1 d_samples, Iter2 d_histogram,
                int num_levels, Iter3 d_levels, Size num_samples) {
  internal::dpl_histogram::histogram(::std::forward<Policy>(policy), d_samples,
                                     d_samples + num_samples, d_histogram,
                                     d_levels, d_levels + num_levels);
}

// Custom Range Histogram of a 2-D ROI in a flattened 2-D Array
template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename OffsetT>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    dpct::internal::is_iterator<Iter3>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
histogram_range_roi(Policy &&policy, Iter1 d_samples, Iter2 d_histogram,
                    int num_levels, Iter3 d_levels, OffsetT num_row_samples,
                    OffsetT num_rows, ::std::size_t row_stride_bytes) {
  return histogram_range(
      ::std::forward<Policy>(policy),
      oneapi::dpl::permutation_iterator(
          d_samples,
          internal::__roi_2d_index_functor(
              num_row_samples,
              row_stride_bytes /
                  sizeof(typename ::std::iterator_traits<Iter1>::value_type))),
      d_histogram, num_levels, d_levels, num_row_samples * num_rows);
}

// Custom Range Multi-Channel Histogram of a 1-D array
template <int NumChannels, int NumActiveChannels, typename Policy,
          typename Iter1, typename Iter2, typename Iter3, typename Size>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    dpct::internal::is_iterator<Iter3>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
multi_histogram_range(Policy &&policy, Iter1 d_samples,
                      Iter2 d_histogram[NumActiveChannels],
                      int num_levels[NumActiveChannels],
                      Iter3 d_levels[NumActiveChannels], Size num_pixels) {
  for (int active_channel = 0; active_channel < NumActiveChannels;
       active_channel++) {
    histogram_range(policy,
                    oneapi::dpl::permutation_iterator(
                        d_samples, internal::__interleaved_index_functor(
                                       NumChannels, active_channel)),
                    d_histogram[active_channel], num_levels[active_channel],
                    d_levels[active_channel], num_pixels);
  }
}

// Custom Range Multi-Channel Histogram of a 2-D ROI in a flattened 2-D array
template <int NumChannels, int NumActiveChannels, typename Policy,
          typename Iter1, typename Iter2, typename Iter3, typename OffsetT>
::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    dpct::internal::is_iterator<Iter3>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
multi_histogram_range_roi(Policy &&policy, Iter1 d_samples,
                          Iter2 d_histogram[NumActiveChannels],
                          int num_levels[NumActiveChannels],
                          Iter3 d_levels[NumActiveChannels],
                          OffsetT num_row_samples, OffsetT num_rows,
                          ::std::size_t row_stride_bytes) {
  for (int active_channel = 0; active_channel < NumActiveChannels;
       active_channel++) {
    histogram_range(
        policy,
        oneapi::dpl::permutation_iterator(
            d_samples,
            internal::__composition_functor(
                internal::__roi_2d_index_functor(
                    num_row_samples,
                    row_stride_bytes /
                        (NumChannels * sizeof(typename ::std::iterator_traits<
                                              Iter1>::value_type))),
                internal::__interleaved_index_functor(NumChannels,
                                                      active_channel))),
        d_histogram[active_channel], num_levels[active_channel],
        d_levels[active_channel], num_row_samples * num_rows);
  }
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value &&
                          dpct::internal::is_iterator<Iter3>::value &&
                          dpct::internal::is_iterator<Iter4>::value>
sort_pairs(Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
           Iter4 values_out, ::std::int64_t n, bool descending, int begin_bit,
           int end_bit) {
  internal::sort_pairs_impl(std::forward<Policy>(policy), keys_in, keys_out,
                            values_in, values_out, n, descending, begin_bit,
                            end_bit);
}

template <typename Policy, typename Iter1, typename Iter2>
inline void sort_pairs(
    Policy &&policy, io_iterator_pair<Iter1> &keys,
    io_iterator_pair<Iter2> &values, ::std::int64_t n, bool descending = false,
    bool do_swap_iters = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  sort_pairs(::std::forward<Policy>(policy), keys.first(), keys.second(),
             values.first(), values.second(), n, descending, begin_bit,
             end_bit);
  if (do_swap_iters) {
    keys.swap();
    values.swap();
  }
}

template <typename Policy, typename Iter1, typename Iter2>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value>
sort_keys(Policy &&policy, Iter1 keys_in, Iter2 keys_out, ::std::int64_t n,
          bool descending, int begin_bit, int end_bit) {
  using key_t_value_t = typename ::std::iterator_traits<Iter1>::value_type;

  int clipped_begin_bit = (::std::max)(begin_bit, 0);
  int clipped_end_bit =
      (::std::min)((::std::uint64_t)end_bit, sizeof(key_t_value_t) * 8);
  int num_bytes = (clipped_end_bit - clipped_begin_bit - 1) / 8 + 1;

  auto transform_and_sort_f = [&](auto x) {
    using T = typename ::std::decay_t<decltype(x)>;
    internal::transform_and_sort<decltype(policy), Iter1, Iter2, T>(
        ::std::forward<Policy>(policy), keys_in, keys_out, n, descending,
        clipped_begin_bit, clipped_end_bit);
  };

  if (clipped_end_bit - clipped_begin_bit == sizeof(key_t_value_t) * 8) {
    internal::sort_only(::std::forward<Policy>(policy), keys_in, keys_out, n,
                        descending);
  } else if (num_bytes == 1) {
    transform_and_sort_f.template operator()<uint8_t>(0);
  } else if (num_bytes == 2) {
    transform_and_sort_f.template operator()<uint16_t>(0);
  } else if (num_bytes <= 4) {
    transform_and_sort_f.template operator()<uint32_t>(0);
  } else // if (num_bytes <= 8)
  {
    transform_and_sort_f.template operator()<::std::uint64_t>(0);
  }
}

template <typename Policy, typename Iter1>
inline void sort_keys(
    Policy &&policy, io_iterator_pair<Iter1> &keys, ::std::int64_t n,
    bool descending = false, bool do_swap_iters = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  sort_keys(std::forward<Policy>(policy), keys.first(), keys.second(), n,
            descending, begin_bit, end_bit);
  if (do_swap_iters)
    keys.swap();
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value>
segmented_sort_keys(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, ::std::int64_t n,
    ::std::int64_t nsegments, Iter3 begin_offsets, Iter3 end_offsets,
    bool descending = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  int compute_units =
      policy.queue()
          .get_device()
          .template get_info<sycl::info::device::max_compute_units>();
  auto sg_sizes = policy.queue()
                      .get_device()
                      .template get_info<sycl::info::device::sub_group_sizes>();
  int subgroup_size = sg_sizes.empty() ? 1 : sg_sizes.back();
  // parallel for of serial sorts when we have sufficient number of segments for
  // load balance when number of segments is large as compared to our target
  // compute capability
  if (nsegments >
      compute_units *
          (policy.queue().get_device().is_gpu() ? subgroup_size : 1)) {
    dpct::internal::segmented_sort_keys_by_parallel_for_of_sorts(
        ::std::forward<Policy>(policy), keys_in, keys_out, n, nsegments,
        begin_offsets, end_offsets, descending, begin_bit, end_bit);
  } else
  {
    dpct::internal::segmented_sort_keys_by_parallel_sorts(
        ::std::forward<Policy>(policy), keys_in, keys_out, n, nsegments,
        begin_offsets, end_offsets, descending, begin_bit, end_bit);
  }
}

template <typename Policy, typename Iter1, typename Iter2>
inline void segmented_sort_keys(
    Policy &&policy, io_iterator_pair<Iter1> &keys, ::std::int64_t n,
    ::std::int64_t nsegments, Iter2 begin_offsets, Iter2 end_offsets,
    bool descending = false, bool do_swap_iters = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  segmented_sort_keys(::std::forward<Policy>(policy), keys.first(),
                      keys.second(), n, nsegments, begin_offsets, end_offsets,
                      descending, begin_bit, end_bit);
  if (do_swap_iters) {
    keys.swap();
  }
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3,
          typename Iter4, typename Iter5>
inline ::std::enable_if_t<dpct::internal::is_iterator<Iter1>::value &&
                          dpct::internal::is_iterator<Iter2>::value &&
                          dpct::internal::is_iterator<Iter3>::value &&
                          dpct::internal::is_iterator<Iter4>::value>
segmented_sort_pairs(
    Policy &&policy, Iter1 keys_in, Iter2 keys_out, Iter3 values_in,
    Iter4 values_out, ::std::int64_t n, ::std::int64_t nsegments,
    Iter5 begin_offsets, Iter5 end_offsets, bool descending = false,
    int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  int compute_units =
      policy.queue()
          .get_device()
          .template get_info<sycl::info::device::max_compute_units>();
  auto sg_sizes = policy.queue()
                      .get_device()
                      .template get_info<sycl::info::device::sub_group_sizes>();
  int subgroup_size = sg_sizes.empty() ? 1 : sg_sizes.back();
  // parallel for of serial sorts when we have sufficient number of segments for
  // load balance when number of segments is large as compared to our target
  // compute capability
  if (nsegments >
      compute_units *
          (policy.queue().get_device().is_gpu() ? subgroup_size : 1)) {
    dpct::internal::segmented_sort_pairs_by_parallel_for_of_sorts(
        ::std::forward<Policy>(policy), keys_in, keys_out, values_in,
        values_out, n, nsegments, begin_offsets, end_offsets, descending,
        begin_bit, end_bit);
  } else
  {
    dpct::internal::segmented_sort_pairs_by_parallel_sorts(
        ::std::forward<Policy>(policy), keys_in, keys_out, values_in,
        values_out, n, nsegments, begin_offsets, end_offsets, descending,
        begin_bit, end_bit);
  }
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline void segmented_sort_pairs(
    Policy &&policy, io_iterator_pair<Iter1> &keys,
    io_iterator_pair<Iter2> &values, ::std::int64_t n, ::std::int64_t nsegments,
    Iter3 begin_offsets, Iter3 end_offsets, bool descending = false,
    bool do_swap_iters = false, int begin_bit = 0,
    int end_bit = sizeof(typename ::std::iterator_traits<Iter1>::value_type) *
                  8) {
  segmented_sort_pairs(std::forward<Policy>(policy), keys.first(),
                       keys.second(), values.first(), values.second(), n,
                       nsegments, begin_offsets, end_offsets, descending,
                       begin_bit, end_bit);
  if (do_swap_iters) {
    keys.swap();
    values.swap();
  }
}

template <typename Policy, typename Iter1, typename Iter2>
inline void reduce_argmax(Policy &&policy, Iter1 input, Iter2 output,
                          ::std::size_t n) {
  dpct::arg_index_input_iterator<decltype(input), int> input_arg_idx(input);
  auto ret = ::std::max_element(
      policy, input_arg_idx, input_arg_idx + n,
      [](const auto &a, const auto &b) { return (a.value < b.value); });
  ::std::copy(::std::forward<Policy>(policy), ret, ret + 1, output);
}

template <typename Policy, typename Iter1, typename Iter2>
inline void reduce_argmin(Policy &&policy, Iter1 input, Iter2 output,
                          ::std::size_t n) {
  dpct::arg_index_input_iterator<decltype(input), int> input_arg_idx(input);
  auto ret = ::std::min_element(
      policy, input_arg_idx, input_arg_idx + n,
      [](const auto &a, const auto &b) { return (a.value < b.value); });
  ::std::copy(::std::forward<Policy>(policy), ret, ret + 1, output);
}

template <typename Policy, typename Iter1, typename ValueT, typename CompT>
inline ::std::pair<Iter1, Iter1> equal_range(Policy &&policy, Iter1 start,
                                             Iter1 end, const ValueT &value,
                                             CompT comp) {
  ::std::vector<::std::int64_t> res_lower(1);
  ::std::vector<::std::int64_t> res_upper(1);
  ::std::vector<ValueT> value_vec(1, value);
  ::oneapi::dpl::lower_bound(policy, start, end, value_vec.begin(),
                             value_vec.end(), res_lower.begin(), comp);
  ::oneapi::dpl::upper_bound(::std::forward<Policy>(policy), start, end,
                             value_vec.begin(), value_vec.end(),
                             res_upper.begin(), comp);
  return ::std::make_pair(start + res_lower[0], start + res_upper[0]);
}

template <typename Policy, typename Iter1, typename ValueT>
inline ::std::pair<Iter1, Iter1> equal_range(Policy &&policy, Iter1 start,
                                             Iter1 end, const ValueT &value) {
  return equal_range(::std::forward<Policy>(policy), start, end, value,
                     internal::__less());
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline ::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
segmented_reduce_argmin(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                        ::std::int64_t nsegments, Iter3 begin_offsets,
                        Iter3 end_offsets) {
  policy.queue().submit([&](sycl::handler &cgh) {
    cgh.parallel_for(nsegments, [=](sycl::id<1> i) {
      if (end_offsets[i] <= begin_offsets[i]) {
        keys_out[i] = dpct::key_value_pair(
            1, ::std::numeric_limits<
                   typename ::std::iterator_traits<Iter1>::value_type>::max());
      } else {
        dpct::arg_index_input_iterator<Iter1, int> arg_index(keys_in +
                                                             begin_offsets[i]);
        keys_out[i] = *::std::min_element(
            arg_index, arg_index + (end_offsets[i] - begin_offsets[i]),
            [](const auto &a, const auto &b) { return a.value < b.value; });
      }
    });
  });
  policy.queue().wait();
}

template <typename Policy, typename Iter1, typename Iter2, typename Iter3>
inline ::std::enable_if_t<
    dpct::internal::is_iterator<Iter1>::value &&
    dpct::internal::is_iterator<Iter2>::value &&
    internal::is_hetero_execution_policy<::std::decay_t<Policy>>::value>
segmented_reduce_argmax(Policy &&policy, Iter1 keys_in, Iter2 keys_out,
                        ::std::int64_t nsegments, Iter3 begin_offsets,
                        Iter3 end_offsets) {
  policy.queue().submit([&](sycl::handler &cgh) {
    cgh.parallel_for(nsegments, [=](sycl::id<1> i) {
      if (end_offsets[i] <= begin_offsets[i]) {
        keys_out[i] = dpct::key_value_pair(
            1,
            ::std::numeric_limits<
                typename ::std::iterator_traits<Iter1>::value_type>::lowest());
      } else {
        dpct::arg_index_input_iterator<Iter1, int> arg_index(keys_in +
                                                             begin_offsets[i]);
        keys_out[i] = *::std::max_element(
            arg_index, arg_index + (end_offsets[i] - begin_offsets[i]),
            [](const auto &a, const auto &b) { return a.value < b.value; });
      }
    });
  });
  policy.queue().wait();
}

template <typename ExecutionPolicy, typename InputIterator,
          typename OutputIterator1, typename OutputIterator2,
          typename OutputIterator3>
void nontrivial_run_length_encode(ExecutionPolicy &&policy,
                                  InputIterator input_beg,
                                  OutputIterator1 offsets_out,
                                  OutputIterator2 lengths_out,
                                  OutputIterator3 num_runs,
                                  ::std::int64_t num_items) {
  using oneapi::dpl::make_transform_iterator;
  using oneapi::dpl::make_zip_iterator;
  using offsets_t =
      typename ::std::iterator_traits<OutputIterator1>::value_type;
  using lengths_t =
      typename ::std::iterator_traits<OutputIterator2>::value_type;

  auto input_end = input_beg + num_items;
  // First element must be nontrivial run (start of first segment)
  auto first_adj_it = oneapi::dpl::adjacent_find(policy, input_beg, input_end);
  auto first_adj_idx = ::std::distance(input_beg, first_adj_it);
  if (first_adj_it == input_end) {
    ::std::fill(policy, num_runs, num_runs + 1, 0);
    return;
  }
  auto get_prev_idx_element = [first_adj_idx](const auto &idx) {
    auto out_idx = idx + first_adj_idx;
    return (out_idx == 0) ? 0 : out_idx - 1;
  };
  auto get_next_idx_element = [first_adj_idx, num_items](const auto &idx) {
    auto out_idx = idx + first_adj_idx;
    return (out_idx == num_items - 1) ? num_items - 1 : out_idx + 1;
  };
  // TODO: Use shifted view to pad range once oneDPL ranges is non-experimental
  auto left_shifted_input_beg =
      oneapi::dpl::make_permutation_iterator(input_beg, get_prev_idx_element);
  auto right_shifted_input_beg =
      oneapi::dpl::make_permutation_iterator(input_beg, get_next_idx_element);
  // Segment type for ith idx consists of zip of iterators at (i-1, i, i+1)
  // padded at the ends
  auto zipped_keys_beg = make_zip_iterator(
      left_shifted_input_beg, input_beg, right_shifted_input_beg,
      oneapi::dpl::counting_iterator<offsets_t>(0));
  // Set flag at the beginning of new nontrivial run (ex: (2, 3, 3) -> 1)
  auto key_flags_beg =
      make_transform_iterator(zipped_keys_beg, [num_items](const auto &zipped) {
        using ::std::get;
        bool last_idx_mask = get<3>(zipped) != num_items - 1;
        return (get<0>(zipped) != get<1>(zipped) &&
                get<1>(zipped) == get<2>(zipped)) &&
               last_idx_mask;
      });
  auto count_beg = oneapi::dpl::counting_iterator<offsets_t>(0);
  // Check for presence of nontrivial element at current index
  auto tr_nontrivial_flags = make_transform_iterator(
      make_zip_iterator(left_shifted_input_beg, input_beg,
                        right_shifted_input_beg, count_beg),
      [num_items](const auto &zip) {
        using ::std::get;
        // Flag all elements in a run with special handling for padding
        return lengths_t{
            get<0>(zip) == get<1>(zip) ||
            (get<1>(zip) == get<2>(zip) && get<3>(zip) != num_items - 1)};
      });
  auto zipped_vals_beg = make_zip_iterator(tr_nontrivial_flags, count_beg);
  auto pred = [](bool lhs, bool rhs) { return !rhs; };
  auto op = [](auto lhs, const auto &rhs) {
    using std::get;
    // Update the left-hand side length of the run and return the lhs tuple.
    // This ensures that get<1> of the result contains the starting offset of
    // the run.
    get<0>(lhs) += get<0>(rhs);
    return std::move(lhs);
  };
  auto zipped_out_beg = make_zip_iterator(lengths_out, offsets_out);
  auto [_, zipped_out_vals_end] = oneapi::dpl::reduce_by_segment(
      policy, key_flags_beg + first_adj_idx, key_flags_beg + num_items,
      zipped_vals_beg + first_adj_idx, oneapi::dpl::discard_iterator(),
      zipped_out_beg, pred, op);
  auto ret_dist = ::std::distance(zipped_out_beg, zipped_out_vals_end);
  ::std::fill(policy, num_runs, num_runs + 1, ret_dist);
}

template <typename ExecutionPolicy, typename InputIterator,
          typename OutputIterator, typename CountIterator,
          typename UnaryPredicate>
void partition_if(ExecutionPolicy &&policy, InputIterator input,
                  OutputIterator output, CountIterator num_true, int num_items,
                  UnaryPredicate pred, bool reverse_last = true) {
  auto copy_policy =
      internal::make_wrapped_policy<internal::copy_before_partition>(policy);
  auto partition_policy =
      internal::make_wrapped_policy<internal::partition_call1>(policy);

  dpl::copy(::std::move(copy_policy), input, input + num_items, output);
  auto beg_false = dpl::stable_partition(::std::move(partition_policy), output,
                                         output + num_items, pred);
  auto num_true_items = ::std::distance(output, beg_false);
  if (reverse_last) {
    auto reverse_policy =
        internal::make_wrapped_policy<internal::reverse_partition>(policy);
    dpl::reverse(::std::move(reverse_policy), beg_false, output + num_items);
  }
  dpl::fill(::std::forward<ExecutionPolicy>(policy), num_true, num_true + 1,
            num_true_items);
}

template <typename ExecutionPolicy, typename InputIterator,
          typename OutputIterator1, typename OutputIterator2,
          typename OutputIterator3, typename CountIterator,
          typename UnaryPredicate1, typename UnaryPredicate2>
void partition_if(ExecutionPolicy &&policy, InputIterator input,
                  OutputIterator1 output1, OutputIterator2 output2,
                  OutputIterator3 output3, CountIterator partition_counts,
                  int num_items, UnaryPredicate1 pred1, UnaryPredicate2 pred2,
                  bool reverse_last = true) {
  using internal::__buffer;
  using ValueType = typename ::std::iterator_traits<InputIterator>::value_type;
  using CountType = typename ::std::iterator_traits<CountIterator>::value_type;
  auto partition1_policy =
      internal::make_wrapped_policy<internal::partition_call1>(policy);
  auto partition2_policy =
      internal::make_wrapped_policy<internal::partition_call2>(policy);
  __buffer<ValueType> tmp(num_items);

  // Partition the first set (elements that satisfy pred1) and store the
  // remaining in temporary storage.
  auto [output1_end, tmp_end] =
      dpct::stable_partition_copy(::std::move(partition1_policy), input,
                                  input + num_items, output1, tmp.get(), pred1);
  // Partition the remaining two sets (elements that satisfy pred2 and
  // unselected).
  auto [output2_end, output3_end] =
      dpct::stable_partition_copy(::std::move(partition2_policy), tmp.get(),
                                  tmp_end, output2, output3, pred2);

  ::std::vector<CountType> host_counts = {
      static_cast<CountType>(::std::distance(output1, output1_end)),
      static_cast<CountType>(::std::distance(output2, output2_end)),
      static_cast<CountType>(::std::distance(output3, output3_end))};
  if (reverse_last) {
    auto reverse_policy =
        internal::make_wrapped_policy<internal::reverse_partition>(policy);
    dpl::reverse(::std::move(reverse_policy), output3, output3_end);
  }
  dpl::copy(::std::forward<ExecutionPolicy>(policy), host_counts.begin(),
            host_counts.end(), partition_counts);
}

template <typename ExecutionPolicy, typename InputIterator,
          typename OutputIterator, typename FlagsIterator,
          typename CountIterator>
void partition_flagged(ExecutionPolicy &&policy, InputIterator input,
                       FlagsIterator flags, OutputIterator output,
                       CountIterator num_true, int num_items,
                       bool reverse_last = true) {
  auto copy_policy =
      internal::make_wrapped_policy<internal::copy_before_partition>(policy);
  auto partition_policy =
      internal::make_wrapped_policy<internal::partition_call1>(policy);

  dpl::copy(::std::move(copy_policy), input, input + num_items, output);
  auto beg_false = dpct::stable_partition(::std::move(partition_policy), output,
                                          output + num_items, flags,
                                          [](auto flag) { return flag != 0; });
  auto num_true_items = ::std::distance(output, beg_false);
  if (reverse_last) {
    auto reverse_policy =
        internal::make_wrapped_policy<internal::reverse_partition>(policy);
    dpl::reverse(::std::move(reverse_policy), beg_false, output + num_items);
  }
  dpl::fill(::std::forward<ExecutionPolicy>(policy), num_true, num_true + 1,
            num_true_items);
}

template <typename ExecutionPolicy, typename InputIterator, typename BinaryPred>
typename ::std::iterator_traits<InputIterator>::difference_type
unique_count(ExecutionPolicy &&policy, InputIterator begin, InputIterator end,
             BinaryPred binary_pred) {
  auto n = ::std::distance(begin, end);
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  auto zip_beg = oneapi::dpl::make_zip_iterator(begin, begin + 1);
  auto zip_end = zip_beg + n - 1;
  return 1 + oneapi::dpl::count_if(::std::forward<ExecutionPolicy>(policy),
                                   zip_beg, zip_end,
                                   [binary_pred](const auto &e) {
                                     using ::std::get;
                                     return !binary_pred(get<0>(e), get<1>(e));
                                   });
}

template <typename ExecutionPolicy, typename InputIterator>
typename ::std::iterator_traits<InputIterator>::difference_type
unique_count(ExecutionPolicy &&policy, InputIterator begin, InputIterator end) {
  using T = typename ::std::iterator_traits<InputIterator>::value_type;
  return dpct::unique_count(::std::forward<ExecutionPolicy>(policy), begin, end,
                            ::std::equal_to<T>());
}

} // end namespace dpct

#endif