Horizon
search_n.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 //===----------------------------------------------------------------------===//
14 //
15 // The LLVM Compiler Infrastructure
16 //
17 // This file is dual licensed under the MIT and the University of Illinois Open
18 // Source Licenses. See LICENSE.TXT for details.
19 //
20 //===----------------------------------------------------------------------===//
21 #ifndef RANGES_V3_ALGORITHM_SEARCH_N_HPP
22 #define RANGES_V3_ALGORITHM_SEARCH_N_HPP
23 
24 #include <meta/meta.hpp>
25 
26 #include <range/v3/range_fwd.hpp>
27 
38 #include <range/v3/utility/static_const.hpp>
40 
41 #include <range/v3/detail/prologue.hpp>
42 
43 namespace ranges
44 {
47 
49  namespace detail
50  {
51  template<typename I, typename S, typename D, typename V, typename C, typename P>
52  constexpr subrange<I> search_n_sized_impl(I const begin_,
53  S last,
54  D const d_,
55  D cnt,
56  V const & val,
57  C & pred,
58  P & proj)
59  {
60  D d = d_; // always the distance from first to end
61  auto first = uncounted(begin_);
62  while(true)
63  {
64  // Find first element in sequence 1 that matches val, with a mininum of
65  // loop checks
66  while(true)
67  {
68  if(d < cnt) // return the last if we've run out of room
69  {
70  auto e = ranges::next(recounted(begin_, std::move(first), d_ - d),
71  std::move(last));
72  return {e, e};
73  }
74  if(invoke(pred, invoke(proj, *first), val))
75  break;
76  ++first;
77  --d;
78  }
79  // *first matches val, now match elements after here
80  auto m = first;
81  D c = 0;
82  while(true)
83  {
84  if(++c == cnt) // If pattern exhausted, first is the answer (works
85  // for 1 element pattern)
86  return {recounted(begin_, std::move(first), d_ - d),
87  recounted(begin_, std::move(++m), d_ - d)};
88  ++m; // No need to check, we know we have room to match successfully
89  if(!invoke(pred,
90  invoke(proj, *m),
91  val)) // if there is a mismatch, restart with a new begin
92  {
93  first = next(std::move(m));
94  d -= (c + 1);
95  break;
96  } // else there is a match, check next elements
97  }
98  }
99  }
100 
101  template<typename I, typename S, typename D, typename V, typename C, typename P>
102  constexpr subrange<I> search_n_impl(I first,
103  S last,
104  D cnt,
105  V const & val,
106  C & pred,
107  P & proj)
108  {
109  while(true)
110  {
111  // Find first element in sequence 1 that matches val, with a mininum of
112  // loop checks
113  while(true)
114  {
115  if(first == last) // return last if no element matches val
116  return {first, first};
117  if(invoke(pred, invoke(proj, *first), val))
118  break;
119  ++first;
120  }
121  // *first matches val, now match elements after here
122  I m = first;
123  D c = 0;
124  while(true)
125  {
126  if(++c == cnt) // If pattern exhausted, first is the answer (works
127  // for 1 element pattern)
128  return {first, ++m};
129  if(++m == last) // Otherwise if source exhausted, pattern not found
130  return {m, m};
131  if(!invoke(pred,
132  invoke(proj, *m),
133  val)) // if there is a mismatch, restart with a new begin
134  {
135  first = next(std::move(m));
136  break;
137  } // else there is a match, check next elements
138  }
139  }
140  }
141  } // namespace detail
143 
144  RANGES_FUNC_BEGIN(search_n)
145 
146 
147  template(typename I,
148  typename S,
149  typename V,
150  typename C = equal_to,
151  typename P = identity)(
152  requires forward_iterator<I> AND sentinel_for<S, I> AND
153  indirectly_comparable<I, V const *, C, P>)
154  constexpr subrange<I> RANGES_FUNC(search_n)(I first,
155  S last,
156  iter_difference_t<I> cnt,
157  V const & val,
158  C pred = C{},
159  P proj = P{}) //
160  {
161  if(cnt <= 0)
162  return {first, first};
163  if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S, I>))
164  return detail::search_n_sized_impl(std::move(first),
165  std::move(last),
166  distance(first, last),
167  cnt,
168  val,
169  pred,
170  proj);
171  else
172  return detail::search_n_impl(
173  std::move(first), std::move(last), cnt, val, pred, proj);
174  }
175 
177  template(typename Rng, typename V, typename C = equal_to, typename P = identity)(
178  requires forward_range<Rng> AND
179  indirectly_comparable<iterator_t<Rng>, V const *, C, P>)
180  constexpr borrowed_subrange_t<Rng> RANGES_FUNC(search_n)(Rng && rng,
181  iter_difference_t<iterator_t<Rng>> cnt,
182  V const & val,
183  C pred = C{},
184  P proj = P{}) //
185  {
186  if(cnt <= 0)
187  return subrange<iterator_t<Rng>>{begin(rng), begin(rng)};
188  if(RANGES_CONSTEXPR_IF(sized_range<Rng>))
189  return detail::search_n_sized_impl(
190  begin(rng), end(rng), distance(rng), cnt, val, pred, proj);
191  else
192  return detail::search_n_impl(begin(rng), end(rng), cnt, val, pred, proj);
193  }
194 
195  RANGES_FUNC_END(search_n)
196 
197  namespace cpp20
198  {
199  using ranges::search_n;
200  }
202 } // namespace ranges
203 
204 #include <range/v3/detail/epilogue.hpp>
205 
206 #endif
CPP_concept indirectly_comparable
\concept indirectly_comparable
Definition: concepts.hpp:832
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.