v3/algorithm/inplace_merge.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_INPLACE_MERGE_HPP
0022 #define RANGES_V3_ALGORITHM_INPLACE_MERGE_HPP
0023
0024 #include <functional>
0025 #include <memory>
0026 #include <new>
0027 #include <type_traits>
0028
0029 #include <range/v3/range_fwd.hpp>
0030
0031 #include <range/v3/algorithm/lower_bound.hpp>
0032 #include <range/v3/algorithm/merge.hpp>
0033 #include <range/v3/algorithm/min.hpp>
0034 #include <range/v3/algorithm/move.hpp>
0035 #include <range/v3/algorithm/rotate.hpp>
0036 #include <range/v3/algorithm/upper_bound.hpp>
0037 #include <range/v3/functional/comparisons.hpp>
0038 #include <range/v3/functional/identity.hpp>
0039 #include <range/v3/functional/invoke.hpp>
0040 #include <range/v3/functional/not_fn.hpp>
0041 #include <range/v3/iterator/concepts.hpp>
0042 #include <range/v3/iterator/move_iterators.hpp>
0043 #include <range/v3/iterator/operations.hpp>
0044 #include <range/v3/iterator/reverse_iterator.hpp>
0045 #include <range/v3/iterator/traits.hpp>
0046 #include <range/v3/range/access.hpp>
0047 #include <range/v3/range/concepts.hpp>
0048 #include <range/v3/range/dangling.hpp>
0049 #include <range/v3/range/traits.hpp>
0050 #include <range/v3/utility/memory.hpp>
0051 #include <range/v3/utility/static_const.hpp>
0052 #include <range/v3/utility/swap.hpp>
0053
0054 #include <range/v3/detail/prologue.hpp>
0055
0056 namespace ranges
0057 {
0058     /// \cond
0059     namespace detail
0060     {
0061         struct merge_adaptive_fn
0062         {
0063         private:
0064             template<typename I, typename C, typename P>
0065             static void impl(I first, I middle, I last, iter_difference_t<I> len1,
0066                              iter_difference_t<I> len2, iter_value_t<I> * const buf,
0067                              C & pred, P & proj)
0068             {
0069                 auto tmpbuf = make_raw_buffer(buf);
0070                 if(len1 <= len2)
0071                 {
0072                     auto p = ranges::move(first, middle, tmpbuf.begin()).out;
0073                     merge(make_move_iterator(buf),
0074                           make_move_iterator(p.base().base()),
0075                           make_move_iterator(std::move(middle)),
0076                           make_move_iterator(std::move(last)),
0077                           std::move(first),
0078                           std::ref(pred),
0079                           std::ref(proj),
0080                           std::ref(proj));
0081                 }
0082                 else
0083                 {
0084                     auto p = ranges::move(middle, last, tmpbuf.begin()).out;
0085                     using RBi = ranges::reverse_iterator<I>;
0086                     using Rv = ranges::reverse_iterator<iter_value_t<I> *>;
0087                     merge(make_move_iterator(RBi{std::move(middle)}),
0088                           make_move_iterator(RBi{std::move(first)}),
0089                           make_move_iterator(Rv{p.base().base()}),
0090                           make_move_iterator(Rv{buf}),
0091                           RBi{std::move(last)},
0092                           not_fn(std::ref(pred)),
0093                           std::ref(proj),
0094                           std::ref(proj));
0095                 }
0096             }
0097
0098         public:
0099             template(typename I, typename C = less, typename P = identity)(
0100                 requires bidirectional_iterator<I> AND sortable<I, C, P>)
0101             void operator()(I first, I middle, I last, iter_difference_t<I> len1,
0102                             iter_difference_t<I> len2, iter_value_t<I> * buf,
0103                             std::ptrdiff_t buf_size, C pred = C{}, P proj = P{}) const
0104             {
0105                 using D = iter_difference_t<I>;
0106                 while(true)
0107                 {
0108                     // if middle == last, we're done
0109                     if(len2 == 0)
0110                         return;
0111                     // shrink [first, middle) as much as possible (with no moves),
0112                     // returning if it shrinks to 0
0113                     for(; true; ++first, --len1)
0114                     {
0115                         if(len1 == 0)
0116                             return;
0117                         if(invoke(pred, invoke(proj, *middle), invoke(proj, *first)))
0118                             break;
0119                     }
0120                     if(len1 <= buf_size || len2 <= buf_size)
0121                     {
0122                         merge_adaptive_fn::impl(std::move(first),
0123                                                 std::move(middle),
0124                                                 std::move(last),
0125                                                 len1,
0126                                                 len2,
0127                                                 buf,
0128                                                 pred,
0129                                                 proj);
0130                         return;
0131                     }
0132                     // first < middle < end
0133                     // *first > *middle
0134                     // partition [first, m1) [m1, middle) [middle, m2) [m2, last) such
0135                     // that
0136                     //     all elements in:
0137                     //         [first, m1)  <= [middle, m2)
0138                     //         [middle, m2) <  [m1, middle)
0139                     //         [m1, middle) <= [m2, last)
0140                     //     and m1 or m2 is in the middle of its range
0141                     I m1;    // "median" of [first, middle)
0142                     I m2;    // "median" of [middle, last)
0143                     D len11; // distance(first, m1)
0144                     D len21; // distance(middle, m2)
0145                     // binary search smaller range
0146                     if(len1 < len2)
0147                     { // len >= 1, len2 >= 2
0148                         len21 = len2 / 2;
0149                         m2 = next(middle, len21);
0150                         m1 = upper_bound(first,
0151                                          middle,
0152                                          invoke(proj, *m2),
0153                                          std::ref(pred),
0154                                          std::ref(proj));
0155                         len11 = distance(first, m1);
0156                     }
0157                     else
0158                     {
0159                         if(len1 == 1)
0160                         { // len1 >= len2 && len2 > 0, therefore len2 == 1
0161                             // It is known *first > *middle
0162                             ranges::iter_swap(first, middle);
0163                             return;
0164                         }
0165                         // len1 >= 2, len2 >= 1
0166                         len11 = len1 / 2;
0167                         m1 = next(first, len11);
0168                         m2 = lower_bound(middle,
0169                                          last,
0170                                          invoke(proj, *m1),
0171                                          std::ref(pred),
0172                                          std::ref(proj));
0173                         len21 = distance(middle, m2);
0174                     }
0175                     D len12 = len1 - len11; // distance(m1, middle)
0176                     D len22 = len2 - len21; // distance(m2, last)
0177                     // [first, m1) [m1, middle) [middle, m2) [m2, last)
0178                     // swap middle two partitions
0179                     middle = rotate(m1, std::move(middle), m2).begin();
0180                     // len12 and len21 now have swapped meanings
0181                     // merge smaller range with recursive call and larger with tail
0182                     // recursion elimination
0183                     if(len11 + len21 < len12 + len22)
0184                     {
0185                         (*this)(std::move(first),
0186                                 std::move(m1),
0187                                 middle,
0188                                 len11,
0189                                 len21,
0190                                 buf,
0191                                 buf_size,
0192                                 std::ref(pred),
0193                                 std::ref(proj));
0194                         first = std::move(middle);
0195                         middle = std::move(m2);
0196                         len1 = len12;
0197                         len2 = len22;
0198                     }
0199                     else
0200                     {
0201                         (*this)(middle,
0202                                 std::move(m2),
0203                                 std::move(last),
0204                                 len12,
0205                                 len22,
0206                                 buf,
0207                                 buf_size,
0208                                 std::ref(pred),
0209                                 std::ref(proj));
0210                         last = std::move(middle);
0211                         middle = std::move(m1);
0212                         len1 = len11;
0213                         len2 = len21;
0214                     }
0215                 }
0216             }
0217         };
0218
0219         RANGES_INLINE_VARIABLE(merge_adaptive_fn, merge_adaptive)
0220
0221         struct inplace_merge_no_buffer_fn
0222         {
0223             template(typename I, typename C = less, typename P = identity)(
0224                 requires bidirectional_iterator<I> AND sortable<I, C, P>)
0225             void operator()(I first, I middle, I last, iter_difference_t<I> len1,
0226                             iter_difference_t<I> len2, C pred = C{}, P proj = P{}) const
0227             {
0228                 merge_adaptive(std::move(first),
0229                                std::move(middle),
0230                                std::move(last),
0231                                len1,
0232                                len2,
0233                                static_cast<iter_value_t<I> *>(nullptr),
0234                                0,
0235                                std::move(pred),
0236                                std::move(proj));
0237             }
0238         };
0239
0240         RANGES_INLINE_VARIABLE(inplace_merge_no_buffer_fn, inplace_merge_no_buffer)
0241     } // namespace detail
0242     /// \endcond
0243
0244     /// \addtogroup group-algorithms
0245     /// @{
0246     RANGES_FUNC_BEGIN(inplace_merge)
0247
0248         // TODO reimplement to only need forward iterators
0249
0250         /// \brief function template \c inplace_merge
0251         template(typename I, typename S, typename C = less, typename P = identity)(
0252             requires bidirectional_iterator<I> AND sortable<I, C, P>)
0253         I RANGES_FUNC(inplace_merge)(
0254             I first, I middle, S last, C pred = C{}, P proj = P{})
0255         {
0256             using value_type = iter_value_t<I>;
0257             auto len1 = distance(first, middle);
0258             auto len2_and_end = enumerate(middle, last);
0259             auto buf_size = ranges::min(len1, len2_and_end.first);
0260             std::pair<value_type *, std::ptrdiff_t> buf{nullptr, 0};
0261             std::unique_ptr<value_type, detail::return_temporary_buffer> h;
0262             if(detail::is_trivially_copy_assignable_v<value_type> && 8 < buf_size)
0263             {
0264                 buf = detail::get_temporary_buffer<value_type>(buf_size);
0265                 h.reset(buf.first);
0266             }
0267             detail::merge_adaptive(std::move(first),
0268                                    std::move(middle),
0269                                    len2_and_end.second,
0270                                    len1,
0271                                    len2_and_end.first,
0272                                    buf.first,
0273                                    buf.second,
0274                                    std::move(pred),
0275                                    std::move(proj));
0276             return len2_and_end.second;
0277         }
0278
0279         /// \overload
0280         template(typename Rng, typename C = less, typename P = identity)(
0281             requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0282         borrowed_iterator_t<Rng> RANGES_FUNC(inplace_merge)(
0283             Rng && rng, iterator_t<Rng> middle, C pred = C{}, P proj = P{})
0284         {
0285             return (*this)(begin(rng),
0286                            std::move(middle),
0287                            end(rng),
0288                            std::move(pred),
0289                            std::move(proj));
0290         }
0291
0292     RANGES_FUNC_END(inplace_merge)
0293
0294     namespace cpp20
0295     {
0296         using ranges::inplace_merge;
0297     }
0298     /// @}
0299 } // namespace ranges
0300
0301 #include <range/v3/detail/epilogue.hpp>
0302
0303 #endif