This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[v3] <algorithm> testcases from v7-branch


Hi,

the below is the set of testcases that I'm going to merge to mainline (a
small fix to replace_copy/replace_copy_if is also included).

Tested x86_64/ia64-linux.

Paolo.

///////////////////////
2005-05-24  Paolo Carlini  <pcarlini@suse.de>

	* testsuite/25_algorithms/equal.cc: Move to...
	* testsuite/25_algorithms/equal: ... here.
	* testsuite/25_algorithms/lower_bound.cc: Move to...
	* testsuite/25_algorithms/lower_bound: ... here.

2005-05-24  Paolo Carlini  <pcarlini@suse.de>

        Port from libstdcxx_so_7-branch:
	2005-20-05  Chris Jefferson  <chris@bubblescope.net>

	* testsuite/25_algorithms/heap.cc: Move to...
	* testsuite/25_algorithms/heap/heap.cc: ...here.
	* testsuite/25_algorithms/partition.cc: Move to...
	* testsuite/25_algorithms/partition/partition.cc: ...here.

	2005-03-29  Christopher Jefferson  <chris@bubblescope.net>

	* testsuite/25_algorithms/includes/1.cc: Add tests.
	* testsuite/25_algorithms/search/1.cc: Likewise.
	* testsuite/25_algorithms/unique_copy/1.cc: Likewise.
	* testsuite/25_algorithms/swap_ranges/1.cc: New.
	* testsuite/25_algorithms/swap_ranges/check_type.cc: New.
	* testsuite/25_algorithms/rotate.cc: Move to...
	* testsuite/25_algorithms/rotate/rotate.cc: ... here.
	* testsuite/25_algorithms/rotate/1.cc: New.
	* testsuite/25_algorithms/rotate/check_type.cc: New.
	* testsuite/25_algorithms/search_n/iterator.cc: Fix typo.

	2005-03-14  Christopher Jefferson  <chris@bubblescope.net>

	* include/bits/stl_algo.h (replace_copy, replace_copy_if):
	Don't assume that __new_value and *__first are convertible to
	each other.	

	* testsuite/25_algorithms/find/1.cc: New.
	* testsuite/25_algorithms/find/check_type.cc: New.
	* testsuite/25_algorithms/find_if/1.cc: New.
	* testsuite/25_algorithms/find_if/check_type.cc: New.
	* testsuite/25_algorithms/replace/1.cc: New.
	* testsuite/25_algorithms/replace/check_type.cc: New.
	* testsuite/25_algorithms/replace_if/1.cc: New.
	* testsuite/25_algorithms/replace_if/check_type.cc: New.
	* testsuite/25_algorithms/replace_copy/1.cc: New.
	* testsuite/25_algorithms/replace_copy/check_type.cc: New.
	* testsuite/25_algorithms/replace_copy_if/1.cc: New.
	* testsuite/25_algorithms/replace_copy_if/check_type.cc: New.
	* testsuite/25_algorithms/remove/1.cc: New.
	* testsuite/25_algorithms/remove/check_type.cc: New.
	* testsuite/25_algorithms/remove_if/1.cc: New.
	* testsuite/25_algorithms/remove_if/check_type.cc: New.
	* testsuite/25_algorithms/count/1.cc: New.
	* testsuite/25_algorithms/count/check_type.cc: New.
	* testsuite/25_algorithms/count_if/1.cc: New.
	* testsuite/25_algorithms/count_if/check_type.cc: New.

	2005-02-27  Christopher Jefferson  <chris@bubblescope.net>
        	    Paolo Carlini  <pcarlini@suse.de>

	* testsuite/ext/is_heap/check_type.cc : New.

	2005-02-01  Christopher Jefferson  <chris@bubblescope.net>

	* testsuite/ext/median.cc: New.
	* testsuite/25_algorithms/adjacent_find/1.cc: New.
	* testsuite/25_algorithms/adjacent_find/check_type.cc: New.
	* testsuite/25_algorithms/search/1.cc: New.
	* testsuite/25_algorithms/search/check_type.cc: New.
	* testsuite/25_algorithms/unique_copy/1.cc: New.
	* testsuite/25_algorithms/unique_copy/check_type.cc: New.
	* testsuite/25_algorithms/partial_sort/1.cc: New.
	* testsuite/25_algorithms/partial_sort/check_type.cc: New.
	* testsuite/25_algorithms/partial_sort_copy/1.cc: New.
	* testsuite/25_algorithms/partial_sort_copy/check_type.cc: New.
	* testsuite/25_algorithms/lower_bound/1.cc: New.
	* testsuite/25_algorithms/lower_bound/check_type.cc: New.
	* testsuite/25_algorithms/upper_bound/1.cc: New.
	* testsuite/25_algorithms/upper_bound/check_type.cc: New.
	* testsuite/25_algorithms/merge/1.cc: New.
	* testsuite/25_algorithms/merge/check_type.cc: New.
	* testsuite/25_algorithms/inplace_merge/1.cc: New.
	* testsuite/25_algorithms/inplace_merge/check_type.cc: New.
	* testsuite/25_algorithms/stable_sort/1.cc: New.
	* testsuite/25_algorithms/stable_sort/check_type.cc: New.
	* testsuite/25_algorithms/nth_element/1.cc: New.
	* testsuite/25_algorithms/nth_element/check_type.cc: New.
	* testsuite/25_algorithms/equal_range/1.cc: New.
	* testsuite/25_algorithms/equal_range/check_type.cc: New.
	* testsuite/25_algorithms/binary_search/1.cc: New.
	* testsuite/25_algorithms/binary_search/check_type.cc: New.
	* testsuite/25_algorithms/includes/1.cc: New.
	* testsuite/25_algorithms/includes/check_type.cc: New.
	* testsuite/25_algorithms/set_union/1.cc: New.
	* testsuite/25_algorithms/set_union/check_type.cc: New.
	* testsuite/25_algorithms/set_intersection/1.cc: New.
	* testsuite/25_algorithms/set_intersection/check_type.cc: New.
	* testsuite/25_algorithms/set_difference/1.cc: New.
	* testsuite/25_algorithms/set_difference/check_type.cc: New.
	* testsuite/25_algorithms/set_symmetric_difference/1.cc: New.
	* testsuite/25_algorithms/set_symmetric_difference/check_type.cc: New.	
	* testsuite/25_algorithms/min_element/1.cc: New.
	* testsuite/25_algorithms/min_element/check_type.cc: New.
	* testsuite/25_algorithms/max_element/1.cc: New.
	* testsuite/25_algorithms/max_element/check_type.cc: New.
	* testsuite/25_algorithms/prev_permutation/1.cc: New.
	* testsuite/25_algorithms/prev_permutation/check_type.cc: New.
	* testsuite/25_algorithms/next_permutation/1.cc: New.
	* testsuite/25_algorithms/next_permutation/check_type.cc: New.
	* testsuite/25_algorithms/find_first_of/1.cc: New.
	* testsuite/25_algorithms/find_first_of/check_type.cc: New.
	* testsuite/25_algorithms/find_end/1.cc: New.
	* testsuite/25_algorithms/find_end/check_type.cc: New.
	* testsuite/25_algorithms/equal/check_type.cc: Insert iterator type.
	* testsuite/25_algorithms/lexicographical_compare/check_type.cc:
	Likewise.

	2005-01-10  Christopher Jefferson <chris@bubblescope.net>

	* testsuite/25_algorithms/lexicographical_compare/check_type.cc: New.
	* testsuite/25_algorithms/lexicographical_compare/1.cc: Likewise.
	* testsuite/25_algorithms/mismatch/check_type.cc: Likewise.
	* testsuite/25_algorithms/mismatch/1.cc: Likewise.
	* testsuite/25_algorithms/equal/check_type.cc: New.
	* testsuite/25_algorithms/equal/1.cc: New.
diff -urN libstdc++-v3-orig/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3-orig/include/bits/stl_algo.h	2005-05-24 12:21:44.000000000 +0200
+++ libstdc++-v3/include/bits/stl_algo.h	2005-05-24 19:42:36.000000000 +0200
@@ -916,7 +916,10 @@
       __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first, ++__result)
-	*__result = *__first == __old_value ? __new_value : *__first;
+	if (*__first == __old_value)
+	  *__result = __new_value;
+	else
+	  *__result = *__first;
       return __result;
     }
 
@@ -950,7 +953,10 @@
       __glibcxx_requires_valid_range(__first, __last);
 
       for ( ; __first != __last; ++__first, ++__result)
