diff mbox

libstdc++/58357 DR 488 std::rotate should return an iterator

Message ID 20150117031607.GP3360@redhat.com
State New
Headers show

Commit Message

Jonathan Wakely Jan. 17, 2015, 3:16 a.m. UTC
http://cplusplus.github.io/LWG/lwg-defects.html#488

Tested x86_64-linux, committed to trunk.
diff mbox

Patch

commit a5ae94562335d47358186f76ca71cc6cf0560ed8
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Sep 23 00:11:26 2014 +0100

    	DR 488
    	PR libstdc++/58357
    	* include/bits/algorithmfwd.h (rotate): Return an iterator.
    	* include/bits/stl_algo.h (rotate, __rotate): Likewise.
    	* testsuite/25_algorithms/rotate/dr488.cc: New.
    	* testsuite/25_algorithms/rotate/check_type.cc: Adjust function type.
    	* testsuite/25_algorithms/rotate/requirements/explicit_instantiation/
    	2.cc: Likewise.
    	* testsuite/25_algorithms/rotate/requirements/explicit_instantiation/
    	pod.cc: Likewise.

diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 283c5e6..11361bb 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -531,7 +531,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     reverse_copy(_BIter, _BIter, _OIter);
 
   template<typename _FIter>
-    void 
+    _FIter
     rotate(_FIter, _FIter, _FIter);
 
   template<typename _FIter, typename _OIter>
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index da642e6..3325b94 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1239,14 +1239,16 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the rotate algorithm.
   template<typename _ForwardIterator>
-    void
+    _ForwardIterator
     __rotate(_ForwardIterator __first,
 	     _ForwardIterator __middle,
 	     _ForwardIterator __last,
 	     forward_iterator_tag)
     {
-      if (__first == __middle || __last  == __middle)
-	return;
+      if (__first == __middle)
+	return __last;
+      else if (__last  == __middle)
+	return __first;
 
       _ForwardIterator __first2 = __middle;
       do
@@ -1259,6 +1261,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
       while (__first2 != __last);
 
+      _ForwardIterator __ret = __first;
+
       __first2 = __middle;
 
       while (__first2 != __last)
@@ -1271,11 +1275,12 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  else if (__first2 == __last)
 	    __first2 = __middle;
 	}
+      return __ret;
     }
 
    /// This is a helper function for the rotate algorithm.
   template<typename _BidirectionalIterator>
-    void
+    _BidirectionalIterator
     __rotate(_BidirectionalIterator __first,
 	     _BidirectionalIterator __middle,
 	     _BidirectionalIterator __last,
@@ -1285,8 +1290,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
 				  _BidirectionalIterator>)
 
-      if (__first == __middle || __last  == __middle)
-	return;
+      if (__first == __middle)
+	return __last;
+      else if (__last  == __middle)
+	return __first;
 
       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
@@ -1298,14 +1305,20 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
 
       if (__first == __middle)
-	std::__reverse(__middle, __last,   bidirectional_iterator_tag());
+	{
+	  std::__reverse(__middle, __last,   bidirectional_iterator_tag());
+	  return __last;
+	}
       else
-	std::__reverse(__first,  __middle, bidirectional_iterator_tag());
+	{
+	  std::__reverse(__first,  __middle, bidirectional_iterator_tag());
+	  return __first;
+	}
     }
 
   /// This is a helper function for the rotate algorithm.
   template<typename _RandomAccessIterator>
-    void
+    _RandomAccessIterator
     __rotate(_RandomAccessIterator __first,
 	     _RandomAccessIterator __middle,
 	     _RandomAccessIterator __last,
@@ -1315,8 +1328,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 				  _RandomAccessIterator>)
 
-      if (__first == __middle || __last  == __middle)
-	return;
+      if (__first == __middle)
+	return __last;
+      else if (__last  == __middle)
+	return __first;
 
       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 	_Distance;
@@ -1329,10 +1344,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__k == __n - __k)
 	{
 	  std::swap_ranges(__first, __middle, __middle);
-	  return;
+	  return __middle;
 	}
 
       _RandomAccessIterator __p = __first;
+      _RandomAccessIterator __ret = __first + (__last - __middle);
 
       for (;;)
 	{
@@ -1343,7 +1359,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  _ValueType __t = _GLIBCXX_MOVE(*__p);
 		  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
 		  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
-		  return;
+		  return __ret;
 		}
 	      _RandomAccessIterator __q = __p + __k;
 	      for (_Distance __i = 0; __i < __n - __k; ++ __i)
@@ -1354,7 +1370,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		}
 	      __n %= __k;
 	      if (__n == 0)
-		return;
+		return __ret;
 	      std::swap(__n, __k);
 	      __k = __n - __k;
 	    }
@@ -1366,7 +1382,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
 		  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
 		  *__p = _GLIBCXX_MOVE(__t);
-		  return;
+		  return __ret;
 		}
 	      _RandomAccessIterator __q = __p + __n;
 	      __p = __q - __k;
@@ -1378,19 +1394,21 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		}
 	      __n %= __k;
 	      if (__n == 0)
-		return;
+		return __ret;
 	      std::swap(__n, __k);
 	    }
 	}
     }
 
+   // _GLIBCXX_RESOLVE_LIB_DEFECTS
+   // DR 488. rotate throws away useful information
   /**
    *  @brief Rotate the elements of a sequence.
    *  @ingroup mutating_algorithms
    *  @param  __first   A forward iterator.
    *  @param  __middle  A forward iterator.
    *  @param  __last    A forward iterator.
-   *  @return  Nothing.
+   *  @return  first + (last - middle).
    *
    *  Rotates the elements of the range @p [__first,__last) by 
    *  @p (__middle - __first) positions so that the element at @p __middle
@@ -1406,7 +1424,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  for each @p n in the range @p [0,__last-__first).
   */
   template<typename _ForwardIterator>
-    inline void
+    inline _ForwardIterator
     rotate(_ForwardIterator __first, _ForwardIterator __middle,
 	   _ForwardIterator __last)
     {
@@ -1416,8 +1434,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      std::__rotate(__first, __middle, __last,
-		    std::__iterator_category(__first));
+      return std::__rotate(__first, __middle, __last,
+			   std::__iterator_category(__first));
     }
 
   /**
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
index f464364..9d4c382 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
@@ -26,19 +26,19 @@  struct X { };
 
 bool operator<(X,X) { return true;}
 
-void
+__gnu_test::forward_iterator_wrapper<X>
 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
+__gnu_test::bidirectional_iterator_wrapper<X>
 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
+__gnu_test::random_access_iterator_wrapper<X>
 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)
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc
new file mode 100644
index 0000000..60bd033
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc
@@ -0,0 +1,77 @@ 
+// Copyright (C) 2015 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 3, 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 COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <algorithm>
+#include <iterator>
+#include <forward_list>
+#include <list>
+#include <vector>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(Container& c)
+{
+  int size = std::distance(c.begin(), c.end());
+  for (int i=0; i < size; ++i)
+  {
+    auto first = c.begin(), middle = std::next(first, i), last = c.end();
+    auto r = std::rotate(first, middle, last);
+    auto expected = std::next(first, std::distance(middle, last));
+    VERIFY( r == expected );
+  }
+}
+
+void
+test01()
+{
+  // test random access iterators
+  std::vector<int> v{ 0, 1, 2, 3, 4 };
+  test(v);
+  v.push_back(5);
+  test(v);
+}
+
+void
+test02()
+{
+  // test bidirectional iterators
+  std::list<int> l{ 0, 1, 2, 3, 4 };
+  test(l);
+  l.push_back(5);
+  test(l);
+}
+
+void
+test03()
+{
+  // test forward iterators
+  std::forward_list<int> l{ 0, 1, 2, 3, 4 };
+  test(l);
+  l.push_front(5);
+  test(l);
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
index d48e653..ec8c917 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
@@ -30,5 +30,5 @@  namespace std
   typedef NonDefaultConstructible 		value_type;
   typedef value_type* 		iterator_type;
 
-  template void rotate(iterator_type, iterator_type, iterator_type);
+  template iterator_type rotate(iterator_type, iterator_type, iterator_type);
 } 
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
index 5804c63..c24ee70 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
@@ -30,5 +30,5 @@  namespace std
   typedef pod_int 		value_type;
   typedef value_type* 		iterator_type;
 
-  template void rotate(iterator_type, iterator_type, iterator_type);
+  template iterator_type rotate(iterator_type, iterator_type, iterator_type);
 }