path: root/contrib/libs/cxxsupp/libcxx/include/experimental/functional

// -*- C++ -*- 
//===-------------------------- functional --------------------------------===// 
// 
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// 
//===----------------------------------------------------------------------===// 
 
#ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL 
#define _LIBCPP_EXPERIMENTAL_FUNCTIONAL 
 
/* 
   experimental/functional synopsis 
 
#include <algorithm> 
 
namespace std { 
namespace experimental { 
inline namespace fundamentals_v1 { 
 
    // See C++14 20.9.9, Function object binders 
    template <class T> constexpr bool is_bind_expression_v 
      = is_bind_expression<T>::value; 
    template <class T> constexpr int is_placeholder_v 
      = is_placeholder<T>::value; 
 
    // 4.2, Class template function 
    template<class> class function; // undefined 
    template<class R, class... ArgTypes> class function<R(ArgTypes...)>; 
 
    template<class R, class... ArgTypes> 
    void swap(function<R(ArgTypes...)>&, function<R(ArgTypes...)>&); 
 
    template<class R, class... ArgTypes> 
    bool operator==(const function<R(ArgTypes...)>&, nullptr_t) noexcept; 
    template<class R, class... ArgTypes> 
    bool operator==(nullptr_t, const function<R(ArgTypes...)>&) noexcept; 
    template<class R, class... ArgTypes> 
    bool operator!=(const function<R(ArgTypes...)>&, nullptr_t) noexcept; 
    template<class R, class... ArgTypes> 
    bool operator!=(nullptr_t, const function<R(ArgTypes...)>&) noexcept; 
 
    // 4.3, Searchers 
    template<class ForwardIterator, class BinaryPredicate = equal_to<>> 
      class default_searcher; 
 
    template<class RandomAccessIterator, 
             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 
             class BinaryPredicate = equal_to<>> 
      class boyer_moore_searcher; 
 
    template<class RandomAccessIterator, 
             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 
             class BinaryPredicate = equal_to<>> 
      class boyer_moore_horspool_searcher; 
 
    template<class ForwardIterator, class BinaryPredicate = equal_to<>> 
    default_searcher<ForwardIterator, BinaryPredicate> 
    make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last, 
                          BinaryPredicate pred = BinaryPredicate()); 
 
    template<class RandomAccessIterator, 
             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 
             class BinaryPredicate = equal_to<>> 
    boyer_moore_searcher<RandomAccessIterator, Hash, BinaryPredicate> 
    make_boyer_moore_searcher( 
        RandomAccessIterator pat_first, RandomAccessIterator pat_last, 
        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 
 
    template<class RandomAccessIterator, 
             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 
             class BinaryPredicate = equal_to<>> 
    boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate> 
    make_boyer_moore_horspool_searcher( 
        RandomAccessIterator pat_first, RandomAccessIterator pat_last, 
        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 
 
  } // namespace fundamentals_v1 
  } // namespace experimental 
 
  template<class R, class... ArgTypes, class Alloc> 
  struct uses_allocator<experimental::function<R(ArgTypes...)>, Alloc>; 
 
} // namespace std 
 
*/ 
 
#include <__memory/uses_allocator.h> 
#include <experimental/__config> 
#include <functional> 
#include <algorithm> 
#include <type_traits> 
#include <vector> 
#include <array> 
#include <unordered_map> 
 
#include <__debug> 
 
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 
#pragma GCC system_header 
#endif 
 
_LIBCPP_PUSH_MACROS 
#include <__undef_macros> 
 
 
_LIBCPP_BEGIN_NAMESPACE_LFTS 
 
#if _LIBCPP_STD_VER > 11 
// default searcher 
template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 
class _LIBCPP_TEMPLATE_VIS default_searcher { 
public: 
    _LIBCPP_INLINE_VISIBILITY 
    default_searcher(_ForwardIterator __f, _ForwardIterator __l,
                       _BinaryPredicate __p = _BinaryPredicate()) 
        : __first_(__f), __last_(__l), __pred_(__p) {} 
 
    template <typename _ForwardIterator2> 
    _LIBCPP_INLINE_VISIBILITY 
    pair<_ForwardIterator2, _ForwardIterator2> 
    operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const 
    { 
        return _VSTD::__search(__f, __l, __first_, __last_, __pred_, 
            typename iterator_traits<_ForwardIterator>::iterator_category(), 
            typename iterator_traits<_ForwardIterator2>::iterator_category()); 
    } 
 
private: 
    _ForwardIterator __first_; 
    _ForwardIterator __last_; 
    _BinaryPredicate __pred_; 
    }; 
 
template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 
_LIBCPP_INLINE_VISIBILITY 
default_searcher<_ForwardIterator, _BinaryPredicate> 
make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ()) 
{ 
    return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p); 
} 
 
