libcxx/include/__algorithm/partition.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___ALGORITHM_PARTITION_H
  10 #define _LIBCPP___ALGORITHM_PARTITION_H
  11
  12 #include <__algorithm/iterator_operations.h>
  13 #include <__config>
  14 #include <__iterator/iterator_traits.h>
  15 #include <__type_traits/remove_cvref.h>
  16 #include <__utility/move.h>
  17 #include <__utility/pair.h>
  18
  19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  20 #  pragma GCC system_header
  21 #endif
  22
  23 _LIBCPP_PUSH_MACROS
  24 #include <__undef_macros>
  25
  26 _LIBCPP_BEGIN_NAMESPACE_STD
  27
  28 template <class _Predicate, class _AlgPolicy, class _ForwardIterator, class _Sentinel>
  29 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator>
  30 __partition_impl(_ForwardIterator __first, _Sentinel __last, _Predicate __pred, forward_iterator_tag) {
  31   while (true) {
  32     if (__first == __last)
  33       return std::make_pair(__first, __first);
  34     if (!__pred(*__first))
  35       break;
  36     ++__first;
  37   }
  38
  39   _ForwardIterator __p = __first;
  40   while (++__p != __last) {
  41     if (__pred(*__p)) {
  42       _IterOps<_AlgPolicy>::iter_swap(__first, __p);
  43       ++__first;
  44     }
  45   }
  46   return std::make_pair(std::move(__first), std::move(__p));
  47 }
  48
  49 template <class _Predicate, class _AlgPolicy, class _BidirectionalIterator, class _Sentinel>
  50 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator, _BidirectionalIterator>
  51 __partition_impl(_BidirectionalIterator __first, _Sentinel __sentinel, _Predicate __pred, bidirectional_iterator_tag) {
  52   _BidirectionalIterator __original_last = _IterOps<_AlgPolicy>::next(__first, __sentinel);
  53   _BidirectionalIterator __last          = __original_last;
  54
  55   while (true) {
  56     while (true) {
  57       if (__first == __last)
  58         return std::make_pair(std::move(__first), std::move(__original_last));
  59       if (!__pred(*__first))
  60         break;
  61       ++__first;
  62     }
  63     do {
  64       if (__first == --__last)
  65         return std::make_pair(std::move(__first), std::move(__original_last));
  66     } while (!__pred(*__last));
  67     _IterOps<_AlgPolicy>::iter_swap(__first, __last);
  68     ++__first;
  69   }
  70 }
  71
  72 template <class _AlgPolicy, class _ForwardIterator, class _Sentinel, class _Predicate, class _IterCategory>
  73 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator>
  74 __partition(_ForwardIterator __first, _Sentinel __last, _Predicate&& __pred, _IterCategory __iter_category) {
  75   return std::__partition_impl<__remove_cvref_t<_Predicate>&, _AlgPolicy>(
  76       std::move(__first), std::move(__last), __pred, __iter_category);
  77 }
  78
  79 template <class _ForwardIterator, class _Predicate>
  80 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
  81 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
  82   using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
  83   auto __result = std::__partition<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred, _IterCategory());
  84   return __result.first;
  85 }
  86
  87 _LIBCPP_END_NAMESPACE_STD
  88
  89 _LIBCPP_POP_MACROS
  90
  91 #endif // _LIBCPP___ALGORITHM_PARTITION_H