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 <__config> 13 #include <__iterator/iterator_traits.h> 14 #include <__utility/swap.h> 15 #include <utility> // pair 16 17 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 18 #pragma GCC system_header 19 #endif 20 21 _LIBCPP_BEGIN_NAMESPACE_STD 22 23 template <class _Predicate, class _ForwardIterator> 24 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 25 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 26 { 27 while (true) 28 { 29 if (__first == __last) 30 return __first; 31 if (!__pred(*__first)) 32 break; 33 ++__first; 34 } 35 for (_ForwardIterator __p = __first; ++__p != __last;) 36 { 37 if (__pred(*__p)) 38 { 39 swap(*__first, *__p); 40 ++__first; 41 } 42 } 43 return __first; 44 } 45 46 template <class _Predicate, class _BidirectionalIterator> 47 _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator 48 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 49 bidirectional_iterator_tag) 50 { 51 while (true) 52 { 53 while (true) 54 { 55 if (__first == __last) 56 return __first; 57 if (!__pred(*__first)) 58 break; 59 ++__first; 60 } 61 do 62 { 63 if (__first == --__last) 64 return __first; 65 } while (!__pred(*__last)); 66 swap(*__first, *__last); 67 ++__first; 68 } 69 } 70 71 template <class _ForwardIterator, class _Predicate> 72 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 73 _ForwardIterator 74 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 75 { 76 return _VSTD::__partition<_Predicate&>( 77 __first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 78 } 79 80 _LIBCPP_END_NAMESPACE_STD 81 82 #endif // _LIBCPP___ALGORITHM_PARTITION_H 83