v1/__algorithm/inplace_merge.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H
0010 #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H
0011
0012 #include <__algorithm/comp.h>
0013 #include <__algorithm/comp_ref_type.h>
0014 #include <__algorithm/iterator_operations.h>
0015 #include <__algorithm/lower_bound.h>
0016 #include <__algorithm/min.h>
0017 #include <__algorithm/move.h>
0018 #include <__algorithm/rotate.h>
0019 #include <__algorithm/upper_bound.h>
0020 #include <__config>
0021 #include <__cstddef/ptrdiff_t.h>
0022 #include <__functional/identity.h>
0023 #include <__iterator/iterator_traits.h>
0024 #include <__iterator/reverse_iterator.h>
0025 #include <__memory/destruct_n.h>
0026 #include <__memory/unique_ptr.h>
0027 #include <__memory/unique_temporary_buffer.h>
0028 #include <__utility/move.h>
0029 #include <__utility/pair.h>
0030
0031 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0032 #  pragma GCC system_header
0033 #endif
0034
0035 _LIBCPP_PUSH_MACROS
0036 #include <__undef_macros>
0037
0038 _LIBCPP_BEGIN_NAMESPACE_STD
0039
0040 template <class _Predicate>
0041 class __invert // invert the sense of a comparison
0042 {
0043 private:
0044   _Predicate __p_;
0045
0046 public:
0047   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __invert() {}
0048
0049   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 explicit __invert(_Predicate __p) : __p_(__p) {}
0050
0051   template <class _T1>
0052   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator()(const _T1& __x) {
0053     return !__p_(__x);
0054   }
0055
0056   template <class _T1, class _T2>
0057   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool operator()(const _T1& __x, const _T2& __y) {
0058     return __p_(__y, __x);
0059   }
0060 };
0061
0062 template <class _AlgPolicy,
0063           class _Compare,
0064           class _InputIterator1,
0065           class _Sent1,
0066           class _InputIterator2,
0067           class _Sent2,
0068           class _OutputIterator>
0069 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __half_inplace_merge(
0070     _InputIterator1 __first1,
0071     _Sent1 __last1,
0072     _InputIterator2 __first2,
0073     _Sent2 __last2,
0074     _OutputIterator __result,
0075     _Compare&& __comp) {
0076   for (; __first1 != __last1; ++__result) {
0077     if (__first2 == __last2) {
0078       std::__move<_AlgPolicy>(__first1, __last1, __result);
0079       return;
0080     }
0081
0082     if (__comp(*__first2, *__first1)) {
0083       *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
0084       ++__first2;
0085     } else {
0086       *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);
0087       ++__first1;
0088     }
0089   }
0090   // __first2 through __last2 are already in the right spot.
0091 }
0092
0093 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
0094 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __buffered_inplace_merge(
0095     _BidirectionalIterator __first,
0096     _BidirectionalIterator __middle,
0097     _BidirectionalIterator __last,
0098     _Compare&& __comp,
0099     typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
0100     typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
0101     typename iterator_traits<_BidirectionalIterator>::value_type* __buff) {
0102   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
0103   __destruct_n __d(0);
0104   unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
0105   if (__len1 <= __len2) {
0106     value_type* __p = __buff;
0107     for (_BidirectionalIterator __i = __first; __i != __middle;
0108          __d.template __incr<value_type>(), (void)++__i, (void)++__p)
0109       ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
0110     std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp);
0111   } else {
0112     value_type* __p = __buff;
0113     for (_BidirectionalIterator __i = __middle; __i != __last;
0114          __d.template __incr<value_type>(), (void)++__i, (void)++__p)
0115       ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
0116     typedef reverse_iterator<_BidirectionalIterator> _RBi;
0117     typedef reverse_iterator<value_type*> _Rv;
0118     typedef __invert<_Compare> _Inverted;
0119     std::__half_inplace_merge<_AlgPolicy>(
0120         _Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp));
0121   }
0122 }
0123
0124 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
0125 _LIBCPP_CONSTEXPR_SINCE_CXX26 void __inplace_merge(
0126     _BidirectionalIterator __first,
0127     _BidirectionalIterator __middle,
0128     _BidirectionalIterator __last,
0129     _Compare&& __comp,
0130     typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
0131     typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
0132     typename iterator_traits<_BidirectionalIterator>::value_type* __buff,
0133     ptrdiff_t __buff_size) {
0134   using _Ops = _IterOps<_AlgPolicy>;
0135
0136   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
0137   while (true) {
0138     // if __middle == __last, we're done
0139     if (__len2 == 0)
0140       return;
0141     if (__len1 <= __buff_size || __len2 <= __buff_size)
0142       return std::__buffered_inplace_merge<_AlgPolicy>(__first, __middle, __last, __comp, __len1, __len2, __buff);
0143     // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
0144     for (; true; ++__first, (void)--__len1) {
0145       if (__len1 == 0)
0146         return;
0147       if (__comp(*__middle, *__first))
0148         break;
0149     }
0150     // __first < __middle < __last
0151     // *__first > *__middle
0152     // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
0153     //     all elements in:
0154     //         [__first, __m1)  <= [__middle, __m2)
0155     //         [__middle, __m2) <  [__m1, __middle)
0156     //         [__m1, __middle) <= [__m2, __last)
0157     //     and __m1 or __m2 is in the middle of its range
0158     _BidirectionalIterator __m1; // "median" of [__first, __middle)
0159     _BidirectionalIterator __m2; // "median" of [__middle, __last)
0160     difference_type __len11;     // distance(__first, __m1)
0161     difference_type __len21;     // distance(__middle, __m2)
0162     // binary search smaller range
0163     if (__len1 < __len2) { // __len >= 1, __len2 >= 2
0164       __len21 = __len2 / 2;
0165       __m2    = __middle;
0166       _Ops::advance(__m2, __len21);
0167       __m1    = std::__upper_bound<_AlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
0168       __len11 = _Ops::distance(__first, __m1);
0169     } else {
0170       if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
0171                          // It is known *__first > *__middle
0172         _Ops::iter_swap(__first, __middle);
0173         return;
0174       }
0175       // __len1 >= 2, __len2 >= 1
0176       __len11 = __len1 / 2;
0177       __m1    = __first;
0178       _Ops::advance(__m1, __len11);
0179       __m2    = std::lower_bound(__middle, __last, *__m1, __comp);
0180       __len21 = _Ops::distance(__middle, __m2);
0181     }
0182     difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
0183     difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
0184     // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
0185     // swap middle two partitions
0186     __middle = std::__rotate<_AlgPolicy>(__m1, __middle, __m2).first;
0187     // __len12 and __len21 now have swapped meanings
0188     // merge smaller range with recursive call and larger with tail recursion elimination
0189     if (__len11 + __len21 < __len12 + __len22) {
0190       std::__inplace_merge<_AlgPolicy>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
0191       __first  = __middle;
0192       __middle = __m2;
0193       __len1   = __len12;
0194       __len2   = __len22;
0195     } else {
0196       std::__inplace_merge<_AlgPolicy>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
0197       __last   = __middle;
0198       __middle = __m1;
0199       __len1   = __len11;
0200       __len2   = __len21;
0201     }
0202   }
0203 }
0204
0205 template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>
0206 _LIBCPP_HIDE_FROM_ABI void __inplace_merge(
0207     _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) {
0208   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
0209   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
0210   difference_type __len1                             = _IterOps<_AlgPolicy>::distance(__first, __middle);
0211   difference_type __len2                             = _IterOps<_AlgPolicy>::distance(__middle, __last);
0212   difference_type __buf_size                         = std::min(__len1, __len2);
0213   __unique_temporary_buffer<value_type> __unique_buf = std::__allocate_unique_temporary_buffer<value_type>(__buf_size);
0214   return std::__inplace_merge<_AlgPolicy>(
0215       std::move(__first),
0216       std::move(__middle),
0217       std::move(__last),
0218       __comp,
0219       __len1,
0220       __len2,
0221       __unique_buf.get(),
0222       __unique_buf.get_deleter().__count_);
0223 }
0224
0225 template <class _BidirectionalIterator, class _Compare>
0226 inline _LIBCPP_HIDE_FROM_ABI void inplace_merge(
0227     _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {
0228   std::__inplace_merge<_ClassicAlgPolicy>(
0229       std::move(__first), std::move(__middle), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp));
0230 }
0231
0232 template <class _BidirectionalIterator>
0233 inline _LIBCPP_HIDE_FROM_ABI void
0234 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) {
0235   std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>());
0236 }
0237
0238 _LIBCPP_END_NAMESPACE_STD
0239
0240 _LIBCPP_POP_MACROS
0241
0242 #endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H