diff options
| -rw-r--r-- | Doc/lib/libstdtypes.tex | 15 | ||||
| -rw-r--r-- | Lib/UserList.py | 5 | ||||
| -rw-r--r-- | Lib/test/test_sort.py | 58 | ||||
| -rw-r--r-- | Misc/NEWS | 4 | ||||
| -rw-r--r-- | Objects/listobject.c | 37 |
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, ) @@ -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 */ }; |