libstdc++
|
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