1 #include <boost/config.hpp>
2 #include <boost/algorithm/sort_subrange.hpp>
3 #include <boost/algorithm/cxx11/is_sorted.hpp>
4
5 #define BOOST_TEST_MAIN
6 #include <boost/test/unit_test.hpp>
7
8 #include <vector>
9 #include <iostream>
10
11 #if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
12 #include <random>
13
14 std::default_random_engine gen;
15 template<typename RandomIt>
do_shuffle(RandomIt first,RandomIt last)16 void do_shuffle(RandomIt first, RandomIt last)
17 { std::shuffle(first, last, gen); }
18 #else
19 template<typename RandomIt>
do_shuffle(RandomIt first,RandomIt last)20 void do_shuffle(RandomIt first, RandomIt last)
21 { std::random_shuffle(first, last); }
22 #endif
23
24 namespace ba = boost::algorithm;
25
26 template <typename Iter>
check_sequence(Iter first,Iter last,Iter sf,Iter sl)27 void check_sequence ( Iter first, Iter last, Iter sf, Iter sl )
28 {
29 if (sf == sl) return;
30 for (Iter i = first; i < sf; ++i)
31 BOOST_CHECK(*i < *sf);
32 BOOST_CHECK(ba::is_sorted(sf, sl));
33 for (Iter i = sl; i < last; ++i)
34 BOOST_CHECK(*(sl-1) < *i);
35 }
36
37 template <typename Iter, typename Pred>
check_sequence(Iter first,Iter last,Iter sf,Iter sl,Pred p)38 void check_sequence ( Iter first, Iter last, Iter sf, Iter sl, Pred p )
39 {
40 if (sf == sl) return;
41 for (Iter i = first; i < sf; ++i)
42 BOOST_CHECK(p(*i, *sf));
43 BOOST_CHECK(ba::is_sorted(sf, sl, p));
44 for (Iter i = sl; i < last; ++i)
45 BOOST_CHECK(p(*(sl-1), *i));
46
47 }
48
49 // for ( int i = 0; i < v.size(); ++i )
50 // std::cout << v[i] << ' ';
51 // std::cout << std::endl;
52
53
BOOST_AUTO_TEST_CASE(test_main)54 BOOST_AUTO_TEST_CASE( test_main )
55 {
56 {
57 std::vector<int> v;
58 for ( int i = 0; i < 10; ++i )
59 v.push_back(i);
60
61 const std::vector<int>::iterator b = v.begin();
62 ba::sort_subrange(b, v.end(), b + 3, b + 6);
63 check_sequence (b, v.end(), b + 3, b + 6);
64
65 BOOST_CHECK_EQUAL(v[3], 3);
66 BOOST_CHECK_EQUAL(v[4], 4);
67 BOOST_CHECK_EQUAL(v[5], 5);
68
69 // Mix them up and try again - single element
70 do_shuffle(v.begin(), v.end());
71 ba::sort_subrange(b, v.end(), b + 7, b + 8);
72 check_sequence (b, v.end(), b + 7, b + 8);
73
74 BOOST_CHECK_EQUAL(v[7], 7);
75
76 // Mix them up and try again - at the end
77 do_shuffle(v.begin(), v.end());
78 ba::sort_subrange(b, v.end(), b + 7, v.end());
79 check_sequence (b, v.end(), b + 7, v.end());
80
81 BOOST_CHECK_EQUAL(v[7], 7);
82 BOOST_CHECK_EQUAL(v[8], 8);
83 BOOST_CHECK_EQUAL(v[9], 9);
84
85 // Mix them up and try again - at the beginning
86 do_shuffle(v.begin(), v.end());
87 ba::sort_subrange(b, v.end(), b, b + 2);
88 check_sequence (b, v.end(), b, b + 2);
89
90 BOOST_CHECK_EQUAL(v[0], 0);
91 BOOST_CHECK_EQUAL(v[1], 1);
92
93 // Mix them up and try again - empty subrange
94 do_shuffle(v.begin(), v.end());
95 ba::sort_subrange(b, v.end(), b, b);
96 check_sequence (b, v.end(), b, b);
97
98 // Mix them up and try again - entire subrange
99 do_shuffle(v.begin(), v.end());
100 ba::sort_subrange(b, v.end(), b, v.end());
101 check_sequence (b, v.end(), b, v.end());
102 }
103
104 {
105 std::vector<int> v;
106 for ( int i = 0; i < 10; ++i )
107 v.push_back(i);
108
109 const std::vector<int>::iterator b = v.begin();
110 ba::sort_subrange(b, v.end(), b + 3, b + 6, std::greater<int>());
111 check_sequence (b, v.end(), b + 3, b + 6, std::greater<int>());
112
113 BOOST_CHECK_EQUAL(v[3], 6);
114 BOOST_CHECK_EQUAL(v[4], 5);
115 BOOST_CHECK_EQUAL(v[5], 4);
116
117 // Mix them up and try again - single element
118 do_shuffle(v.begin(), v.end());
119 ba::sort_subrange(b, v.end(), b + 7, b + 8, std::greater<int>());
120 check_sequence (b, v.end(), b + 7, b + 8, std::greater<int>());
121
122 BOOST_CHECK_EQUAL(v[7], 2);
123
124 // Mix them up and try again - at the end
125 do_shuffle(v.begin(), v.end());
126 ba::sort_subrange(b, v.end(), b + 7, v.end(), std::greater<int>());
127 check_sequence (b, v.end(), b + 7, v.end(), std::greater<int>());
128
129 BOOST_CHECK_EQUAL(v[7], 2);
130 BOOST_CHECK_EQUAL(v[8], 1);
131 BOOST_CHECK_EQUAL(v[9], 0);
132
133 // Mix them up and try again - at the beginning
134 do_shuffle(v.begin(), v.end());
135 ba::sort_subrange(b, v.end(), b, b + 2, std::greater<int>());
136 check_sequence (b, v.end(), b, b + 2, std::greater<int>());
137
138 BOOST_CHECK_EQUAL(v[0], 9);
139 BOOST_CHECK_EQUAL(v[1], 8);
140
141 // Mix them up and try again - empty subrange
142 do_shuffle(v.begin(), v.end());
143 ba::sort_subrange(b, v.end(), b, b, std::greater<int>());
144 check_sequence (b, v.end(), b, b, std::greater<int>());
145
146 // Mix them up and try again - entire subrange
147 do_shuffle(v.begin(), v.end());
148 ba::sort_subrange(b, v.end(), b, v.end(), std::greater<int>());
149 check_sequence (b, v.end(), b, v.end(), std::greater<int>());
150 }
151 }
152