1// <experimental/functional> -*- C++ -*- 2 3// Copyright (C) 2014-2017 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{ 50namespace experimental 51{ 52inline namespace fundamentals_v1 53{ 54_GLIBCXX_BEGIN_NAMESPACE_VERSION 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 template<typename _Pred> 161 struct __is_std_equal_to : std::false_type { }; 162 163 template<> 164 struct __is_std_equal_to<std::equal_to<void>> : std::true_type { }; 165 166 // Use __boyer_moore_array_base when pattern consists of narrow characters 167 // and uses std::equal_to as the predicate. 168 template<typename _RAIter, typename _Hash, typename _Pred, 169 typename _Val = typename iterator_traits<_RAIter>::value_type, 170 typename _Diff = typename iterator_traits<_RAIter>::difference_type> 171 using __boyer_moore_base_t 172 = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value 173 && __is_std_equal_to<_Pred>::value, 174 __boyer_moore_array_base<_Diff, 256, _Pred>, 175 __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; 176 177 template<typename _RAIter, typename _Hash 178 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 179 typename _BinaryPredicate = std::equal_to<>> 180 class boyer_moore_searcher 181 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 182 { 183 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 184 using typename _Base::__diff_type; 185 186 public: 187 boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 188 _Hash __hf = _Hash(), 189 _BinaryPredicate __pred = _BinaryPredicate()); 190 191 template<typename _RandomAccessIterator2> 192 _RandomAccessIterator2 193 operator()(_RandomAccessIterator2 __first, 194 _RandomAccessIterator2 __last) const; 195 196 private: 197 bool 198 _M_is_prefix(_RAIter __word, __diff_type __len, 199 __diff_type __pos) 200 { 201 const auto& __pred = this->_M_pred(); 202 __diff_type __suffixlen = __len - __pos; 203 for (__diff_type __i = 0; __i < __suffixlen; ++__i) 204 if (!__pred(__word[__i], __word[__pos + __i])) 205 return false; 206 return true; 207 } 208 209 __diff_type 210 _M_suffix_length(_RAIter __word, __diff_type __len, 211 __diff_type __pos) 212 { 213 const auto& __pred = this->_M_pred(); 214 __diff_type __i = 0; 215 while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) 216 && __i < __pos) 217 { 218 ++__i; 219 } 220 return __i; 221 } 222 223 template<typename _Tp> 224 __diff_type 225 _M_bad_char_shift(_Tp __c) const 226 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 227 228 _RAIter _M_pat; 229 _RAIter _M_pat_end; 230 _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix; 231 }; 232 233 template<typename _RAIter, typename _Hash 234 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 235 typename _BinaryPredicate = std::equal_to<>> 236 class boyer_moore_horspool_searcher 237 : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> 238 { 239 using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; 240 using typename _Base::__diff_type; 241 242 public: 243 boyer_moore_horspool_searcher(_RAIter __pat, 244 _RAIter __pat_end, 245 _Hash __hf = _Hash(), 246 _BinaryPredicate __pred 247 = _BinaryPredicate()) 248 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 249 _M_pat(__pat), _M_pat_end(__pat_end) 250 { } 251 252 template<typename _RandomAccessIterator2> 253 _RandomAccessIterator2 254 operator()(_RandomAccessIterator2 __first, 255 _RandomAccessIterator2 __last) const 256 { 257 const auto& __pred = this->_M_pred(); 258 auto __patlen = _M_pat_end - _M_pat; 259 if (__patlen == 0) 260 return __first; 261 auto __len = __last - __first; 262 while (__len >= __patlen) 263 { 264 for (auto __scan = __patlen - 1; 265 __pred(__first[__scan], _M_pat[__scan]); --__scan) 266 if (__scan == 0) 267 return __first; 268 auto __shift = _M_bad_char_shift(__first[__patlen - 1]); 269 __len -= __shift; 270 __first += __shift; 271 } 272 return __last; 273 } 274 275 private: 276 template<typename _Tp> 277 __diff_type 278 _M_bad_char_shift(_Tp __c) const 279 { return this->_M_lookup(__c, _M_pat_end - _M_pat); } 280 281 _RAIter _M_pat; 282 _RAIter _M_pat_end; 283 }; 284 285 /// Generator function for default_searcher 286 template<typename _ForwardIterator, 287 typename _BinaryPredicate = std::equal_to<>> 288 inline default_searcher<_ForwardIterator, _BinaryPredicate> 289 make_default_searcher(_ForwardIterator __pat_first, 290 _ForwardIterator __pat_last, 291 _BinaryPredicate __pred = _BinaryPredicate()) 292 { return { __pat_first, __pat_last, __pred }; } 293 294 /// Generator function for boyer_moore_searcher 295 template<typename _RAIter, typename _Hash 296 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 297 typename _BinaryPredicate = equal_to<>> 298 inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> 299 make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, 300 _Hash __hf = _Hash(), 301 _BinaryPredicate __pred = _BinaryPredicate()) 302 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 303 304 /// Generator function for boyer_moore_horspool_searcher 305 template<typename _RAIter, typename _Hash 306 = std::hash<typename std::iterator_traits<_RAIter>::value_type>, 307 typename _BinaryPredicate = equal_to<>> 308 inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> 309 make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, 310 _Hash __hf = _Hash(), 311 _BinaryPredicate __pred 312 = _BinaryPredicate()) 313 { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } 314 315 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 316 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 317 boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, 318 _Hash __hf, _BinaryPredicate __pred) 319 : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), 320 _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) 321 { 322 auto __patlen = __pat_end - __pat; 323 if (__patlen == 0) 324 return; 325 __diff_type __last_prefix = __patlen - 1; 326 for (__diff_type __p = __patlen - 1; __p >= 0; --__p) 327 { 328 if (_M_is_prefix(__pat, __patlen, __p + 1)) 329 __last_prefix = __p + 1; 330 _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); 331 } 332 for (__diff_type __p = 0; __p < __patlen - 1; ++__p) 333 { 334 auto __slen = _M_suffix_length(__pat, __patlen, __p); 335 auto __pos = __patlen - 1 - __slen; 336 if (!__pred(__pat[__p - __slen], __pat[__pos])) 337 _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; 338 } 339 } 340 341 template<typename _RAIter, typename _Hash, typename _BinaryPredicate> 342 template<typename _RandomAccessIterator2> 343 _RandomAccessIterator2 344 boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: 345 operator()(_RandomAccessIterator2 __first, 346 _RandomAccessIterator2 __last) const 347 { 348 auto __patlen = _M_pat_end - _M_pat; 349 if (__patlen == 0) 350 return __first; 351 const auto& __pred = this->_M_pred(); 352 __diff_type __i = __patlen - 1; 353 auto __stringlen = __last - __first; 354 while (__i < __stringlen) 355 { 356 __diff_type __j = __patlen - 1; 357 while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) 358 { 359 --__i; 360 --__j; 361 } 362 if (__j < 0) 363 return __first + __i + 1; 364 __i += std::max(_M_bad_char_shift(__first[__i]), 365 _M_good_suffix[__j]); 366 } 367 return __last; 368 } 369 370_GLIBCXX_END_NAMESPACE_VERSION 371} // namespace fundamentals_v1 372 373inline namespace fundamentals_v2 374{ 375_GLIBCXX_BEGIN_NAMESPACE_VERSION 376 377#define __cpp_lib_experimental_not_fn 201406 378 379 /// [func.not_fn] Function template not_fn 380 template<typename _Fn> 381 inline auto 382 not_fn(_Fn&& __fn) 383 noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value) 384 { 385 return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0}; 386 } 387 388_GLIBCXX_END_NAMESPACE_VERSION 389} // namespace fundamentals_v2 390} // namespace experimental 391} // namespace std 392 393#endif // C++14 394 395#endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 396