Revision 99df01fda8dd45d3f791d917001bc4d5ee605a7b authored by Dmitri Naumov on 05 July 2021, 13:15:45 UTC, committed by Dmitri Naumov on 05 July 2021, 21:55:13 UTC
1 parent 7d3a855
TestQuicksort.cpp
/**
* \file
* \author Dmitrij Naumov
* \date Nov. 2012
* \brief Testing the specialized version of quicksort.
*
* \copyright
* Copyright (c) 2012-2021, OpenGeoSys Community (http://www.opengeosys.org)
* Distributed under a Modified BSD License.
* See accompanying file LICENSE.txt or
* http://www.opengeosys.org/project/license
*
*/
#include <gtest/gtest.h>
#include <algorithm>
#include <autocheck/autocheck.hpp>
#include <numeric>
#include <random>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
#include "BaseLib/quicksort.h"
namespace ac = autocheck;
struct BaseLibQuicksort : public ::testing::Test
{
void SetUp() override
{
cls.trivial([](const std::vector<int>& xs) { return xs.size() < 2; });
cls.collect([](std::vector<int> const& xs) {
return xs.size() < 10 ? "short" : "long";
});
}
ac::gtest_reporter gtest_reporter;
ac::classifier<std::vector<int>> cls;
};
// Quicksort result is sorted.
TEST_F(BaseLibQuicksort, SortsAsSTLSort)
{
cls.classify(
[](std::vector<int> const& xs) {
return std::is_sorted(xs.begin(), xs.end());
},
"sorted");
auto quicksortSortsAsSTLSort = [](std::vector<int>& xs) -> bool {
std::vector<std::size_t> perm(xs.size());
if (!xs.empty())
{
BaseLib::quicksort(xs, 0, xs.size(), perm);
}
return std::is_sorted(xs.begin(), xs.end());
};
ac::check<std::vector<int>>(quicksortSortsAsSTLSort, 100,
ac::make_arbitrary<std::vector<int>>(),
gtest_reporter, cls);
}
template <typename T>
struct OrderedUniqueListGen
{
ac::generator<std::vector<T>> source;
using result_type = std::vector<T>;
std::vector<T> operator()(std::size_t size)
{
// Generate double as many elements because many will be discarded by
// applying unique.
result_type xs(source(2 * size));
std::sort(xs.begin(), xs.end());
auto last = std::unique(xs.begin(), xs.end());
xs.erase(last, xs.end());
return xs;
}
};
// Permutations of non-empty, sorted, unique vector remain untouched.
TEST_F(BaseLibQuicksort, ReportCorrectPermutations)
{
auto gen = ac::make_arbitrary(OrderedUniqueListGen<int>());
auto quicksortCheckPermutations = [](std::vector<int>& xs) {
std::vector<std::size_t> perm(xs.size());
std::iota(perm.begin(), perm.end(), 0);
BaseLib::quicksort(xs, 0, xs.size(), perm);
for (std::size_t i = 0; i < perm.size(); ++i)
{
if (perm[i] != i)
{
std::cerr << i << " " << perm[i] << "\n";
return false;
}
}
return true;
};
ac::check<std::vector<int>>(
quicksortCheckPermutations, 100,
gen.discard_if([](std::vector<int> xs) { return xs.empty(); }),
gtest_reporter, cls);
}
// Permutations of non-empty, sorted, unique vector remain untouched.
TEST_F(BaseLibQuicksort, ReportCorrectPermutationsWithPointer)
{
auto gen = ac::make_arbitrary(OrderedUniqueListGen<int>());
auto quicksortCheckPermutations = [](std::vector<int>& xs) {
std::vector<std::size_t> perm(xs.size());
std::iota(perm.begin(), perm.end(), 0);
std::vector<int*> p_xs;
for (int& x : xs)
{
p_xs.push_back(&x);
}
BaseLib::quicksort(p_xs, 0, p_xs.size(), perm);
for (std::size_t i = 0; i < perm.size(); ++i)
{
if (perm[i] != i)
{
std::cerr << i << " " << perm[i] << "\n";
return false;
}
}
return true;
};
ac::check<std::vector<int>>(
quicksortCheckPermutations, 100,
gen.discard_if([](std::vector<int> xs) { return xs.empty(); }),
gtest_reporter, cls);
}
// Permutations of non-empty, reverse sorted, unique vector is also reversed.
TEST_F(BaseLibQuicksort, ReportCorrectPermutationsReverse)
{
auto reverse = [](std::vector<int>&& xs,
std::size_t /*unused*/) -> std::vector<int> {
std::reverse(xs.begin(), xs.end());
return std::move(xs);
};
auto gen =
ac::make_arbitrary(ac::map(reverse, OrderedUniqueListGen<int>()));
auto quicksortCheckPermutations = [](std::vector<int>& xs) {
std::vector<std::size_t> perm(xs.size());
std::iota(perm.begin(), perm.end(), 0);
BaseLib::quicksort(xs, 0, xs.size(), perm);
for (std::size_t i = 0; i < perm.size(); ++i)
{
if (perm[i] != perm.size() - i - 1)
{
return false;
}
}
return true;
};
ac::check<std::vector<int>>(
quicksortCheckPermutations, 100,
gen.discard_if([](std::vector<int> xs) { return xs.empty(); }),
gtest_reporter, cls);
}
// Permutations of non-empty, reverse sorted, unique vector is also reversed.
TEST_F(BaseLibQuicksort, ReportCorrectPermutationsReverseWithPointer)
{
auto reverse = [](std::vector<int>&& xs,
std::size_t /*unused*/) -> std::vector<int> {
std::reverse(xs.begin(), xs.end());
return std::move(xs);
};
auto gen =
ac::make_arbitrary(ac::map(reverse, OrderedUniqueListGen<int>()));
auto quicksortCheckPermutations = [](std::vector<int>& xs) {
std::vector<std::size_t> perm(xs.size());
std::iota(perm.begin(), perm.end(), 0);
std::vector<int*> p_xs;
for (int& x : xs)
{
p_xs.push_back(&x);
}
BaseLib::quicksort(p_xs, 0, p_xs.size(), perm);
for (std::size_t i = 0; i < perm.size(); ++i)
{
if (perm[i] != perm.size() - i - 1)
{
return false;
}
}
return true;
};
ac::check<std::vector<int>>(
quicksortCheckPermutations, 100,
gen.discard_if([](std::vector<int> xs) { return xs.empty(); }),
gtest_reporter, cls);
}
template <typename T, typename Gen = ac::generator<T>>
struct randomSortedPairGenerator
{
Gen source;
using result_type = std::tuple<T, T>;
result_type operator()(std::size_t /*unused*/)
{
auto p = std::make_tuple(source(), source());
if (std::get<0>(p) > std::get<1>(p))
{
std::swap(std::get<0>(p), std::get<1>(p));
}
return p;
}
};
TEST_F(BaseLibQuicksort, SortsRangeAsSTLSort)
{
auto quicksortSortsRangeAsSTLSort =
[](std::vector<int>& xs,
std::tuple<std::size_t, std::size_t> const& range) -> bool {
if (xs.empty())
{
return true;
}
std::vector<std::size_t> perm(xs.size());
std::iota(perm.begin(), perm.end(), 0);
BaseLib::quicksort(xs, std::get<0>(range), std::get<1>(range), perm);
return std::is_sorted(xs.begin() + std::get<0>(range),
xs.begin() + std::get<1>(range)) &&
std::is_sorted(perm.begin(),
perm.begin() + std::get<0>(range)) &&
std::is_sorted(perm.begin() + std::get<1>(range), perm.end());
};
ac::check<std::vector<int>, std::tuple<std::size_t, std::size_t>>(
quicksortSortsRangeAsSTLSort,
100,
ac::make_arbitrary(ac::generator<std::vector<int>>(),
randomSortedPairGenerator<std::size_t>())
.discard_if([](std::vector<int> const& xs,
std::tuple<std::size_t, std::size_t> const& range) {
return std::get<1>(range) >= xs.size();
}),
gtest_reporter);
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...