Skip to content

Commit 85c20a4

Browse files
rhettingerrhettinger
committed
Implement and apply PEP 322, reverse iteration
1 parent f607fc5 commit 85c20a4

File tree

12 files changed

+198
-9
lines changed

12 files changed

+198
-9
lines changed

‎Doc/lib/libfuncs.tex‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -880,6 +880,14 @@ \section{Built-in Functions \label{built-in-funcs}}
880880
when passed to \function{eval()}.
881881
\end{funcdesc}
882882

883+
\begin{funcdesc}{reversed}{seq}
884+
Return a reverse iterator. \var{seq} must be an object which
885+
supports the sequence protocol (the __len__() method and the
886+
\method{__getitem__()} method with integer arguments starting at
887+
\code{0}).
888+
\versionadded{2.4}
889+
\end{funcdesc}
890+
883891
\begin{funcdesc}{round}{x\optional{, n}}
884892
Return the floating point value \var{x} rounded to \var{n} digits
885893
after the decimal point. If \var{n} is omitted, it defaults to zero.

‎Include/enumobject.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ extern "C" {
88
#endif
99

1010
PyAPI_DATA(PyTypeObject) PyEnum_Type;
11+
PyAPI_DATA(PyTypeObject) PyReversed_Type;
1112

1213
#ifdef __cplusplus
1314
}

