libstdc++
functional
Go to the documentation of this file.
00001 // <experimental/functional> -*- C++ -*-
00002 
00003 // Copyright (C) 2014-2016 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file experimental/functional
00026  *  This is a TS C++ Library header.
00027  */
00028 
00029 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
00030 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
00031 
00032 #pragma GCC system_header
00033 
00034 #if __cplusplus <= 201103L
00035 # include <bits/c++14_warning.h>
00036 #else
00037 
00038 #include <functional>
00039 #include <tuple>
00040 #include <iterator>
00041 #include <unordered_map>
00042 #include <vector>
00043 #include <array>
00044 #include <bits/stl_algo.h>
00045 #ifdef _GLIBCXX_PARALLEL
00046 # include <parallel/algorithm> // For std::__parallel::search
00047 #endif
00048 
00049 namespace std _GLIBCXX_VISIBILITY(default)
00050 {
00051 namespace experimental
00052 {
00053 inline namespace fundamentals_v1
00054 {
00055 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00056 
00057   // See C++14 ยง20.9.9, Function object binders
00058 
00059   /// Variable template for std::is_bind_expression
00060   template<typename _Tp>
00061     constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
00062 
00063   /// Variable template for std::is_placeholder
00064   template<typename _Tp>
00065     constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
00066 
00067 #define __cpp_lib_experimental_boyer_moore_searching 201411
00068 
00069   // Searchers
00070 
00071   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
00072     class default_searcher
00073     {
00074     public:
00075       default_searcher(_ForwardIterator1 __pat_first,
00076                        _ForwardIterator1 __pat_last,
00077                        _BinaryPredicate __pred = _BinaryPredicate())
00078       : _M_m(__pat_first, __pat_last, std::move(__pred))
00079       { }
00080 
00081       template<typename _ForwardIterator2>
00082         _ForwardIterator2
00083         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
00084         {
00085           return std::search(__first, __last,
00086                              std::get<0>(_M_m), std::get<1>(_M_m),
00087                              std::get<2>(_M_m));
00088         }
00089 
00090     private:
00091       std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
00092     };
00093 
00094   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
00095     struct __boyer_moore_map_base
00096     {
00097       template<typename _RAIter>
00098         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
00099                                _Hash&& __hf, _Pred&& __pred)
00100         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
00101         {
00102           if (__patlen > 0)
00103             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00104               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
00105         }
00106 
00107       using __diff_type = _Tp;
00108 
00109       __diff_type
00110       _M_lookup(_Key __key, __diff_type __not_found) const
00111       {
00112         auto __iter = _M_bad_char.find(__key);
00113         if (__iter == _M_bad_char.end())
00114           return __not_found;
00115         return __iter->second;
00116       }
00117 
00118       _Pred
00119       _M_pred() const { return _M_bad_char.key_eq(); }
00120 
00121       std::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
00122     };
00123 
00124   template<typename _Tp, size_t _Len, typename _Pred>
00125     struct __boyer_moore_array_base
00126     {
00127       template<typename _RAIter, typename _Unused>
00128         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
00129                                  _Unused&&, _Pred&& __pred)
00130         : _M_bad_char{ std::array<_Tp, _Len>{}, std::move(__pred) }
00131         {
00132           std::get<0>(_M_bad_char).fill(__patlen);
00133           if (__patlen > 0)
00134             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00135               {
00136                 auto __ch = __pat[__i];
00137                 using _UCh = std::make_unsigned_t<decltype(__ch)>;
00138                 auto __uch = static_cast<_UCh>(__ch);
00139                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
00140               }
00141         }
00142 
00143       using __diff_type = _Tp;
00144 
00145       template<typename _Key>
00146         __diff_type
00147         _M_lookup(_Key __key, __diff_type __not_found) const
00148         {
00149           auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
00150           if (__ukey >= _Len)
00151             return __not_found;
00152           return std::get<0>(_M_bad_char)[__ukey];
00153         }
00154 
00155       const _Pred&
00156       _M_pred() const { return std::get<1>(_M_bad_char); }
00157 
00158       std::tuple<std::array<_Tp, _Len>, _Pred> _M_bad_char;
00159     };
00160 
00161   template<typename _Pred>
00162     struct __is_std_equal_to : std::false_type { };
00163 
00164   template<>
00165     struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
00166 
00167   // Use __boyer_moore_array_base when pattern consists of narrow characters
00168   // and uses std::equal_to as the predicate.
00169   template<typename _RAIter, typename _Hash, typename _Pred,
00170            typename _Val = typename iterator_traits<_RAIter>::value_type,
00171            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
00172     using __boyer_moore_base_t
00173       = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
00174                            && __is_std_equal_to<_Pred>::value,
00175                            __boyer_moore_array_base<_Diff, 256, _Pred>,
00176                            __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
00177 
00178   template<typename _RAIter, typename _Hash
00179              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00180            typename _BinaryPredicate = std::equal_to<>>
00181     class boyer_moore_searcher
00182     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
00183     {
00184       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
00185       using typename _Base::__diff_type;
00186 
00187     public:
00188       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
00189                            _Hash __hf = _Hash(),
00190                            _BinaryPredicate __pred = _BinaryPredicate());
00191 
00192       template<typename _RandomAccessIterator2>
00193         _RandomAccessIterator2
00194         operator()(_RandomAccessIterator2 __first,
00195                    _RandomAccessIterator2 __last) const;
00196 
00197     private:
00198       bool
00199       _M_is_prefix(_RAIter __word, __diff_type __len,
00200                    __diff_type __pos)
00201       {
00202         const auto& __pred = this->_M_pred();
00203         __diff_type __suffixlen = __len - __pos;
00204         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
00205           if (!__pred(__word[__i], __word[__pos + __i]))
00206             return false;
00207         return true;
00208       }
00209 
00210       __diff_type
00211       _M_suffix_length(_RAIter __word, __diff_type __len,
00212                        __diff_type __pos)
00213       {
00214         const auto& __pred = this->_M_pred();
00215         __diff_type __i = 0;
00216         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
00217                && __i < __pos)
00218           {
00219             ++__i;
00220           }
00221         return __i;
00222       }
00223 
00224       template<typename _Tp>
00225         __diff_type
00226         _M_bad_char_shift(_Tp __c) const
00227         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
00228 
00229       _RAIter _M_pat;
00230       _RAIter _M_pat_end;
00231       std::vector<__diff_type> _M_good_suffix;
00232     };
00233 
00234   template<typename _RAIter, typename _Hash
00235              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00236            typename _BinaryPredicate = std::equal_to<>>
00237     class boyer_moore_horspool_searcher
00238     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
00239     {
00240       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
00241       using typename _Base::__diff_type;
00242 
00243     public:
00244       boyer_moore_horspool_searcher(_RAIter __pat,
00245                                     _RAIter __pat_end,
00246                                     _Hash __hf = _Hash(),
00247                                     _BinaryPredicate __pred
00248                                     = _BinaryPredicate())
00249       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
00250         _M_pat(__pat), _M_pat_end(__pat_end)
00251       { }
00252 
00253       template<typename _RandomAccessIterator2>
00254         _RandomAccessIterator2
00255         operator()(_RandomAccessIterator2 __first,
00256                    _RandomAccessIterator2 __last) const
00257         {
00258           const auto& __pred = this->_M_pred();
00259           auto __patlen = _M_pat_end - _M_pat;
00260           if (__patlen == 0)
00261             return __first;
00262           auto __len = __last - __first;
00263           while (__len >= __patlen)
00264             {
00265               for (auto __scan = __patlen - 1;
00266                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
00267                 if (__scan == 0)
00268                   return __first;
00269               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
00270               __len -= __shift;
00271               __first += __shift;
00272             }
00273           return __last;
00274         }
00275 
00276     private:
00277       template<typename _Tp>
00278         __diff_type
00279         _M_bad_char_shift(_Tp __c) const
00280         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
00281 
00282       _RAIter _M_pat;
00283       _RAIter _M_pat_end;
00284     };
00285 
00286   /// Generator function for default_searcher
00287   template<typename _ForwardIterator,
00288            typename _BinaryPredicate = std::equal_to<>>
00289     inline default_searcher<_ForwardIterator, _BinaryPredicate>
00290     make_default_searcher(_ForwardIterator __pat_first,
00291                           _ForwardIterator __pat_last,
00292                           _BinaryPredicate __pred = _BinaryPredicate())
00293     { return { __pat_first, __pat_last, __pred }; }
00294 
00295   /// Generator function for boyer_moore_searcher
00296   template<typename _RAIter, typename _Hash
00297              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00298            typename _BinaryPredicate = equal_to<>>
00299     inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
00300     make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
00301                               _Hash __hf = _Hash(),
00302                               _BinaryPredicate __pred = _BinaryPredicate())
00303     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
00304 
00305   /// Generator function for boyer_moore_horspool_searcher
00306   template<typename _RAIter, typename _Hash
00307              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00308            typename _BinaryPredicate = equal_to<>>
00309     inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
00310     make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
00311                                        _Hash __hf = _Hash(),
00312                                        _BinaryPredicate __pred
00313                                        = _BinaryPredicate())
00314     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
00315 
00316   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
00317     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
00318     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
00319                          _Hash __hf, _BinaryPredicate __pred)
00320     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
00321       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
00322     {
00323       auto __patlen = __pat_end - __pat;
00324       if (__patlen == 0)
00325         return;
00326       __diff_type __last_prefix = __patlen - 1;
00327       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
00328         {
00329           if (_M_is_prefix(__pat, __patlen, __p + 1))
00330             __last_prefix = __p + 1;
00331           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
00332         }
00333       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
00334         {
00335           auto __slen = _M_suffix_length(__pat, __patlen, __p);
00336           auto __pos = __patlen - 1 - __slen;
00337           if (!__pred(__pat[__p - __slen], __pat[__pos]))
00338             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
00339         }
00340     }
00341 
00342   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
00343   template<typename _RandomAccessIterator2>
00344     _RandomAccessIterator2
00345     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
00346     operator()(_RandomAccessIterator2 __first,
00347                _RandomAccessIterator2 __last) const
00348     {
00349       auto __patlen = _M_pat_end - _M_pat;
00350       if (__patlen == 0)
00351         return __first;
00352       const auto& __pred = this->_M_pred();
00353       __diff_type __i = __patlen - 1;
00354       auto __stringlen = __last - __first;
00355       while (__i < __stringlen)
00356         {
00357           __diff_type __j = __patlen - 1;
00358           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
00359             {
00360               --__i;
00361               --__j;
00362             }
00363           if (__j < 0)
00364             return __first + __i + 1;
00365           __i += std::max(_M_bad_char_shift(__first[__i]),
00366                           _M_good_suffix[__j]);
00367         }
00368       return __last;
00369     }
00370 
00371 _GLIBCXX_END_NAMESPACE_VERSION
00372 } // namespace fundamentals_v1
00373 
00374 inline namespace fundamentals_v2
00375 {
00376 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00377 
00378 #define __cpp_lib_experimental_not_fn 201406
00379 
00380   /// Generalized negator.
00381   template<typename _Fn>
00382     class _Not_fn
00383     {
00384       _Fn _M_fn;
00385 
00386     public:
00387       template<typename _Fn2>
00388         explicit
00389         _Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { }
00390 
00391       _Not_fn(const _Not_fn& __fn) = default;
00392       _Not_fn(_Not_fn&& __fn) = default;
00393       _Not_fn& operator=(const _Not_fn& __fn) = default;
00394       _Not_fn& operator=(_Not_fn&& __fn) = default;
00395       ~_Not_fn() = default;
00396 
00397       template<typename... _Args>
00398         auto
00399         operator()(_Args&&... __args)
00400         noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
00401         -> decltype(!_M_fn(std::forward<_Args>(__args)...))
00402         { return !_M_fn(std::forward<_Args>(__args)...); }
00403 
00404       template<typename... _Args>
00405         auto
00406         operator()(_Args&&... __args) const
00407         noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
00408         -> decltype(!_M_fn(std::forward<_Args>(__args)...))
00409         { return !_M_fn(std::forward<_Args>(__args)...); }
00410 
00411       template<typename... _Args>
00412         auto
00413         operator()(_Args&&... __args) volatile
00414         noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
00415         -> decltype(!_M_fn(std::forward<_Args>(__args)...))
00416         { return !_M_fn(std::forward<_Args>(__args)...); }
00417 
00418       template<typename... _Args>
00419         auto
00420         operator()(_Args&&... __args) const volatile
00421         noexcept(noexcept(!_M_fn(std::forward<_Args>(__args)...)))
00422         -> decltype(!_M_fn(std::forward<_Args>(__args)...))
00423         { return !_M_fn(std::forward<_Args>(__args)...); }
00424     };
00425 
00426   /// [func.not_fn] Function template not_fn
00427   template<typename _Fn>
00428     inline auto
00429     not_fn(_Fn&& __fn)
00430     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
00431     {
00432       using __maybe_type = _Maybe_wrap_member_pointer<std::decay_t<_Fn>>;
00433       return _Not_fn<typename __maybe_type::type>{std::forward<_Fn>(__fn)};
00434     }
00435 
00436 _GLIBCXX_END_NAMESPACE_VERSION
00437 } // namespace fundamentals_v2
00438 } // namespace experimental
00439 } // namespace std
00440 
00441 #endif // C++14
00442 
00443 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL