ceph/src/boost/libs/range/test/algorithm_test/partial_sort.cpp

   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>
  32             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>
  49             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>
  59             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>
  76             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>
  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>
 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>
 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>
 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
 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*
 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 }