contrib/llvm-project/libcxx/include/experimental/functional

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