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
14std::default_random_engine gen;
15template<typename RandomIt>
16void do_shuffle(RandomIt first, RandomIt last)
17{ std::shuffle(first, last, gen); }
18#else
19template<typename RandomIt>
20void do_shuffle(RandomIt first, RandomIt last)
21{ std::random_shuffle(first, last); }
22#endif
23
24namespace ba = boost::algorithm;
25
26template <typename Iter>
27void 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
37template <typename Iter, typename Pred>
38void 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
54BOOST_AUTO_TEST_CASE( test_main )
55{
56 {
57 std::vector<int> v;
58 for ( int i = 0; i < 10; ++i )
59 v.push_back(x: i);
60
61 const std::vector<int>::iterator b = v.begin();
62 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 3, sub_last: b + 6);
63 check_sequence (first: b, last: v.end(), sf: b + 3, sl: 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(first: v.begin(), last: v.end());
71 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 7, sub_last: b + 8);
72 check_sequence (first: b, last: v.end(), sf: b + 7, sl: b + 8);
73
74 BOOST_CHECK_EQUAL(v[7], 7);
75
76// Mix them up and try again - at the end
77 do_shuffle(first: v.begin(), last: v.end());
78 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 7, sub_last: v.end());
79 check_sequence (first: b, last: v.end(), sf: b + 7, sl: 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(first: v.begin(), last: v.end());
87 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: b + 2);
88 check_sequence (first: b, last: v.end(), sf: b, sl: 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(first: v.begin(), last: v.end());
95 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: b);
96 check_sequence (first: b, last: v.end(), sf: b, sl: b);
97
98// Mix them up and try again - entire subrange
99 do_shuffle(first: v.begin(), last: v.end());
100 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: v.end());
101 check_sequence (first: b, last: v.end(), sf: b, sl: v.end());
102 }
103
104 {
105 std::vector<int> v;
106 for ( int i = 0; i < 10; ++i )
107 v.push_back(x: i);
108
109 const std::vector<int>::iterator b = v.begin();
110 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 3, sub_last: b + 6, p: std::greater<int>());
111 check_sequence (first: b, last: v.end(), sf: b + 3, sl: b + 6, p: 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(first: v.begin(), last: v.end());
119 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 7, sub_last: b + 8, p: std::greater<int>());
120 check_sequence (first: b, last: v.end(), sf: b + 7, sl: b + 8, p: 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(first: v.begin(), last: v.end());
126 ba::sort_subrange(first: b, last: v.end(), sub_first: b + 7, sub_last: v.end(), p: std::greater<int>());
127 check_sequence (first: b, last: v.end(), sf: b + 7, sl: v.end(), p: 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(first: v.begin(), last: v.end());
135 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: b + 2, p: std::greater<int>());
136 check_sequence (first: b, last: v.end(), sf: b, sl: b + 2, p: 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(first: v.begin(), last: v.end());
143 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: b, p: std::greater<int>());
144 check_sequence (first: b, last: v.end(), sf: b, sl: b, p: std::greater<int>());
145
146// Mix them up and try again - entire subrange
147 do_shuffle(first: v.begin(), last: v.end());
148 ba::sort_subrange(first: b, last: v.end(), sub_first: b, sub_last: v.end(), p: std::greater<int>());
149 check_sequence (first: b, last: v.end(), sf: b, sl: v.end(), p: std::greater<int>());
150 }
151}
152

source code of boost/libs/algorithm/test/sort_subrange_test.cpp