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_UNIQUE_COPY_H 10 #define _LIBCPP___ALGORITHM_UNIQUE_COPY_H 11 12 #include <__algorithm/comp.h> 13 #include <__algorithm/iterator_operations.h> 14 #include <__config> 15 #include <__iterator/iterator_traits.h> 16 #include <__type_traits/conditional.h> 17 #include <__type_traits/is_base_of.h> 18 #include <__type_traits/is_same.h> 19 #include <__utility/move.h> 20 #include <__utility/pair.h> 21 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23 # pragma GCC system_header 24 #endif 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 namespace __unique_copy_tags { 29 30 struct __reread_from_input_tag {}; 31 struct __reread_from_output_tag {}; 32 struct __read_from_tmp_value_tag {}; 33 34 } // namespace __unique_copy_tags 35 36 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _OutputIterator> 37 _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _OutputIterator> 38 __unique_copy(_InputIterator __first, 39 _Sent __last, 40 _OutputIterator __result, 41 _BinaryPredicate&& __pred, 42 __unique_copy_tags::__read_from_tmp_value_tag) { 43 if (__first != __last) { 44 typename _IterOps<_AlgPolicy>::template __value_type<_InputIterator> __t(*__first); 45 *__result = __t; 46 ++__result; 47 while (++__first != __last) { 48 if (!__pred(__t, *__first)) { 49 __t = *__first; 50 *__result = __t; 51 ++__result; 52 } 53 } 54 } 55 return pair<_InputIterator, _OutputIterator>(std::move(__first), std::move(__result)); 56 } 57 58 template <class _AlgPolicy, class _BinaryPredicate, class _ForwardIterator, class _Sent, class _OutputIterator> 59 _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_ForwardIterator, _OutputIterator> 60 __unique_copy(_ForwardIterator __first, 61 _Sent __last, 62 _OutputIterator __result, 63 _BinaryPredicate&& __pred, 64 __unique_copy_tags::__reread_from_input_tag) { 65 if (__first != __last) { 66 _ForwardIterator __i = __first; 67 *__result = *__i; 68 ++__result; 69 while (++__first != __last) { 70 if (!__pred(*__i, *__first)) { 71 *__result = *__first; 72 ++__result; 73 __i = __first; 74 } 75 } 76 } 77 return pair<_ForwardIterator, _OutputIterator>(std::move(__first), std::move(__result)); 78 } 79 80 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _InputAndOutputIterator> 81 _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _InputAndOutputIterator> 82 __unique_copy(_InputIterator __first, 83 _Sent __last, 84 _InputAndOutputIterator __result, 85 _BinaryPredicate&& __pred, 86 __unique_copy_tags::__reread_from_output_tag) { 87 if (__first != __last) { 88 *__result = *__first; 89 while (++__first != __last) 90 if (!__pred(*__result, *__first)) 91 *++__result = *__first; 92 ++__result; 93 } 94 return pair<_InputIterator, _InputAndOutputIterator>(std::move(__first), std::move(__result)); 95 } 96 97 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> 98 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 99 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) { 100 using __algo_tag = typename conditional< 101 is_base_of<forward_iterator_tag, typename iterator_traits<_InputIterator>::iterator_category>::value, 102 __unique_copy_tags::__reread_from_input_tag, 103 typename conditional< 104 is_base_of<forward_iterator_tag, typename iterator_traits<_OutputIterator>::iterator_category>::value && 105 is_same< typename iterator_traits<_InputIterator>::value_type, 106 typename iterator_traits<_OutputIterator>::value_type>::value, 107 __unique_copy_tags::__reread_from_output_tag, 108 __unique_copy_tags::__read_from_tmp_value_tag>::type >::type; 109 return std::__unique_copy<_ClassicAlgPolicy>( 110 std::move(__first), std::move(__last), std::move(__result), __pred, __algo_tag()) 111 .second; 112 } 113 114 template <class _InputIterator, class _OutputIterator> 115 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 116 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { 117 typedef typename iterator_traits<_InputIterator>::value_type __v; 118 return std::unique_copy(std::move(__first), std::move(__last), std::move(__result), __equal_to<__v>()); 119 } 120 121 _LIBCPP_END_NAMESPACE_STD 122 123 #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H 124