v1/__algorithm/unique_copy.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_UNIQUE_COPY_H
0010 #define _LIBCPP___ALGORITHM_UNIQUE_COPY_H
0011
0012 #include <__algorithm/comp.h>
0013 #include <__algorithm/iterator_operations.h>
0014 #include <__config>
0015 #include <__iterator/iterator_traits.h>
0016 #include <__type_traits/conditional.h>
0017 #include <__type_traits/is_base_of.h>
0018 #include <__type_traits/is_same.h>
0019 #include <__utility/move.h>
0020 #include <__utility/pair.h>
0021
0022 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0023 #  pragma GCC system_header
0024 #endif
0025
0026 _LIBCPP_PUSH_MACROS
0027 #include <__undef_macros>
0028
0029 _LIBCPP_BEGIN_NAMESPACE_STD
0030
0031 namespace __unique_copy_tags {
0032
0033 struct __reread_from_input_tag {};
0034 struct __reread_from_output_tag {};
0035 struct __read_from_tmp_value_tag {};
0036
0037 } // namespace __unique_copy_tags
0038
0039 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _OutputIterator>
0040 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _OutputIterator>
0041 __unique_copy(_InputIterator __first,
0042               _Sent __last,
0043               _OutputIterator __result,
0044               _BinaryPredicate&& __pred,
0045               __unique_copy_tags::__read_from_tmp_value_tag) {
0046   if (__first != __last) {
0047     typename _IterOps<_AlgPolicy>::template __value_type<_InputIterator> __t(*__first);
0048     *__result = __t;
0049     ++__result;
0050     while (++__first != __last) {
0051       if (!__pred(__t, *__first)) {
0052         __t       = *__first;
0053         *__result = __t;
0054         ++__result;
0055       }
0056     }
0057   }
0058   return pair<_InputIterator, _OutputIterator>(std::move(__first), std::move(__result));
0059 }
0060
0061 template <class _AlgPolicy, class _BinaryPredicate, class _ForwardIterator, class _Sent, class _OutputIterator>
0062 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_ForwardIterator, _OutputIterator>
0063 __unique_copy(_ForwardIterator __first,
0064               _Sent __last,
0065               _OutputIterator __result,
0066               _BinaryPredicate&& __pred,
0067               __unique_copy_tags::__reread_from_input_tag) {
0068   if (__first != __last) {
0069     _ForwardIterator __i = __first;
0070     *__result            = *__i;
0071     ++__result;
0072     while (++__first != __last) {
0073       if (!__pred(*__i, *__first)) {
0074         *__result = *__first;
0075         ++__result;
0076         __i = __first;
0077       }
0078     }
0079   }
0080   return pair<_ForwardIterator, _OutputIterator>(std::move(__first), std::move(__result));
0081 }
0082
0083 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _InputAndOutputIterator>
0084 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _InputAndOutputIterator>
0085 __unique_copy(_InputIterator __first,
0086               _Sent __last,
0087               _InputAndOutputIterator __result,
0088               _BinaryPredicate&& __pred,
0089               __unique_copy_tags::__reread_from_output_tag) {
0090   if (__first != __last) {
0091     *__result = *__first;
0092     while (++__first != __last)
0093       if (!__pred(*__result, *__first))
0094         *++__result = *__first;
0095     ++__result;
0096   }
0097   return pair<_InputIterator, _InputAndOutputIterator>(std::move(__first), std::move(__result));
0098 }
0099
0100 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
0101 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
0102 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) {
0103   using __algo_tag = __conditional_t<
0104       is_base_of<forward_iterator_tag, typename iterator_traits<_InputIterator>::iterator_category>::value,
0105       __unique_copy_tags::__reread_from_input_tag,
0106       __conditional_t<
0107           is_base_of<forward_iterator_tag, typename iterator_traits<_OutputIterator>::iterator_category>::value &&
0108               is_same< typename iterator_traits<_InputIterator>::value_type,
0109                        typename iterator_traits<_OutputIterator>::value_type>::value,
0110           __unique_copy_tags::__reread_from_output_tag,
0111           __unique_copy_tags::__read_from_tmp_value_tag> >;
0112   return std::__unique_copy<_ClassicAlgPolicy>(
0113              std::move(__first), std::move(__last), std::move(__result), __pred, __algo_tag())
0114       .second;
0115 }
0116
0117 template <class _InputIterator, class _OutputIterator>
0118 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
0119 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
0120   return std::unique_copy(std::move(__first), std::move(__last), std::move(__result), __equal_to());
0121 }
0122
0123 _LIBCPP_END_NAMESPACE_STD
0124
0125 _LIBCPP_POP_MACROS
0126
0127 #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H