__cxx03/__algorithm/stable_partition.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_STABLE_PARTITION_H
0010 #define _LIBCPP___CXX03___ALGORITHM_STABLE_PARTITION_H
0011
0012 #include <__cxx03/__algorithm/iterator_operations.h>
0013 #include <__cxx03/__algorithm/rotate.h>
0014 #include <__cxx03/__config>
0015 #include <__cxx03/__iterator/advance.h>
0016 #include <__cxx03/__iterator/distance.h>
0017 #include <__cxx03/__iterator/iterator_traits.h>
0018 #include <__cxx03/__memory/destruct_n.h>
0019 #include <__cxx03/__memory/temporary_buffer.h>
0020 #include <__cxx03/__memory/unique_ptr.h>
0021 #include <__cxx03/__utility/move.h>
0022 #include <__cxx03/__utility/pair.h>
0023 #include <__cxx03/new>
0024
0025 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0026 #  pragma GCC system_header
0027 #endif
0028
0029 _LIBCPP_PUSH_MACROS
0030 #include <__cxx03/__undef_macros>
0031
0032 _LIBCPP_BEGIN_NAMESPACE_STD
0033
0034 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
0035 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition_impl(
0036     _ForwardIterator __first,
0037     _ForwardIterator __last,
0038     _Predicate __pred,
0039     _Distance __len,
0040     _Pair __p,
0041     forward_iterator_tag __fit) {
0042   using _Ops = _IterOps<_AlgPolicy>;
0043
0044   // *__first is known to be false
0045   // __len >= 1
0046   if (__len == 1)
0047     return __first;
0048   if (__len == 2) {
0049     _ForwardIterator __m = __first;
0050     if (__pred(*++__m)) {
0051       _Ops::iter_swap(__first, __m);
0052       return __m;
0053     }
0054     return __first;
0055   }
0056   if (__len <= __p.second) { // The buffer is big enough to use
0057     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
0058     __destruct_n __d(0);
0059     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
0060     // Move the falses into the temporary buffer, and the trues to the front of the line
0061     // Update __first to always point to the end of the trues
0062     value_type* __t = __p.first;
0063     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
0064     __d.template __incr<value_type>();
0065     ++__t;
0066     _ForwardIterator __i = __first;
0067     while (++__i != __last) {
0068       if (__pred(*__i)) {
0069         *__first = _Ops::__iter_move(__i);
0070         ++__first;
0071       } else {
0072         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
0073         __d.template __incr<value_type>();
0074         ++__t;
0075       }
0076     }
0077     // All trues now at start of range, all falses in buffer
0078     // Move falses back into range, but don't mess up __first which points to first false
0079     __i = __first;
0080     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
0081       *__i = _Ops::__iter_move(__t2);
0082     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
0083     return __first;
0084   }
0085   // Else not enough buffer, do in place
0086   // __len >= 3
0087   _ForwardIterator __m = __first;
0088   _Distance __len2     = __len / 2; // __len2 >= 2
0089   _Ops::advance(__m, __len2);
0090   // recurse on [__first, __m), *__first know to be false
0091   // F?????????????????
0092   // f       m         l
0093   _ForwardIterator __first_false =
0094       std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m, __pred, __len2, __p, __fit);
0095   // TTTFFFFF??????????
0096   // f  ff   m         l
0097   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
0098   _ForwardIterator __m1           = __m;
0099   _ForwardIterator __second_false = __last;
0100   _Distance __len_half            = __len - __len2;
0101   while (__pred(*__m1)) {
0102     if (++__m1 == __last)
0103       goto __second_half_done;
0104     --__len_half;
0105   }
0106   // TTTFFFFFTTTF??????
0107   // f  ff   m  m1     l
0108   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
0109 __second_half_done:
0110   // TTTFFFFFTTTTTFFFFF
0111   // f  ff   m    sf   l
0112   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
0113   // TTTTTTTTFFFFFFFFFF
0114   //         |
0115 }
0116
0117 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
0118 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
0119 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) {
0120   typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
0121   typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
0122
0123   const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment
0124   // Either prove all true and return __first or point to first false
0125   while (true) {
0126     if (__first == __last)
0127       return __first;
0128     if (!__pred(*__first))
0129       break;
0130     ++__first;
0131   }
0132   // We now have a reduced range [__first, __last)
0133   // *__first is known to be false
0134   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
0135   pair<value_type*, ptrdiff_t> __p(0, 0);
0136   unique_ptr<value_type, __return_temporary_buffer> __h;
0137   if (__len >= __alloc_limit) {
0138     // TODO: Remove the use of std::get_temporary_buffer
0139     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
0140     __p = std::get_temporary_buffer<value_type>(__len);
0141     _LIBCPP_SUPPRESS_DEPRECATED_POP
0142     __h.reset(__p.first);
0143   }
0144   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
0145       std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
0146 }
0147
0148 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
0149 _BidirectionalIterator __stable_partition_impl(
0150     _BidirectionalIterator __first,
0151     _BidirectionalIterator __last,
0152     _Predicate __pred,
0153     _Distance __len,
0154     _Pair __p,
0155     bidirectional_iterator_tag __bit) {
0156   using _Ops = _IterOps<_AlgPolicy>;
0157
0158   // *__first is known to be false
0159   // *__last is known to be true
0160   // __len >= 2
0161   if (__len == 2) {
0162     _Ops::iter_swap(__first, __last);
0163     return __last;
0164   }
0165   if (__len == 3) {
0166     _BidirectionalIterator __m = __first;
0167     if (__pred(*++__m)) {
0168       _Ops::iter_swap(__first, __m);
0169       _Ops::iter_swap(__m, __last);
0170       return __last;
0171     }
0172     _Ops::iter_swap(__m, __last);
0173     _Ops::iter_swap(__first, __m);
0174     return __m;
0175   }
0176   if (__len <= __p.second) { // The buffer is big enough to use
0177     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
0178     __destruct_n __d(0);
0179     unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
0180     // Move the falses into the temporary buffer, and the trues to the front of the line
0181     // Update __first to always point to the end of the trues
0182     value_type* __t = __p.first;
0183     ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
0184     __d.template __incr<value_type>();
0185     ++__t;
0186     _BidirectionalIterator __i = __first;
0187     while (++__i != __last) {
0188       if (__pred(*__i)) {
0189         *__first = _Ops::__iter_move(__i);
0190         ++__first;
0191       } else {
0192         ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
0193         __d.template __incr<value_type>();
0194         ++__t;
0195       }
0196     }
0197     // move *__last, known to be true
0198     *__first = _Ops::__iter_move(__i);
0199     __i      = ++__first;
0200     // All trues now at start of range, all falses in buffer
0201     // Move falses back into range, but don't mess up __first which points to first false
0202     for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void)++__i)
0203       *__i = _Ops::__iter_move(__t2);
0204     // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
0205     return __first;
0206   }
0207   // Else not enough buffer, do in place
0208   // __len >= 4
0209   _BidirectionalIterator __m = __first;
0210   _Distance __len2           = __len / 2; // __len2 >= 2
0211   _Ops::advance(__m, __len2);
0212   // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
0213   // F????????????????T
0214   // f       m        l
0215   _BidirectionalIterator __m1          = __m;
0216   _BidirectionalIterator __first_false = __first;
0217   _Distance __len_half                 = __len2;
0218   while (!__pred(*--__m1)) {
0219     if (__m1 == __first)
0220       goto __first_half_done;
0221     --__len_half;
0222   }
0223   // F???TFFF?????????T
0224   // f   m1  m        l
0225   __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
0226 __first_half_done:
0227   // TTTFFFFF?????????T
0228   // f  ff   m        l
0229   // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
0230   __m1                                  = __m;
0231   _BidirectionalIterator __second_false = __last;
0232   ++__second_false;
0233   __len_half = __len - __len2;
0234   while (__pred(*__m1)) {
0235     if (++__m1 == __last)
0236       goto __second_half_done;
0237     --__len_half;
0238   }
0239   // TTTFFFFFTTTF?????T
0240   // f  ff   m  m1    l
0241   __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
0242 __second_half_done:
0243   // TTTFFFFFTTTTTFFFFF
0244   // f  ff   m    sf  l
0245   return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
0246   // TTTTTTTTFFFFFFFFFF
0247   //         |
0248 }
0249
0250 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
0251 _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __stable_partition_impl(
0252     _BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag) {
0253   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
0254   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
0255   const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
0256   // Either prove all true and return __first or point to first false
0257   while (true) {
0258     if (__first == __last)
0259       return __first;
0260     if (!__pred(*__first))
0261       break;
0262     ++__first;
0263   }
0264   // __first points to first false, everything prior to __first is already set.
0265   // Either prove [__first, __last) is all false and return __first, or point __last to last true
0266   do {
0267     if (__first == --__last)
0268       return __first;
0269   } while (!__pred(*__last));
0270   // We now have a reduced range [__first, __last]
0271   // *__first is known to be false
0272   // *__last is known to be true
0273   // __len >= 2
0274   difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
0275   pair<value_type*, ptrdiff_t> __p(0, 0);
0276   unique_ptr<value_type, __return_temporary_buffer> __h;
0277   if (__len >= __alloc_limit) {
0278     // TODO: Remove the use of std::get_temporary_buffer
0279     _LIBCPP_SUPPRESS_DEPRECATED_PUSH
0280     __p = std::get_temporary_buffer<value_type>(__len);
0281     _LIBCPP_SUPPRESS_DEPRECATED_POP
0282     __h.reset(__p.first);
0283   }
0284   return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
0285       std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
0286 }
0287
0288 template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
0289 _LIBCPP_HIDE_FROM_ABI _ForwardIterator __stable_partition(
0290     _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
0291   return std::__stable_partition_impl<_AlgPolicy, __remove_cvref_t<_Predicate>&>(
0292       std::move(__first), std::move(__last), __pred, __iter_category);
0293 }
0294
0295 template <class _ForwardIterator, class _Predicate>
0296 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator
0297 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
0298   using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
0299   return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
0300       std::move(__first), std::move(__last), __pred, _IterCategory());
0301 }
0302
0303 _LIBCPP_END_NAMESPACE_STD
0304
0305 _LIBCPP_POP_MACROS
0306
0307 #endif // _LIBCPP___CXX03___ALGORITHM_STABLE_PARTITION_H