69 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___ALGORITHM_UPPER_BOUND_H10#define _LIBCPP___CXX03___ALGORITHM_UPPER_BOUND_H11 12#include <__cxx03/__algorithm/comp.h>13#include <__cxx03/__algorithm/half_positive.h>14#include <__cxx03/__algorithm/iterator_operations.h>15#include <__cxx03/__config>16#include <__cxx03/__functional/identity.h>17#include <__cxx03/__iterator/advance.h>18#include <__cxx03/__iterator/distance.h>19#include <__cxx03/__iterator/iterator_traits.h>20#include <__cxx03/__type_traits/invoke.h>21#include <__cxx03/__type_traits/is_constructible.h>22#include <__cxx03/__utility/move.h>23 24#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)25# pragma GCC system_header26#endif27 28_LIBCPP_PUSH_MACROS29#include <__cxx03/__undef_macros>30 31_LIBCPP_BEGIN_NAMESPACE_STD32 33template <class _AlgPolicy, class _Compare, class _Iter, class _Sent, class _Tp, class _Proj>34_LIBCPP_HIDE_FROM_ABI _Iter35__upper_bound(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp, _Proj&& __proj) {36 auto __len = _IterOps<_AlgPolicy>::distance(__first, __last);37 while (__len != 0) {38 auto __half_len = std::__half_positive(__len);39 auto __mid = _IterOps<_AlgPolicy>::next(__first, __half_len);40 if (std::__invoke(__comp, __value, std::__invoke(__proj, *__mid)))41 __len = __half_len;42 else {43 __first = ++__mid;44 __len -= __half_len + 1;45 }46 }47 return __first;48}49 50template <class _ForwardIterator, class _Tp, class _Compare>51_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator52upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) {53 static_assert(is_copy_constructible<_ForwardIterator>::value, "Iterator has to be copy constructible");54 return std::__upper_bound<_ClassicAlgPolicy>(55 std::move(__first), std::move(__last), __value, std::move(__comp), std::__identity());56}57 58template <class _ForwardIterator, class _Tp>59_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator60upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {61 return std::upper_bound(std::move(__first), std::move(__last), __value, __less<>());62}63 64_LIBCPP_END_NAMESPACE_STD65 66_LIBCPP_POP_MACROS67 68#endif // _LIBCPP___CXX03___ALGORITHM_UPPER_BOUND_H69