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