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_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