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