diff options
| -rw-r--r-- | Doc/lib/libfuncs.tex | 9 | ||||
| -rw-r--r-- | Doc/lib/libitertools.tex | 2 | ||||
| -rw-r--r-- | Doc/lib/libstdtypes.tex | 13 | ||||
| -rw-r--r-- | Doc/whatsnew/whatsnew24.tex | 22 | ||||
| -rw-r--r-- | Lib/UserList.py | 5 | ||||
| -rw-r--r-- | Lib/pyclbr.py | 2 | ||||
| -rw-r--r-- | Lib/test/test_builtin.py | 37 | ||||
| -rw-r--r-- | Lib/test/test_descrtut.py | 3 | ||||
| -rw-r--r-- | Lib/test/test_itertools.py | 10 | ||||
| -rw-r--r-- | Lib/test/test_operator.py | 2 | ||||
| -rw-r--r-- | Lib/test/test_set.py | 10 | ||||
| -rw-r--r-- | Lib/test/test_sort.py | 55 | ||||
| -rw-r--r-- | Misc/NEWS | 6 | ||||
| -rw-r--r-- | Objects/listobject.c | 37 | ||||
| -rw-r--r-- | Python/bltinmodule.c | 45 |
15 files changed, 120 insertions, 138 deletions
diff --git a/Doc/lib/libfuncs.tex b/Doc/lib/libfuncs.tex index dc9f344..99c586b 100644 --- a/Doc/lib/libfuncs.tex +++ b/Doc/lib/libfuncs.tex @@ -886,6 +886,15 @@ class C(object): \samp{a[start:stop, i]}. \end{funcdesc} +\begin{funcdesc}{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}. + The optional arguments \var{cmp}, \var{key}, and \var{reverse} + have the same meaning as those for the \method{list.sort()} method. + \versionadded{2.4} +\end{funcdesc} + \begin{funcdesc}{staticmethod}{function} Return a static method for \var{function}. diff --git a/Doc/lib/libitertools.tex b/Doc/lib/libitertools.tex index 59fb185..a85e048 100644 --- a/Doc/lib/libitertools.tex +++ b/Doc/lib/libitertools.tex @@ -398,7 +398,7 @@ Samuele # Show a dictionary sorted and grouped by value >>> from operator import itemgetter >>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3) ->>> di = list.sorted(d.iteritems(), key=itemgetter(1)) +>>> di = sorted(d.iteritems(), key=itemgetter(1)) >>> for k, g in groupby(di, key=itemgetter(1)): ... print k, map(itemgetter(0), g) ... diff --git a/Doc/lib/libstdtypes.tex b/Doc/lib/libstdtypes.tex index 8b6b194..6e38222 100644 --- a/Doc/lib/libstdtypes.tex +++ b/Doc/lib/libstdtypes.tex @@ -988,9 +988,6 @@ 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} @@ -1040,8 +1037,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()} and \method{sorted()} methods take optional - arguments for controlling the comparisons. +\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 @@ -1068,8 +1065,7 @@ 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. Starting with Python 2.4, the \method{sorted()} - method is also guaranteed to be stable. A sort is stable if it does not + 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). @@ -1079,9 +1075,6 @@ 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} \subsection{Set Types \label{types-set}} diff --git a/Doc/whatsnew/whatsnew24.tex b/Doc/whatsnew/whatsnew24.tex index 9e699a3..a881393 100644 --- a/Doc/whatsnew/whatsnew24.tex +++ b/Doc/whatsnew/whatsnew24.tex @@ -177,9 +177,9 @@ they were input. For example, you can sort a list of people by name, and then sort the list by age, resulting in a list sorted by age where people with the same age are in name-sorted order. -\item The list type gained a \method{sorted(iterable)} method that works -like the in-place \method{sort()} method but has been made suitable for -use in expressions. The differences are: +\item There is a new builtin function \function{sorted(iterable)} that works +like the in-place \method{list.sort()} method but has been made suitable +for use in expressions. The differences are: \begin{itemize} \item the input may be any iterable; \item a newly formed copy is sorted, leaving the original intact; and @@ -188,17 +188,17 @@ use in expressions. The differences are: \begin{verbatim} >>> L = [9,7,8,3,2,4,1,6,5] ->>> [10+i for i in list.sorted(L)] # usable in a list comprehension +>>> [10+i for i in sorted(L)] # usable in a list comprehension [11, 12, 13, 14, 15, 16, 17, 18, 19] >>> L = [9,7,8,3,2,4,1,6,5] # original is left unchanged [9,7,8,3,2,4,1,6,5] ->>> list.sorted('Monte Python') # any iterable may be an input +>>> sorted('Monte Python') # any iterable may be an input [' ', 'M', 'P', 'e', 'h', 'n', 'n', 'o', 'o', 't', 't', 'y'] >>> # List the contents of a dict sorted by key values >>> colormap = dict(red=1, blue=2, green=3, black=4, yellow=5) ->>> for k, v in list.sorted(colormap.iteritems()): +>>> for k, v in sorted(colormap.iteritems()): ... print k, v ... black 4 @@ -301,14 +301,14 @@ counting, or identifying duplicate elements: \begin{verbatim} >>> word = 'abracadabra' ->>> word = list.sorted(word) # Turn string into sorted list of letters ->>> word +>>> letters = sorted(word) # Turn string into sorted list of letters +>>> letters ['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r'] ->>> [k for k, g in groupby(word)] # List the various group keys +>>> [k for k, g in groupby(word)] # List unique letters ['a', 'b', 'c', 'd', 'r'] ->>> [(k, len(list(g))) for k, g in groupby(word)] # List key and group length +>>> [(k, len(list(g))) for k, g in groupby(word)] # Count letter occurences [('a', 5), ('b', 2), ('c', 1), ('d', 1), ('r', 2)] ->>> [k for k, g in groupby(word) if len(list(g)) > 1] # All groups of size >1 +>>> [k for k, g in groupby(word) if len(list(g)) > 1] # List duplicate letters ['a', 'b', 'r'] \end{verbatim} diff --git a/Lib/UserList.py b/Lib/UserList.py index e8fd356..072f6a7 100644 --- a/Lib/UserList.py +++ b/Lib/UserList.py @@ -78,11 +78,6 @@ 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/pyclbr.py b/Lib/pyclbr.py index 6674b71..9e6bcb0 100644 --- a/Lib/pyclbr.py +++ b/Lib/pyclbr.py @@ -327,7 +327,7 @@ def _main(): for obj in objs: if isinstance(obj, Class): print "class", obj.name, obj.super, obj.lineno - methods = list.sorted(obj.methods.iteritems(), key=itemgetter(1)) + methods = sorted(obj.methods.iteritems(), key=itemgetter(1)) for name, lineno in methods: if name != "__path__": print " def", name, lineno diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py index 1953f29..db823ff 100644 --- a/Lib/test/test_builtin.py +++ b/Lib/test/test_builtin.py @@ -3,7 +3,7 @@ import test.test_support, unittest from test.test_support import fcmp, have_unicode, TESTFN, unlink -import sys, warnings, cStringIO +import sys, warnings, cStringIO, random warnings.filterwarnings("ignore", "hex../oct.. of negative int", FutureWarning, __name__) warnings.filterwarnings("ignore", "integer argument expected", @@ -1153,8 +1153,41 @@ class BuiltinTest(unittest.TestCase): return i self.assertRaises(ValueError, zip, BadSeq(), BadSeq()) +class TestSorted(unittest.TestCase): + + def test_basic(self): + data = range(100) + copy = data[:] + random.shuffle(copy) + self.assertEqual(data, sorted(copy)) + self.assertNotEqual(data, copy) + + data.reverse() + random.shuffle(copy) + self.assertEqual(data, sorted(copy, cmp=lambda x, y: cmp(y,x))) + self.assertNotEqual(data, copy) + random.shuffle(copy) + self.assertEqual(data, sorted(copy, key=lambda x: -x)) + self.assertNotEqual(data, copy) + random.shuffle(copy) + self.assertEqual(data, sorted(copy, reverse=1)) + self.assertNotEqual(data, copy) + + def test_inputtypes(self): + s = 'abracadabra' + for T in [unicode, list, tuple]: + self.assertEqual(sorted(s), sorted(T(s))) + + s = ''.join(dict.fromkeys(s).keys()) # unique letters only + for T in [unicode, set, frozenset, list, tuple, dict.fromkeys]: + self.assertEqual(sorted(s), sorted(T(s))) + + def test_baddecorator(self): + data = 'The quick Brown fox Jumped over The lazy Dog'.split() + self.assertRaises(TypeError, sorted, data, None, lambda x,y: 0) + def test_main(): - test.test_support.run_unittest(BuiltinTest) + test.test_support.run_unittest(BuiltinTest, TestSorted) if __name__ == "__main__": test_main() diff --git a/Lib/test/test_descrtut.py b/Lib/test/test_descrtut.py index b895d6d..58b7451 100644 --- a/Lib/test/test_descrtut.py +++ b/Lib/test/test_descrtut.py @@ -226,8 +226,7 @@ Instead, you can get the same information from the list type: 'pop', 'remove', 'reverse', - 'sort', - 'sorted'] + 'sort'] The new introspection API gives more information than the old one: in addition to the regular methods, it also shows the methods that are diff --git a/Lib/test/test_itertools.py b/Lib/test/test_itertools.py index b4c0a8b..31b1b7c 100644 --- a/Lib/test/test_itertools.py +++ b/Lib/test/test_itertools.py @@ -97,16 +97,16 @@ class TestBasicOps(unittest.TestCase): # Exercise pipes and filters style s = 'abracadabra' # sort s | uniq - r = [k for k, g in groupby(list.sorted(s))] + r = [k for k, g in groupby(sorted(s))] self.assertEqual(r, ['a', 'b', 'c', 'd', 'r']) # sort s | uniq -d - r = [k for k, g in groupby(list.sorted(s)) if list(islice(g,1,2))] + r = [k for k, g in groupby(sorted(s)) if list(islice(g,1,2))] self.assertEqual(r, ['a', 'b', 'r']) # sort s | uniq -c - r = [(len(list(g)), k) for k, g in groupby(list.sorted(s))] + r = [(len(list(g)), k) for k, g in groupby(sorted(s))] self.assertEqual(r, [(5, 'a'), (2, 'b'), (1, 'c'), (1, 'd'), (2, 'r')]) # sort s | uniq -c | sort -rn | head -3 - r = list.sorted([(len(list(g)) , k) for k, g in groupby(list.sorted(s))], reverse=True)[:3] + r = sorted([(len(list(g)) , k) for k, g in groupby(sorted(s))], reverse=True)[:3] self.assertEqual(r, [(5, 'a'), (2, 'r'), (2, 'b')]) # iter.next failure @@ -669,7 +669,7 @@ Samuele >>> from operator import itemgetter >>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3) ->>> di = list.sorted(d.iteritems(), key=itemgetter(1)) +>>> di = sorted(d.iteritems(), key=itemgetter(1)) >>> for k, g in groupby(di, itemgetter(1)): ... print k, map(itemgetter(0), g) ... diff --git a/Lib/test/test_operator.py b/Lib/test/test_operator.py index e3a67f0..3263db2 100644 --- a/Lib/test/test_operator.py +++ b/Lib/test/test_operator.py @@ -263,7 +263,7 @@ class OperatorTestCase(unittest.TestCase): inventory = [('apple', 3), ('banana', 2), ('pear', 5), ('orange', 1)] getcount = operator.itemgetter(1) self.assertEqual(map(getcount, inventory), [3, 2, 5, 1]) - self.assertEqual(list.sorted(inventory, key=getcount), + self.assertEqual(sorted(inventory, key=getcount), [('orange', 1), ('banana', 2), ('apple', 3), ('pear', 5)]) def test_main(): diff --git a/Lib/test/test_set.py b/Lib/test/test_set.py index f3cdc17..5d37169 100644 --- a/Lib/test/test_set.py +++ b/Lib/test/test_set.py @@ -22,8 +22,8 @@ class TestJointOps(unittest.TestCase): self.d = dict.fromkeys(word) def test_uniquification(self): - actual = list.sorted(self.s) - expected = list.sorted(self.d) + actual = sorted(self.s) + expected = sorted(self.d) self.assertEqual(actual, expected) self.assertRaises(PassThru, self.thetype, check_pass_thru()) self.assertRaises(TypeError, self.thetype, [[]]) @@ -1241,7 +1241,7 @@ class TestVariousIteratorArgs(unittest.TestCase): for cons in (set, frozenset): for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): for g in (G, I, Ig, S, L, R): - self.assertEqual(list.sorted(cons(g(s))), list.sorted(g(s))) + self.assertEqual(sorted(cons(g(s))), sorted(g(s))) self.assertRaises(TypeError, cons , X(s)) self.assertRaises(TypeError, cons , N(s)) self.assertRaises(ZeroDivisionError, cons , E(s)) @@ -1253,7 +1253,7 @@ class TestVariousIteratorArgs(unittest.TestCase): for g in (G, I, Ig, L, R): expected = meth(data) actual = meth(G(data)) - self.assertEqual(list.sorted(actual), list.sorted(expected)) + self.assertEqual(sorted(actual), sorted(expected)) self.assertRaises(TypeError, meth, X(s)) self.assertRaises(TypeError, meth, N(s)) self.assertRaises(ZeroDivisionError, meth, E(s)) @@ -1267,7 +1267,7 @@ class TestVariousIteratorArgs(unittest.TestCase): t = s.copy() getattr(s, methname)(list(g(data))) getattr(t, methname)(g(data)) - self.assertEqual(list.sorted(s), list.sorted(t)) + self.assertEqual(sorted(s), sorted(t)) self.assertRaises(TypeError, getattr(set('january'), methname), X(data)) self.assertRaises(TypeError, getattr(set('january'), methname), N(data)) diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py index 667c9ce..dedc41c 100644 --- a/Lib/test/test_sort.py +++ b/Lib/test/test_sort.py @@ -248,66 +248,11 @@ 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, frozenset, 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, ) @@ -75,6 +75,9 @@ Core and builtins - Added a reversed() builtin function that returns a reverse iterator over a sequence. +- Added a sorted() builtin function that returns a new sorted list + from any iterable. + - CObjects are now mutable (on the C level) through PyCObject_SetVoidPtr. - list.sort() now supports three keyword arguments: cmp, key, and reverse. @@ -86,9 +89,6 @@ 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.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 unicode implementation assumes an unsigned type. diff --git a/Objects/listobject.c b/Objects/listobject.c index 3915cc9..47673be 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -2021,38 +2021,6 @@ 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) @@ -2394,9 +2362,6 @@ 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 PyObject *list_subscript(PyListObject*, PyObject*); @@ -2412,8 +2377,6 @@ 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 */ }; diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c index 9d6378b..314fb4e 100644 --- a/Python/bltinmodule.c +++ b/Python/bltinmodule.c @@ -1758,6 +1758,50 @@ PyDoc_STRVAR(round_doc, Round a number to a given precision in decimal digits (default 0 digits).\n\ This always returns a floating point number. Precision may be negative."); +static PyObject * +builtin_sorted(PyObject *self, PyObject *args, PyObject *kwds) +{ + PyObject *newlist, *v, *seq, *compare=NULL, *keyfunc=NULL, *newargs; + PyObject *callable; + 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 = PySequence_List(seq); + if (newlist == NULL) + return NULL; + + callable = PyObject_GetAttrString(newlist, "sort"); + if (callable == NULL) { + Py_DECREF(newlist); + return NULL; + } + + newargs = PyTuple_GetSlice(args, 1, 4); + if (newargs == NULL) { + Py_DECREF(newlist); + Py_DECREF(callable); + return NULL; + } + + v = PyObject_Call(callable, newargs, kwds); + Py_DECREF(newargs); + Py_DECREF(callable); + if (v == NULL) { + Py_DECREF(newlist); + return NULL; + } + Py_DECREF(v); + return newlist; +} + +PyDoc_STRVAR(sorted_doc, +"sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list"); static PyObject * builtin_vars(PyObject *self, PyObject *args) @@ -2055,6 +2099,7 @@ static PyMethodDef builtin_methods[] = { {"repr", builtin_repr, METH_O, repr_doc}, {"round", builtin_round, METH_VARARGS, round_doc}, {"setattr", builtin_setattr, METH_VARARGS, setattr_doc}, + {"sorted", (PyCFunction)builtin_sorted, METH_VARARGS | METH_KEYWORDS, sorted_doc}, {"sum", builtin_sum, METH_VARARGS, sum_doc}, #ifdef Py_USING_UNICODE {"unichr", builtin_unichr, METH_VARARGS, unichr_doc}, |