29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
32 #pragma GCC system_header
34 #if __cplusplus <= 201103L
46 namespace std _GLIBCXX_VISIBILITY(default)
48 namespace experimental
50 inline namespace fundamentals_v1
52 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57 template<
typename _Tp>
61 template<
typename _Tp>
64 #define __cpp_lib_experimental_boyer_moore_searching 201411
68 template<
typename _ForwardIterator1,
typename _BinaryPredicate = equal_to<>>
69 class default_searcher
72 default_searcher(_ForwardIterator1 __pat_first,
73 _ForwardIterator1 __pat_last,
74 _BinaryPredicate __pred = _BinaryPredicate())
75 : _M_m(__pat_first, __pat_last,
std::move(__pred))
78 template<
typename _ForwardIterator2>
80 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last)
const
83 std::get<0>(_M_m), std::get<1>(_M_m),
91 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred>
92 struct __boyer_moore_map_base
94 template<
typename _RAIter>
95 __boyer_moore_map_base(_RAIter __pat,
size_t __patlen,
96 _Hash&& __hf, _Pred&& __pred)
97 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
100 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
101 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
104 using __diff_type = _Tp;
107 _M_lookup(_Key __key, __diff_type __not_found)
const
109 auto __iter = _M_bad_char.find(__key);
110 if (__iter == _M_bad_char.end())
112 return __iter->second;
116 _M_pred()
const {
return _M_bad_char.key_eq(); }
121 template<
typename _Tp,
size_t _Len,
typename _Pred>
122 struct __boyer_moore_array_base
124 template<
typename _RAIter,
typename _Unused>
125 __boyer_moore_array_base(_RAIter __pat,
size_t __patlen,
126 _Unused&&, _Pred&& __pred)
127 : _M_bad_char{ {}, std::move(__pred) }
129 std::get<0>(_M_bad_char).fill(__patlen);
131 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
133 auto __ch = __pat[__i];
134 using _UCh = std::make_unsigned_t<decltype(__ch)>;
135 auto __uch =
static_cast<_UCh
>(__ch);
136 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
140 using __diff_type = _Tp;
142 template<
typename _Key>
144 _M_lookup(_Key __key, __diff_type __not_found)
const
146 auto __ukey =
static_cast<std::make_unsigned_t<_Key>
>(__key);
149 return std::get<0>(_M_bad_char)[__ukey];
153 _M_pred()
const {
return std::get<1>(_M_bad_char); }
158 template<
typename _Pred>
166 template<
typename _RAIter,
typename _Hash,
typename _Pred,
167 typename _Val =
typename iterator_traits<_RAIter>::value_type,
168 typename _Diff =
typename iterator_traits<_RAIter>::difference_type>
169 using __boyer_moore_base_t
170 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
171 && __is_std_equal_to<_Pred>::value,
172 __boyer_moore_array_base<_Diff, 256, _Pred>,
173 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
175 template<
typename _RAIter,
typename _Hash
178 class boyer_moore_searcher
179 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
181 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
182 using typename _Base::__diff_type;
185 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
186 _Hash __hf = _Hash(),
187 _BinaryPredicate __pred = _BinaryPredicate());
189 template<
typename _RandomAccessIterator2>
190 _RandomAccessIterator2
191 operator()(_RandomAccessIterator2 __first,
192 _RandomAccessIterator2 __last)
const;
196 _M_is_prefix(_RAIter __word, __diff_type __len,
199 const auto& __pred = this->_M_pred();
200 __diff_type __suffixlen = __len - __pos;
201 for (__diff_type __i = 0; __i < __suffixlen; ++__i)
202 if (!__pred(__word[__i], __word[__pos + __i]))
208 _M_suffix_length(_RAIter __word, __diff_type __len,
211 const auto& __pred = this->_M_pred();
213 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
221 template<
typename _Tp>
223 _M_bad_char_shift(_Tp __c)
const
224 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
231 template<
typename _RAIter,
typename _Hash
234 class boyer_moore_horspool_searcher
235 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
237 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
238 using typename _Base::__diff_type;
241 boyer_moore_horspool_searcher(_RAIter __pat,
243 _Hash __hf = _Hash(),
244 _BinaryPredicate __pred
245 = _BinaryPredicate())
246 : _Base(__pat, __pat_end - __pat,
std::move(__hf),
std::move(__pred)),
247 _M_pat(__pat), _M_pat_end(__pat_end)
250 template<
typename _RandomAccessIterator2>
251 _RandomAccessIterator2
252 operator()(_RandomAccessIterator2 __first,
253 _RandomAccessIterator2 __last)
const
255 const auto& __pred = this->_M_pred();
256 auto __patlen = _M_pat_end - _M_pat;
259 auto __len = __last - __first;
260 while (__len >= __patlen)
262 for (
auto __scan = __patlen - 1;
263 __pred(__first[__scan], _M_pat[__scan]); --__scan)
266 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
274 template<
typename _Tp>
276 _M_bad_char_shift(_Tp __c)
const
277 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
284 template<
typename _ForwardIterator,
286 inline default_searcher<_ForwardIterator, _BinaryPredicate>
287 make_default_searcher(_ForwardIterator __pat_first,
288 _ForwardIterator __pat_last,
289 _BinaryPredicate __pred = _BinaryPredicate())
290 {
return { __pat_first, __pat_last, __pred }; }
293 template<
typename _RAIter,
typename _Hash
295 typename _BinaryPredicate = equal_to<>>
296 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
297 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
298 _Hash __hf = _Hash(),
299 _BinaryPredicate __pred = _BinaryPredicate())
300 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
303 template<
typename _RAIter,
typename _Hash
305 typename _BinaryPredicate = equal_to<>>
306 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
307 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
308 _Hash __hf = _Hash(),
309 _BinaryPredicate __pred
310 = _BinaryPredicate())
311 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
313 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
314 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
315 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
316 _Hash __hf, _BinaryPredicate __pred)
317 : _Base(__pat, __pat_end - __pat,
std::move(__hf),
std::move(__pred)),
318 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
320 auto __patlen = __pat_end - __pat;
323 __diff_type __last_prefix = __patlen - 1;
324 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
326 if (_M_is_prefix(__pat, __patlen, __p + 1))
327 __last_prefix = __p + 1;
328 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
330 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
332 auto __slen = _M_suffix_length(__pat, __patlen, __p);
333 auto __pos = __patlen - 1 - __slen;
334 if (!__pred(__pat[__p - __slen], __pat[__pos]))
335 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
339 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
340 template<
typename _RandomAccessIterator2>
341 _RandomAccessIterator2
342 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
343 operator()(_RandomAccessIterator2 __first,
344 _RandomAccessIterator2 __last)
const
346 auto __patlen = _M_pat_end - _M_pat;
349 const auto& __pred = this->_M_pred();
350 __diff_type __i = __patlen - 1;
351 auto __stringlen = __last - __first;
352 while (__i < __stringlen)
354 __diff_type __j = __patlen - 1;
355 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
361 return __first + __i + 1;
362 __i +=
std::max(_M_bad_char_shift(__first[__i]),
363 _M_good_suffix[__j]);
368 _GLIBCXX_END_NAMESPACE_VERSION
371 inline namespace fundamentals_v2
373 _GLIBCXX_BEGIN_NAMESPACE_VERSION
375 #define __cpp_lib_experimental_not_fn 201406
378 template<
typename _Fn>
384 template<
typename _Fn2>
386 _Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { }
394 template<
typename... _Args>
396 operator()(_Args&&... __args)
397 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
398 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
399 {
return !_M_fn(std::forward<_Args>(__args)...); }
401 template<
typename... _Args>
403 operator()(_Args&&... __args)
const
404 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
405 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
406 {
return !_M_fn(std::forward<_Args>(__args)...); }
408 template<
typename... _Args>
410 operator()(_Args&&... __args)
volatile
411 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
412 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
413 {
return !_M_fn(std::forward<_Args>(__args)...); }
415 template<
typename... _Args>
417 operator()(_Args&&... __args)
const volatile
418 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
419 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
420 {
return !_M_fn(std::forward<_Args>(__args)...); }
424 template<
typename _Fn>
427 noexcept(
std::is_nothrow_constructible<
std::decay_t<_Fn>, _Fn&&>::value)
433 _GLIBCXX_END_NAMESPACE_VERSION
440 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
Primary class template hash.
ISO C++ entities toplevel namespace is std.
Determines if the given type _Tp is a placeholder in a bind() expression and, if so, which placeholder it is. [TR1 3.6.2].
One of the comparison functors.
Determines if the given type _Tp is a function object should be treated as a subexpression when evalu...