Index: include/bits/stl_algo.h =================================================================== --- include/bits/stl_algo.h (revision 168743) +++ include/bits/stl_algo.h (working copy) @@ -1,6 +1,7 @@ // Algorithm implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, +// 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -63,7 +64,8 @@ #include // for _Temporary_buffer #ifdef __GXX_EXPERIMENTAL_CXX0X__ -#include // for std::uniform_int_distribution +#include // for std::uniform_int_distribution +#include // for std::bind #endif // See concept_check.h for the __glibcxx_*_requires macros. @@ -4109,6 +4111,99 @@ return std::make_pair(*__p.first, *__p.second); } + /** + * @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. + * @return true if there exists a permutation of the elements in the range + * [first2, first2 + (last1 - first1)), beginning with + * ForwardIterator2 begin, such that equal(first1, last1, begin) + * returns true; otherwise, returns false. + */ + template + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2) + { + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + break; + + if (__first1 == __last1) + return true; + + // Establish __last2 assuming equal ranges by iterating over the + // rest of the list. + _ForwardIterator2 __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + if (__scan != _GLIBCXX_STD_P::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 pred A binary predicate. + * @return true if there exists a permutation of the elements in the range + * [first2, first2 + (last1 - first1)), beginning with + * ForwardIterator2 begin, such that equal(first1, last1, begin, + * pred) returns true; otherwise, returns false. + */ + template + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _BinaryPredicate __pred) + { + // 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 (__first1 == __last1) + return true; + + // Establish __last2 assuming equal ranges by iterating over the + // rest of the list. + _ForwardIterator2 __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + using std::placeholders::_1; + + if (__scan != _GLIBCXX_STD_P::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; + } + #ifdef _GLIBCXX_USE_C99_STDINT_TR1 /** * @brief Shuffle the elements of a sequence using a uniform random Index: include/bits/algorithmfwd.h =================================================================== --- include/bits/algorithmfwd.h (revision 168743) +++ include/bits/algorithmfwd.h (working copy) @@ -1,6 +1,6 @@ // declarations -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011 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 @@ -301,6 +301,15 @@ bool is_partitioned(_IIter, _IIter, _Predicate); + template + bool + is_permutation(_FIter1, _FIter1, _FIter2); + + template + bool + is_permutation(_FIter1, _FIter1, _FIter2, _BinaryPredicate); + template bool is_sorted(_FIter, _FIter); Index: testsuite/25_algorithms/is_permutation/check_type.cc =================================================================== --- testsuite/25_algorithms/is_permutation/check_type.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/check_type.cc (revision 0) @@ -0,0 +1,48 @@ +// { dg-options "-std=gnu++0x" } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +// 25.2.12 [alg.is_permutation] Is permutation + +// { dg-do compile } + +#include +#include + +using __gnu_test::forward_iterator_wrapper; + +struct X { }; + +bool operator==(const X&, const X) { return true; } +bool predicate(const X&, const X&) { return true; } + +bool +test1(forward_iterator_wrapper& lhs1, + forward_iterator_wrapper& rhs1) +{ + return std::is_permutation(lhs1, lhs1, rhs1); +} + +bool +test2(forward_iterator_wrapper& x1, + forward_iterator_wrapper& x2) +{ + return std::is_permutation(x1, x1, x2, predicate); +} Index: testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc =================================================================== --- testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc (revision 0) @@ -0,0 +1,41 @@ +// { dg-options "-std=gnu++0x" } +// { dg-do compile } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +#include +#include +#include + +namespace std +{ + using __gnu_test::NonDefaultConstructible; + + typedef NonDefaultConstructible value_type; + typedef value_type* iterator_type; + typedef std::pointer_to_binary_function + predicate_type; + + template bool is_permutation(iterator_type, iterator_type, + iterator_type); + + template bool is_permutation(iterator_type, iterator_type, + iterator_type, predicate_type); +} Index: testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc =================================================================== --- testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc (revision 0) @@ -0,0 +1,40 @@ +// { dg-options "-std=gnu++0x" } +// { dg-do compile } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +#include +#include + +namespace std +{ + using __gnu_test::pod_int; + + typedef pod_int value_type; + typedef value_type* iterator_type; + typedef std::pointer_to_binary_function + predicate_type; + + template bool is_permutation(iterator_type, iterator_type, + iterator_type); + + template bool is_permutation(iterator_type, iterator_type, + iterator_type, predicate_type); +} Index: testsuite/25_algorithms/is_permutation/1.cc =================================================================== --- testsuite/25_algorithms/is_permutation/1.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/1.cc (revision 0) @@ -0,0 +1,104 @@ +// { dg-options "-std=gnu++0x" } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +// 25.2.12 [alg.is_permutation] Is permutation + +#include +#include +#include + +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) +{ + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0) == np ); + while (std::next_permutation(arr1, arr1 + 5)); +} + +template + void + do_test(int arr1[5], Predicate pred, bool np = true) + { + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, pred) == np ); + while (std::next_permutation(arr1, arr1 + 5)); + } + +void test01() +{ + int arr1[] = { 11, 22, 33, 44, 55 }; + do_test(arr1); + + 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 arr5[] = { 11, 33, 33, 44, 55 }; + do_test(arr5, std::equal_to(), false); + + int arr6[] = { 33, 33, 33, 44, 44 }; + do_test(arr6, std::equal_to(), false); + + int arr7[] = { 1, 2, 3, 4, 5 }; + do_test(arr7, my_equal_to()); + + 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()); + + 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); +} + +int main() +{ + test01(); + return 0; +}