//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

// <algorithm>

// template<InputIterator InIter, RandomAccessIterator RAIter>
//   requires ShuffleIterator<RAIter>
//         && OutputIterator<RAIter, InIter::reference>
//         && HasLess<InIter::value_type, RAIter::value_type>
//         && LessThanComparable<RAIter::value_type>
//   constexpr RAIter  // constexpr in C++20
//   partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);

#include <algorithm>
#include <cassert>

#include "test_macros.h"
#include "test_iterators.h"
#include "MoveOnly.h"

template<class T, class Iter, class OutIter>
TEST_CONSTEXPR_CXX20 bool test()
{
    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
    T work[15] = {};
    for (int n = 0; n < 15; ++n) {
        for (int m = 0; m < 15; ++m) {
            OutIter it = std::partial_sort_copy(Iter(orig), Iter(orig+n), OutIter(work), OutIter(work+m));
            if (n <= m) {
                assert(it == OutIter(work+n));
                assert(std::is_permutation(OutIter(work), it, orig));
            } else {
                assert(it == OutIter(work+m));
            }
            assert(std::is_sorted(OutIter(work), it));
            if (it != OutIter(work)) {
                // At most m-1 elements in the input are less than the biggest element in the result.
                int count = 0;
                for (int i = m; i < n; ++i) {
                    count += (T(orig[i]) < *(it - 1));
                }
                assert(count < m);
            }
        }
    }

    {
        int input[] = {3, 4, 2, 5, 1};
        T output[] = {0, 0, 0};
        std::partial_sort_copy(Iter(input), Iter(input + 5), OutIter(output), OutIter(output + 3));
        assert(output[0] == 1);
        assert(output[1] == 2);
        assert(output[2] == 3);
    }
    return true;
}

int main(int, char**)
{
    int i = 42;
    int j = 75;
    std::partial_sort_copy(&i, &i, &j, &j);  // no-op
    assert(i == 42);
    assert(j == 75);

    test<int, random_access_iterator<int*>, random_access_iterator<int*> >();
    test<int, random_access_iterator<int*>, int*>();
    test<int, int*, random_access_iterator<int*> >();
    test<int, int*, int*>();

#if TEST_STD_VER >= 11
    test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>();
    test<MoveOnly, random_access_iterator<int*>, MoveOnly*>();
    test<MoveOnly, int*, random_access_iterator<MoveOnly*>>();
    test<MoveOnly, int*, MoveOnly*>();
#endif

#if TEST_STD_VER >= 20
    static_assert(test<int, random_access_iterator<int*>, random_access_iterator<int*>>());
    static_assert(test<int, int*, random_access_iterator<int*>>());
    static_assert(test<int, random_access_iterator<int*>, int*>());
    static_assert(test<int, int*, int*>());
    static_assert(test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>());
    static_assert(test<MoveOnly, random_access_iterator<int*>, MoveOnly*>());
    static_assert(test<MoveOnly, int*, random_access_iterator<MoveOnly*>>());
    static_assert(test<MoveOnly, int*, MoveOnly*>());
#endif

    return 0;
}