diff options
Diffstat (limited to 'tests/libcxx/include/algorithm')
| -rw-r--r-- | tests/libcxx/include/algorithm | 5331 |
1 files changed, 0 insertions, 5331 deletions
diff --git a/tests/libcxx/include/algorithm b/tests/libcxx/include/algorithm deleted file mode 100644 index a3764dfd..00000000 --- a/tests/libcxx/include/algorithm +++ /dev/null @@ -1,5331 +0,0 @@ -// -*- C++ -*- -//===-------------------------- algorithm ---------------------------------===// -// -// 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_ALGORITHM -#define _LIBCPP_ALGORITHM - -/* - algorithm synopsis - -#include <initializer_list> - -namespace std -{ - -template <class InputIterator, class Predicate> - bool - all_of(InputIterator first, InputIterator last, Predicate pred); - -template <class InputIterator, class Predicate> - bool - any_of(InputIterator first, InputIterator last, Predicate pred); - -template <class InputIterator, class Predicate> - bool - none_of(InputIterator first, InputIterator last, Predicate pred); - -template <class InputIterator, class Function> - Function - for_each(InputIterator first, InputIterator last, Function f); - -template <class InputIterator, class T> - InputIterator - find(InputIterator first, InputIterator last, const T& value); - -template <class InputIterator, class Predicate> - InputIterator - find_if(InputIterator first, InputIterator last, Predicate pred); - -template<class InputIterator, class Predicate> - InputIterator - find_if_not(InputIterator first, InputIterator last, Predicate pred); - -template <class ForwardIterator1, class ForwardIterator2> - ForwardIterator1 - find_end(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2); - -template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> - ForwardIterator1 - find_end(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); - -template <class ForwardIterator1, class ForwardIterator2> - ForwardIterator1 - find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2); - -template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> - ForwardIterator1 - find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); - -template <class ForwardIterator> - ForwardIterator - adjacent_find(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class BinaryPredicate> - ForwardIterator - adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); - -template <class InputIterator, class T> - typename iterator_traits<InputIterator>::difference_type - count(InputIterator first, InputIterator last, const T& value); - -template <class InputIterator, class Predicate> - typename iterator_traits<InputIterator>::difference_type - count_if(InputIterator first, InputIterator last, Predicate pred); - -template <class InputIterator1, class InputIterator2> - pair<InputIterator1, InputIterator2> - mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); - -template <class InputIterator1, class InputIterator2, class BinaryPredicate> - pair<InputIterator1, InputIterator2> - mismatch(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, BinaryPredicate pred); - -template <class InputIterator1, class InputIterator2> - bool - equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); - -template <class InputIterator1, class InputIterator2, class BinaryPredicate> - bool - equal(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, BinaryPredicate pred); - -template<class ForwardIterator1, class ForwardIterator2> - bool - is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2); - -template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> - bool - is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, BinaryPredicate pred); - -template <class ForwardIterator1, class ForwardIterator2> - ForwardIterator1 - search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2); - -template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> - ForwardIterator1 - search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); - -template <class ForwardIterator, class Size, class T> - ForwardIterator - search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); - -template <class ForwardIterator, class Size, class T, class BinaryPredicate> - ForwardIterator - search_n(ForwardIterator first, ForwardIterator last, - Size count, const T& value, BinaryPredicate pred); - -template <class InputIterator, class OutputIterator> - OutputIterator - copy(InputIterator first, InputIterator last, OutputIterator result); - -template<class InputIterator, class OutputIterator, class Predicate> - OutputIterator - copy_if(InputIterator first, InputIterator last, - OutputIterator result, Predicate pred); - -template<class InputIterator, class Size, class OutputIterator> - OutputIterator - copy_n(InputIterator first, Size n, OutputIterator result); - -template <class BidirectionalIterator1, class BidirectionalIterator2> - BidirectionalIterator2 - copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, - BidirectionalIterator2 result); - -template <class ForwardIterator1, class ForwardIterator2> - ForwardIterator2 - swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); - -template <class ForwardIterator1, class ForwardIterator2> - void - iter_swap(ForwardIterator1 a, ForwardIterator2 b); - -template <class InputIterator, class OutputIterator, class UnaryOperation> - OutputIterator - transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> - OutputIterator - transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, - OutputIterator result, BinaryOperation binary_op); - -template <class ForwardIterator, class T> - void - replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); - -template <class ForwardIterator, class Predicate, class T> - void - replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); - -template <class InputIterator, class OutputIterator, class T> - OutputIterator - replace_copy(InputIterator first, InputIterator last, OutputIterator result, - const T& old_value, const T& new_value); - -template <class InputIterator, class OutputIterator, class Predicate, class T> - OutputIterator - replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); - -template <class ForwardIterator, class T> - void - fill(ForwardIterator first, ForwardIterator last, const T& value); - -template <class OutputIterator, class Size, class T> - OutputIterator - fill_n(OutputIterator first, Size n, const T& value); - -template <class ForwardIterator, class Generator> - void - generate(ForwardIterator first, ForwardIterator last, Generator gen); - -template <class OutputIterator, class Size, class Generator> - OutputIterator - generate_n(OutputIterator first, Size n, Generator gen); - -template <class ForwardIterator, class T> - ForwardIterator - remove(ForwardIterator first, ForwardIterator last, const T& value); - -template <class ForwardIterator, class Predicate> - ForwardIterator - remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); - -template <class InputIterator, class OutputIterator, class T> - OutputIterator - remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); - -template <class InputIterator, class OutputIterator, class Predicate> - OutputIterator - remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); - -template <class ForwardIterator> - ForwardIterator - unique(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class BinaryPredicate> - ForwardIterator - unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); - -template <class InputIterator, class OutputIterator> - OutputIterator - unique_copy(InputIterator first, InputIterator last, OutputIterator result); - -template <class InputIterator, class OutputIterator, class BinaryPredicate> - OutputIterator - unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); - -template <class BidirectionalIterator> - void - reverse(BidirectionalIterator first, BidirectionalIterator last); - -template <class BidirectionalIterator, class OutputIterator> - OutputIterator - reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); - -template <class ForwardIterator> - ForwardIterator - rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); - -template <class ForwardIterator, class OutputIterator> - OutputIterator - rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); - -template <class RandomAccessIterator> - void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class RandomNumberGenerator> - void - random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); - -template<class RandomAccessIterator, class UniformRandomNumberGenerator> - void shuffle(RandomAccessIterator first, RandomAccessIterator last, - UniformRandomNumberGenerator&& g); - -template <class InputIterator, class Predicate> - bool - is_partitioned(InputIterator first, InputIterator last, Predicate pred); - -template <class ForwardIterator, class Predicate> - ForwardIterator - partition(ForwardIterator first, ForwardIterator last, Predicate pred); - -template <class InputIterator, class OutputIterator1, - class OutputIterator2, class Predicate> - pair<OutputIterator1, OutputIterator2> - partition_copy(InputIterator first, InputIterator last, - OutputIterator1 out_true, OutputIterator2 out_false, - Predicate pred); - -template <class ForwardIterator, class Predicate> - ForwardIterator - stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); - -template<class ForwardIterator, class Predicate> - ForwardIterator - partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); - -template <class ForwardIterator> - bool - is_sorted(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class Compare> - bool - is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); - -template<class ForwardIterator> - ForwardIterator - is_sorted_until(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class Compare> - ForwardIterator - is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); - -template <class RandomAccessIterator> - void - sort(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - void - stable_sort(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - void - partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); - -template <class InputIterator, class RandomAccessIterator> - RandomAccessIterator - partial_sort_copy(InputIterator first, InputIterator last, - RandomAccessIterator result_first, RandomAccessIterator result_last); - -template <class InputIterator, class RandomAccessIterator, class Compare> - RandomAccessIterator - partial_sort_copy(InputIterator first, InputIterator last, - RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); - -template <class RandomAccessIterator> - void - nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); - -template <class ForwardIterator, class T> - ForwardIterator - lower_bound(ForwardIterator first, ForwardIterator last, const T& value); - -template <class ForwardIterator, class T, class Compare> - ForwardIterator - lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); - -template <class ForwardIterator, class T> - ForwardIterator - upper_bound(ForwardIterator first, ForwardIterator last, const T& value); - -template <class ForwardIterator, class T, class Compare> - ForwardIterator - upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); - -template <class ForwardIterator, class T> - pair<ForwardIterator, ForwardIterator> - equal_range(ForwardIterator first, ForwardIterator last, const T& value); - -template <class ForwardIterator, class T, class Compare> - pair<ForwardIterator, ForwardIterator> - equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); - -template <class ForwardIterator, class T> - bool - binary_search(ForwardIterator first, ForwardIterator last, const T& value); - -template <class ForwardIterator, class T, class Compare> - bool - binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); - -template <class InputIterator1, class InputIterator2, class OutputIterator> - OutputIterator - merge(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> - OutputIterator - merge(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); - -template <class BidirectionalIterator> - void - inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); - -template <class BidirectionalIterator, class Compare> - void - inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); - -template <class InputIterator1, class InputIterator2> - bool - includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); - -template <class InputIterator1, class InputIterator2, class Compare> - bool - includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); - -template <class InputIterator1, class InputIterator2, class OutputIterator> - OutputIterator - set_union(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> - OutputIterator - set_union(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); - -template <class InputIterator1, class InputIterator2, class OutputIterator> - OutputIterator - set_intersection(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> - OutputIterator - set_intersection(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); - -template <class InputIterator1, class InputIterator2, class OutputIterator> - OutputIterator - set_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> - OutputIterator - set_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); - -template <class InputIterator1, class InputIterator2, class OutputIterator> - OutputIterator - set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result); - -template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> - OutputIterator - set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); - -template <class RandomAccessIterator> - void - push_heap(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - void - pop_heap(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - void - make_heap(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - void - sort_heap(RandomAccessIterator first, RandomAccessIterator last); - -template <class RandomAccessIterator, class Compare> - void - sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); - -template <class RandomAccessIterator> - bool - is_heap(RandomAccessIterator first, RandomAccessiterator last); - -template <class RandomAccessIterator, class Compare> - bool - is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); - -template <class RandomAccessIterator> - RandomAccessIterator - is_heap_until(RandomAccessIterator first, RandomAccessiterator last); - -template <class RandomAccessIterator, class Compare> - RandomAccessIterator - is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); - -template <class ForwardIterator> - ForwardIterator - min_element(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class Compare> - ForwardIterator - min_element(ForwardIterator first, ForwardIterator last, Compare comp); - -template <class T> - const T& - min(const T& a, const T& b); - -template <class T, class Compare> - const T& - min(const T& a, const T& b, Compare comp); - -template<class T> - T - min(initializer_list<T> t); - -template<class T, class Compare> - T - min(initializer_list<T> t, Compare comp); - -template <class ForwardIterator> - ForwardIterator - max_element(ForwardIterator first, ForwardIterator last); - -template <class ForwardIterator, class Compare> - ForwardIterator - max_element(ForwardIterator first, ForwardIterator last, Compare comp); - -template <class T> - const T& - max(const T& a, const T& b); - -template <class T, class Compare> - const T& - max(const T& a, const T& b, Compare comp); - -template<class T> - T - max(initializer_list<T> t); - -template<class T, class Compare> - T - max(initializer_list<T> t, Compare comp); - -template<class ForwardIterator> - pair<ForwardIterator, ForwardIterator> - minmax_element(ForwardIterator first, ForwardIterator last); - -template<class ForwardIterator, class Compare> - pair<ForwardIterator, ForwardIterator> - minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); - -template<class T> - pair<const T&, const T&> - minmax(const T& a, const T& b); - -template<class T, class Compare> - pair<const T&, const T&> - minmax(const T& a, const T& b, Compare comp); - -template<class T> - pair<T, T> - minmax(initializer_list<T> t); - -template<class T, class Compare> - pair<T, T> - minmax(initializer_list<T> t, Compare comp); - -template <class InputIterator1, class InputIterator2> - bool - lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); - -template <class InputIterator1, class InputIterator2, class Compare> - bool - lexicographical_compare(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, Compare comp); - -template <class BidirectionalIterator> - bool - next_permutation(BidirectionalIterator first, BidirectionalIterator last); - -template <class BidirectionalIterator, class Compare> - bool - next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); - -template <class BidirectionalIterator> - bool - prev_permutation(BidirectionalIterator first, BidirectionalIterator last); - -template <class BidirectionalIterator, class Compare> - bool - prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); - -} // std - -*/ - -#include <__config> -#include <initializer_list> -#include <type_traits> -#include <cstring> -#include <utility> -#include <memory> -#include <iterator> -#ifdef _LIBCPP_DEBUG -#include <cassert> -#endif -#include <cstdlib> - -#pragma GCC system_header - -_LIBCPP_BEGIN_NAMESPACE_STD - -template <class _T1, class _T2 = _T1> -struct __equal_to -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;} -}; - -template <class _T1> -struct __equal_to<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template <class _T1> -struct __equal_to<const _T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template <class _T1> -struct __equal_to<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} -}; - -template <class _T1, class _T2 = _T1> -struct __less -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} -}; - -template <class _T1> -struct __less<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template <class _T1> -struct __less<const _T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template <class _T1> -struct __less<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template <class _Predicate> -class __negate -{ -private: - _Predicate __p_; -public: - _LIBCPP_INLINE_VISIBILITY __negate() {} - - _LIBCPP_INLINE_VISIBILITY - explicit __negate(_Predicate __p) : __p_(__p) {} - - template <class _T1> - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x) {return !__p_(__x);} - - template <class _T1, class _T2> - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);} -}; - -#ifdef _LIBCPP_DEBUG - -template <class _Compare> -struct __debug_less -{ - _Compare __comp_; - __debug_less(_Compare& __c) : __comp_(__c) {} - template <class _Tp, class _Up> - bool operator()(const _Tp& __x, const _Up& __y) - { - bool __r = __comp_(__x, __y); - if (__r) - assert(!__comp_(__y, __x)); - return __r; - } -}; - -#endif // _LIBCPP_DEBUG - -// Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY unsigned __ctz(unsigned __x) {return __builtin_ctz (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long __ctz(unsigned long __x) {return __builtin_ctzl (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long long __ctz(unsigned long long __x) {return __builtin_ctzll(__x);} - -// Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY unsigned __clz(unsigned __x) {return __builtin_clz (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long __clz(unsigned long __x) {return __builtin_clzl (__x);} -inline _LIBCPP_INLINE_VISIBILITY unsigned long long __clz(unsigned long long __x) {return __builtin_clzll(__x);} - -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);} -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);} -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);} - -// all_of - -template <class _InputIterator, class _Predicate> -inline _LIBCPP_INLINE_VISIBILITY -bool -all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (!__pred(*__first)) - return false; - return true; -} - -// any_of - -template <class _InputIterator, class _Predicate> -inline _LIBCPP_INLINE_VISIBILITY -bool -any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - return true; - return false; -} - -// none_of - -template <class _InputIterator, class _Predicate> -inline _LIBCPP_INLINE_VISIBILITY -bool -none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - return false; - return true; -} - -// for_each - -template <class _InputIterator, class _Function> -inline _LIBCPP_INLINE_VISIBILITY -_Function -for_each(_InputIterator __first, _InputIterator __last, _Function __f) -{ - for (; __first != __last; ++__first) - __f(*__first); - return _STD::move(__f); -} - -// find - -template <class _InputIterator, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY -_InputIterator -find(_InputIterator __first, _InputIterator __last, const _Tp& __value) -{ - for (; __first != __last; ++__first) - if (*__first == __value) - break; - return __first; -} - -// find_if - -template <class _InputIterator, class _Predicate> -inline _LIBCPP_INLINE_VISIBILITY -_InputIterator -find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (__pred(*__first)) - break; - return __first; -} - -// find_if_not - -template<class _InputIterator, class _Predicate> -inline _LIBCPP_INLINE_VISIBILITY -_InputIterator -find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) -{ - for (; __first != __last; ++__first) - if (!__pred(*__first)) - break; - return __first; -} - -// find_end - -template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -_ForwardIterator1 -__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, - forward_iterator_tag, forward_iterator_tag) -{ - // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer - if (__first2 == __last2) - return __r; - while (true) - { - while (true) - { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) - break; - ++__first1; - } - // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; - while (true) - { - if (++__m2 == __last2) - { // Pattern exhaused, record answer and search for another one - __r = __first1; - ++__first1; - break; - } - if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first - { - ++__first1; - break; - } // else there is a match, check next elements - } - } -} - -template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> -_BidirectionalIterator1 -__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, - _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred, - bidirectional_iterator_tag, bidirectional_iterator_tag) -{ - // modeled after search algorithm (in reverse) - if (__first2 == __last2) - return __last1; // Everything matches an empty sequence - _BidirectionalIterator1 __l1 = __last1; - _BidirectionalIterator2 __l2 = __last2; - --__l2; - while (true) - { - // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks - while (true) - { - if (__first1 == __l1) // return __last1 if no element matches *__first2 - return __last1; - if (__pred(*--__l1, *__l2)) - break; - } - // *__l1 matches *__l2, now match elements before here - _BidirectionalIterator1 __m1 = __l1; - _BidirectionalIterator2 __m2 = __l2; - while (true) - { - if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) - return __m1; - if (__m1 == __first1) // Otherwise if source exhaused, pattern not found - return __last1; - if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 - { - break; - } // else there is a match, check next elements - } - } -} - -template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_RandomAccessIterator1 -__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag) -{ - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; - if (__len2 == 0) - return __last1; - typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; - if (__len1 < __len2) - return __last1; - const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; - --__l2; - while (true) - { - while (true) - { - if (__s == __l1) - return __last1; - if (__pred(*--__l1, *__l2)) - break; - } - _RandomAccessIterator1 __m1 = __l1; - _RandomAccessIterator2 __m2 = __l2; - while (true) - { - if (__m2 == __first2) - return __m1; - // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*--__m1, *--__m2)) - { - break; - } - } - } -} - -template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -inline _LIBCPP_INLINE_VISIBILITY -_ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - return _STD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type> - (__first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); -} - -template <class _ForwardIterator1, class _ForwardIterator2> -inline _LIBCPP_INLINE_VISIBILITY -_ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _STD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} - -// find_first_of - -template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) -{ - for (; __first1 != __last1; ++__first1) - for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) - if (__pred(*__first1, *__j)) - return __first1; - return __last1; -} - -template <class _ForwardIterator1, class _ForwardIterator2> -inline _LIBCPP_INLINE_VISIBILITY -_ForwardIterator1 -find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) -{ - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _STD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); -} - -// adjacent_find - -template <class _ForwardIterator, class _BinaryPredicate> -inline _LIBCPP_INLINE_VISIBILITY -_ForwardIterator -adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) -{ - if (__first != __last) - { - _ForwardIterator __i = __first; - while (++__i != __last) - { - if (__pred(*__first, *__i)) - return __first; - __first = __i; |