summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2003-10-29 06:54:43 (GMT)
committerRaymond Hettinger <python@rcn.com>2003-10-29 06:54:43 (GMT)
commit0a9b9da0c39eb74075cc93f7d7bd3b5dbcc25320 (patch)
tree9f383ec9b1ddc0e5bc09d25cd502aaac2b2432f8
parentc43a7e7c370215518ea110f4d98493935bd1c2b8 (diff)
downloadcpython-0a9b9da0c39eb74075cc93f7d7bd3b5dbcc25320.zip
cpython-0a9b9da0c39eb74075cc93f7d7bd3b5dbcc25320.tar.gz
cpython-0a9b9da0c39eb74075cc93f7d7bd3b5dbcc25320.tar.bz2
Add list.sorted() classmethod.
-rw-r--r--Doc/lib/libstdtypes.tex15
-rw-r--r--Lib/UserList.py5
-rw-r--r--Lib/test/test_sort.py58
-rw-r--r--Misc/NEWS4
-rw-r--r--Objects/listobject.c37
5 files changed, 113 insertions, 6 deletions
diff --git a/Doc/lib/libstdtypes.tex b/Doc/lib/libstdtypes.tex
index bffcea9..fec0ede 100644
--- a/Doc/lib/libstdtypes.tex
+++ b/Doc/lib/libstdtypes.tex
@@ -629,7 +629,7 @@ there is at least one character, false otherwise.
\begin{methoddesc}[string]{istitle}{}
Return true if the string is a titlecased string and there is at least one
-character, i.e. uppercase characters may only follow uncased
+character, for example uppercase characters may only follow uncased
characters and lowercase characters only cased ones. Return false
otherwise.
\end{methoddesc}
@@ -975,6 +975,9 @@ The following operations are defined on mutable sequence types (where
\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)}
+ \lineiii{\var{s}.sorted(\var{iterable}\optional{, \var{cmp}=None\optional{, \var{key}=None
+ \optional{, \var{reverse}=False}}})}
+ {return a new sorted list from the items in \var{iterable}}{(8), (9), (11)}
\end{tableiii}
\indexiv{operations on}{mutable}{sequence}{types}
\indexiii{operations on}{sequence}{types}
@@ -1024,8 +1027,8 @@ Notes:
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 optional arguments for
- controlling the comparisions.
+\item[(8)] The \method{sort()} and \method{sorted()} methods take 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
@@ -1052,7 +1055,8 @@ Notes:
\versionchanged[Support for \var{key} and \var{reverse} was added]{2.4}
\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
+ guaranteed to be stable. Starting with Python 2.4, the \method{sorted()}
+ method is also guaranteed to be stable. A sort is stable if it does not
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).
@@ -1062,6 +1066,9 @@ Notes:
of Python 2.3 makes the list appear empty for the duration, and raises
\exception{ValueError} if it can detect that the list has been
mutated during a sort.
+
+\item[(11)] \method{sorted()} is a class method that returns a new list.
+ \versionadded{2.4}
\end{description}
diff --git a/Lib/UserList.py b/Lib/UserList.py
index 072f6a7..e8fd356 100644
--- a/Lib/UserList.py
+++ b/Lib/UserList.py
@@ -78,6 +78,11 @@ class UserList:
def index(self, item, *args): return self.data.index(item, *args)
def reverse(self): self.data.reverse()
def sort(self, *args, **kwds): self.data.sort(*args, **kwds)
+ def sorted(cls, iterable, *args, **kwds):
+ s = cls(iterable)
+ s.sort(*args, **kwds)
+ return s
+ sorted = classmethod(sorted)
def extend(self, other):
if isinstance(other, UserList):
self.data.extend(other.data)
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index ca6fc801..1c10230 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -1,5 +1,7 @@
from test.test_support import verbose
import random
+from UserList import UserList
+from sets import Set
nerrors = 0
@@ -190,6 +192,7 @@ class TestDecorateSortUndecorate(unittest.TestCase):
random.shuffle(data)
data.sort(reverse=True)
self.assertEqual(data, range(99,-1,-1))
+ self.assertRaises(TypeError, data.sort, "wrong type")
def test_reverse_stability(self):
data = [(random.randrange(100), i) for i in xrange(200)]
@@ -201,11 +204,66 @@ class TestDecorateSortUndecorate(unittest.TestCase):
copy2.sort(key=lambda x: x[0], reverse=True)
self.assertEqual(data, copy2)
+class TestSorted(unittest.TestCase):
+
+ def test_basic(self):
+ data = range(100)
+ copy = data[:]
+ random.shuffle(copy)
+ self.assertEqual(data, list.sorted(copy))
+ self.assertNotEqual(data, copy)
+
+ data.reverse()
+ random.shuffle(copy)
+ self.assertEqual(data, list.sorted(copy, cmp=lambda x, y: cmp(y,x)))
+ self.assertNotEqual(data, copy)
+ random.shuffle(copy)
+ self.assertEqual(data, list.sorted(copy, key=lambda x: -x))
+ self.assertNotEqual(data, copy)
+ random.shuffle(copy)
+ self.assertEqual(data, list.sorted(copy, reverse=1))
+ self.assertNotEqual(data, copy)
+
+ def test_inputtypes(self):
+ s = 'abracadabra'
+ for T in [unicode, list, tuple]:
+ self.assertEqual(list.sorted(s), list.sorted(T(s)))
+
+ s = ''.join(dict.fromkeys(s).keys()) # unique letters only
+ for T in [unicode, Set, list, tuple, dict.fromkeys]:
+ self.assertEqual(list.sorted(s), list.sorted(T(s)))
+
+ def test_baddecorator(self):
+ data = 'The quick Brown fox Jumped over The lazy Dog'.split()
+ self.assertRaises(TypeError, list.sorted, data, None, lambda x,y: 0)
+
+ def classmethods(self):
+ s = "hello world"
+ a = list.sorted(s)
+ b = UserList.sorted(s)
+ c = [].sorted(s)
+ d = UserList().sorted(s)
+ class Mylist(list):
+ def __new__(cls):
+ return UserList()
+ e = MyList.sorted(s)
+ f = MyList().sorted(s)
+ class Myuserlist(UserList):
+ def __new__(cls):
+ return []
+ g = MyList.sorted(s)
+ h = MyList().sorted(s)
+ self.assert_(a == b == c == d == e == f == g == h)
+ self.assert_(b.__class__ == d.__class__ == UserList)
+ self.assert_(e.__class__ == f.__class__ == MyList)
+ self.assert_(g.__class__ == h.__class__ == Myuserlist)
+
#==============================================================================
def test_main(verbose=None):
test_classes = (
TestDecorateSortUndecorate,
+ TestSorted,
TestBugs,
)
diff --git a/Misc/NEWS b/Misc/NEWS
index a3c5fe5..4bbbb57 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -23,8 +23,8 @@ Core and builtins
starting with Py2.3 are guaranteed to be stable (the relative order of
records with equal keys is unchanged).
-- Added a list.copysort() method that returns a copy of the sorted list
- while leaving the original intact.
+- Added a list.sorted() classmethod that returns a new sorted list
+ from any iterable.
- 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
diff --git a/Objects/listobject.c b/Objects/listobject.c
index b53b948..23d7d9a 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -2001,6 +2001,38 @@ PyList_Sort(PyObject *v)
}
static PyObject *
+listsorted(PyObject *cls, PyObject *args, PyObject *kwds)
+{
+ PyObject *newlist, *v, *seq, *compare=NULL, *keyfunc=NULL, *newargs;
+ static char *kwlist[] = {"iterable", "cmp", "key", "reverse", 0};
+ long reverse;
+
+ if (args != NULL) {
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|OOi:sorted",
+ kwlist, &seq, &compare, &keyfunc, &reverse))
+ return NULL;
+ }
+
+ newlist = PyObject_CallFunctionObjArgs(cls, seq, NULL);
+ if (newlist == NULL)
+ return NULL;
+
+ newargs = PyTuple_GetSlice(args, 1, 4);
+ if (newargs == NULL) {
+ Py_DECREF(newlist);
+ return NULL;
+ }
+ v = listsort((PyListObject *)newlist, newargs, kwds);
+ Py_DECREF(newargs);
+ if (v == NULL) {
+ Py_DECREF(newlist);
+ return NULL;
+ }
+ Py_DECREF(v);
+ return newlist;
+}
+
+static PyObject *
listreverse(PyListObject *self)
{
if (self->ob_size > 1)
@@ -2335,6 +2367,9 @@ PyDoc_STRVAR(reverse_doc,
PyDoc_STRVAR(sort_doc,
"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
cmp(x, y) -> -1, 0, 1");
+PyDoc_STRVAR(sorted_doc,
+"list.sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list;\n\
+cmp(x, y) -> -1, 0, 1");
static PyMethodDef list_methods[] = {
{"append", (PyCFunction)listappend, METH_O, append_doc},
@@ -2346,6 +2381,8 @@ static PyMethodDef list_methods[] = {
{"count", (PyCFunction)listcount, METH_O, count_doc},
{"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
{"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
+ {"sorted", (PyCFunction)listsorted,
+ METH_VARARGS | METH_KEYWORDS | METH_CLASS, sorted_doc},
{NULL, NULL} /* sentinel */
};