1// <experimental/functional> -*- C++ -*- 2 3// Copyright (C) 2014-2021 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 49namespace std _GLIBCXX_VISIBILITY(default) 50{ 51_GLIBCXX_BEGIN_NAMESPACE_VERSION 52 53namespace experimental 54{ 55inline 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 365inline 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