stl_heap.h (__is_heap_until): Add.

2007-10-12  Paolo Carlini  <pcarlini@suse.de>

	* include/bits/stl_heap.h (__is_heap_until): Add.
	(__is_heap(_RandomAccessIterator, _Distance),
	__is_heap(_RandomAccessIterator, _Compare, _Distance)):
	Adjust, call the latter.
	(is_heap, is_heap_until): Add, call the above.
	* include/bits/algorithmfwd.h: Add.
	* testsuite/25_algorithms/is_heap/requirements/
	explicit_instantiation/2.cc: New.
	* testsuite/25_algorithms/is_heap/requirements/
	explicit_instantiation/pod.cc: Likewise.
	* testsuite/25_algorithms/is_heap/1.cc: Likewise.
	* testsuite/25_algorithms/is_heap_until/requirements/
	explicit_instantiation/2.cc: Likewise.
	* testsuite/25_algorithms/is_heap_until/requirements/
	explicit_instantiation/pod.cc: Likewise.
	* testsuite/25_algorithms/is_heap_until/1.cc: Likewise.
	* testsuite/25_algorithms/headers/algorithm/synopsis.cc:
	Add is_heap and is_heap_until.

From-SVN: r129266

10 files changed, 441 insertions, 16 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index e4e6924..7b4721b 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,24 @@
+2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+
+	* include/bits/stl_heap.h (__is_heap_until): Add.
+	(__is_heap(_RandomAccessIterator, _Distance),
+	__is_heap(_RandomAccessIterator, _Compare, _Distance)):
+	Adjust, call the latter.
+	(is_heap, is_heap_until): Add, call the above.
+	* include/bits/algorithmfwd.h: Add.
+	* testsuite/25_algorithms/is_heap/requirements/
+	explicit_instantiation/2.cc: New.
+	* testsuite/25_algorithms/is_heap/requirements/
+	explicit_instantiation/pod.cc: Likewise.
+	* testsuite/25_algorithms/is_heap/1.cc: Likewise.
+	* testsuite/25_algorithms/is_heap_until/requirements/
+	explicit_instantiation/2.cc: Likewise.
+	* testsuite/25_algorithms/is_heap_until/requirements/
+	explicit_instantiation/pod.cc: Likewise.
+	* testsuite/25_algorithms/is_heap_until/1.cc: Likewise.
+	* testsuite/25_algorithms/headers/algorithm/synopsis.cc:
+	Add is_heap and is_heap_until.
+
 2007-10-12  Benjamin Kosnik  <bkoz@redhat.com>
 
 	* docs/doxygen/user.cfg.in: Scan tr1_impl/hashtable.
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 0e30473..b831e30 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -43,6 +43,8 @@
   generate_n
   includes
   inplace_merge
+  is_heap (C++0x)
+  is_heap_until (C++0x)
   iter_swap
   lexicographical_compare
   lower_bound
@@ -179,6 +181,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     void 
     inplace_merge(_BIter, _BIter, _BIter, _Compare);
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _RAIter>
+    bool 
+    is_heap(_RAIter, _RAIter);
+
+  template<typename _RAIter, typename _Compare>
+    bool 
+    is_heap(_RAIter, _RAIter, _Compare);
+
+  template<typename _RAIter>
+    _RAIter 
+    is_heap_until(_RAIter, _RAIter);
+
+  template<typename _RAIter, typename _Compare>
+    _RAIter 
+    is_heap_until(_RAIter, _RAIter, _Compare);
+#endif
+
   template<typename _FIter1, typename _FIter2>
     void 
     iter_swap(_FIter1, _FIter2);
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index 1fd9f7a..06d9093 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -66,53 +66,64 @@
 
 _GLIBCXX_BEGIN_NAMESPACE(std)
 
-  // is_heap, a predicate testing whether or not a range is
-  // a heap.  This function is an extension, not part of the C++
-  // standard.
   template<typename _RandomAccessIterator, typename _Distance>
