2 //===-------------------------- functional --------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL
12 #define _LIBCPP_EXPERIMENTAL_FUNCTIONAL
15 experimental/functional synopsis
20 namespace experimental {
21 inline namespace fundamentals_v1 {
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;
29 // 4.2, Class template function
30 template<class> class function; // undefined
31 template<class R, class... ArgTypes> class function<R(ArgTypes...)>;
33 template<class R, class... ArgTypes>
34 void swap(function<R(ArgTypes...)>&, function<R(ArgTypes...)>&);
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;
46 template<class ForwardIterator, class BinaryPredicate = equal_to<>>
47 class default_searcher;
49 template<class RandomAccessIterator,
50 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
51 class BinaryPredicate = equal_to<>>
52 class boyer_moore_searcher;
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;
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());
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());
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());
80 } // namespace fundamentals_v1
81 } // namespace experimental
83 template<class R, class... ArgTypes, class Alloc>
84 struct uses_allocator<experimental::function<R(ArgTypes...)>, Alloc>;
90 #include <experimental/__config>
94 #include <type_traits>
97 #include <unordered_map>
99 #include <__undef_min_max>
103 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
104 #pragma GCC system_header
107 _LIBCPP_BEGIN_NAMESPACE_LFTS
109 #if _LIBCPP_STD_VER > 11
111 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
113 class default_searcher {
115 _LIBCPP_INLINE_VISIBILITY
116 default_searcher(_ForwardIterator __f, _ForwardIterator __l,
117 _BinaryPredicate __p = _BinaryPredicate())
118 : __first_(__f), __last_(__l), __pred_(__p) {}
120 template <typename _ForwardIterator2>
121 _LIBCPP_INLINE_VISIBILITY
122 pair<_ForwardIterator2, _ForwardIterator2>
123 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
125 return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
126 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category(),
127 typename _VSTD::iterator_traits<_ForwardIterator2>::iterator_category());
131 _ForwardIterator __first_;
132 _ForwardIterator __last_;
133 _BinaryPredicate __pred_;
136 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
137 _LIBCPP_INLINE_VISIBILITY
138 default_searcher<_ForwardIterator, _BinaryPredicate>
139 make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())
141 return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);
144 template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;
146 // General case for BM data searching; use a map
147 template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
148 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
149 public: // TODO private:
150 typedef _Value value_type;
151 typedef _Key key_type;
153 const _Value __default_value_;
154 std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table;
157 _LIBCPP_INLINE_VISIBILITY
158 _BMSkipTable(std::size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred)
159 : __default_value_(__default), __table(__sz, __hf, __pred) {}
161 _LIBCPP_INLINE_VISIBILITY
162 void insert(const key_type &__key, value_type __val)
164 __table [__key] = __val; // Would skip_.insert (val) be better here?
167 _LIBCPP_INLINE_VISIBILITY
168 value_type operator [](const key_type & __key) const
170 auto __it = __table.find (__key);
171 return __it == __table.end() ? __default_value_ : __it->second;
176 // Special case small numeric values; use an array
177 template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
178 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
180 typedef _Value value_type;
181 typedef _Key key_type;
183 typedef typename std::make_unsigned<key_type>::type unsigned_key_type;
184 typedef std::array<value_type, _VSTD::numeric_limits<unsigned_key_type>::max()> skip_map;
188 _LIBCPP_INLINE_VISIBILITY
189 _BMSkipTable(std::size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/)
191 std::fill_n(__table.begin(), __table.size(), __default);
194 _LIBCPP_INLINE_VISIBILITY
195 void insert(key_type __key, value_type __val)
197 __table[static_cast<unsigned_key_type>(__key)] = __val;
200 _LIBCPP_INLINE_VISIBILITY
201 value_type operator [](key_type __key) const
203 return __table[static_cast<unsigned_key_type>(__key)];
208 template <class _RandomAccessIterator1,
209 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
210 class _BinaryPredicate = equal_to<>>
212 class boyer_moore_searcher {
214 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
215 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type;
216 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
217 _VSTD::is_integral<value_type>::value && // what about enums?
218 sizeof(value_type) == 1 &&
219 is_same<_Hash, hash<value_type>>::value &&
220 is_same<_BinaryPredicate, equal_to<>>::value
224 boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
225 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
226 : __first_(__f), __last_(__l), __pred_(__pred),
227 __pattern_length_(_VSTD::distance(__first_, __last_)),
228 __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)},
229 __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)}
231 // build the skip table
232 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
233 __skip_->insert(*__f, __i);
235 this->__build_suffix_table ( __first_, __last_, __pred_ );
238 template <typename _RandomAccessIterator2>
239 pair<_RandomAccessIterator2, _RandomAccessIterator2>
240 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
242 static_assert ( std::is_same<
243 typename std::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
244 typename std::decay<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type
246 "Corpus and Pattern iterators must point to the same type" );
248 if (__f == __l ) return make_pair(__l, __l); // empty corpus
249 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
251 // If the pattern is larger than the corpus, we can't find it!
252 if ( __pattern_length_ > _VSTD::distance (__f, __l))
253 return make_pair(__l, __l);
256 return this->__search(__f, __l);
259 public: // TODO private:
260 _RandomAccessIterator1 __first_;
261 _RandomAccessIterator1 __last_;
262 _BinaryPredicate __pred_;
263 difference_type __pattern_length_;
264 shared_ptr<skip_table_type> __skip_;
265 shared_ptr<vector<difference_type>> __suffix_;
267 template <typename _RandomAccessIterator2>
268 pair<_RandomAccessIterator2, _RandomAccessIterator2>
269 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
271 _RandomAccessIterator2 __cur = __f;
272 const _RandomAccessIterator2 __last = __l - __pattern_length_;
273 const skip_table_type & __skip = *__skip_.get();
274 const vector<difference_type> & __suffix = *__suffix_.get();
276 while (__cur <= __last)
279 // Do we match right where we are?
280 difference_type __j = __pattern_length_;
281 while (__pred_(__first_ [__j-1], __cur [__j-1])) {
283 // We matched - we're done!
285 return make_pair(__cur, __cur + __pattern_length_);
288 // Since we didn't match, figure out how far to skip forward
289 difference_type __k = __skip[__cur [ __j - 1 ]];
290 difference_type __m = __j - __k - 1;
291 if (__k < __j && __m > __suffix[ __j ])
294 __cur += __suffix[ __j ];
297 return make_pair(__l, __l); // We didn't find anything
301 template<typename _Iterator, typename _Container>
302 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix )
304 const std::size_t __count = _VSTD::distance(__f, __l);
308 for ( std::size_t __i = 1; __i < __count; ++__i )
310 while ( __k > 0 && !__pred ( __f[__k], __f[__i] ))
311 __k = __prefix [ __k - 1 ];
313 if ( __pred ( __f[__k], __f[__i] ))
315 __prefix [ __i ] = __k;
319 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
320 _BinaryPredicate __pred)
322 const std::size_t __count = _VSTD::distance(__f, __l);
323 vector<difference_type> & __suffix = *__suffix_.get();
326 _VSTD::vector<value_type> __scratch(__count);
328 __compute_bm_prefix(__f, __l, __pred, __scratch);
329 for ( std::size_t __i = 0; __i <= __count; __i++ )
330 __suffix[__i] = __count - __scratch[__count-1];
332 typedef _VSTD::reverse_iterator<_RandomAccessIterator1> _RevIter;
333 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch);
335 for ( std::size_t __i = 0; __i < __count; __i++ )
337 const std::size_t __j = __count - __scratch[__i];
338 const difference_type __k = __i - __scratch[__i] + 1;
340 if (__suffix[__j] > __k)
348 template<class _RandomAccessIterator,
349 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
350 class _BinaryPredicate = equal_to<>>
351 _LIBCPP_INLINE_VISIBILITY
352 boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
353 make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
354 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
356 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
359 // boyer-moore-horspool
360 template <class _RandomAccessIterator1,
361 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
362 class _BinaryPredicate = equal_to<>>
364 class boyer_moore_horspool_searcher {
366 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
367 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type;
368 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
369 _VSTD::is_integral<value_type>::value && // what about enums?
370 sizeof(value_type) == 1 &&
371 is_same<_Hash, hash<value_type>>::value &&
372 is_same<_BinaryPredicate, equal_to<>>::value
376 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
377 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
378 : __first_(__f), __last_(__l), __pred_(__pred),
379 __pattern_length_(_VSTD::distance(__first_, __last_)),
380 __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)}
382 // build the skip table
386 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
387 __skip_->insert(*__f, __pattern_length_ - 1 - __i);
391 template <typename _RandomAccessIterator2>
392 pair<_RandomAccessIterator2, _RandomAccessIterator2>
393 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
395 static_assert ( std::is_same<
396 typename std::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
397 typename std::decay<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type
399 "Corpus and Pattern iterators must point to the same type" );
401 if (__f == __l ) return make_pair(__l, __l); // empty corpus
402 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
404 // If the pattern is larger than the corpus, we can't find it!
405 if ( __pattern_length_ > _VSTD::distance (__f, __l))
406 return make_pair(__l, __l);
409 return this->__search(__f, __l);
413 _RandomAccessIterator1 __first_;
414 _RandomAccessIterator1 __last_;
415 _BinaryPredicate __pred_;
416 difference_type __pattern_length_;
417 shared_ptr<skip_table_type> __skip_;
419 template <typename _RandomAccessIterator2>
420 pair<_RandomAccessIterator2, _RandomAccessIterator2>
421 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const {
422 _RandomAccessIterator2 __cur = __f;
423 const _RandomAccessIterator2 __last = __l - __pattern_length_;
424 const skip_table_type & __skip = *__skip_.get();
426 while (__cur <= __last)
428 // Do we match right where we are?
429 difference_type __j = __pattern_length_;
430 while (__pred_(__first_[__j-1], __cur[__j-1]))
433 // We matched - we're done!
435 return make_pair(__cur, __cur + __pattern_length_);
437 __cur += __skip[__cur[__pattern_length_-1]];
440 return make_pair(__l, __l);
444 template<class _RandomAccessIterator,
445 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
446 class _BinaryPredicate = equal_to<>>
447 _LIBCPP_INLINE_VISIBILITY
448 boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
449 make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
450 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
452 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
455 #endif // _LIBCPP_STD_VER > 11
457 _LIBCPP_END_NAMESPACE_LFTS
459 #endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */