libstdc++
functional
Go to the documentation of this file.
00001 // <experimental/functional> -*- C++ -*-
00002 
00003 // Copyright (C) 2014-2019 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 >= 201402L
00035 
00036 #include <functional>
00037 #include <tuple>
00038 #include <iterator>
00039 #include <unordered_map>
00040 #include <vector>
00041 #include <array>
00042 #include <bits/stl_algo.h>
00043 #ifdef _GLIBCXX_PARALLEL
00044 # include <parallel/algorithm> // For std::__parallel::search
00045 #endif
00046 #include <experimental/bits/lfts_config.h>
00047 
00048 namespace std _GLIBCXX_VISIBILITY(default)
00049 {
00050 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00051 
00052 namespace experimental
00053 {
00054 inline namespace fundamentals_v1
00055 {
00056   // See C++14 20.9.9, Function object binders
00057 
00058   /// Variable template for std::is_bind_expression
00059   template<typename _Tp>
00060     constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
00061 
00062   /// Variable template for std::is_placeholder
00063   template<typename _Tp>
00064     constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
00065 
00066 #define __cpp_lib_experimental_boyer_moore_searching 201411
00067 
00068   // Searchers
00069 
00070   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
00071     class default_searcher
00072     {
00073     public:
00074       default_searcher(_ForwardIterator1 __pat_first,
00075                        _ForwardIterator1 __pat_last,
00076                        _BinaryPredicate __pred = _BinaryPredicate())
00077       : _M_m(__pat_first, __pat_last, std::move(__pred))
00078       { }
00079 
00080       template<typename _ForwardIterator2>
00081         _ForwardIterator2
00082         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
00083         {
00084           return std::search(__first, __last,
00085                              std::get<0>(_M_m), std::get<1>(_M_m),
00086                              std::get<2>(_M_m));
00087         }
00088 
00089     private:
00090       std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
00091     };
00092 
00093   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
00094     struct __boyer_moore_map_base
00095     {
00096       template<typename _RAIter>
00097         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
00098                                _Hash&& __hf, _Pred&& __pred)
00099         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
00100         {
00101           if (__patlen > 0)
00102             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00103               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
00104         }
00105 
00106       using __diff_type = _Tp;
00107 
00108       __diff_type
00109       _M_lookup(_Key __key, __diff_type __not_found) const
00110       {
00111         auto __iter = _M_bad_char.find(__key);
00112         if (__iter == _M_bad_char.end())
00113           return __not_found;
00114         return __iter->second;
00115       }
00116 
00117       _Pred
00118       _M_pred() const { return _M_bad_char.key_eq(); }
00119 
00120       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
00121     };
00122 
00123   template<typename _Tp, size_t _Len, typename _Pred>
00124     struct __boyer_moore_array_base
00125     {
00126       template<typename _RAIter, typename _Unused>
00127         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
00128                                  _Unused&&, _Pred&& __pred)
00129         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
00130         {
00131           std::get<0>(_M_bad_char).fill(__patlen);
00132           if (__patlen > 0)
00133             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00134               {
00135                 auto __ch = __pat[__i];
00136                 using _UCh = std::make_unsigned_t<decltype(__ch)>;
00137                 auto __uch = static_cast<_UCh>(__ch);
00138                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
00139               }
00140         }
00141 
00142       using __diff_type = _Tp;
00143 
00144       template<typename _Key>
00145         __diff_type
00146         _M_lookup(_Key __key, __diff_type __not_found) const
00147         {
00148           auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
00149           if (__ukey >= _Len)
00150             return __not_found;
00151           return std::get<0>(_M_bad_char)[__ukey];
00152         }
00153 
00154       const _Pred&
00155       _M_pred() const { return std::get<1>(_M_bad_char); }
00156 
00157       std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
00158     };
00159 
00160   // Use __boyer_moore_array_base when pattern consists of narrow characters
00161   // (or std::byte) and uses std::equal_to as the predicate.
00162   template<typename _RAIter, typename _Hash, typename _Pred,
00163            typename _Val = typename iterator_traits<_RAIter>::value_type,
00164            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
00165     using __boyer_moore_base_t
00166       = std::conditional_t<std::__is_byte_like<_Val, _Pred>::value,
00167                            __boyer_moore_array_base<_Diff, 256, _Pred>,
00168                            __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
00169 
00170   template<typename _RAIter, typename _Hash
00171              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00172            typename _BinaryPredicate = std::equal_to<>>
00173     class boyer_moore_searcher
00174     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
00175     {
00176       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
00177       using typename _Base::__diff_type;
00178 
00179     public:
00180       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
00181                            _Hash __hf = _Hash(),
00182                            _BinaryPredicate __pred = _BinaryPredicate());
00183 
00184       template<typename _RandomAccessIterator2>
00185         _RandomAccessIterator2
00186         operator()(_RandomAccessIterator2 __first,
00187                    _RandomAccessIterator2 __last) const;
00188 
00189     private:
00190       bool
00191       _M_is_prefix(_RAIter __word, __diff_type __len,
00192                    __diff_type __pos)
00193       {
00194         const auto& __pred = this->_M_pred();
00195         __diff_type __suffixlen = __len - __pos;
00196         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
00197           if (!__pred(__word[__i], __word[__pos + __i]))
00198             return false;
00199         return true;
00200       }
00201 
00202       __diff_type
00203       _M_suffix_length(_RAIter __word, __diff_type __len,
00204                        __diff_type __pos)
00205       {
00206         const auto& __pred = this->_M_pred();
00207         __diff_type __i = 0;
00208         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
00209                && __i < __pos)
00210           {
00211             ++__i;
00212           }
00213         return __i;
00214       }
00215 
00216       template<typename _Tp>
00217         __diff_type
00218         _M_bad_char_shift(_Tp __c) const
00219         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
00220 
00221       _RAIter _M_pat;
00222       _RAIter _M_pat_end;
00223       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
00224     };
00225 
00226   template<typename _RAIter, typename _Hash
00227              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00228            typename _BinaryPredicate = std::equal_to<>>
00229     class boyer_moore_horspool_searcher
00230     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
00231     {
00232       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
00233       using typename _Base::__diff_type;
00234 
00235     public:
00236       boyer_moore_horspool_searcher(_RAIter __pat,
00237                                     _RAIter __pat_end,
00238                                     _Hash __hf = _Hash(),
00239                                     _BinaryPredicate __pred
00240                                     = _BinaryPredicate())
00241       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
00242         _M_pat(__pat), _M_pat_end(__pat_end)
00243       { }
00244 
00245       template<typename _RandomAccessIterator2>
00246         _RandomAccessIterator2
00247         operator()(_RandomAccessIterator2 __first,
00248                    _RandomAccessIterator2 __last) const
00249         {
00250           const auto& __pred = this->_M_pred();
00251           auto __patlen = _M_pat_end - _M_pat;
00252           if (__patlen == 0)
00253             return __first;
00254           auto __len = __last - __first;
00255           while (__len >= __patlen)
00256             {
00257               for (auto __scan = __patlen - 1;
00258                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
00259                 if (__scan == 0)
00260                   return __first;
00261               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
00262               __len -= __shift;
00263               __first += __shift;
00264             }
00265           return __last;
00266         }
00267 
00268     private:
00269       template<typename _Tp>
00270         __diff_type
00271         _M_bad_char_shift(_Tp __c) const
00272         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
00273 
00274       _RAIter _M_pat;
00275       _RAIter _M_pat_end;
00276     };
00277 
00278   /// Generator function for default_searcher
00279   template<typename _ForwardIterator,
00280            typename _BinaryPredicate = std::equal_to<>>
00281     inline default_searcher<_ForwardIterator, _BinaryPredicate>
00282     make_default_searcher(_ForwardIterator __pat_first,
00283                           _ForwardIterator __pat_last,
00284                           _BinaryPredicate __pred = _BinaryPredicate())
00285     { return { __pat_first, __pat_last, __pred }; }
00286 
00287   /// Generator function for boyer_moore_searcher
00288   template<typename _RAIter, typename _Hash
00289              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00290            typename _BinaryPredicate = equal_to<>>
00291     inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
00292     make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
00293                               _Hash __hf = _Hash(),
00294                               _BinaryPredicate __pred = _BinaryPredicate())
00295     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
00296 
00297   /// Generator function for boyer_moore_horspool_searcher
00298   template<typename _RAIter, typename _Hash
00299              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
00300            typename _BinaryPredicate = equal_to<>>
00301     inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
00302     make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
00303                                        _Hash __hf = _Hash(),
00304                                        _BinaryPredicate __pred
00305                                        = _BinaryPredicate())
00306     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
00307 
00308   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
00309     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
00310     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
00311                          _Hash __hf, _BinaryPredicate __pred)
00312     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
00313       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
00314     {
00315       auto __patlen = __pat_end - __pat;
00316       if (__patlen == 0)
00317         return;
00318       __diff_type __last_prefix = __patlen - 1;
00319       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
00320         {
00321           if (_M_is_prefix(__pat, __patlen, __p + 1))
00322             __last_prefix = __p + 1;
00323           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
00324         }
00325       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
00326         {
00327           auto __slen = _M_suffix_length(__pat, __patlen, __p);
00328           auto __pos = __patlen - 1 - __slen;
00329           if (!__pred(__pat[__p - __slen], __pat[__pos]))
00330             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
00331         }
00332     }
00333 
00334   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
00335   template<typename _RandomAccessIterator2>
00336     _RandomAccessIterator2
00337     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
00338     operator()(_RandomAccessIterator2 __first,
00339                _RandomAccessIterator2 __last) const
00340     {
00341       auto __patlen = _M_pat_end - _M_pat;
00342       if (__patlen == 0)
00343         return __first;
00344       const auto& __pred = this->_M_pred();
00345       __diff_type __i = __patlen - 1;
00346       auto __stringlen = __last - __first;
00347       while (__i < __stringlen)
00348         {
00349           __diff_type __j = __patlen - 1;
00350           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
00351             {
00352               --__i;
00353               --__j;
00354             }
00355           if (__j < 0)
00356             return __first + __i + 1;
00357           __i += std::max(_M_bad_char_shift(__first[__i]),
00358                           _M_good_suffix[__j]);
00359         }
00360       return __last;
00361     }
00362 } // namespace fundamentals_v1
00363 
00364 inline namespace fundamentals_v2
00365 {
00366 #define __cpp_lib_experimental_not_fn 201406
00367 
00368   /// [func.not_fn] Function template not_fn
00369   template<typename _Fn>
00370     inline auto
00371     not_fn(_Fn&& __fn)
00372     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
00373     {
00374       return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
00375     }
00376 } // namespace fundamentals_v2
00377 } // namespace experimental
00378 
00379 _GLIBCXX_END_NAMESPACE_VERSION
00380 } // namespace std
00381 
00382 #endif // C++14
00383 
00384 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL