30#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
31#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
33#pragma GCC system_header
37#if __cplusplus >= 201402L
42#include <unordered_map>
46#ifdef _GLIBCXX_PARALLEL
51namespace std _GLIBCXX_VISIBILITY(default)
53_GLIBCXX_BEGIN_NAMESPACE_VERSION
57inline namespace fundamentals_v1
62 template<
typename _Tp>
66 template<
typename _Tp>
69#define __cpp_lib_experimental_boyer_moore_searching 201411
73 template<
typename _ForwardIterator1,
typename _BinaryPredicate = equal_to<>>
74 class default_searcher
77 default_searcher(_ForwardIterator1 __pat_first,
78 _ForwardIterator1 __pat_last,
79 _BinaryPredicate __pred = _BinaryPredicate())
80 : _M_m(__pat_first, __pat_last,
std::move(__pred))
83 template<
typename _ForwardIterator2>
85 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last)
const
87 return std::search(__first, __last,
88 std::get<0>(_M_m), std::get<1>(_M_m),
96 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred>
97 struct __boyer_moore_map_base
99 template<
typename _RAIter>
100 __boyer_moore_map_base(_RAIter __pat,
size_t __patlen,
101 _Hash&& __hf, _Pred&& __pred)
105 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
106 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
109 using __diff_type = _Tp;
112 _M_lookup(_Key __key, __diff_type __not_found)
const
114 auto __iter = _M_bad_char.find(__key);
115 if (__iter == _M_bad_char.end())
117 return __iter->second;
121 _M_pred()
const {
return _M_bad_char.key_eq(); }
123 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
126 template<
typename _Tp,
size_t _Len,
typename _Pred>
127 struct __boyer_moore_array_base
129 template<
typename _RAIter,
typename _Unused>
130 __boyer_moore_array_base(_RAIter __pat,
size_t __patlen,
131 _Unused&&, _Pred&& __pred)
132 : _M_bad_char{
std::array<_Tp, _Len>{},
std::move(__pred) }
134 std::get<0>(_M_bad_char).fill(__patlen);
136 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
138 auto __ch = __pat[__i];
140 auto __uch =
static_cast<_UCh
>(__ch);
141 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
145 using __diff_type = _Tp;
147 template<
typename _Key>
149 _M_lookup(_Key __key, __diff_type __not_found)
const
154 return std::get<0>(_M_bad_char)[__ukey];
158 _M_pred()
const {
return std::get<1>(_M_bad_char); }
165 template<
typename _RAIter,
typename _Hash,
typename _Pred,
166 typename _Val =
typename iterator_traits<_RAIter>::value_type,
167 typename _Diff =
typename iterator_traits<_RAIter>::difference_type>
168 using __boyer_moore_base_t
169 = std::__conditional_t<std::__is_byte_like<_Val, _Pred>::value,
170 __boyer_moore_array_base<_Diff, 256, _Pred>,
171 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
173 template<
typename _RAIter,
typename _Hash
176 class boyer_moore_searcher
177 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
179 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
180 using typename _Base::__diff_type;
183 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
184 _Hash __hf = _Hash(),
185 _BinaryPredicate __pred = _BinaryPredicate());
187 template<
typename _RandomAccessIterator2>
188 _RandomAccessIterator2
189 operator()(_RandomAccessIterator2 __first,
190 _RandomAccessIterator2 __last)
const;
194 _M_is_prefix(_RAIter __word, __diff_type __len,
197 const auto& __pred = this->_M_pred();
198 __diff_type __suffixlen = __len - __pos;
199 for (__diff_type __i = 0; __i < __suffixlen; ++__i)
200 if (!__pred(__word[__i], __word[__pos + __i]))
206 _M_suffix_length(_RAIter __word, __diff_type __len,
209 const auto& __pred = this->_M_pred();
211 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
219 template<
typename _Tp>
221 _M_bad_char_shift(_Tp __c)
const
222 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
226 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
229 template<
typename _RAIter,
typename _Hash
232 class boyer_moore_horspool_searcher
233 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
235 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
236 using typename _Base::__diff_type;
239 boyer_moore_horspool_searcher(_RAIter __pat,
241 _Hash __hf = _Hash(),
242 _BinaryPredicate __pred
243 = _BinaryPredicate())
244 : _Base(__pat, __pat_end - __pat,
std::
move(__hf),
std::
move(__pred)),
245 _M_pat(__pat), _M_pat_end(__pat_end)
248 template<
typename _RandomAccessIterator2>
249 _RandomAccessIterator2
250 operator()(_RandomAccessIterator2 __first,
251 _RandomAccessIterator2 __last)
const
253 const auto& __pred = this->_M_pred();
254 auto __patlen = _M_pat_end - _M_pat;
257 auto __len = __last - __first;
258 while (__len >= __patlen)
260 for (
auto __scan = __patlen - 1;
261 __pred(__first[__scan], _M_pat[__scan]); --__scan)
264 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
272 template<
typename _Tp>
274 _M_bad_char_shift(_Tp __c)
const
275 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
282 template<
typename _ForwardIterator,
284 inline default_searcher<_ForwardIterator, _BinaryPredicate>
286 _ForwardIterator __pat_last,
287 _BinaryPredicate __pred = _BinaryPredicate())
288 {
return { __pat_first, __pat_last, __pred }; }
291 template<
typename _RAIter,
typename _Hash
294 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
296 _Hash __hf = _Hash(),
297 _BinaryPredicate __pred = _BinaryPredicate())
301 template<
typename _RAIter,
typename _Hash
304 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
306 _Hash __hf = _Hash(),
307 _BinaryPredicate __pred
308 = _BinaryPredicate())
311 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
312 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
313 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
314 _Hash __hf, _BinaryPredicate __pred)
315 : _Base(__pat, __pat_end - __pat,
std::
move(__hf),
std::
move(__pred)),
316 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
318 auto __patlen = __pat_end - __pat;
321 __diff_type __last_prefix = __patlen - 1;
322 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
324 if (_M_is_prefix(__pat, __patlen, __p + 1))
325 __last_prefix = __p + 1;
326 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
328 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
330 auto __slen = _M_suffix_length(__pat, __patlen, __p);
331 auto __pos = __patlen - 1 - __slen;
332 if (!__pred(__pat[__p - __slen], __pat[__pos]))
333 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
337 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
338 template<
typename _RandomAccessIterator2>
339 _RandomAccessIterator2
340 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
341 operator()(_RandomAccessIterator2 __first,
342 _RandomAccessIterator2 __last)
const
344 auto __patlen = _M_pat_end - _M_pat;
347 const auto& __pred = this->_M_pred();
348 __diff_type __i = __patlen - 1;
349 auto __stringlen = __last - __first;
350 while (__i < __stringlen)
352 __diff_type __j = __patlen - 1;
353 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
359 return __first + __i + 1;
360 __i +=
std::max(_M_bad_char_shift(__first[__i]),
361 _M_good_suffix[__j]);
367inline namespace fundamentals_v2
369#define __cpp_lib_experimental_not_fn 201406
372 template<
typename _Fn>
382_GLIBCXX_END_NAMESPACE_VERSION
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr auto not_fn(_Fn &&__fn) noexcept(std::is_nothrow_constructible< std::decay_t< _Fn >, _Fn && >::value)
ISO C++ entities toplevel namespace is std.
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.
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.
default_searcher< _ForwardIterator, _BinaryPredicate > make_default_searcher(_ForwardIterator __pat_first, _ForwardIterator __pat_last, _BinaryPredicate __pred=_BinaryPredicate())
Generator function for default_searcher.
Trait that identifies a bind expression.
Determines if the given type _Tp is a placeholder in a bind() expression and, if so,...
Primary class template hash.
Primary class template, tuple.
One of the comparison functors.