‎Lib/heapq.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -165,7 +165,7 @@ def heapify(x):
165165
# or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
166166
# j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is
167167
# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
168-
for i in xrange(n//2 - 1, -1, -1):
168+
for i in reversed(xrange(n//2)):
169169
_siftup(x, i)
170170

171171
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos

‎Lib/mhlib.py‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -975,8 +975,7 @@ def do(s): print s; print eval(s)
975975
print seqs
976976
f.putsequences(seqs)
977977
do('f.getsequences()')
978-
testfolders.reverse()
979-
for t in testfolders: do('mh.deletefolder(%s)' % `t`)
978+
for t in reversed(testfolders): do('mh.deletefolder(%s)' % `t`)
980979
do('mh.getcontext()')
981980
context = mh.getcontext()
982981
f = mh.openfolder(context)

‎Lib/platform.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -201,7 +201,7 @@ def _dist_try_harder(distname,version,id):
201201
if os.path.isdir('/usr/lib/setup'):
202202
# Check for slackware verson tag file (thanks to Greg Andruk)
203203
verfiles = os.listdir('/usr/lib/setup')
204-
for n in range(len(verfiles)-1, -1, -1):
204+
for n in reversed(xrange(len(verfiles))):
205205
if verfiles[n][:14] != 'slack-version-':
206206
del verfiles[n]
207207
if verfiles:

‎Lib/random.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -253,7 +253,7 @@ def shuffle(self, x, random=None, int=int):
253253

254254
if random is None:
255255
random = self.random
256-
for i in xrange(len(x)-1, 0, -1):
256+
for i in reversed(xrange(1, len(x))):
257257
# pick an element in x[:i+1] with which to exchange x[i]
258258
j = int(random() * (i+1))
259259
x[i], x[j] = x[j], x[i]

‎Lib/rfc822.py‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -421,8 +421,7 @@ def __delitem__(self, name):
421421
hit = 0
422422
if hit:
423423
list.append(i)
424-
list.reverse()
425-
for i in list:
424+
for i in reversed(list):
426425
del self.headers[i]
427426

428427
def setdefault(self, name, default=""):

‎Lib/test/test_enumerate.py‎

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -124,9 +124,27 @@ class TestBig(EnumerateTestCase):
124124
seq = range(10,20000,2)
125125
res = zip(range(20000), seq)
126126

127+
class TestReversed(unittest.TestCase):
128+
129+
def test_simple(self):
130+
class A:
131+
def __getitem__(self, i):
132+
if i < 5:
133+
return str(i)
134+
raise StopIteration
135+
def __len__(self):
136+
return 5
137+
for data in 'abc', range(5), tuple(enumerate('abc')), A(), xrange(1,17,5):
138+
self.assertEqual(list(data)[::-1], list(reversed(data)))
139+
self.assertRaises(TypeError, reversed, {})
140+
141+
def test_xrange_optimization(self):
142+
x = xrange(1)
143+
self.assertEqual(type(reversed(x)), type(iter(x)))
127144

128145
def test_main(verbose=None):
129-
testclasses = (EnumerateTestCase, SubclassTestCase, TestEmpty, TestBig)
146+
testclasses = (EnumerateTestCase, SubclassTestCase, TestEmpty, TestBig,
147+
TestReversed)
130148
test_support.run_unittest(*testclasses)
131149

132150
# verify reference counting

‎Misc/NEWS‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,9 @@ What's New in Python 2.4 alpha 1?
1212
Core and builtins
1313
-----------------
1414

15+
- Added a reversed() builtin function that returns a reverse iterator
16+
over a sequence.
17+
1518
- CObjects are now mutable (on the C level) through PyCObject_SetVoidPtr.
1619

1720
- list.sort() now supports three keyword arguments: cmp, key, and reverse.

‎Objects/enumobject.c‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -155,3 +155,128 @@ PyTypeObject PyEnum_Type = {
155155
enum_new, /* tp_new */
156156
PyObject_GC_Del, /* tp_free */
157157
};
158+
159+
/* Reversed Object ***************************************************************/
160+
161+
typedef struct {
162+
PyObject_HEAD
163+
long index;
164+
PyObject* seq;
165+
} reversedobject;
166+
167+
static PyObject *
168+
reversed_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
169+
{
170+
long n;
171+
PyObject *seq;
172+
reversedobject *ro;
173+
174+
if (!PyArg_UnpackTuple(args, "reversed", 1, 1, &seq))
175+
return NULL;
176+
177+
/* Special case optimization for xrange */
178+
if (PyRange_Check(seq))
179+
return PyObject_CallMethod(seq, "__reversed__", NULL);
180+
181+
if (!PySequence_Check(seq)) {
182+
PyErr_SetString(PyExc_TypeError,
183+
"argument to reversed() must be a sequence");
184+
return NULL;
185+
}
186+
187+
n = PySequence_Size(seq);
188+
if (n == -1)
189+
return NULL;
190+
191+
ro = (reversedobject *)type->tp_alloc(type, 0);
192+
if (ro == NULL)
193+
return NULL;
194+
195+
ro->index = n-1;
196+
Py_INCREF(seq);
197+
ro->seq = seq;
198+
return (PyObject *)ro;
199+
}
200+
201+
static void
202+
reversed_dealloc(reversedobject *ro)
203+
{
204+
PyObject_GC_UnTrack(ro);
205+
Py_XDECREF(ro->seq);
206+
ro->ob_type->tp_free(ro);
207+
}
208+
209+
static int
210+
reversed_traverse(reversedobject *ro, visitproc visit, void *arg)
211+
{
212+
if (ro->seq)
213+
return visit((PyObject *)(ro->seq), arg);
214+
return 0;
215+
}
216+
217+
static PyObject *
218+
reversed_next(reversedobject *ro)
219+
{
220+
PyObject *item;
221+
222+
if (ro->index < 0)
223+
return NULL;
224+
225+
assert(PySequence_Check(ro->seq));
226+
item = PySequence_GetItem(ro->seq, ro->index);
227+
if (item == NULL)
228+
return NULL;
229+
230+
ro->index--;
231+
return item;
232+
}
233+
234+
PyDoc_STRVAR(reversed_doc,
235+
"reverse(sequence) -> reverse iterator over values of the sequence\n"
236+
"\n"
237+
"Return a reverse iterator");
238+
239+
PyTypeObject PyReversed_Type = {
240+
PyObject_HEAD_INIT(&PyType_Type)
241+
0, /* ob_size */
242+
"reversed", /* tp_name */
243+
sizeof(reversedobject), /* tp_basicsize */
244+
0, /* tp_itemsize */
245+
/* methods */
246+
(destructor)reversed_dealloc, /* tp_dealloc */
247+
0, /* tp_print */
248+
0, /* tp_getattr */
249+
0, /* tp_setattr */
250+
0, /* tp_compare */
251+
0, /* tp_repr */
252+
0, /* tp_as_number */
253+
0, /* tp_as_sequence */
254+
0, /* tp_as_mapping */
255+
0, /* tp_hash */
256+
0, /* tp_call */
257+
0, /* tp_str */
258+
PyObject_GenericGetAttr, /* tp_getattro */
259+
0, /* tp_setattro */
260+
0, /* tp_as_buffer */
261+
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
262+
Py_TPFLAGS_BASETYPE, /* tp_flags */
263+
reversed_doc, /* tp_doc */
264+
(traverseproc)reversed_traverse,/* tp_traverse */
265+
0, /* tp_clear */
266+
0, /* tp_richcompare */
267+
0, /* tp_weaklistoffset */
268+
PyObject_SelfIter, /* tp_iter */
269+
(iternextfunc)reversed_next, /* tp_iternext */
270+
0, /* tp_methods */
271+
0, /* tp_members */
272+
0, /* tp_getset */
273+
0, /* tp_base */
274+
0, /* tp_dict */
275+
0, /* tp_descr_get */
276+
0, /* tp_descr_set */
277+
0, /* tp_dictoffset */
278+
0, /* tp_init */
279+
PyType_GenericAlloc, /* tp_alloc */
280+
reversed_new, /* tp_new */
281+
PyObject_GC_Del, /* tp_free */
282+
};

0 commit comments

Comments
 (0)