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
22namespace boost
23{
24 namespace
25 {
26 struct nth_element_policy
27 {
28 template<class Container, class Iterator>
29 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>
49 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>
59 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>
77 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>
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>
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>
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>
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>
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
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
165boost::unit_test::test_suite*
166init_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

source code of boost/libs/range/test/algorithm_test/nth_element.cpp