-    bool
-    __is_heap(_RandomAccessIterator __first, _Distance __n)
+    _Distance
+    __is_heap_until(_RandomAccessIterator __first, _Distance __n)
     {
       _Distance __parent = 0;
       for (_Distance __child = 1; __child < __n; ++__child)
 	{
 	  if (__first[__parent] < __first[__child])
-	    return false;
+	    return __child;
 	  if ((__child & 1) == 0)
 	    ++__parent;
 	}
-      return true;
+      return __n;
     }
 
   template<typename _RandomAccessIterator, typename _Distance,
-           typename _StrictWeakOrdering>
-    bool
-    __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
-	      _Distance __n)
+	   typename _Compare>
+    _Distance
+    __is_heap_until(_RandomAccessIterator __first, _Distance __n,
+		    _Compare __comp)
     {
       _Distance __parent = 0;
       for (_Distance __child = 1; __child < __n; ++__child)
 	{
 	  if (__comp(__first[__parent], __first[__child]))
-	    return false;
+	    return __child;
 	  if ((__child & 1) == 0)
 	    ++__parent;
 	}
-      return true;
+      return __n;
     }
 
+  // __is_heap, a predicate testing whether or not a range is a heap.
+  // This function is an extension, not part of the C++ standard.
+  template<typename _RandomAccessIterator, typename _Distance>
+    inline bool
+    __is_heap(_RandomAccessIterator __first, _Distance __n)
+    { return std::__is_heap_until(__first, __n) == __n; }
+
+  template<typename _RandomAccessIterator, typename _Compare,
+	   typename _Distance>
+    inline bool
+    __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
+    { return std::__is_heap_until(__first, __n, __comp) == __n; }
+
   template<typename _RandomAccessIterator>
     inline bool
     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     { return std::__is_heap(__first, std::distance(__first, __last)); }
 
-  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
+  template<typename _RandomAccessIterator, typename _Compare>
     inline bool
     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
-	      _StrictWeakOrdering __comp)
+	      _Compare __comp)
     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 
-  // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
+  // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
+  // + is_heap and is_heap_until in C++0x.
 
   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
     void
