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)
7 // For more information, see http://www.boost.org/libs/range/
9 #include <boost/range/algorithm/nth_element.hpp>
11 #include <boost/test/test_tools.hpp>
12 #include <boost/test/unit_test.hpp>
14 #include <boost/assign.hpp>
26 struct nth_element_policy
28 template<class Container
, class Iterator
>
29 void test_nth_element(Container
& cont
, Iterator mid
)
31 const Container
old_cont(cont
);
33 boost::nth_element(cont
, mid
);
35 // Test the same operation on the container, for the
36 // case where a temporary is passed as the first
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
);
44 BOOST_CHECK_EQUAL_COLLECTIONS( cont
.begin(), cont
.end(),
45 cont2
.begin(), cont2
.end() );
48 template<class Container
, class Iterator
>
49 void reference_nth_element(Container
& cont
, Iterator mid
)
51 std::nth_element(cont
.begin(), mid
, cont
.end());
55 template<class BinaryPredicate
>
56 struct nth_element_pred_policy
58 template<class Container
, class Iterator
>
59 void test_nth_element(Container
& cont
, Iterator mid
)
61 const Container
old_cont(cont
);
63 boost::nth_element(cont
, mid
, BinaryPredicate());
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
,
72 BOOST_CHECK_EQUAL_COLLECTIONS( cont
.begin(), cont
.end(),
73 cont2
.begin(), cont2
.end() );
76 template<class Container
, class Iterator
>
77 void reference_nth_element(Container
& cont
, Iterator mid
)
79 std::nth_element(cont
.begin(), mid
, cont
.end(), BinaryPredicate());
83 template<class Container
, class TestPolicy
>
84 void test_nth_element_tp_impl(Container
& cont
, TestPolicy policy
)
86 Container
reference(cont
);
89 typedef BOOST_DEDUCED_TYPENAME range_iterator
<Container
>::type iterator_t
;
91 BOOST_CHECK_EQUAL( reference
.size(), test
.size() );
92 if (reference
.size() != test
.size())
95 iterator_t reference_mid
= reference
.begin();
96 iterator_t test_mid
= test
.begin();
98 bool complete
= false;
101 if (reference_mid
== reference
.end())
104 policy
.test_nth_element(test
, test_mid
);
105 policy
.reference_nth_element(reference
, reference_mid
);
107 BOOST_CHECK_EQUAL_COLLECTIONS(
108 reference
.begin(), reference
.end(),
109 test
.begin(), test
.end()
112 if (reference_mid
!= reference
.end())
120 template<class Container
>
121 void test_nth_element_impl(Container
& cont
)
123 test_nth_element_tp_impl(cont
, nth_element_policy());
126 template<class Container
, class BinaryPredicate
>
127 void test_nth_element_impl(Container
& cont
, BinaryPredicate pred
)
129 test_nth_element_tp_impl(cont
, nth_element_pred_policy
<BinaryPredicate
>());
132 template<class Container
>
133 void run_tests(Container
& cont
)
135 test_nth_element_impl(cont
);
136 test_nth_element_impl(cont
, std::less
<int>());
137 test_nth_element_impl(cont
, std::greater
<int>());
140 template<class Container
>
141 void test_nth_element_impl()
143 using namespace boost::assign
;
153 cont
+= 1,2,3,4,5,6,7,8,9;
157 void test_nth_element()
159 test_nth_element_impl
< std::vector
<int> >();
160 test_nth_element_impl
< std::deque
<int> >();
165 boost::unit_test::test_suite
*
166 init_unit_test_suite(int argc
, char* argv
[])
168 boost::unit_test::test_suite
* test
169 = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.nth_element" );
171 test
->add( BOOST_TEST_CASE( &boost::test_nth_element
) );