29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
32 #pragma GCC system_header
34 #if __cplusplus <= 201103L
45 #ifdef _GLIBCXX_PARALLEL
49 namespace std _GLIBCXX_VISIBILITY(default)
51 namespace experimental
53 inline namespace fundamentals_v1
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
60 template<
typename _Tp>
64 template<
typename _Tp>
67 #define __cpp_lib_experimental_boyer_moore_searching 201411
71 template<
typename _ForwardIterator1,
typename _BinaryPredicate = equal_to<>>
72 class default_searcher
75 default_searcher(_ForwardIterator1 __pat_first,
76 _ForwardIterator1 __pat_last,
77 _BinaryPredicate __pred = _BinaryPredicate())
78 : _M_m(__pat_first, __pat_last, std::move(__pred))
81 template<
typename _ForwardIterator2>
83 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last)
const
86 std::get<0>(_M_m), std::get<1>(_M_m),
94 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred>
95 struct __boyer_moore_map_base
97 template<
typename _RAIter>
98 __boyer_moore_map_base(_RAIter __pat,
size_t __patlen,
99 _Hash&& __hf, _Pred&& __pred)
100 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
103 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
104 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
107 using __diff_type = _Tp;
110 _M_lookup(_Key __key, __diff_type __not_found)
const
112 auto __iter = _M_bad_char.find(__key);
113 if (__iter == _M_bad_char.end())
115 return __iter->second;
119 _M_pred()
const {
return _M_bad_char.key_eq(); }
124 template<
typename _Tp,
size_t _Len,
typename _Pred>
125 struct __boyer_moore_array_base
127 template<
typename _RAIter,
typename _Unused>
128 __boyer_moore_array_base(_RAIter __pat,
size_t __patlen,
129 _Unused&&, _Pred&& __pred)
132 std::get<0>(_M_bad_char).fill(__patlen);
134 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
136 auto __ch = __pat[__i];
137 using _UCh = std::make_unsigned_t<decltype(__ch)>;
138 auto __uch =
static_cast<_UCh
>(__ch);
139 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
143 using __diff_type = _Tp;
145 template<
typename _Key>
147 _M_lookup(_Key __key, __diff_type __not_found)
const
149 auto __ukey =
static_cast<std::make_unsigned_t<_Key>
>(__key);
152 return std::get<0>(_M_bad_char)[__ukey];
156 _M_pred()
const {
return std::get<1>(_M_bad_char); }
161 template<
typename _Pred>
165 struct __is_std_equal_to<std::equal_to<void>> :
std::true_type { };
169 template<
typename _RAIter,
typename _Hash,
typename _Pred,
170 typename _Val =
typename iterator_traits<_RAIter>::value_type,
171 typename _Diff =
typename iterator_traits<_RAIter>::difference_type>
172 using __boyer_moore_base_t
173 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
174 && __is_std_equal_to<_Pred>::value,
175 __boyer_moore_array_base<_Diff, 256, _Pred>,
176 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
178 template<
typename _RAIter,
typename _Hash
181 class boyer_moore_searcher
182 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
184 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
185 using typename _Base::__diff_type;
188 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
189 _Hash __hf = _Hash(),
190 _BinaryPredicate __pred = _BinaryPredicate());
192 template<
typename _RandomAccessIterator2>
193 _RandomAccessIterator2
194 operator()(_RandomAccessIterator2 __first,
195 _RandomAccessIterator2 __last)
const;
199 _M_is_prefix(_RAIter __word, __diff_type __len,
202 const auto& __pred = this->_M_pred();
203 __diff_type __suffixlen = __len - __pos;
204 for (__diff_type __i = 0; __i < __suffixlen; ++__i)
205 if (!__pred(__word[__i], __word[__pos + __i]))
211 _M_suffix_length(_RAIter __word, __diff_type __len,
214 const auto& __pred = this->_M_pred();
216 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
224 template<
typename _Tp>
226 _M_bad_char_shift(_Tp __c)
const
227 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
234 template<
typename _RAIter,
typename _Hash
237 class boyer_moore_horspool_searcher
238 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
240 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
241 using typename _Base::__diff_type;
244 boyer_moore_horspool_searcher(_RAIter __pat,
246 _Hash __hf = _Hash(),
247 _BinaryPredicate __pred
248 = _BinaryPredicate())
249 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
250 _M_pat(__pat), _M_pat_end(__pat_end)
253 template<
typename _RandomAccessIterator2>
254 _RandomAccessIterator2
255 operator()(_RandomAccessIterator2 __first,
256 _RandomAccessIterator2 __last)
const
258 const auto& __pred = this->_M_pred();
259 auto __patlen = _M_pat_end - _M_pat;
262 auto __len = __last - __first;
263 while (__len >= __patlen)
265 for (
auto __scan = __patlen - 1;
266 __pred(__first[__scan], _M_pat[__scan]); --__scan)
269 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
277 template<
typename _Tp>
279 _M_bad_char_shift(_Tp __c)
const
280 {
return this->_M_lookup(__c, _M_pat_end - _M_pat); }
287 template<
typename _ForwardIterator,
289 inline default_searcher<_ForwardIterator, _BinaryPredicate>
290 make_default_searcher(_ForwardIterator __pat_first,
291 _ForwardIterator __pat_last,
292 _BinaryPredicate __pred = _BinaryPredicate())
293 {
return { __pat_first, __pat_last, __pred }; }
296 template<
typename _RAIter,
typename _Hash
298 typename _BinaryPredicate = equal_to<>>
299 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
300 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
301 _Hash __hf = _Hash(),
302 _BinaryPredicate __pred = _BinaryPredicate())
303 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
306 template<
typename _RAIter,
typename _Hash
308 typename _BinaryPredicate = equal_to<>>
309 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
310 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
311 _Hash __hf = _Hash(),
312 _BinaryPredicate __pred
313 = _BinaryPredicate())
314 {
return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
316 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
317 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
318 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
319 _Hash __hf, _BinaryPredicate __pred)
320 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
321 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
323 auto __patlen = __pat_end - __pat;
326 __diff_type __last_prefix = __patlen - 1;
327 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
329 if (_M_is_prefix(__pat, __patlen, __p + 1))
330 __last_prefix = __p + 1;
331 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
333 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
335 auto __slen = _M_suffix_length(__pat, __patlen, __p);
336 auto __pos = __patlen - 1 - __slen;
337 if (!__pred(__pat[__p - __slen], __pat[__pos]))
338 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
342 template<
typename _RAIter,
typename _Hash,
typename _BinaryPredicate>
343 template<
typename _RandomAccessIterator2>
344 _RandomAccessIterator2
345 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
346 operator()(_RandomAccessIterator2 __first,
347 _RandomAccessIterator2 __last)
const
349 auto __patlen = _M_pat_end - _M_pat;
352 const auto& __pred = this->_M_pred();
353 __diff_type __i = __patlen - 1;
354 auto __stringlen = __last - __first;
355 while (__i < __stringlen)
357 __diff_type __j = __patlen - 1;
358 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
364 return __first + __i + 1;
365 __i +=
std::max(_M_bad_char_shift(__first[__i]),
366 _M_good_suffix[__j]);
371 _GLIBCXX_END_NAMESPACE_VERSION
374 inline namespace fundamentals_v2
376 _GLIBCXX_BEGIN_NAMESPACE_VERSION
378 #define __cpp_lib_experimental_not_fn 201406
381 template<
typename _Fn>
387 template<
typename _Fn2>
389 _Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { }
397 template<
typename... _Args>
399 operator()(_Args&&... __args)
400 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
401 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
402 {
return !_M_fn(std::forward<_Args>(__args)...); }
404 template<
typename... _Args>
406 operator()(_Args&&... __args)
const
407 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
408 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
409 {
return !_M_fn(std::forward<_Args>(__args)...); }
411 template<
typename... _Args>
413 operator()(_Args&&... __args)
volatile
414 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
415 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
416 {
return !_M_fn(std::forward<_Args>(__args)...); }
418 template<
typename... _Args>
420 operator()(_Args&&... __args)
const volatile
421 noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
422 -> decltype(!_M_fn(std::forward<_Args>(__args)...))
423 {
return !_M_fn(std::forward<_Args>(__args)...); }
427 template<
typename _Fn>
430 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
436 _GLIBCXX_END_NAMESPACE_VERSION
443 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Primary class template hash.
A standard container for storing a fixed size sequence of elements.
Determines if the given type _Tp is a function object that should be treated as a subexpression when ...
One of the comparison functors.
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
Determines if the given type _Tp is a placeholder in a bind() expression and, if so, which placeholder it is.