include/experimental/functional - third_party/libcxx - Git at Google

 // -*- 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 <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_TYPE_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 _VSTD::iterator_traits<_ForwardIterator>::iterator_category(),
             typename _VSTD::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(std::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 std::make_unsigned<key_type>::type unsigned_key_type;
     typedef std::array<value_type, _VSTD::numeric_limits<unsigned_key_type>::max()> skip_map;
     skip_map __table;

 public:
     _LIBCPP_INLINE_VISIBILITY
     _BMSkipTable(std::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_TYPE_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,
                     _VSTD::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 std::size_t __count = _VSTD::distance(__f, __l);

         __prefix[0] = 0;
         std::size_t __k = 0;
         for ( std::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 std::size_t __count = _VSTD::distance(__f, __l);
         vector<difference_type> & __suffix = *__suffix_.get();
         if (__count > 0)
         {
             _VSTD::vector<value_type> __scratch(__count);

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

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

             for ( std::size_t __i = 0; __i < __count; __i++ )
             {
                 const std::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_TYPE_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,
                     _VSTD::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 */
	// -- 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 <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_TYPE_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 _VSTD::iterator_traits<_ForwardIterator>::iterator_category(),
	typename _VSTD::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(std::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 std::make_unsigned<key_type>::type unsigned_key_type;
	typedef std::array<value_type, _VSTD::numeric_limits<unsigned_key_type>::max()> skip_map;
	skip_map __table;

	public:
	_LIBCPP_INLINE_VISIBILITY
	_BMSkipTable(std::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_TYPE_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,
	_VSTD::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 std::size_t __count = _VSTD::distance(__f, __l);

	__prefix[0] = 0;
	std::size_t __k = 0;
	for ( std::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 std::size_t __count = _VSTD::distance(__f, __l);
	vector<difference_type> & __suffix = *__suffix_.get();
	if (__count > 0)
	{
	_VSTD::vector<value_type> __scratch(__count);

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

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

	for ( std::size_t __i = 0; __i < __count; __i++ )
	{
	const std::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_TYPE_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,
	_VSTD::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 */