]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
b32b8144 FG |
10 | |
11 | #if __cplusplus >= 201103L | |
12 | #include <random> | |
13 | ||
14 | std::default_random_engine gen; | |
15 | template<typename RandomIt> | |
16 | void do_shuffle(RandomIt first, RandomIt last) | |
17 | { std::shuffle(first, last, gen); } | |
18 | #else | |
19 | template<typename RandomIt> | |
20 | void do_shuffle(RandomIt first, RandomIt last) | |
21 | { std::random_shuffle(first, last); } | |
22 | #endif | |
23 | ||
7c673cae FG |
24 | namespace ba = boost::algorithm; |
25 | ||
26 | template <typename Iter> | |
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> | |
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 | ||
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 | |
b32b8144 | 70 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 77 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 86 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 94 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 99 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 118 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 125 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 134 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 142 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | |
b32b8144 | 147 | do_shuffle(v.begin(), v.end()); |
7c673cae FG |
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 | } |