-
Notifications
You must be signed in to change notification settings - Fork 58
/
Copy pathis_stable.cpp
110 lines (87 loc) · 5.53 KB
/
is_stable.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
* Copyright (c) 2016-2022 Morwenn
* SPDX-License-Identifier: MIT
*/
#include <functional>
#include <vector>
#include <catch2/catch_test_macros.hpp>
#include <cpp-sort/fixed/low_comparisons_sorter.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/sorters/merge_sorter.h>
#include <cpp-sort/sorters/quick_sorter.h>
#include <cpp-sort/utility/functional.h>
TEST_CASE( "test is_stable with raw sorters",
"[is_stable]" )
{
// Exhaustive test for every scenario where is_sorter is
// supposed to trivially fall back to is_always_stable
using cppsort::is_stable;
using cppsort::utility::identity;
SECTION( "merge_sorter" )
{
using sorter = cppsort::merge_sorter;
STATIC_CHECK( is_stable<sorter(std::vector<int>&)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::less<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::greater<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::negate<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::negate<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::less<>, identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>, identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::greater<>, identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>, identity)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::less<>, std::negate<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>, std::negate<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>&, std::greater<>, std::negate<>)>::value );
STATIC_CHECK( is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>, std::negate<>)>::value );
}
SECTION( "quick_sorter" )
{
using sorter = cppsort::quick_sorter;
STATIC_CHECK( not is_stable<sorter(std::vector<int>&)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::less<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::greater<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::negate<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::negate<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::less<>, identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>, identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::greater<>, identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>, identity)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::less<>, std::negate<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::less<>, std::negate<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>&, std::greater<>, std::negate<>)>::value );
STATIC_CHECK( not is_stable<sorter(std::vector<int>::iterator, std::vector<int>::iterator,
std::greater<>, std::negate<>)>::value );
}
SECTION( "low_comparisons_sorter" )
{
// Many fixed-size sorters define is_always_stable through
// sorter_traits, which makes this test interesting
using sorter = cppsort::low_comparisons_sorter<8>;
STATIC_CHECK( not is_stable<sorter(int(&)[8])>::value );
}
}