2001-07-17 Stephen M. Webb <stephen@bregmasoft.com>r

	All occurrences of the __value_type() and __distance_type()
	functions, which were required to support the HP STL, have been
	removed along with all the auxiliary forwarding functions that
	were required to support their use.

	The __iterator_category() function was pretty much left alone
	because there was no benefit to removing it and its use made code
	just a little more readable.

	Incidences of distance() with nonstandard argument list were
	replaced by calls to the standard function (only in the files
	affected by the removal of the other HP functions).

	The signature of the rotate() algorithm was changed to match the
	standard.

	Headers were reformatted under C++STYLE guidelines (indentation,
	linebreaks, typename keyword).

	* include/bits/stl_algo.h: replaced __value_type() and
	__distance_type() with iterator_traits, eliminated auxiliary
	support functions required to support said function usage.
	Changed nonstandard distance() call to standard call.

	* include/bits/stl_algobase.h: Same.
	* include/bits/stl_heap.h: Same.
	* include/bits/stl_numeric.h: Same.
	* include/bits/stl_uninitialized.h: Same.
	* include/bits/stl_iterator_base_types.h (__value_type()):
	Removed.
	(__distance_type()): Removed.
	(value_type()): Gone.
	(distance_type()): Done in.
	(iterator_category()): Hasta la vista, baby.

	* include/bits/stl_iterator_base_funcs.h (iterator_category()):
	Replaced with __iterator_category().
	* include/backward/iterator.h: moved definition of value_type(),
	distance_type(), and iterator_category() out of std:: and into
	here.
	* testsuite/23_containers/vector_ctor.cc (test03): New testcases.
	* testsuite/23_containers/vector_modifiers.cc (test03): New testcases.
	* testsuite/25_algorithms/rotate.cc: New testcase.
	* testsuite/25_algorithms/copy.cc: New testcase.
	* testsuite/25_algorithms/sort.cc: Same.
	* testsuite/25_algorithms/heap.cc: Same.
	* testsuite/25_algorithms/partition.cc: Same.
	* testsuite/25_algorithms/binary_search.cc: Same.
	* testsuite/26_numerics/sum_diff.cc: Ditto.


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

10 files changed, 810 insertions, 22 deletions

diff --git a/libstdc++-v3/testsuite/23_containers/vector_ctor.cc b/libstdc++-v3/testsuite/23_containers/vector_ctor.cc
index 6e97159281b..94782bf2509 100644
--- a/libstdc++-v3/testsuite/23_containers/vector_ctor.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector_ctor.cc
@@ -1,7 +1,6 @@
-// 1999-06-29
-// bkoz 
+// 1999-06-29 bkoz
 
-// Copyright (C) 1999, 2000 Free Software Foundation, Inc.
+// Copyright (C) 1999-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
@@ -57,10 +56,36 @@ void test02()
   std::vector<int> v2 (v1);
 }
 
