1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
|
// <experimental/functional> -*- C++ -*-
// Copyright (C) 2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file experimental/functional
* This is a TS C++ Library header.
*/
#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
#pragma GCC system_header
#if __cplusplus <= 201103L
# include <bits/c++14_warning.h>
#else
#include <functional>
#include <tuple>
#include <iterator>
#include <unordered_map>
#include <vector>
#include <array>
#include <bits/stl_algo.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
namespace experimental
{
inline namespace fundamentals_v1
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
// See C++14 ยง20.9.9, Function object binders
/// Variable template for std::is_bind_expression
template<typename _Tp>
constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
/// Variable template for std::is_placeholder
template<typename _Tp>
constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
#define __cpp_lib_experimental_boyer_moore_searching 201411
// Searchers
template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
class default_searcher
{
public:
default_searcher(_ForwardIterator1 __pat_first,
_ForwardIterator1 __pat_last,
_BinaryPredicate __pred = _BinaryPredicate())
: _M_m(__pat_first, __pat_last, std::move(__pred))
{ }
template<typename _ForwardIterator2>
_ForwardIterator2
operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
{
return std::search(__first, __last,
std::get<0>(_M_m), std::get<1>(_M_m),
std::get<2>(_M_m));
}
private:
std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
};
template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
struct __boyer_moore_map_base
{
template<typename _RAIter>
__boyer_moore_map_base(_RAIter __pat, size_t __patlen,
_Hash&& __hf, _Pred&& __pred)
: _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
{
if (__patlen > 0)
for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
_M_bad_char[__pat[__i]] = __patlen - 1 - __i;
}
using __diff_type = _Tp;
__diff_type
_M_lookup(_Key __key, __diff_type __not_found) const
{
auto __iter = _M_bad_char.find(__key);
if (__iter == _M_bad_char.end())
return __not_found;
return __iter->second;
}
_Pred
_M_pred() const { return _M_bad_char.key_eq(); }
std::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
};
template<typename _Tp, size_t _Len, typename _Pred>
struct __boyer_moore_array_base
{
template<typename _RAIter, typename _Unused>
__boyer_moore_array_base(_RAIter __pat, size_t __patlen,
_Unused&&, _Pred&& __pred)
: _M_bad_char{ {}, std::move(__pred) }
{
std::get<0>(_M_bad_char).fill(__patlen);
if (__patlen > 0)
for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
{
auto __ch = __pat[__i];
using _UCh = std::make_unsigned_t<decltype(__ch)>;
auto __uch = static_cast<_UCh>(__ch);
std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
}
}
using __diff_type = _Tp;
template<typename _Key>
__diff_type
_M_lookup(_Key __key, __diff_type __not_found) const
{
auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
if (__ukey >= _Len)
return __not_found;
return std::get<0>(_M_bad_char)[__ukey];
}
const _Pred&
_M_pred() const { return std::get<1>(_M_bad_char); }
std::tuple<std::array<_Tp, _Len>, _Pred> _M_bad_char;
};
template<typename _Pred>
struct __is_std_equal_to : std::false_type { };
template<>
struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
// Use __boyer_moore_array_base when pattern consists of narrow characters
// and uses std::equal_to as the predicate.
template<typename _RAIter, typename _Hash, typename _Pred,
typename _Val = typename iterator_traits<_RAIter>::value_type,
typename _Diff = typename iterator_traits<_RAIter>::difference_type>
using __boyer_moore_base_t
= std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
&& __is_std_equal_to<_Pred>::value,
__boyer_moore_array_base<_Diff, 256, _Pred>,
__boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
template<typename _RAIter, typename _Hash
= std::hash<typename std::iterator_traits<_RAIter>::value_type>,
typename _BinaryPredicate = std::equal_to<>>
class boyer_moore_searcher
: __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
{
using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
using typename _Base::__diff_type;
public:
boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
_Hash __hf = _Hash(),
_BinaryPredicate __pred = _BinaryPredicate());
template<typename _RandomAccessIterator2>
_RandomAccessIterator2
operator()(_RandomAccessIterator2 __first,
_RandomAccessIterator2 __last) const;
private:
bool
_M_is_prefix(_RAIter __word, __diff_type __len,
__diff_type __pos)
{
const auto& __pred = this->_M_pred();
__diff_type __suffixlen = __len - __pos;
for (__diff_type __i = 0; __i < __suffixlen; ++__i)
if (!__pred(__word[__i], __word[__pos + __i]))
return false;
return true;
}
__diff_type
_M_suffix_length(_RAIter __word, __diff_type __len,
__diff_type __pos)
{
const auto& __pred = this->_M_pred();
__diff_type __i = 0;
while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
&& __i < __pos)
{
++__i;
}
return __i;
}
template<typename _Tp>
__diff_type
_M_bad_char_shift(_Tp __c) const
{ return this->_M_lookup(__c, _M_pat_end - _M_pat); }
_RAIter _M_pat;
_RAIter _M_pat_end;
std::vector<__diff_type> _M_good_suffix;
};
template<typename _RAIter, typename _Hash
= std::hash<typename std::iterator_traits<_RAIter>::value_type>,
typename _BinaryPredicate = std::equal_to<>>
class boyer_moore_horspool_searcher
: __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
{
using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
using typename _Base::__diff_type;
public:
boyer_moore_horspool_searcher(_RAIter __pat,
_RAIter __pat_end,
_Hash __hf = _Hash(),
_BinaryPredicate __pred
= _BinaryPredicate())
: _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
_M_pat(__pat), _M_pat_end(__pat_end)
{ }
template<typename _RandomAccessIterator2>
_RandomAccessIterator2
operator()(_RandomAccessIterator2 __first,
_RandomAccessIterator2 __last) const
{
const auto& __pred = this->_M_pred();
auto __patlen = _M_pat_end - _M_pat;
if (__patlen == 0)
return __first;
auto __len = __last - __first;
while (__len >= __patlen)
{
for (auto __scan = __patlen - 1;
__pred(__first[__scan], _M_pat[__scan]); --__scan)
if (__scan == 0)
return __first;
auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
__len -= __shift;
__first += __shift;
}
return __last;
}
private:
template<typename _Tp>
__diff_type
_M_bad_char_shift(_Tp __c) const
{ return this->_M_lookup(__c, _M_pat_end - _M_pat); }
_RAIter _M_pat;
_RAIter _M_pat_end;
};
/// Generator function for default_searcher
template<typename _ForwardIterator,
typename _BinaryPredicate = std::equal_to<>>
inline default_searcher<_ForwardIterator, _BinaryPredicate>
make_default_searcher(_ForwardIterator __pat_first,
_ForwardIterator __pat_last,
_BinaryPredicate __pred = _BinaryPredicate())
{ return { __pat_first, __pat_last, __pred }; }
/// Generator function for boyer_moore_searcher
template<typename _RAIter, typename _Hash
= std::hash<typename std::iterator_traits<_RAIter>::value_type>,
typename _BinaryPredicate = equal_to<>>
inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
_Hash __hf = _Hash(),
_BinaryPredicate __pred = _BinaryPredicate())
{ return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
/// Generator function for boyer_moore_horspool_searcher
template<typename _RAIter, typename _Hash
= std::hash<typename std::iterator_traits<_RAIter>::value_type>,
typename _BinaryPredicate = equal_to<>>
inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
_Hash __hf = _Hash(),
_BinaryPredicate __pred
= _BinaryPredicate())
{ return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
_Hash __hf, _BinaryPredicate __pred)
: _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
_M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
{
auto __patlen = __pat_end - __pat;
if (__patlen == 0)
return;
__diff_type __last_prefix = __patlen - 1;
for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
{
if (_M_is_prefix(__pat, __patlen, __p + 1))
__last_prefix = __p + 1;
_M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
}
for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
{
auto __slen = _M_suffix_length(__pat, __patlen, __p);
auto __pos = __patlen - 1 - __slen;
if (!__pred(__pat[__p - __slen], __pat[__pos]))
_M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
}
}
template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
template<typename _RandomAccessIterator2>
_RandomAccessIterator2
boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
operator()(_RandomAccessIterator2 __first,
_RandomAccessIterator2 __last) const
{
auto __patlen = _M_pat_end - _M_pat;
if (__patlen == 0)
return __first;
const auto& __pred = this->_M_pred();
__diff_type __i = __patlen - 1;
auto __stringlen = __last - __first;
while (__i < __stringlen)
{
__diff_type __j = __patlen - 1;
while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
{
--__i;
--__j;
}
if (__j < 0)
return __first + __i + 1;
__i += std::max(_M_bad_char_shift(__first[__i]),
_M_good_suffix[__j]);
}
return __last;
}
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace fundamentals_v1
inline namespace fundamentals_v2
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
#define __cpp_lib_experimental_not_fn 201406
/// Generalized negator.
template<typename _Fn>
struct _Not_fn
{
template<typename _Fn2>
explicit
_Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { }
_Not_fn(const _Not_fn& __fn) = default;
_Not_fn(_Not_fn&& __fn) = default;
_Not_fn& operator=(const _Not_fn& __fn) = default;
_Not_fn& operator=(_Not_fn&& __fn) = default;
~_Not_fn() = default;
template<typename... _Args>
decltype(auto)
operator()(_Args&&... __args)
{ return !_M_fn(std::forward<_Args>(__args)...); }
template<typename... _Args>
decltype(auto)
operator()(_Args&&... __args) const
{ return !_M_fn(std::forward<_Args>(__args)...); }
template<typename... _Args>
decltype(auto)
operator()(_Args&&... __args) volatile
{ return !_M_fn(std::forward<_Args>(__args)...); }
template<typename... _Args>
decltype(auto)
operator()(_Args&&... __args) const volatile
{ return !_M_fn(std::forward<_Args>(__args)...); }
private:
_Fn _M_fn;
};
/// [func.not_fn] Function template not_fn
template <class _Fn>
inline auto
not_fn(_Fn&& __fn)
{ return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn)}; }
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace fundamentals_v2
} // namespace experimental
} // namespace std
#endif // C++14
#endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
|