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