v3/algorithm/stable_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_STABLE_SORT_HPP
0037 #define RANGES_V3_ALGORITHM_STABLE_SORT_HPP
0038
0039 #include <functional>
0040 #include <iterator>
0041 #include <memory>
0042
0043 #include <range/v3/range_fwd.hpp>
0044
0045 #include <range/v3/algorithm/inplace_merge.hpp>
0046 #include <range/v3/algorithm/merge.hpp>
0047 #include <range/v3/algorithm/min.hpp>
0048 #include <range/v3/algorithm/sort.hpp>
0049 #include <range/v3/functional/comparisons.hpp>
0050 #include <range/v3/functional/identity.hpp>
0051 #include <range/v3/iterator/concepts.hpp>
0052 #include <range/v3/iterator/move_iterators.hpp>
0053 #include <range/v3/iterator/operations.hpp>
0054 #include <range/v3/iterator/traits.hpp>
0055 #include <range/v3/range/access.hpp>
0056 #include <range/v3/range/concepts.hpp>
0057 #include <range/v3/range/dangling.hpp>
0058 #include <range/v3/range/traits.hpp>
0059 #include <range/v3/utility/memory.hpp>
0060 #include <range/v3/utility/static_const.hpp>
0061
0062 #include <range/v3/detail/prologue.hpp>
0063
0064 namespace ranges
0065 {
0066     /// \addtogroup group-algorithms
0067     /// @{
0068
0069     /// \cond
0070     namespace detail
0071     {
0072         template<typename I, typename C, typename P>
0073         void inplace_stable_sort(I first, I last, C & pred, P & proj)
0074         {
0075             if(last - first < 15)
0076                 return detail::insertion_sort(first, last, pred, proj), void();
0077             I middle = first + (last - first) / 2;
0078             detail::inplace_stable_sort(first, middle, pred, proj);
0079             detail::inplace_stable_sort(middle, last, pred, proj);
0080             detail::inplace_merge_no_buffer(first,
0081                                             middle,
0082                                             last,
0083                                             middle - first,
0084                                             last - middle,
0085                                             std::ref(pred),
0086                                             std::ref(proj));
0087         }
0088
0089         template<typename I1, typename I2, typename D, typename C, typename P>
0090         void merge_sort_loop(I1 first, I1 last, I2 result, D step_size, C & pred,
0091                              P & proj)
0092         {
0093             D two_step = 2 * step_size;
0094             while(last - first >= two_step)
0095             {
0096                 result = merge(make_move_iterator(first),
0097                                make_move_iterator(first + step_size),
0098                                make_move_iterator(first + step_size),
0099                                make_move_iterator(first + two_step),
0100                                result,
0101                                std::ref(pred),
0102                                std::ref(proj),
0103                                std::ref(proj))
0104                              .out;
0105                 first += two_step;
0106             }
0107             step_size = ranges::min(D(last - first), step_size);
0108             merge(make_move_iterator(first),
0109                   make_move_iterator(first + step_size),
0110                   make_move_iterator(first + step_size),
0111                   make_move_iterator(last),
0112                   result,
0113                   std::ref(pred),
0114                   std::ref(proj),
0115                   std::ref(proj));
0116         }
0117
0118         constexpr int merge_sort_chunk_size()
0119         {
0120             return 7;
0121         }
0122
0123         template<typename I, typename D, typename C, typename P>
0124         void chunk_insertion_sort(I first, I last, D chunk_size, C & pred, P & proj)
0125         {
0126             while(last - first >= chunk_size)
0127             {
0128                 detail::insertion_sort(first, first + chunk_size, pred, proj);
0129                 first += chunk_size;
0130             }
0131             detail::insertion_sort(first, last, pred, proj);
0132         }
0133
0134         // buffer points to raw memory, we create objects, and then restore the buffer to
0135         // raw memory by destroying the objects on return.
0136         template<typename I, typename V, typename C, typename P>
0137         void merge_sort_with_buffer(I first, I last, V * buffer, C & pred, P & proj)
0138         {
0139             iter_difference_t<I> len = last - first,
0140                                  step_size = detail::merge_sort_chunk_size();
0141             detail::chunk_insertion_sort(first, last, step_size, pred, proj);
0142             if(step_size >= len)
0143                 return;
0144             // The first call to merge_sort_loop moves into raw storage. Construct
0145             // on-demand and keep track of how many objects we need to destroy.
0146             V * buffer_end = buffer + static_cast<std::ptrdiff_t>(len);
0147             auto tmpbuf = make_raw_buffer(buffer);
0148             detail::merge_sort_loop(first, last, tmpbuf.begin(), step_size, pred, proj);
0149             step_size *= 2;
0150         loop:
0151             detail::merge_sort_loop(
0152                 buffer, buffer_end, first, (std::ptrdiff_t)step_size, pred, proj);
0153             step_size *= 2;
0154             if(step_size >= len)
0155                 return;
0156             detail::merge_sort_loop(first, last, buffer, step_size, pred, proj);
0157             step_size *= 2;
0158             goto loop;
0159         }
0160
0161         // buffer points to raw memory
0162         template<typename I, typename V, typename C, typename P>
0163         void stable_sort_adaptive(I first, I last, V * buffer, std::ptrdiff_t buffer_size,
0164                                   C & pred, P & proj)
0165         {
0166             iter_difference_t<I> len = (last - first + 1) / 2;
0167             I middle = first + len;
0168             if(len > buffer_size)
0169             {
0170                 detail::stable_sort_adaptive(
0171                     first, middle, buffer, buffer_size, pred, proj);
0172                 detail::stable_sort_adaptive(
0173                     middle, last, buffer, buffer_size, pred, proj);
0174             }
0175             else
0176             {
0177                 detail::merge_sort_with_buffer(first, middle, buffer, pred, proj);
0178                 detail::merge_sort_with_buffer(middle, last, buffer, pred, proj);
0179             }
0180             detail::merge_adaptive(first,
0181                                    middle,
0182                                    last,
0183                                    middle - first,
0184                                    last - middle,
0185                                    buffer,
0186                                    buffer_size,
0187                                    std::ref(pred),
0188                                    std::ref(proj));
0189         }
0190     } // namespace detail
0191     /// \endcond
0192
0193     RANGES_FUNC_BEGIN(stable_sort)
0194
0195         /// \brief function template \c stable_sort
0196         template(typename I, typename S, typename C = less, typename P = identity)(
0197             requires sortable<I, C, P> AND random_access_iterator<I> AND
0198             sentinel_for<S, I>)
0199         I RANGES_FUNC(stable_sort)(I first, S end_, C pred = C{}, P proj = P{})
0200         {
0201             I last = ranges::next(first, end_);
0202             using D = iter_difference_t<I>;
0203             using V = iter_value_t<I>;
0204             D len = last - first;
0205             auto buf =
0206                 len > 256 ? detail::get_temporary_buffer<V>(len) : detail::value_init{};
0207             std::unique_ptr<V, detail::return_temporary_buffer> h{buf.first};
0208             if(buf.first == nullptr)
0209                 detail::inplace_stable_sort(first, last, pred, proj);
0210             else
0211                 detail::stable_sort_adaptive(
0212                     first, last, buf.first, buf.second, pred, proj);
0213             return last;
0214         }
0215
0216         /// \overload
0217         template(typename Rng, typename C = less, typename P = identity)(
0218             requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
0219         borrowed_iterator_t<Rng> //
0220         RANGES_FUNC(stable_sort)(Rng && rng, C pred = C{}, P proj = P{}) //
0221         {
0222             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0223         }
0224
0225     RANGES_FUNC_END(stable_sort)
0226
0227     namespace cpp20
0228     {
0229         using ranges::stable_sort;
0230     }
0231     /// @}
0232 } // namespace ranges
0233
0234 #include <range/v3/detail/epilogue.hpp>
0235
0236 #endif