v3/algorithm/heap_algorithm.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013 //===----------------------------------------------------------------------===//
0014 //
0015 //                     The LLVM Compiler Infrastructure
0016 //
0017 // This file is dual licensed under the MIT and the University of Illinois Open
0018 // Source Licenses. See LICENSE.TXT for details.
0019 //
0020 //===----------------------------------------------------------------------===//
0021 #ifndef RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
0022 #define RANGES_V3_ALGORITHM_HEAP_ALGORITHM_HPP
0023
0024 #include <functional>
0025
0026 #include <meta/meta.hpp>
0027
0028 #include <range/v3/range_fwd.hpp>
0029
0030 #include <range/v3/functional/comparisons.hpp>
0031 #include <range/v3/functional/identity.hpp>
0032 #include <range/v3/functional/invoke.hpp>
0033 #include <range/v3/iterator/concepts.hpp>
0034 #include <range/v3/iterator/operations.hpp>
0035 #include <range/v3/iterator/traits.hpp>
0036 #include <range/v3/range/access.hpp>
0037 #include <range/v3/range/concepts.hpp>
0038 #include <range/v3/range/dangling.hpp>
0039 #include <range/v3/range/traits.hpp>
0040 #include <range/v3/utility/static_const.hpp>
0041
0042 #include <range/v3/detail/prologue.hpp>
0043
0044 namespace ranges
0045 {
0046     /// \cond
0047     namespace detail
0048     {
0049         struct is_heap_until_n_fn
0050         {
0051             template(typename I, typename C = less, typename P = identity)(
0052                 requires random_access_iterator<I> AND
0053                     indirect_strict_weak_order<C, projected<I, P>>)
0054             constexpr I operator()(I const begin_,
0055                                    iter_difference_t<I> const n_,
0056                                    C pred = C{},
0057                                    P proj = P{}) const
0058             {
0059                 RANGES_EXPECT(0 <= n_);
0060                 iter_difference_t<I> p = 0, c = 1;
0061                 I pp = begin_;
0062                 while(c < n_)
0063                 {
0064                     I cp = begin_ + c;
0065                     if(invoke(pred, invoke(proj, *pp), invoke(proj, *cp)))
0066                         return cp;
0067                     ++c;
0068                     ++cp;
0069                     if(c == n_ || invoke(pred, invoke(proj, *pp), invoke(proj, *cp)))
0070                         return cp;
0071                     ++p;
0072                     ++pp;
0073                     c = 2 * p + 1;
0074                 }
0075                 return begin_ + n_;
0076             }
0077         };
0078
0079         RANGES_INLINE_VARIABLE(is_heap_until_n_fn, is_heap_until_n)
0080
0081         struct is_heap_n_fn
0082         {
0083             template(typename I, typename C = less, typename P = identity)(
0084                 requires random_access_iterator<I> AND
0085                     indirect_strict_weak_order<C, projected<I, P>>)
0086             constexpr bool operator()(I first,
0087                                       iter_difference_t<I> n,
0088                                       C pred = C{},
0089                                       P proj = P{}) const
0090             {
0091                 return is_heap_until_n(first, n, std::move(pred), std::move(proj)) ==
0092                        first + n;
0093             }
0094         };
0095
0096         RANGES_INLINE_VARIABLE(is_heap_n_fn, is_heap_n)
0097     } // namespace detail
0098     /// \endcond
0099
0100     /// \addtogroup group-algorithms
0101     /// @{
0102     RANGES_FUNC_BEGIN(is_heap_until)
0103
0104         /// \brief function template \c is_heap_until
0105         template(typename I, typename S, typename C = less, typename P = identity)(
0106             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0107             indirect_strict_weak_order<C, projected<I, P>>)
0108         constexpr I RANGES_FUNC(is_heap_until)(I first, S last, C pred = C{}, P proj = P{})
0109         {
0110             return detail::is_heap_until_n(std::move(first),
0111                                            distance(first, last),
0112                                            std::move(pred),
0113                                            std::move(proj));
0114         }
0115
0116         /// \overload
0117         template(typename Rng, typename C = less, typename P = identity)(
0118             requires random_access_range<Rng> AND
0119             indirect_strict_weak_order<C, projected<iterator_t<Rng>, P>>)
0120         constexpr borrowed_iterator_t<Rng> //
0121         RANGES_FUNC(is_heap_until)(Rng && rng, C pred = C{}, P proj = P{})
0122         {
0123             return detail::is_heap_until_n(
0124                 begin(rng), distance(rng), std::move(pred), std::move(proj));
0125         }
0126
0127     RANGES_FUNC_END(is_heap_until)
0128
0129     namespace cpp20
0130     {
0131         using ranges::is_heap_until;
0132     }
0133
0134     RANGES_FUNC_BEGIN(is_heap)
0135
0136         /// \brief function template \c is_heap
0137         template(typename I, typename S, typename C = less, typename P = identity)(
0138             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0139             indirect_strict_weak_order<C, projected<I, P>>)
0140         constexpr bool RANGES_FUNC(is_heap)(I first, S last, C pred = C{}, P proj = P{}) //
0141         {
0142             return detail::is_heap_n(std::move(first),
0143                                      distance(first, last),
0144                                      std::move(pred),
0145                                      std::move(proj));
0146         }
0147
0148         /// \overload
0149         template(typename Rng, typename C = less, typename P = identity)(
0150             requires random_access_range<Rng> AND
0151             indirect_strict_weak_order<C, projected<iterator_t<Rng>, P>>)
0152         constexpr bool RANGES_FUNC(is_heap)(Rng && rng, C pred = C{}, P proj = P{}) //
0153         {
0154             return detail::is_heap_n(
0155                 begin(rng), distance(rng), std::move(pred), std::move(proj));
0156         }
0157
0158     RANGES_FUNC_END(is_heap)
0159
0160     namespace cpp20
0161     {
0162         using ranges::is_heap;
0163     }
0164     /// @}
0165
0166     /// \cond
0167     namespace detail
0168     {
0169         struct sift_up_n_fn
0170         {
0171             template<typename I, typename C = less, typename P = identity>
0172             constexpr void operator()(I first,
0173                                       iter_difference_t<I> len,
0174                                       C pred = C{},
0175                                       P proj = P{}) const
0176             {
0177                 if(len > 1)
0178                 {
0179                     I last = first + len;
0180                     len = (len - 2) / 2;
0181                     I i = first + len;
0182                     if(invoke(pred, invoke(proj, *i), invoke(proj, *--last)))
0183                     {
0184                         iter_value_t<I> v = iter_move(last);
0185                         do
0186                         {
0187                             *last = iter_move(i);
0188                             last = i;
0189                             if(len == 0)
0190                                 break;
0191                             len = (len - 1) / 2;
0192                             i = first + len;
0193                         } while(invoke(pred, invoke(proj, *i), invoke(proj, v)));
0194                         *last = std::move(v);
0195                     }
0196                 }
0197             }
0198         };
0199
0200         RANGES_INLINE_VARIABLE(sift_up_n_fn, sift_up_n)
0201
0202         struct sift_down_n_fn
0203         {
0204             template<typename I, typename C = less, typename P = identity>
0205             constexpr void operator()(I first,
0206                                       iter_difference_t<I> len,
0207                                       I start,
0208                                       C pred = C{},
0209                                       P proj = P{}) const
0210             {
0211                 // left-child of start is at 2 * start + 1
0212                 // right-child of start is at 2 * start + 2
0213                 auto child = start - first;
0214
0215                 if(len < 2 || (len - 2) / 2 < child)
0216                     return;
0217
0218                 child = 2 * child + 1;
0219                 I child_i = first + child;
0220
0221                 if((child + 1) < len &&
0222                    invoke(pred, invoke(proj, *child_i), invoke(proj, *(child_i + 1))))
0223                 {
0224                     // right-child exists and is greater than left-child
0225                     ++child_i;
0226                     ++child;
0227                 }
0228
0229                 // check if we are in heap-order
0230                 if(invoke(pred, invoke(proj, *child_i), invoke(proj, *start)))
0231                     // we are, start is larger than it's largest child
0232                     return;
0233
0234                 iter_value_t<I> top = iter_move(start);
0235                 do
0236                 {
0237                     // we are not in heap-order, swap the parent with it's largest child
0238                     *start = iter_move(child_i);
0239                     start = child_i;
0240
0241                     if((len - 2) / 2 < child)
0242                         break;
0243
0244                     // recompute the child based off of the updated parent
0245                     child = 2 * child + 1;
0246                     child_i = first + child;
0247
0248                     if((child + 1) < len &&
0249                        invoke(pred, invoke(proj, *child_i), invoke(proj, *(child_i + 1))))
0250                     {
0251                         // right-child exists and is greater than left-child
0252                         ++child_i;
0253                         ++child;
0254                     }
0255
0256                     // check if we are in heap-order
0257                 } while(!invoke(pred, invoke(proj, *child_i), invoke(proj, top)));
0258                 *start = std::move(top);
0259             }
0260         };
0261
0262         RANGES_INLINE_VARIABLE(sift_down_n_fn, sift_down_n)
0263     } // namespace detail
0264     /// \endcond
0265
0266     /// \addtogroup group-algorithms
0267     /// @{
0268     RANGES_FUNC_BEGIN(push_heap)
0269
0270         /// \brief function template \c push_heap
0271         template(typename I, typename S, typename C = less, typename P = identity)(
0272             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0273             sortable<I, C, P>)
0274         constexpr I RANGES_FUNC(push_heap)(I first, S last, C pred = C{}, P proj = P{})
0275         {
0276             auto n = distance(first, last);
0277             detail::sift_up_n(first, n, std::move(pred), std::move(proj));
0278             return first + n;
0279         }
0280
0281         /// \overload
0282         template(typename Rng, typename C = less, typename P = identity)(
0283             requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0284         constexpr borrowed_iterator_t<Rng> //
0285         RANGES_FUNC(push_heap)(Rng && rng, C pred = C{}, P proj = P{}) //
0286         {
0287             iterator_t<Rng> first = ranges::begin(rng);
0288             auto n = distance(rng);
0289             detail::sift_up_n(first, n, std::move(pred), std::move(proj));
0290             return first + n;
0291         }
0292
0293     RANGES_FUNC_END(push_heap)
0294
0295     namespace cpp20
0296     {
0297         using ranges::push_heap;
0298     }
0299     /// @}
0300
0301     /// \cond
0302     namespace detail
0303     {
0304         struct pop_heap_n_fn
0305         {
0306             template(typename I, typename C = less, typename P = identity)(
0307                 requires random_access_iterator<I> AND sortable<I, C, P>)
0308             constexpr void operator()(I first,
0309                                       iter_difference_t<I> len,
0310                                       C pred = C{},
0311                                       P proj = P{}) const
0312             {
0313                 if(len > 1)
0314                 {
0315                     ranges::iter_swap(first, first + (len - 1));
0316                     detail::sift_down_n(
0317                         first, len - 1, first, std::move(pred), std::move(proj));
0318                 }
0319             }
0320         };
0321
0322         RANGES_INLINE_VARIABLE(pop_heap_n_fn, pop_heap_n)
0323     } // namespace detail
0324     /// \endcond
0325
0326     /// \addtogroup group-algorithms
0327     /// @{
0328     RANGES_FUNC_BEGIN(pop_heap)
0329
0330         /// \brief function template \c pop_heap
0331         template(typename I, typename S, typename C = less, typename P = identity)(
0332             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0333             sortable<I, C, P>)
0334         constexpr I RANGES_FUNC(pop_heap)(I first, S last, C pred = C{}, P proj = P{})
0335         {
0336             auto n = distance(first, last);
0337             detail::pop_heap_n(first, n, std::move(pred), std::move(proj));
0338             return first + n;
0339         }
0340
0341         /// \overload
0342         template(typename Rng, typename C = less, typename P = identity)(
0343             requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0344         constexpr borrowed_iterator_t<Rng> //
0345         RANGES_FUNC(pop_heap)(Rng && rng, C pred = C{}, P proj = P{})
0346         {
0347             iterator_t<Rng> first = ranges::begin(rng);
0348             auto n = distance(rng);
0349             detail::pop_heap_n(first, n, std::move(pred), std::move(proj));
0350             return first + n;
0351         }
0352
0353     RANGES_FUNC_END(pop_heap)
0354
0355     namespace cpp20
0356     {
0357         using ranges::pop_heap;
0358     }
0359
0360     RANGES_FUNC_BEGIN(make_heap)
0361
0362         /// \brief function template \c make_heap
0363         template(typename I, typename S, typename C = less, typename P = identity)(
0364             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0365             sortable<I, C, P>)
0366         constexpr I RANGES_FUNC(make_heap)(I first, S last, C pred = C{}, P proj = P{})
0367         {
0368             iter_difference_t<I> const n = distance(first, last);
0369             if(n > 1)
0370                 // start from the first parent, there is no need to consider children
0371                 for(auto start = (n - 2) / 2; start >= 0; --start)
0372                     detail::sift_down_n(
0373                         first, n, first + start, ranges::ref(pred), ranges::ref(proj));
0374             return first + n;
0375         }
0376
0377         /// \overload
0378         template(typename Rng, typename C = less, typename P = identity)(
0379             requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0380         constexpr borrowed_iterator_t<Rng> //
0381         RANGES_FUNC(make_heap)(Rng && rng, C pred = C{}, P proj = P{})
0382         {
0383             iterator_t<Rng> first = ranges::begin(rng);
0384             auto const n = distance(rng);
0385             if(n > 1)
0386                 // start from the first parent, there is no need to consider children
0387                 for(auto start = (n - 2) / 2; start >= 0; --start)
0388                     detail::sift_down_n(
0389                         first, n, first + start, ranges::ref(pred), ranges::ref(proj));
0390             return first + n;
0391         }
0392
0393     RANGES_FUNC_END(make_heap)
0394
0395     namespace cpp20
0396     {
0397         using ranges::make_heap;
0398     }
0399
0400     RANGES_FUNC_BEGIN(sort_heap)
0401
0402         template(typename I, typename S, typename C = less, typename P = identity)(
0403             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0404             sortable<I, C, P>)
0405         constexpr I RANGES_FUNC(sort_heap)(I first, S last, C pred = C{}, P proj = P{})
0406         {
0407             iter_difference_t<I> const n = distance(first, last);
0408             for(auto i = n; i > 1; --i)
0409                 detail::pop_heap_n(first, i, ranges::ref(pred), ranges::ref(proj));
0410             return first + n;
0411         }
0412
0413         template(typename Rng, typename C = less, typename P = identity)(
0414             requires random_access_range<Rng &> AND sortable<iterator_t<Rng>, C, P>)
0415         constexpr borrowed_iterator_t<Rng> //
0416         RANGES_FUNC(sort_heap)(Rng && rng, C pred = C{}, P proj = P{})
0417         {
0418             iterator_t<Rng> first = ranges::begin(rng);
0419             auto const n = distance(rng);
0420             for(auto i = n; i > 1; --i)
0421                 detail::pop_heap_n(first, i, ranges::ref(pred), ranges::ref(proj));
0422             return first + n;
0423         }
0424
0425     RANGES_FUNC_END(sort_heap)
0426
0427     namespace cpp20
0428     {
0429         using ranges::sort_heap;
0430     }
0431     /// @}
0432 } // namespace ranges
0433
0434 #include <range/v3/detail/epilogue.hpp>
0435
0436 #endif