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

   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)
   5 //
   6 //
   7 // For more information, see http://www.boost.org/libs/range/
   8 //
   9 #include <boost/range/algorithm/heap_algorithm.hpp>
  10
  11 #include <boost/test/test_tools.hpp>
  12 #include <boost/test/unit_test.hpp>
  13
  14 #include <boost/assign.hpp>
  15 #include <boost/bind.hpp>
  16 #include <algorithm>
  17 #include <functional>
  18 #include <list>
  19 #include <numeric>
  20 #include <deque>
  21 #include <vector>
  22
  23 namespace boost
  24 {
  25     namespace
  26     {
  27         template<class Container1, class Container2>
  28         void check_equal(const Container1& cont1, const Container2& cont2)
  29         {
  30             BOOST_CHECK_EQUAL_COLLECTIONS(
  31                 cont1.begin(), cont1.end(),
  32                 cont2.begin(), cont2.end()
  33                 );
  34         }
  35
  36         void test()
  37         {
  38             using namespace boost::assign;
  39
  40             std::vector<int> reference;
  41             reference += 1,2,3,4,5,6,7,8,9;
  42
  43             std::vector<int> test_cont(reference);
  44             std::vector<int> test_cont2(reference);
  45
  46             std::make_heap(reference.begin(), reference.end());
  47             boost::make_heap(test_cont);
  48             check_equal(reference, test_cont);
  49             boost::make_heap(boost::make_iterator_range(test_cont2));
  50             check_equal(reference, test_cont2);
  51
  52             std::push_heap(reference.begin(), reference.end());
  53             boost::push_heap(test_cont);
  54             check_equal(reference, test_cont);
  55             boost::push_heap(boost::make_iterator_range(test_cont2));
  56             check_equal(reference, test_cont2);
  57
  58             std::make_heap(reference.begin(), reference.end());
  59             boost::make_heap(test_cont);
  60             boost::make_heap(boost::make_iterator_range(test_cont2));
  61
  62             std::sort_heap(reference.begin(), reference.end());
  63             boost::sort_heap(test_cont);
  64             check_equal(reference, test_cont);
  65             boost::sort_heap(boost::make_iterator_range(test_cont2));
  66             check_equal(reference, test_cont2);
  67
  68             std::make_heap(reference.begin(), reference.end());
  69             boost::make_heap(test_cont);
  70             boost::make_heap(boost::make_iterator_range(test_cont2));
  71
  72             std::pop_heap(reference.begin(), reference.end());
  73             boost::pop_heap(test_cont);
  74             check_equal(reference, test_cont);
  75             boost::pop_heap(boost::make_iterator_range(test_cont2));
  76             check_equal(reference, test_cont2);
  77         }
  78
  79         template<class BinaryPredicate>
  80         void test_pred(BinaryPredicate pred)
  81         {
  82             using namespace boost::assign;
  83
  84             std::vector<int> reference;
  85             reference += 1,2,3,4,5,6,7,8,9;
  86             std::sort(reference.begin(), reference.end(), pred);
  87
  88             std::vector<int> test_cont(reference);
  89             std::vector<int> test_cont2(reference);
  90
  91             std::make_heap(reference.begin(), reference.end(), pred);
  92             boost::make_heap(test_cont, pred);
  93             check_equal(reference, test_cont);
  94             boost::make_heap(boost::make_iterator_range(test_cont2), pred);
  95             check_equal(reference, test_cont2);
  96
  97             reference.push_back(5);
  98             test_cont.push_back(5);
  99             test_cont2.push_back(5);
 100             std::push_heap(reference.begin(), reference.end(), pred);
 101             boost::push_heap(test_cont, pred);
 102             check_equal(reference, test_cont);
 103             boost::push_heap(boost::make_iterator_range(test_cont2), pred);
 104             check_equal(reference, test_cont2);
 105
 106             std::make_heap(reference.begin(), reference.end(), pred);
 107             boost::make_heap(test_cont, pred);
 108             boost::make_heap(boost::make_iterator_range(test_cont2), pred);
 109
 110             std::sort_heap(reference.begin(), reference.end(), pred);
 111             boost::sort_heap(test_cont, pred);
 112             check_equal(reference, test_cont);
 113             boost::sort_heap(boost::make_iterator_range(test_cont2), pred);
 114             check_equal(reference, test_cont2);
 115
 116             std::make_heap(reference.begin(), reference.end(), pred);
 117             boost::make_heap(test_cont, pred);
 118             boost::make_heap(boost::make_iterator_range(test_cont2), pred);
 119
 120             std::pop_heap(reference.begin(), reference.end(), pred);
 121             boost::pop_heap(test_cont, pred);
 122             check_equal(reference, test_cont);
 123             boost::pop_heap(boost::make_iterator_range(test_cont2), pred);
 124             check_equal(reference, test_cont2);
 125         }
 126
 127         void test_heap()
 128         {
 129             test();
 130             test_pred(std::less<int>());
 131             test_pred(std::greater<int>());
 132         }
 133     }
 134 }
 135
 136 boost::unit_test::test_suite*
 137 init_unit_test_suite(int argc, char* argv[])
 138 {
 139     boost::unit_test::test_suite* test
 140         = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.heap" );
 141
 142     test->add( BOOST_TEST_CASE( &boost::test_heap ) );
 143
 144     return test;
 145 }