Horizon
search.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_HPP
22 #define RANGES_V3_ALGORITHM_SEARCH_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 I1, typename S1, typename D1, typename I2, typename S2,
52  typename D2, typename C, typename P1, typename P2>
53  constexpr subrange<I1> search_sized_impl(I1 const begin1_,
54  S1 end1,
55  D1 const d1_,
56  I2 begin2,
57  S2 end2,
58  D2 d2,
59  C & pred,
60  P1 & proj1,
61  P2 & proj2)
62  {
63  D1 d1 = d1_;
64  auto begin1 = uncounted(begin1_);
65  while(true)
66  {
67  // Find first element in sequence 1 that matches *begin2, with a mininum
68  // of loop checks
69  while(true)
70  {
71  if(d1 < d2) // return the last if we've run out of room
72  {
73  auto e =
74  ranges::next(recounted(begin1_, std::move(begin1), d1_ - d1),
75  std::move(end1));
76  return {e, e};
77  }
78  if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
79  break;
80  ++begin1;
81  --d1;
82  }
83  // *begin1 matches *begin2, now match elements after here
84  auto m1 = begin1;
85  I2 m2 = begin2;
86  while(true)
87  {
88  if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
89  // for 1 element pattern)
90  {
91  return {recounted(begin1_, std::move(begin1), d1_ - d1),
92  recounted(begin1_, std::move(++m1), d1_ - d1)};
93  }
94  ++m1; // No need to check, we know we have room to match successfully
95  if(!invoke(
96  pred,
97  invoke(proj1, *m1),
98  invoke(
99  proj2,
100  *m2))) // if there is a mismatch, restart with a new begin1
101  {
102  ++begin1;
103  --d1;
104  break;
105  } // else there is a match, check next elements
106  }
107  }
108  }
109 
110  template<typename I1, typename S1, typename I2, typename S2, typename C,
111  typename P1, typename P2>
112  constexpr subrange<I1> search_impl(I1 begin1,
113  S1 end1,
114  I2 begin2,
115  S2 end2,
116  C & pred,
117  P1 & proj1,
118  P2 & proj2)
119  {
120  while(true)
121  {
122  // Find first element in sequence 1 that matches *begin2, with a mininum
123  // of loop checks
124  while(true)
125  {
126  if(begin1 == end1) // return end1 if no element matches *begin2
127  return {begin1, begin1};
128  if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
129  break;
130  ++begin1;
131  }
132  // *begin1 matches *begin2, now match elements after here
133  I1 m1 = begin1;
134  I2 m2 = begin2;
135  while(true)
136  {
137  if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
138  // for 1 element pattern)
139  return {begin1, ++m1};
140  if(++m1 == end1) // Otherwise if source exhausted, pattern not found
141  return {m1, m1};
142  if(!invoke(
143  pred,
144  invoke(proj1, *m1),
145  invoke(
146  proj2,
147  *m2))) // if there is a mismatch, restart with a new begin1
148  {
149  ++begin1;
150  break;
151  } // else there is a match, check next elements
152  }
153  }
154  }
155  } // namespace detail
157 
158  RANGES_FUNC_BEGIN(search)
159 
160 
161  template(typename I1,
162  typename S1,
163  typename I2,
164  typename S2,
165  typename C = equal_to,
166  typename P1 = identity,
167  typename P2 = identity)(
168  requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
169  forward_iterator<I2> AND sentinel_for<S2, I2> AND
170  indirectly_comparable<I1, I2, C, P1, P2>)
171  constexpr subrange<I1> RANGES_FUNC(search)(I1 begin1,
172  S1 end1,
173  I2 begin2,
174  S2 end2,
175  C pred = C{},
176  P1 proj1 = P1{},
177  P2 proj2 = P2{}) //
178  {
179  if(begin2 == end2)
180  return {begin1, begin1};
181  if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
182  sized_sentinel_for<S2, I2>))
183  return detail::search_sized_impl(std::move(begin1),
184  std::move(end1),
185  distance(begin1, end1),
186  std::move(begin2),
187  std::move(end2),
188  distance(begin2, end2),
189  pred,
190  proj1,
191  proj2);
192  else
193  return detail::search_impl(std::move(begin1),
194  std::move(end1),
195  std::move(begin2),
196  std::move(end2),
197  pred,
198  proj1,
199  proj2);
200  }
201 
203  template(typename Rng1,
204  typename Rng2,
205  typename C = equal_to,
206  typename P1 = identity,
207  typename P2 = identity)(
208  requires forward_range<Rng1> AND forward_range<Rng2> AND
209  indirectly_comparable<iterator_t<Rng1>, iterator_t<Rng2>, C, P1, P2>)
210  constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(search)(
211  Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
212  {
213  if(empty(rng2))
214  return subrange<iterator_t<Rng1>>{begin(rng1), begin(rng1)};
215  if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
216  return detail::search_sized_impl(begin(rng1),
217  end(rng1),
218  distance(rng1),
219  begin(rng2),
220  end(rng2),
221  distance(rng2),
222  pred,
223  proj1,
224  proj2);
225  else
226  return detail::search_impl(
227  begin(rng1), end(rng1), begin(rng2), end(rng2), pred, proj1, proj2);
228  }
229 
230  RANGES_FUNC_END(search)
231 
232  namespace cpp20
233  {
234  using ranges::search;
235  }
237 } // namespace ranges
238 
239 #include <range/v3/detail/epilogue.hpp>
240 
241 #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
bool_< 0==size< L >::type::value > empty
An Boolean integral constant wrapper around true if L is an empty type list; false,...
Definition: meta.hpp:2231
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.