From ee33b27ef0bd49227aa59f0d3bca67e7f1e0ab64 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sun, 8 Feb 2004 04:05:26 +0000
Subject: Make deque.rotate() smarter.  Beef-up related tests.

---
 Lib/test/test_deque.py      | 52 +++++++++++++++++++++++++++++++++++++--------
 Modules/collectionsmodule.c | 15 +++++++++----
 2 files changed, 54 insertions(+), 13 deletions(-)

diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index 016c2ae..f3bc59f 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -41,16 +41,50 @@ class TestBasic(unittest.TestCase):
         self.assertEqual(list(d), list(reversed('abcd')))
 
     def test_rotate(self):
-        s = 'abcde'
+        s = tuple('abcde')
+        n = len(s)
+
+        d = deque(s)
+        d.rotate(1)             # verify rot(1)
+        self.assertEqual(''.join(d), 'eabcd')
+
+        d = deque(s)
+        d.rotate(-1)            # verify rot(-1)
+        self.assertEqual(''.join(d), 'bcdea')
+        d.rotate()              # check default to 1
+        self.assertEqual(tuple(d), s)
+
+        for i in xrange(n*3):
+            d = deque(s)
+            e = deque(d)
+            d.rotate(i)         # check vs. rot(1) n times
+            for j in xrange(i):
+                e.rotate(1)
+            self.assertEqual(tuple(d), tuple(e))
+            d.rotate(-i)        # check that it works in reverse
+            self.assertEqual(tuple(d), s)
+            e.rotate(n-i)       # check that it wraps forward
+            self.assertEqual(tuple(e), s)
+
+        for i in xrange(n*3):
+            d = deque(s)
+            e = deque(d)
+            d.rotate(-i)
+            for j in xrange(i):
+                e.rotate(-1)    # check vs. rot(-1) n times
+            self.assertEqual(tuple(d), tuple(e))
+            d.rotate(i)         # check that it works in reverse
+            self.assertEqual(tuple(d), s)
+            e.rotate(i-n)       # check that it wraps backaround
+            self.assertEqual(tuple(e), s)
+
         d = deque(s)
-        d.rotate(2)
-        self.assertEqual(''.join(d), 'deabc')
-        d.rotate(3)
-        self.assertEqual(''.join(d), s)
-        d.rotate(-3)
-        self.assertEqual(''.join(d), 'deabc')
-        d.rotate(-15)
-        self.assertEqual(''.join(d), 'deabc')
+        e = deque(s)
+        e.rotate(BIG+17)        # verify on long series of rotates
+        dr = d.rotate
+        for i in xrange(BIG+17):
+            dr()
+        self.assertEqual(tuple(d), tuple(e))
 
     def test_len(self):
         d = deque('ab')
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
index d60ede1..0e0b2d6 100644
--- a/Modules/collectionsmodule.c
+++ b/Modules/collectionsmodule.c
@@ -247,14 +247,21 @@ PyDoc_STRVAR(extendleft_doc,
 static PyObject *
 deque_rotate(dequeobject *deque, PyObject *args)
 {
-	int i, n;
+	int i, n=1, len=deque->len, halflen=(len+1)>>1;
 	PyObject *item, *rv;
 
-	if (!PyArg_ParseTuple(args, "i:rotate", &n))
+	if (!PyArg_ParseTuple(args, "|i:rotate", &n))
 		return NULL;
 
-	if (n == 0  ||  deque->len == 0)
+	if (len == 0)
 		Py_RETURN_NONE;
+	if (n > halflen || n < -halflen) {
+		n %= len;
+		if (n > halflen)
+			n -= len;
+		else if (n < -halflen)
+			n += len;
+	}
 
 	for (i=0 ; i<n ; i++) {
 		item = deque_pop(deque, NULL);
@@ -280,7 +287,7 @@ deque_rotate(dequeobject *deque, PyObject *args)
 }
 
 PyDoc_STRVAR(rotate_doc, 
-"Rotate the deque n steps to the right.  If n is negative, rotates left.");
+"Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.");
 
 static int
 deque_len(dequeobject *deque)
-- 
cgit v0.12