-	*__result = __pred(*__first) ? __new_value : *__first;
+	if (__pred(*__first))
+	  *__result = __new_value;
+	else
+	  *__result = *__first;
       return __result;
     }
 
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/adjacent_find/1.cc libstdc++-v3/testsuite/25_algorithms/adjacent_find/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/adjacent_find/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/adjacent_find/1.cc	2005-05-24 18:46:14.000000000 +0200
@@ -0,0 +1,67 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.5 [lib.alg.adjacent_find]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::adjacent_find;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+int array[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
+
+void 
+test01()
+{
+  Container con(array, array);
+  VERIFY(adjacent_find(con.begin(), con.end()).ptr == array);
+}  
+
+void 
+test02()
+{
+  Container con(array, array + 1);
+  VERIFY(adjacent_find(con.begin(), con.end()).ptr == array + 1);
+}
+
+void 
+test03()
+{
+  Container con(array, array + 2);
+  VERIFY(adjacent_find(con.begin(), con.end()).ptr == array);
+}
+
+void 
+test04()
+{
+  Container con(array + 1, array + 10);
+  VERIFY(adjacent_find(con.begin(), con.end()).ptr == array + 10);
+}
+
+int 
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/adjacent_find/check_type.cc libstdc++-v3/testsuite/25_algorithms/adjacent_find/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/adjacent_find/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/adjacent_find/check_type.cc	2005-05-24 18:46:14.000000000 +0200
@@ -0,0 +1,42 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.5 [lib.alg.adjacent_find]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool operator==(const S&, const S&) {return true;}
+
+struct X { };
+
+bool predicate(const X&, const X&) {return true;}
+
+forward_iterator_wrapper<S> 
+test1(forward_iterator_wrapper<S>& s)
+{ return std::adjacent_find(s, s); }
+
+forward_iterator_wrapper<X> 
+test2(forward_iterator_wrapper<X>& x)
+{ return std::adjacent_find(x, x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/binary_search/1.cc libstdc++-v3/testsuite/25_algorithms/binary_search/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/binary_search/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/binary_search/1.cc	2005-05-24 18:46:38.000000000 +0200
@@ -0,0 +1,54 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.4 [lib.binary.search]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::binary_search;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int array[] = {0};
+  Container con(array, array);
+  VERIFY(!binary_search(con.begin(), con.end(), 1));
+}
+
+void
+test2()
+{
+  int array[] = {0, 2, 4, 6, 8};
+  Container con(array, array + 5);
+  for(int i = 0; i < 10; i += 2)
+    VERIFY(binary_search(con.begin(), con.end(), i));
+  for(int i = -1; i < 11; i += 2)
+    VERIFY(!binary_search(con.begin(), con.end(), i));
+}
+
+int main()
+{
+  test1();
+  test2();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/binary_search/check_type.cc libstdc++-v3/testsuite/25_algorithms/binary_search/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/binary_search/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/binary_search/check_type.cc	2005-05-24 18:46:38.000000000 +0200
@@ -0,0 +1,42 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.4 [lib.binary.search]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool predicate(const X&, const X&) {return true;}
+
+bool
+test1(forward_iterator_wrapper<S>& s)
+{ return std::binary_search(s, s, *s); }
+
+bool
+test2(forward_iterator_wrapper<X>& x)
+{ return std::binary_search(x, x, *x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/count/1.cc libstdc++-v3/testsuite/25_algorithms/count/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/count/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/count/1.cc	2005-05-24 18:46:59.000000000 +0200
@@ -0,0 +1,58 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.6 count
+
+#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, 0, 1, 0, 1};
+
+void
+test1()
+{
+  Container con(array, array);
+  VERIFY(std::count(con.begin(), con.end(), 1) == 0);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  VERIFY(std::count(con.begin(), con.end(), 1) == 0);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  VERIFY(std::count(con.begin(), con.end(), 1) == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/count/check_type.cc libstdc++-v3/testsuite/25_algorithms/count/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/count/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/count/check_type.cc	2005-05-24 18:46:59.000000000 +0200
@@ -0,0 +1,42 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find_if
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct X { };
+
+struct Y { };
+
+using __gnu_test::input_iterator_wrapper;
+
+bool
+operator==(const X&, const Y&)
+{ return true; }
+
+typedef std::iterator_traits<input_iterator_wrapper<X> >::difference_type
+	diff_type;
+
+diff_type
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::count(begin, end, Y()); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/count_if/1.cc libstdc++-v3/testsuite/25_algorithms/count_if/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/count_if/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/count_if/1.cc	2005-05-24 18:47:11.000000000 +0200
@@ -0,0 +1,65 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.6 count_if
+
+#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, 0, 1, 0, 1};
+
+bool
+predicate(const int& i) 
+{ return i == 1; }
+
+void
+test1()
+{
+  Container con(array, array);
+  VERIFY(std::count_if(con.begin(), con.end(), 
+		       predicate) == 0);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  VERIFY(std::count_if(con.begin(), con.end(), 
+		       predicate) == 0);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  VERIFY(std::count_if(con.begin(), con.end(),
+		       predicate) == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/count_if/check_type.cc libstdc++-v3/testsuite/25_algorithms/count_if/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/count_if/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/count_if/check_type.cc	2005-05-24 18:47:11.000000000 +0200
@@ -0,0 +1,52 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find_if
+
+// { dg-do compile }
+
+#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; }
+};
+
+typedef std::iterator_traits<input_iterator_wrapper<X> >::difference_type
+	diff_type;
+
+diff_type
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::count_if(begin, end, pred_function); }
+
+diff_type
+test2(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::count_if(begin, end, pred_obj()); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal/1.cc libstdc++-v3/testsuite/25_algorithms/equal/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal/1.cc	2005-05-24 18:47:26.000000000 +0200
@@ -0,0 +1,73 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// 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 array1[] = {0, 1};
+int array2[] = {1, 0};
+int array3[] = {1, 0};
+
+void test1()
+{
+  Container con1(array1, array1);
+  Container con2(array2, array2);
+  VERIFY( std::equal(con1.begin(), con1.end(), con2.begin()) );
+}
+
+void test2()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( !std::equal(con2.begin(), con2.end(), con1.begin()) );
+}
+
+void test3()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( !std::equal(con2.begin(), con2.end(), con1.begin()) );
+}
+
+void test4()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( !std::equal(con1.begin(), con1.end(), con2.begin()) );
+}
+
+void test5()
+{
+  Container con3(array3, array3 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::equal(con3.begin(), con3.end(), con2.begin()) );
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal/check_type.cc libstdc++-v3/testsuite/25_algorithms/equal/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal/check_type.cc	2005-05-24 18:47:26.000000000 +0200
@@ -0,0 +1,48 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.8 [lib.alg.equal]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct Lhs2 { };
+
+struct Rhs2 { };
+
+bool 
+predicate(const Lhs2&, const Rhs2&) {return true;}
+
+bool 
+test1(input_iterator_wrapper<Lhs1>& lhs1,
+      input_iterator_wrapper<Rhs1>& rhs1)
+{ return std::equal(lhs1, lhs1, rhs1); }
+
+bool 
+test2(input_iterator_wrapper<Lhs2>& lhs2,
+      input_iterator_wrapper<Rhs2>& rhs2)
+{ return std::equal(lhs2, lhs2, rhs2, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal/equal.cc libstdc++-v3/testsuite/25_algorithms/equal/equal.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal/equal.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal/equal.cc	2005-03-16 12:24:32.000000000 +0100
@@ -0,0 +1,40 @@
+// 2001-04-06 gdr
+
+// Copyright (C) 2000, 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+#include <vector>
+#include <algorithm>
+
+//
+// 25.1.8 Make sure std::equal doesn't make any extra assumption
+//        about operator== and operator!=
+//
+
+struct X { };
+
+bool operator==(X, X) { return true; }
+
+// Not implemented on purpose.  { dg-do link }
+bool operator!=(X, X);
+
+int main()
+{
+  std::vector<X> v, w;
+  return !std::equal(v.begin(), v.end(), w.begin());
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal.cc libstdc++-v3/testsuite/25_algorithms/equal.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal.cc	2005-03-16 12:24:32.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,40 +0,0 @@
-// 2001-04-06 gdr
-
-// Copyright (C) 2000, 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-#include <vector>
-#include <algorithm>
-
-//
-// 25.1.8 Make sure std::equal doesn't make any extra assumption
-//        about operator== and operator!=
-//
-
-struct X { };
-
-bool operator==(X, X) { return true; }
-
-// Not implemented on purpose.  { dg-do link }
-bool operator!=(X, X);
-
-int main()
-{
-  std::vector<X> v, w;
-  return !std::equal(v.begin(), v.end(), w.begin());
-}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal_range/1.cc libstdc++-v3/testsuite/25_algorithms/equal_range/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal_range/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal_range/1.cc	2005-05-24 18:47:41.000000000 +0200
@@ -0,0 +1,63 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.3 [lib.equal.range]
+
+#include <algorithm>
+#include <utility>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::equal_range;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+int array[] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2};
+
+void 
+test1()
+{
+  for(int i = 0; i < 6; ++i)
+    for(int j = 6; j < 12; ++j)
+      {
+	Container con(array + i, array + j);
+        VERIFY(equal_range(con.begin(), con.end(), 1).first.ptr ==
+	       array + std::max(i, 4));
+        VERIFY(equal_range(con.begin(), con.end(), 1).second.ptr ==
+               array + std::min(j, 8));
+      }
+}
+
+void
+test2()
+{
+  int array[]={0, 0, 2, 2, 2};
+  Container con(array, array + 5);
+  VERIFY(equal_range(con.begin(), con.end(), 1).first.ptr ==
+	 array + 2);
+  VERIFY(equal_range(con.begin(), con.end(), 1).second.ptr ==
+	 array + 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/equal_range/check_type.cc libstdc++-v3/testsuite/25_algorithms/equal_range/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/equal_range/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/equal_range/check_type.cc	2005-05-24 18:47:41.000000000 +0200
@@ -0,0 +1,43 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.3 [lib.equal.range]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <utility>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool predicate(const X&, const X&) {return true;}
+
+std::pair<forward_iterator_wrapper<S>, forward_iterator_wrapper<S> > 
+test1(forward_iterator_wrapper<S>& s)
+{ return std::equal_range(s, s, *s); }
+
+std::pair<forward_iterator_wrapper<X>, forward_iterator_wrapper<X> >
+test2(forward_iterator_wrapper<X>& x)
+{ return std::equal_range(x, x, *x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find/1.cc libstdc++-v3/testsuite/25_algorithms/find/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find/1.cc	2005-05-24 18:47:58.000000000 +0200
@@ -0,0 +1,58 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find
+
+#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, 0, 1, 0, 1};
+
+void
+test1()
+{
+  Container con(array, array);
+  VERIFY(std::find(con.begin(), con.end(), 1).ptr == array);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  VERIFY(std::find(con.begin(), con.end(), 1).ptr == array + 1);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  VERIFY(std::find(con.begin(), con.end(), 1).ptr == array + 3);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find/check_type.cc libstdc++-v3/testsuite/25_algorithms/find/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find/check_type.cc	2005-05-24 18:47:58.000000000 +0200
@@ -0,0 +1,38 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs { };
+struct Rhs { };
+
+bool
+operator==(const Lhs&, const Rhs&)
+{ return true; }
+
+input_iterator_wrapper<Lhs>
+test1(input_iterator_wrapper<Lhs>& begin,
+      input_iterator_wrapper<Lhs>& end, Rhs& val)
+{ return std::find(begin, end, val); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_end/1.cc libstdc++-v3/testsuite/25_algorithms/find_end/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_end/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_end/1.cc	2005-05-24 18:48:15.000000000 +0200
@@ -0,0 +1,57 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.3 [lib.alg.find.end]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+
+using std::find_end;
+
+void
+test1()
+{
+  int array[] = {0};
+  Container con1(array, array);
+  Container con2(array, array + 1);
+  VERIFY(find_end(con1.begin(), con1.end(), con1.begin(), con1.end()).ptr == array);
+  VERIFY(find_end(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr == array);
+  VERIFY(find_end(con2.begin(), con2.end(), con1.begin(), con1.end()).ptr == array + 1);
+}
+
+void 
+test2()
+{
+  int array1[] = {2, 2, 1, 2, 2, 1};
+  int array2[] = {2, 2};
+  Container con1(array1, array1 + 6);
+  Container con2(array2, array2 + 2);
+  VERIFY(find_end(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr == array1 + 3);
+}
+
+int main()
+{
+  test1();
+  test2();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_end/check_type.cc libstdc++-v3/testsuite/25_algorithms/find_end/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_end/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_end/check_type.cc	2005-05-24 18:48:15.000000000 +0200
@@ -0,0 +1,53 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.3 [lib.alg.find.end]
+
+// { dg-do compile }
+
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct X1 { };
+
+struct X2 { };
+
+bool predicate(const X1&, const X2&) {return true;}
+
+forward_iterator_wrapper<Lhs1>
+test1(forward_iterator_wrapper<Lhs1>& lhs1, 
+      forward_iterator_wrapper<Rhs1>& rhs1)
+{
+  return std::find_end(lhs1, lhs1, rhs1, rhs1);
+}
+
+forward_iterator_wrapper<X1>
+test2(forward_iterator_wrapper<X1>& x1,
+      forward_iterator_wrapper<X2>& x2)
+{
+  return std::find_end(x1, x1, x2, x2, predicate);
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_first_of/1.cc libstdc++-v3/testsuite/25_algorithms/find_first_of/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_first_of/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_first_of/1.cc	2005-05-24 18:48:33.000000000 +0200
@@ -0,0 +1,58 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.4 [lib.alg.find.first.of]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+
+using std::find_first_of;
+
+void 
+test1()
+{
+  int array[] = {0};
+  Container con1(array, array);
+  Container con2(array, array + 1);
+  VERIFY(find_first_of(con1.begin(), con1.end(), con1.begin(), con1.end()).ptr == array);
+  VERIFY(find_first_of(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr == array);
+  VERIFY(find_first_of(con2.begin(), con2.end(), con1.begin(), con1.end()).ptr == array + 1);
+}
+
+void 
+test2()
+{
+  int array1[] = {1 ,2, 3, 4, 5, 6};
+  int array2[] = {3, 4, 9};
+  Container con1(array1, array1 + 6);
+  Container con2(array2, array2 + 3);
+  VERIFY(find_first_of(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr == array1 + 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_first_of/check_type.cc libstdc++-v3/testsuite/25_algorithms/find_first_of/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_first_of/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_first_of/check_type.cc	2005-05-24 18:48:37.000000000 +0200
@@ -0,0 +1,49 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.4 [lib.alg.find.first.of]
+
+// { dg-do compile }
+
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct X1 { };
+
+struct X2 { };
+
+bool predicate(const X1&, const X2&) {return true;}
+
+forward_iterator_wrapper<Lhs1>
+test1(forward_iterator_wrapper<Lhs1>& lhs1, 
+      forward_iterator_wrapper<Rhs1>& rhs1)
+{ return std::find_first_of(lhs1, lhs1, rhs1, rhs1); }
+
+forward_iterator_wrapper<X1>
+test2(forward_iterator_wrapper<X1>& x1,
+      forward_iterator_wrapper<X2>& x2)
+{ return std::find_first_of(x1, x1, x2, x2, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_if/1.cc libstdc++-v3/testsuite/25_algorithms/find_if/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_if/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_if/1.cc	2005-05-24 18:48:50.000000000 +0200
@@ -0,0 +1,65 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find_if
+
+#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, 0, 1, 0, 1};
+
+bool
+predicate(const int& i) 
+{ return i == 1; }
+
+void
+test1()
+{
+  Container con(array, array);
+  VERIFY(std::find_if(con.begin(), con.end(), 
+		      predicate).ptr == array);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  VERIFY(std::find_if(con.begin(), con.end(), 
+		      predicate).ptr == array + 1);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  VERIFY(std::find_if(con.begin(), con.end(),
+		      predicate).ptr == array + 3);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/find_if/check_type.cc libstdc++-v3/testsuite/25_algorithms/find_if/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/find_if/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/find_if/check_type.cc	2005-05-24 18:48:50.000000000 +0200
@@ -0,0 +1,49 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.2 find_if
+
+// { dg-do compile }
+
+#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; }
+};
+
+input_iterator_wrapper<X>
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::find_if(begin, end, pred_function); }
+
+input_iterator_wrapper<X>
+test2(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::find_if(begin, end, pred_obj()); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/heap/heap.cc libstdc++-v3/testsuite/25_algorithms/heap/heap.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/heap/heap.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/heap/heap.cc	2003-11-11 21:09:16.000000000 +0100
@@ -0,0 +1,140 @@
+// Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.6 Heap operations [lib.alg.heap.operations]
+
+#include <algorithm>
+//#include <cmath>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+const int A[] = {1, 11, 12, 3, 10, 6, 17, 4, 8, 2, 5, 13, 9, 15, 14, 16, 7};
+const int B[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+const int C[] = {17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+
+// This functor has the equivalent functionality of std::geater<>,
+// but there is no dependency on <functional> and it also tracks the
+// number of invocations since creation.
+class Gt
+{
+public:
+    static int count() { return itsCount; }
+    static void reset() { itsCount = 0; }
+
+    bool
+    operator()(const int& x, const int& y)
+    {
+        ++itsCount;
+        return x > y; 
+    }
+
+private:
+    static int itsCount;
+};
+
+int Gt::itsCount = 0;
+
+// Exercise all of the heap functions for operator<.  The
+// intermediate results between push_heap and pop_heap and
+// make_heap and sort_heap are not checked (they could be).
+void
+test01()
+{
+    // sort array s1 using push_heap/pop_heap
+    int s1[N];
+    std::copy(A, A + N, s1);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    for (int i = 2; i <= N; ++i) {
+        std::push_heap(s1, s1 + i);
+    }
+    for (int i = N; i >= 2; --i) {
+        std::pop_heap(s1, s1 + i);
+    }
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    // sort array s2 using make_heap/sort_heap
+    int s2[N];
+    std::copy(A, A + N, s2);
+    VERIFY(std::equal(s2, s2 + N, A));
+
+    std::make_heap(s2, s2 + N);
+    std::sort_heap(s2, s2 + N);
+    VERIFY(std::equal(s2, s2 + N, B));
+}
+
+// Perform same tests as above but with the comparison predicate
+// versions, and add complexity constraint checks.
+void
+test02()
+{
+    Gt gt;
+//    const int logN = static_cast<int>(std::log(static_cast<double>(N)) + 0.5);
+    const int logN = 3;
+
+    int s1[N];
+    std::copy(A, A + N, s1);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    for (int i = 2; i <= N; ++i) {
+        std::push_heap(s1, s1 + i, gt);
+#ifndef _GLIBCXX_DEBUG
+        VERIFY(gt.count() <= logN);
+#endif
+        gt.reset();
+    }
+
+    for (int i = N; i >= 2; --i) {
+        std::pop_heap(s1, s1 + i, gt);
+#ifndef _GLIBCXX_DEBUG
+        VERIFY(gt.count() <= 2 * logN);
+#endif
+        gt.reset();
+    }
+
+    VERIFY(std::equal(s1, s1 + N, C));
+
+    // sort array s2 using make_heap/sort_heap
+    int s2[N];
+    std::copy(A, A + N, s2);
+    VERIFY(std::equal(s2, s2 + N, A));
+
+    std::make_heap(s2, s2 + N, gt);
+#ifndef _GLIBCXX_DEBUG
+    VERIFY(gt.count() <= 3 * N);
+#endif
+    gt.reset();
+
+    std::sort_heap(s2, s2 + N, gt);
+#ifndef _GLIBCXX_DEBUG
+    VERIFY(gt.count() <= N * logN);
+#endif
+
+    VERIFY(std::equal(s2, s2 + N, C));
+}
+
+int
+main()
+{
+  test01();
+  test02();
+
+  return 0;
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/heap.cc libstdc++-v3/testsuite/25_algorithms/heap.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/heap.cc	2003-11-11 21:09:16.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/heap.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,140 +0,0 @@
-// Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.3.6 Heap operations [lib.alg.heap.operations]
-
-#include <algorithm>
-//#include <cmath>
-#include <testsuite_hooks.h>
-
-bool test __attribute__((unused)) = true;
-
-const int A[] = {1, 11, 12, 3, 10, 6, 17, 4, 8, 2, 5, 13, 9, 15, 14, 16, 7};
-const int B[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
-const int C[] = {17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
-const int N = sizeof(A) / sizeof(int);
-
-// This functor has the equivalent functionality of std::geater<>,
-// but there is no dependency on <functional> and it also tracks the
-// number of invocations since creation.
-class Gt
-{
-public:
-    static int count() { return itsCount; }
-    static void reset() { itsCount = 0; }
-
-    bool
-    operator()(const int& x, const int& y)
-    {
-        ++itsCount;
-        return x > y; 
-    }
-
-private:
-    static int itsCount;
-};
-
-int Gt::itsCount = 0;
-
-// Exercise all of the heap functions for operator<.  The
-// intermediate results between push_heap and pop_heap and
-// make_heap and sort_heap are not checked (they could be).
-void
-test01()
-{
-    // sort array s1 using push_heap/pop_heap
-    int s1[N];
-    std::copy(A, A + N, s1);
-    VERIFY(std::equal(s1, s1 + N, A));
-
-    for (int i = 2; i <= N; ++i) {
-        std::push_heap(s1, s1 + i);
-    }
-    for (int i = N; i >= 2; --i) {
-        std::pop_heap(s1, s1 + i);
-    }
-    VERIFY(std::equal(s1, s1 + N, B));
-
-    // sort array s2 using make_heap/sort_heap
-    int s2[N];
-    std::copy(A, A + N, s2);
-    VERIFY(std::equal(s2, s2 + N, A));
-
-    std::make_heap(s2, s2 + N);
-    std::sort_heap(s2, s2 + N);
-    VERIFY(std::equal(s2, s2 + N, B));
-}
-
-// Perform same tests as above but with the comparison predicate
-// versions, and add complexity constraint checks.
-void
-test02()
-{
-    Gt gt;
-//    const int logN = static_cast<int>(std::log(static_cast<double>(N)) + 0.5);
-    const int logN = 3;
-
-    int s1[N];
-    std::copy(A, A + N, s1);
-    VERIFY(std::equal(s1, s1 + N, A));
-
-    for (int i = 2; i <= N; ++i) {
-        std::push_heap(s1, s1 + i, gt);
-#ifndef _GLIBCXX_DEBUG
-        VERIFY(gt.count() <= logN);
-#endif
-        gt.reset();
-    }
-
-    for (int i = N; i >= 2; --i) {
-        std::pop_heap(s1, s1 + i, gt);
-#ifndef _GLIBCXX_DEBUG
-        VERIFY(gt.count() <= 2 * logN);
-#endif
-        gt.reset();
-    }
-
-    VERIFY(std::equal(s1, s1 + N, C));
-
-    // sort array s2 using make_heap/sort_heap
-    int s2[N];
-    std::copy(A, A + N, s2);
-    VERIFY(std::equal(s2, s2 + N, A));
-
-    std::make_heap(s2, s2 + N, gt);
-#ifndef _GLIBCXX_DEBUG
-    VERIFY(gt.count() <= 3 * N);
-#endif
-    gt.reset();
-
-    std::sort_heap(s2, s2 + N, gt);
-#ifndef _GLIBCXX_DEBUG
-    VERIFY(gt.count() <= N * logN);
-#endif
-
-    VERIFY(std::equal(s2, s2 + N, C));
-}
-
-int
-main()
-{
-  test01();
-  test02();
-
-  return 0;
-}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/includes/1.cc libstdc++-v3/testsuite/25_algorithms/includes/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/includes/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/includes/1.cc	2005-05-24 18:58:45.000000000 +0200
@@ -0,0 +1,90 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.1 [lib.includes]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using std::includes;
+
+typedef test_container<int, input_iterator_wrapper> Container;
+
+void
+test1()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {0};
+  Container con1(array, array);
+  Container con2(array, array);
+  VERIFY(includes(con1.begin(), con1.end(), con2.begin(), con2.end()));
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {0, 1};
+  Container con1(array, array);
+  Container con2(array, array + 2);
+  VERIFY(!includes(con1.begin(), con1.end(), con2.begin(), con2.end()));
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {0, 1};
+  Container con1(array, array + 2);
+  Container con2(array, array);
+  VERIFY(includes(con1.begin(), con1.end(), con2.begin(), con2.end()));
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+  int array1[] = {1, 2, 3, 4, 6, 8, 9};
+  int array2[] = {2, 4, 6, 8};
+  Container con1(array1, array1 + 7);
+  Container con2(array2, array2 + 4);
+  VERIFY(includes(con1.begin(), con1.end(), con2.begin(), con2.end()));
+}
+
+void
+test5()
+{
+  bool test __attribute__((unused)) = true;
+  int array1[] = {1, 2, 3, 5};
+  int array2[] = {2, 4, 6, 8};
+  Container con1(array1, array1 + 4);
+  Container con2(array2, array2 + 4);
+  VERIFY(!includes(con1.begin(), con1.end(), con2.begin(), con2.end()));
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/includes/check_type.cc libstdc++-v3/testsuite/25_algorithms/includes/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/includes/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/includes/check_type.cc	2005-05-24 18:58:45.000000000 +0200
@@ -0,0 +1,46 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.1 [lib.includes]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) 
+{ return true; }
+
+struct X { };
+
+bool
+predicate(const X&, const X&)
+{ return true; }
+
+bool
+test1(input_iterator_wrapper<S>& s)
+{ return std::includes(s, s, s, s); }
+
+bool
+test2(input_iterator_wrapper<X>& x)
+{ return std::includes(x, x, x, x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/inplace_merge/1.cc libstdc++-v3/testsuite/25_algorithms/inplace_merge/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/inplace_merge/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/inplace_merge/1.cc	2005-05-24 18:58:57.000000000 +0200
@@ -0,0 +1,84 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using std::inplace_merge;
+
+typedef test_container<int, bidirectional_iterator_wrapper> container;
+
+
+void 
+test1()
+{
+  int array[]={1};
+  container con1(array, array);
+  inplace_merge(con1.begin(), con1.end(), con1.end());
+  container con2(array, array + 1);
+  inplace_merge(con2.begin(), con2.end(), con2.end());
+  inplace_merge(con2.begin(), con2.begin(), con2.end());
+}
+
+void 
+test2()
+{
+  int array[]={0,2,4,1,3,5};
+  container con(array, array + 6);
+  inplace_merge(con.begin(), con.it(3), con.end());
+  VERIFY(array[0] == 0 && array[1] == 1 && array[2] == 2 &&
+	 array[3] == 3 && array[4] == 4 && array[5] == 5);
+}
+
+struct S
+{
+  int a;
+  int b;
+  S(int _a, int _b) : a(_a), b(_b) { }
+  S() { }
+  bool 
+  operator<(const S& _s) const 
+  { return _s.a < a; }
+};
+
+void 
+test3()
+{
+  S s[4];
+  s[0].a = 0;
+  s[1].a = 1;
+  s[2].a = 0;
+  s[3].a = 1;
+  s[0].b = 0;
+  s[1].b = 0;
+  s[2].b = 1;
+  s[3].b = 1;
+  inplace_merge(s, s + 2, s + 4);
+  VERIFY(s[0].b == 0 && s[1].b == 1 && s[2].b == 0 && s[3].b == 1);
+}
+
+int 
+main()
+{
+  test1();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/inplace_merge/check_type.cc libstdc++-v3/testsuite/25_algorithms/inplace_merge/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/inplace_merge/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/inplace_merge/check_type.cc	2005-05-24 18:58:57.000000000 +0200
@@ -0,0 +1,48 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::bidirectional_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+void 
+test1(bidirectional_iterator_wrapper<S>& s)
+{
+  std::inplace_merge(s, s, s);
+}
+
+void 
+test2(bidirectional_iterator_wrapper<X>& x)
+{
+  std::inplace_merge(x, x, x, predicate);
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lexicographical_compare/1.cc libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lexicographical_compare/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc	2005-05-24 18:59:48.000000000 +0200
@@ -0,0 +1,86 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.8 [lib.alg.lex.comparison]
+
+#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 array1[] = {0, 1};
+int array2[] = {1, 0};
+int array3[] = {1, 0, 1};
+
+void 
+test1()
+{
+  Container con1(array1, array1);
+  Container con2(array2, array2);
+  VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(), 
+					con2.begin(), con2.end()) );
+}
+
+void 
+test2()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::lexicographical_compare(con1.begin(), con1.end(), 
+				       con2.begin(), con2.end()) );
+}
+
+void 
+test3()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(), 
+				        con1.begin(), con1.end()) );
+}
+
+void 
+test4()
+{
+  Container con3(array3, array3 + 3);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::lexicographical_compare(con2.begin(), con2.end(), 
+				       con3.begin(), con3.end()) );
+}
+
+void 
+test5()
+{
+  Container con3(array3, array3 + 3);
+  Container con2(array2, array2 + 2);
+  VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+					con2.begin(), con2.end()) );
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lexicographical_compare/check_type.cc libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lexicographical_compare/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/check_type.cc	2005-05-24 18:59:48.000000000 +0200
@@ -0,0 +1,51 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.8 [lib.alg.lex.comparison]
+
+// { dg-do compile }
+
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool 
+operator<(const Lhs1&, const Rhs1&) {return true;}
+
+bool 
+operator<(const Rhs1&, const Lhs1&) {return false;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+bool 
+test1(input_iterator_wrapper<Lhs1>& lhs1,
+      input_iterator_wrapper<Rhs1>& rhs1)
+{ return std::lexicographical_compare(lhs1, lhs1, rhs1, rhs1); }
+
+bool 
+test2(input_iterator_wrapper<X>& x)
+{ return std::lexicographical_compare(x, x, x, x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/1.cc libstdc++-v3/testsuite/25_algorithms/lower_bound/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/lower_bound/1.cc	2005-05-24 19:00:03.000000000 +0200
@@ -0,0 +1,47 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.1 [lib.lower.bound]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::lower_bound;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+int array[] = {0, 0, 0, 0, 1, 1, 1, 1};
+
+void 
+test1()
+{
+  for(int i = 0; i < 5; ++i)
+    for(int j = 4; j < 7; ++j)
+      {
+	Container con(array + i, array + j);
+	VERIFY(lower_bound(con.begin(), con.end(), 1).ptr == array + 4);
+      }
+}
+
+int 
+main()
+{
+  test1();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/check_type.cc libstdc++-v3/testsuite/25_algorithms/lower_bound/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/lower_bound/check_type.cc	2005-05-24 19:00:06.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.1 [lib.lower.bound]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+forward_iterator_wrapper<S> 
+test1(forward_iterator_wrapper<S>& s)
+{ return std::lower_bound(s, s, *s); }
+
+forward_iterator_wrapper<X> 
+test2(forward_iterator_wrapper<X>& x)
+{ return std::lower_bound(x, x, *x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/lower_bound.cc libstdc++-v3/testsuite/25_algorithms/lower_bound/lower_bound.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lower_bound/lower_bound.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/lower_bound/lower_bound.cc	2003-09-23 22:02:52.000000000 +0200
@@ -0,0 +1,32 @@
+// { dg-do compile }
+// Copyright (C) 2000, 2003 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// http://gcc.gnu.org/ml/libstdc++/2000-06/msg00316.html
+struct foo { };
+
+bool operator== (const foo&, const foo&) { return true; };
+bool operator< (const foo&, const foo&) { return true; };
+
+void bar(foo* a, foo* b, foo& x)
+{
+  foo* c __attribute__((unused)) = std::lower_bound(a, b, x);
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/lower_bound.cc libstdc++-v3/testsuite/25_algorithms/lower_bound.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/lower_bound.cc	2003-09-23 22:02:52.000000000 +0200
+++ libstdc++-v3/testsuite/25_algorithms/lower_bound.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,32 +0,0 @@
-// { dg-do compile }
-// Copyright (C) 2000, 2003 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-#include <algorithm>
-#include <testsuite_hooks.h>
-
-// http://gcc.gnu.org/ml/libstdc++/2000-06/msg00316.html
-struct foo { };
-
-bool operator== (const foo&, const foo&) { return true; };
-bool operator< (const foo&, const foo&) { return true; };
-
-void bar(foo* a, foo* b, foo& x)
-{
-  foo* c __attribute__((unused)) = std::lower_bound(a, b, x);
-}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/max_element/1.cc libstdc++-v3/testsuite/25_algorithms/max_element/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/max_element/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/max_element/1.cc	2005-05-24 19:00:22.000000000 +0200
@@ -0,0 +1,71 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.7 [lib.alg.min.max]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::max_element;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+
+void
+test1()
+{
+  // Note: The standard is unclear on what should happen in this case.
+  // This seems the only really sensible behaviour, and what is done.
+  int array[] = {0};
+  Container con(array, array);
+  VERIFY(max_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test2()
+{
+  int array[] = {0};
+  Container con(array, array + 1);
+  VERIFY(max_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test3()
+{
+  int array[] = {3, 0};
+  Container con(array, array + 2);
+  VERIFY(max_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test4()
+{
+  int array[] = {0, 3, 6, 2, 6, 4, 0};
+  Container con(array, array + 7);
+  VERIFY(max_element(con.begin(), con.end()).ptr == array + 2);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/max_element/check_type.cc libstdc++-v3/testsuite/25_algorithms/max_element/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/max_element/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/max_element/check_type.cc	2005-05-24 19:00:25.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.7 [lib.alg.min.max]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+forward_iterator_wrapper<S>
+test1(forward_iterator_wrapper<S>& s)
+{ return std::max_element(s, s); }
+
+forward_iterator_wrapper<X>
+test2(forward_iterator_wrapper<X>& x)
+{ return std::max_element(x, x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/merge/1.cc libstdc++-v3/testsuite/25_algorithms/merge/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/merge/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/merge/1.cc	2005-05-24 19:00:37.000000000 +0200
@@ -0,0 +1,101 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::merge;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+void 
+test1()
+{
+  int array1[1], array2[1];
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(merge(con1.begin(), con1.end(), con2.begin(), con2.end(),
+	       con3.begin()).ptr == array2);
+}
+
+void 
+test2()
+{
+  int array1[]={0,1,4};
+  int array2[]={2,3};
+  int array3[5];
+  Icontainer con1(array1, array1 + 3);
+  Icontainer con2(array2, array2 + 2);
+  Ocontainer con3(array3, array3 + 5);
+  VERIFY(merge(con1.begin(), con1.end(), con2.begin(), con2.end(),
+	       con3.begin()).ptr == array3 + 5);
+  VERIFY(array3[0] == 0 && array3[1] == 1 && array3[2] == 2 &&
+	 array3[3] == 3 && array3[4] == 4);
+
+}
+
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+void 
+test3()
+{
+  S array1[] = { -1 , -3};
+  S array2[] = { 1, 2, 3};
+  S array3[5];
+  merge(array1, array1 + 2, array2, array2 + 3, array3);
+  VERIFY(array3[0].j == 0 && array3[1].j == 1 && array3[2].j == 1 &&
+         array3[3].j == 0 && array3[4].j == 1);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/merge/check_type.cc libstdc++-v3/testsuite/25_algorithms/merge/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/merge/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/merge/check_type.cc	2005-05-24 19:00:40.000000000 +0200
@@ -0,0 +1,46 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.4 [lib.alg.merge]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+output_iterator_wrapper<S> 
+test1(input_iterator_wrapper<S>& in,
+      output_iterator_wrapper<S>& out)
+{ return std::merge(in, in, in, in, out); }
+
+output_iterator_wrapper<X> 
+test2(input_iterator_wrapper<X>& in,
+      output_iterator_wrapper<X>& out)
+{ return std::merge(in, in, in, in, out, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/min_element/1.cc libstdc++-v3/testsuite/25_algorithms/min_element/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/min_element/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/min_element/1.cc	2005-05-24 19:00:54.000000000 +0200
@@ -0,0 +1,71 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.7 [lib.alg.min.max]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::min_element;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+
+void
+test1()
+{
+  // Note: The standard is unclear on what should happen in this case.
+  // This seems the only really sensible behaviour, and what is done.
+  int array[] = {0};
+  Container con(array, array);
+  VERIFY(min_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test2()
+{
+  int array[] = {0};
+  Container con(array, array + 1);
+  VERIFY(min_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test3()
+{
+  int array[] = {0, 3};
+  Container con(array, array + 2);
+  VERIFY(min_element(con.begin(), con.end()).ptr == array);
+}
+
+void
+test4()
+{
+  int array[] = {6, 3, 0, 2, 6, 4, 0};
+  Container con(array, array + 7);
+  VERIFY(min_element(con.begin(), con.end()).ptr == array + 2);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/min_element/check_type.cc libstdc++-v3/testsuite/25_algorithms/min_element/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/min_element/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/min_element/check_type.cc	2005-05-24 19:00:57.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.7 [lib.alg.min.max]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+forward_iterator_wrapper<S>
+test1(forward_iterator_wrapper<S>& s)
+{ return std::min_element(s,s); }
+
+forward_iterator_wrapper<X>
+test2(forward_iterator_wrapper<X>& x)
+{ return std::min_element(x,x,predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/mismatch/1.cc libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/mismatch/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc	2005-05-24 19:01:11.000000000 +0200
@@ -0,0 +1,89 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.7 [lib.mismatch]
+
+#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 array1[] = {0, 1};
+int array2[] = {1, 0};
+int array3[] = {1, 0, 1};
+
+void test1a()
+{
+  Container con1(array1, array1);
+  Container con2(array2, array2);
+  VERIFY( std::mismatch(con1.begin(), con1.end(), con2.begin()).first.ptr
+	  == array1 );
+}
+
+void test1b()
+{
+  Container con1(array1, array1);
+  Container con2(array2, array2);
+  VERIFY( std::mismatch(con1.begin(), con1.end(), con2.begin()).second.ptr
+	  == array2 );
+}
+
+void test2a()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::mismatch(con1.begin(), con1.end(), con2.begin()).first.ptr
+	  == array1 );
+}
+
+void test2b()
+{
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::mismatch(con1.begin(), con1.end(), con2.begin()).second.ptr
+	  == array2 );
+}
+
+void test3a()
+{
+  Container con3(array3, array3 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::mismatch(con3.begin(), con3.end(), con2.begin()).first.ptr
+	  == array3 + 2 );
+}
+
+void test3b()
+{
+  Container con3(array3, array3 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY( std::mismatch(con3.begin(), con3.end(), con2.begin()).second.ptr
+	  == array2 + 2 );
+}
+
+int main()
+{
+  test1a();
+  test1b();
+  test2a();
+  test2b();
+  test3a();
+  test3b();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/mismatch/check_type.cc libstdc++-v3/testsuite/25_algorithms/mismatch/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/mismatch/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/mismatch/check_type.cc	2005-05-24 19:01:14.000000000 +0200
@@ -0,0 +1,51 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.7 [lib.mismatch]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <utility>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct Lhs2 { };
+
+struct Rhs2 { };
+
+bool predicate(const Lhs2&, const Rhs2&) {return true;}
+
+std::pair<input_iterator_wrapper<Lhs1>, input_iterator_wrapper<Rhs1> >
+test1(input_iterator_wrapper<Lhs1>& lhs1, input_iterator_wrapper<Rhs1>& rhs1)
+{
+  return std::mismatch(lhs1, lhs1, rhs1);
+}
+
+std::pair<input_iterator_wrapper<Lhs2>, input_iterator_wrapper<Rhs2> >
+test2(input_iterator_wrapper<Lhs2>& lhs2, input_iterator_wrapper<Rhs2>& rhs2)
+{
+  return std::mismatch(lhs2, lhs2, rhs2, predicate);
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/next_permutation/1.cc libstdc++-v3/testsuite/25_algorithms/next_permutation/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/next_permutation/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/next_permutation/1.cc	2005-05-24 19:01:26.000000000 +0200
@@ -0,0 +1,84 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.9 [lib.alg.permutation.generators]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using std::next_permutation;
+
+typedef test_container<int, bidirectional_iterator_wrapper> Container;
+
+void
+test1()
+{
+  // Note: The standard is unclear on what should happen in this case.
+  // This seems the only really sensible behaviour, and what is done.
+  int array[] = {0};
+  Container con(array, array);
+  VERIFY(!next_permutation(con.begin(), con.end()));
+}
+
+void
+test2()
+{
+  int array[] = {0};
+  Container con(array, array + 1);
+  VERIFY(!next_permutation(con.begin(), con.end()));
+}
+
+void
+test3()
+{
+  int array[] = {0, 3};
+  Container con(array, array + 2);
+  VERIFY(next_permutation(con.begin(), con.end()));
+  VERIFY(array[0] == 3 && array[1] == 0);
+  VERIFY(!next_permutation(con.begin(), con.end()));
+  VERIFY(array[0] == 0 && array[1] == 3);
+}
+
+void
+test4()
+{
+  int array[6] = {0, 1, 2, 3, 4, 5};
+  Container con(array, array + 6);
+  for(int i = 0 ; i < 719; ++i)
+    {
+      int temp_array[6];
+      std::copy(array, array + 6, temp_array);
+      VERIFY(next_permutation(array, array + 6));
+      VERIFY(std::lexicographical_compare(temp_array, temp_array + 6, 
+					  array, array + 6));
+    }
+  VERIFY(!next_permutation(array,array + 6));
+  for(int i = 0; i < 6; ++i)
+    VERIFY(array[i] == i);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/next_permutation/check_type.cc libstdc++-v3/testsuite/25_algorithms/next_permutation/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/next_permutation/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/next_permutation/check_type.cc	2005-05-24 19:01:29.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.9 [lib.alg.permutation.generators]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::bidirectional_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+bool
+test1(bidirectional_iterator_wrapper<S>& s)
+{ return std::next_permutation(s,s); }
+
+bool
+test2(bidirectional_iterator_wrapper<X>& x)
+{ return std::next_permutation(x,x,predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/nth_element/1.cc libstdc++-v3/testsuite/25_algorithms/nth_element/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/nth_element/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/nth_element/1.cc	2005-05-24 19:01:45.000000000 +0200
@@ -0,0 +1,79 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.2 [lib.alg.nth.element]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::nth_element;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int array[]={0};
+  Container con(array, array);
+  partial_sort(con.begin(), con.begin(), con.end());
+}
+
+void 
+test2()
+{
+  int array[]={2,1,0};
+  Container con(array, array + 2);
+  partial_sort(con.begin(), con.begin(), con.end());
+  partial_sort(con.begin(), con.end(), con.end());
+}
+
+void 
+test3()
+{
+  int array[] = {6, 5, 4, 3, 2, 1, 0};
+  Container con(array, array + 7);
+  nth_element(con.begin(), con.it(3), con.end());
+  for(int i = 0; i < 3; ++i)
+    VERIFY(array[i] < array[3]);
+  for(int i = 4; i < 7; ++i)
+    VERIFY(array[3] < array[i]);
+}
+
+void 
+test4()
+{
+  int array[] = {0, 6, 1, 5, 2, 4, 3};
+  Container con(array,array + 7);
+  nth_element(con.begin(), con.it(3), con.end());
+  for(int i = 0; i < 3; ++i)
+    VERIFY(array[i] < array[3]);
+  for(int i = 4; i < 7; ++i)
+    VERIFY(array[3] < array[i]);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/nth_element/check_type.cc libstdc++-v3/testsuite/25_algorithms/nth_element/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/nth_element/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/nth_element/check_type.cc	2005-05-24 19:01:48.000000000 +0200
@@ -0,0 +1,45 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.2 [lib.alg.nth.element]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::random_access_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+void
+test1(random_access_iterator_wrapper<S>& s)
+{ std::nth_element(s, s, s); }
+
+void
+test2(random_access_iterator_wrapper<X>& x)
+{ std::nth_element(x, x, x, predicate); }
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partial_sort/1.cc libstdc++-v3/testsuite/25_algorithms/partial_sort/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partial_sort/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort/1.cc	2005-05-24 19:02:02.000000000 +0200
@@ -0,0 +1,66 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.3 [lib.partial.sort]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::partial_sort;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int array[]={2,1,0};
+  Container con1(array, array + 2);
+  Container con2(array, array);
+  partial_sort(con2.begin(), con2.begin(), con2.end());
+  partial_sort(con1.begin(), con1.begin(), con1.end());
+  partial_sort(con1.begin(), con1.end(), con1.end());
+}
+
+void 
+test2()
+{
+  int array[] = {6, 5, 4, 3, 2, 1, 0};
+  Container con(array, array + 7);
+  partial_sort(con.begin(), con.it(3), con.end());
+  VERIFY(array[0] == 0 && array[1] == 1 && array[2] == 2);
+}
+
+void 
+test3()
+{
+  int array[] = {0, 6, 1, 5, 2, 4, 3};
+  Container con(array,array + 7);
+  partial_sort(con.begin(), con.it(3), con.end());
+  VERIFY(array[0] == 0 && array[1] == 1 && array[2] == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partial_sort/check_type.cc libstdc++-v3/testsuite/25_algorithms/partial_sort/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partial_sort/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort/check_type.cc	2005-05-24 19:02:05.000000000 +0200
@@ -0,0 +1,49 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.3 [lib.partial.sort]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::random_access_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+void
+test1(random_access_iterator_wrapper<S>& s)
+{
+  std::partial_sort(s, s, s);
+}
+
+void
+test2(random_access_iterator_wrapper<X>& x)
+{
+  std::partial_sort(x, x, x, predicate);
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partial_sort_copy/1.cc libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partial_sort_copy/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/1.cc	2005-05-24 19:02:16.000000000 +0200
@@ -0,0 +1,89 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.4 [lib.partial.sort.copy]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::input_iterator_wrapper;
+using std::partial_sort_copy;
+
+typedef test_container<int, random_access_iterator_wrapper> Rcontainer;
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+
+void 
+test1()
+{
+  int array[]={2,1,0};
+  Rcontainer rcon1(array, array);
+  Rcontainer rcon2(array, array + 2);
+  Icontainer icon1(array, array);
+  Icontainer icon2(array, array + 2);
+  partial_sort_copy(icon1.begin(), icon1.end(), rcon1.begin(), rcon1.end());
+  partial_sort_copy(icon1.begin(), icon1.end(), rcon2.begin(), rcon2.end());
+  partial_sort_copy(icon2.begin(), icon2.end(), rcon1.begin(), rcon1.end());
+  partial_sort_copy(icon2.begin(), icon2.end(), rcon2.begin(), rcon2.end()); 
+}
+
+void 
+test2()
+{
+  int array1[] = {4, 3, 2, 1, 0};
+  int array2[5];
+  Icontainer icon(array1, array1 + 5);
+  Rcontainer rcon(array2, array2 + 5);
+  partial_sort_copy(icon.begin(), icon.end(), rcon.begin(), rcon.end());
+  VERIFY(array2[0] == 0 && array2[1] == 1 && array2[2] == 2 &&
+	 array2[3] == 3 && array2[4] == 4);
+}
+
+void 
+test3()
+{
+  int array1[] = {4, 0, 1, 3, 2};
+  int array2[5];
+  Icontainer icon(array1, array1 + 5);
+  Rcontainer rcon(array2, array2 + 2);
+  partial_sort_copy(icon.begin(), icon.end(), rcon.begin(), rcon.end());
+  VERIFY(array2[0] == 0 && array2[1] == 1);
+}
+
+void 
+test4()
+{
+  int array1[] = {4, 1, 3, 2, 0};
+  int array2[20];
+  Icontainer icon(array1, array1 + 5);
+  Rcontainer rcon(array2, array2 + 20);
+  partial_sort_copy(icon.begin(), icon.end(), rcon.begin(), rcon.end());
+  VERIFY(array2[0] == 0 && array2[1] == 1 && array2[2] == 2 &&
+	 array2[3] == 3 && array2[4] == 4);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partial_sort_copy/check_type.cc libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partial_sort_copy/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/check_type.cc	2005-05-24 19:02:19.000000000 +0200
@@ -0,0 +1,68 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.4 [lib.partial.sort.copy]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+struct S1 { };
+struct S2 
+{ 
+  S2(const S1&) {}
+  S2() {}
+};
+
+bool 
+operator<(const S1&, const S1&) 
+{return true;}
+
+bool 
+operator<(const S2&, const S2&) 
+{return true;}
+
+struct X1 { };
+struct X2 
+{
+  X2(const X1&) {}
+  X2() {}
+};
+
+struct predicate
+{
+  bool 
+  operator()(const X1&, const X1&) 
+  {return true;}
+  
+  bool 
+  operator()(const X2&, const X2&) 
+  {return true;}
+};
+
+random_access_iterator_wrapper<S2>
+test1(input_iterator_wrapper<S1>& s1, random_access_iterator_wrapper<S2>& s2)
+{ return std::partial_sort_copy(s1, s1, s2, s2); }
+
+random_access_iterator_wrapper<X2>
+test2(input_iterator_wrapper<X1>& x1, random_access_iterator_wrapper<X2>& x2)
+{ return std::partial_sort_copy(x1, x1, x2, x2, predicate()); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partition/partition.cc libstdc++-v3/testsuite/25_algorithms/partition/partition.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partition/partition.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partition/partition.cc	2003-09-23 22:02:52.000000000 +0200
@@ -0,0 +1,73 @@
+// Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.12 [lib.alg.partitions] Partitions.
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+const int B[] = {2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15, 17};
+const int N = sizeof(A) / sizeof(int);
+
+struct Pred
+{
+    bool
+    operator()(const int& x) const
+    { return (x % 2) == 0; }
+};
+
+// 25.2.12 partition()
+void
+test01()
+{
+    using std::partition;
+
+    int s1[N];
+    std::copy(A, A + N, s1);
+
+    Pred pred;
+    int* m = partition(s1, s1 + N, pred);
+    for (const int* i = s1; i < m; ++i) VERIFY(pred(*i));
+    for (const int* i = m; i < s1 + N; ++i) VERIFY(!pred(*i));
+}
+
+// 25.2.12 stable_partition()
+void
+test02()
+{
+    using std::stable_partition;
+
+    int s1[N];
+    std::copy(A, A + N, s1);
+
+    stable_partition(s1, s1 + N, Pred());
+    VERIFY(std::equal(s1, s1 + N, B));
+}
+
+int
+main()
+{
+  test01();
+  test02();
+
+  return 0;
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/partition.cc libstdc++-v3/testsuite/25_algorithms/partition.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/partition.cc	2003-09-23 22:02:52.000000000 +0200
+++ libstdc++-v3/testsuite/25_algorithms/partition.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,73 +0,0 @@
-// Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.2.12 [lib.alg.partitions] Partitions.
-
-#include <algorithm>
-#include <functional>
-#include <testsuite_hooks.h>
-
-bool test __attribute__((unused)) = true;
-
-const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
-const int B[] = {2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15, 17};
-const int N = sizeof(A) / sizeof(int);
-
-struct Pred
-{
-    bool
-    operator()(const int& x) const
-    { return (x % 2) == 0; }
-};
-
-// 25.2.12 partition()
-void
-test01()
-{
-    using std::partition;
-
-    int s1[N];
-    std::copy(A, A + N, s1);
-
-    Pred pred;
-    int* m = partition(s1, s1 + N, pred);
-    for (const int* i = s1; i < m; ++i) VERIFY(pred(*i));
-    for (const int* i = m; i < s1 + N; ++i) VERIFY(!pred(*i));
-}
-
-// 25.2.12 stable_partition()
-void
-test02()
-{
-    using std::stable_partition;
-
-    int s1[N];
-    std::copy(A, A + N, s1);
-
-    stable_partition(s1, s1 + N, Pred());
-    VERIFY(std::equal(s1, s1 + N, B));
-}
-
-int
-main()
-{
-  test01();
-  test02();
-
-  return 0;
-}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/prev_permutation/1.cc libstdc++-v3/testsuite/25_algorithms/prev_permutation/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/prev_permutation/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/prev_permutation/1.cc	2005-05-24 19:03:07.000000000 +0200
@@ -0,0 +1,84 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.9 [lib.alg.permutation.generators]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+using std::prev_permutation;
+
+typedef test_container<int, bidirectional_iterator_wrapper> Container;
+
+void
+test1()
+{
+  // Note: The standard is unclear on what should happen in this case.
+  // This seems the only really sensible behaviour, and what is done.
+  int array[] = {0};
+  Container con(array, array);
+  VERIFY(!prev_permutation(con.begin(), con.end()));
+}
+
+void
+test2()
+{
+  int array[] = {0};
+  Container con(array, array + 1);
+  VERIFY(!prev_permutation(con.begin(), con.end()));
+}
+
+void
+test3()
+{
+  int array[] = {3, 0};
+  Container con(array, array + 2);
+  VERIFY(prev_permutation(con.begin(), con.end()));
+  VERIFY(array[0] == 0 && array[1] == 3);
+  VERIFY(!prev_permutation(con.begin(), con.end()));
+  VERIFY(array[0] == 3 && array[1] == 0);
+}
+
+void
+test4()
+{
+  int array[6] = {5, 4, 3, 2, 1, 0};
+  Container con(array, array + 6);
+  for(int i = 0 ; i < 719; ++i)
+    {
+      int temp_array[6];
+      std::copy(array, array + 6, temp_array);
+      VERIFY(prev_permutation(array, array + 6));
+      VERIFY(std::lexicographical_compare(array, array + 6,
+					  temp_array, temp_array + 6));
+    }
+  VERIFY(!prev_permutation(array,array + 6));
+  for(int i = 0; i < 6; ++i)
+    VERIFY(array[i] == 5 - i);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/prev_permutation/check_type.cc libstdc++-v3/testsuite/25_algorithms/prev_permutation/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/prev_permutation/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/prev_permutation/check_type.cc	2005-05-24 19:03:10.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.9 [lib.alg.permutation.generators]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::bidirectional_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+bool
+test1(bidirectional_iterator_wrapper<S>& s)
+{ return std::prev_permutation(s,s); }
+
+bool
+test2(bidirectional_iterator_wrapper<X>& x)
+{ return std::prev_permutation(x,x,predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/remove/1.cc libstdc++-v3/testsuite/25_algorithms/remove/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/remove/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/remove/1.cc	2005-05-24 19:16:04.000000000 +0200
@@ -0,0 +1,63 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 remove
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container; 
+
+void
+test1()
+{
+  int array[1];
+  Container con(array, array);
+  VERIFY(std::remove(con.begin(), con.end(), 1).ptr == array);
+}
+
+void
+test2()
+{
+  int array[] = {1};
+  Container con(array, array + 1);
+  VERIFY(std::remove(con.begin(), con.end(), 0).ptr == array + 1);
+  VERIFY(std::remove(con.begin(), con.end(), 1).ptr == array);
+}
+
+void
+test3()
+{
+  int array[] = {0, 1, 0, 1, 0, 0, 1, 1};
+  Container con(array, array + 8);
+  VERIFY(std::remove(con.begin(), con.end(), 1).ptr == array + 4);
+  VERIFY(array[0] == 0 && array[1] == 0 && array[2] == 0 && 
+	 array[3] == 0);
+}
+
+int
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/remove/check_type.cc libstdc++-v3/testsuite/25_algorithms/remove/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/remove/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/remove/check_type.cc	2005-05-24 19:16:08.000000000 +0200
@@ -0,0 +1,39 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.7 Remove
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct X { };
+
+struct Y { };
+
+bool
+operator==(const X&, const Y&)
+{ return true; }
+
+forward_iterator_wrapper<X>
+test1(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end, const Y& val)
+{ return std::remove(begin, end, val); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/remove_if/1.cc libstdc++-v3/testsuite/25_algorithms/remove_if/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/remove_if/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/remove_if/1.cc	2005-05-24 19:16:30.000000000 +0200
@@ -0,0 +1,66 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 remove
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container; 
+
+bool equal1(int val) { return val == 1; }
+bool equal0(int val) { return val == 0; }
+
+void
+test1()
+{
+  int array[1];
+  Container con(array, array);
+  VERIFY(std::remove_if(con.begin(), con.end(), equal1).ptr == array);
+}
+
+void
+test2()
+{
+  int array[] = {1};
+  Container con(array, array + 1);
+  VERIFY(std::remove_if(con.begin(), con.end(), equal0).ptr == array + 1);
+  VERIFY(std::remove_if(con.begin(), con.end(), equal1).ptr == array);
+}
+
+void
+test3()
+{
+  int array[] = {0, 1, 0, 1, 0, 0, 1, 1};
+  Container con(array, array + 8);
+  VERIFY(std::remove_if(con.begin(), con.end(), equal1).ptr == array + 4);
+  VERIFY(array[0] == 0 && array[1] == 0 && array[2] == 0 &&
+         array[3] == 0);
+}
+
+int
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/remove_if/check_type.cc libstdc++-v3/testsuite/25_algorithms/remove_if/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/remove_if/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/remove_if/check_type.cc	2005-05-24 19:16:33.000000000 +0200
@@ -0,0 +1,50 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.7 Remove_if
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct X { };
+
+bool
+pred_fn(const X&)
+{ return true; }
+
+struct pred_obj
+{
+  bool
+  operator()(const X&) const
+  { return true; }
+};
+
+forward_iterator_wrapper<X>
+test1(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end)
+{ return std::remove_if(begin, end, pred_fn); }
+
+forward_iterator_wrapper<X>
+test2(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end)
+{ return std::remove_if(begin, end, pred_obj()); }
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace/1.cc libstdc++-v3/testsuite/25_algorithms/replace/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace/1.cc	2005-05-24 19:17:00.000000000 +0200
@@ -0,0 +1,61 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container; 
+int array[] = {0, 0, 0, 1, 0, 1};
+
+void
+test1()
+{
+  Container con(array, array);
+  std::replace(con.begin(), con.end(), 1, 1);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  std::replace(con.begin(), con.end(), 0, 1);
+  VERIFY(array[0] == 1);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  std::replace(con.begin(), con.end(), 1, 2);
+  VERIFY(array[0] == 2 && array[1] == 0 && array[2] == 0 &&
+         array[3] == 2 && array[4] == 0 && array[5] == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace/check_type.cc libstdc++-v3/testsuite/25_algorithms/replace/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace/check_type.cc	2005-05-24 19:17:03.000000000 +0200
@@ -0,0 +1,38 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 Replace
+
+// { 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; }
+
+void
+test1(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end, const X& old_val,
+      const X& new_val)
+{ return std::replace(begin, end, old_val, new_val); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_copy/1.cc libstdc++-v3/testsuite/25_algorithms/replace_copy/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_copy/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_copy/1.cc	2005-05-24 19:17:16.000000000 +0200
@@ -0,0 +1,72 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_copy
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer; 
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+int array[] = {0, 0, 0, 1, 0, 1};
+
+void
+test1()
+{
+  int out[1];
+  Icontainer in_con(array, array);
+  Ocontainer out_con(out, out);
+  VERIFY(std::replace_copy(in_con.begin(), in_con.end(), 
+	                   out_con.begin(), 1, 1).ptr == out);
+}
+
+void
+test2()
+{
+  int out[1];
+  Icontainer in_con(array, array + 1);
+  Ocontainer out_con(out, out + 1);
+  VERIFY(std::replace_copy(in_con.begin(), in_con.end(), 
+			   out_con.begin(), 0, 1).ptr == out + 1);
+  VERIFY(out[0] == 1);
+}
+
+void
+test3()
+{
+  int out[6];
+  Icontainer in_con(array, array + 6);
+  Ocontainer out_con(out, out + 6);
+  VERIFY(std::replace_copy(in_con.begin(), in_con.end(),
+			   out_con.begin(), 1, 2).ptr == out + 6);
+  VERIFY(out[0] == 0 && out[1] == 0 && out[2] == 0 &&
+         out[3] == 2 && out[4] == 0 && out[5] == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_copy/check_type.cc libstdc++-v3/testsuite/25_algorithms/replace_copy/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_copy/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_copy/check_type.cc	2005-05-24 19:17:19.000000000 +0200
@@ -0,0 +1,56 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_copy
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct X { };
+
+struct Y { };
+
+struct Z
+{
+  Z&
+  operator=(const X&)
+  { }
+
+  Z&
+  operator=(const Y&)
+  { }
+};
+
+bool
+operator==(const X&, const Y&)
+{ return true; }
+
+output_iterator_wrapper<Z>
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end,
+      output_iterator_wrapper<Z>& output,
+      const Y& old_val, const Y& new_val)
+{ 
+  return std::replace_copy(begin, end, output, old_val, 
+			   new_val); 
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_copy_if/1.cc libstdc++-v3/testsuite/25_algorithms/replace_copy_if/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_copy_if/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_copy_if/1.cc	2005-05-24 19:17:36.000000000 +0200
@@ -0,0 +1,76 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_copy_if
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer; 
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+int array[] = {0, 0, 0, 1, 0, 1};
+
+bool
+pred(int i)
+{ return i == 1; }
+
+void
+test1()
+{
+  int out[1];
+  Icontainer in_con(array, array);
+  Ocontainer out_con(out, out);
+  VERIFY(std::replace_copy_if(in_con.begin(), in_con.end(), 
+	                      out_con.begin(), pred, 1).ptr == out);
+}
+
+void
+test2()
+{
+  int out[1];
+  Icontainer in_con(array, array + 1);
+  Ocontainer out_con(out, out + 1);
+  VERIFY(std::replace_copy_if(in_con.begin(), in_con.end(), 
+			      out_con.begin(), pred, 2).ptr == out + 1);
+  VERIFY(out[0] == 0);
+}
+
+void
+test3()
+{
+  int out[6];
+  Icontainer in_con(array, array + 6);
+  Ocontainer out_con(out, out + 6);
+  VERIFY(std::replace_copy_if(in_con.begin(), in_con.end(),
+			      out_con.begin(), pred, 2).ptr == out + 6);
+  VERIFY(out[0] == 0 && out[1] == 0 && out[2] == 0 &&
+         out[3] == 2 && out[4] == 0 && out[5] == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_copy_if/check_type.cc libstdc++-v3/testsuite/25_algorithms/replace_copy_if/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_copy_if/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_copy_if/check_type.cc	2005-05-24 19:17:39.000000000 +0200
@@ -0,0 +1,56 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_copy_if
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct X { };
+
+struct Y { };
+
+struct Z
+{
+  Z&
+  operator=(const X&)
+  { }
+
+  Z&
+  operator=(const Y&)
+  { }
+};
+
+bool
+predicate(const X&)
+{ return true; }
+
+output_iterator_wrapper<Z>
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end,
+      output_iterator_wrapper<Z>& output,
+      const Y& new_val)
+{ 
+  return std::replace_copy_if(begin, end, output, predicate, 
+			      new_val); 
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_if/1.cc libstdc++-v3/testsuite/25_algorithms/replace_if/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_if/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_if/1.cc	2005-05-24 19:17:52.000000000 +0200
@@ -0,0 +1,65 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_if
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container; 
+int array[] = {1, 0, 0, 1, 0, 1};
+
+bool
+predicate(const int& i)
+{ return i == 1; }
+
+void
+test1()
+{
+  Container con(array, array);
+  std::replace_if(con.begin(), con.end(), predicate, 1);
+}
+
+void
+test2()
+{
+  Container con(array, array + 1);
+  std::replace_if(con.begin(), con.end(), predicate, 2);
+  VERIFY(array[0] == 2);
+}
+
+void
+test3()
+{
+  Container con(array, array + 6);
+  std::replace_if(con.begin(), con.end(), predicate, 3);
+  VERIFY(array[0] == 2 && array[1] == 0 && array[2] == 0 &&
+         array[3] == 3 && array[4] == 0 && array[5] == 3);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/replace_if/check_type.cc libstdc++-v3/testsuite/25_algorithms/replace_if/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/replace_if/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/replace_if/check_type.cc	2005-05-24 19:17:55.000000000 +0200
@@ -0,0 +1,52 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 replace_if
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct X { };
+
+bool
+pred_fn(const X&)
+{ return true; }
+
+struct pred_obj
+{
+  bool
+  operator()(const X&)
+  { return true; }
+};
+
+
+void
+test1(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end, const X& new_val)
+{ return std::replace_if(begin, end, pred_fn, new_val); }
+
+void
+test2(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end, const X& new_val)
+{ return std::replace_if(begin, end, pred_obj(), new_val); }
+
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/rotate/1.cc libstdc++-v3/testsuite/25_algorithms/rotate/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/rotate/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/rotate/1.cc	2005-05-24 19:18:17.000000000 +0200
@@ -0,0 +1,126 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.10 rotate
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Fcontainer; 
+typedef test_container<int, bidirectional_iterator_wrapper> Bcontainer; 
+typedef test_container<int, random_access_iterator_wrapper> Rcontainer; 
+
+
+
+void
+test1()
+{
+  bool test __attribute__((unused)) = true;
+  int array[]={1};
+  Fcontainer fcon(array, array);
+  Bcontainer bcon(array, array);
+  Rcontainer rcon(array, array);
+  std::rotate(fcon.begin(), fcon.begin(), fcon.end());
+  std::rotate(bcon.begin(), bcon.begin(), bcon.end());
+  std::rotate(rcon.begin(), rcon.begin(), rcon.end());
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {1};
+  Fcontainer fcon(array, array + 1);
+  Bcontainer bcon(array, array + 1);
+  Rcontainer rcon(array, array + 1);
+  std::rotate(fcon.begin(), fcon.begin(), fcon.end());
+  std::rotate(bcon.begin(), bcon.begin(), bcon.end());
+  std::rotate(rcon.begin(), rcon.begin(), rcon.end());
+  std::rotate(fcon.begin(), fcon.end(), fcon.end());
+  std::rotate(bcon.begin(), bcon.end(), bcon.end());
+  std::rotate(rcon.begin(), rcon.end(), rcon.end());
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {1, 2, 3, 4, 5};
+  Fcontainer fcon(array, array + 5);
+  Bcontainer bcon(array, array + 5);
+  Rcontainer rcon(array, array + 5);
+  std::rotate(fcon.begin(), fcon.it(2), fcon.end());
+  VERIFY(array[0] == 3 && array[1] == 4 && array[2] == 5 && 
+	 array[3] == 1 && array[4] == 2);
+  std::rotate(bcon.begin(), bcon.it(2), bcon.end());
+  VERIFY(array[0] == 5 && array[1] == 1 && array[2] == 2 && 
+	 array[3] == 3 && array[4] == 4);
+  std::rotate(rcon.begin(), rcon.it(2), rcon.end());
+  VERIFY(array[0] == 2 && array[1] == 3 && array[2] == 4 && 
+	 array[3] == 5 && array[4] == 1);
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {1, 2, 3, 4};
+  Fcontainer fcon(array, array + 4);
+  Bcontainer bcon(array, array + 4);  
+  Rcontainer rcon(array, array + 4);
+
+  std::rotate(fcon.begin(), fcon.it(3), fcon.end());
+  VERIFY(array[0] == 4 && array[1] == 1 && array[2] == 2 && 
+	 array[3] == 3);
+
+  std::rotate(bcon.begin(), bcon.it(3), bcon.end());
+  VERIFY(array[0] == 3 && array[1] == 4 && array[2] == 1 && 
+	 array[3] == 2);
+
+  std::rotate(rcon.begin(), rcon.it(3), rcon.end());
+  VERIFY(array[0] == 2 && array[1] == 3 && array[2] == 4 && 
+	 array[3] == 1);
+  
+}
+
+void
+test5()
+{
+  bool test __attribute__((unused)) = true;
+  int array[] = {1, 2, 3, 4};
+  Rcontainer con(array, array + 4);
+  std::rotate(con.begin(), con.it(2), con.end());
+  VERIFY(array[0] == 3 && array[1] == 4 && array[2] == 1 && 
+	 array[3] == 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/rotate/check_type.cc libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/rotate/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc	2005-05-24 19:18:21.000000000 +0200
@@ -0,0 +1,48 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.10 Rotate
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct X { };
+
+bool operator<(X,X) { return true;}
+
+void
+test1(__gnu_test::forward_iterator_wrapper<X>& begin,
+      __gnu_test::forward_iterator_wrapper<X>& middle,
+      __gnu_test::forward_iterator_wrapper<X>& end)
+{ return std::rotate(begin,middle,end); }
+
+void
+test1(__gnu_test::bidirectional_iterator_wrapper<X>& begin,
+      __gnu_test::bidirectional_iterator_wrapper<X>& middle,
+      __gnu_test::bidirectional_iterator_wrapper<X>& end)
+{ return std::rotate(begin,middle,end); }
+
+void
+test1(__gnu_test::random_access_iterator_wrapper<X>& begin,
+      __gnu_test::random_access_iterator_wrapper<X>& middle,
+      __gnu_test::random_access_iterator_wrapper<X>& end)
+{ return std::rotate(begin,middle,end); }
+
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/rotate/rotate.cc libstdc++-v3/testsuite/25_algorithms/rotate/rotate.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/rotate/rotate.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/rotate/rotate.cc	2005-03-16 12:24:32.000000000 +0100
@@ -0,0 +1,80 @@
+// Copyright (C) 2001, 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.?? algorithms, rotate()
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <list>
+
+bool test __attribute__((unused)) = true;
+
+int A[] = {1, 2, 3, 4, 5, 6, 7};
+int B[] = {2, 3, 4, 5, 6, 7, 1};
+int C[] = {1, 2, 3, 4, 5, 6, 7};
+int D[] = {5, 6, 7, 1, 2, 3, 4};
+const int N = sizeof(A) / sizeof(int);
+
+/* need a test for a forward iterator -- can't think of one that makes sense */
+
+/* biderectional iterator */
+void
+test02()
+{
+    using std::rotate;
+    typedef std::list<int> Container;
+
+    Container a(A, A + N);
+    VERIFY(std::equal(a.begin(), a.end(), A));
+
+    Container::iterator i = a.begin();
+    rotate(a.begin(), ++i, a.end());
+    VERIFY(std::equal(a.begin(), a.end(), B));
+
+    i = a.end();
+    rotate(a.begin(), --i, a.end());
+    VERIFY(std::equal(a.begin(), a.end(), C));
+
+    i = a.begin();
+    std::advance(i, 3);
+    rotate(a.begin(), ++i, a.end());
+    VERIFY(std::equal(a.begin(), a.end(), D));
+}
+
+/* random iterator */
+void
+test03()
+{
+    using std::rotate;
+    rotate(A, A + 1, A + N);
+    VERIFY(std::equal(A, A + N, B));
+
+    rotate(A, A + N - 1, A + N);
+    VERIFY(std::equal(A, A + N, C));
+
+    rotate(A, A + 4, A + N);
+    VERIFY(std::equal(A, A + N, D));
+}
+
+int
+main()
+{
+  test02();
+  test03();
+  return 0;
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/rotate.cc libstdc++-v3/testsuite/25_algorithms/rotate.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/rotate.cc	2005-03-16 12:24:32.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/rotate.cc	1970-01-01 01:00:00.000000000 +0100
@@ -1,80 +0,0 @@
-// Copyright (C) 2001, 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.?? algorithms, rotate()
-
-#include <algorithm>
-#include <testsuite_hooks.h>
-#include <list>
-
-bool test __attribute__((unused)) = true;
-
-int A[] = {1, 2, 3, 4, 5, 6, 7};
-int B[] = {2, 3, 4, 5, 6, 7, 1};
-int C[] = {1, 2, 3, 4, 5, 6, 7};
-int D[] = {5, 6, 7, 1, 2, 3, 4};
-const int N = sizeof(A) / sizeof(int);
-
-/* need a test for a forward iterator -- can't think of one that makes sense */
-
-/* biderectional iterator */
-void
-test02()
-{
-    using std::rotate;
-    typedef std::list<int> Container;
-
-    Container a(A, A + N);
-    VERIFY(std::equal(a.begin(), a.end(), A));
-
-    Container::iterator i = a.begin();
-    rotate(a.begin(), ++i, a.end());
-    VERIFY(std::equal(a.begin(), a.end(), B));
-
-    i = a.end();
-    rotate(a.begin(), --i, a.end());
-    VERIFY(std::equal(a.begin(), a.end(), C));
-
-    i = a.begin();
-    std::advance(i, 3);
-    rotate(a.begin(), ++i, a.end());
-    VERIFY(std::equal(a.begin(), a.end(), D));
-}
-
-/* random iterator */
-void
-test03()
-{
-    using std::rotate;
-    rotate(A, A + 1, A + N);
-    VERIFY(std::equal(A, A + N, B));
-
-    rotate(A, A + N - 1, A + N);
-    VERIFY(std::equal(A, A + N, C));
-
-    rotate(A, A + 4, A + N);
-    VERIFY(std::equal(A, A + N, D));
-}
-
-int
-main()
-{
-  test02();
-  test03();
-  return 0;
-}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/search/1.cc libstdc++-v3/testsuite/25_algorithms/search/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/search/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/search/1.cc	2005-05-24 19:18:38.000000000 +0200
@@ -0,0 +1,113 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.5 [lib.alg.search]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::search;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+int array1[] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1};
+int array2[] = {0, 0, 0};
+
+void 
+test1()
+{
+  bool test __attribute__((unused)) = true;
+  Container con1(array1, array1);
+  Container con2(array1, array1 + 1);
+  VERIFY(search(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr == array1);
+  VERIFY(search(con2.begin(), con2.end(), con1.begin(), con1.end()).ptr == array1);
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  Container con1(array1, array1 + 3);
+  Container con2(array2, array2 + 3);
+  VERIFY(search(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr 
+         == array1);
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+  Container con1(array1 + 3, array1 + 10);
+  Container con2(array2, array2 + 3);
+  VERIFY(search(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr 
+         == array1 + 10);
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+  Container con1(array1, array1 + 10);
+  Container con2(array2, array2 + 1);
+  VERIFY(search(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr
+	 == array1);
+}
+
+void
+test5()
+{
+  bool test __attribute__((unused)) = true;
+  Container con1(array1 + 6, array1 + 10);
+  Container con2(array2, array2 + 1);
+  VERIFY(search(con1.begin(), con1.end(), con2.begin(), con2.end()).ptr
+	 == array1 + 10);
+}
+
+void
+test6()
+{
+  bool test __attribute__((unused)) = true;
+  int array3[]={2, 2, 1, 2, 3, 5};
+  int array4[]={1, 2, 3, 4};
+  Container con1(array3, array3 + 3);
+  Container con2(array3, array3 + 4);
+  Container con3(array3, array3 + 5);
+  Container con4(array3, array3 + 6);
+  Container endcon(array4, array4 + 4);
+  VERIFY(search(con1.begin(), con1.end(), endcon.begin(), endcon.end()).ptr
+	 == array3 + 3);
+  VERIFY(search(con2.begin(), con2.end(), endcon.begin(), endcon.end()).ptr
+	 == array3 + 4);
+  VERIFY(search(con3.begin(), con3.end(), endcon.begin(), endcon.end()).ptr
+	 == array3 + 5);
+  VERIFY(search(con4.begin(), con4.end(), endcon.begin(), endcon.end()).ptr
+	 == array3 + 6);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+  test6();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/search/check_type.cc libstdc++-v3/testsuite/25_algorithms/search/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/search/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/search/check_type.cc	2005-05-24 19:18:41.000000000 +0200
@@ -0,0 +1,46 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.1.9 [lib.alg.search]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S1 { };
+struct S2 { };
+
+bool 
+operator==(const S1&, const S2&) {return true;}
+
+struct X1 { };
+struct X2 { };
+
+bool 
+predicate(const X1&, const X2&) {return true;}
+
+forward_iterator_wrapper<S1>
+test1(forward_iterator_wrapper<S1>& s1, forward_iterator_wrapper<S2>& s2)
+{ return std::search(s1, s1, s2, s2); }
+
+forward_iterator_wrapper<X1>
+test2(forward_iterator_wrapper<X1>& x1, forward_iterator_wrapper<X2>& x2)
+{ return std::search(x1, x1, x2, x2, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/search_n/iterator.cc libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/search_n/iterator.cc	2004-11-24 07:24:09.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc	2005-05-24 19:34:17.000000000 +0200
@@ -76,7 +76,7 @@
 	  {
 	    test_container<int, forward_iterator_wrapper>
 	      forwardcon(array2, array2 + i);
-	    test_container<int, bidirectional_iterator_wrapper>
+	    test_container<int, random_access_iterator_wrapper>
 	      randomcon(array2, array2 + i);
 	    test_container<int, bidirectional_iterator_wrapper>
 	      bidircon(array2, array2 + i);
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_difference/1.cc libstdc++-v3/testsuite/25_algorithms/set_difference/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_difference/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_difference/1.cc	2005-05-24 19:19:11.000000000 +0200
@@ -0,0 +1,132 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.3 [lib.set.difference]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::set_difference;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+void 
+test1()
+{
+  int array1[1], array2[1];
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_difference(con1.begin(), con1.end(), con2.begin(), con2.end(), 
+	 con3.begin()).ptr == array2);
+}
+
+void 
+test2()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1 + 1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_difference(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array2);
+}
+
+void 
+test3()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1 + 1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2 + 1);
+  VERIFY(set_difference(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array2 + 1);
+}
+
+void 
+test4()
+{
+  int array1[]={0,1,1,2,4};
+  int array2[]={1,2,3};
+  int array3[6];
+  Icontainer con1(array1, array1 + 5);
+  Icontainer con2(array2, array2 + 3);
+  Ocontainer con3(array3, array3 + 3);
+  VERIFY(set_difference(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array3 + 3);
+  VERIFY(array3[0] == 0 && array3[1] == 1 && array3[2] == 4);
+}
+
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+typedef test_container<S, input_iterator_wrapper> SIcontainer;
+typedef test_container<S, output_iterator_wrapper> SOcontainer;
+
+void 
+test5()
+{
+  S array1[] = { -1, -1, -1, -2, -2, -3, -4};
+  S array2[] = { 1, 1, 1, 1, 2, 4, 4};
+  S array3[9];
+  SIcontainer con1(array1, array1 + 7);
+  SIcontainer con2(array2, array2 + 7);
+  SOcontainer con3(array3, array3 + 2);
+  VERIFY(set_difference(con1.begin(), con1.end(), con2.begin(), con2.end(),
+ 		   con3.begin()).ptr == array3 + 2);
+  for(int i = 0; i < 2; ++i)
+    VERIFY(array3[i].j == 0);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_difference/check_type.cc libstdc++-v3/testsuite/25_algorithms/set_difference/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_difference/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_difference/check_type.cc	2005-05-24 19:19:14.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.4 [lib.set.difference]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+output_iterator_wrapper<S>
+test1(input_iterator_wrapper<S>& in, output_iterator_wrapper<S>& out)
+{ return std::set_difference(in, in, in, in, out); }
+
+output_iterator_wrapper<X> 
+test2(input_iterator_wrapper<X>& in, output_iterator_wrapper<X>& out)
+{ return std::set_difference(in, in, in, in, out, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_intersection/1.cc libstdc++-v3/testsuite/25_algorithms/set_intersection/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_intersection/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_intersection/1.cc	2005-05-24 19:19:37.000000000 +0200
@@ -0,0 +1,132 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.3 [lib.set.intersection]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::set_intersection;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+void 
+test1()
+{
+  int array1[1], array2[1];
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_intersection(con1.begin(), con1.end(), con2.begin(), con2.end(),
+	           con3.begin()).ptr == array2);
+}
+
+void 
+test2()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1 + 1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_intersection(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array2);
+}
+
+void 
+test3()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1 + 1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_intersection(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array2);
+}
+
+void 
+test4()
+{
+  int array1[]={0,1,1,2,4};
+  int array2[]={1,2,3};
+  int array3[6];
+  Icontainer con1(array1, array1 + 5);
+  Icontainer con2(array2, array2 + 3);
+  Ocontainer con3(array3, array3 + 2);
+  VERIFY(set_intersection(con1.begin(), con1.end(), con2.begin(), con2.end(),
+			  con3.begin()).ptr == array3 + 2);
+  VERIFY(array3[0] == 1 && array3[1] == 2);
+}
+
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+typedef test_container<S, input_iterator_wrapper> SIcontainer;
+typedef test_container<S, output_iterator_wrapper> SOcontainer;
+
+void 
+test5()
+{
+  S array1[] = { -1, -1, -1, -2, -2, -4};
+  S array2[] = { 1, 1, 1, 1, 2, 3, 4, 4};
+  S array3[5];
+  SIcontainer con1(array1, array1 + 6);
+  SIcontainer con2(array2, array2 + 8);
+  SOcontainer con3(array3, array3 + 5);
+  VERIFY(set_intersection(con1.begin(), con1.end(), con2.begin(), con2.end(),
+ 		   con3.begin()).ptr == array3 + 5);
+  for(int i = 0; i < 5; ++i)
+    VERIFY(array3[i].j == 0);
+}
+
+int main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_intersection/check_type.cc libstdc++-v3/testsuite/25_algorithms/set_intersection/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_intersection/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_intersection/check_type.cc	2005-05-24 19:19:40.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.3 [lib.set.intersection]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+output_iterator_wrapper<S>
+test1(input_iterator_wrapper<S>& in, output_iterator_wrapper<S>& out)
+{ return std::set_intersection(in, in, in, in, out); }
+
+output_iterator_wrapper<X> 
+test2(input_iterator_wrapper<X>& in, output_iterator_wrapper<X>& out)
+{ return std::set_intersection(in, in, in, in, out, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_symmetric_difference/1.cc libstdc++-v3/testsuite/25_algorithms/set_symmetric_difference/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_symmetric_difference/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_symmetric_difference/1.cc	2005-05-24 19:19:55.000000000 +0200
@@ -0,0 +1,134 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.5 [lib.set.symmetric.difference]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::set_symmetric_difference;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+void
+test1()
+{
+  int array1[1], array2[1];
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_symmetric_difference(con1.begin(), con1.end(), con2.begin(), 
+				  con2.end(), con3.begin()).ptr == array2);
+}
+
+void 
+test2()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1 + 1);
+  Ocontainer con3(array2, array2 + 1);
+  VERIFY(set_symmetric_difference(con1.begin(), con1.end(), con2.begin(), 
+				  con2.end(), con3.begin()).ptr == array2 + 1);
+}
+
+void 
+test3()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1 + 1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2 + 1);
+  VERIFY(set_symmetric_difference(con1.begin(), con1.end(), con2.begin(), 
+				  con2.end(), con3.begin()).ptr == array2 + 1);
+}
+
+void 
+test4()
+{
+  int array1[]={0,1,1,2,4};
+  int array2[]={1,2,2,3};
+  int array3[5];
+  Icontainer con1(array1, array1 + 5);
+  Icontainer con2(array2, array2 + 4);
+  Ocontainer con3(array3, array3 + 5);
+  VERIFY(set_symmetric_difference(con1.begin(), con1.end(), con2.begin(), 
+				  con2.end(), con3.begin()).ptr == array3 + 5);
+  VERIFY(array3[0] == 0 && array3[1] == 1 && array3[2] == 2 &&
+	 array3[3] == 3 && array3[4] == 4);
+}
+
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+typedef test_container<S, input_iterator_wrapper> SIcontainer;
+typedef test_container<S, output_iterator_wrapper> SOcontainer;
+
+void 
+test5()
+{
+  S array1[] = { -1, -1, -2, -2, -4, -5};
+  S array2[] = { 1, 1, 1, 2, 3, 4};
+  S array3[4];
+  SIcontainer con1(array1, array1 + 6);
+  SIcontainer con2(array2, array2 + 6);
+  SOcontainer con3(array3, array3 + 4);
+  VERIFY(set_symmetric_difference(con1.begin(), con1.end(), con2.begin(), 
+				  con2.end(), con3.begin()).ptr == array3 + 4);
+  VERIFY(array3[0].j == 1 && array3[1].j == 0 && array3[2].j == 1 &&
+	 array3[3].j == 0);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_symmetric_difference/check_type.cc libstdc++-v3/testsuite/25_algorithms/set_symmetric_difference/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_symmetric_difference/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_symmetric_difference/check_type.cc	2005-05-24 19:19:57.000000000 +0200
@@ -0,0 +1,45 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.5 [lib.set.symmetric.difference]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+output_iterator_wrapper<S>
+test1(input_iterator_wrapper<S>& in, output_iterator_wrapper<S>& out)
+{ return std::set_symmetric_difference(in, in, in, in, out); }
+
+output_iterator_wrapper<X> 
+test2(input_iterator_wrapper<X>& in, output_iterator_wrapper<X>& out)
+{ return std::set_symmetric_difference(in, in, in, in, out, predicate); 
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_union/1.cc libstdc++-v3/testsuite/25_algorithms/set_union/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_union/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_union/1.cc	2005-05-24 19:20:11.000000000 +0200
@@ -0,0 +1,137 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.2 [lib.set.union]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::set_union;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+void 
+test1()
+{
+  int array1[1], array2[1];
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2);
+  VERIFY(set_union(con1.begin(), con1.end(), con2.begin(), con2.end(),
+	           con3.begin()).ptr == array2);
+}
+
+void 
+test2()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1);
+  Icontainer con2(array1, array1 + 1);
+  Ocontainer con3(array2, array2 + 1);
+  VERIFY(set_union(con1.begin(), con1.end(), con2.begin(), con2.end(),
+		   con3.begin()).ptr == array2 + 1);
+  VERIFY(array2[0] == 1);
+}
+
+void 
+test3()
+{
+  int array1[] = {1};
+  int array2[] = {0};
+  Icontainer con1(array1, array1 + 1);
+  Icontainer con2(array1, array1);
+  Ocontainer con3(array2, array2 + 1);
+  VERIFY(set_union(con1.begin(), con1.end(), con2.begin(), con2.end(),
+                   con3.begin()).ptr == array2 + 1);
+  VERIFY(array2[0] == 1);
+}
+
+void 
+test4()
+{
+  int array1[]={0,1,1,2,4};
+  int array2[]={1,2,3};
+  int array3[6];
+  Icontainer con1(array1, array1 + 5);
+  Icontainer con2(array2, array2 + 3);
+  Ocontainer con3(array3, array3 + 6);
+  VERIFY(set_union(con1.begin(), con1.end(), con2.begin(), con2.end(),
+	       con3.begin()).ptr == array3 + 6);
+  VERIFY(array3[0] == 0 && array3[1] == 1 && array3[2] == 1 &&
+	 array3[3] == 2 && array3[4] == 3 && array3[5] == 4);
+}
+
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+typedef test_container<S, input_iterator_wrapper> SIcontainer;
+typedef test_container<S, output_iterator_wrapper> SOcontainer;
+
+void 
+test5()
+{
+  S array1[] = { -1, -1, -1, -2, -2, -4};
+  S array2[] = { 1, 1, 1, 1, 2, 3, 4, 4};
+  S array3[9];
+  SIcontainer con1(array1, array1 + 6);
+  SIcontainer con2(array2, array2 + 8);
+  SOcontainer con3(array3, array3 + 9);
+  VERIFY(set_union(con1.begin(), con1.end(), con2.begin(), con2.end(),
+ 		   con3.begin()).ptr == array3 + 9);
+  VERIFY(array3[0].j == 0 && array3[1].j == 0 && array3[2].j == 0 &&
+         array3[3].j == 1 && array3[4].j == 0 && array3[5].j == 0 &&
+	 array3[6].j == 1 && array3[7].j == 0 && array3[8].j == 1);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  test5();
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/set_union/check_type.cc libstdc++-v3/testsuite/25_algorithms/set_union/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/set_union/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/set_union/check_type.cc	2005-05-24 19:20:14.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.5.2 [lib.set.union]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+output_iterator_wrapper<S>
+test1(input_iterator_wrapper<S>& in, output_iterator_wrapper<S>& out)
+{ return std::set_union(in, in, in, in, out); }
+
+output_iterator_wrapper<X> 
+test2(input_iterator_wrapper<X>& in, output_iterator_wrapper<X>& out)
+{ return std::set_union(in, in, in, in, out, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/stable_sort/1.cc libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/stable_sort/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/stable_sort/1.cc	2005-05-24 19:20:36.000000000 +0200
@@ -0,0 +1,90 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.2 [lib.stable.sort]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::stable_sort;
+
+typedef test_container<int, random_access_iterator_wrapper> Container;
+
+void 
+test1()
+{
+  int array[]={0};
+  Container con(array, array);
+  stable_sort(con.begin(), con.end());
+}
+
+void 
+test2()
+{
+  int array[] = {6, 5, 4, 3, 2, 1, 0};
+  Container con(array, array + 7);
+  stable_sort(con.begin(), con.end());
+  VERIFY(array[0] == 0 && array[1] == 1 && array[2] == 2 &&
+	 array[3] == 3 && array[4] == 4 && array[5] == 5 &&
+	 array[6] == 6);
+}
+struct S
+{
+  int i;
+  int j;
+  S() {}
+  S(int in)
+  {
+    if(in > 0)
+    {
+      i = in;
+      j = 1;
+    }
+    else
+    {
+      i = -in;
+      j = 0;
+    }
+  }
+};
+
+bool 
+operator<(const S& s1, const S& s2)
+{ return s1.i < s2.i; }
+
+void 
+test3()
+{
+
+  S array[] = {-1, -2, 1, 2, -3 ,-5 ,3 , -4, 5, 4};
+  test_container<S, random_access_iterator_wrapper> con(array,array + 10);
+  stable_sort(con.begin(), con.end());
+  for(int i = 0; i < 10; ++i)
+    VERIFY(array[i].j == i % 2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/stable_sort/check_type.cc libstdc++-v3/testsuite/25_algorithms/stable_sort/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/stable_sort/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/stable_sort/check_type.cc	2005-05-24 19:20:39.000000000 +0200
@@ -0,0 +1,49 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.1 [lib.stable.sort]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::random_access_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+void
+test1(random_access_iterator_wrapper<S>& s)
+{
+  std::stable_sort(s, s);
+}
+
+void
+test2(random_access_iterator_wrapper<X>& x)
+{
+  std::stable_sort(x, x, predicate);
+}
+
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/swap_ranges/1.cc libstdc++-v3/testsuite/25_algorithms/swap_ranges/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/swap_ranges/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/swap_ranges/1.cc	2005-05-24 19:21:02.000000000 +0200
@@ -0,0 +1,60 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.2 swap_ranges
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+typedef test_container<int, forward_iterator_wrapper> Container; 
+
+
+void
+test1()
+{
+  bool test __attribute__((unused)) = true;
+  int array1[]={1, 2};
+  int array2[]={3, 4};
+  Container con1(array1, array1 + 2);
+  Container con2(array2, array2 + 2);
+  VERIFY(std::swap_ranges(con1.begin(), con1.end(), con2.begin()).ptr ==
+	 array2 + 2);
+  VERIFY(array1[0] == 3 && array1[1] == 4 && array2[0] == 1 && array2[1] == 2);
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  int array1[] = {1};
+  int array2[] = {1};
+  Container con1(array1, array1);
+  Container con2(array2, array2);
+  VERIFY(swap_ranges(con1.begin(), con1.end(), con2.begin()).ptr == array2);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/swap_ranges/check_type.cc libstdc++-v3/testsuite/25_algorithms/swap_ranges/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/swap_ranges/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/swap_ranges/check_type.cc	2005-05-24 19:21:05.000000000 +0200
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.2.4 Swap Ranges
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct X {
+};
+
+void
+test1(forward_iterator_wrapper<X>& begin,
+      forward_iterator_wrapper<X>& end, 
+      forward_iterator_wrapper<X>& begin2)
+{ std::swap_ranges(begin, end, begin2); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/unique_copy/1.cc libstdc++-v3/testsuite/25_algorithms/unique_copy/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/unique_copy/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/unique_copy/1.cc	2005-05-24 19:21:40.000000000 +0200
@@ -0,0 +1,85 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.5.8 [lib.alg.unique]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using std::unique;
+
+typedef test_container<int, input_iterator_wrapper> Icontainer;
+typedef test_container<int, forward_iterator_wrapper> Fcontainer;
+typedef test_container<int, output_iterator_wrapper> Ocontainer;
+
+int array1[] = {0, 0, 0, 1, 1, 1};
+int array2[2];
+
+void 
+test1()
+{
+  bool test __attribute__((unused)) = true;
+  Icontainer con1(array1, array1);
+  Ocontainer con2(array2, array2);
+  VERIFY(unique_copy(con1.begin(), con1.end(), con2.begin()).ptr == array2);
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  Icontainer con1(array1, array1 + 6);
+  Ocontainer con2(array2, array2 + 2);
+  VERIFY(unique_copy(con1.begin(), con1.end(), con2.begin()).ptr 
+         == array2 + 2);
+  VERIFY(array2[0] == 0 && array2[1] == 1);
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+  Icontainer con1(array1, array1);
+  Fcontainer con2(array2, array2);
+  VERIFY(unique_copy(con1.begin(), con1.end(), con2.begin()).ptr == array2);
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+  Icontainer con1(array1, array1 + 6);
+  Fcontainer con2(array2, array2 + 2);
+  VERIFY(unique_copy(con1.begin(), con1.end(), con2.begin()).ptr
+         == array2 + 2);
+  VERIFY(array2[0] == 0 && array2[1] == 1);
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/unique_copy/check_type.cc libstdc++-v3/testsuite/25_algorithms/unique_copy/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/unique_copy/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/unique_copy/check_type.cc	2005-05-24 19:21:46.000000000 +0200
@@ -0,0 +1,55 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.5.8 [lib.alg.unique_copy]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+struct S1 { };
+
+struct S2
+{
+  S2(const S1& s1) {}
+};
+
+bool 
+operator==(const S1&, const S1&) {return true;}
+
+struct X1 { };
+
+struct X2
+{
+  X2(const X1& x1) {}
+};
+
+bool 
+predicate(const X1&, const X1&) {return true;}
+
+output_iterator_wrapper<S2> 
+test1(input_iterator_wrapper<S1>& s1, output_iterator_wrapper<S2>& s2)
+{ return std::unique_copy(s1, s1, s2); }
+
+output_iterator_wrapper<X2>
+test2(input_iterator_wrapper<X1>& x1, output_iterator_wrapper<X2>& x2)
+{ return std::unique_copy(x1, x1, x2, predicate); }
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/upper_bound/1.cc libstdc++-v3/testsuite/25_algorithms/upper_bound/1.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/upper_bound/1.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/upper_bound/1.cc	2005-05-24 19:21:58.000000000 +0200
@@ -0,0 +1,47 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.2 [lib.upper.bound]
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using std::upper_bound;
+
+typedef test_container<int, forward_iterator_wrapper> Container;
+int array[] = {0, 0, 0, 0, 1, 1, 1, 1};
+
+void 
+test1()
+{
+  for(int i = 0; i < 5; ++i)
+    for(int j = 4; j < 7; ++j)
+      {
+	Container con(array + i, array + j);
+	VERIFY(upper_bound(con.begin(), con.end(), 0).ptr == array + 4);
+      }
+}
+
+int 
+main()
+{
+  test1();
+}
diff -urN libstdc++-v3-orig/testsuite/25_algorithms/upper_bound/check_type.cc libstdc++-v3/testsuite/25_algorithms/upper_bound/check_type.cc
--- libstdc++-v3-orig/testsuite/25_algorithms/upper_bound/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/upper_bound/check_type.cc	2005-05-24 19:22:01.000000000 +0200
@@ -0,0 +1,44 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.3.2 [lib.upper.bound]
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+forward_iterator_wrapper<S>
+test1(forward_iterator_wrapper<S>& s)
+{ return std::upper_bound(s, s, *s); }
+
+forward_iterator_wrapper<X>
+test2(forward_iterator_wrapper<X>& x)
+{ return std::upper_bound(x, x, *x, predicate); }
diff -urN libstdc++-v3-orig/testsuite/ext/check_type.cc libstdc++-v3/testsuite/ext/check_type.cc
--- libstdc++-v3-orig/testsuite/ext/check_type.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/ext/check_type.cc	2005-05-24 19:45:25.000000000 +0200
@@ -0,0 +1,47 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// { dg-do compile }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::random_access_iterator_wrapper;
+
+struct S { };
+
+bool 
+operator<(const S&, const S&) {return true;}
+
+struct X { };
+
+bool 
+predicate(const X&, const X&) {return true;}
+
+bool
+test1(random_access_iterator_wrapper<S>& start,
+      random_access_iterator_wrapper<S>& end)
+{ return std::__is_heap(start, end) && std::__is_heap(start, 1); }
+
+bool
+test2(random_access_iterator_wrapper<X>& start,
+      random_access_iterator_wrapper<X>& end)
+{ 
+  return std::__is_heap(start, end, predicate) &&
+         std::__is_heap(start, predicate, 1);
+}
diff -urN libstdc++-v3-orig/testsuite/ext/median.cc libstdc++-v3/testsuite/ext/median.cc
--- libstdc++-v3-orig/testsuite/ext/median.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/ext/median.cc	2005-05-24 19:46:38.000000000 +0200
@@ -0,0 +1,42 @@
+// Copyright (C) 2005 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// median - SGI extension
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+bool pred(const int& l, const int& r)
+{
+  return l<r;
+}
+
+using std::__median;
+
+int main(void)
+{
+  const int i=1;
+  const int j=2;
+  const int k=3;
+  VERIFY(__median(i, j, k) == j && __median(i, j, k, pred) == j);
+  VERIFY(__median(i, k, j) == j && __median(i, k, j, pred) == j);
+  VERIFY(__median(j, i, k) == j && __median(j, i, k, pred) == j);
+  VERIFY(__median(j, k, i) == j && __median(j, k, i, pred) == j);
+  VERIFY(__median(k, i, j) == j && __median(k, i, j, pred) == j);
+  VERIFY(__median(k, j, i) == j && __median(k, j, i, pred) == j);
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]