libcxx/include/__algorithm/unique_copy.h

   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_PUSH_MACROS
  27 #include <__undef_macros>
  28
  29 _LIBCPP_BEGIN_NAMESPACE_STD
  30
  31 namespace __unique_copy_tags {
  32
  33 struct __reread_from_input_tag {};
  34 struct __reread_from_output_tag {};
  35 struct __read_from_tmp_value_tag {};
  36
  37 } // namespace __unique_copy_tags
  38
  39 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _OutputIterator>
  40 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _OutputIterator>
  41 __unique_copy(_InputIterator __first,
  42               _Sent __last,
  43               _OutputIterator __result,
  44               _BinaryPredicate&& __pred,
  45               __unique_copy_tags::__read_from_tmp_value_tag) {
  46   if (__first != __last) {
  47     typename _IterOps<_AlgPolicy>::template __value_type<_InputIterator> __t(*__first);
  48     *__result = __t;
  49     ++__result;
  50     while (++__first != __last) {
  51       if (!__pred(__t, *__first)) {
  52         __t       = *__first;
  53         *__result = __t;
  54         ++__result;
  55       }
  56     }
  57   }
  58   return pair<_InputIterator, _OutputIterator>(std::move(__first), std::move(__result));
  59 }
  60
  61 template <class _AlgPolicy, class _BinaryPredicate, class _ForwardIterator, class _Sent, class _OutputIterator>
  62 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_ForwardIterator, _OutputIterator>
  63 __unique_copy(_ForwardIterator __first,
  64               _Sent __last,
  65               _OutputIterator __result,
  66               _BinaryPredicate&& __pred,
  67               __unique_copy_tags::__reread_from_input_tag) {
  68   if (__first != __last) {
  69     _ForwardIterator __i = __first;
  70     *__result            = *__i;
  71     ++__result;
  72     while (++__first != __last) {
  73       if (!__pred(*__i, *__first)) {
  74         *__result = *__first;
  75         ++__result;
  76         __i = __first;
  77       }
  78     }
  79   }
  80   return pair<_ForwardIterator, _OutputIterator>(std::move(__first), std::move(__result));
  81 }
  82
  83 template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _InputAndOutputIterator>
  84 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _InputAndOutputIterator>
  85 __unique_copy(_InputIterator __first,
  86               _Sent __last,
  87               _InputAndOutputIterator __result,
  88               _BinaryPredicate&& __pred,
  89               __unique_copy_tags::__reread_from_output_tag) {
  90   if (__first != __last) {
  91     *__result = *__first;
  92     while (++__first != __last)
  93       if (!__pred(*__result, *__first))
  94         *++__result = *__first;
  95     ++__result;
  96   }
  97   return pair<_InputIterator, _InputAndOutputIterator>(std::move(__first), std::move(__result));
  98 }
  99
 100 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
 101 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
 102 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) {
 103   using __algo_tag = __conditional_t<
 104       is_base_of<forward_iterator_tag, typename iterator_traits<_InputIterator>::iterator_category>::value,
 105       __unique_copy_tags::__reread_from_input_tag,
 106       __conditional_t<
 107           is_base_of<forward_iterator_tag, typename iterator_traits<_OutputIterator>::iterator_category>::value &&
 108               is_same< typename iterator_traits<_InputIterator>::value_type,
 109                        typename iterator_traits<_OutputIterator>::value_type>::value,
 110           __unique_copy_tags::__reread_from_output_tag,
 111           __unique_copy_tags::__read_from_tmp_value_tag> >;
 112   return std::__unique_copy<_ClassicAlgPolicy>(
 113              std::move(__first), std::move(__last), std::move(__result), __pred, __algo_tag())
 114       .second;
 115 }
 116
 117 template <class _InputIterator, class _OutputIterator>
 118 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
 119 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
 120   return std::unique_copy(std::move(__first), std::move(__last), std::move(__result), __equal_to());
 121 }
 122
 123 _LIBCPP_END_NAMESPACE_STD
 124
 125 _LIBCPP_POP_MACROS
 126
 127 #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H