range/algorithm/heap_algorithm.hpp

0001 //  Copyright Neil Groves 2009. Use, modification and
0002 //  distribution is subject to the Boost Software License, Version
0003 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005 //
0006 //
0007 // For more information, see http://www.boost.org/libs/range/
0008 //
0009 #ifndef BOOST_RANGE_ALGORITHM_HEAP_ALGORITHM_HPP_INCLUDED
0010 #define BOOST_RANGE_ALGORITHM_HEAP_ALGORITHM_HPP_INCLUDED
0011
0012 #include <boost/concept_check.hpp>
0013 #include <boost/range/begin.hpp>
0014 #include <boost/range/end.hpp>
0015 #include <boost/range/concepts.hpp>
0016 #include <algorithm>
0017
0018 namespace boost
0019 {
0020     namespace range
0021     {
0022
0023 /// \brief template function push_heap
0024 ///
0025 /// range-based version of the push_heap std algorithm
0026 ///
0027 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
0028 /// \pre Compare is a model of the BinaryPredicateConcept
0029 template<class RandomAccessRange>
0030 inline RandomAccessRange& push_heap(RandomAccessRange& rng)
0031 {
0032     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0033     std::push_heap(boost::begin(rng), boost::end(rng));
0034     return rng;
0035 }
0036
0037 /// \overload
0038 template<class RandomAccessRange>
0039 inline const RandomAccessRange& push_heap(const RandomAccessRange& rng)
0040 {
0041     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0042     std::push_heap(boost::begin(rng), boost::end(rng));
0043     return rng;
0044 }
0045
0046 /// \overload
0047 template<class RandomAccessRange, class Compare>
0048 inline RandomAccessRange& push_heap(RandomAccessRange& rng, Compare comp_pred)
0049 {
0050     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0051     std::push_heap(boost::begin(rng), boost::end(rng), comp_pred);
0052     return rng;
0053 }
0054
0055 /// \overload
0056 template<class RandomAccessRange, class Compare>
0057 inline const RandomAccessRange& push_heap(const RandomAccessRange& rng, Compare comp_pred)
0058 {
0059     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0060     std::push_heap(boost::begin(rng), boost::end(rng), comp_pred);
0061     return rng;
0062 }
0063
0064 /// \brief template function pop_heap
0065 ///
0066 /// range-based version of the pop_heap std algorithm
0067 ///
0068 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
0069 /// \pre Compare is a model of the BinaryPredicateConcept
0070 template<class RandomAccessRange>
0071 inline RandomAccessRange& pop_heap(RandomAccessRange& rng)
0072 {
0073     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0074     std::pop_heap(boost::begin(rng), boost::end(rng));
0075     return rng;
0076 }
0077
0078 /// \overload
0079 template<class RandomAccessRange>
0080 inline const RandomAccessRange& pop_heap(const RandomAccessRange& rng)
0081 {
0082     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0083     std::pop_heap(boost::begin(rng), boost::end(rng));
0084     return rng;
0085 }
0086
0087 /// \overload
0088 template<class RandomAccessRange, class Compare>
0089 inline RandomAccessRange& pop_heap(RandomAccessRange& rng, Compare comp_pred)
0090 {
0091     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0092     std::pop_heap(boost::begin(rng), boost::end(rng), comp_pred);
0093     return rng;
0094 }
0095
0096 /// \overload
0097 template<class RandomAccessRange, class Compare>
0098 inline const RandomAccessRange& pop_heap(const RandomAccessRange& rng, Compare comp_pred)
0099 {
0100     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0101     std::pop_heap(boost::begin(rng), boost::end(rng), comp_pred);
0102     return rng;
0103 }
0104
0105 /// \brief template function make_heap
0106 ///
0107 /// range-based version of the make_heap std algorithm
0108 ///
0109 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
0110 /// \pre Compare is a model of the BinaryPredicateConcept
0111 template<class RandomAccessRange>
0112 inline RandomAccessRange& make_heap(RandomAccessRange& rng)
0113 {
0114     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0115     std::make_heap(boost::begin(rng), boost::end(rng));
0116     return rng;
0117 }
0118
0119 /// \overload
0120 template<class RandomAccessRange>
0121 inline const RandomAccessRange& make_heap(const RandomAccessRange& rng)
0122 {
0123     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0124     std::make_heap(boost::begin(rng), boost::end(rng));
0125     return rng;
0126 }
0127
0128 /// \overload
0129 template<class RandomAccessRange, class Compare>
0130 inline RandomAccessRange& make_heap(RandomAccessRange& rng, Compare comp_pred)
0131 {
0132     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0133     std::make_heap(boost::begin(rng), boost::end(rng), comp_pred);
0134     return rng;
0135 }
0136
0137 /// \overload
0138 template<class RandomAccessRange, class Compare>
0139 inline const RandomAccessRange& make_heap(const RandomAccessRange& rng, Compare comp_pred)
0140 {
0141     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0142     std::make_heap(boost::begin(rng), boost::end(rng), comp_pred);
0143     return rng;
0144 }
0145
0146 /// \brief template function sort_heap
0147 ///
0148 /// range-based version of the sort_heap std algorithm
0149 ///
0150 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
0151 /// \pre Compare is a model of the BinaryPredicateConcept
0152 template<class RandomAccessRange>
0153 inline RandomAccessRange& sort_heap(RandomAccessRange& rng)
0154 {
0155     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0156     std::sort_heap(boost::begin(rng), boost::end(rng));
0157     return rng;
0158 }
0159
0160 /// \overload
0161 template<class RandomAccessRange>
0162 inline const RandomAccessRange& sort_heap(const RandomAccessRange& rng)
0163 {
0164     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0165     std::sort_heap(boost::begin(rng), boost::end(rng));
0166     return rng;
0167 }
0168
0169 /// \overload
0170 template<class RandomAccessRange, class Compare>
0171 inline RandomAccessRange& sort_heap(RandomAccessRange& rng, Compare comp_pred)
0172 {
0173     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0174     std::sort_heap(boost::begin(rng), boost::end(rng), comp_pred);
0175     return rng;
0176 }
0177
0178 /// \overload
0179 template<class RandomAccessRange, class Compare>
0180 inline const RandomAccessRange& sort_heap(const RandomAccessRange& rng, Compare comp_pred)
0181 {
0182     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0183     std::sort_heap(boost::begin(rng), boost::end(rng), comp_pred);
0184     return rng;
0185 }
0186
0187     } // namespace range
0188     using range::push_heap;
0189     using range::pop_heap;
0190     using range::make_heap;
0191     using range::sort_heap;
0192 } // namespace boost
0193
0194 #endif // include guard