Implement and apply PEP 322, reverse iteration
diff --git a/Doc/lib/libfuncs.tex b/Doc/lib/libfuncs.tex
index a9f3a65..7d64f93 100644
--- a/Doc/lib/libfuncs.tex
+++ b/Doc/lib/libfuncs.tex
@@ -880,6 +880,14 @@
when passed to \function{eval()}.
\end{funcdesc}
+\begin{funcdesc}{reversed}{seq}
+ Return a reverse iterator. \var{seq} must be an object which
+ supports the sequence protocol (the __len__() method and the
+ \method{__getitem__()} method with integer arguments starting at
+ \code{0}).
+ \versionadded{2.4}
+\end{funcdesc}
+
\begin{funcdesc}{round}{x\optional{, n}}
Return the floating point value \var{x} rounded to \var{n} digits
after the decimal point. If \var{n} is omitted, it defaults to zero.
diff --git a/Include/enumobject.h b/Include/enumobject.h
index 053fb72..c14dbfc 100644
--- a/Include/enumobject.h
+++ b/Include/enumobject.h
@@ -8,6 +8,7 @@
#endif
PyAPI_DATA(PyTypeObject) PyEnum_Type;
+PyAPI_DATA(PyTypeObject) PyReversed_Type;
#ifdef __cplusplus
}
diff --git a/Lib/heapq.py b/Lib/heapq.py
index 2c30b12..2223a97 100644
--- a/Lib/heapq.py
+++ b/Lib/heapq.py
@@ -165,7 +165,7 @@
# or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
# j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is
# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
- for i in xrange(n//2 - 1, -1, -1):
+ for i in reversed(xrange(n//2)):
_siftup(x, i)
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
diff --git a/Lib/mhlib.py b/Lib/mhlib.py
index 5520f82..899939a 100644
--- a/Lib/mhlib.py
+++ b/Lib/mhlib.py
@@ -975,8 +975,7 @@
print seqs
f.putsequences(seqs)
do('f.getsequences()')
- testfolders.reverse()
- for t in testfolders: do('mh.deletefolder(%s)' % `t`)
+ for t in reversed(testfolders): do('mh.deletefolder(%s)' % `t`)
do('mh.getcontext()')
context = mh.getcontext()
f = mh.openfolder(context)
diff --git a/Lib/platform.py b/Lib/platform.py
index 31c47b4..389e50c 100755
--- a/Lib/platform.py
+++ b/Lib/platform.py
@@ -201,7 +201,7 @@
if os.path.isdir('/usr/lib/setup'):
# Check for slackware verson tag file (thanks to Greg Andruk)
verfiles = os.listdir('/usr/lib/setup')
- for n in range(len(verfiles)-1, -1, -1):
+ for n in reversed(xrange(len(verfiles))):
if verfiles[n][:14] != 'slack-version-':
del verfiles[n]
if verfiles:
diff --git a/Lib/random.py b/Lib/random.py
index 16b667a..1f279bb 100644
--- a/Lib/random.py
+++ b/Lib/random.py
@@ -253,7 +253,7 @@
if random is None:
random = self.random
- for i in xrange(len(x)-1, 0, -1):
+ for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]
diff --git a/Lib/rfc822.py b/Lib/rfc822.py
index 4f69b22..9a52a90 100644
--- a/Lib/rfc822.py
+++ b/Lib/rfc822.py
@@ -421,8 +421,7 @@
hit = 0
if hit:
list.append(i)
- list.reverse()
- for i in list:
+ for i in reversed(list):
del self.headers[i]
def setdefault(self, name, default=""):
diff --git a/Lib/test/test_enumerate.py b/Lib/test/test_enumerate.py
index 88e24e8..b073606 100644
--- a/Lib/test/test_enumerate.py
+++ b/Lib/test/test_enumerate.py
@@ -124,9 +124,27 @@
seq = range(10,20000,2)
res = zip(range(20000), seq)
+class TestReversed(unittest.TestCase):
+
+ def test_simple(self):
+ class A:
+ def __getitem__(self, i):
+ if i < 5:
+ return str(i)
+ raise StopIteration
+ def __len__(self):
+ return 5
+ for data in 'abc', range(5), tuple(enumerate('abc')), A(), xrange(1,17,5):
+ self.assertEqual(list(data)[::-1], list(reversed(data)))
+ self.assertRaises(TypeError, reversed, {})
+
+ def test_xrange_optimization(self):
+ x = xrange(1)
+ self.assertEqual(type(reversed(x)), type(iter(x)))
def test_main(verbose=None):
- testclasses = (EnumerateTestCase, SubclassTestCase, TestEmpty, TestBig)
+ testclasses = (EnumerateTestCase, SubclassTestCase, TestEmpty, TestBig,
+ TestReversed)
test_support.run_unittest(*testclasses)
# verify reference counting
diff --git a/Misc/NEWS b/Misc/NEWS
index c47ed15..838cfc8 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -12,6 +12,9 @@
Core and builtins
-----------------
+- Added a reversed() builtin function that returns a reverse iterator
+ over a sequence.
+
- CObjects are now mutable (on the C level) through PyCObject_SetVoidPtr.
- list.sort() now supports three keyword arguments: cmp, key, and reverse.
diff --git a/Objects/enumobject.c b/Objects/enumobject.c
index 17a6282..998e381 100644
--- a/Objects/enumobject.c
+++ b/Objects/enumobject.c
@@ -155,3 +155,128 @@
enum_new, /* tp_new */
PyObject_GC_Del, /* tp_free */
};
+
+/* Reversed Object ***************************************************************/
+
+typedef struct {
+ PyObject_HEAD
+ long index;
+ PyObject* seq;
+} reversedobject;
+
+static PyObject *
+reversed_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+ long n;
+ PyObject *seq;
+ reversedobject *ro;
+
+ if (!PyArg_UnpackTuple(args, "reversed", 1, 1, &seq))
+ return NULL;
+
+ /* Special case optimization for xrange */
+ if (PyRange_Check(seq))
+ return PyObject_CallMethod(seq, "__reversed__", NULL);
+
+ if (!PySequence_Check(seq)) {
+ PyErr_SetString(PyExc_TypeError,
+ "argument to reversed() must be a sequence");
+ return NULL;
+ }
+
+ n = PySequence_Size(seq);
+ if (n == -1)
+ return NULL;
+
+ ro = (reversedobject *)type->tp_alloc(type, 0);
+ if (ro == NULL)
+ return NULL;
+
+ ro->index = n-1;
+ Py_INCREF(seq);
+ ro->seq = seq;
+ return (PyObject *)ro;
+}
+
+static void
+reversed_dealloc(reversedobject *ro)
+{
+ PyObject_GC_UnTrack(ro);
+ Py_XDECREF(ro->seq);
+ ro->ob_type->tp_free(ro);
+}
+
+static int
+reversed_traverse(reversedobject *ro, visitproc visit, void *arg)
+{
+ if (ro->seq)
+ return visit((PyObject *)(ro->seq), arg);
+ return 0;
+}
+
+static PyObject *
+reversed_next(reversedobject *ro)
+{
+ PyObject *item;
+
+ if (ro->index < 0)
+ return NULL;
+
+ assert(PySequence_Check(ro->seq));
+ item = PySequence_GetItem(ro->seq, ro->index);
+ if (item == NULL)
+ return NULL;
+
+ ro->index--;
+ return item;
+}
+
+PyDoc_STRVAR(reversed_doc,
+"reverse(sequence) -> reverse iterator over values of the sequence\n"
+"\n"
+"Return a reverse iterator");
+
+PyTypeObject PyReversed_Type = {
+ PyObject_HEAD_INIT(&PyType_Type)
+ 0, /* ob_size */
+ "reversed", /* tp_name */
+ sizeof(reversedobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)reversed_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ reversed_doc, /* tp_doc */
+ (traverseproc)reversed_traverse,/* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)reversed_next, /* tp_iternext */
+ 0, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ 0, /* tp_init */
+ PyType_GenericAlloc, /* tp_alloc */
+ reversed_new, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+};
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
index 299f4a6..1f56728 100644
--- a/Objects/rangeobject.c
+++ b/Objects/rangeobject.c
@@ -171,6 +171,15 @@
};
static PyObject * range_iter(PyObject *seq);
+static PyObject * range_reverse(PyObject *seq);
+
+PyDoc_STRVAR(reverse_doc,
+"Returns a reverse iterator.");
+
+static PyMethodDef range_methods[] = {
+ {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
+ {NULL, NULL} /* sentinel */
+};
PyTypeObject PyRange_Type = {
PyObject_HEAD_INIT(&PyType_Type)
@@ -201,7 +210,7 @@
0, /* tp_weaklistoffset */
(getiterfunc)range_iter, /* tp_iter */
0, /* tp_iternext */
- 0, /* tp_methods */
+ range_methods, /* tp_methods */
0, /* tp_members */
0, /* tp_getset */
0, /* tp_base */
@@ -246,6 +255,32 @@
}
static PyObject *
+range_reverse(PyObject *seq)
+{
+ rangeiterobject *it;
+ long start, step, len;
+
+ if (!PyRange_Check(seq)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
+ if (it == NULL)
+ return NULL;
+
+ start = ((rangeobject *)seq)->start;
+ step = ((rangeobject *)seq)->step;
+ len = ((rangeobject *)seq)->len;
+
+ it->index = 0;
+ it->start = start + (len-1) * step;
+ it->step = -step;
+ it->len = len;
+
+ return (PyObject *)it;
+}
+
+static PyObject *
rangeiter_next(rangeiterobject *r)
{
if (r->index < r->len)
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index 0309f1de..35283fc 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -2121,6 +2121,7 @@
SETBUILTIN("list", &PyList_Type);
SETBUILTIN("long", &PyLong_Type);
SETBUILTIN("object", &PyBaseObject_Type);
+ SETBUILTIN("reversed", &PyReversed_Type);
SETBUILTIN("slice", &PySlice_Type);
SETBUILTIN("staticmethod", &PyStaticMethod_Type);
SETBUILTIN("str", &PyString_Type);