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
22namespace boost
23{
24 namespace
25 {
26 template<class Container1, class Container2>
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
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(first: reference.begin(), last: reference.end());
46 boost::make_heap(rng&: test_cont);
47 check_equal(cont1: reference, cont2: test_cont);
48 boost::make_heap(rng: boost::make_iterator_range(r&: test_cont2));
49 check_equal(cont1: reference, cont2: test_cont2);
50
51 std::push_heap(first: reference.begin(), last: reference.end());
52 boost::push_heap(rng&: test_cont);
53 check_equal(cont1: reference, cont2: test_cont);
54 boost::push_heap(rng: boost::make_iterator_range(r&: test_cont2));
55 check_equal(cont1: reference, cont2: test_cont2);
56
57 std::make_heap(first: reference.begin(), last: reference.end());
58 boost::make_heap(rng&: test_cont);
59 boost::make_heap(rng: boost::make_iterator_range(r&: test_cont2));
60
61 std::sort_heap(first: reference.begin(), last: reference.end());
62 boost::sort_heap(rng&: test_cont);
63 check_equal(cont1: reference, cont2: test_cont);
64 boost::sort_heap(rng: boost::make_iterator_range(r&: test_cont2));
65 check_equal(cont1: reference, cont2: test_cont2);
66
67 std::make_heap(first: reference.begin(), last: reference.end());
68 boost::make_heap(rng&: test_cont);
69 boost::make_heap(rng: boost::make_iterator_range(r&: test_cont2));
70
71 std::pop_heap(first: reference.begin(), last: reference.end());
72 boost::pop_heap(rng&: test_cont);
73 check_equal(cont1: reference, cont2: test_cont);
74 boost::pop_heap(rng: boost::make_iterator_range(r&: test_cont2));
75 check_equal(cont1: reference, cont2: test_cont2);
76 }
77
78 template<class BinaryPredicate>
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(cont1: reference, cont2: test_cont);
93 boost::make_heap(boost::make_iterator_range(r&: test_cont2), pred);
94 check_equal(cont1: reference, cont2: test_cont2);
95
96 reference.push_back(x: 5);
97 test_cont.push_back(x: 5);
98 test_cont2.push_back(x: 5);
99 std::push_heap(reference.begin(), reference.end(), pred);
100 boost::push_heap(test_cont, pred);
101 check_equal(cont1: reference, cont2: test_cont);
102 boost::push_heap(boost::make_iterator_range(r&: test_cont2), pred);
103 check_equal(cont1: reference, cont2: 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(r&: test_cont2), pred);
108
109 std::sort_heap(reference.begin(), reference.end(), pred);
110 boost::sort_heap(test_cont, pred);
111 check_equal(cont1: reference, cont2: test_cont);
112 boost::sort_heap(boost::make_iterator_range(r&: test_cont2), pred);
113 check_equal(cont1: reference, cont2: 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(r&: test_cont2), pred);
118
119 std::pop_heap(reference.begin(), reference.end(), pred);
120 boost::pop_heap(test_cont, pred);
121 check_equal(cont1: reference, cont2: test_cont);
122 boost::pop_heap(boost::make_iterator_range(r&: test_cont2), pred);
123 check_equal(cont1: reference, cont2: test_cont2);
124 }
125
126 void test_heap()
127 {
128 test();
129 test_pred(pred: std::less<int>());
130 test_pred(pred: std::greater<int>());
131 }
132 }
133}
134
135boost::unit_test::test_suite*
136init_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

source code of boost/libs/range/test/algorithm_test/heap.cpp