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