* list.sort() now supports three keyword arguments: cmp, key, and reverse.
key provides C support for the decorate-sort-undecorate pattern.
reverse provide a stable sort of the list with the comparisions reversed.
* Amended the docs to guarantee sort stability.
diff --git a/Doc/lib/libstdtypes.tex b/Doc/lib/libstdtypes.tex
index c3a0305..62f1644 100644
--- a/Doc/lib/libstdtypes.tex
+++ b/Doc/lib/libstdtypes.tex
@@ -970,7 +970,8 @@
{same as \code{del \var{s}[\var{s}.index(\var{x})]}}{(4)}
\lineiii{\var{s}.reverse()}
{reverses the items of \var{s} in place}{(7)}
- \lineiii{\var{s}.sort(\optional{\var{cmpfunc=None}})}
+ \lineiii{\var{s}.sort(\optional{\var{cmp}=None\optional{, \var{key}=None
+ \optional{, \var{reverse}=False}}})}
{sort the items of \var{s} in place}{(7), (8), (9), (10)}
\end{tableiii}
\indexiv{operations on}{mutable}{sequence}{types}
@@ -1021,47 +1022,38 @@
list. To remind you that they operate by side effect, they don't return
the sorted or reversed list.
-\item[(8)] The \method{sort()} method takes an optional argument
- specifying a comparison function of two arguments (list items) which
- should return a negative, zero or positive number depending on whether
- the first argument is considered smaller than, equal to, or larger
- than the second argument. Note that this slows the sorting process
- down considerably; for example to sort a list in reverse order it is much
- faster to call \method{sort()} followed by \method{reverse()}
- than to use \method{sort()} with a comparison function that
- reverses the ordering of the elements. Passing \constant{None} as the
- comparison function is semantically equivalent to calling
- \method{sort()} with no comparison function.
+\item[(8)] The \method{sort()} method takes optional arguments for
+ controlling the comparisions.
+
+ \var{cmp} specifies a custom comparison function of two arguments
+ (list items) which should return a negative, zero or positive number
+ depending on whether the first argument is considered smaller than,
+ equal to, or larger than the second argument:
+ \samp{\var{cmp}=\keyword{lambda} \var{x},\var{y}:
+ \function{cmp}(x.lower(), y.lower())}
+
+ \var{key} specifies a function of one argument that is used to
+ extract a comparison key from each list element:
+ \samp{\var{cmp}=\function{str.lower}}
+
+ \var{reverse} is a boolean value. If set to \code{True}, then the
+ list elements are sorted as if each comparison were reversed.
+
+ In general, the \var{key} and \var{reverse} conversion processes are
+ much faster than specifying an equivalent \var{cmp} function. This is
+ because \var{cmp} is called multiple times for each list element while
+ \var{key} and \{reverse} touch each element only once.
+
\versionchanged[Support for \code{None} as an equivalent to omitting
\var{cmpfunc} was added]{2.3}
- As an example of using the \var{cmpfunc} argument to the
- \method{sort()} method, consider sorting a list of sequences by the
- second element of that list:
+ \versionadded[Support for \var{key} and \var{reverse} was added]{2.4}
-\begin{verbatim}
-def mycmp(a, b):
- return cmp(a[1], b[1])
-
-mylist.sort(mycmp)
-\end{verbatim}
-
- A more time-efficient approach for reasonably-sized data structures can
- often be used:
-
-\begin{verbatim}
-tmplist = [(x[1], x) for x in mylist]
-tmplist.sort()
-mylist = [x for (key, x) in tmplist]
-\end{verbatim}
-
-\item[(9)] Whether the \method{sort()} method is stable is not defined by
- the language (a sort is stable if it guarantees not to change the
- relative order of elements that compare equal). In the C
- implementation of Python, sorts were stable only by accident through
- Python 2.2. The C implementation of Python 2.3 introduced a stable
- \method{sort()} method, but code that intends to be portable across
- implementations and versions must not rely on stability.
+\item[(9)] Starting with Python 2.3, the \method{sort()} method is
+ guaranteed to be stable. A sort is stable if it guarantees not to
+ change the relative order of elements that compare equal --- this is
+ helpful for sorting in multiple passes (for example, sort by
+ department, then by salary grade).
\item[(10)] While a list is being sorted, the effect of attempting to
mutate, or even inspect, the list is undefined. The C implementation
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index 6c35f42..ca6fc80 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -116,56 +116,112 @@
x = [e for e, i in augmented] # a stable sort of s
check("stability", x, s)
-def bug453523():
- global nerrors
- from random import random
- # If this fails, the most likely outcome is a core dump.
- if verbose:
- print "Testing bug 453523 -- list.sort() crasher."
+import unittest
+from test import test_support
+import sys
- class C:
- def __lt__(self, other):
- if L and random() < 0.75:
- pop()
- else:
- push(3)
- return random() < 0.5
+#==============================================================================
- L = [C() for i in range(50)]
- pop = L.pop
- push = L.append
- try:
- L.sort()
- except ValueError:
- pass
- else:
- print " Mutation during list.sort() wasn't caught."
- nerrors += 1
+class TestBugs(unittest.TestCase):
-bug453523()
+ def test_bug453523(self):
+ # bug 453523 -- list.sort() crasher.
+ # If this fails, the most likely outcome is a core dump.
+ # Mutations during a list sort should raise a ValueError.
-def cmpNone():
- global nerrors
+ class C:
+ def __lt__(self, other):
+ if L and random.random() < 0.75:
+ L.pop()
+ else:
+ L.append(3)
+ return random.random() < 0.5
- if verbose:
- print "Testing None as a comparison function."
+ L = [C() for i in range(50)]
+ self.assertRaises(ValueError, L.sort)
- L = range(50)
- random.shuffle(L)
- try:
+ def test_cmpNone(self):
+ # Testing None as a comparison function.
+
+ L = range(50)
+ random.shuffle(L)
L.sort(None)
- except TypeError:
- print " Passing None as cmpfunc failed."
- nerrors += 1
- else:
- if L != range(50):
- print " Passing None as cmpfunc failed."
- nerrors += 1
+ self.assertEqual(L, range(50))
-cmpNone()
+#==============================================================================
-if nerrors:
- print "Test failed", nerrors
-elif verbose:
- print "Test passed -- no errors."
+class TestDecorateSortUndecorate(unittest.TestCase):
+
+ def test_decorated(self):
+ data = 'The quick Brown fox Jumped over The lazy Dog'.split()
+ copy = data[:]
+ random.shuffle(data)
+ data.sort(key=str.lower)
+ copy.sort(cmp=lambda x,y: cmp(x.lower(), y.lower()))
+
+ def test_baddecorator(self):
+ data = 'The quick Brown fox Jumped over The lazy Dog'.split()
+ self.assertRaises(TypeError, data.sort, None, lambda x,y: 0)
+
+ def test_stability(self):
+ data = [(random.randrange(100), i) for i in xrange(200)]
+ copy = data[:]
+ data.sort(key=lambda (x,y): x) # sort on the random first field
+ copy.sort() # sort using both fields
+ self.assertEqual(data, copy) # should get the same result
+
+ def test_cmp_and_key_combination(self):
+ # Verify that the wrapper has been removed
+ def compare(x, y):
+ self.assertEqual(type(x), str)
+ self.assertEqual(type(x), str)
+ return cmp(x, y)
+ data = 'The quick Brown fox Jumped over The lazy Dog'.split()
+ data.sort(cmp=compare, key=str.lower)
+
+ def test_badcmp_with_key(self):
+ # Verify that the wrapper has been removed
+ data = 'The quick Brown fox Jumped over The lazy Dog'.split()
+ self.assertRaises(TypeError, data.sort, "bad", str.lower)
+
+ def test_reverse(self):
+ data = range(100)
+ random.shuffle(data)
+ data.sort(reverse=True)
+ self.assertEqual(data, range(99,-1,-1))
+
+ def test_reverse_stability(self):
+ data = [(random.randrange(100), i) for i in xrange(200)]
+ copy1 = data[:]
+ copy2 = data[:]
+ data.sort(cmp=lambda x,y: cmp(x[0],y[0]), reverse=True)
+ copy1.sort(cmp=lambda x,y: cmp(y[0],x[0]))
+ self.assertEqual(data, copy1)
+ copy2.sort(key=lambda x: x[0], reverse=True)
+ self.assertEqual(data, copy2)
+
+#==============================================================================
+
+def test_main(verbose=None):
+ test_classes = (
+ TestDecorateSortUndecorate,
+ TestBugs,
+ )
+
+ test_support.run_unittest(*test_classes)
+
+ # verify reference counting
+ if verbose and hasattr(sys, "gettotalrefcount"):
+ import gc
+ counts = [None] * 5
+ for i in xrange(len(counts)):
+ test_support.run_unittest(*test_classes)
+ gc.collect()
+ counts[i] = sys.gettotalrefcount()
+ print counts
+
+if __name__ == "__main__":
+ test_main(verbose=True)
+
+
diff --git a/Misc/NEWS b/Misc/NEWS
index eb57e68..02f541f 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -12,6 +12,15 @@
Core and builtins
-----------------
+- list.sort() now supports three keyword arguments: cmp, key, and reverse.
+ The key argument can be a function of one argument that extracts a
+ comparison key from the original record: mylist.sort(key=str.lower).
+ The reverse argument is a boolean value and if True will change the
+ sort order as if the comparison arguments were reversed. In addition,
+ the documentation has been amended to provide a guarantee that all sorts
+ starting with Py2.3 are guaranteed to be stable (the relative order of
+ records with equal keys is unchanged).
+
- Added test whether wchar_t is signed or not. A signed wchar_t is not
usable as internal unicode type base for Py_UNICODE since the
unicode implementation assumes an unsigned type.
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 727c9e6..2edbedf 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -1656,13 +1656,186 @@
return n + r;
}
+/* Special wrapper to support stable sorting using the decorate-sort-undecorate
+ pattern. Holds a key which is used for comparisions and the original record
+ which is returned during the undecorate phase. By exposing only the key
+ during comparisons, the underlying sort stability characteristics are left
+ unchanged. Also, if a custom comparison function is used, it will only see
+ the key instead of a full record. */
+
+typedef struct {
+ PyObject_HEAD
+ PyObject *key;
+ PyObject *value;
+} sortwrapperobject;
+
+static PyTypeObject sortwrapper_type;
+
+static PyObject *
+sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
+{
+ if (!PyObject_TypeCheck(b, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
+ }
+ return PyObject_RichCompare(a->key, b->key, op);
+}
+
+static void
+sortwrapper_dealloc(sortwrapperobject *so)
+{
+ Py_XDECREF(so->key);
+ Py_XDECREF(so->value);
+ PyObject_Del(so);
+}
+
+PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");
+
+static PyTypeObject sortwrapper_type = {
+ PyObject_HEAD_INIT(&PyType_Type)
+ 0, /* ob_size */
+ "sortwrapper", /* tp_name */
+ sizeof(sortwrapperobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)sortwrapper_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_RICHCOMPARE, /* tp_flags */
+ sortwrapper_doc, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */
+};
+
+/* Returns a new reference to a sortwrapper.
+ Consumes the references to the two underlying objects. */
+
+static PyObject *
+build_sortwrapper(PyObject *key, PyObject *value)
+{
+ sortwrapperobject *so;
+
+ so = PyObject_New(sortwrapperobject, &sortwrapper_type);
+ if (so == NULL)
+ return NULL;
+ so->key = key;
+ so->value = value;
+ return (PyObject *)so;
+}
+
+/* Returns a new reference to the value underlying the wrapper. */
+static PyObject *
+sortwrapper_getvalue(PyObject *so)
+{
+ PyObject *value;
+
+ if (!PyObject_TypeCheck(so, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
+ }
+ value = ((sortwrapperobject *)so)->value;
+ Py_INCREF(value);
+ return value;
+}
+
+/* Wrapper for user specified cmp functions in combination with a
+ specified key function. Makes sure the cmp function is presented
+ with the actual key instead of the sortwrapper */
+
+typedef struct {
+ PyObject_HEAD
+ PyObject *func;
+} cmpwrapperobject;
+
+static void
+cmpwrapper_dealloc(cmpwrapperobject *co)
+{
+ Py_XDECREF(co->func);
+ PyObject_Del(co);
+}
+
+static PyObject *
+cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)
+{
+ PyObject *x, *y, *xx, *yy;
+
+ if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))
+ return NULL;
+ if (!PyObject_TypeCheck(x, &sortwrapper_type) ||
+ !PyObject_TypeCheck(x, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
+ }
+ xx = ((sortwrapperobject *)x)->key;
+ yy = ((sortwrapperobject *)y)->key;
+ return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);
+}
+
+PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");
+
+static PyTypeObject cmpwrapper_type = {
+ PyObject_HEAD_INIT(&PyType_Type)
+ 0, /* ob_size */
+ "cmpwrapper", /* tp_name */
+ sizeof(cmpwrapperobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)cmpwrapper_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 */
+ (ternaryfunc)cmpwrapper_call, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ cmpwrapper_doc, /* tp_doc */
+};
+
+static PyObject *
+build_cmpwrapper(PyObject *cmpfunc)
+{
+ cmpwrapperobject *co;
+
+ co = PyObject_New(cmpwrapperobject, &cmpwrapper_type);
+ if (co == NULL)
+ return NULL;
+ Py_INCREF(cmpfunc);
+ co->func = cmpfunc;
+ return (PyObject *)co;
+}
+
/* An adaptive, stable, natural mergesort. See listsort.txt.
* Returns Py_None on success, NULL on error. Even in case of error, the
* list will be some permutation of its input state (nothing is lost or
* duplicated).
*/
static PyObject *
-listsort(PyListObject *self, PyObject *args)
+listsort(PyListObject *self, PyObject *args, PyObject *kwds)
{
MergeState ms;
PyObject **lo, **hi;
@@ -1673,14 +1846,48 @@
PyObject **empty_ob_item;
PyObject *compare = NULL;
PyObject *result = NULL; /* guilty until proved innocent */
+ int reverse = 0;
+ PyObject *keyfunc = NULL;
+ int i, n;
+ PyObject *key, *value, *kvpair;
+ static char *kwlist[] = {"cmp", "key", "reverse", 0};
assert(self != NULL);
+ assert (PyList_Check(self));
if (args != NULL) {
- if (!PyArg_UnpackTuple(args, "sort", 0, 1, &compare))
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",
+ kwlist, &compare, &keyfunc, &reverse))
return NULL;
}
if (compare == Py_None)
compare = NULL;
+ if (keyfunc == Py_None)
+ keyfunc = NULL;
+ if (compare != NULL && keyfunc != NULL) {
+ compare = build_cmpwrapper(compare);
+ if (compare == NULL)
+ goto dsu_fail;
+ } else
+ Py_XINCREF(compare);
+
+ if (keyfunc != NULL) {
+ n = PyList_GET_SIZE(self);
+ for (i=0 ; i<n ; i++) {
+ value = PyList_GET_ITEM(self, i);
+ key = PyObject_CallFunctionObjArgs(keyfunc, value, NULL);
+ if (key == NULL)
+ goto dsu_fail;
+ kvpair = build_sortwrapper(key, value);
+ if (kvpair == NULL)
+ goto dsu_fail;
+ PyList_SET_ITEM(self, i, kvpair);
+ }
+ }
+
+ /* Reverse sort stability achieved by initialially reversing the list,
+ applying a stable forward sort, then reversing the final result. */
+ if (reverse && self->ob_size > 1)
+ reverse_slice(self->ob_item, self->ob_item + self->ob_size);
merge_init(&ms, compare);
@@ -1758,6 +1965,21 @@
self->ob_size = saved_ob_size;
self->ob_item = saved_ob_item;
merge_freemem(&ms);
+
+ if (keyfunc != NULL) {
+ for (i=0 ; i<n ; i++) {
+ kvpair = PyList_GET_ITEM(self, i);
+ value = sortwrapper_getvalue(kvpair);
+ PyList_SET_ITEM(self, i, value);
+ Py_DECREF(kvpair);
+ }
+ }
+
+ if (reverse && self->ob_size > 1)
+ reverse_slice(self->ob_item, self->ob_item + self->ob_size);
+
+dsu_fail:
+ Py_XDECREF(compare);
Py_XINCREF(result);
return result;
}
@@ -1771,7 +1993,7 @@
PyErr_BadInternalCall();
return -1;
}
- v = listsort((PyListObject *)v, (PyObject *)NULL);
+ v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
if (v == NULL)
return -1;
Py_DECREF(v);
@@ -2111,7 +2333,8 @@
PyDoc_STRVAR(reverse_doc,
"L.reverse() -- reverse *IN PLACE*");
PyDoc_STRVAR(sort_doc,
-"L.sort(cmpfunc=None) -- stable sort *IN PLACE*; cmpfunc(x, y) -> -1, 0, 1");
+"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
+cmp(x, y) -> -1, 0, 1");
static PyMethodDef list_methods[] = {
{"append", (PyCFunction)listappend, METH_O, append_doc},
@@ -2122,7 +2345,7 @@
{"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
{"count", (PyCFunction)listcount, METH_O, count_doc},
{"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
- {"sort", (PyCFunction)listsort, METH_VARARGS, sort_doc},
+ {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
{NULL, NULL} /* sentinel */
};