1// -*- C++ -*- 2//===-------------------------- functional --------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL 12#define _LIBCPP_EXPERIMENTAL_FUNCTIONAL 13 14/* 15 experimental/functional synopsis 16 17#include <algorithm> 18 19namespace std { 20namespace experimental { 21inline namespace fundamentals_v1 { 22 23 // See C++14 20.9.9, Function object binders 24 template <class T> constexpr bool is_bind_expression_v 25 = is_bind_expression<T>::value; 26 template <class T> constexpr int is_placeholder_v 27 = is_placeholder<T>::value; 28 29 // 4.2, Class template function 30 template<class> class function; // undefined 31 template<class R, class... ArgTypes> class function<R(ArgTypes...)>; 32 33 template<class R, class... ArgTypes> 34 void swap(function<R(ArgTypes...)>&, function<R(ArgTypes...)>&); 35 36 template<class R, class... ArgTypes> 37 bool operator==(const function<R(ArgTypes...)>&, nullptr_t) noexcept; 38 template<class R, class... ArgTypes> 39 bool operator==(nullptr_t, const function<R(ArgTypes...)>&) noexcept; 40 template<class R, class... ArgTypes> 41 bool operator!=(const function<R(ArgTypes...)>&, nullptr_t) noexcept; 42 template<class R, class... ArgTypes> 43 bool operator!=(nullptr_t, const function<R(ArgTypes...)>&) noexcept; 44 45 // 4.3, Searchers 46 template<class ForwardIterator, class BinaryPredicate = equal_to<>> 47 class default_searcher; 48 49 template<class RandomAccessIterator, 50 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 51 class BinaryPredicate = equal_to<>> 52 class boyer_moore_searcher; 53 54 template<class RandomAccessIterator, 55 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 56 class BinaryPredicate = equal_to<>> 57 class boyer_moore_horspool_searcher; 58 59 template<class ForwardIterator, class BinaryPredicate = equal_to<>> 60 default_searcher<ForwardIterator, BinaryPredicate> 61 make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last, 62 BinaryPredicate pred = BinaryPredicate()); 63 64 template<class RandomAccessIterator, 65 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 66 class BinaryPredicate = equal_to<>> 67 boyer_moore_searcher<RandomAccessIterator, Hash, BinaryPredicate> 68 make_boyer_moore_searcher( 69 RandomAccessIterator pat_first, RandomAccessIterator pat_last, 70 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 71 72 template<class RandomAccessIterator, 73 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 74 class BinaryPredicate = equal_to<>> 75 boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate> 76 make_boyer_moore_horspool_searcher( 77 RandomAccessIterator pat_first, RandomAccessIterator pat_last, 78 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 79 80 } // namespace fundamentals_v1 81 } // namespace experimental 82 83 template<class R, class... ArgTypes, class Alloc> 84 struct uses_allocator<experimental::function<R(ArgTypes...)>, Alloc>; 85 86} // namespace std 87 88*/ 89 90#include <experimental/__config> 91#include <functional> 92#include <algorithm> 93#include <type_traits> 94#include <vector> 95#include <array> 96#include <unordered_map> 97 98#include <__debug> 99 100#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 101#pragma GCC system_header 102#endif 103 104_LIBCPP_PUSH_MACROS 105#include <__undef_macros> 106 107 108_LIBCPP_BEGIN_NAMESPACE_LFTS 109 110#if _LIBCPP_STD_VER > 11 111// default searcher 112template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 113_LIBCPP_TYPE_VIS 114class default_searcher { 115public: 116 _LIBCPP_INLINE_VISIBILITY 117 default_searcher(_ForwardIterator __f, _ForwardIterator __l, 118 _BinaryPredicate __p = _BinaryPredicate()) 119 : __first_(__f), __last_(__l), __pred_(__p) {} 120 121 template <typename _ForwardIterator2> 122 _LIBCPP_INLINE_VISIBILITY 123 pair<_ForwardIterator2, _ForwardIterator2> 124 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const 125 { 126 return _VSTD::__search(__f, __l, __first_, __last_, __pred_, 127 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category(), 128 typename _VSTD::iterator_traits<_ForwardIterator2>::iterator_category()); 129 } 130 131private: 132 _ForwardIterator __first_; 133 _ForwardIterator __last_; 134 _BinaryPredicate __pred_; 135 }; 136 137template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 138_LIBCPP_INLINE_VISIBILITY 139default_searcher<_ForwardIterator, _BinaryPredicate> 140make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ()) 141{ 142 return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p); 143} 144 145template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable; 146 147// General case for BM data searching; use a map 148template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 149class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> { 150public: // TODO private: 151 typedef _Value value_type; 152 typedef _Key key_type; 153 154 const _Value __default_value_; 155 std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table; 156 157public: 158 _LIBCPP_INLINE_VISIBILITY 159 _BMSkipTable(std::size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred) 160 : __default_value_(__default), __table(__sz, __hf, __pred) {} 161 162 _LIBCPP_INLINE_VISIBILITY 163 void insert(const key_type &__key, value_type __val) 164 { 165 __table [__key] = __val; // Would skip_.insert (val) be better here? 166 } 167 168 _LIBCPP_INLINE_VISIBILITY 169 value_type operator [](const key_type & __key) const 170 { 171 auto __it = __table.find (__key); 172 return __it == __table.end() ? __default_value_ : __it->second; 173 } 174}; 175 176 177// Special case small numeric values; use an array 178template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 179class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> { 180private: 181 typedef _Value value_type; 182 typedef _Key key_type; 183 184 typedef typename std::make_unsigned<key_type>::type unsigned_key_type; 185 typedef std::array<value_type, _VSTD::numeric_limits<unsigned_key_type>::max()> skip_map; 186 skip_map __table; 187 188public: 189 _LIBCPP_INLINE_VISIBILITY 190 _BMSkipTable(std::size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/) 191 { 192 std::fill_n(__table.begin(), __table.size(), __default); 193 } 194 195 _LIBCPP_INLINE_VISIBILITY 196 void insert(key_type __key, value_type __val) 197 { 198 __table[static_cast<unsigned_key_type>(__key)] = __val; 199 } 200 201 _LIBCPP_INLINE_VISIBILITY 202 value_type operator [](key_type __key) const 203 { 204 return __table[static_cast<unsigned_key_type>(__key)]; 205 } 206}; 207 208 209template <class _RandomAccessIterator1, 210 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 211 class _BinaryPredicate = equal_to<>> 212_LIBCPP_TYPE_VIS 213class boyer_moore_searcher { 214private: 215 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 216 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 217 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 218 _VSTD::is_integral<value_type>::value && // what about enums? 219 sizeof(value_type) == 1 && 220 is_same<_Hash, hash<value_type>>::value && 221 is_same<_BinaryPredicate, equal_to<>>::value 222 > skip_table_type; 223 224public: 225 boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 226 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 227 : __first_(__f), __last_(__l), __pred_(__pred), 228 __pattern_length_(_VSTD::distance(__first_, __last_)), 229 __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)}, 230 __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)} 231 { 232 // build the skip table 233 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 234 __skip_->insert(*__f, __i); 235 236 this->__build_suffix_table ( __first_, __last_, __pred_ ); 237 } 238 239 template <typename _RandomAccessIterator2> 240 pair<_RandomAccessIterator2, _RandomAccessIterator2> 241 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 242 { 243 static_assert ( std::is_same< 244 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 245 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 246 >::value, 247 "Corpus and Pattern iterators must point to the same type" ); 248 249 if (__f == __l ) return make_pair(__l, __l); // empty corpus 250 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 251 252 // If the pattern is larger than the corpus, we can't find it! 253 if ( __pattern_length_ > _VSTD::distance (__f, __l)) 254 return make_pair(__l, __l); 255 256 // Do the search 257 return this->__search(__f, __l); 258 } 259 260public: // TODO private: 261 _RandomAccessIterator1 __first_; 262 _RandomAccessIterator1 __last_; 263 _BinaryPredicate __pred_; 264 difference_type __pattern_length_; 265 shared_ptr<skip_table_type> __skip_; 266 shared_ptr<vector<difference_type>> __suffix_; 267 268 template <typename _RandomAccessIterator2> 269 pair<_RandomAccessIterator2, _RandomAccessIterator2> 270 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 271 { 272 _RandomAccessIterator2 __cur = __f; 273 const _RandomAccessIterator2 __last = __l - __pattern_length_; 274 const skip_table_type & __skip = *__skip_.get(); 275 const vector<difference_type> & __suffix = *__suffix_.get(); 276 277 while (__cur <= __last) 278 { 279 280 // Do we match right where we are? 281 difference_type __j = __pattern_length_; 282 while (__pred_(__first_ [__j-1], __cur [__j-1])) { 283 __j--; 284 // We matched - we're done! 285 if ( __j == 0 ) 286 return make_pair(__cur, __cur + __pattern_length_); 287 } 288 289 // Since we didn't match, figure out how far to skip forward 290 difference_type __k = __skip[__cur [ __j - 1 ]]; 291 difference_type __m = __j - __k - 1; 292 if (__k < __j && __m > __suffix[ __j ]) 293 __cur += __m; 294 else 295 __cur += __suffix[ __j ]; 296 } 297 298 return make_pair(__l, __l); // We didn't find anything 299 } 300 301 302 template<typename _Iterator, typename _Container> 303 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) 304 { 305 const std::size_t __count = _VSTD::distance(__f, __l); 306 307 __prefix[0] = 0; 308 std::size_t __k = 0; 309 for ( std::size_t __i = 1; __i < __count; ++__i ) 310 { 311 while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) 312 __k = __prefix [ __k - 1 ]; 313 314 if ( __pred ( __f[__k], __f[__i] )) 315 __k++; 316 __prefix [ __i ] = __k; 317 } 318 } 319 320 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 321 _BinaryPredicate __pred) 322 { 323 const std::size_t __count = _VSTD::distance(__f, __l); 324 vector<difference_type> & __suffix = *__suffix_.get(); 325 if (__count > 0) 326 { 327 _VSTD::vector<value_type> __scratch(__count); 328 329 __compute_bm_prefix(__f, __l, __pred, __scratch); 330 for ( std::size_t __i = 0; __i <= __count; __i++ ) 331 __suffix[__i] = __count - __scratch[__count-1]; 332 333 typedef _VSTD::reverse_iterator<_RandomAccessIterator1> _RevIter; 334 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch); 335 336 for ( std::size_t __i = 0; __i < __count; __i++ ) 337 { 338 const std::size_t __j = __count - __scratch[__i]; 339 const difference_type __k = __i - __scratch[__i] + 1; 340 341 if (__suffix[__j] > __k) 342 __suffix[__j] = __k; 343 } 344 } 345 } 346 347}; 348 349template<class _RandomAccessIterator, 350 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 351 class _BinaryPredicate = equal_to<>> 352_LIBCPP_INLINE_VISIBILITY 353boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 354make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 355 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 356{ 357 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 358} 359 360// boyer-moore-horspool 361template <class _RandomAccessIterator1, 362 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 363 class _BinaryPredicate = equal_to<>> 364_LIBCPP_TYPE_VIS 365class boyer_moore_horspool_searcher { 366private: 367 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 368 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 369 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 370 _VSTD::is_integral<value_type>::value && // what about enums? 371 sizeof(value_type) == 1 && 372 is_same<_Hash, hash<value_type>>::value && 373 is_same<_BinaryPredicate, equal_to<>>::value 374 > skip_table_type; 375 376public: 377 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 378 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 379 : __first_(__f), __last_(__l), __pred_(__pred), 380 __pattern_length_(_VSTD::distance(__first_, __last_)), 381 __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)} 382 { 383 // build the skip table 384 if ( __f != __l ) 385 { 386 __l = __l - 1; 387 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 388 __skip_->insert(*__f, __pattern_length_ - 1 - __i); 389 } 390 } 391 392 template <typename _RandomAccessIterator2> 393 pair<_RandomAccessIterator2, _RandomAccessIterator2> 394 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 395 { 396 static_assert ( std::is_same< 397 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 398 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 399 >::value, 400 "Corpus and Pattern iterators must point to the same type" ); 401 402 if (__f == __l ) return make_pair(__l, __l); // empty corpus 403 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 404 405 // If the pattern is larger than the corpus, we can't find it! 406 if ( __pattern_length_ > _VSTD::distance (__f, __l)) 407 return make_pair(__l, __l); 408 409 // Do the search 410 return this->__search(__f, __l); 411 } 412 413private: 414 _RandomAccessIterator1 __first_; 415 _RandomAccessIterator1 __last_; 416 _BinaryPredicate __pred_; 417 difference_type __pattern_length_; 418 shared_ptr<skip_table_type> __skip_; 419 420 template <typename _RandomAccessIterator2> 421 pair<_RandomAccessIterator2, _RandomAccessIterator2> 422 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { 423 _RandomAccessIterator2 __cur = __f; 424 const _RandomAccessIterator2 __last = __l - __pattern_length_; 425 const skip_table_type & __skip = *__skip_.get(); 426 427 while (__cur <= __last) 428 { 429 // Do we match right where we are? 430 difference_type __j = __pattern_length_; 431 while (__pred_(__first_[__j-1], __cur[__j-1])) 432 { 433 __j--; 434 // We matched - we're done! 435 if ( __j == 0 ) 436 return make_pair(__cur, __cur + __pattern_length_); 437 } 438 __cur += __skip[__cur[__pattern_length_-1]]; 439 } 440 441 return make_pair(__l, __l); 442 } 443}; 444 445template<class _RandomAccessIterator, 446 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 447 class _BinaryPredicate = equal_to<>> 448_LIBCPP_INLINE_VISIBILITY 449boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 450make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 451 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 452{ 453 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 454} 455 456#endif // _LIBCPP_STD_VER > 11 457 458_LIBCPP_END_NAMESPACE_LFTS 459 460_LIBCPP_POP_MACROS 461 462#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */ 463