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