1 // <experimental/functional> -*- C++ -*-
3 // Copyright (C) 2014-2022 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file experimental/functional
26 * This is a TS C++ Library header.
30 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
31 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
33 #pragma GCC system_header
35 #if __cplusplus >= 201402L
40 #include <unordered_map>
43 #include <bits/stl_algo.h>
44 #ifdef _GLIBCXX_PARALLEL
45 # include <parallel/algorithm> // For std::__parallel::search
47 #include <experimental/bits/lfts_config.h>
49 namespace std _GLIBCXX_VISIBILITY(default)
51 _GLIBCXX_BEGIN_NAMESPACE_VERSION
53 namespace experimental
55 inline namespace fundamentals_v1
57 // See C++14 20.9.9, Function object binders
59 /// Variable template for std::is_bind_expression
60 template<typename _Tp>
61 constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
63 /// Variable template for std::is_placeholder
64 template<typename _Tp>
65 constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
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
85 return std::search(__first, __last,
86 std::get<0>(_M_m), std::get<1>(_M_m),
91 std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _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(); }
121 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
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)
130 : _M_bad_char{ std::array<_Tp, _Len>{}, std::move(__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); }
158 std::tuple<std::array<_Tp, _Len>, _Pred> _M_bad_char;
161 // Use __boyer_moore_array_base when pattern consists of narrow characters
162 // (or std::byte) and uses std::equal_to as the predicate.
163 template<typename _RAIter, typename _Hash, typename _Pred,
164 typename _Val = typename iterator_traits<_RAIter>::value_type,
165 typename _Diff = typename iterator_traits<_RAIter>::difference_type>
166 using __boyer_moore_base_t
167 = std::__conditional_t<std::__is_byte_like<_Val, _Pred>::value,
168 __boyer_moore_array_base<_Diff, 256, _Pred>,
169 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
171 template<typename _RAIter, typename _Hash
172 = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
173 typename _BinaryPredicate = std::equal_to<>>
174 class boyer_moore_searcher
175 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
177 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
178 using typename _Base::__diff_type;
181 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
182 _Hash __hf = _Hash(),
183 _BinaryPredicate __pred = _BinaryPredicate());
185 template<typename _RandomAccessIterator2>
186 _RandomAccessIterator2
187 operator()(_RandomAccessIterator2 __first,
188 _RandomAccessIterator2 __last) const;
192 _M_is_prefix(_RAIter __word, __diff_type __len,
195 const auto& __pred = this->_M_pred();
196 __diff_type __suffixlen = __len - __pos;
197 for (__diff_type __i = 0; __i < __suffixlen; ++__i)
198 if (!__pred(__word[__i], __word[__pos + __i]))
204 _M_suffix_length(_RAIter __word, __diff_type __len,
207 const auto& __pred = this->_M_pred();
209 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
217 template<typename _Tp>
219 _M_bad_char_shift(_Tp __c) const
220 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
224 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
227 template<typename _RAIter, typename _Hash
228 = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
229 typename _BinaryPredicate = std::equal_to<>>
230 class boyer_moore_horspool_searcher
231 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
233 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
234 using typename _Base::__diff_type;
237 boyer_moore_horspool_searcher(_RAIter __pat,
239 _Hash __hf = _Hash(),
240 _BinaryPredicate __pred
241 = _BinaryPredicate())
242 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
243 _M_pat(__pat), _M_pat_end(__pat_end)
246 template<typename _RandomAccessIterator2>
247 _RandomAccessIterator2
248 operator()(_RandomAccessIterator2 __first,
249 _RandomAccessIterator2 __last) const
251 const auto& __pred = this->_M_pred();
252 auto __patlen = _M_pat_end - _M_pat;
255 auto __len = __last - __first;
256 while (__len >= __patlen)
258 for (auto __scan = __patlen - 1;
259 __pred(__first[__scan], _M_pat[__scan]); --__scan)
262 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
270 template<typename _Tp>
272 _M_bad_char_shift(_Tp __c) const
273 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
279 /// Generator function for default_searcher
280 template<typename _ForwardIterator,
281 typename _BinaryPredicate = std::equal_to<>>
282 inline default_searcher<_ForwardIterator, _BinaryPredicate>
283 make_default_searcher(_ForwardIterator __pat_first,
284 _ForwardIterator __pat_last,
285 _BinaryPredicate __pred = _BinaryPredicate())
286 { return { __pat_first, __pat_last, __pred }; }
288 /// Generator function for boyer_moore_searcher
289 template<typename _RAIter, typename _Hash
290 = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
291 typename _BinaryPredicate = equal_to<>>
292 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
293 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
294 _Hash __hf = _Hash(),
295 _BinaryPredicate __pred = _BinaryPredicate())
296 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
298 /// Generator function for boyer_moore_horspool_searcher
299 template<typename _RAIter, typename _Hash
300 = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
301 typename _BinaryPredicate = equal_to<>>
302 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
303 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
304 _Hash __hf = _Hash(),
305 _BinaryPredicate __pred
306 = _BinaryPredicate())
307 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
309 template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
310 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
311 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
312 _Hash __hf, _BinaryPredicate __pred)
313 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
314 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
316 auto __patlen = __pat_end - __pat;
319 __diff_type __last_prefix = __patlen - 1;
320 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
322 if (_M_is_prefix(__pat, __patlen, __p + 1))
323 __last_prefix = __p + 1;
324 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
326 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
328 auto __slen = _M_suffix_length(__pat, __patlen, __p);
329 auto __pos = __patlen - 1 - __slen;
330 if (!__pred(__pat[__p - __slen], __pat[__pos]))
331 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
335 template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
336 template<typename _RandomAccessIterator2>
337 _RandomAccessIterator2
338 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
339 operator()(_RandomAccessIterator2 __first,
340 _RandomAccessIterator2 __last) const
342 auto __patlen = _M_pat_end - _M_pat;
345 const auto& __pred = this->_M_pred();
346 __diff_type __i = __patlen - 1;
347 auto __stringlen = __last - __first;
348 while (__i < __stringlen)
350 __diff_type __j = __patlen - 1;
351 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
357 return __first + __i + 1;
358 __i += std::max(_M_bad_char_shift(__first[__i]),
359 _M_good_suffix[__j]);
363 } // namespace fundamentals_v1
365 inline namespace fundamentals_v2
367 #define __cpp_lib_experimental_not_fn 201406
369 /// [func.not_fn] Function template not_fn
370 template<typename _Fn>
373 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
375 return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
377 } // namespace fundamentals_v2
378 } // namespace experimental
380 _GLIBCXX_END_NAMESPACE_VERSION
385 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL