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