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_SET_INTERSECTION_H 10 #define _LIBCPP___ALGORITHM_SET_INTERSECTION_H 11 12 #include <__algorithm/comp.h> 13 #include <__algorithm/comp_ref_type.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__config> 16 #include <__iterator/iterator_traits.h> 17 #include <__iterator/next.h> 18 #include <__utility/move.h> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 23 24 _LIBCPP_PUSH_MACROS 25 #include <__undef_macros> 26 27 _LIBCPP_BEGIN_NAMESPACE_STD 28 29 template <class _InIter1, class _InIter2, class _OutIter> 30 struct __set_intersection_result { 31 _InIter1 __in1_; 32 _InIter2 __in2_; 33 _OutIter __out_; 34 35 // need a constructor as C++03 aggregate init is hard 36 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 37 __set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter) 38 : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {} 39 }; 40 41 template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> 42 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_intersection_result<_InIter1, _InIter2, _OutIter> 43 __set_intersection( 44 _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { 45 while (__first1 != __last1 && __first2 != __last2) { 46 if (__comp(*__first1, *__first2)) 47 ++__first1; 48 else { 49 if (!__comp(*__first2, *__first1)) { 50 *__result = *__first1; 51 ++__result; 52 ++__first1; 53 } 54 ++__first2; 55 } 56 } 57 58 return __set_intersection_result<_InIter1, _InIter2, _OutIter>( 59 _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)), 60 _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)), 61 std::move(__result)); 62 } 63 64 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 65 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_intersection( 66 _InputIterator1 __first1, 67 _InputIterator1 __last1, 68 _InputIterator2 __first2, 69 _InputIterator2 __last2, 70 _OutputIterator __result, 71 _Compare __comp) { 72 return std::__set_intersection<_ClassicAlgPolicy, __comp_ref_type<_Compare> >( 73 std::move(__first1), 74 std::move(__last1), 75 std::move(__first2), 76 std::move(__last2), 77 std::move(__result), 78 __comp) 79 .__out_; 80 } 81 82 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 83 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_intersection( 84 _InputIterator1 __first1, 85 _InputIterator1 __last1, 86 _InputIterator2 __first2, 87 _InputIterator2 __last2, 88 _OutputIterator __result) { 89 return std::__set_intersection<_ClassicAlgPolicy>( 90 std::move(__first1), 91 std::move(__last1), 92 std::move(__first2), 93 std::move(__last2), 94 std::move(__result), 95 __less<>()) 96 .__out_; 97 } 98 99 _LIBCPP_END_NAMESPACE_STD 100 101 _LIBCPP_POP_MACROS 102 103 #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H 104