[multiple changes]

2011-01-13  Paolo Carlini  <paolo.carlini@oracle.com>

	* testsuite/25_algorithms/is_permutation/check_type.cc: New.
	* testsuite/25_algorithms/is_permutation/requirements/
	explicit_instantiation/2.cc: Likewise.
	* testsuite/25_algorithms/is_permutation/requirements/
	explicit_instantiation/pod.cc: Likewise.
	* testsuite/25_algorithms/is_permutation/1.cc: Likewise.

2011-01-13  John Lakos  <jlakos@bloomberg.net>
	    Pablo Halpern  <phalpern@halpernwightsoftware.com>
	    Paolo Carlini  <paolo.carlini@oracle.com>

	* include/bits/stl_algo.h (is_permutation): Add, per N3068.
	* include/bits/algorithmfwd.h: Add.

From-SVN: r168773

7 files changed, 356 insertions, 3 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 33ab2e1..33c7f73 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,19 @@
+2011-01-13  Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* testsuite/25_algorithms/is_permutation/check_type.cc: New.
+	* testsuite/25_algorithms/is_permutation/requirements/
+	explicit_instantiation/2.cc: Likewise.
+	* testsuite/25_algorithms/is_permutation/requirements/
+	explicit_instantiation/pod.cc: Likewise.
+	* testsuite/25_algorithms/is_permutation/1.cc: Likewise.
+
+2011-01-13  John Lakos  <jlakos@bloomberg.net>
+	    Pablo Halpern  <phalpern@halpernwightsoftware.com>
+	    Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* include/bits/stl_algo.h (is_permutation): Add, per N3068.
+	* include/bits/algorithmfwd.h: Add.
+
 2011-01-13  Jonathan Wakely  <jwakely.gcc@gmail.com>
 
 	PR libstdc++/47045
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 9fad4ce..fd5dbb2 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -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 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     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);
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 0fdc924..c55c44f 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -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 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       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
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/1.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/1.cc
new file mode 100644
index 0000000..264cb13
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/1.cc
@@ -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;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type.cc
new file mode 100644
index 0000000..fe4ec1f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type.cc
@@ -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);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc
new file mode 100644
index 0000000..1d629d4
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc
@@ -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);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc
new file mode 100644
index 0000000..fcf878a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc
@@ -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);
+}