template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable; 
 
//  General case for BM data searching; use a map 
template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 
class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> { 
public: // TODO private: 
    typedef _Value value_type; 
    typedef _Key   key_type; 
 
    const _Value __default_value_; 
    std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table; 

public: 
    _LIBCPP_INLINE_VISIBILITY 
    _BMSkipTable(size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred) 
        : __default_value_(__default), __table(__sz, __hf, __pred) {} 

    _LIBCPP_INLINE_VISIBILITY 
    void insert(const key_type &__key, value_type __val) 
    { 
        __table [__key] = __val;    // Would skip_.insert (val) be better here? 
    } 
 
    _LIBCPP_INLINE_VISIBILITY 
    value_type operator [](const key_type & __key) const 
    { 
        auto __it = __table.find (__key); 
        return __it == __table.end() ? __default_value_ : __it->second; 
    } 
}; 
 

//  Special case small numeric values; use an array 
template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 
class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> { 
private: 
    typedef _Value value_type; 
    typedef _Key   key_type; 
 
    typedef typename make_unsigned<key_type>::type unsigned_key_type; 
    typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map; 
    skip_map __table; 
 
public: 
    _LIBCPP_INLINE_VISIBILITY 
    _BMSkipTable(size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/) 
    { 
        std::fill_n(__table.begin(), __table.size(), __default); 
    } 

    _LIBCPP_INLINE_VISIBILITY 
    void insert(key_type __key, value_type __val) 
    { 
        __table[static_cast<unsigned_key_type>(__key)] = __val; 
    } 
 
    _LIBCPP_INLINE_VISIBILITY 
    value_type operator [](key_type __key) const 
    { 
        return __table[static_cast<unsigned_key_type>(__key)]; 
    } 
}; 
 
 
template <class _RandomAccessIterator1,
          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
          class _BinaryPredicate = equal_to<>> 
class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher { 
private: 
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 
    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type; 
    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 
                    is_integral<value_type>::value && // what about enums? 
                    sizeof(value_type) == 1 && 
                    is_same<_Hash, hash<value_type>>::value && 
                    is_same<_BinaryPredicate, equal_to<>>::value 
            > skip_table_type; 

public: 
    boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 
            : __first_(__f), __last_(__l), __pred_(__pred), 
              __pattern_length_(_VSTD::distance(__first_, __last_)), 
              __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)}, 
              __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)} 
        { 
    //  build the skip table 
        for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 
            __skip_->insert(*__f, __i); 
 
        this->__build_suffix_table ( __first_, __last_, __pred_ ); 
        } 

    template <typename _RandomAccessIterator2> 
    pair<_RandomAccessIterator2, _RandomAccessIterator2> 
    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 
    { 
        static_assert ( std::is_same< 
                typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
                typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 
                    >::value, 
                "Corpus and Pattern iterators must point to the same type" ); 
 
        if (__f      == __l )    return make_pair(__l, __l); // empty corpus 
        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 
 
    //  If the pattern is larger than the corpus, we can't find it! 
        if ( __pattern_length_ > _VSTD::distance(__f, __l)) 
            return make_pair(__l, __l); 
 
    //  Do the search
        return this->__search(__f, __l); 
    } 

