Horizon
unique_copy.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 //
13 #ifndef RANGES_V3_ALGORITHM_UNIQUE_COPY_HPP
14 #define RANGES_V3_ALGORITHM_UNIQUE_COPY_HPP
15 
16 #include <meta/meta.hpp>
17 
18 #include <range/v3/range_fwd.hpp>
19 
20 #include <range/v3/algorithm/result_types.hpp>
30 #include <range/v3/utility/static_const.hpp>
31 
32 #include <range/v3/detail/prologue.hpp>
33 
34 namespace ranges
35 {
38 
39  template<typename I, typename O>
40  using unique_copy_result = detail::in_out_result<I, O>;
41 
43  namespace detail
44  {
45  template<typename I, typename S, typename O, typename C, typename P>
46  constexpr unique_copy_result<I, O> unique_copy_impl(I first,
47  S last,
48  O out,
49  C pred,
50  P proj,
51  std::input_iterator_tag,
52  std::false_type)
53  {
54  if(first != last)
55  {
56  // Must save a copy into a local because we will need this value
57  // even after we advance the input iterator.
58  iter_value_t<I> value =
59  *first; // This is guaranteed by indirectly_copyable
60  *out = value;
61  ++out;
62  while(++first != last)
63  {
64  auto && x = *first;
65  if(!invoke(pred, invoke(proj, value), invoke(proj, x)))
66  {
67  value = (decltype(x) &&)x;
68  *out = value;
69  ++out;
70  }
71  }
72  }
73  return {first, out};
74  }
75 
76  template<typename I, typename S, typename O, typename C, typename P>
77  constexpr unique_copy_result<I, O> unique_copy_impl(I first,
78  S last,
79  O out,
80  C pred,
81  P proj,
82  std::forward_iterator_tag,
83  std::false_type)
84  {
85  if(first != last)
86  {
87  I tmp = first;
88  *out = *tmp;
89  ++out;
90  while(++first != last)
91  {
92  auto && x = *first;
93  if(!invoke(pred, invoke(proj, *tmp), invoke(proj, x)))
94  {
95  *out = (decltype(x) &&)x;
96  ++out;
97  tmp = first;
98  }
99  }
100  }
101  return {first, out};
102  }
103 
104  template<typename I, typename S, typename O, typename C, typename P>
105  constexpr unique_copy_result<I, O> unique_copy_impl(I first,
106  S last,
107  O out,
108  C pred,
109  P proj,
110  std::input_iterator_tag, std::true_type)
111  {
112  if(first != last)
113  {
114  *out = *first;
115  while(++first != last)
116  {
117  auto && x = *first;
118  if(!invoke(pred, invoke(proj, *out), invoke(proj, x)))
119  *++out = (decltype(x) &&)x;
120  }
121  ++out;
122  }
123  return {first, out};
124  }
125  } // namespace detail
127 
128  RANGES_FUNC_BEGIN(unique_copy)
129 
130 
137  template(typename I,
138  typename S,
139  typename O,
140  typename C = equal_to,
141  typename P = identity)(
142  requires input_iterator<I> AND sentinel_for<S, I> AND
143  indirect_relation<C, projected<I, P>> AND weakly_incrementable<O> AND
144  indirectly_copyable<I, O> AND
145  (forward_iterator<I> || forward_iterator<O> ||
146  indirectly_copyable_storable<I, O>)) //
147  constexpr unique_copy_result<I, O> RANGES_FUNC(unique_copy)(
148  I first, S last, O out, C pred = C{}, P proj = P{}) //
149  {
150  return detail::unique_copy_impl(std::move(first),
151  std::move(last),
152  std::move(out),
153  std::move(pred),
154  std::move(proj),
155  iterator_tag_of<I>(),
156  meta::bool_<forward_iterator<O>>{});
157  }
158 
160  template(typename Rng, typename O, typename C = equal_to, typename P = identity)(
161  requires input_range<Rng> AND
162  indirect_relation<C, projected<iterator_t<Rng>, P>> AND
163  weakly_incrementable<O> AND indirectly_copyable<iterator_t<Rng>, O> AND
164  (forward_iterator<iterator_t<Rng>> || forward_iterator<O> ||
165  indirectly_copyable_storable<iterator_t<Rng>, O>)) //
166  constexpr unique_copy_result<borrowed_iterator_t<Rng>, O> //
167  RANGES_FUNC(unique_copy)(Rng && rng, O out, C pred = C{}, P proj = P{}) //
168  {
169  return detail::unique_copy_impl(begin(rng),
170  end(rng),
171  std::move(out),
172  std::move(pred),
173  std::move(proj),
174  iterator_tag_of<iterator_t<Rng>>(),
175  meta::bool_<forward_iterator<O>>{});
176  }
177 
178  RANGES_FUNC_END(unique_copy)
179 
180  namespace cpp20
181  {
182  using ranges::unique_copy;
183  using ranges::unique_copy_result;
184  } // namespace cpp20
186 } // namespace ranges
187 
188 #include <range/v3/detail/epilogue.hpp>
189 
190 #endif
CPP_concept indirect_relation
\concept indirect_relation
Definition: concepts.hpp:670
CPP_concept forward_iterator
\concept forward_iterator
Definition: concepts.hpp:370
CPP_concept indirectly_copyable_storable
\concept indirectly_copyable_storable
Definition: concepts.hpp:798
CPP_concept indirectly_copyable
\concept indirectly_copyable
Definition: concepts.hpp:782
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition: meta.hpp:168
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
bool_< T::type::value==U::type::value > equal_to
A Boolean integral constant wrapper around the result of comparing T::type::value and U::type::value ...
Definition: meta.hpp:237
Tiny meta-programming library.