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 <boost/bind.hpp>
18 #include <algorithm>
19 #include <functional>
20 #include <list>
21 #include <numeric>
22 #include <deque>
23 #include <vector>
24 
25 namespace boost
26 {
27     namespace
28     {
29         struct partial_sort_policy
30         {
31             template<class Container, class Iterator>
test_partial_sortboost::__anon2b0592500111::partial_sort_policy32             void test_partial_sort(Container& cont, Iterator mid)
33             {
34                 const Container old_cont(cont);
35 
36                 boost::partial_sort(cont, mid);
37 
38                 const std::size_t index = std::distance(cont.begin(), mid);
39                 Container cont2(old_cont);
40                 Iterator mid2(cont2.begin());
41                 std::advance(mid2, index);
42                 boost::partial_sort(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_partial_sortboost::__anon2b0592500111::partial_sort_policy49             void reference_partial_sort(Container& cont, Iterator mid)
50             {
51                 std::partial_sort(cont.begin(), mid, cont.end());
52             }
53         };
54 
55         template<class BinaryPredicate>
56         struct partial_sort_pred_policy
57         {
58             template<class Container, class Iterator>
test_partial_sortboost::__anon2b0592500111::partial_sort_pred_policy59             void test_partial_sort(Container& cont, Iterator mid)
60             {
61                 const Container old_cont(cont);
62 
63                 boost::partial_sort(cont, mid, BinaryPredicate());
64 
65                 const std::size_t index = std::distance(cont.begin(), mid);
66                 Container cont2(old_cont);
67                 Iterator mid2(cont2.begin());
68                 std::advance(mid2, index);
69                 boost::partial_sort(cont2, mid2, BinaryPredicate());
70 
71                 BOOST_CHECK_EQUAL_COLLECTIONS( cont.begin(), cont.end(),
72                                                cont2.begin(), cont2.end() );
73             }
74 
75             template<class Container, class Iterator>
reference_partial_sortboost::__anon2b0592500111::partial_sort_pred_policy76             void reference_partial_sort(Container& cont, Iterator mid)
77             {
78                 std::partial_sort(cont.begin(), mid, cont.end(), BinaryPredicate());
79             }
80         };
81 
82         template<class Container, class TestPolicy>
test_partial_sort_tp_impl(Container & cont,TestPolicy policy)83         void test_partial_sort_tp_impl(Container& cont, TestPolicy policy)
84         {
85             Container reference(cont);
86             Container test(cont);
87 
88             typedef BOOST_DEDUCED_TYPENAME range_iterator<Container>::type iterator_t;
89 
90             BOOST_CHECK_EQUAL( reference.size(), test.size() );
91             if (reference.size() != test.size())
92                 return;
93 
94             iterator_t reference_mid = reference.begin();
95             iterator_t test_mid = test.begin();
96 
97             bool complete = false;
98             while (!complete)
99             {
100                 if (reference_mid == reference.end())
101                     complete = true;
102 
103                 policy.test_partial_sort(test, test_mid);
104                 policy.reference_partial_sort(reference, reference_mid);
105 
106                 BOOST_CHECK_EQUAL_COLLECTIONS(
107                     reference.begin(), reference.end(),
108                     test.begin(), test.end()
109                     );
110 
111                 if (reference_mid != reference.end())
112                 {
113                     ++reference_mid;
114                     ++test_mid;
115                 }
116             }
117         }
118 
119         template<class Container>
test_partial_sort_impl(Container & cont)120         void test_partial_sort_impl(Container& cont)
121         {
122             test_partial_sort_tp_impl(cont, partial_sort_policy());
123         }
124 
125         template<class Container, class BinaryPredicate>
test_partial_sort_impl(Container & cont,BinaryPredicate pred)126         void test_partial_sort_impl(Container& cont, BinaryPredicate pred)
127         {
128             test_partial_sort_tp_impl(cont, partial_sort_pred_policy<BinaryPredicate>());
129         }
130 
131         template<class Container>
test_partial_sort_impl()132         void test_partial_sort_impl()
133         {
134             using namespace boost::assign;
135 
136             Container cont;
137             test_partial_sort_impl(cont);
138             test_partial_sort_impl(cont, std::less<int>());
139             test_partial_sort_impl(cont, std::greater<int>());
140 
141             cont.clear();
142             cont += 1;
143             test_partial_sort_impl(cont);
144             test_partial_sort_impl(cont, std::less<int>());
145             test_partial_sort_impl(cont, std::greater<int>());
146 
147             cont.clear();
148             cont += 1,2,3,4,5,6,7,8,9;
149             test_partial_sort_impl(cont);
150             test_partial_sort_impl(cont, std::less<int>());
151             test_partial_sort_impl(cont, std::greater<int>());
152         }
153 
test_partial_sort()154         void test_partial_sort()
155         {
156             test_partial_sort_impl< std::vector<int> >();
157             test_partial_sort_impl< std::deque<int> >();
158         }
159     }
160 }
161 
162 boost::unit_test::test_suite*
init_unit_test_suite(int argc,char * argv[])163 init_unit_test_suite(int argc, char* argv[])
164 {
165     boost::unit_test::test_suite* test
166         = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.partial_sort" );
167 
168     test->add( BOOST_TEST_CASE( &boost::test_partial_sort ) );
169 
170     return test;
171 }
172