Make deque.rotate() smarter. Beef-up related tests.
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 @@
self.assertEqual(list(d), list(reversed('abcd')))
def test_rotate(self):
- s = 'abcde'
+ s = tuple('abcde')
+ n = len(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')
+ 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)
+ 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 @@
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 @@
}
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)