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 <__algorithm/lower_bound.h> 16 #include <__config> 17 #include <__functional/identity.h> 18 #include <__iterator/iterator_traits.h> 19 #include <__iterator/next.h> 20 #include <__type_traits/is_same.h> 21 #include <__utility/exchange.h> 22 #include <__utility/move.h> 23 #include <__utility/swap.h> 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_PUSH_MACROS 30 #include <__undef_macros> 31 32 _LIBCPP_BEGIN_NAMESPACE_STD 33 34 template <class _InIter1, class _InIter2, class _OutIter> 35 struct __set_intersection_result { 36 _InIter1 __in1_; 37 _InIter2 __in2_; 38 _OutIter __out_; 39 40 // need a constructor as C++03 aggregate init is hard 41 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 42 __set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter) 43 : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {} 44 }; 45 46 // Helper for __set_intersection() with one-sided binary search: populate result and advance input iterators if they 47 // are found to potentially contain the same value in two consecutive calls. This function is very intimately related to 48 // the way it is used and doesn't attempt to abstract that, it's not appropriate for general usage outside of its 49 // context. 50 template <class _InForwardIter1, class _InForwardIter2, class _OutIter> 51 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __set_intersection_add_output_if_equal( 52 bool __may_be_equal, 53 _InForwardIter1& __first1, 54 _InForwardIter2& __first2, 55 _OutIter& __result, 56 bool& __prev_may_be_equal) { 57 if (__may_be_equal && __prev_may_be_equal) { 58 *__result = *__first1; 59 ++__result; 60 ++__first1; 61 ++__first2; 62 __prev_may_be_equal = false; 63 } else { 64 __prev_may_be_equal = __may_be_equal; 65 } 66 } 67 68 // With forward iterators we can make multiple passes over the data, allowing the use of one-sided binary search to 69 // reduce best-case complexity to log(N). Understanding how we can use binary search and still respect complexity 70 // guarantees is _not_ straightforward: the guarantee is "at most 2*(N+M)-1 comparisons", and one-sided binary search 71 // will necessarily overshoot depending on the position of the needle in the haystack -- for instance, if we're 72 // searching for 3 in (1, 2, 3, 4), we'll check if 3<1, then 3<2, then 3<4, and, finally, 3<3, for a total of 4 73 // comparisons, when linear search would have yielded 3. However, because we won't need to perform the intervening 74 // reciprocal comparisons (ie 1<3, 2<3, 4<3), that extra comparison doesn't run afoul of the guarantee. Additionally, 75 // this type of scenario can only happen for match distances of up to 5 elements, because 2*log2(8) is 6, and we'll 76 // still be worse-off at position 5 of an 8-element set. From then onwards these scenarios can't happen. TL;DR: we'll be 77 // 1 comparison worse-off compared to the classic linear-searching algorithm if matching position 3 of a set with 4 78 // elements, or position 5 if the set has 7 or 8 elements, but we'll never exceed the complexity guarantees from the 79 // standard. 80 template <class _AlgPolicy, 81 class _Compare, 82 class _InForwardIter1, 83 class _Sent1, 84 class _InForwardIter2, 85 class _Sent2, 86 class _OutIter> 87 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI 88 _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_intersection_result<_InForwardIter1, _InForwardIter2, _OutIter> 89 __set_intersection( 90 _InForwardIter1 __first1, 91 _Sent1 __last1, 92 _InForwardIter2 __first2, 93 _Sent2 __last2, 94 _OutIter __result, 95 _Compare&& __comp, 96 std::forward_iterator_tag, 97 std::forward_iterator_tag) { 98 _LIBCPP_CONSTEXPR std::__identity __proj; 99 bool __prev_may_be_equal = false; 100 101 while (__first2 != __last2) { 102 _InForwardIter1 __first1_next = 103 std::__lower_bound_onesided<_AlgPolicy>(__first1, __last1, *__first2, __comp, __proj); 104 std::swap(__first1_next, __first1); 105 // keeping in mind that a==b iff !(a<b) && !(b<a): 106 // if we can't advance __first1, that means !(*__first1 < *_first2), therefore __may_be_equal==true 107 std::__set_intersection_add_output_if_equal( 108 __first1 == __first1_next, __first1, __first2, __result, __prev_may_be_equal); 109 if (__first1 == __last1) 110 break; 111 112 _InForwardIter2 __first2_next = 113 std::__lower_bound_onesided<_AlgPolicy>(__first2, __last2, *__first1, __comp, __proj); 114 std::swap(__first2_next, __first2); 115 std::__set_intersection_add_output_if_equal( 116 __first2 == __first2_next, __first1, __first2, __result, __prev_may_be_equal); 117 } 118 return __set_intersection_result<_InForwardIter1, _InForwardIter2, _OutIter>( 119 _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)), 120 _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)), 121 std::move(__result)); 122 } 123 124 // input iterators are not suitable for multipass algorithms, so we stick to the classic single-pass version 125 template <class _AlgPolicy, 126 class _Compare, 127 class _InInputIter1, 128 class _Sent1, 129 class _InInputIter2, 130 class _Sent2, 131 class _OutIter> 132 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI 133 _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_intersection_result<_InInputIter1, _InInputIter2, _OutIter> 134 __set_intersection( 135 _InInputIter1 __first1, 136 _Sent1 __last1, 137 _InInputIter2 __first2, 138 _Sent2 __last2, 139 _OutIter __result, 140 _Compare&& __comp, 141 std::input_iterator_tag, 142 std::input_iterator_tag) { 143 while (__first1 != __last1 && __first2 != __last2) { 144 if (__comp(*__first1, *__first2)) 145 ++__first1; 146 else { 147 if (!__comp(*__first2, *__first1)) { 148 *__result = *__first1; 149 ++__result; 150 ++__first1; 151 } 152 ++__first2; 153 } 154 } 155 156 return __set_intersection_result<_InInputIter1, _InInputIter2, _OutIter>( 157 _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)), 158 _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)), 159 std::move(__result)); 160 } 161 162 template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> 163 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI 164 _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_intersection_result<_InIter1, _InIter2, _OutIter> 165 __set_intersection( 166 _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { 167 return std::__set_intersection<_AlgPolicy>( 168 std::move(__first1), 169 std::move(__last1), 170 std::move(__first2), 171 std::move(__last2), 172 std::move(__result), 173 std::forward<_Compare>(__comp), 174 typename std::_IterOps<_AlgPolicy>::template __iterator_category<_InIter1>(), 175 typename std::_IterOps<_AlgPolicy>::template __iterator_category<_InIter2>()); 176 } 177 178 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 179 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_intersection( 180 _InputIterator1 __first1, 181 _InputIterator1 __last1, 182 _InputIterator2 __first2, 183 _InputIterator2 __last2, 184 _OutputIterator __result, 185 _Compare __comp) { 186 return std::__set_intersection<_ClassicAlgPolicy, __comp_ref_type<_Compare> >( 187 std::move(__first1), 188 std::move(__last1), 189 std::move(__first2), 190 std::move(__last2), 191 std::move(__result), 192 __comp) 193 .__out_; 194 } 195 196 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 197 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_intersection( 198 _InputIterator1 __first1, 199 _InputIterator1 __last1, 200 _InputIterator2 __first2, 201 _InputIterator2 __last2, 202 _OutputIterator __result) { 203 return std::__set_intersection<_ClassicAlgPolicy>( 204 std::move(__first1), 205 std::move(__last1), 206 std::move(__first2), 207 std::move(__last2), 208 std::move(__result), 209 __less<>()) 210 .__out_; 211 } 212 213 _LIBCPP_END_NAMESPACE_STD 214 215 _LIBCPP_POP_MACROS 216 217 #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H 218