Horizon
Loading...
Searching...
No Matches
search_n.hpp
Go to the documentation of this file.
1
2// 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
27
38#include <range/v3/utility/static_const.hpp>
40
41#include <range/v3/detail/prologue.hpp>
42
43namespace 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
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.