1 // <experimental/functional> -*- C++ -*- 2 3 // Copyright (C) 2014-2022 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file experimental/functional 26 * This is a TS C++ Library header. 27 * @ingroup libfund-ts 28 */ 29 30 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 31 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 32 33 #pragma GCC system_header 34 35 #if __cplusplus >= 201402L 36 37 #include <functional> 38 #include <tuple> 39 #include <iterator> 40 #include <unordered_map> 41 #include <vector> 42 #include <array> 43 #include <bits/stl_algo.h> 44 #ifdef _GLIBCXX_PARALLEL 45 # include <parallel/algorithm> // For std::__parallel::search 46 #endif 47 #include <experimental/bits/lfts_config.h> 48 49 namespace std _GLIBCXX_VISIBILITY(default) 50 { 51 _GLIBCXX_BEGIN_NAMESPACE_VERSION 52 53 namespace experimental 54 { 55 inline namespace fundamentals_v1 56 { 57 // See C++14 20.9.9, Function object binders 58 59 /// Variable template for std::is_bind_expression 60 template<typename _Tp> 61 constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; 62 63 /// Variable template for std::is_placeholder 64 template<typename _Tp> 65 constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; 66 67 #define __cpp_lib_experimental_boyer_moore_searching 201411 68 69 // Searchers 70 71 template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>> 72 class default_searcher 73 { 74 public: 75 default_searcher(_ForwardIterator1 __pat_first, 76 _ForwardIterator1 __pat_last, 77 _BinaryPredicate __pred = _BinaryPredicate()) 78 : _M_m(__pat_first, __pat_last, std::move(__pred)) 79 { } 80 81 template<typename _ForwardIterator2> 82 _ForwardIterator2 83 operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const 84 { 85 return std::search(__first, __last, 86 std::get<0>(_M_m), std::get<1>(_M_m), 87 std::get<2>(_M_m)); 88 } 89 90 private: 91 std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; 92 }; 93 94 template<typename _Key, typename _Tp, typename _Hash, typename _Pred> 95 struct __boyer_moore_map_base 96 { 97 template<typename _RAIter> 98 __boyer_moore_map_base(_RAIter __pat, size_t __patlen, 99 _Hash&& __hf, _Pred&& __pred) 100 : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) } 101 { 102 if (__patlen > 0) 103 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 104 _M_bad_char[__pat[__i]] = __patlen - 1 - __i; 105 } 106 107 using __diff_type = _Tp; 108 109 __diff_type 110 _M_lookup(_Key __key, __diff_type __not_found) const 111 { 112 auto __iter = _M_bad_char.find(__key); 113 if (__iter == _M_bad_char.end()) 114 return __not_found; 115 return __iter->second; 116 } 117 118 _Pred 119 _M_pred() const { return _M_bad_char.key_eq(); } 120 121 _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char; 122 }; 123 124 template<typename _Tp, size_t _Len, typename _Pred> 125 struct __boyer_moore_array_base 126 { 127 template<typename _RAIter, typename _Unused> 128 __boyer_moore_array_base(_RAIter __pat, size_t __patlen, 129 _Unused&&, _Pred&& __pred) 130 : _M_bad_char{ std::array<_Tp, _Len>{}, std::move(__pred) } 131 { 132 std::get<0>(_M_bad_char).fill(__patlen); 133 if (__patlen > 0) 134 for (__diff_type __i = 0; __i < __patlen - 1; ++__i) 135 { 136 auto __ch = __pat[__i]; 137 using _UCh = std::make_unsigned_t<decltype(__ch)>; 138 auto __uch = static_cast<_UCh>(__ch); 139 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; 140 } 141 } 142 143 using __diff_type = _Tp; 144 145 template<typename _Key> 146 __diff_type 147 _M_lookup(_Key __key, __diff_type __not_found) const 148 { 149 auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key); 150 if (__ukey >= _Len) 151 return __not_found; 152 return std::get<0>(_M_bad_char)[__ukey]; 153 } 154 155 const _Pred& 156 _M_pred() const { return std::get<1>(_M_bad_char); } 157 158 std::tuple<std::array<_Tp, _Len>, _Pred> _M_bad_char; 159 }; 160 161 // Use __boyer_moore_array_base when pattern consists of narrow characters 162 // (or std::byte) and uses std::equal_to as the predicate. 163 template<typename _RAIter, typename _Hash, typename _Pred, 164 typename _Val = typename iterator_traits<_RAIter>::value_type, 165 typename _Diff = typename iterator_traits<_RAIter>::difference_type> 166 using __boyer_moore_base_t 167 = std::__conditional_t<std::__is_byte_like<_Val, _Pred>::value, 168 __boyer_moore_array_base<_Diff, 256, _Pred>, 169 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; 170 171 template<typename _RAIter, typename _Hash 172 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 173 typename _BinaryPredicate = std::equal_to<>> 174 class boyer_moore_searcher 175 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 176 { 177 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 178 using typename _Base::__diff_type; 179 180 public: 181 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 182 _Hash __hf = _Hash(), 183 _BinaryPredicate __pred = _BinaryPredicate()); 184 185 template<typename _RandomAccessIterator2> 186 _RandomAccessIterator2 187 operator()(_RandomAccessIterator2 __first, 188 _RandomAccessIterator2 __last) const; 189 190 private: 191 bool 192 _M_is_prefix(_RAIter __word, __diff_type __len, 193 __diff_type __pos) 194 { 195 const auto& __pred = this->_M_pred(); 196 __diff_type __suffixlen = __len - __pos; 197 for (__diff_type __i = 0; __i < __suffixlen; ++__i) 198 if (!__pred(__word[__i], __word[__pos + __i])) 199 return false; 200 return true; 201 } 202 203 __diff_type 204 _M_suffix_length(_RAIter __word, __diff_type __len, 205 __diff_type __pos) 206 { 207 const auto& __pred = this->_M_pred(); 208 __diff_type __i = 0; 209 while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) 210 && __i < __pos) 211 { 212 ++__i; 213 } 214 return __i; 215 } 216 217 template<typename _Tp> 218 __diff_type 219 _M_bad_char_shift(_Tp __c) const 220 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 221 222 _RAIter _M_pat; 223 _RAIter _M_pat_end; 224 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix; 225 }; 226 227 template<typename _RAIter, typename _Hash 228 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 229 typename _BinaryPredicate = std::equal_to<>> 230 class boyer_moore_horspool_searcher 231 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 232 { 233 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 234 using typename _Base::__diff_type; 235 236 public: 237 boyer_moore_horspool_searcher(_RAIter __pat, 238 _RAIter __pat_end, 239 _Hash __hf = _Hash(), 240 _BinaryPredicate __pred 241 = _BinaryPredicate()) 242 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 243 _M_pat(__pat), _M_pat_end(__pat_end) 244 { } 245 246 template<typename _RandomAccessIterator2> 247 _RandomAccessIterator2 248 operator()(_RandomAccessIterator2 __first, 249 _RandomAccessIterator2 __last) const 250 { 251 const auto& __pred = this->_M_pred(); 252 auto __patlen = _M_pat_end - _M_pat; 253 if (__patlen == 0) 254 return __first; 255 auto __len = __last - __first; 256 while (__len >= __patlen) 257 { 258 for (auto __scan = __patlen - 1; 259 __pred(__first[__scan], _M_pat[__scan]); --__scan) 260 if (__scan == 0) 261 return __first; 262 auto __shift = _M_bad_char_shift(__first[__patlen - 1]); 263 __len -= __shift; 264 __first += __shift; 265 } 266 return __last; 267 } 268 269 private: 270 template<typename _Tp> 271 __diff_type 272 _M_bad_char_shift(_Tp __c) const 273 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 274 275 _RAIter _M_pat; 276 _RAIter _M_pat_end; 277 }; 278 279 /// Generator function for default_searcher 280 template<typename _ForwardIterator, 281 typename _BinaryPredicate = std::equal_to<>> 282 inline default_searcher<_ForwardIterator, _BinaryPredicate> 283 make_default_searcher(_ForwardIterator __pat_first, 284 _ForwardIterator __pat_last, 285 _BinaryPredicate __pred = _BinaryPredicate()) 286 { return { __pat_first, __pat_last, __pred }; } 287 288 /// Generator function for boyer_moore_searcher 289 template<typename _RAIter, typename _Hash 290 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 291 typename _BinaryPredicate = equal_to<>> 292 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> 293 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 294 _Hash __hf = _Hash(), 295 _BinaryPredicate __pred = _BinaryPredicate()) 296 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 297 298 /// Generator function for boyer_moore_horspool_searcher 299 template<typename _RAIter, typename _Hash 300 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 301 typename _BinaryPredicate = equal_to<>> 302 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> 303 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, 304 _Hash __hf = _Hash(), 305 _BinaryPredicate __pred 306 = _BinaryPredicate()) 307 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 308 309 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 310 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 311 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, 312 _Hash __hf, _BinaryPredicate __pred) 313 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 314 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) 315 { 316 auto __patlen = __pat_end - __pat; 317 if (__patlen == 0) 318 return; 319 __diff_type __last_prefix = __patlen - 1; 320 for (__diff_type __p = __patlen - 1; __p >= 0; --__p) 321 { 322 if (_M_is_prefix(__pat, __patlen, __p + 1)) 323 __last_prefix = __p + 1; 324 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); 325 } 326 for (__diff_type __p = 0; __p < __patlen - 1; ++__p) 327 { 328 auto __slen = _M_suffix_length(__pat, __patlen, __p); 329 auto __pos = __patlen - 1 - __slen; 330 if (!__pred(__pat[__p - __slen], __pat[__pos])) 331 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; 332 } 333 } 334 335 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 336 template<typename _RandomAccessIterator2> 337 _RandomAccessIterator2 338 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 339 operator()(_RandomAccessIterator2 __first, 340 _RandomAccessIterator2 __last) const 341 { 342 auto __patlen = _M_pat_end - _M_pat; 343 if (__patlen == 0) 344 return __first; 345 const auto& __pred = this->_M_pred(); 346 __diff_type __i = __patlen - 1; 347 auto __stringlen = __last - __first; 348 while (__i < __stringlen) 349 { 350 __diff_type __j = __patlen - 1; 351 while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) 352 { 353 --__i; 354 --__j; 355 } 356 if (__j < 0) 357 return __first + __i + 1; 358 __i += std::max(_M_bad_char_shift(__first[__i]), 359 _M_good_suffix[__j]); 360 } 361 return __last; 362 } 363 } // namespace fundamentals_v1 364 365 inline namespace fundamentals_v2 366 { 367 #define __cpp_lib_experimental_not_fn 201406 368 369 /// [func.not_fn] Function template not_fn 370 template<typename _Fn> 371 inline auto 372 not_fn(_Fn&& __fn) 373 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value) 374 { 375 return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0}; 376 } 377 } // namespace fundamentals_v2 378 } // namespace experimental 379 380 _GLIBCXX_END_NAMESPACE_VERSION 381 } // namespace std 382 383 #endif // C++14 384 385 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 386
Indexes created Sun Mar 01 05:31:48 UTC 2026