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