v3/algorithm/sort.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-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 //  Copyright (c) 1994
0014 //  Hewlett-Packard Company
0015 //
0016 //  Permission to use, copy, modify, distribute and sell this software
0017 //  and its documentation for any purpose is hereby granted without fee,
0018 //  provided that the above copyright notice appear in all copies and
0019 //  that both that copyright notice and this permission notice appear
0020 //  in supporting documentation.  Hewlett-Packard Company makes no
0021 //  representations about the suitability of this software for any
0022 //  purpose.  It is provided "as is" without express or implied warranty.
0023 //
0024 //  Copyright (c) 1996
0025 //  Silicon Graphics Computer Systems, Inc.
0026 //
0027 //  Permission to use, copy, modify, distribute and sell this software
0028 //  and its documentation for any purpose is hereby granted without fee,
0029 //  provided that the above copyright notice appear in all copies and
0030 //  that both that copyright notice and this permission notice appear
0031 //  in supporting documentation.  Silicon Graphics makes no
0032 //  representations about the suitability of this software for any
0033 //  purpose.  It is provided "as is" without express or implied warranty.
0034 //
0035
0036 #ifndef RANGES_V3_ALGORITHM_SORT_HPP
0037 #define RANGES_V3_ALGORITHM_SORT_HPP
0038
0039 #include <range/v3/range_fwd.hpp>
0040
0041 #include <range/v3/algorithm/heap_algorithm.hpp>
0042 #include <range/v3/algorithm/move_backward.hpp>
0043 #include <range/v3/algorithm/partial_sort.hpp>
0044 #include <range/v3/functional/comparisons.hpp>
0045 #include <range/v3/functional/identity.hpp>
0046 #include <range/v3/functional/invoke.hpp>
0047 #include <range/v3/iterator/concepts.hpp>
0048 #include <range/v3/iterator/operations.hpp>
0049 #include <range/v3/iterator/traits.hpp>
0050 #include <range/v3/range/access.hpp>
0051 #include <range/v3/range/concepts.hpp>
0052 #include <range/v3/range/dangling.hpp>
0053 #include <range/v3/range/traits.hpp>
0054 #include <range/v3/utility/static_const.hpp>
0055
0056 #include <range/v3/detail/prologue.hpp>
0057
0058 namespace ranges
0059 {
0060     /// \cond
0061     namespace detail
0062     {
0063         template<typename I, typename C, typename P>
0064         inline constexpr I unguarded_partition(I first, I last, C & pred, P & proj)
0065         {
0066             I mid = first + (last - first) / 2, penultimate = ranges::prev(last);
0067             auto &&x = *first, &&y = *mid, &&z = *penultimate;
0068             auto &&a = invoke(proj, (decltype(x) &&)x),
0069                  &&b = invoke(proj, (decltype(y) &&)y),
0070                  &&c = invoke(proj, (decltype(z) &&)z);
0071
0072             // Find the median:
0073             I pivot_pnt =
0074                 invoke(pred, a, b)
0075                     ? (invoke(pred, b, c) ? mid
0076                                           : (invoke(pred, a, c) ? penultimate : first))
0077                     : (invoke(pred, a, c) ? first
0078                                           : (invoke(pred, b, c) ? penultimate : mid));
0079
0080             // Do the partition:
0081             while(true)
0082             {
0083                 auto && v = *pivot_pnt;
0084                 auto && pivot = invoke(proj, (decltype(v) &&)v);
0085                 while(invoke(pred, invoke(proj, *first), pivot))
0086                     ++first;
0087                 --last;
0088                 while(invoke(pred, pivot, invoke(proj, *last)))
0089                     --last;
0090                 if(!(first < last))
0091                     return first;
0092                 ranges::iter_swap(first, last);
0093                 pivot_pnt =
0094                     pivot_pnt == first ? last : (pivot_pnt == last ? first : pivot_pnt);
0095                 ++first;
0096             }
0097         }
0098
0099         template<typename I, typename C, typename P>
0100         inline constexpr void unguarded_linear_insert(I last,
0101                                                       iter_value_t<I> val,
0102                                                       C & pred,
0103                                                       P & proj)
0104         {
0105             I next_ = prev(last);
0106             while(invoke(pred, invoke(proj, val), invoke(proj, *next_)))
0107             {
0108                 *last = iter_move(next_);
0109                 last = next_;
0110                 --next_;
0111             }
0112             *last = std::move(val);
0113         }
0114
0115         template<typename I, typename C, typename P>
0116         inline constexpr void linear_insert(I first, I last, C & pred, P & proj)
0117         {
0118             iter_value_t<I> val = iter_move(last);
0119             if(invoke(pred, invoke(proj, val), invoke(proj, *first)))
0120             {
0121                 move_backward(first, last, last + 1);
0122                 *first = std::move(val);
0123             }
0124             else
0125                 detail::unguarded_linear_insert(last, std::move(val), pred, proj);
0126         }
0127
0128         template<typename I, typename C, typename P>
0129         inline constexpr void insertion_sort(I first, I last, C & pred, P & proj)
0130         {
0131             if(first == last)
0132                 return;
0133             for(I i = next(first); i != last; ++i)
0134                 detail::linear_insert(first, i, pred, proj);
0135         }
0136
0137         template<typename I, typename C, typename P>
0138         inline constexpr void unguarded_insertion_sort(I first, I last, C & pred, P & proj)
0139         {
0140             for(I i = first; i != last; ++i)
0141                 detail::unguarded_linear_insert(i, iter_move(i), pred, proj);
0142         }
0143
0144         constexpr int introsort_threshold()
0145         {
0146             return 16;
0147         }
0148
0149         template<typename I, typename C, typename P>
0150         inline constexpr void final_insertion_sort(I first, I last, C & pred, P & proj)
0151         {
0152             if(last - first > detail::introsort_threshold())
0153             {
0154                 detail::insertion_sort(
0155                     first, first + detail::introsort_threshold(), pred, proj);
0156                 detail::unguarded_insertion_sort(
0157                     first + detail::introsort_threshold(), last, pred, proj);
0158             }
0159             else
0160                 detail::insertion_sort(first, last, pred, proj);
0161         }
0162
0163         template<typename Size>
0164         inline constexpr Size log2(Size n)
0165         {
0166             Size k = 0;
0167             for(; n != 1; n >>= 1)
0168                 ++k;
0169             return k;
0170         }
0171
0172         template<typename I, typename Size, typename C, typename P>
0173         inline constexpr void introsort_loop(I first, I last, Size depth_limit, C & pred, P & proj)
0174         {
0175             while(last - first > detail::introsort_threshold())
0176             {
0177                 if(depth_limit == 0)
0178                     return partial_sort(
0179                                first, last, last, std::ref(pred), std::ref(proj)),
0180                            void();
0181                 I cut = detail::unguarded_partition(first, last, pred, proj);
0182                 detail::introsort_loop(cut, last, --depth_limit, pred, proj);
0183                 last = cut;
0184             }
0185         }
0186     } // namespace detail
0187     /// \endcond
0188
0189     /// \addtogroup group-algorithms
0190     /// @{
0191
0192     // Introsort: Quicksort to a certain depth, then Heapsort. Insertion
0193     // sort below a certain threshold.
0194     // TODO Forward iterators, like EoP?
0195
0196     RANGES_FUNC_BEGIN(sort)
0197
0198         /// \brief function template \c sort
0199         template(typename I, typename S, typename C = less, typename P = identity)(
0200             requires sortable<I, C, P> AND random_access_iterator<I> AND
0201                 sentinel_for<S, I>)
0202         constexpr I RANGES_FUNC(sort)(I first, S end_, C pred = C{}, P proj = P{})
0203         {
0204             I last = ranges::next(first, std::move(end_));
0205             if(first != last)
0206             {
0207                 detail::introsort_loop(
0208                     first, last, detail::log2(last - first) * 2, pred, proj);
0209                 detail::final_insertion_sort(first, last, pred, proj);
0210             }
0211             return last;
0212         }
0213
0214         /// \overload
0215         template(typename Rng, typename C = less, typename P = identity)(
0216             requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
0217         constexpr borrowed_iterator_t<Rng> //
0218         RANGES_FUNC(sort)(Rng && rng, C pred = C{}, P proj = P{}) //
0219         {
0220             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0221         }
0222
0223     RANGES_FUNC_END(sort)
0224
0225     namespace cpp20
0226     {
0227         using ranges::sort;
0228     }
0229     /// @}
0230 } // namespace ranges
0231
0232 #include <range/v3/detail/epilogue.hpp>
0233
0234 #endif