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