29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 32 #pragma GCC system_header 34 #if __cplusplus >= 201402L 43 #ifdef _GLIBCXX_PARALLEL 48 namespace std _GLIBCXX_VISIBILITY(default)
50 namespace experimental
52 inline namespace fundamentals_v1
54 _GLIBCXX_BEGIN_NAMESPACE_VERSION
59 template<
typename _Tp>
63 template<
typename _Tp>
66 #define __cpp_lib_experimental_boyer_moore_searching 201411 70 template<
typename _ForwardIterator1,
typename _BinaryPredicate = equal_to<>>
71 class default_searcher
74 default_searcher(_ForwardIterator1 __pat_first,
75 _ForwardIterator1 __pat_last,
76 _BinaryPredicate __pred = _BinaryPredicate())
77 : _M_m(__pat_first, __pat_last, std::move(__pred))
80 template<
typename _ForwardIterator2>
82 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last)
const 85 std::get<0>(_M_m), std::get<1>(_M_m),
93 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred>
94 struct __boyer_moore_map_base
96 template<
typename _RAIter>
97 __boyer_moore_map_base(_RAIter __pat,
size_t __patlen,
98 _Hash&& __hf, _Pred&& __pred)
99 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
102 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
103 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
106 using __diff_type = _Tp;
109 _M_lookup(_Key __key, __diff_type __not_found)
const 111 auto __iter = _M_bad_char.find(__key);
112 if (__iter == _M_bad_char.end())
114 return __iter->second;
118 _M_pred()
const {
return _M_bad_char.key_eq(); }
120 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
123 template<
typename _Tp,
size_t _Len,
typename _Pred>
124 struct __boyer_moore_array_base
126 template<
typename _RAIter,
typename _Unused>
127 __boyer_moore_array_base(_RAIter __pat,
size_t __patlen,
128 _Unused&&, _Pred&& __pred)
129 : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
131 std::get<0>(_M_bad_char).fill(__patlen);
133 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
135 auto __ch = __pat[__i];
136 using _UCh = std::make_unsigned_t<decltype(__ch)>;
137 auto __uch =
static_cast<_UCh
>(__ch);
138 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
142 using __diff_type = _Tp;
144 template<
typename _Key>
146 _M_lookup(_Key __key, __diff_type __not_found)
const 148 auto __ukey =
static_cast<std::make_unsigned_t<_Key>
>(__key);
151 return std::get<0>(_M_bad_char)[__ukey];
155 _M_pred()
const {
return std::get<1>(_M_bad_char); }
160 template<
typename _Pred>
168 template<
typename _RAIter,
typename _Hash,
typename _Pred,
169 typename _Val =
typename iterator_traits<_RAIter>::value_type,
170 typename _Diff =
typename iterator_traits<_RAIter>::difference_type>
171 using __boyer_moore_base_t
172 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
173 && __is_std_equal_to<_Pred>::value,
174 __boyer_moore_array_base<_Diff, 256, _Pred>,
175 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
177 template<
typename _RAIter,
typename _Hash
180 class boyer_moore_searcher
181 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
183 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
184 using typename _Base::__diff_type;
187 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
188 _Hash __hf = _Hash(),
189 _BinaryPredicate __pred = _BinaryPredicate());
191 template<
typename _RandomAccessIterator2>
192 _RandomAccessIterator2
193 operator()(_RandomAccessIterator2 __first,
194 _RandomAccessIterator2 __last)
const;
198 _M_is_prefix(_RAIter __word, __diff_type __len,
201 const auto& __pred = this->_M_pred();
202 __diff_type __suffixlen = __len - __pos;
203 for (__diff_type __i = 0; __i < __suffixlen; ++__i)
204 if (!__pred(__word[__i], __word[__pos + __i]))
210 _M_suffix_length(_RAIter __word, __diff_type __len,
213 const auto& __pred = this->_M_pred();
215 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
223 template<
typename _Tp>
225 _M_bad_char_shift(_Tp __c)
const 226 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
230 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
233 template<
typename _RAIter,
typename _Hash
236 class boyer_moore_horspool_searcher
237 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
239 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
240 using typename _Base::__diff_type;
243 boyer_moore_horspool_searcher(_RAIter __pat,
245 _Hash __hf = _Hash(),
246 _BinaryPredicate __pred
247 = _BinaryPredicate())
248 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
249 _M_pat(__pat), _M_pat_end(__pat_end)
252 template<
typename _RandomAccessIterator2>
253 _RandomAccessIterator2
254 operator()(_RandomAccessIterator2 __first,
255 _RandomAccessIterator2 __last)
const 257 const auto& __pred = this->_M_pred();
258 auto __patlen = _M_pat_end - _M_pat;
261 auto __len = __last - __first;
262 while (__len >= __patlen)
264 for (
auto __scan = __patlen - 1;
265 __pred(__first[__scan], _M_pat[__scan]); --__scan)
268 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
276 template<
typename _Tp>
278 _M_bad_char_shift(_Tp __c)
const 279 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
286 template<
typename _ForwardIterator,
288 inline default_searcher<_ForwardIterator, _BinaryPredicate>
290 _ForwardIterator __pat_last,
291 _BinaryPredicate __pred = _BinaryPredicate())
292 {
return { __pat_first, __pat_last, __pred }; }
295 template<
typename _RAIter,
typename _Hash
298 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
300 _Hash __hf = _Hash(),
301 _BinaryPredicate __pred = _BinaryPredicate())
302 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
305 template<
typename _RAIter,
typename _Hash
308 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
310 _Hash __hf = _Hash(),
311 _BinaryPredicate __pred
312 = _BinaryPredicate())
313 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
315 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
316 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
317 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
318 _Hash __hf, _BinaryPredicate __pred)
319 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
320 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
322 auto __patlen = __pat_end - __pat;
325 __diff_type __last_prefix = __patlen - 1;
326 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
328 if (_M_is_prefix(__pat, __patlen, __p + 1))
329 __last_prefix = __p + 1;
330 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
332 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
334 auto __slen = _M_suffix_length(__pat, __patlen, __p);
335 auto __pos = __patlen - 1 - __slen;
336 if (!__pred(__pat[__p - __slen], __pat[__pos]))
337 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
341 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
342 template<
typename _RandomAccessIterator2>
343 _RandomAccessIterator2
344 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
345 operator()(_RandomAccessIterator2 __first,
346 _RandomAccessIterator2 __last)
const 348 auto __patlen = _M_pat_end - _M_pat;
351 const auto& __pred = this->_M_pred();
352 __diff_type __i = __patlen - 1;
353 auto __stringlen = __last - __first;
354 while (__i < __stringlen)
356 __diff_type __j = __patlen - 1;
357 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
363 return __first + __i + 1;
364 __i +=
std::max(_M_bad_char_shift(__first[__i]),
365 _M_good_suffix[__j]);
370 _GLIBCXX_END_NAMESPACE_VERSION
373 inline namespace fundamentals_v2
375 _GLIBCXX_BEGIN_NAMESPACE_VERSION
377 #define __cpp_lib_experimental_not_fn 201406 380 template<
typename _Fn>
383 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
388 _GLIBCXX_END_NAMESPACE_VERSION
395 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
boyer_moore_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())
Generator function for boyer_moore_searcher.
One of the comparison functors.
constexpr bool is_bind_expression_v
Variable template for std::is_bind_expression.
boyer_moore_horspool_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())
Generator function for boyer_moore_horspool_searcher.
Determines if the given type _Tp is a placeholder in a bind() expression and, if so, which placeholder it is.
constexpr int is_placeholder_v
Variable template for std::is_placeholder.
ISO C++ entities toplevel namespace is std.
Determines if the given type _Tp is a function object that should be treated as a subexpression when ...
default_searcher< _ForwardIterator, _BinaryPredicate > make_default_searcher(_ForwardIterator __pat_first, _ForwardIterator __pat_last, _BinaryPredicate __pred=_BinaryPredicate())
Generator function for default_searcher.
Primary class template hash.
auto not_fn(_Fn &&__fn) noexcept(std::is_nothrow_constructible< std::decay_t< _Fn >, _Fn &&>::value)
[func.not_fn] Function template not_fn
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.