• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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::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
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::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
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