// -*- C++ -*-
//===-- partial_sort_copy.pass.cpp ----------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// UNSUPPORTED: c++03, c++11, c++14

// Tests for partial_sort_copy
#include "support/pstl_test_config.h"

#include <cmath>
#include <execution>
#include <algorithm>

#include "support/utils.h"

using namespace TestUtils;

template <typename T>
struct Num
{
    T val;

    Num() : val(0) {}
    Num(T v) : val(v) {}
    Num(const Num<T>& v) : val(v.val) {}
    Num(Num<T>&& v) : val(v.val) {}
    Num<T>&
    operator=(const Num<T>& v)
    {
        val = v.val;
        return *this;
    }
    operator T() const { return val; }
    bool
    operator<(const Num<T>& v) const
    {
        return val < v.val;
    }
};

template <typename RandomAccessIterator>
struct test_one_policy
{
    RandomAccessIterator d_first;
    RandomAccessIterator d_last;
    RandomAccessIterator exp_first;
    RandomAccessIterator exp_last;
    // This ctor is needed because output shouldn't be transformed to any iterator type (only random access iterators are allowed)
    test_one_policy(RandomAccessIterator b1, RandomAccessIterator e1, RandomAccessIterator b2, RandomAccessIterator e2)
        : d_first(b1), d_last(e1), exp_first(b2), exp_last(e2)
    {
    }
#if _PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN ||                                                             \
    _PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration
    template <typename InputIterator, typename Size, typename T, typename Compare>
    void
    operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
               const T& trash, Compare compare)
    {
    }

    template <typename InputIterator, typename Size, typename T, typename Compare>
    void
    operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
               const T& trash, Compare compare)
    {
    }

    template <typename InputIterator, typename Size, typename T>
    void
    operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
               const T& trash)
    {
    }

    template <typename InputIterator, typename Size, typename T>
    void
    operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
               const T& trash)
    {
    }
#endif

    template <typename Policy, typename InputIterator, typename Size, typename T, typename Compare>
    void
    operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash,
               Compare compare)
    {
        prepare_data(first, last, n1, trash);
        RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last, compare);
        RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last, compare);

        EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy with predicate");
        EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy with predicate");
    }

    template <typename Policy, typename InputIterator, typename Size, typename T>
    void
    operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash)
    {
        prepare_data(first, last, n1, trash);
        RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last);
        RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last);

        EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy without predicate");
        EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy without predicate");
    }

  private:
    template <typename InputIterator, typename Size, typename T>
    void
    prepare_data(InputIterator first, InputIterator last, Size n1, const T& trash)
    {
        // The rand()%(2*n+1) encourages generation of some duplicates.
        std::srand(42);
        std::generate(first, last, [n1]() { return T(rand() % (2 * n1 + 1)); });

        std::fill(exp_first, exp_last, trash);
        std::fill(d_first, d_last, trash);
    }
};

template <typename T, typename Compare>
void
test_partial_sort_copy(Compare compare)
{

    typedef typename Sequence<T>::iterator iterator_type;
    const std::size_t n_max = 100000;
    Sequence<T> in(n_max);
    Sequence<T> out(2 * n_max);
    Sequence<T> exp(2 * n_max);
    std::size_t n1 = 0;
    std::size_t n2;
    T trash = T(-666);
    for (; n1 < n_max; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1))
    {
        // If both sequences are equal
        n2 = n1;
        invoke_on_all_policies(
            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
            in.begin() + n1, n1, n2, trash, compare);

        // If first sequence is greater than second
        n2 = n1 / 3;
        invoke_on_all_policies(
            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
            in.begin() + n1, n1, n2, trash, compare);

        // If first sequence is less than second
        n2 = 2 * n1;
        invoke_on_all_policies(
            test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
            in.begin() + n1, n1, n2, trash, compare);
    }
    // Test partial_sort_copy without predicate
    n1 = n_max;
    n2 = 2 * n1;
    invoke_on_all_policies(test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2),
                           in.begin(), in.begin() + n1, n1, n2, trash);
}

template <typename T>
struct test_non_const
{
    template <typename Policy, typename InputIterator, typename OutputInterator>
    void
    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
    {
        invoke_if(exec, [&]() {
            partial_sort_copy(exec, input_iter, input_iter, out_iter, out_iter, non_const(std::less<T>()));
        });
    }
};

int
main()
{
    test_partial_sort_copy<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
    test_partial_sort_copy<int32_t>([](int32_t x, int32_t y) { return x > y; });

    test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>());

    test_partial_sort_copy<MemoryChecker>(
        [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() < val2.value(); });
    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from partial_sort_copy: number of ctors calls < num of dtors calls");
    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from partial_sort_copy: number of ctors calls > num of dtors calls");

    std::cout << done() << std::endl;
    return 0;
}