contrib/libc++/include/experimental/functional

   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
  19 namespace std {
  20 namespace experimental {
  21 inline 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
 112 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
 113 _LIBCPP_TYPE_VIS
 114 class default_searcher {
 115 public:
 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
 131 private:
 132     _ForwardIterator __first_;
 133     _ForwardIterator __last_;
 134     _BinaryPredicate __pred_;
 135     };
 136
 137 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
 138 _LIBCPP_INLINE_VISIBILITY
 139 default_searcher<_ForwardIterator, _BinaryPredicate>
 140 make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())
 141 {
 142     return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);
 143 }
 144
 145 template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;
 146
 147 //  General case for BM data searching; use a map
 148 template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
 149 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
 150 public: // 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
 157 public:
 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
 178 template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
 179 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
 180 private:
 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
 188 public:
 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
 209 template <class _RandomAccessIterator1,
 210           class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
 211           class _BinaryPredicate = equal_to<>>
 212 _LIBCPP_TYPE_VIS
 213 class boyer_moore_searcher {
 214 private:
 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
 224 public:
 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::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
 245                 typename std::decay<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
 260 public: // 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
 349 template<class _RandomAccessIterator,
 350          class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
 351          class _BinaryPredicate = equal_to<>>
 352 _LIBCPP_INLINE_VISIBILITY
 353 boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
 354 make_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
 361 template <class _RandomAccessIterator1,
 362           class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
 363           class _BinaryPredicate = equal_to<>>
 364 _LIBCPP_TYPE_VIS
 365 class boyer_moore_horspool_searcher {
 366 private:
 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
 376 public:
 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::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
 398                 typename std::decay<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
 413 private:
 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
 445 template<class _RandomAccessIterator,
 446          class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
 447          class _BinaryPredicate = equal_to<>>
 448 _LIBCPP_INLINE_VISIBILITY
 449 boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
 450 make_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 */