// Copyright Epic Games, Inc. All Rights Reserved.

#include <zenutil/parallelsort.h>

#include <zencore/testing.h>

namespace zen {

#if ZEN_WITH_TESTS

void
parallelsort_forcelink()
{
}

TEST_SUITE_BEGIN("util.parallelsort");

TEST_CASE("empty range")
{
	WorkerThreadPool   Pool(2);
	eastl::vector<int> Vec;
	ParallelSort(Pool, Vec.begin(), Vec.end(), [](int A, int B) { return A < B; });
	CHECK(Vec.empty());
}

TEST_CASE("single element")
{
	WorkerThreadPool   Pool(2);
	eastl::vector<int> Vec = {42};
	ParallelSort(Pool, Vec.begin(), Vec.end(), [](int A, int B) { return A < B; });
	CHECK(Vec.size() == 1);
	CHECK(Vec[0] == 42);
}

TEST_CASE("small array below threshold")
{
	WorkerThreadPool   Pool(2);
	eastl::vector<int> Vec = {5, 3, 8, 1, 9, 2, 7, 4, 6, 0};
	ParallelSort(Pool, Vec.begin(), Vec.end(), [](int A, int B) { return A < B; });
	for (size_t I = 0; I < Vec.size(); ++I)
	{
		CHECK(Vec[I] == int(I));
	}
}

TEST_CASE("large array triggers parallel path")
{
	WorkerThreadPool Pool(4);

	// 200K elements — well above the 64K threshold.
	constexpr size_t		N = 200'000;
	eastl::vector<uint32_t> Vec(N);

	// Fill with descending values.
	for (size_t I = 0; I < N; ++I)
	{
		Vec[I] = uint32_t(N - 1 - I);
	}

	ParallelSort(Pool, Vec.begin(), Vec.end(), [](uint32_t A, uint32_t B) { return A < B; });

	for (size_t I = 0; I < N; ++I)
	{
		CHECK_MESSAGE(Vec[I] == uint32_t(I), "index=", I, " got=", Vec[I]);
	}
}

TEST_CASE("already sorted")
{
	WorkerThreadPool Pool(4);

	constexpr size_t		N = 200'000;
	eastl::vector<uint32_t> Vec(N);
	for (size_t I = 0; I < N; ++I)
	{
		Vec[I] = uint32_t(I);
	}

	ParallelSort(Pool, Vec.begin(), Vec.end(), [](uint32_t A, uint32_t B) { return A < B; });

	for (size_t I = 0; I < N; ++I)
	{
		CHECK_MESSAGE(Vec[I] == uint32_t(I), "index=", I, " got=", Vec[I]);
	}
}

TEST_CASE("reverse sorted")
{
	WorkerThreadPool Pool(4);

	constexpr size_t		N = 200'000;
	eastl::vector<uint32_t> Vec(N);
	for (size_t I = 0; I < N; ++I)
	{
		Vec[I] = uint32_t(N - 1 - I);
	}

	ParallelSort(Pool, Vec.begin(), Vec.end(), [](uint32_t A, uint32_t B) { return A < B; });

	for (size_t I = 0; I < N; ++I)
	{
		CHECK_MESSAGE(Vec[I] == uint32_t(I), "index=", I, " got=", Vec[I]);
	}
}

TEST_CASE("duplicate keys")
{
	WorkerThreadPool Pool(4);

	constexpr size_t		N = 200'000;
	eastl::vector<uint32_t> Vec(N);
	for (size_t I = 0; I < N; ++I)
	{
		Vec[I] = uint32_t(I % 100);	 // only 100 distinct values
	}

	ParallelSort(Pool, Vec.begin(), Vec.end(), [](uint32_t A, uint32_t B) { return A < B; });

	for (size_t I = 1; I < N; ++I)
	{
		CHECK_MESSAGE(Vec[I - 1] <= Vec[I], "not sorted at index=", I);
	}
}

TEST_CASE("custom comparator descending")
{
	WorkerThreadPool Pool(4);

	constexpr size_t		N = 200'000;
	eastl::vector<uint32_t> Vec(N);
	for (size_t I = 0; I < N; ++I)
	{
		Vec[I] = uint32_t(I);
	}

	ParallelSort(Pool, Vec.begin(), Vec.end(), [](uint32_t A, uint32_t B) { return A > B; });

	for (size_t I = 0; I < N; ++I)
	{
		CHECK_MESSAGE(Vec[I] == uint32_t(N - 1 - I), "index=", I, " got=", Vec[I]);
	}
}

TEST_SUITE_END();

#endif

}  // namespace zen