1 // Copyright Neil Groves 2009. Use, modification and
2 // distribution is subject to the Boost Software License, Version
3 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 //
6 //
7 // For more information, see http://www.boost.org/libs/range/
8 //
9 #include <boost/range/algorithm/nth_element.hpp>
10
11 #include <boost/test/test_tools.hpp>
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/assign.hpp>
15 #include <algorithm>
16 #include <functional>
17 #include <list>
18 #include <numeric>
19 #include <deque>
20 #include <vector>
21
22 namespace boost
23 {
24 namespace
25 {
26 struct nth_element_policy
27 {
28 template<class Container, class Iterator>
test_nth_elementboost::__anonda3e36c80111::nth_element_policy29 void test_nth_element(Container& cont, Iterator mid)
30 {
31 const Container old_cont(cont);
32
33 boost::nth_element(cont, mid);
34
35 // Test the same operation on the container, for the
36 // case where a temporary is passed as the first
37 // argument.
38 Container cont2(old_cont);
39 const std::size_t index = std::distance(cont.begin(), mid);
40 Iterator mid2(cont2.begin());
41 std::advance(mid2, index);
42 boost::nth_element(boost::make_iterator_range(cont2), mid2);
43
44 BOOST_CHECK_EQUAL_COLLECTIONS( cont.begin(), cont.end(),
45 cont2.begin(), cont2.end() );
46 }
47
48 template<class Container, class Iterator>
reference_nth_elementboost::__anonda3e36c80111::nth_element_policy49 void reference_nth_element(Container& cont, Iterator mid)
50 {
51 std::nth_element(cont.begin(), mid, cont.end());
52 }
53 };
54
55 template<class BinaryPredicate>
56 struct nth_element_pred_policy
57 {
58 template<class Container, class Iterator>
test_nth_elementboost::__anonda3e36c80111::nth_element_pred_policy59 void test_nth_element(Container& cont, Iterator mid)
60 {
61 const Container old_cont(cont);
62
63 boost::nth_element(cont, mid, BinaryPredicate());
64
65 Container cont2(old_cont);
66 const std::size_t index = std::distance(cont.begin(), mid);
67 Iterator mid2(cont2.begin());
68 std::advance(mid2, index);
69 boost::nth_element(boost::make_iterator_range(cont2), mid2,
70 BinaryPredicate());
71
72 BOOST_CHECK_EQUAL_COLLECTIONS( cont.begin(), cont.end(),
73 cont2.begin(), cont2.end() );
74 }
75
76 template<class Container, class Iterator>
reference_nth_elementboost::__anonda3e36c80111::nth_element_pred_policy77 void reference_nth_element(Container& cont, Iterator mid)
78 {
79 std::nth_element(cont.begin(), mid, cont.end(), BinaryPredicate());
80 }
81 };
82
83 template<class Container, class TestPolicy>
test_nth_element_tp_impl(Container & cont,TestPolicy policy)84 void test_nth_element_tp_impl(Container& cont, TestPolicy policy)
85 {
86 Container reference(cont);
87 Container test(cont);
88
89 typedef BOOST_DEDUCED_TYPENAME range_iterator<Container>::type iterator_t;
90
91 BOOST_CHECK_EQUAL( reference.size(), test.size() );
92 if (reference.size() != test.size())
93 return;
94
95 iterator_t reference_mid = reference.begin();
96 iterator_t test_mid = test.begin();
97
98 bool complete = false;
99 while (!complete)
100 {
101 if (reference_mid == reference.end())
102 complete = true;
103
104 policy.test_nth_element(test, test_mid);
105 policy.reference_nth_element(reference, reference_mid);
106
107 BOOST_CHECK_EQUAL_COLLECTIONS(
108 reference.begin(), reference.end(),
109 test.begin(), test.end()
110 );
111
112 if (reference_mid != reference.end())
113 {
114 ++reference_mid;
115 ++test_mid;
116 }
117 }
118 }
119
120 template<class Container>
test_nth_element_impl(Container & cont)121 void test_nth_element_impl(Container& cont)
122 {
123 test_nth_element_tp_impl(cont, nth_element_policy());
124 }
125
126 template<class Container, class BinaryPredicate>
test_nth_element_impl(Container & cont,BinaryPredicate pred)127 void test_nth_element_impl(Container& cont, BinaryPredicate pred)
128 {
129 test_nth_element_tp_impl(cont, nth_element_pred_policy<BinaryPredicate>());
130 }
131
132 template<class Container>
run_tests(Container & cont)133 void run_tests(Container& cont)
134 {
135 test_nth_element_impl(cont);
136 test_nth_element_impl(cont, std::less<int>());
137 test_nth_element_impl(cont, std::greater<int>());
138 }
139
140 template<class Container>
test_nth_element_impl()141 void test_nth_element_impl()
142 {
143 using namespace boost::assign;
144
145 Container cont;
146 run_tests(cont);
147
148 cont.clear();
149 cont += 1;
150 run_tests(cont);
151
152 cont.clear();
153 cont += 1,2,3,4,5,6,7,8,9;
154 run_tests(cont);
155 }
156
test_nth_element()157 void test_nth_element()
158 {
159 test_nth_element_impl< std::vector<int> >();
160 test_nth_element_impl< std::deque<int> >();
161 }
162 }
163 }
164
165 boost::unit_test::test_suite*
init_unit_test_suite(int argc,char * argv[])166 init_unit_test_suite(int argc, char* argv[])
167 {
168 boost::unit_test::test_suite* test
169 = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.nth_element" );
170
171 test->add( BOOST_TEST_CASE( &boost::test_nth_element ) );
172
173 return test;
174 }
175