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
24 namespace boost
25 {
26 namespace
27 {
28 struct partial_sort_policy
29 {
30 template<class Container, class Iterator>
test_partial_sortboost::__anonee7cafc90111::partial_sort_policy31 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>
reference_partial_sortboost::__anonee7cafc90111::partial_sort_policy48 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>
test_partial_sortboost::__anonee7cafc90111::partial_sort_pred_policy58 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>
reference_partial_sortboost::__anonee7cafc90111::partial_sort_pred_policy75 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>
test_partial_sort_tp_impl(Container & cont,TestPolicy policy)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>
test_partial_sort_impl(Container & cont)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>
test_partial_sort_impl(Container & cont,BinaryPredicate pred)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>
test_partial_sort_impl()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
test_partial_sort()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
161 boost::unit_test::test_suite*
init_unit_test_suite(int argc,char * argv[])162 init_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