libstdc++
experimental/functional
Go to the documentation of this file.
1 // <experimental/functional> -*- C++ -*-
2 
3 // Copyright (C) 2014-2017 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  */
28 
29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
31 
32 #pragma GCC system_header
33 
34 #if __cplusplus <= 201103L
35 # include <bits/c++14_warning.h>
36 #else
37 
38 #include <functional>
39 #include <tuple>
40 #include <iterator>
41 #include <unordered_map>
42 #include <vector>
43 #include <array>
44 #include <bits/stl_algo.h>
45 #ifdef _GLIBCXX_PARALLEL
46 # include <parallel/algorithm> // For std::__parallel::search
47 #endif
49 
50 namespace std _GLIBCXX_VISIBILITY(default)
51 {
52 namespace experimental
53 {
54 inline namespace fundamentals_v1
55 {
56 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57 
58  // See C++14 ยง20.9.9, Function object binders
59 
60  /// Variable template for std::is_bind_expression
61  template<typename _Tp>
63 
64  /// Variable template for std::is_placeholder
65  template<typename _Tp>
67 
68 #define __cpp_lib_experimental_boyer_moore_searching 201411
69 
70  // Searchers
71 
72  template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
73  class default_searcher
74  {
75  public:
76  default_searcher(_ForwardIterator1 __pat_first,
77  _ForwardIterator1 __pat_last,
78  _BinaryPredicate __pred = _BinaryPredicate())
79  : _M_m(__pat_first, __pat_last, std::move(__pred))
80  { }
81 
82  template<typename _ForwardIterator2>
83  _ForwardIterator2
84  operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
85  {
86  return std::search(__first, __last,
87  std::get<0>(_M_m), std::get<1>(_M_m),
88  std::get<2>(_M_m));
89  }
90 
91  private:
93  };
94 
95  template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
96  struct __boyer_moore_map_base
97  {
98  template<typename _RAIter>
99  __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
100  _Hash&& __hf, _Pred&& __pred)
101  : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
102  {
103  if (__patlen > 0)
104  for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
105  _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
106  }
107 
108  using __diff_type = _Tp;
109 
110  __diff_type
111  _M_lookup(_Key __key, __diff_type __not_found) const
112  {
113  auto __iter = _M_bad_char.find(__key);
114  if (__iter == _M_bad_char.end())
115  return __not_found;
116  return __iter->second;
117  }
118 
119  _Pred
120  _M_pred() const { return _M_bad_char.key_eq(); }
121 
122  _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
123  };
124 
125  template<typename _Tp, size_t _Len, typename _Pred>
126  struct __boyer_moore_array_base
127  {
128  template<typename _RAIter, typename _Unused>
129  __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
130  _Unused&&, _Pred&& __pred)
131  : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
132  {
133  std::get<0>(_M_bad_char).fill(__patlen);
134  if (__patlen > 0)
135  for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
136  {
137  auto __ch = __pat[__i];
138  using _UCh = std::make_unsigned_t<decltype(__ch)>;
139  auto __uch = static_cast<_UCh>(__ch);
140  std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
141  }
142  }
143 
144  using __diff_type = _Tp;
145 
146  template<typename _Key>
147  __diff_type
148  _M_lookup(_Key __key, __diff_type __not_found) const
149  {
150  auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
151  if (__ukey >= _Len)
152  return __not_found;
153  return std::get<0>(_M_bad_char)[__ukey];
154  }
155 
156  const _Pred&
157  _M_pred() const { return std::get<1>(_M_bad_char); }
158 
160  };
161 
162  template<typename _Pred>
163  struct __is_std_equal_to : std::false_type { };
164 
165  template<>
166  struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
167 
168  // Use __boyer_moore_array_base when pattern consists of narrow characters
169  // and uses std::equal_to as the predicate.
170  template<typename _RAIter, typename _Hash, typename _Pred,
171  typename _Val = typename iterator_traits<_RAIter>::value_type,
172  typename _Diff = typename iterator_traits<_RAIter>::difference_type>
173  using __boyer_moore_base_t
174  = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
175  && __is_std_equal_to<_Pred>::value,
176  __boyer_moore_array_base<_Diff, 256, _Pred>,
177  __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
178 
179  template<typename _RAIter, typename _Hash
181  typename _BinaryPredicate = std::equal_to<>>
182  class boyer_moore_searcher
183  : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
184  {
185  using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
186  using typename _Base::__diff_type;
187 
188  public:
189  boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
190  _Hash __hf = _Hash(),
191  _BinaryPredicate __pred = _BinaryPredicate());
192 
193  template<typename _RandomAccessIterator2>
194  _RandomAccessIterator2
195  operator()(_RandomAccessIterator2 __first,
196  _RandomAccessIterator2 __last) const;
197 
198  private:
199  bool
200  _M_is_prefix(_RAIter __word, __diff_type __len,
201  __diff_type __pos)
202  {
203  const auto& __pred = this->_M_pred();
204  __diff_type __suffixlen = __len - __pos;
205  for (__diff_type __i = 0; __i < __suffixlen; ++__i)
206  if (!__pred(__word[__i], __word[__pos + __i]))
207  return false;
208  return true;
209  }
210 
211  __diff_type
212  _M_suffix_length(_RAIter __word, __diff_type __len,
213  __diff_type __pos)
214  {
215  const auto& __pred = this->_M_pred();
216  __diff_type __i = 0;
217  while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
218  && __i < __pos)
219  {
220  ++__i;
221  }
222  return __i;
223  }
224 
225  template<typename _Tp>
226  __diff_type
227  _M_bad_char_shift(_Tp __c) const
228  { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
229 
230  _RAIter _M_pat;
231  _RAIter _M_pat_end;
232  _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
233  };
234 
235  template<typename _RAIter, typename _Hash
237  typename _BinaryPredicate = std::equal_to<>>
238  class boyer_moore_horspool_searcher
239  : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
240  {
241  using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
242  using typename _Base::__diff_type;
243 
244  public:
245  boyer_moore_horspool_searcher(_RAIter __pat,
246  _RAIter __pat_end,
247  _Hash __hf = _Hash(),
248  _BinaryPredicate __pred
249  = _BinaryPredicate())
250  : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
251  _M_pat(__pat), _M_pat_end(__pat_end)
252  { }
253 
254  template<typename _RandomAccessIterator2>
255  _RandomAccessIterator2
256  operator()(_RandomAccessIterator2 __first,
257  _RandomAccessIterator2 __last) const
258  {
259  const auto& __pred = this->_M_pred();
260  auto __patlen = _M_pat_end - _M_pat;
261  if (__patlen == 0)
262  return __first;
263  auto __len = __last - __first;
264  while (__len >= __patlen)
265  {
266  for (auto __scan = __patlen - 1;
267  __pred(__first[__scan], _M_pat[__scan]); --__scan)
268  if (__scan == 0)
269  return __first;
270  auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
271  __len -= __shift;
272  __first += __shift;
273  }
274  return __last;
275  }
276 
277  private:
278  template<typename _Tp>
279  __diff_type
280  _M_bad_char_shift(_Tp __c) const
281  { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
282 
283  _RAIter _M_pat;
284  _RAIter _M_pat_end;
285  };
286 
287  /// Generator function for default_searcher
288  template<typename _ForwardIterator,
289  typename _BinaryPredicate = std::equal_to<>>
290  inline default_searcher<_ForwardIterator, _BinaryPredicate>
291  make_default_searcher(_ForwardIterator __pat_first,
292  _ForwardIterator __pat_last,
293  _BinaryPredicate __pred = _BinaryPredicate())
294  { return { __pat_first, __pat_last, __pred }; }
295 
296  /// Generator function for boyer_moore_searcher
297  template<typename _RAIter, typename _Hash
299  typename _BinaryPredicate = equal_to<>>
300  inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
301  make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
302  _Hash __hf = _Hash(),
303  _BinaryPredicate __pred = _BinaryPredicate())
304  { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
305 
306  /// Generator function for boyer_moore_horspool_searcher
307  template<typename _RAIter, typename _Hash
309  typename _BinaryPredicate = equal_to<>>
310  inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
311  make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
312  _Hash __hf = _Hash(),
313  _BinaryPredicate __pred
314  = _BinaryPredicate())
315  { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
316 
317  template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
318  boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
319  boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
320  _Hash __hf, _BinaryPredicate __pred)
321  : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
322  _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
323  {
324  auto __patlen = __pat_end - __pat;
325  if (__patlen == 0)
326  return;
327  __diff_type __last_prefix = __patlen - 1;
328  for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
329  {
330  if (_M_is_prefix(__pat, __patlen, __p + 1))
331  __last_prefix = __p + 1;
332  _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
333  }
334  for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
335  {
336  auto __slen = _M_suffix_length(__pat, __patlen, __p);
337  auto __pos = __patlen - 1 - __slen;
338  if (!__pred(__pat[__p - __slen], __pat[__pos]))
339  _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
340  }
341  }
342 
343  template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
344  template<typename _RandomAccessIterator2>
345  _RandomAccessIterator2
346  boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
347  operator()(_RandomAccessIterator2 __first,
348  _RandomAccessIterator2 __last) const
349  {
350  auto __patlen = _M_pat_end - _M_pat;
351  if (__patlen == 0)
352  return __first;
353  const auto& __pred = this->_M_pred();
354  __diff_type __i = __patlen - 1;
355  auto __stringlen = __last - __first;
356  while (__i < __stringlen)
357  {
358  __diff_type __j = __patlen - 1;
359  while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
360  {
361  --__i;
362  --__j;
363  }
364  if (__j < 0)
365  return __first + __i + 1;
366  __i += std::max(_M_bad_char_shift(__first[__i]),
367  _M_good_suffix[__j]);
368  }
369  return __last;
370  }
371 
372 _GLIBCXX_END_NAMESPACE_VERSION
373 } // namespace fundamentals_v1
374 
375 inline namespace fundamentals_v2
376 {
377 _GLIBCXX_BEGIN_NAMESPACE_VERSION
378 
379 #define __cpp_lib_experimental_not_fn 201406
380 
381  /// [func.not_fn] Function template not_fn
382  template<typename _Fn>
383  inline auto
384  not_fn(_Fn&& __fn)
385  noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
386  {
387  return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
388  }
389 
390 _GLIBCXX_END_NAMESPACE_VERSION
391 } // namespace fundamentals_v2
392 } // namespace experimental
393 } // namespace std
394 
395 #endif // C++14
396 
397 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
Generalized negator.
Definition: functional:909
Determines if the given type _Tp is a placeholder in a bind() expression and, if so, which placeholder it is.
Definition: functional:246
integral_constant
Definition: type_traits:69
ISO C++ entities toplevel namespace is std.
auto not_fn(_Fn &&__fn) noexcept(std::is_nothrow_constructible< std::decay_t< _Fn >, _Fn &&>::value)
[func.not_fn] Function template not_fn
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:219
boyer_moore_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())
Generator function for boyer_moore_searcher.
constexpr bool is_bind_expression_v
Variable template for std::is_bind_expression.
constexpr int is_placeholder_v
Variable template for std::is_placeholder.
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
Definition: stl_algo.h:4179
default_searcher< _ForwardIterator, _BinaryPredicate > make_default_searcher(_ForwardIterator __pat_first, _ForwardIterator __pat_last, _BinaryPredicate __pred=_BinaryPredicate())
Generator function for default_searcher.
Determines if the given type _Tp is a function object that should be treated as a subexpression when ...
Definition: functional:235
One of the comparison functors.
Definition: stl_function.h:331
Primary class template hash.
Definition: system_error:142
boyer_moore_horspool_searcher< _RAIter, _Hash, _BinaryPredicate > make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, _Hash __hf=_Hash(), _BinaryPredicate __pred=_BinaryPredicate())
Generator function for boyer_moore_horspool_searcher.