Horizon
find_end.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2014-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_FIND_END_HPP
14 #define RANGES_V3_ALGORITHM_FIND_END_HPP
15 
16 #include <utility>
17 
18 #include <meta/meta.hpp>
19 
20 #include <range/v3/range_fwd.hpp>
21 
31 #include <range/v3/utility/static_const.hpp>
33 
34 #include <range/v3/detail/prologue.hpp>
35 
36 namespace ranges
37 {
39  namespace detail
40  {
41  template(typename I, typename S)(
42  requires input_iterator<I> AND sentinel_for<S, I>)
43  constexpr I next_to_if(I i, S s, std::true_type)
44  {
45  return ranges::next(i, s);
46  }
47 
48  template(typename I, typename S)(
49  requires input_iterator<I> AND sentinel_for<S, I>)
50  constexpr S next_to_if(I, S s, std::false_type)
51  {
52  return s;
53  }
54 
55  template(bool B, typename I, typename S)(
56  requires input_iterator<I> AND sentinel_for<S, I>)
57  constexpr meta::if_c<B, I, S> next_to_if(I i, S s)
58  {
59  return detail::next_to_if(std::move(i), std::move(s), meta::bool_<B>{});
60  }
61 
62  template<typename I1, typename S1, typename I2, typename S2, typename R,
63  typename P>
64  constexpr subrange<I1> find_end_impl(I1 begin1, S1 end1, I2 begin2, S2 end2, R pred, P proj,
65  std::forward_iterator_tag, std::forward_iterator_tag)
66  {
67  bool found = false;
68  I1 res_begin, res_end;
69  if(begin2 == end2)
70  {
71  auto e1 = ranges::next(begin1, end1);
72  return {e1, e1};
73  }
74  while(true)
75  {
76  while(true)
77  {
78  if(begin1 == end1)
79  return {(found ? res_begin : begin1), (found ? res_end : begin1)};
80  if(invoke(pred, invoke(proj, *begin1), *begin2))
81  break;
82  ++begin1;
83  }
84  auto tmp1 = begin1;
85  auto tmp2 = begin2;
86  while(true)
87  {
88  if(++tmp2 == end2)
89  {
90  res_begin = begin1++;
91  res_end = ++tmp1;
92  found = true;
93  break;
94  }
95  if(++tmp1 == end1)
96  return {(found ? res_begin : tmp1), (found ? res_end : tmp1)};
97  if(!invoke(pred, invoke(proj, *tmp1), *tmp2))
98  {
99  ++begin1;
100  break;
101  }
102  }
103  }
104  }
105 
106  template<typename I1, typename I2, typename R, typename P>
107  constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
108  std::bidirectional_iterator_tag,
109  std::bidirectional_iterator_tag)
110  {
111  // modeled after search algorithm (in reverse)
112  if(begin2 == end2)
113  return {end1, end1}; // Everything matches an empty sequence
114  I1 l1 = end1;
115  I2 l2 = end2;
116  --l2;
117  while(true)
118  {
119  // Find end element in sequence 1 that matches *(end2-1), with a mininum
120  // of loop checks
121  do
122  // return {end1,end1} if no element matches *begin2
123  if(begin1 == l1)
124  return {end1, end1};
125  while(!invoke(pred, invoke(proj, *--l1), *l2));
126  // *l1 matches *l2, now match elements before here
127  I1 m1 = l1;
128  I2 m2 = l2;
129  do
130  // If pattern exhausted, {m1,++l1} is the answer
131  // (works for 1 element pattern)
132  if(m2 == begin2)
133  return {m1, ++l1};
134  // Otherwise if source exhausted, pattern not found
135  else if(m1 == begin1)
136  return {end1, end1};
137  // if there is a mismatch, restart with a new l1
138  // else there is a match, check next elements
139  while(invoke(pred, invoke(proj, *--m1), *--m2));
140  }
141  }
142 
143  template<typename I1, typename I2, typename R, typename P>
144  constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
145  std::random_access_iterator_tag,
146  std::random_access_iterator_tag)
147  {
148  // Take advantage of knowing source and pattern lengths. Stop short when
149  // source is smaller than pattern
150  auto len2 = end2 - begin2;
151  if(len2 == 0)
152  return {end1, end1};
153  auto len1 = end1 - begin1;
154  if(len1 < len2)
155  return {end1, end1};
156  I1 const start =
157  begin1 + (len2 - 1); // End of pattern match can't go before here
158  I1 l1 = end1;
159  I2 l2 = end2;
160  --l2;
161  while(true)
162  {
163  do
164  if(start == l1)
165  return {end1, end1};
166  while(!invoke(pred, invoke(proj, *--l1), *l2));
167  I1 m1 = l1;
168  I2 m2 = l2;
169  do
170  if(m2 == begin2)
171  return {m1, ++l1};
172  // no need to check range on m1 because s guarantees we have enough source
173  while(invoke(pred, invoke(proj, *--m1), *--m2));
174  }
175  }
176  } // namespace detail
178 
181  RANGES_FUNC_BEGIN(find_end)
182 
183 
184  template(typename I1,
185  typename S1,
186  typename I2,
187  typename S2,
188  typename R = equal_to,
189  typename P = identity)(
190  requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
191  forward_iterator<I2> AND sentinel_for<S2, I2> AND
192  indirect_relation<R, projected<I1, P>, I2>)
193  constexpr subrange<I1> RANGES_FUNC(find_end)(
194  I1 begin1, S1 end1, I2 begin2, S2 end2, R pred = R{}, P proj = P{}) //
195  {
196  constexpr bool Bidi =
197  bidirectional_iterator<I1> && bidirectional_iterator<I2>;
198  return detail::find_end_impl(begin1,
199  detail::next_to_if<Bidi>(begin1, end1),
200  begin2,
201  detail::next_to_if<Bidi>(begin2, end2),
202  std::move(pred),
203  std::move(proj),
204  iterator_tag_of<I1>(),
205  iterator_tag_of<I2>());
206  }
207 
209  template(typename Rng1,
210  typename Rng2,
211  typename R = equal_to,
212  typename P = identity)(
213  requires forward_range<Rng1> AND forward_range<Rng2> AND
215  constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(find_end)(
216  Rng1 && rng1, Rng2 && rng2, R pred = R{}, P proj = P{}) //
217  {
218  return (*this)(begin(rng1),
219  end(rng1),
220  begin(rng2),
221  end(rng2),
222  std::move(pred),
223  std::move(proj));
224  }
225 
226  RANGES_FUNC_END(find_end)
227 
228  namespace cpp20
229  {
230  using ranges::find_end;
231  }
233 } // namespace ranges
234 
235 #include <range/v3/detail/epilogue.hpp>
236 
237 #endif
template(typename Rng1, typename Rng2, typename R=equal_to, typename P=identity)(requires forward_range< Rng1 > AND forward_range< Rng2 > AND indirect_relation< R
This is an overloaded member function, provided for convenience. It differs from the above function o...
CPP_concept sentinel_for
\concept sentinel_for
Definition: concepts.hpp:306
CPP_concept indirect_relation
\concept indirect_relation
Definition: concepts.hpp:670
CPP_concept forward_iterator
\concept forward_iterator
Definition: concepts.hpp:370
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
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
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.
Definition: comparisons.hpp:28
Definition: identity.hpp:25
Definition: subrange.hpp:196