source: Daodan/MSYS2/mingw32/include/c++/11.2.0/experimental/functional@ 1181

Last change on this file since 1181 was 1166, checked in by rossy, 3 years ago

Daodan: Replace MinGW build env with an up-to-date MSYS2 env
File size: 12.0 KB
RevLine 
[1166]1// <experimental/functional> -*- C++ -*-
2
3// Copyright (C) 2014-2021 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file experimental/functional
26 * This is a TS C++ Library header.
27 * @ingroup libfund-ts
28 */
29
30#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
31#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
32
33#pragma GCC system_header
34
35#if __cplusplus >= 201402L
36
37#include <functional>
38#include <tuple>
39#include <iterator>
40#include <unordered_map>
41#include <vector>
42#include <array>
43#include <bits/stl_algo.h>
44#ifdef _GLIBCXX_PARALLEL
45# include <parallel/algorithm> // For std::__parallel::search
46#endif
47#include <experimental/bits/lfts_config.h>
48
49namespace std _GLIBCXX_VISIBILITY(default)
50{
51_GLIBCXX_BEGIN_NAMESPACE_VERSION
52
53namespace experimental
54{
55inline namespace fundamentals_v1
56{
57 // See C++14 20.9.9, Function object binders
58
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;
62
63 /// Variable template for std::is_placeholder
64 template<typename _Tp>
65 constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
66
67#define __cpp_lib_experimental_boyer_moore_searching 201411
68
69 // Searchers
70
71 template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
72 class default_searcher
73 {
74 public:
75 default_searcher(_ForwardIterator1 __pat_first,
76 _ForwardIterator1 __pat_last,
77 _BinaryPredicate __pred = _BinaryPredicate())
78 : _M_m(__pat_first, __pat_last, std::move(__pred))
79 { }
80
81 template<typename _ForwardIterator2>
82 _ForwardIterator2
83 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
84 {
85 return std::search(__first, __last,
86 std::get<0>(_M_m), std::get<1>(_M_m),
87 std::get<2>(_M_m));
88 }
89
90 private:
91 std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
92 };
93
94 template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
95 struct __boyer_moore_map_base
96 {
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) }
101 {
102 if (__patlen > 0)
103 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
104 _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
105 }
106
107 using __diff_type = _Tp;
108
109 __diff_type
110 _M_lookup(_Key __key, __diff_type __not_found) const
111 {
112 auto __iter = _M_bad_char.find(__key);
113 if (__iter == _M_bad_char.end())
114 return __not_found;
115 return __iter->second;
116 }
117
118 _Pred
119 _M_pred() const { return _M_bad_char.key_eq(); }
120
121 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
122 };
123
124 template<typename _Tp, size_t _Len, typename _Pred>
125 struct __boyer_moore_array_base
126 {
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) }
131 {
132 std::get<0>(_M_bad_char).fill(__patlen);
133 if (__patlen > 0)
134 for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
135 {
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;
140 }
141 }
142
143 using __diff_type = _Tp;
144
145 template<typename _Key>
146 __diff_type
147 _M_lookup(_Key __key, __diff_type __not_found) const
148 {
149 auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
150 if (__ukey >= _Len)
151 return __not_found;
152 return std::get<0>(_M_bad_char)[__ukey];
153 }
154
155 const _Pred&
156 _M_pred() const { return std::get<1>(_M_bad_char); }
157
158 std::tuple<std::array<_Tp, _Len>, _Pred> _M_bad_char;
159 };
160
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>>;
170
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>
176 {
177 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
178 using typename _Base::__diff_type;
179
180 public:
181 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
182 _Hash __hf = _Hash(),
183 _BinaryPredicate __pred = _BinaryPredicate());
184
185 template<typename _RandomAccessIterator2>
186 _RandomAccessIterator2
187 operator()(_RandomAccessIterator2 __first,
188 _RandomAccessIterator2 __last) const;
189
190 private:
191 bool
192 _M_is_prefix(_RAIter __word, __diff_type __len,
193 __diff_type __pos)
194 {
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]))
199 return false;
200 return true;
201 }
202
203 __diff_type
204 _M_suffix_length(_RAIter __word, __diff_type __len,
205 __diff_type __pos)
206 {
207 const auto& __pred = this->_M_pred();
208 __diff_type __i = 0;
209 while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
210 && __i < __pos)
211 {
212 ++__i;
213 }
214 return __i;
215 }
216
217 template<typename _Tp>
218 __diff_type
219 _M_bad_char_shift(_Tp __c) const
220 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
221
222 _RAIter _M_pat;
223 _RAIter _M_pat_end;
224 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
225 };
226
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>
232 {
233 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
234 using typename _Base::__diff_type;
235
236 public:
237 boyer_moore_horspool_searcher(_RAIter __pat,
238 _RAIter __pat_end,
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)
244 { }
245
246 template<typename _RandomAccessIterator2>
247 _RandomAccessIterator2
248 operator()(_RandomAccessIterator2 __first,
249 _RandomAccessIterator2 __last) const
250 {
251 const auto& __pred = this->_M_pred();
252 auto __patlen = _M_pat_end - _M_pat;
253 if (__patlen == 0)
254 return __first;
255 auto __len = __last - __first;
256 while (__len >= __patlen)
257 {
258 for (auto __scan = __patlen - 1;
259 __pred(__first[__scan], _M_pat[__scan]); --__scan)
260 if (__scan == 0)
261 return __first;
262 auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
263 __len -= __shift;
264 __first += __shift;
265 }
266 return __last;
267 }
268
269 private:
270 template<typename _Tp>
271 __diff_type
272 _M_bad_char_shift(_Tp __c) const
273 { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
274
275 _RAIter _M_pat;
276 _RAIter _M_pat_end;
277 };
278
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 }; }
287
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) }; }
297
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) }; }
308
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)
315 {
316 auto __patlen = __pat_end - __pat;
317 if (__patlen == 0)
318 return;
319 __diff_type __last_prefix = __patlen - 1;
320 for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
321 {
322 if (_M_is_prefix(__pat, __patlen, __p + 1))
323 __last_prefix = __p + 1;
324 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
325 }
326 for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
327 {
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;
332 }
333 }
334
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
341 {
342 auto __patlen = _M_pat_end - _M_pat;
343 if (__patlen == 0)
344 return __first;
345 const auto& __pred = this->_M_pred();
346 __diff_type __i = __patlen - 1;
347 auto __stringlen = __last - __first;
348 while (__i < __stringlen)
349 {
350 __diff_type __j = __patlen - 1;
351 while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
352 {
353 --__i;
354 --__j;
355 }
356 if (__j < 0)
357 return __first + __i + 1;
358 __i += std::max(_M_bad_char_shift(__first[__i]),
359 _M_good_suffix[__j]);
360 }
361 return __last;
362 }
363} // namespace fundamentals_v1
364
365inline namespace fundamentals_v2
366{
367#define __cpp_lib_experimental_not_fn 201406
368
369 /// [func.not_fn] Function template not_fn
370 template<typename _Fn>
371 inline auto
372 not_fn(_Fn&& __fn)
373 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
374 {
375 return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
376 }
377} // namespace fundamentals_v2
378} // namespace experimental
379
380_GLIBCXX_END_NAMESPACE_VERSION
381} // namespace std
382
383#endif // C++14
384
385#endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
Note: See TracBrowser for help on using the repository browser.