libstdc++
experimental/functional
Go to the documentation of this file.
1 // <experimental/functional> -*- C++ -*-
2 
3 // Copyright (C) 2014-2015 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 #include <experimental/lfts_config.h>
46 
47 namespace std _GLIBCXX_VISIBILITY(default)
48 {
49 namespace experimental
50 {
51 inline namespace fundamentals_v1
52 {
53 _GLIBCXX_BEGIN_NAMESPACE_VERSION
54 
55  // See C++14 ยง20.9.9, Function object binders
56 
57  /// Variable template for std::is_bind_expression
58  template<typename _Tp>
59  constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
60 
61  /// Variable template for std::is_placeholder
62  template<typename _Tp>
63  constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
64 
65 #define __cpp_lib_experimental_boyer_moore_searching 201411
66 
67  // Searchers
68 
69  template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
70  class default_searcher
71  {
72  public:
73  default_searcher(_ForwardIterator1 __pat_first,
74  _ForwardIterator1 __pat_last,
75  _BinaryPredicate __pred = _BinaryPredicate())
76  : _M_m(__pat_first, __pat_last, std::move(__pred))
77  { }
78 
79  template<typename _ForwardIterator2>
80  _ForwardIterator2
81  operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
82  {
83  return std::search(__first, __last,
84  std::get<0>(_M_m), std::get<1>(_M_m),
85  std::get<2>(_M_m));
86  }
87 
88  private:
89  std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
90  };
91 
92  template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
93  struct __boyer_moore_map_base
94  {
95  template<typename _RAIter>
96  __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
97  _Hash&& __hf, _Pred&& __pred)
98  : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
99  {
100  if (__patlen > 0)
101  for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
102  _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
103  }
104 
105  using __diff_type = _Tp;
106 
107  __diff_type
108  _M_lookup(_Key __key, __diff_type __not_found) const
109  {
110  auto __iter = _M_bad_char.find(__key);
111  if (__iter == _M_bad_char.end())
112  return __not_found;
113  return __iter->second;
114  }
115 
116  _Pred
117  _M_pred() const { return _M_bad_char.key_eq(); }
118 
119  _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
120  };
121 
122  template<typename _Tp, size_t _Len, typename _Pred>
123  struct __boyer_moore_array_base
124  {
125  template<typename _RAIter, typename _Unused>
126  __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
127  _Unused&&, _Pred&& __pred)
128  : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
129  {
130  std::get<0>(_M_bad_char).fill(__patlen);
131  if (__patlen > 0)
132  for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
133  {
134  auto __ch = __pat[__i];
135  using _UCh = std::make_unsigned_t<decltype(__ch)>;
136  auto __uch = static_cast<_UCh>(__ch);
137  std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
138  }
139  }
140 
141  using __diff_type = _Tp;
142 
143  template<typename _Key>
144  __diff_type
145  _M_lookup(_Key __key, __diff_type __not_found) const
146  {
147  auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
148  if (__ukey >= _Len)
149  return __not_found;
150  return std::get<0>(_M_bad_char)[__ukey];
151  }
152 
153  const _Pred&
154  _M_pred() const { return std::get<1>(_M_bad_char); }
155 
156  std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
157  };
158 
159  template<typename _Pred>
160  struct __is_std_equal_to : std::false_type { };
161 
162  template<>
163  struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
164 
165  // Use __boyer_moore_array_base when pattern consists of narrow characters
166  // and uses std::equal_to as the predicate.
167  template<typename _RAIter, typename _Hash, typename _Pred,
168  typename _Val = typename iterator_traits<_RAIter>::value_type,
169  typename _Diff = typename iterator_traits<_RAIter>::difference_type>
170  using __boyer_moore_base_t
171  = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
172  && __is_std_equal_to<_Pred>::value,
173  __boyer_moore_array_base<_Diff, 256, _Pred>,
174  __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
175 
176  template<typename _RAIter, typename _Hash
177  = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
178  typename _BinaryPredicate = std::equal_to<>>
179  class boyer_moore_searcher
180  : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
181  {
182  using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
183  using typename _Base::__diff_type;
184 
185  public:
186  boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
187  _Hash __hf = _Hash(),
188  _BinaryPredicate __pred = _BinaryPredicate());
189 
190  template<typename _RandomAccessIterator2>
191  _RandomAccessIterator2
192  operator()(_RandomAccessIterator2 __first,
193  _RandomAccessIterator2 __last) const;
194 
195  private:
196  bool
197  _M_is_prefix(_RAIter __word, __diff_type __len,
198  __diff_type __pos)
199  {
200  const auto& __pred = this->_M_pred();
201  __diff_type __suffixlen = __len - __pos;
202  for (__diff_type __i = 0; __i < __suffixlen; ++__i)
203  if (!__pred(__word[__i], __word[__pos + __i]))
204  return false;
205  return true;
206  }
207 
208  __diff_type
209  _M_suffix_length(_RAIter __word, __diff_type __len,
210  __diff_type __pos)
211  {
212  const auto& __pred = this->_M_pred();
213  __diff_type __i = 0;
214  while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
215  && __i < __pos)
216  {
217  ++__i;
218  }
219  return __i;
220  }
221 
222  template<typename _Tp>
223  __diff_type
224  _M_bad_char_shift(_Tp __c) const
225  { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
226 
227  _RAIter _M_pat;
228  _RAIter _M_pat_end;
229  _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
230  };
231 
232  template<typename _RAIter, typename _Hash
233  = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
234  typename _BinaryPredicate = std::equal_to<>>
235  class boyer_moore_horspool_searcher
236  : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
237  {
238  using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
239  using typename _Base::__diff_type;
240 
241  public:
242  boyer_moore_horspool_searcher(_RAIter __pat,
243  _RAIter __pat_end,
244  _Hash __hf = _Hash(),
245  _BinaryPredicate __pred
246  = _BinaryPredicate())
247  : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
248  _M_pat(__pat), _M_pat_end(__pat_end)
249  { }
250 
251  template<typename _RandomAccessIterator2>
252  _RandomAccessIterator2
253  operator()(_RandomAccessIterator2 __first,
254  _RandomAccessIterator2 __last) const
255  {
256  const auto& __pred = this->_M_pred();
257  auto __patlen = _M_pat_end - _M_pat;
258  if (__patlen == 0)
259  return __first;
260  auto __len = __last - __first;
261  while (__len >= __patlen)
262  {
263  for (auto __scan = __patlen - 1;
264  __pred(__first[__scan], _M_pat[__scan]); --__scan)
265  if (__scan == 0)
266  return __first;
267  auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
268  __len -= __shift;
269  __first += __shift;
270  }
271  return __last;
272  }
273 
274  private:
275  template<typename _Tp>
276  __diff_type
277  _M_bad_char_shift(_Tp __c) const
278  { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
279 
280  _RAIter _M_pat;
281  _RAIter _M_pat_end;
282  };
283 
284  /// Generator function for default_searcher
285  template<typename _ForwardIterator,
286  typename _BinaryPredicate = std::equal_to<>>
287  inline default_searcher<_ForwardIterator, _BinaryPredicate>
288  make_default_searcher(_ForwardIterator __pat_first,
289  _ForwardIterator __pat_last,
290  _BinaryPredicate __pred = _BinaryPredicate())
291  { return { __pat_first, __pat_last, __pred }; }
292 
293  /// Generator function for boyer_moore_searcher
294  template<typename _RAIter, typename _Hash
295  = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
296  typename _BinaryPredicate = equal_to<>>
297  inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
298  make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
299  _Hash __hf = _Hash(),
300  _BinaryPredicate __pred = _BinaryPredicate())
301  { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
302 
303  /// Generator function for boyer_moore_horspool_searcher
304  template<typename _RAIter, typename _Hash
305  = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
306  typename _BinaryPredicate = equal_to<>>
307  inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
308  make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
309  _Hash __hf = _Hash(),
310  _BinaryPredicate __pred
311  = _BinaryPredicate())
312  { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
313 
314  template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
315  boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
316  boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
317  _Hash __hf, _BinaryPredicate __pred)
318  : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
319  _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
320  {
321  auto __patlen = __pat_end - __pat;
322  if (__patlen == 0)
323  return;
324  __diff_type __last_prefix = __patlen - 1;
325  for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
326  {
327  if (_M_is_prefix(__pat, __patlen, __p + 1))
328  __last_prefix = __p + 1;
329  _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
330  }
331  for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
332  {
333  auto __slen = _M_suffix_length(__pat, __patlen, __p);
334  auto __pos = __patlen - 1 - __slen;
335  if (!__pred(__pat[__p - __slen], __pat[__pos]))
336  _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
337  }
338  }
339 
340  template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
341  template<typename _RandomAccessIterator2>
342  _RandomAccessIterator2
343  boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
344  operator()(_RandomAccessIterator2 __first,
345  _RandomAccessIterator2 __last) const
346  {
347  auto __patlen = _M_pat_end - _M_pat;
348  if (__patlen == 0)
349  return __first;
350  const auto& __pred = this->_M_pred();
351  __diff_type __i = __patlen - 1;
352  auto __stringlen = __last - __first;
353  while (__i < __stringlen)
354  {
355  __diff_type __j = __patlen - 1;
356  while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
357  {
358  --__i;
359  --__j;
360  }
361  if (__j < 0)
362  return __first + __i + 1;
363  __i += std::max(_M_bad_char_shift(__first[__i]),
364  _M_good_suffix[__j]);
365  }
366  return __last;
367  }
368 
369 _GLIBCXX_END_NAMESPACE_VERSION
370 } // namespace fundamentals_v1
371 
372 inline namespace fundamentals_v2
373 {
374 _GLIBCXX_BEGIN_NAMESPACE_VERSION
375 
376 #define __cpp_lib_experimental_not_fn 201406
377 
378  /// Generalized negator.
379  template<typename _Fn>
380  class _Not_fn
381  {
382  _Fn _M_fn;
383 
384  public:
385  template<typename _Fn2>
386  explicit
387  _Not_fn(_Fn2&& __fn, int) : _M_fn(std::forward<_Fn2>(__fn)) { }
388 
389  _Not_fn(const _Not_fn& __fn) = default;
390  _Not_fn(_Not_fn&& __fn) = default;
391  _Not_fn& operator=(const _Not_fn& __fn) = default;
392  _Not_fn& operator=(_Not_fn&& __fn) = default;
393  ~_Not_fn() = default;
394 
395  template<typename... _Args>
396  auto
397  operator()(_Args&&... __args)
398  noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
399  -> decltype(!_M_fn(std::forward<_Args>(__args)...))
400  { return !_M_fn(std::forward<_Args>(__args)...); }
401 
402  template<typename... _Args>
403  auto
404  operator()(_Args&&... __args) const
405  noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
406  -> decltype(!_M_fn(std::forward<_Args>(__args)...))
407  { return !_M_fn(std::forward<_Args>(__args)...); }
408 
409  template<typename... _Args>
410  auto
411  operator()(_Args&&... __args) volatile
412  noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
413  -> decltype(!_M_fn(std::forward<_Args>(__args)...))
414  { return !_M_fn(std::forward<_Args>(__args)...); }
415 
416  template<typename... _Args>
417  auto
418  operator()(_Args&&... __args) const volatile
419  noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
420  -> decltype(!_M_fn(std::forward<_Args>(__args)...))
421  { return !_M_fn(std::forward<_Args>(__args)...); }
422  };
423 
424  /// [func.not_fn] Function template not_fn
425  template<typename _Fn>
426  inline auto
427  not_fn(_Fn&& __fn)
428  noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
429  {
430  using __maybe_type = _Maybe_wrap_member_pointer<std::decay_t<_Fn>>;
431  return _Not_fn<typename __maybe_type::type>{std::forward<_Fn>(__fn), 0};
432  }
433 
434 _GLIBCXX_END_NAMESPACE_VERSION
435 } // namespace fundamentals_v2
436 } // namespace experimental
437 } // namespace std
438 
439 #endif // C++14
440 
441 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL