2009-08-24 Chris Jefferson <chris@bubblescope.net>

	* include/stl_algo.h (__unguarded_partition_pivot,
	__move_median_first): New.
	(__insertion_sort, __unguarded_insertion_sort): Adjust for move-only
	types.
	(__unguarded_linear_insert): Assume always inserting value at __last.
	(__unguarded_partition): Take pivot by reference.
	(__introsort_loop, __introselect) : Use __unguarded_partition_pivot.
	* testsuite/25_algorithms/nth_element/moveable.cc : Enable.


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

3 files changed, 116 insertions, 65 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 56bbffa57ab..f60c2b48f1d 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,14 @@
+2009-08-24  Chris Jefferson  <chris@bubblescope.net>
+
+	* include/stl_algo.h (__unguarded_partition_pivot,
+	__move_median_first): New.
+	(__insertion_sort, __unguarded_insertion_sort): Adjust for move-only
+	types.
+	(__unguarded_linear_insert): Assume always inserting value at __last.
+	(__unguarded_partition): Take pivot by reference.
+	(__introsort_loop, __introselect) : Use __unguarded_partition_pivot.
+	* testsuite/25_algorithms/nth_element/moveable.cc : Enable.
+
 2009-08-23  Ralf Wildenhues  <Ralf.Wildenhues@gmx.de>
 
 	* libsupc++/Makefile.am (LTCOMPILE): Expand $(LIBTOOLFLAGS)
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 6418ebf6db4..a745295e9b0 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -136,6 +136,56 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	return __b;
     }
 
+  /// Swaps the median value of *__a, *__b and *__c to *__a
+  template<typename _Iterator>
+    void
+    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_Iterator>::value_type>)
+
+      if (*__a < *__b)
+	{
+	  if (*__b < *__c)
+	    std::iter_swap(__a, __b);
+	  else if (*__a < *__c)
+	    std::iter_swap(__a, __c);
+	}
+      else if (*__a < *__c)
+	return;
+      else if (*__b < *__c)
+	std::iter_swap(__a, __c);
+      else
+	std::iter_swap(__a, __b);
+    }
+
+  /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
+  template<typename _Iterator, typename _Compare>
+    void
+    __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
+			_Compare __comp)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
+	    typename iterator_traits<_Iterator>::value_type,
+	    typename iterator_traits<_Iterator>::value_type>)
+
+      if (__comp(*__a, *__b))
+	{
+	  if (__comp(*__b, *__c))
+	    std::iter_swap(__a, __b);
+	  else if (__comp(*__a, *__c))
+	    std::iter_swap(__a, __c);
+	}
+      else if (__comp(*__a, *__c))
+	return;
+      else if (__comp(*__b, *__c))
+	std::iter_swap(__a, __c);
+      else
+	std::iter_swap(__a, __b);
+    }
+
   // for_each
 
   /// This is an overload used by find() for the Input Iterator case.
@@ -2058,36 +2108,40 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     }
 
   /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator, typename _Tp>
+  template<typename _RandomAccessIterator>
     void
-    __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
+    __unguarded_linear_insert(_RandomAccessIterator __last)
     {
+      typename iterator_traits<_RandomAccessIterator>::value_type
+	__val = _GLIBCXX_MOVE(*__last);
       _RandomAccessIterator __next = __last;
       --__next;
       while (__val < *__next)
 	{
-	  *__last = *__next;
+	  *__last = _GLIBCXX_MOVE(*__next);
 	  __last = __next;
 	  --__next;
 	}
-      *__last = __val;
+      *__last = _GLIBCXX_MOVE(__val);
     }
 
   /// This is a helper function for the sort routine.
-  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
+  template<typename _RandomAccessIterator, typename _Compare>
     void
-    __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
+    __unguarded_linear_insert(_RandomAccessIterator __last,
 			      _Compare __comp)
     {
+      typename iterator_traits<_RandomAccessIterator>::value_type
+	__val = _GLIBCXX_MOVE(*__last);
       _RandomAccessIterator __next = __last;
       --__next;
       while (__comp(__val, *__next))
 	{
-	  *__last = *__next;
+	  *__last = _GLIBCXX_MOVE(*__next);
 	  __last = __next;
 	  --__next;
 	}
-      *__last = __val;
+      *__last = _GLIBCXX_MOVE(__val);
     }
 
   /// This is a helper function for the sort routine.
@@ -2101,15 +2155,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
 	{
-	  typename iterator_traits<_RandomAccessIterator>::value_type
-	    __val = *__i;
-	  if (__val < *__first)
+	  if (*__i < *__first)
 	    {
-	      std::copy_backward(__first, __i, __i + 1);
-	      *__first = __val;
+	      typename iterator_traits<_RandomAccessIterator>::value_type
+		__val = _GLIBCXX_MOVE(*__i);
+	      _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+	      *__first = _GLIBCXX_MOVE(__val);
 	    }
 	  else
-	    std::__unguarded_linear_insert(__i, __val);
+	    std::__unguarded_linear_insert(__i);
 	}
     }
 
@@ -2123,15 +2177,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
 	{
-	  typename iterator_traits<_RandomAccessIterator>::value_type
-	    __val = *__i;
-	  if (__comp(__val, *__first))
+	  if (__comp(*__i, *__first))
 	    {
-	      std::copy_backward(__first, __i, __i + 1);
-	      *__first = __val;
+	      typename iterator_traits<_RandomAccessIterator>::value_type
+		__val = _GLIBCXX_MOVE(*__i);
+	      _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+	      *__first = _GLIBCXX_MOVE(__val);
 	    }
 	  else
-	    std::__unguarded_linear_insert(__i, __val, __comp);
+	    std::__unguarded_linear_insert(__i, __comp);
 	}
     }
 
@@ -2145,7 +2199,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	_ValueType;
 
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-	std::__unguarded_linear_insert(__i, _ValueType(*__i));
+	std::__unguarded_linear_insert(__i);
     }
 
   /// This is a helper function for the sort routine.
@@ -2158,7 +2212,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	_ValueType;
 
       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
-	std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
+	std::__unguarded_linear_insert(__i, __comp);
     }
 
   /**
@@ -2202,7 +2256,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
   template<typename _RandomAccessIterator, typename _Tp>
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
-			  _RandomAccessIterator __last, _Tp __pivot)
+			  _RandomAccessIterator __last, const _Tp& __pivot)
     {
       while (true)
 	{
@@ -2223,7 +2277,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
 			  _RandomAccessIterator __last,
-			  _Tp __pivot, _Compare __comp)
+			  const _Tp& __pivot, _Compare __comp)
     {
       while (true)
 	{
@@ -2239,6 +2293,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	}
     }
 
+  /// This is a helper function...
+  template<typename _RandomAccessIterator>
+    inline _RandomAccessIterator
+    __unguarded_partition_pivot(_RandomAccessIterator __first,
+				_RandomAccessIterator __last)
+    {
+      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
+      std::__move_median_first(__first, __mid, (__last - 1));
+      return std::__unguarded_partition(__first + 1, __last, *__first);
+    }
+
+
+  /// This is a helper function...
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline _RandomAccessIterator
+    __unguarded_partition_pivot(_RandomAccessIterator __first,
+				_RandomAccessIterator __last, _Compare __comp)
+    {
+      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
+      std::__move_median_first(__first, __mid, (__last - 1), __comp);
+      return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
+    }
+
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Size>
     void
@@ -2246,9 +2323,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 		     _RandomAccessIterator __last,
 		     _Size __depth_limit)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       while (__last - __first > int(_S_threshold))
 	{
 	  if (__depth_limit == 0)
@@ -2258,14 +2332,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	    }
 	  --__depth_limit;
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last
-								  - 1))));
+	    std::__unguarded_partition_pivot(__first, __last);
 	  std::__introsort_loop(__cut, __last, __depth_limit);
 	  __last = __cut;
 	}
@@ -2278,9 +2345,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 		     _RandomAccessIterator __last,
 		     _Size __depth_limit, _Compare __comp)
     {
-      typedef typename iterator_traits<_RandomAccessIterator>::value_type
-	_ValueType;
-
       while (__last - __first > int(_S_threshold))
 	{
 	  if (__depth_limit == 0)
@@ -2290,15 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	    }
 	  --__depth_limit;
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last - 1),
-								__comp)),
-				       __comp);
+	    std::__unguarded_partition_pivot(__first, __last, __comp);
 	  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
 	  __last = __cut;
 	}
@@ -2349,14 +2405,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	    }
 	  --__depth_limit;
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last
-								  - 1))));
+	    std::__unguarded_partition_pivot(__first, __last);
 	  if (__cut <= __nth)
 	    __first = __cut;
 	  else
@@ -2385,15 +2434,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	    }
 	  --__depth_limit;
 	  _RandomAccessIterator __cut =
-	    std::__unguarded_partition(__first, __last,
-				       _ValueType(std::__median(*__first,
-								*(__first
-								  + (__last
-								     - __first)
-								  / 2),
-								*(__last - 1),
-								__comp)),
-				       __comp);
+	    std::__unguarded_partition_pivot(__first, __last, __comp);
 	  if (__cut <= __nth)
 	    __first = __cut;
 	  else
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
index cb729492bf2..005f6ec7cbc 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
@@ -1,4 +1,3 @@
-// { dg-require-rvalref "" }
 // { dg-options "-std=gnu++0x" }
 
 // Copyright (C) 2005, 2007, 2009 Free Software Foundation, Inc.