176d0caaeSpatrick //===----------------------------------------------------------------------===// 276d0caaeSpatrick // 376d0caaeSpatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 476d0caaeSpatrick // See https://llvm.org/LICENSE.txt for license information. 576d0caaeSpatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 676d0caaeSpatrick // 776d0caaeSpatrick //===----------------------------------------------------------------------===// 876d0caaeSpatrick 976d0caaeSpatrick #ifndef _LIBCPP___ALGORITHM_PARTITION_POINT_H 1076d0caaeSpatrick #define _LIBCPP___ALGORITHM_PARTITION_POINT_H 1176d0caaeSpatrick 1276d0caaeSpatrick #include <__algorithm/half_positive.h> 13*4bdff4beSrobert #include <__config> 14*4bdff4beSrobert #include <__iterator/advance.h> 15*4bdff4beSrobert #include <__iterator/distance.h> 16*4bdff4beSrobert #include <__iterator/iterator_traits.h> 1776d0caaeSpatrick 1876d0caaeSpatrick #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 1976d0caaeSpatrick # pragma GCC system_header 2076d0caaeSpatrick #endif 2176d0caaeSpatrick 2276d0caaeSpatrick _LIBCPP_BEGIN_NAMESPACE_STD 2376d0caaeSpatrick 2476d0caaeSpatrick template<class _ForwardIterator, class _Predicate> 25*4bdff4beSrobert _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator partition_point(_ForwardIterator __first,_ForwardIterator __last,_Predicate __pred)2676d0caaeSpatrickpartition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2776d0caaeSpatrick { 2876d0caaeSpatrick typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 2976d0caaeSpatrick difference_type __len = _VSTD::distance(__first, __last); 3076d0caaeSpatrick while (__len != 0) 3176d0caaeSpatrick { 3276d0caaeSpatrick difference_type __l2 = _VSTD::__half_positive(__len); 3376d0caaeSpatrick _ForwardIterator __m = __first; 3476d0caaeSpatrick _VSTD::advance(__m, __l2); 3576d0caaeSpatrick if (__pred(*__m)) 3676d0caaeSpatrick { 3776d0caaeSpatrick __first = ++__m; 3876d0caaeSpatrick __len -= __l2 + 1; 3976d0caaeSpatrick } 4076d0caaeSpatrick else 4176d0caaeSpatrick __len = __l2; 4276d0caaeSpatrick } 4376d0caaeSpatrick return __first; 4476d0caaeSpatrick } 4576d0caaeSpatrick 4676d0caaeSpatrick _LIBCPP_END_NAMESPACE_STD 4776d0caaeSpatrick 4876d0caaeSpatrick #endif // _LIBCPP___ALGORITHM_PARTITION_POINT_H 49