+// test range constructors and range-fill constructor
+void
+test03()
+{
+    const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+    const int B[] = {7, 7, 7, 7, 7};
+    const int N = sizeof(A) / sizeof(int);
+    const int M = sizeof(B) / sizeof(int);
+    bool test = true;
+
+    std::vector<int> v3(A, A + N);
+    VERIFY(std::equal(v3.begin(), v3.end(), A));
+
+    std::vector<int> v4(v3.begin(), v3.end());
+    VERIFY(std::equal(v4.begin(), v4.end(), A));
+
+    std::vector<int> v5(M, 7);
+    VERIFY(std::equal(v5.begin(), v5.end(), B));
+    VERIFY(std::equal(B, B + M, v5.begin()));
+
+#ifdef DEBUG_ASSERT
+  assert(test);
+#endif
+}
 
 int main()
 {
   test01();
   test02(); 
+  test03();
+
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector_modifiers.cc b/libstdc++-v3/testsuite/23_containers/vector_modifiers.cc
index 7ca7cf6390e..db18b9a41a3 100644
--- a/libstdc++-v3/testsuite/23_containers/vector_modifiers.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector_modifiers.cc
@@ -1,6 +1,6 @@
 // 1999-11-09 bkoz
 
-// Copyright (C) 1999 Free Software Foundation, Inc.
+// Copyright (C) 1999, 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
@@ -21,7 +21,9 @@
 // 23.2.4.3 vector modifiers
 
 #include <vector>
-#include <debug_assert.h>
+#include "debug_assert.h"
+
+bool test = true;
 
 template<typename T>
   struct A { };
@@ -29,10 +31,9 @@ template<typename T>
 struct B { };
 
 // vector::insert(iterator, inputiterator first, inputiterator last)
-bool test01()
+void
+test01()
 {
-  bool test = true;
-
   // POD types
   typedef std::vector<int> 	vec_POD;
   vec_POD	vec01;
@@ -46,20 +47,42 @@ bool test01()
   A<B>		np01;
   A<B>*		pnp01 = &np01;
   vec02.insert(vec02.begin(), pnp01, pnp01 + 1);
+}
+
+// test the assign() function
+void
+test03()
+{
+  const int K = 417;
+  const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+  const int B[] = {K, K, K, K, K};
+  const int N = sizeof(A) / sizeof(int);
+  const int M = sizeof(B) / sizeof(int);
+  bool test = true;
+
+  // assign from pointer range
+  std::vector<int> v3;
+  v3.assign(A, A + N);
+  VERIFY(std::equal(v3.begin(), v3.end(), A));
+  VERIFY(v3.size() == N);
 
-  // Test that assign compiles.
-  vec01.assign (pi01, pi01 + 1);
+  // assign from iterator range
+  std::vector<int> v4;
+  v4.assign(v3.begin(), v3.end());
+  VERIFY(std::equal(v4.begin(), v4.end(), A));
+  VERIFY(std::equal(A, A + N, v4.begin()));
 
-#ifdef DEBUG_ASSERT
-  assert(test);
-#endif
-  
-  return test;
+  // assign from initializer range with resize
+  v4.assign(M, K);
+  VERIFY(std::equal(v4.begin(), v4.end(), B));
+  VERIFY(std::equal(B, B + M, v4.begin()));
+  VERIFY((v4.size() == M) && (M != N));
 }
 
 int main()
 {
   test01();
+  test03();
 
-  return 0;
+  return !test;
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/binary_search.cc b/libstdc++-v3/testsuite/25_algorithms/binary_search.cc
new file mode 100644
index 00000000000..7e4396b4cb5
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/binary_search.cc
@@ -0,0 +1,183 @@
+// 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 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 [lib.alg.binary.search] Binary search algorithms.
+
+#include <algorithm>
+#include <debug_assert.h>
+
+bool test = true;
+
+const int A[] = {1, 2, 3, 3, 3, 5, 8};
+const int C[] = {8, 5, 3, 3, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+
+// A comparison, equalivalent to std::greater<int> without the
+// dependency on <functional>.
+
+struct gt
+{
+    bool
+    operator()(const int& x, const int& y) const
+    { return x > y; }
+};
+
+// Each test performs general-case, bookend, not-found condition,
+// and predicate functional checks.
+
+// 25.3.3.1 lower_bound, with and without comparison predicate
+void
+test01()
+{
+    using std::lower_bound;
+
+    const int first = A[0];
+    const int last = A[N - 1];
+
+    const int* p = lower_bound(A, A + N, 3);
+    VERIFY(p == A + 2);
+
+    const int* q = lower_bound(A, A + N, first);
+    VERIFY(q == A + 0);
+
+    const int* r = lower_bound(A, A + N, last);
+    VERIFY(r == A + N - 1);
+
+    const int* s = lower_bound(A, A + N, 4);
+    VERIFY(s == A + 5);
+
+    const int* t = lower_bound(C, C + N, 3, gt());
+    VERIFY(t == C + 2);
+
+    const int* u = lower_bound(C, C + N, first, gt());
+    VERIFY(u == C + N - 1);
+
+    const int* v = lower_bound(C, C + N, last, gt());
+    VERIFY(v == C + 0);
+
+    const int* w = lower_bound(C, C + N, 4, gt());
+    VERIFY(w == C + 2);
+}
+
+// 25.3.3.2 upper_bound, with and without comparison predicate
+void
+test02()
+{
+    using std::upper_bound;
+
+    const int first = A[0];
+    const int last = A[N - 1];
+
+    const int* p = upper_bound(A, A + N, 3);
+    VERIFY(p == A + 5);
+
+    const int* q = upper_bound(A, A + N, first);
+    VERIFY(q == A + 1);
+
+    const int* r = upper_bound(A, A + N, last);
+    VERIFY(r == A + N);
+
+    const int* s = upper_bound(A, A + N, 4);
+    VERIFY(s == A + 5);
+
+    const int* t = upper_bound(C, C + N, 3, gt());
+    VERIFY(t == C + 5);
+
+    const int* u = upper_bound(C, C + N, first, gt());
+    VERIFY(u == C + N);
+
+    const int* v = upper_bound(C, C + N, last, gt());
+    VERIFY(v == C + 1);
+
+    const int* w = upper_bound(C, C + N, 4, gt());
+    VERIFY(w == C + 2);
+}
+
+// 25.3.3.3 equal_range, with and without comparison predicate
+void
+test03()
+{
+    using std::equal_range;
+    typedef std::pair<const int*, const int*> Ipair;
+    
+    const int first = A[0];
+    const int last = A[N - 1];
+
+    Ipair p = equal_range(A, A + N, 3);
+    VERIFY(p.first == A + 2);
+    VERIFY(p.second == A + 5);
+    
+    Ipair q = equal_range(A, A + N, first);
+    VERIFY(q.first == A + 0);
+    VERIFY(q.second == A + 1);
+    
+    Ipair r = equal_range(A, A + N, last);
+    VERIFY(r.first == A + N - 1);
+    VERIFY(r.second == A + N);
+    
+    Ipair s = equal_range(A, A + N, 4);
+    VERIFY(s.first == A + 5);
+    VERIFY(s.second == A + 5);
+    
+    Ipair t = equal_range(C, C + N, 3, gt());
+    VERIFY(t.first == C + 2);
+    VERIFY(t.second == C + 5);
+    
+    Ipair u = equal_range(C, C + N, first, gt());
+    VERIFY(u.first == C + N - 1);
+    VERIFY(u.second == C + N);
+    
+    Ipair v = equal_range(C, C + N, last, gt());
+    VERIFY(v.first == C + 0);
+    VERIFY(v.second == C + 1);
+    
+    Ipair w = equal_range(C, C + N, 4, gt());
+    VERIFY(w.first == C + 2);
+    VERIFY(w.second == C + 2);
+}
+
+// 25.3.3.4 binary_search, with and without comparison predicate
+void
+test04()
+{
+    using std::binary_search;
+    
+    const int first = A[0];
+    const int last = A[N - 1];
+
+    VERIFY(binary_search(A, A + N, 5));
+    VERIFY(binary_search(A, A + N, first));
+    VERIFY(binary_search(A, A + N, last));
+    VERIFY(!binary_search(A, A + N, 4));
+
+    VERIFY(binary_search(C, C + N, 5, gt()));
+    VERIFY(binary_search(C, C + N, first, gt()));
+    VERIFY(binary_search(C, C + N, last, gt()));
+    VERIFY(!binary_search(C, C + N, 4, gt()));
+}
+
+int
+main(int argc, char* argv[])
+{
+    test01();
+    test02();
+    test03();
+    test04();
+
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy.cc b/libstdc++-v3/testsuite/25_algorithms/copy.cc
new file mode 100644
index 00000000000..f08694f28b3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy.cc
@@ -0,0 +1,58 @@
+// 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 <debug_assert.h>
+
+bool test = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+const int N = sizeof(A) / sizeof(int);
+
+// copy
+void
+test01()
+{
+    using std::copy;
+
+    int s1[N];
+    copy(A, A + N, s1);
+    VERIFY(std::equal(s1, s1 + N, A));
+}
+
+// copy_backward
+void
+test02()
+{
+    using std::copy_backward;
+
+    int s1[N];
+    copy_backward(A, A + N, s1 + N);
+    VERIFY(std::equal(s1, s1 + N, A));
+}
+
+int
+main(int argc, char* argv[])
+{
+    test01();
+    test02();
+
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/heap.cc b/libstdc++-v3/testsuite/25_algorithms/heap.cc
new file mode 100644
index 00000000000..452b6aaa905
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/heap.cc
@@ -0,0 +1,132 @@
+// 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 <debug_assert.h>
+
+bool test = 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);
+        VERIFY(gt.count() <= logN);
+        gt.reset();
+    }
+
+    for (int i = N; i >= 2; --i) {
+        std::pop_heap(s1, s1 + i, gt);
+        VERIFY(gt.count() <= 2 * logN);
+        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);
+    VERIFY(gt.count() <= 3 * N);
+    gt.reset();
+
+    std::sort_heap(s2, s2 + N, gt);
+    VERIFY(gt.count() <= N * logN);
+
+    VERIFY(std::equal(s2, s2 + N, C));
+}
+
+int
+main(int argc, char* argv[])
+{
+    test01();
+    test02();
+
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/partition.cc b/libstdc++-v3/testsuite/25_algorithms/partition.cc
new file mode 100644
index 00000000000..6623cd3f0ed
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/partition.cc
@@ -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 <debug_assert.h>
+
+bool test = 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(int argc, char* argv[])
+{
+    test01();
+    test02();
+
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate.cc b/libstdc++-v3/testsuite/25_algorithms/rotate.cc
new file mode 100644
index 00000000000..e80d3cd3cd3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate.cc
@@ -0,0 +1,80 @@
+// 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 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 <debug_assert.h>
+#include <list>
+
+bool test = 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(int argc, char* argv[])
+{
+    test02();
+    test03();
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort.cc b/libstdc++-v3/testsuite/25_algorithms/sort.cc
new file mode 100644
index 00000000000..f26dd018727
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort.cc
@@ -0,0 +1,171 @@
+// 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 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 algorithms, sort()
+
+#include <algorithm>
+#include <debug_assert.h>
+
+bool test = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
+const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
+const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+const int logN = 3; // ln(N) rounded up
+const int P = 7;
+
+// comparison predicate for stable_sort: order by rightmost digit
+struct CompLast
+{
+    bool
+    operator()(const int x, const int y)
+    { return x % 10 < y % 10; }
+};
+
+// 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;
+
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::sort(s1, s1 + N);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    Gt gt;
+    gt.reset();
+    std::sort(s1, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + N, C));
+}
+
+// 25.3.1.2 stable_sort()
+void
+test02()
+{
+    int s1[N];
+    std::copy(A, A + N, s1);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    std::stable_sort(s1, s1 + N, CompLast());
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::stable_sort(s1, s1 + N);
+    VERIFY(std::equal(s1, s1 + N, A));
+
+    Gt gt;
+    gt.reset();
+    std::stable_sort(s1, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + N, C));
+    VERIFY(gt.count() <= N * logN * logN);
+}
+
+// 25.3.1.3 partial_sort()
+void
+test03()
+{
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    std::partial_sort(s1, s1 + P, s1 + N);
+    VERIFY(std::equal(s1, s1 + P, A));
+
+    Gt gt;
+    gt.reset();
+    std::partial_sort(s1, s1 + P, s1 + N, gt);
+    VERIFY(std::equal(s1, s1 + P, C));
+}
+
+// 25.3.1.4 partial_sort_copy()
+void
+test04()
+{
+    using std::partial_sort_copy;
+
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    int s2[2*N];
+
+    partial_sort_copy(s1, s1 + N, s2, s2 + P);
+    VERIFY(std::equal(s2, s2 + P, A));
+
+    Gt gt;
+    gt.reset();
+    partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
+    VERIFY(std::equal(s2, s2 + P, C));
+
+    VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
+}
+
+// 25.3.2 nth_element()
+void
+test05()
+{
+    using std::nth_element;
+
+    int s1[N];
+    std::copy(B, B + N, s1);
+    VERIFY(std::equal(s1, s1 + N, B));
+
+    int* pn = s1 + (N / 2) - 1;
+    nth_element(s1, pn, s1 + N);
+    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
+
+    CompLast pred;
+    nth_element(s1, pn, s1 + N, pred);
+    for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
+}
+
+int
+main(int argc, char* argv[])
+{
+    test01();
+    test02();
+    test03();
+    test04();
+    test05();
+
+    return !test;
+}
diff --git a/libstdc++-v3/testsuite/26_numerics/sum_diff.cc b/libstdc++-v3/testsuite/26_numerics/sum_diff.cc
new file mode 100644
index 00000000000..ffc4e639c1c
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/sum_diff.cc
@@ -0,0 +1,47 @@
+// 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 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.
+
+// 26.4.3 [lib.partial.sum]
+// 26.4.4 [lib.adjacent.difference]
+
+#include <algorithm>
+#include <numeric>
+#include <cassert>
+
+int A[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
+int B[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
+const int N = sizeof(A) / sizeof(int);
+
+void
+test01()
+{
+    int D[N];
+
+    std::adjacent_difference(A, A + N, D);
+    assert(std::equal(D, D + N, B));
+
+    std::partial_sum(D, D + N, D);
+    assert(std::equal(D, D + N, A));
+}
+
+int
+main(int argc, char* argv[])
+{
+    test01();
+    return 0;
+}
diff --git a/libstdc++-v3/testsuite/Makefile.in b/libstdc++-v3/testsuite/Makefile.in
index 2c350e5a1c4..1af4d4e6d0c 100644
--- a/libstdc++-v3/testsuite/Makefile.in
+++ b/libstdc++-v3/testsuite/Makefile.in
@@ -128,14 +128,10 @@ AUTOMAKE_OPTIONS = foreign dejagnu
 
 DEJATOOL = libstdc++-v3
 
-EXPECT = `if [ -f @glibcpp_builddir@/../../expect/expect ] ; then \
-            echo @glibcpp_builddir@/../../expect/expect ; \
-          else echo expect ; fi`
+EXPECT = `if [ -f @glibcpp_builddir@/../../expect/expect ] ; then             echo @glibcpp_builddir@/../../expect/expect ;           else echo expect ; fi`
 
 
-RUNTEST = `if [ -f @glibcpp_srcdir@/../dejagnu/runtest ] ; then \
-	       echo @glibcpp_srcdir@/../dejagnu/runtest ; \
-	    else echo runtest; fi`
+RUNTEST = `if [ -f @glibcpp_srcdir@/../dejagnu/runtest ] ; then 	       echo @glibcpp_srcdir@/../dejagnu/runtest ; 	    else echo runtest; fi`
 
 
 RUNTESTFLAGS =