===================================================================
@@ -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 <bits/stl_tempbuf.h> // for _Temporary_buffer
#ifdef __GXX_EXPERIMENTAL_CXX0X__
-#include <random> // for std::uniform_int_distribution
+#include <random> // for std::uniform_int_distribution
+#include <functional> // 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<typename _ForwardIterator1, typename _ForwardIterator2>
+ 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<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ 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
===================================================================
@@ -1,6 +1,6 @@
// <algorithm> 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<typename _FIter1, typename _FIter2>
+ bool
+ is_permutation(_FIter1, _FIter1, _FIter2);
+
+ template<typename _FIter1, typename _FIter2,
+ typename _BinaryPredicate>
+ bool
+ is_permutation(_FIter1, _FIter1, _FIter2, _BinaryPredicate);
+
template<typename _FIter>
bool
is_sorted(_FIter, _FIter);
===================================================================
@@ -0,0 +1,48 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2011-01-13 Paolo Carlini <paolo.carlini@oracle.com>
+//
+// 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
+// <http://www.gnu.org/licenses/>.
+
+// 25.2.12 [alg.is_permutation] Is permutation
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+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<X>& lhs1,
+ forward_iterator_wrapper<X>& rhs1)
+{
+ return std::is_permutation(lhs1, lhs1, rhs1);
+}
+
+bool
+test2(forward_iterator_wrapper<X>& x1,
+ forward_iterator_wrapper<X>& x2)
+{
+ return std::is_permutation(x1, x1, x2, predicate);
+}
===================================================================
@@ -0,0 +1,41 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// 2011-01-13 Paolo Carlini <paolo.carlini@oracle.com>
+//
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_api.h>
+
+namespace std
+{
+ using __gnu_test::NonDefaultConstructible;
+
+ typedef NonDefaultConstructible value_type;
+ typedef value_type* iterator_type;
+ typedef std::pointer_to_binary_function<value_type, value_type, bool>
+ predicate_type;
+
+ template bool is_permutation(iterator_type, iterator_type,
+ iterator_type);
+
+ template bool is_permutation(iterator_type, iterator_type,
+ iterator_type, predicate_type);
+}
===================================================================
@@ -0,0 +1,40 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// 2011-01-13 Paolo Carlini <paolo.carlini@oracle.com>
+//
+// 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
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <testsuite_character.h>
+
+namespace std
+{
+ using __gnu_test::pod_int;
+
+ typedef pod_int value_type;
+ typedef value_type* iterator_type;
+ typedef std::pointer_to_binary_function<value_type, value_type, bool>
+ predicate_type;
+
+ template bool is_permutation(iterator_type, iterator_type,
+ iterator_type);
+
+ template bool is_permutation(iterator_type, iterator_type,
+ iterator_type, predicate_type);
+}
===================================================================
@@ -0,0 +1,104 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2011-01-13 Paolo Carlini <paolo.carlini@oracle.com>
+//
+// 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
+// <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)
+{
+ bool test __attribute__((unused)) = true;
+
+ do
+ VERIFY( std::is_permutation(arr1, arr1 + 5, arr0) == np );
+ while (std::next_permutation(arr1, arr1 + 5));
+}
+
+template<typename Predicate>
+ 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>());
+
+ 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());
+
+ 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;
+}