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 // for (Iter i = first; i < last; ++i) {
30 // if (i != first) std::cout << ' ';
31 // if (i == sf) std::cout << ">";
32 // std::cout << *i;
33 // if (i == sl) std::cout << "<";
34 // }
35 // if (sl == last) std::cout << "<";
36 // std::cout << '\n';
37
38 if (sf == sl) return;
39 for (Iter i = first; i < sf; ++i)
40 BOOST_CHECK(*i < *sf);
41 for (Iter i = sf; i < sl; ++i) {
42 if (first != sf) // if there is an element before the subrange
43 BOOST_CHECK(*i > *(sf-1));
44 if (last != sl) // if there is an element after the subrange
45 BOOST_CHECK(*i < *sl);
46 }
47 for (Iter i = sl; i < last; ++i)
48 BOOST_CHECK(*(sl-1) < *i);
49 }
50
51 template <typename Iter, typename Pred>
check_sequence(Iter first,Iter last,Iter sf,Iter sl,Pred p)52 void check_sequence ( Iter first, Iter last, Iter sf, Iter sl, Pred p )
53 {
54 if (sf == sl) return;
55 for (Iter i = first; i < sf; ++i)
56 BOOST_CHECK(p(*i, *sf));
57 for (Iter i = sf; i < sl; ++i) {
58 if (first != sf) // if there is an element before the subrange
59 BOOST_CHECK(p(*(sf-1), *i));
60 if (last != sl) // if there is an element after the subrange
61 BOOST_CHECK(p(*i, *sl));
62 }
63 for (Iter i = sl; i < last; ++i)
64 BOOST_CHECK(p(*(sl-1), *i));
65
66 }
67
68 // for ( int i = 0; i < v.size(); ++i )
69 // std::cout << v[i] << ' ';
70 // std::cout << std::endl;
71
72
BOOST_AUTO_TEST_CASE(test_main)73 BOOST_AUTO_TEST_CASE( test_main )
74 {
75 {
76 std::vector<int> v;
77 for ( int i = 0; i < 10; ++i )
78 v.push_back(i);
79
80 const std::vector<int>::iterator b = v.begin();
81 ba::partition_subrange(b, v.end(), b + 3, b + 6);
82 check_sequence (b, v.end(), b + 3, b + 6);
83
84 // BOOST_CHECK_EQUAL(v[3], 3);
85 // BOOST_CHECK_EQUAL(v[4], 4);
86 // BOOST_CHECK_EQUAL(v[5], 5);
87
88 // Mix them up and try again - single element
89 do_shuffle(v.begin(), v.end());
90 ba::partition_subrange(b, v.end(), b + 7, b + 8);
91 check_sequence (b, v.end(), b + 7, b + 8);
92
93 // BOOST_CHECK_EQUAL(v[7], 7);
94
95 // Mix them up and try again - at the end
96 do_shuffle(v.begin(), v.end());
97 ba::partition_subrange(b, v.end(), b + 7, v.end());
98 check_sequence (b, v.end(), b + 7, v.end());
99
100 // BOOST_CHECK_EQUAL(v[7], 7);
101 // BOOST_CHECK_EQUAL(v[8], 8);
102 // BOOST_CHECK_EQUAL(v[9], 9);
103
104 // Mix them up and try again - at the beginning
105 do_shuffle(v.begin(), v.end());
106 ba::partition_subrange(b, v.end(), b, b + 2);
107 check_sequence (b, v.end(), b, b + 2);
108
109 // BOOST_CHECK_EQUAL(v[0], 0);
110 // BOOST_CHECK_EQUAL(v[1], 1);
111
112 // Mix them up and try again - empty subrange
113 do_shuffle(v.begin(), v.end());
114 ba::partition_subrange(b, v.end(), b, b);
115 check_sequence (b, v.end(), b, b);
116
117 // Mix them up and try again - entire subrange
118 do_shuffle(v.begin(), v.end());
119 ba::partition_subrange(b, v.end(), b, v.end());
120 check_sequence (b, v.end(), b, v.end());
121 }
122
123 {
124 std::vector<int> v;
125 for ( int i = 0; i < 10; ++i )
126 v.push_back(i);
127
128 const std::vector<int>::iterator b = v.begin();
129 ba::partition_subrange(b, v.end(), b + 3, b + 6, std::greater<int>());
130 check_sequence (b, v.end(), b + 3, b + 6, std::greater<int>());
131
132 // BOOST_CHECK_EQUAL(v[3], 6);
133 // BOOST_CHECK_EQUAL(v[4], 5);
134 // BOOST_CHECK_EQUAL(v[5], 4);
135
136 // Mix them up and try again - single element
137 do_shuffle(v.begin(), v.end());
138 ba::partition_subrange(b, v.end(), b + 7, b + 8, std::greater<int>());
139 check_sequence (b, v.end(), b + 7, b + 8, std::greater<int>());
140
141 // BOOST_CHECK_EQUAL(v[7], 2);
142
143 // Mix them up and try again - at the end
144 do_shuffle(v.begin(), v.end());
145 ba::partition_subrange(b, v.end(), b + 7, v.end(), std::greater<int>());
146 check_sequence (b, v.end(), b + 7, v.end(), std::greater<int>());
147
148 // BOOST_CHECK_EQUAL(v[7], 2);
149 // BOOST_CHECK_EQUAL(v[8], 1);
150 // BOOST_CHECK_EQUAL(v[9], 0);
151
152 // Mix them up and try again - at the beginning
153 do_shuffle(v.begin(), v.end());
154 ba::partition_subrange(b, v.end(), b, b + 2, std::greater<int>());
155 check_sequence (b, v.end(), b, b + 2, std::greater<int>());
156
157 // BOOST_CHECK_EQUAL(v[0], 9);
158 // BOOST_CHECK_EQUAL(v[1], 8);
159
160 // Mix them up and try again - empty subrange
161 do_shuffle(v.begin(), v.end());
162 ba::partition_subrange(b, v.end(), b, b, std::greater<int>());
163 check_sequence (b, v.end(), b, b, std::greater<int>());
164
165 // Mix them up and try again - entire subrange
166 do_shuffle(v.begin(), v.end());
167 ba::partition_subrange(b, v.end(), b, v.end(), std::greater<int>());
168 check_sequence (b, v.end(), b, v.end(), std::greater<int>());
169 }
170 }
171