2008-06-27 Paolo Carlini <paolo.carlini@oracle.com>

	* include/bits/stl_algo.h (is_partitioned): Add in C++0x mode.
	* include/bits/algorithmfwd.h: Add.
	* testsuite/25_algorithms/headers/algorithm/synopsis.cc: Update.
	* testsuite/25_algorithms/is_partitioned/1.cc: New.
	* testsuite/25_algorithms/is_partitioned/check_type.cc: Likewise.
	* testsuite/25_algorithms/is_partitioned/requirements/
	explicit_instantiation/2.cc: Likewise.
	* testsuite/25_algorithms/is_partitioned/requirements/
	explicit_instantiation/pod.cc: Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@137196 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 269 insertions, 8 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index b5191e8385a..1531ff3b2d7 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,17 @@
 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
 
+	* include/bits/stl_algo.h (is_partitioned): Add in C++0x mode.
+	* include/bits/algorithmfwd.h: Add.
+	* testsuite/25_algorithms/headers/algorithm/synopsis.cc: Update.
+	* testsuite/25_algorithms/is_partitioned/1.cc: New.
+	* testsuite/25_algorithms/is_partitioned/check_type.cc: Likewise.
+	* testsuite/25_algorithms/is_partitioned/requirements/
+	explicit_instantiation/2.cc: Likewise.
+	* testsuite/25_algorithms/is_partitioned/requirements/
+	explicit_instantiation/pod.cc: Likewise.
+
+2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
 	* include/bits/stl_numeric.h (iota): Add in C++0x mode.
 	* testsuite/util/testsuite_character.h (pod_int): Add operator++
 	in C++0x mode.
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index fa4e72cd412..4b78983517e 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -49,6 +49,7 @@
   inplace_merge
   is_heap (C++0x)
   is_heap_until (C++0x)
+  is_partitioned (C++0x)
   is_sorted (C++0x)
   is_sorted_until (C++0x)
   iter_swap
@@ -231,6 +232,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     _RAIter 
     is_heap_until(_RAIter, _RAIter, _Compare);
 
+  template<typename _IIter, typename _Predicate>
+    bool
+    is_partitioned(_IIter, _IIter, _Predicate);
+
   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 43b0582db74..f0199a43946 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -730,8 +730,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   /**
-   *  @brief Checks that a predicate is true for all the elements
-   *         of a sequence.
+   *  @brief  Checks that a predicate is true for all the elements
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -746,8 +746,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     { return __last == std::find_if_not(__first, __last, __pred); }
 
   /**
-   *  @brief Checks that a predicate is false for all the elements
-   *         of a sequence.
+   *  @brief  Checks that a predicate is false for all the elements
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -762,8 +762,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     { return __last == _GLIBCXX_STD_P::find_if(__first, __last, __pred); }
 
   /**
-   *  @brief Checks that a predicate is false for at least an element
-   *         of a sequence.
+   *  @brief  Checks that a predicate is false for at least an element
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -778,8 +778,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     { return !std::none_of(__first, __last, __pred); }
 
   /**
-   *  @brief Find the first element in a sequence for which a
-   *         predicate is false.
+   *  @brief  Find the first element in a sequence for which a
+   *          predicate is false.
    *  @param  first  An input iterator.
    *  @param  last   An input iterator.
    *  @param  pred   A predicate.
@@ -799,6 +799,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       return std::__find_if_not(__first, __last, __pred,
 				std::__iterator_category(__first));
     }
+
+  /**
+   *  @brief  Checks whether the sequence is partitioned.
+   *  @param  first  An input iterator.
+   *  @param  last   An input iterator.
+   *  @param  pred   A predicate.
+   *  @return  True if the range @p [first,last) is partioned by @p pred,
+   *  i.e. if all elements that satisfy @p pred appear before those that
+   *  do not.
+  */
+  template<typename _InputIterator, typename _Predicate>
+    inline bool
+    is_partitioned(_InputIterator __first, _InputIterator __last,
+		   _Predicate __pred)
+    {
+      __first = std::find_if_not(__first, __last, __pred);
+      return std::none_of(__first, __last, __pred);
+    }
 #endif
 
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index c52c779c1ed..8aa882aa949 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -51,6 +51,10 @@ namespace std
   template<typename _IIter, typename _Predicate>
     _IIter
     find_if_not(_IIter, _IIter, _Predicate);
+
+  template<typename _IIter, typename _Predicate>
+    bool
+    is_partitioned(_IIter, _IIter, _Predicate);
 #endif
 
   template<typename _FIter1, typename _FIter2>
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_partitioned/1.cc b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/1.cc
new file mode 100644
index 00000000000..b644cc5313f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/1.cc
@@ -0,0 +1,81 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+#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 array[] = {0, 0, 1, 1, 1, 0, 0, 1};
+
+bool
+predicate(const int& i) 
+{ return i == 1; }
+
+void
+test1()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array, array);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  
+  Container con(array, array + 1);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array, array + 8);
+  VERIFY( !std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array + 2, array + 7);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_partitioned/check_type.cc b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/check_type.cc
new file mode 100644
index 00000000000..98fa31c8413
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/check_type.cc
@@ -0,0 +1,50 @@
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct X { };
+
+using __gnu_test::input_iterator_wrapper;
+
+bool
+pred_function(const X&)
+{ return true; }
+
+struct pred_obj
+{
+  bool 
+  operator()(const X&)
+  { return true; }
+};
+
+bool
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::is_partitioned(begin, end, pred_function); }
+
+bool
+test2(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::is_partitioned(begin, end, pred_obj()); }
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc
new file mode 100644
index 00000000000..d717273e9bc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc
@@ -0,0 +1,46 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#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_unary_function<value_type, bool> predicate_type;
+
+  template bool is_partitioned(iterator_type, iterator_type, predicate_type);
+} 
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc
new file mode 100644
index 00000000000..be152b3c569
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc
@@ -0,0 +1,45 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#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_unary_function<value_type, bool> predicate_type;
+
+  template bool is_partitioned(iterator_type, iterator_type, predicate_type);
+}