diff options
| -rw-r--r-- | libstdc++-v3/ChangeLog | 13 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 134 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algobase.h | 241 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/equal/1.cc | 12 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/equal/2.cc | 193 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc | 48 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc | 115 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc | 46 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc | 2 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc | 175 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc | 51 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/util/testsuite_iterators.h | 10 |
12 files changed, 1026 insertions, 14 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index c198998..55037c1 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,18 @@ 2013-06-08 Jonathan Wakely <jwakely.gcc@gmail.com> + * include/bits/stl_algo.h (is_permutation): Add overloads from N3671. + * include/bits/stl_algobase.h (equal, mismatch): Likewise. + * testsuite/25_algorithms/equal/1.cc: Remove duplicate test case. + * testsuite/25_algorithms/equal/2.cc: New. + * testsuite/25_algorithms/equal/check_type2.cc: New. + * testsuite/25_algorithms/is_permutationqual/2.cc: New. + * testsuite/25_algorithms/is_permutationqual/check_type2.cc: New. + * testsuite/25_algorithms/mismatch/2.cc: New. + * testsuite/25_algorithms/mismatch/check_type2.cc: New. + * testsuite/util/testsuite_iterators.h: Fix spelling. + +2013-06-08 Jonathan Wakely <jwakely.gcc@gmail.com> + * include/std/type-traits (integral_constant::operator()): Implement N3545. * testsuite/20_util/integral_constant/call_operator.cc: New. diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 873005b..e61f22b 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -4371,6 +4371,140 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return true; } +#if __cplusplus > 201103L + /** + * @brief Checks whether a permutaion of the second sequence is equal + * to the first sequence. + * @ingroup non_mutating_algorithms + * @param __first1 Start of first range. + * @param __last1 End of first range. + * @param __first2 Start of second range. + * @param __last2 End of first range. + * @return true if there exists a permutation of the elements in the range + * [__first2, __last2), beginning with ForwardIterator2 begin, + * such that equal(__first1, __last1, begin) returns true; + * otherwise, returns false. + */ + template<typename _ForwardIterator1, typename _ForwardIterator2> + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) + { + using _Cat1 + = typename iterator_traits<_ForwardIterator1>::iterator_category; + using _Cat2 + = typename iterator_traits<_ForwardIterator2>::iterator_category; + using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; + using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; + if (_It1_is_RA() && _It1_is_RA()) + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 != __d2) + return false; + } + + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + break; + + if (__first1 == __last1 && __first2 == __last2) + return true; + + if (std::distance(__first1, __last1) != std::distance(__first2, __last2)) + return false; + + for (auto __scan = __first1; __scan != __last1; ++__scan) + { + if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan)) + continue; // We've seen this one before. + + auto __matches = std::count(__first2, __last2, *__scan); + if (0 == __matches + || std::count(__scan, __last1, *__scan) != __matches) + return false; + } + return true; + } + + /** + * @brief Checks whether a permutation of the second sequence is equal + * to the first sequence. + * @ingroup non_mutating_algorithms + * @param __first1 Start of first range. + * @param __last1 End of first range. + * @param __first2 Start of second range. + * @param __last2 End of first range. + * @param __pred A binary predicate. + * @return true if there exists a permutation of the elements in the range + * [__first2, __last2), beginning with ForwardIterator2 begin, + * such that equal(__first1, __last1, __begin, __pred) returns true; + * otherwise, returns false. + */ + template<typename _ForwardIterator1, typename _ForwardIterator2, + typename _BinaryPredicate> + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) + { + using _Cat1 + = typename iterator_traits<_ForwardIterator1>::iterator_category; + using _Cat2 + = typename iterator_traits<_ForwardIterator2>::iterator_category; + using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; + using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; + constexpr bool __ra_iters = _It1_is_RA() && _It1_is_RA(); + if (__ra_iters) + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 != __d2) + return false; + } + + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1; ++__first1, ++__first2) + if (!bool(__pred(*__first1, *__first2))) + break; + + if (__ra_iters) + { + if (__first1 == __last1) + return true; + } + else + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 == 0 && __d2 == 0) + return true; + if (__d1 != __d2) + return false; + } + + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + using std::placeholders::_1; + + if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan, + std::bind(__pred, _1, *__scan))) + continue; // We've seen this one before. + + auto __matches = std::count_if(__first2, __last2, + std::bind(__pred, _1, *__scan)); + if (0 == __matches + || std::count_if(__scan, __last1, + std::bind(__pred, _1, *__scan)) != __matches) + return false; + } + return true; + } +#endif + #ifdef _GLIBCXX_USE_C99_STDINT_TR1 /** * @brief Shuffle the elements of a sequence using a uniform random diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index a90881f..67f859b 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -798,6 +798,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return false; return true; } + +#if __cplusplus > 201103L + template<typename _II1, typename _II2> + static bool + equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + for (; __first1 != __last1 && __first2 != __last2; + ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + return false; + return true; + } +#endif }; template<> @@ -810,6 +823,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * (__last1 - __first1)); } + +#if __cplusplus > 201103L + template<typename _Tp> + static bool + equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2, + const _Tp* __last2) + { + return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) + * (__last1 - __first1)); + } +#endif }; template<typename _II1, typename _II2> @@ -827,6 +851,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::__equal<__simple>::equal(__first1, __last1, __first2); } +#if __cplusplus > 201103L + template<bool _BoolType> + struct __equal2 + { + template<typename _It> + using _IterCat = typename iterator_traits<_It>::iterator_category; + template<typename _It> + using _IsRA = is_same<_IterCat<_It>, random_access_iterator_tag>; + + template<typename _II1, typename _II2> + static bool + equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + constexpr bool __ra_iters = _IsRA<_II1>() && _IsRA<_II2>(); + if (__ra_iters) + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 != __d2) + return false; + } + for (; __first1 != __last1 && __first2 != __last2; + ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + return false; + return __ra_iters || (__first1 == __last1 && __first2 == __last2); + } + }; + + template<> + struct __equal2<true> + { + template<typename _Tp> + static bool + equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2, + const _Tp* __last2) + { + if ((__last1 - __first1) != (__last2 - __first2)) + return false; + return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) + * (__last1 - __first1)); + } + }; + + template<typename _II1, typename _II2> + inline bool + __equal2_aux(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + const bool __simple = ((__is_integer<_ValueType1>::__value + || __is_pointer<_ValueType1>::__value) + && __is_pointer<_II1>::__value + && __is_pointer<_II2>::__value + && __are_same<_ValueType1, _ValueType2>::__value); + + return __equal2<__simple>::equal(__first1, __last1, __first2, __last2); + } +#endif template<typename, typename> struct __lc_rai @@ -1064,6 +1147,86 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO return true; } +#if __cplusplus > 201103L + /** + * @brief Tests a range for element-wise equality. + * @ingroup non_mutating_algorithms + * @param __first1 An input iterator. + * @param __last1 An input iterator. + * @param __first2 An input iterator. + * @param __last2 An input iterator. + * @return A boolean true or false. + * + * This compares the elements of two ranges using @c == and returns true or + * false depending on whether all of the corresponding elements of the + * ranges are equal. + */ + template<typename _II1, typename _II2> + inline bool + equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_II1>) + __glibcxx_function_requires(_InputIteratorConcept<_II2>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_II1>::value_type, + typename iterator_traits<_II2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + return std::__equal2_aux(std::__niter_base(__first1), + std::__niter_base(__last1), + std::__niter_base(__first2), + std::__niter_base(__last2)); + } + + /** + * @brief Tests a range for element-wise equality. + * @ingroup non_mutating_algorithms + * @param __first1 An input iterator. + * @param __last1 An input iterator. + * @param __first2 An input iterator. + * @param __last2 An input iterator. + * @param __binary_pred A binary predicate @link functors + * functor@endlink. + * @return A boolean true or false. + * + * This compares the elements of two ranges using the binary_pred + * parameter, and returns true or + * false depending on whether all of the corresponding elements of the + * ranges are equal. + */ + template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> + inline bool + equal(_IIter1 __first1, _IIter1 __last1, + _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) + __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + using _Cat1 = typename iterator_traits<_IIter1>::iterator_category; + using _Cat2 = typename iterator_traits<_IIter2>::iterator_category; + using _IIter1_is_RA = is_same<_Cat1, random_access_iterator_tag>; + using _IIter2_is_RA = is_same<_Cat2, random_access_iterator_tag>; + constexpr bool __ra_iters = _IIter1_is_RA() && _IIter1_is_RA(); + if (__ra_iters) + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 != __d2) + return false; + } + + for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + if (!bool(__binary_pred(*__first1, *__first2))) + return false; + return __ra_iters || (__first1 == __last1 && __first2 == __last2); + } +#endif + /** * @brief Performs @b dictionary comparison on ranges. * @ingroup sorting_algorithms @@ -1211,6 +1374,84 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO return pair<_InputIterator1, _InputIterator2>(__first1, __first2); } +#if __cplusplus > 201103L + /** + * @brief Finds the places in ranges which don't match. + * @ingroup non_mutating_algorithms + * @param __first1 An input iterator. + * @param __last1 An input iterator. + * @param __first2 An input iterator. + * @param __last2 An input iterator. + * @return A pair of iterators pointing to the first mismatch. + * + * This compares the elements of two ranges using @c == and returns a pair + * of iterators. The first iterator points into the first range, the + * second iterator points into the second range, and the elements pointed + * to by the iterators are not equal. + */ + template<typename _InputIterator1, typename _InputIterator2> + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + while (__first1 != __last1 && __first2 != __last2 + && *__first1 == *__first2) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } + + /** + * @brief Finds the places in ranges which don't match. + * @ingroup non_mutating_algorithms + * @param __first1 An input iterator. + * @param __last1 An input iterator. + * @param __first2 An input iterator. + * @param __last2 An input iterator. + * @param __binary_pred A binary predicate @link functors + * functor@endlink. + * @return A pair of iterators pointing to the first mismatch. + * + * This compares the elements of two ranges using the binary_pred + * parameter, and returns a pair + * of iterators. The first iterator points into the first range, the + * second iterator points into the second range, and the elements pointed + * to by the iterators are not equal. + */ + template<typename _InputIterator1, typename _InputIterator2, + typename _BinaryPredicate> + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _BinaryPredicate __binary_pred) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + while (__first1 != __last1 && __first2 != __last2 + && bool(__binary_pred(*__first1, *__first2))) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } +#endif + _GLIBCXX_END_NAMESPACE_ALGO } // namespace std diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/1.cc b/libstdc++-v3/testsuite/25_algorithms/equal/1.cc index 22af765..f8c1355 100644 --- a/libstdc++-v3/testsuite/25_algorithms/equal/1.cc +++ b/libstdc++-v3/testsuite/25_algorithms/equal/1.cc @@ -27,6 +27,8 @@ int array1[] = {0, 1}; int array2[] = {1, 0}; int array3[] = {1, 0}; +bool __attribute__((unused)) test = false; + void test1() { Container con1(array1, array1); @@ -45,17 +47,10 @@ void test3() { Container con1(array1, array1 + 2); Container con2(array2, array2 + 2); - VERIFY( !std::equal(con2.begin(), con2.end(), con1.begin()) ); -} - -void test4() -{ - Container con1(array1, array1 + 2); - Container con2(array2, array2 + 2); VERIFY( !std::equal(con1.begin(), con1.end(), con2.begin()) ); } -void test5() +void test4() { Container con3(array3, array3 + 2); Container con2(array2, array2 + 2); @@ -68,5 +63,4 @@ int main() test2(); test3(); test4(); - test5(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/2.cc b/libstdc++-v3/testsuite/25_algorithms/equal/2.cc new file mode 100644 index 0000000..012609f --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/equal/2.cc @@ -0,0 +1,193 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.11 [alg.equal] + +// { dg-options "-std=gnu++1y" } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +typedef test_container<int, input_iterator_wrapper> Container; +typedef test_container<int, random_access_iterator_wrapper> RA_Container; +int array1[] = {0, 1}; +int array2[] = {1, 0}; +int array3[] = {1, 0}; + +struct equal_to +{ + static int count; + + bool operator()(int l, int r) + { + ++count; + return l == r; + } +} eq; + +int equal_to::count = 0; + +bool __attribute__((unused)) test = false; + +void test1() +{ + const Container con1(array1, array1); + const Container con2(array2, array2); + + auto c1 = con1; + auto c2 = con2; + VERIFY( std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) ); + VERIFY( equal_to::count == 0 ); + + c1 = con1; + c2 = con2; + VERIFY( std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 0 ); +} + +void test2() +{ + const Container con1(array1, array1 + 0); + const Container con2(array2, array2 + 2); + + auto c1 = con1; + auto c2 = con2; + VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) ); + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 0 ); + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end()) ); + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end(), eq) ); + VERIFY( equal_to::count == 0 ); +} + +void test3() +{ + const Container con1(array1, array1 + 2); + const Container con2(array2, array2 + 2); + + auto c1 = con1; + auto c2 = con2; + VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) ); + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 1 ); + equal_to::count = 0; + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end()) ); + + c1 = con1; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end(), eq) ); + VERIFY( equal_to::count == 1 ); + equal_to::count = 0; +} + +void test4() +{ + const Container con3(array3, array3 + 2); + const Container con2(array2, array2 + 2); + + auto c3 = con3; + auto c2 = con2; + VERIFY( std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) ); + + c3 = con3; + c2 = con2; + VERIFY( std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 2 ); + equal_to::count = 0; + + c3 = con3; + c2 = con2; + VERIFY( std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) ); + + c3 = con3; + c2 = con2; + VERIFY( std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) ); + VERIFY( equal_to::count == 2 ); + equal_to::count = 0; +} + +void test5() +{ + const Container con3(array3, array3 + 1); + const Container con2(array2, array2 + 2); + + auto c3 = con3; + auto c2 = con2; + VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) ); + + c3 = con3; + c2 = con2; + VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 1 ); + equal_to::count = 0; + + c3 = con3; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) ); + + c3 = con3; + c2 = con2; + VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) ); + VERIFY( equal_to::count == 1 ); + equal_to::count = 0; +} + +void test6() +{ + RA_Container c3(array3, array3 + 1); + RA_Container c2(array2, array2 + 2); + + VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) ); + + VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) ); + VERIFY( equal_to::count == 0 ); + + VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) ); + + VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) ); + VERIFY( equal_to::count == 0 ); +} + +int main() +{ + test1(); + test2(); + test3(); + test4(); + test5(); + test6(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc new file mode 100644 index 0000000..c80cced --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc @@ -0,0 +1,48 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.11 [alg.equal] + +// { dg-do compile } +// { dg-options " -std=gnu++1y " } + +#include <algorithm> +#include <testsuite_iterators.h> +using __gnu_test::input_iterator_wrapper; + +struct Lhs1 { }; + +struct Rhs1 { }; + +bool operator==(const Lhs1&, const Rhs1&) {return true;} + +struct Lhs2 { }; + +struct Rhs2 { }; + +bool +predicate(const Lhs2&, const Rhs2&) {return true;} + +bool +test1(input_iterator_wrapper<Lhs1>& lhs1, + input_iterator_wrapper<Rhs1>& rhs1) +{ return std::equal(lhs1, lhs1, rhs1, rhs1); } + +bool +test2(input_iterator_wrapper<Lhs2>& lhs2, + input_iterator_wrapper<Rhs2>& rhs2) +{ return std::equal(lhs2, lhs2, rhs2, rhs2, predicate); } diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc new file mode 100644 index 0000000..d573fa2 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc @@ -0,0 +1,115 @@ +// { dg-options "-std=gnu++1y" } + +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.12 [alg.is_permutation] Is permutation + +#include <algorithm> +#include <functional> +#include <testsuite_hooks.h> + +struct my_equal_to +{ + bool + operator()(int __x, int __y) const + { return __x % 10 == __y % 10; } +}; + +const int arr0[] = { 11, 22, 33, 44, 55 }; + +void +do_test(int arr1[5], bool np = true, unsigned N = 5) +{ + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, arr0 + N) == np ); + while (std::next_permutation(arr1, arr1 + 5)); +} + +template<typename Predicate> + void + do_test(int arr1[5], Predicate pred, bool np = true, unsigned N = 5) + { + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, arr0 + N, pred) == np ); + while (std::next_permutation(arr1, arr1 + 5)); + } + +void test01() +{ + int arr1[] = { 11, 22, 33, 44, 55 }; + do_test(arr1); + do_test(arr1, false, 4); + + int arr2[] = { 11, 33, 33, 44, 55 }; + do_test(arr2, false); + + int arr3[] = { 33, 33, 33, 44, 44 }; + do_test(arr3, false); + + int arr4[] = { 11, 22, 33, 44, 55 }; + do_test(arr4, std::equal_to<int>()); + do_test(arr4, std::equal_to<int>(), false, 4); + + int arr5[] = { 11, 33, 33, 44, 55 }; + do_test(arr5, std::equal_to<int>(), false); + + int arr6[] = { 33, 33, 33, 44, 44 }; + do_test(arr6, std::equal_to<int>(), false); + + int arr7[] = { 1, 2, 3, 4, 5 }; + do_test(arr7, my_equal_to()); + do_test(arr7, my_equal_to(), false, 4); + + int arr8[] = { 1, 3, 3, 4, 5 }; + do_test(arr8, my_equal_to(), false); + + int arr9[] = { 3, 3, 3, 4, 4 }; + do_test(arr9, my_equal_to(), false); + + int arr10[] = { 111, 222, 333, 444, 555 }; + do_test(arr10, my_equal_to()); + do_test(arr10, my_equal_to(), false, 4); + + int arr11[] = { 1, 222, 33, 4, 55 }; + do_test(arr11, my_equal_to()); + + int arr12[] = { 111, 333, 333, 444, 555 }; + do_test(arr12, my_equal_to(), false); + + int arr13[] = { 333, 333, 333, 444, 444 }; + do_test(arr13, my_equal_to(), false); +} + +bool thrower(int, int) { throw 1; } + +void test02() +{ + int arr[] = { 11, 22, 33 }; + using namespace std; + is_permutation(begin(arr0), end(arr0), begin(arr), end(arr), thrower); +} + +int main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc new file mode 100644 index 0000000..9cdf87d --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc @@ -0,0 +1,46 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.12 [alg.is_permutation] Is permutation + +// { dg-do compile } +// { dg-options " -std=gnu++1y " } + +#include <algorithm> +#include <testsuite_iterators.h> + +using __gnu_test::forward_iterator_wrapper; + +struct X { }; +bool operator==(const X&, const X) { return true; } + +struct Y { }; +bool predicate(const Y&, const Y&) { return true; } + +bool +test1(forward_iterator_wrapper<X>& x1, + forward_iterator_wrapper<X>& x2) +{ + return std::is_permutation(x1, x1, x2, x2); +} + +bool +test2(forward_iterator_wrapper<Y>& y1, + forward_iterator_wrapper<Y>& y2) +{ + return std::is_permutation(y1, y1, y2, y2, predicate); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc index bcf2f5e..c70d778 100644 --- a/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc +++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc @@ -29,6 +29,8 @@ int array1[] = {0, 1}; int array2[] = {1, 0}; int array3[] = {1, 0, 1}; +bool __attribute__((unused)) test = false; + void test1a() { Container con1(array1, array1); diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc new file mode 100644 index 0000000..4eac4a9 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc @@ -0,0 +1,175 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.10 [mismatch] + +// { dg-options " -std=gnu++1y " } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; + +typedef test_container<int, input_iterator_wrapper> Container; + +int array1[] = {0, 1}; +int array2[] = {1, 0}; +int array3[] = {1, 0, 1}; + +struct equal_to +{ + static int count; + + bool operator()(int l, int r) + { + ++count; + return l == r; + } +} eq; + +int equal_to::count = 0; + +bool __attribute__((unused)) test = false; + +void test1() +{ + // empty ranges + Container con1(array1, array1); + Container con2(array2, array2); + auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + VERIFY( equal_to::count == 0 ); +} + +void test2() +{ + // first range empty, second non-empty + Container con1(array1, array1); + Container con2(array2, array2 + 2); + auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + + res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + VERIFY( equal_to::count == 0 ); +} + +void test3() +{ + // first range non-empty, second empty + Container con1(array1, array1 + 2); + Container con2(array2, array2); + auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + + res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + VERIFY( equal_to::count == 0 ); +} + +void test4() +{ + // non-empty, mismatching ranges + Container con1(array1, array1 + 2); + Container con2(array2, array2 + 2); + auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + + con1.bounds.first = array1; + con2.bounds.first = array2; + res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array1 ); + VERIFY( res.second.ptr == array2 ); + VERIFY( equal_to::count == 1 ); + equal_to::count = 0; +} + +void test5() +{ + // non-empty, matching ranges + Container con3(array3, array3 + 2); + Container con2(array2, array2 + 2); + auto res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array3 + 2 ); + VERIFY( res.second.ptr == array2 + 2 ); + + con3.bounds.first = array3; + con2.bounds.first = array2; + res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array3 + 2 ); + VERIFY( res.second.ptr == array2 + 2 ); + VERIFY( equal_to::count == 2 ); + equal_to::count = 0; +} + +void test6() +{ + // non-empty, matching sub-ranges, first range longer + Container con3(array3, array3 + 3); + Container con2(array2, array2 + 2); + auto res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end()); + VERIFY( res.first.ptr == array3 + 2 ); + VERIFY( res.second.ptr == array2 + 2 ); + + con3.bounds.first = array3; + con2.bounds.first = array2; + res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end(), eq); + VERIFY( res.first.ptr == array3 + 2 ); + VERIFY( res.second.ptr == array2 + 2 ); + VERIFY( equal_to::count == 2 ); + equal_to::count = 0; +} + +void test7() +{ + // non-empty, matching sub-ranges, second range longer + Container con3(array3, array3 + 3); + Container con2(array2, array2 + 2); + auto res = std::mismatch(con2.begin(), con2.end(), con3.begin(), con3.end()); + VERIFY( res.first.ptr == array2 + 2 ); + VERIFY( res.second.ptr == array3 + 2 ); + + con3.bounds.first = array3; + con2.bounds.first = array2; + res = std::mismatch(con2.begin(), con2.end(), con3.begin(), con3.end(), eq); + VERIFY( res.first.ptr == array2 + 2 ); + VERIFY( res.second.ptr == array3 + 2 ); + VERIFY( equal_to::count == 2 ); + equal_to::count = 0; +} + +int main() +{ + test1(); + test2(); + test3(); + test4(); + test5(); + test6(); + test7(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc new file mode 100644 index 0000000..3ec1f88 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc @@ -0,0 +1,51 @@ +// Copyright (C) 2005-2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// 25.2.10 [mismatch] + +// { dg-options " -std=gnu++1y " } +// { dg-do compile } + +#include <algorithm> +#include <utility> +#include <testsuite_iterators.h> + +using __gnu_test::input_iterator_wrapper; + +struct Lhs1 { }; + +struct Rhs1 { }; + +bool operator==(const Lhs1&, const Rhs1&) {return true;} + +struct Lhs2 { }; + +struct Rhs2 { }; + +bool predicate(const Lhs2&, const Rhs2&) {return true;} + +std::pair<input_iterator_wrapper<Lhs1>, input_iterator_wrapper<Rhs1> > +test1(input_iterator_wrapper<Lhs1>& lhs1, input_iterator_wrapper<Rhs1>& rhs1) +{ + return std::mismatch(lhs1, lhs1, rhs1, rhs1); +} + +std::pair<input_iterator_wrapper<Lhs2>, input_iterator_wrapper<Rhs2> > +test2(input_iterator_wrapper<Lhs2>& lhs2, input_iterator_wrapper<Rhs2>& rhs2) +{ + return std::mismatch(lhs2, lhs2, rhs2, rhs2, predicate); +} diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h index 757282b..9bb5858 100644 --- a/libstdc++-v3/testsuite/util/testsuite_iterators.h +++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h @@ -116,7 +116,7 @@ namespace __gnu_test * * This class takes a pointer and wraps it to provide exactly * the requirements of a output_iterator. It should not be - * instansiated directly, but generated from a test_container + * instantiated directly, but generated from a test_container */ template<class T> struct output_iterator_wrapper @@ -177,7 +177,7 @@ namespace __gnu_test * * This class takes a pointer and wraps it to provide exactly * the requirements of a input_iterator. It should not be - * instansiated directly, but generated from a test_container + * instantiated directly, but generated from a test_container */ template<class T> class input_iterator_wrapper @@ -259,7 +259,7 @@ namespace __gnu_test * * This class takes a pointer and wraps it to provide exactly * the requirements of a forward_iterator. It should not be - * instansiated directly, but generated from a test_container + * instantiated directly, but generated from a test_container */ template<class T> struct forward_iterator_wrapper : public input_iterator_wrapper<T> @@ -313,7 +313,7 @@ namespace __gnu_test * * This class takes a pointer and wraps it to provide exactly * the requirements of a forward_iterator. It should not be - * instansiated directly, but generated from a test_container + * instantiated directly, but generated from a test_container */ template<class T> struct bidirectional_iterator_wrapper : public forward_iterator_wrapper<T> @@ -377,7 +377,7 @@ namespace __gnu_test * * This class takes a pointer and wraps it to provide exactly * the requirements of a forward_iterator. It should not be - * instansiated directly, but generated from a test_container + * instantiated directly, but generated from a test_container */ template<class T> struct random_access_iterator_wrapper |