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