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

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