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 #ifndef BOOST_RANGE_ALGORITHM_HEAP_ALGORITHM_HPP_INCLUDED
10 #define BOOST_RANGE_ALGORITHM_HEAP_ALGORITHM_HPP_INCLUDED
11 
12 #include <boost/concept_check.hpp>
13 #include <boost/range/begin.hpp>
14 #include <boost/range/end.hpp>
15 #include <boost/range/concepts.hpp>
16 #include <algorithm>
17 
18 namespace boost
19 {
20     namespace range
21     {
22 
23 /// \brief template function push_heap
24 ///
25 /// range-based version of the push_heap std algorithm
26 ///
27 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
28 /// \pre Compare is a model of the BinaryPredicateConcept
29 template<class RandomAccessRange>
push_heap(RandomAccessRange & rng)30 inline RandomAccessRange& push_heap(RandomAccessRange& rng)
31 {
32     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
33     std::push_heap(boost::begin(rng), boost::end(rng));
34     return rng;
35 }
36 
37 /// \overload
38 template<class RandomAccessRange>
push_heap(const RandomAccessRange & rng)39 inline const RandomAccessRange& push_heap(const RandomAccessRange& rng)
40 {
41     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
42     std::push_heap(boost::begin(rng), boost::end(rng));
43     return rng;
44 }
45 
46 /// \overload
47 template<class RandomAccessRange, class Compare>
push_heap(RandomAccessRange & rng,Compare comp_pred)48 inline RandomAccessRange& push_heap(RandomAccessRange& rng, Compare comp_pred)
49 {
50     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
51     std::push_heap(boost::begin(rng), boost::end(rng), comp_pred);
52     return rng;
53 }
54 
55 /// \overload
56 template<class RandomAccessRange, class Compare>
push_heap(const RandomAccessRange & rng,Compare comp_pred)57 inline const RandomAccessRange& push_heap(const RandomAccessRange& rng, Compare comp_pred)
58 {
59     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
60     std::push_heap(boost::begin(rng), boost::end(rng), comp_pred);
61     return rng;
62 }
63 
64 /// \brief template function pop_heap
65 ///
66 /// range-based version of the pop_heap std algorithm
67 ///
68 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
69 /// \pre Compare is a model of the BinaryPredicateConcept
70 template<class RandomAccessRange>
pop_heap(RandomAccessRange & rng)71 inline RandomAccessRange& pop_heap(RandomAccessRange& rng)
72 {
73     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
74     std::pop_heap(boost::begin(rng), boost::end(rng));
75     return rng;
76 }
77 
78 /// \overload
79 template<class RandomAccessRange>
pop_heap(const RandomAccessRange & rng)80 inline const RandomAccessRange& pop_heap(const RandomAccessRange& rng)
81 {
82     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
83     std::pop_heap(boost::begin(rng), boost::end(rng));
84     return rng;
85 }
86 
87 /// \overload
88 template<class RandomAccessRange, class Compare>
pop_heap(RandomAccessRange & rng,Compare comp_pred)89 inline RandomAccessRange& pop_heap(RandomAccessRange& rng, Compare comp_pred)
90 {
91     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
92     std::pop_heap(boost::begin(rng), boost::end(rng), comp_pred);
93     return rng;
94 }
95 
96 /// \overload
97 template<class RandomAccessRange, class Compare>
pop_heap(const RandomAccessRange & rng,Compare comp_pred)98 inline const RandomAccessRange& pop_heap(const RandomAccessRange& rng, Compare comp_pred)
99 {
100     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
101     std::pop_heap(boost::begin(rng), boost::end(rng), comp_pred);
102     return rng;
103 }
104 
105 /// \brief template function make_heap
106 ///
107 /// range-based version of the make_heap std algorithm
108 ///
109 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
110 /// \pre Compare is a model of the BinaryPredicateConcept
111 template<class RandomAccessRange>
make_heap(RandomAccessRange & rng)112 inline RandomAccessRange& make_heap(RandomAccessRange& rng)
113 {
114     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
115     std::make_heap(boost::begin(rng), boost::end(rng));
116     return rng;
117 }
118 
119 /// \overload
120 template<class RandomAccessRange>
make_heap(const RandomAccessRange & rng)121 inline const RandomAccessRange& make_heap(const RandomAccessRange& rng)
122 {
123     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
124     std::make_heap(boost::begin(rng), boost::end(rng));
125     return rng;
126 }
127 
128 /// \overload
129 template<class RandomAccessRange, class Compare>
make_heap(RandomAccessRange & rng,Compare comp_pred)130 inline RandomAccessRange& make_heap(RandomAccessRange& rng, Compare comp_pred)
131 {
132     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
133     std::make_heap(boost::begin(rng), boost::end(rng), comp_pred);
134     return rng;
135 }
136 
137 /// \overload
138 template<class RandomAccessRange, class Compare>
make_heap(const RandomAccessRange & rng,Compare comp_pred)139 inline const RandomAccessRange& make_heap(const RandomAccessRange& rng, Compare comp_pred)
140 {
141     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
142     std::make_heap(boost::begin(rng), boost::end(rng), comp_pred);
143     return rng;
144 }
145 
146 /// \brief template function sort_heap
147 ///
148 /// range-based version of the sort_heap std algorithm
149 ///
150 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
151 /// \pre Compare is a model of the BinaryPredicateConcept
152 template<class RandomAccessRange>
sort_heap(RandomAccessRange & rng)153 inline RandomAccessRange& sort_heap(RandomAccessRange& rng)
154 {
155     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
156     std::sort_heap(boost::begin(rng), boost::end(rng));
157     return rng;
158 }
159 
160 /// \overload
161 template<class RandomAccessRange>
sort_heap(const RandomAccessRange & rng)162 inline const RandomAccessRange& sort_heap(const RandomAccessRange& rng)
163 {
164     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
165     std::sort_heap(boost::begin(rng), boost::end(rng));
166     return rng;
167 }
168 
169 /// \overload
170 template<class RandomAccessRange, class Compare>
sort_heap(RandomAccessRange & rng,Compare comp_pred)171 inline RandomAccessRange& sort_heap(RandomAccessRange& rng, Compare comp_pred)
172 {
173     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
174     std::sort_heap(boost::begin(rng), boost::end(rng), comp_pred);
175     return rng;
176 }
177 
178 /// \overload
179 template<class RandomAccessRange, class Compare>
sort_heap(const RandomAccessRange & rng,Compare comp_pred)180 inline const RandomAccessRange& sort_heap(const RandomAccessRange& rng, Compare comp_pred)
181 {
182     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
183     std::sort_heap(boost::begin(rng), boost::end(rng), comp_pred);
184     return rng;
185 }
186 
187     } // namespace range
188     using range::push_heap;
189     using range::pop_heap;
190     using range::make_heap;
191     using range::sort_heap;
192 } // namespace boost
193 
194 #endif // include guard
195