public: // TODO private: 
    _RandomAccessIterator1               __first_; 
    _RandomAccessIterator1               __last_; 
    _BinaryPredicate                     __pred_; 
    difference_type                      __pattern_length_; 
    shared_ptr<skip_table_type>          __skip_; 
    shared_ptr<vector<difference_type>>  __suffix_; 
 
    template <typename _RandomAccessIterator2> 
    pair<_RandomAccessIterator2, _RandomAccessIterator2> 
    __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 
    { 
        _RandomAccessIterator2 __cur = __f; 
        const _RandomAccessIterator2 __last = __l - __pattern_length_; 
        const skip_table_type &         __skip   = *__skip_.get(); 
        const vector<difference_type> & __suffix = *__suffix_.get(); 

        while (__cur <= __last) 
        { 
 
        //  Do we match right where we are? 
            difference_type __j = __pattern_length_; 
            while (__pred_(__first_ [__j-1], __cur [__j-1])) { 
                __j--; 
            //  We matched - we're done! 
                if ( __j == 0 ) 
                    return make_pair(__cur, __cur + __pattern_length_); 
                } 

        //  Since we didn't match, figure out how far to skip forward 
            difference_type __k = __skip[__cur [ __j - 1 ]]; 
            difference_type __m = __j - __k - 1; 
            if (__k < __j && __m > __suffix[ __j ]) 
                __cur += __m; 
            else 
                __cur += __suffix[ __j ]; 
        } 

        return make_pair(__l, __l);     // We didn't find anything 
    } 
 
 
    template<typename _Iterator, typename _Container> 
    void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) 
    { 
        const size_t __count = _VSTD::distance(__f, __l); 

        __prefix[0] = 0; 
        size_t __k = 0; 
        for ( size_t __i = 1; __i < __count; ++__i ) 
        { 
            while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) 
                __k = __prefix [ __k - 1 ]; 

            if ( __pred ( __f[__k], __f[__i] )) 
                __k++; 
            __prefix [ __i ] = __k; 
        } 
    } 
 
    void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
                                                    _BinaryPredicate __pred) 
    { 
        const size_t __count = _VSTD::distance(__f, __l); 
        vector<difference_type> & __suffix = *__suffix_.get(); 
        if (__count > 0) 
        { 
            vector<value_type> __scratch(__count); 

            __compute_bm_prefix(__f, __l, __pred, __scratch); 
            for ( size_t __i = 0; __i <= __count; __i++ ) 
                __suffix[__i] = __count - __scratch[__count-1]; 

            typedef reverse_iterator<_RandomAccessIterator1> _RevIter; 
            __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch); 

            for ( size_t __i = 0; __i < __count; __i++ ) 
            { 
                const size_t     __j = __count - __scratch[__i]; 
                const difference_type __k = __i     - __scratch[__i] + 1; 

                if (__suffix[__j] > __k) 
                    __suffix[__j] = __k; 
            } 
        } 
    } 
 
}; 
 
template<class _RandomAccessIterator,
         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
         class _BinaryPredicate = equal_to<>> 
_LIBCPP_INLINE_VISIBILITY 
boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 
make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 
{ 
    return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 
} 
 
// boyer-moore-horspool 
template <class _RandomAccessIterator1,
          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
          class _BinaryPredicate = equal_to<>> 
class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher { 
private: 
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 
    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type; 
    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 
                    is_integral<value_type>::value && // what about enums? 
                    sizeof(value_type) == 1 && 
                    is_same<_Hash, hash<value_type>>::value && 
                    is_same<_BinaryPredicate, equal_to<>>::value 
            > skip_table_type; 
 
public: 
    boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 
            : __first_(__f), __last_(__l), __pred_(__pred), 
              __pattern_length_(_VSTD::distance(__first_, __last_)), 
              __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)} 
        { 
    //  build the skip table 
            if ( __f != __l ) 
            { 
                __l = __l - 1; 
                for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 
                    __skip_->insert(*__f, __pattern_length_ - 1 - __i); 
            } 
        } 

    template <typename _RandomAccessIterator2> 
    pair<_RandomAccessIterator2, _RandomAccessIterator2> 
    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 
    { 
        static_assert ( std::is_same< 
                typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type,
                typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 
                    >::value, 
                "Corpus and Pattern iterators must point to the same type" ); 
 
        if (__f      == __l )    return make_pair(__l, __l); // empty corpus 
        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 
 
    //  If the pattern is larger than the corpus, we can't find it! 
        if ( __pattern_length_ > _VSTD::distance(__f, __l)) 
            return make_pair(__l, __l); 
 
    //  Do the search
        return this->__search(__f, __l); 
    } 

private: 
    _RandomAccessIterator1      __first_; 
    _RandomAccessIterator1      __last_; 
    _BinaryPredicate            __pred_; 
    difference_type             __pattern_length_; 
    shared_ptr<skip_table_type> __skip_; 
 
    template <typename _RandomAccessIterator2> 
    pair<_RandomAccessIterator2, _RandomAccessIterator2> 
    __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { 
        _RandomAccessIterator2 __cur = __f; 
        const _RandomAccessIterator2 __last = __l - __pattern_length_; 
        const skip_table_type & __skip = *__skip_.get(); 
 
        while (__cur <= __last) 
        { 
        //  Do we match right where we are? 
            difference_type __j = __pattern_length_; 
            while (__pred_(__first_[__j-1], __cur[__j-1])) 
            { 
                __j--; 
            //  We matched - we're done! 
                if ( __j == 0 ) 
                    return make_pair(__cur, __cur + __pattern_length_); 
            } 
            __cur += __skip[__cur[__pattern_length_-1]]; 
        } 

        return make_pair(__l, __l); 
    } 
}; 
 
template<class _RandomAccessIterator,
         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
         class _BinaryPredicate = equal_to<>> 
_LIBCPP_INLINE_VISIBILITY 
boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 
make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 
{ 
    return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 
} 
 
#endif // _LIBCPP_STD_VER > 11 
 
_LIBCPP_END_NAMESPACE_LFTS 
 
_LIBCPP_POP_MACROS 
 
#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */