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