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 93#include <algorithm> 94#include <type_traits> 95#include <vector> 96#include <array> 97#include <unordered_map> 98 99#include <__undef_min_max> 100 101#include <__debug> 102 103#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 104#pragma GCC system_header 105#endif 106 107_LIBCPP_BEGIN_NAMESPACE_LFTS 108 109#if _LIBCPP_STD_VER > 11 110// default searcher 111template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 112_LIBCPP_TYPE_VIS 113class default_searcher { 114public: 115 _LIBCPP_INLINE_VISIBILITY 116 default_searcher(_ForwardIterator __f, _ForwardIterator __l, 117 _BinaryPredicate __p = _BinaryPredicate()) 118 : __first_(__f), __last_(__l), __pred_(__p) {} 119 120 template <typename _ForwardIterator2> 121 _LIBCPP_INLINE_VISIBILITY 122 _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const 123 { 124 return _VSTD::search(__f, __l, __first_, __last_, __pred_); 125 } 126 127private: 128 _ForwardIterator __first_; 129 _ForwardIterator __last_; 130 _BinaryPredicate __pred_; 131 }; 132 133template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 134_LIBCPP_INLINE_VISIBILITY 135default_searcher<_ForwardIterator, _BinaryPredicate> 136make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ()) 137{ 138 return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p); 139} 140 141template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable; 142 143// General case for BM data searching; use a map 144template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 145class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> { 146public: // TODO private: 147 typedef _Value value_type; 148 typedef _Key key_type; 149 150 const _Value __default_value_; 151 std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table; 152 153public: 154 _LIBCPP_INLINE_VISIBILITY 155 _BMSkipTable(std::size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred) 156 : __default_value_(__default), __table(__sz, __hf, __pred) {} 157 158 _LIBCPP_INLINE_VISIBILITY 159 void insert(const key_type &__key, value_type __val) 160 { 161 __table [__key] = __val; // Would skip_.insert (val) be better here? 162 } 163 164 _LIBCPP_INLINE_VISIBILITY 165 value_type operator [](const key_type & __key) const 166 { 167 auto __it = __table.find (__key); 168 return __it == __table.end() ? __default_value_ : __it->second; 169 } 170}; 171 172 173// Special case small numeric values; use an array 174template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 175class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> { 176private: 177 typedef _Value value_type; 178 typedef _Key key_type; 179 180 typedef typename std::make_unsigned<key_type>::type unsigned_key_type; 181 typedef std::array<value_type, _VSTD::numeric_limits<unsigned_key_type>::max()> skip_map; 182 skip_map __table; 183 184public: 185 _LIBCPP_INLINE_VISIBILITY 186 _BMSkipTable(std::size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/) 187 { 188 std::fill_n(__table.begin(), __table.size(), __default); 189 } 190 191 _LIBCPP_INLINE_VISIBILITY 192 void insert(key_type __key, value_type __val) 193 { 194 __table[static_cast<unsigned_key_type>(__key)] = __val; 195 } 196 197 _LIBCPP_INLINE_VISIBILITY 198 value_type operator [](key_type __key) const 199 { 200 return __table[static_cast<unsigned_key_type>(__key)]; 201 } 202}; 203 204 205template <class _RandomAccessIterator1, 206 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 207 class _BinaryPredicate = equal_to<>> 208_LIBCPP_TYPE_VIS 209class boyer_moore_searcher { 210private: 211 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 212 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 213 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 214 _VSTD::is_integral<value_type>::value && // what about enums? 215 sizeof(value_type) == 1 && 216 is_same<_Hash, hash<value_type>>::value && 217 is_same<_BinaryPredicate, equal_to<>>::value 218 > skip_table_type; 219 220public: 221 boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 222 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 223 : __first_(__f), __last_(__l), __pred_(__pred), 224 __pattern_length_(_VSTD::distance(__first_, __last_)), 225 __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)}, 226 __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)} 227 { 228 // build the skip table 229 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 230 __skip_->insert(*__f, __i); 231 232 this->__build_suffix_table ( __first_, __last_, __pred_ ); 233 } 234 235 template <typename _RandomAccessIterator2> 236 _RandomAccessIterator2 237 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 238 { 239 static_assert ( std::is_same< 240 typename std::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 241 typename std::decay<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 242 >::value, 243 "Corpus and Pattern iterators must point to the same type" ); 244 245 if (__f == __l ) return __l; // empty corpus 246 if (__first_ == __last_) return __f; // empty pattern 247 248 // If the pattern is larger than the corpus, we can't find it! 249 if ( __pattern_length_ > _VSTD::distance (__f, __l)) 250 return __l; 251 252 // Do the search 253 return this->__search(__f, __l); 254 } 255 256public: // TODO private: 257 _RandomAccessIterator1 __first_; 258 _RandomAccessIterator1 __last_; 259 _BinaryPredicate __pred_; 260 difference_type __pattern_length_; 261 shared_ptr<skip_table_type> __skip_; 262 shared_ptr<vector<difference_type>> __suffix_; 263 264 template <typename _RandomAccessIterator2> 265 _RandomAccessIterator2 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 266 { 267 _RandomAccessIterator2 __cur = __f; 268 const _RandomAccessIterator2 __last = __l - __pattern_length_; 269 const skip_table_type & __skip = *__skip_.get(); 270 const vector<difference_type> & __suffix = *__suffix_.get(); 271 272 while (__cur <= __last) 273 { 274 275 // Do we match right where we are? 276 difference_type __j = __pattern_length_; 277 while (__pred_(__first_ [__j-1], __cur [__j-1])) { 278 __j--; 279 // We matched - we're done! 280 if ( __j == 0 ) 281 return __cur; 282 } 283 284 // Since we didn't match, figure out how far to skip forward 285 difference_type __k = __skip[__cur [ __j - 1 ]]; 286 difference_type __m = __j - __k - 1; 287 if (__k < __j && __m > __suffix[ __j ]) 288 __cur += __m; 289 else 290 __cur += __suffix[ __j ]; 291 } 292 293 return __l; // We didn't find anything 294 } 295 296 297 template<typename _Iterator, typename _Container> 298 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) 299 { 300 const std::size_t __count = _VSTD::distance(__f, __l); 301 302 __prefix[0] = 0; 303 std::size_t __k = 0; 304 for ( std::size_t __i = 1; __i < __count; ++__i ) 305 { 306 while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) 307 __k = __prefix [ __k - 1 ]; 308 309 if ( __pred ( __f[__k], __f[__i] )) 310 __k++; 311 __prefix [ __i ] = __k; 312 } 313 } 314 315 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 316 _BinaryPredicate __pred) 317 { 318 const std::size_t __count = _VSTD::distance(__f, __l); 319 vector<difference_type> & __suffix = *__suffix_.get(); 320 if (__count > 0) 321 { 322 _VSTD::vector<value_type> __scratch(__count); 323 324 __compute_bm_prefix(__f, __l, __pred, __scratch); 325 for ( std::size_t __i = 0; __i <= __count; __i++ ) 326 __suffix[__i] = __count - __scratch[__count-1]; 327 328 typedef _VSTD::reverse_iterator<_RandomAccessIterator1> _RevIter; 329 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch); 330 331 for ( std::size_t __i = 0; __i < __count; __i++ ) 332 { 333 const std::size_t __j = __count - __scratch[__i]; 334 const difference_type __k = __i - __scratch[__i] + 1; 335 336 if (__suffix[__j] > __k) 337 __suffix[__j] = __k; 338 } 339 } 340 } 341 342}; 343 344template<class _RandomAccessIterator, 345 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 346 class _BinaryPredicate = equal_to<>> 347_LIBCPP_INLINE_VISIBILITY 348boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 349make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 350 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 351{ 352 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 353} 354 355// boyer-moore-horspool 356template <class _RandomAccessIterator1, 357 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 358 class _BinaryPredicate = equal_to<>> 359_LIBCPP_TYPE_VIS 360class boyer_moore_horspool_searcher { 361private: 362 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 363 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 364 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 365 _VSTD::is_integral<value_type>::value && // what about enums? 366 sizeof(value_type) == 1 && 367 is_same<_Hash, hash<value_type>>::value && 368 is_same<_BinaryPredicate, equal_to<>>::value 369 > skip_table_type; 370 371public: 372 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 373 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 374 : __first_(__f), __last_(__l), __pred_(__pred), 375 __pattern_length_(_VSTD::distance(__first_, __last_)), 376 __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)} 377 { 378 // build the skip table 379 if ( __f != __l ) 380 { 381 __l = __l - 1; 382 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 383 __skip_->insert(*__f, __pattern_length_ - 1 - __i); 384 } 385 } 386 387 template <typename _RandomAccessIterator2> 388 _RandomAccessIterator2 389 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 390 { 391 static_assert ( std::is_same< 392 typename std::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 393 typename std::decay<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 394 >::value, 395 "Corpus and Pattern iterators must point to the same type" ); 396 397 if (__f == __l ) return __l; // empty corpus 398 if (__first_ == __last_) return __f; // empty pattern 399 400 // If the pattern is larger than the corpus, we can't find it! 401 if ( __pattern_length_ > _VSTD::distance (__f, __l)) 402 return __l; 403 404 // Do the search 405 return this->__search(__f, __l); 406 } 407 408private: 409 _RandomAccessIterator1 __first_; 410 _RandomAccessIterator1 __last_; 411 _BinaryPredicate __pred_; 412 difference_type __pattern_length_; 413 shared_ptr<skip_table_type> __skip_; 414 415 template <typename _RandomAccessIterator2> 416 _RandomAccessIterator2 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { 417 _RandomAccessIterator2 __cur = __f; 418 const _RandomAccessIterator2 __last = __l - __pattern_length_; 419 const skip_table_type & __skip = *__skip_.get(); 420 421 while (__cur <= __last) 422 { 423 // Do we match right where we are? 424 difference_type __j = __pattern_length_; 425 while (__pred_(__first_[__j-1], __cur[__j-1])) 426 { 427 __j--; 428 // We matched - we're done! 429 if ( __j == 0 ) 430 return __cur; 431 } 432 __cur += __skip[__cur[__pattern_length_-1]]; 433 } 434 435 return __l; 436 } 437}; 438 439template<class _RandomAccessIterator, 440 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 441 class _BinaryPredicate = equal_to<>> 442_LIBCPP_INLINE_VISIBILITY 443boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 444make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 445 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 446{ 447 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 448} 449 450#endif // _LIBCPP_STD_VER > 11 451 452_LIBCPP_END_NAMESPACE_LFTS 453 454#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */ 455