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_SINCE_CXX20 _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_SINCE_CXX20 _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_SINCE_CXX20 _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_SINCE_CXX20 _OutputIterator
99 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) {
100   using __algo_tag = __conditional_t<
101       is_base_of<forward_iterator_tag, typename iterator_traits<_InputIterator>::iterator_category>::value,
102       __unique_copy_tags::__reread_from_input_tag,
103       __conditional_t<
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> >;
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_SINCE_CXX20 _OutputIterator
116 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
117   return std::unique_copy(std::move(__first), std::move(__last), std::move(__result), __equal_to());
118 }
119 
120 _LIBCPP_END_NAMESPACE_STD
121 
122 #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H
123