@@ -475,6 +486,69 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
     }
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  /**
+   *  @brief  Check whether a range is a heap.
+   *  @param  first  Start of range.
+   *  @param  last   End of range.
+   *  @ingroup heap
+  */
+  template<typename _RandomAccessIterator>
+    inline bool
+    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    { return std::is_heap_until(__first, __last) == __last; }
+
+  /**
+   *  @brief  Check whether a range is a heap using comparison functor.
+   *  @param  first  Start of range.
+   *  @param  last   End of range.
+   *  @param  comp   Comparison functor to use.
+   *  @ingroup heap
+  */
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline bool
+    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	    _Compare __comp)
+    { return std::is_heap_until(__first, __last, __comp) == __last; }
+
+  /**
+   *  @brief  Search the end of a heap.
+   *  @param  first  Start of range.
+   *  @param  last   End of range.
+   *  @ingroup heap
+   *
+   *  This operation returns the last iterator i in [first, last) for which
+   *  the range [first, i) is a heap.
+  */
+  template<typename _RandomAccessIterator>
+    inline _RandomAccessIterator
+    is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    {
+      return __first + std::__is_heap_until(__first, std::distance(__first,
+								   __last));
+    }
+
+  /**
+   *  @brief  Search the end of a heap using comparison functor.
+   *  @param  first  Start of range.
+   *  @param  last   End of range.
+   *  @param  comp   Comparison functor to use.
+   *  @ingroup heap
+   *
+   *  This operation returns the last iterator i in [first, last) for which
+   *  the range [first, i) is a heap.  Comparisons are made using comp.
+  */
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline _RandomAccessIterator
+    is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
+		  _Compare __comp)
+    {
+      return __first + std::__is_heap_until(__first, std::distance(__first,
+								   __last),
+					    __comp);
+    }
+#endif
+
 _GLIBCXX_END_NAMESPACE
 
 #endif /* _STL_HEAP_H */
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 800de34..3176a53 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -401,6 +401,24 @@ namespace std
     void 
     sort_heap(_RAIter, _RAIter, _Compare);
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+  template<typename _RAIter>
+    bool 
+    is_heap(_RAIter, _RAIter);
+
+  template<typename _RAIter, typename _Compare>
+    bool 
+    is_heap(_RAIter, _RAIter, _Compare);
+
+  template<typename _RAIter>
+    _RAIter 
+    is_heap_until(_RAIter, _RAIter);
+
+  template<typename _RAIter, typename _Compare>
+    _RAIter 
+    is_heap_until(_RAIter, _RAIter, _Compare);
+#endif
+
   // 25.3.7, minimum and maximum:
   template<typename _Tp> 
     const _Tp& 
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap/1.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap/1.cc
new file mode 100644
index 0000000..da4f529
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap/1.cc
@@ -0,0 +1,52 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+//
+// Copyright (C) 2007 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 Pred 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.
+
+// 25.3.6 Heap operations [lib.alg.heap.operations]
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_hooks.h>
+
+int A[] = {9, 8, 6, 7, 7, 5, 5, 3, 6, 4, 1, 2, 3, 4};
+int B[] = {1, 3, 2, 4, 4, 6, 3, 5, 5, 7, 7, 6, 8, 9};
+const int N = sizeof(A) / sizeof(int);
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  for (int i = 0; i <= N; ++i)
+    {
+      VERIFY( std::is_heap(A, A + i) );
+      VERIFY( std::is_heap(A, A + i, std::less<int>()) );
+      VERIFY( std::is_heap(B, B + i, std::greater<int>()) );
+      VERIFY( (i < 2) || !std::is_heap(B, B + i) );
+    }
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/2.cc
new file mode 100644
index 0000000..8e4b42f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/2.cc
@@ -0,0 +1,47 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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::less<value_type> compare_type;
+
+  template bool is_heap(iterator_type, iterator_type);
+  template bool is_heap(iterator_type, iterator_type, compare_type);
+} 
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/pod.cc
new file mode 100644
index 0000000..04f5c7d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap/requirements/explicit_instantiation/pod.cc
@@ -0,0 +1,46 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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::less<value_type> compare_type;
+
+  template bool is_heap(iterator_type, iterator_type);
+  template bool is_heap(iterator_type, iterator_type, compare_type);
+} 
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap_until/1.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/1.cc
new file mode 100644
index 0000000..3b821cf
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/1.cc
@@ -0,0 +1,52 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+//
+// Copyright (C) 2007 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 Pred 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.
+
+// 25.3.6 Heap operations [lib.alg.heap.operations]
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_hooks.h>
+
+int A[] = {9, 8, 6, 7, 7, 5, 5, 3, 6, 4, 1, 2, 3, 4};
+int B[] = {1, 3, 2, 4, 4, 6, 3, 5, 5, 7, 7, 6, 8, 9};
+const int N = sizeof(A) / sizeof(int);
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  for (int i = 0; i <= N; ++i)
+    {
+      VERIFY( A + i == std::is_heap_until(A, A + i) );
+      VERIFY( A + i == std::is_heap_until(A, A + i, std::less<int>()) );
+      VERIFY( B + i == std::is_heap_until(B, B + i, std::greater<int>()) );
+      VERIFY( B + (i < 2 ? i : 1) == std::is_heap_until(B, B + i) );      
+    }
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/2.cc
new file mode 100644
index 0000000..c96e766
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/2.cc
@@ -0,0 +1,48 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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::less<value_type> compare_type;
+
+  template iterator_type is_heap_until(iterator_type, iterator_type);
+  template iterator_type is_heap_until(iterator_type, iterator_type,
+				       compare_type);
+} 
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/pod.cc
new file mode 100644
index 0000000..326f89a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_heap_until/requirements/explicit_instantiation/pod.cc
@@ -0,0 +1,47 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2007-10-12  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2007 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::less<value_type> compare_type;
+
+  template iterator_type is_heap_until(iterator_type, iterator_type);
+  template iterator_type is_heap_until(iterator_type, iterator_type,
+				       compare_type);
+}