1 // Copyright (c) 2010 Nuovation System Designs, LLC
2 // Grant Erickson <gerickson@nuovations.com>
3 //
4 // Reworked by Marshall Clow; August 2010
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // See http://www.boost.org/ for latest version.
11
12 #include <algorithm>
13 #include <iostream>
14
15 #include <boost/algorithm/cxx11/is_sorted.hpp>
16
17 #define BOOST_TEST_MAIN
18 #include <boost/test/unit_test.hpp>
19
20 using namespace boost;
21
22 /* Preprocessor Defines */
23
24 #define elementsof(v) (sizeof (v) / sizeof (v[0]))
25 #define a_begin(v) (&v[0])
26 #define a_end(v) (v + elementsof (v))
27 #define a_range(v) v
28 #define b_e(v) a_begin(v),a_end(v)
29
30 namespace ba = boost::algorithm;
31
less(int x,int y)32 BOOST_CXX14_CONSTEXPR bool less( int x, int y ) { return x < y; }
33
34 static void
test_ordered(void)35 test_ordered(void)
36 {
37 BOOST_CXX14_CONSTEXPR const int strictlyIncreasingValues[] = { 1, 2, 3, 4, 5 };
38 BOOST_CXX14_CONSTEXPR const int randomValues[] = { 3, 6, 1, 2, 7 };
39 const int constantValues[] = { 1, 2, 2, 2, 5 };
40 int nonConstantArray[] = { 1, 2, 2, 2, 5 };
41 const int inOrderUntilTheEnd [] = { 0, 1, 2, 3, 4, 5, 6, 7, 6 };
42
43 // Begin/end checks
44 BOOST_CHECK ( ba::is_sorted (b_e(strictlyIncreasingValues)));
45 BOOST_CHECK ( !ba::is_sorted (b_e(randomValues)));
46 BOOST_CHECK ( ba::is_sorted (b_e(strictlyIncreasingValues), std::less<int>()));
47 BOOST_CHECK ( !ba::is_sorted (b_e(strictlyIncreasingValues), std::greater<int>()));
48
49 // Range checks
50 BOOST_CHECK ( ba::is_sorted (a_range(strictlyIncreasingValues)));
51 BOOST_CHECK ( !ba::is_sorted (a_range(randomValues)));
52 BOOST_CHECK ( ba::is_sorted (a_range(strictlyIncreasingValues), std::less<int>()));
53 BOOST_CHECK ( !ba::is_sorted (a_range(strictlyIncreasingValues), std::greater<int>()));
54
55 BOOST_CHECK ( ba::is_sorted_until ( b_e(strictlyIncreasingValues)) == a_end(strictlyIncreasingValues));
56 BOOST_CHECK ( ba::is_sorted_until ( b_e(strictlyIncreasingValues), std::less<int>()) == a_end(strictlyIncreasingValues));
57 BOOST_CHECK ( ba::is_sorted_until ( a_range(strictlyIncreasingValues)) == boost::end(strictlyIncreasingValues));
58 BOOST_CHECK ( ba::is_sorted_until ( a_range(strictlyIncreasingValues), std::less<int>()) == boost::end(strictlyIncreasingValues));
59
60 // Check for const and non-const arrays
61 BOOST_CHECK ( ba::is_sorted_until ( b_e(constantValues), std::less<int>()) == a_end(constantValues));
62 BOOST_CHECK ( ba::is_sorted_until ( a_range(constantValues), std::less<int>()) == boost::end(constantValues));
63 BOOST_CHECK ( ba::is_sorted_until ( b_e(nonConstantArray), std::less<int>()) == a_end(nonConstantArray));
64 BOOST_CHECK ( ba::is_sorted_until ( a_range(nonConstantArray), std::less<int>()) == boost::end(nonConstantArray));
65
66 BOOST_CHECK ( ba::is_sorted_until ( b_e(randomValues), std::less<int>()) == &randomValues[2] );
67 BOOST_CHECK ( ba::is_sorted_until ( b_e(randomValues)) == &randomValues[2] );
68 BOOST_CHECK ( ba::is_sorted_until ( a_range(randomValues), std::less<int>()) == &randomValues[2] );
69 BOOST_CHECK ( ba::is_sorted_until ( a_range(randomValues)) == &randomValues[2] );
70
71 BOOST_CHECK ( ba::is_sorted_until ( a_range(inOrderUntilTheEnd), std::less<int>()) == &inOrderUntilTheEnd[8] );
72 BOOST_CHECK ( ba::is_sorted_until ( a_range(inOrderUntilTheEnd)) == &inOrderUntilTheEnd[8] );
73
74 // For zero and one element collections, the comparison predicate should never be called
75 BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues), std::equal_to<int>()) == a_begin(randomValues));
76 BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues)) == a_begin(randomValues));
77 BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues) + 1, std::equal_to<int>()) == a_begin(randomValues) + 1);
78 BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues) + 1 ) == a_begin(randomValues) + 1);
79
80 BOOST_CXX14_CONSTEXPR bool constexpr_res = (
81 ba::is_sorted ( boost::begin(strictlyIncreasingValues), boost::end(strictlyIncreasingValues) )
82 && !ba::is_sorted (a_range(randomValues))
83 && ba::is_sorted_until ( boost::begin(strictlyIncreasingValues), boost::end(strictlyIncreasingValues), less) == a_end(strictlyIncreasingValues)
84 && ba::is_sorted_until ( randomValues, less) == &randomValues[2]
85 );
86 BOOST_CHECK ( constexpr_res );
87 }
88
89
90 static void
test_increasing_decreasing(void)91 test_increasing_decreasing(void)
92 {
93 BOOST_CXX14_CONSTEXPR const int strictlyIncreasingValues[] = { 1, 2, 3, 4, 5 };
94 BOOST_CXX14_CONSTEXPR const int strictlyDecreasingValues[] = { 9, 8, 7, 6, 5 };
95 BOOST_CXX14_CONSTEXPR const int increasingValues[] = { 1, 2, 2, 2, 5 };
96 BOOST_CXX14_CONSTEXPR const int decreasingValues[] = { 9, 7, 7, 7, 5 };
97 BOOST_CXX14_CONSTEXPR const int randomValues[] = { 3, 6, 1, 2, 7 };
98 BOOST_CXX14_CONSTEXPR const int constantValues[] = { 7, 7, 7, 7, 7 };
99
100 // Test a strictly increasing sequence
101 BOOST_CHECK ( ba::is_strictly_increasing (b_e(strictlyIncreasingValues)));
102 BOOST_CHECK ( ba::is_increasing (b_e(strictlyIncreasingValues)));
103 BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(strictlyIncreasingValues)));
104 BOOST_CHECK ( !ba::is_decreasing (b_e(strictlyIncreasingValues)));
105
106 BOOST_CHECK ( ba::is_strictly_increasing (a_range(strictlyIncreasingValues)));
107 BOOST_CHECK ( ba::is_increasing (a_range(strictlyIncreasingValues)));
108 BOOST_CHECK ( !ba::is_strictly_decreasing (a_range(strictlyIncreasingValues)));
109 BOOST_CHECK ( !ba::is_decreasing (a_range(strictlyIncreasingValues)));
110
111 // Test a strictly decreasing sequence
112 BOOST_CHECK ( !ba::is_strictly_increasing (b_e(strictlyDecreasingValues)));
113 BOOST_CHECK ( !ba::is_increasing (b_e(strictlyDecreasingValues)));
114 BOOST_CHECK ( ba::is_strictly_decreasing (b_e(strictlyDecreasingValues)));
115 BOOST_CHECK ( ba::is_decreasing (b_e(strictlyDecreasingValues)));
116
117 // Test an increasing sequence
118 BOOST_CHECK ( !ba::is_strictly_increasing (b_e(increasingValues)));
119 BOOST_CHECK ( ba::is_increasing (b_e(increasingValues)));
120 BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(increasingValues)));
121 BOOST_CHECK ( !ba::is_decreasing (b_e(increasingValues)));
122
123 // Test a decreasing sequence
124 BOOST_CHECK ( !ba::is_strictly_increasing (b_e(decreasingValues)));
125 BOOST_CHECK ( !ba::is_increasing (b_e(decreasingValues)));
126 BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(decreasingValues)));
127 BOOST_CHECK ( ba::is_decreasing (b_e(decreasingValues)));
128
129 // Test a random sequence
130 BOOST_CHECK ( !ba::is_strictly_increasing (b_e(randomValues)));
131 BOOST_CHECK ( !ba::is_increasing (b_e(randomValues)));
132 BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(randomValues)));
133 BOOST_CHECK ( !ba::is_decreasing (b_e(randomValues)));
134
135 // Test a constant sequence
136 BOOST_CHECK ( !ba::is_strictly_increasing (b_e(constantValues)));
137 BOOST_CHECK ( ba::is_increasing (b_e(constantValues)));
138 BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(constantValues)));
139 BOOST_CHECK ( ba::is_decreasing (b_e(constantValues)));
140
141 // Test an empty sequence
142 BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues));
143 BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues));
144 BOOST_CHECK ( ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues));
145 BOOST_CHECK ( ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues));
146
147 // Test a one-element sequence
148 BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
149 BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
150 BOOST_CHECK ( ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
151 BOOST_CHECK ( ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
152
153 // Test a two-element sequence
154 BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
155 BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
156 BOOST_CHECK ( !ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
157 BOOST_CHECK ( !ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
158
159 BOOST_CXX14_CONSTEXPR bool constexpr_res = (
160 ba::is_increasing (boost::begin(increasingValues), boost::end(increasingValues))
161 && ba::is_decreasing (boost::begin(decreasingValues), boost::end(decreasingValues))
162 && ba::is_strictly_increasing (boost::begin(strictlyIncreasingValues), boost::end(strictlyIncreasingValues))
163 && ba::is_strictly_decreasing (boost::begin(strictlyDecreasingValues), boost::end(strictlyDecreasingValues))
164 && !ba::is_strictly_increasing (boost::begin(increasingValues), boost::end(increasingValues))
165 && !ba::is_strictly_decreasing (boost::begin(decreasingValues), boost::end(decreasingValues))
166 );
167 BOOST_CHECK ( constexpr_res );
168 }
169
BOOST_AUTO_TEST_CASE(test_main)170 BOOST_AUTO_TEST_CASE( test_main )
171 {
172 test_ordered ();
173 test_increasing_decreasing ();
174 }
175