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