Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
18 kB · 462 lines
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463// -*- C++ -*-//===-------------------------- functional --------------------------------===////// The LLVM Compiler Infrastructure//// This file is dual licensed under the MIT and the University of Illinois Open// Source Licenses. See LICENSE.TXT for details.////===----------------------------------------------------------------------===//#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 searchertemplate<class _ForwardIterator, class _BinaryPredicate = equal_to<>>_LIBCPP_TYPE_VISclass 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_VISIBILITYdefault_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 maptemplate<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 arraytemplate<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<>>_LIBCPP_TYPE_VISclass 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::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, typename std::decay<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_VISIBILITYboyer_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-horspooltemplate <class _RandomAccessIterator1, class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, class _BinaryPredicate = equal_to<>>_LIBCPP_TYPE_VISclass 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::decay<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, typename std::decay<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_VISIBILITYboyer_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 */