Forward port total_ordering() and cmp_to_key().

10 files changed, 187 insertions, 26 deletions

diff --git a/Doc/library/functions.rst b/Doc/library/functions.rst
index b85eb71..f371ffe 100644
--- a/Doc/library/functions.rst
+++ b/Doc/library/functions.rst
@@ -1014,9 +1014,8 @@ are always available.  They are listed here in alphabetical order.
    *reverse* is a boolean value.  If set to ``True``, then the list elements are
    sorted as if each comparison were reversed.
 
-   To convert an old-style *cmp* function to a *key* function, see the
-   `CmpToKey recipe in the ASPN cookbook
-   <http://code.activestate.com/recipes/576653/>`_\.
+   Use :func:`functools.cmp_to_key` to convert an
+   old-style *cmp* function to a *key* function.
 
    For sorting examples and a brief sorting tutorial, see `Sorting HowTo
    <http://wiki.python.org/moin/HowTo/Sorting/>`_\.
diff --git a/Doc/library/functools.rst b/Doc/library/functools.rst
index 94be636..1511a25 100644
--- a/Doc/library/functools.rst
+++ b/Doc/library/functools.rst
@@ -15,6 +15,51 @@ function for the purposes of this module.
 
 The :mod:`functools` module defines the following functions:
 
+..  function:: cmp_to_key(func)
+
+    Transform an old-style comparison function to a key-function.  Used with
+    tools that accept key functions (such as :func:`sorted`, :func:`min`,
+    :func:`max`, :func:`heapq.nlargest`, :func:`heapq.nsmallest`,
+    :func:`itertools.groupby`).
+    This function is primarily used as a transition tool for programs
+    being converted from Py2.x which supported the use of comparison
+    functions.
+
+    A compare function is any callable that accept two arguments, compares
+    them, and returns a negative number for less-than, zero for equality,
+    or a positive number for greater-than.  A key function is a callable
+    that accepts one argument and returns another value that indicates
+    the position in the desired collation sequence.
+
+    Example::
+
+        sorted(iterable, key=cmp_to_key(locale.strcoll))  # locale-aware sort order
+
+   .. versionadded:: 3.2
+
+.. function:: total_ordering(cls)
+
+   Given a class defining one or more rich comparison ordering methods, this
+   class decorator supplies the rest.  This simplies the effort involved
+   in specifying all of the possible rich comparison operations:
+
+   The class must define one of :meth:`__lt__`, :meth:`__le__`,
+   :meth:`__gt__`, or :meth:`__ge__`.
+   In addition, the class should supply an :meth:`__eq__` method.
+
+   For example::
+
+       @total_ordering
+       class Student:
+           def __eq__(self, other):
+               return ((self.lastname.lower(), self.firstname.lower()) ==
+                       (other.lastname.lower(), other.firstname.lower()))
+           def __lt__(self, other):
+               return ((self.lastname.lower(), self.firstname.lower()) <
+                       (other.lastname.lower(), other.firstname.lower()))
+
+   .. versionadded:: 3.2
+
 .. function:: partial(func, *args, **keywords)
 
    Return a new :class:`partial` object which when called will behave like *func*
diff --git a/Doc/library/stdtypes.rst b/Doc/library/stdtypes.rst
index 586fc8f..70eeca3 100644
--- a/Doc/library/stdtypes.rst
+++ b/Doc/library/stdtypes.rst
@@ -1567,6 +1567,9 @@ Notes:
 
    *key* specifies a function of one argument that is used to extract a comparison
    key from each list element: ``key=str.lower``.  The default value is ``None``.
+   Use :func:`functools.cmp_to_key` to convert an
+   old-style *cmp* function to a *key* function.
+
 
    *reverse* is a boolean value.  If set to ``True``, then the list elements are
    sorted as if each comparison were reversed.
diff --git a/Doc/reference/datamodel.rst b/Doc/reference/datamodel.rst
index d2f8c16..5af615d 100644
--- a/Doc/reference/datamodel.rst
+++ b/Doc/reference/datamodel.rst
@@ -1209,8 +1209,7 @@ Basic customization
    Arguments to rich comparison methods are never coerced.
 
    To automatically generate ordering operations from a single root operation,
-   see the `Total Ordering recipe in the ASPN cookbook
-   <http://code.activestate.com/recipes/576529/>`_\.
+   see :func:`functools.total_ordering`.
 
 .. method:: object.__hash__(self)
 
diff --git a/Lib/functools.py b/Lib/functools.py
index a54f030..539dc90 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -49,3 +49,50 @@ def wraps(wrapped,
     """
     return partial(update_wrapper, wrapped=wrapped,
                    assigned=assigned, updated=updated)
+
+def total_ordering(cls):
+    'Class decorator that fills-in missing ordering methods'
+    convert = {
+        '__lt__': [('__gt__', lambda self, other: other < self),
+                   ('__le__', lambda self, other: not other < self),
+                   ('__ge__', lambda self, other: not self < other)],
+        '__le__': [('__ge__', lambda self, other: other <= self),
+                   ('__lt__', lambda self, other: not other <= self),
+                   ('__gt__', lambda self, other: not self <= other)],
+        '__gt__': [('__lt__', lambda self, other: other > self),
+                   ('__ge__', lambda self, other: not other > self),
+                   ('__le__', lambda self, other: not self > other)],
+        '__ge__': [('__le__', lambda self, other: other >= self),
+                   ('__gt__', lambda self, other: not other >= self),
+                   ('__lt__', lambda self, other: not self >= other)]
+    }
+    roots = set(dir(cls)) & set(convert)
+    assert roots, 'must define at least one ordering operation: < > <= >='
+    root = max(roots)       # prefer __lt __ to __le__ to __gt__ to __ge__
+    for opname, opfunc in convert[root]:
+        if opname not in roots:
+            opfunc.__name__ = opname
+            opfunc.__doc__ = getattr(int, opname).__doc__
+            setattr(cls, opname, opfunc)
+    return cls
+
+def cmp_to_key(mycmp):
+    'Convert a cmp= function into a key= function'
+    class K(object):
+        def __init__(self, obj, *args):
+            self.obj = obj
+        def __lt__(self, other):
+            return mycmp(self.obj, other.obj) < 0
+        def __gt__(self, other):
+            return mycmp(self.obj, other.obj) > 0
+        def __eq__(self, other):
+            return mycmp(self.obj, other.obj) == 0
+        def __le__(self, other):
+            return mycmp(self.obj, other.obj) <= 0
+        def __ge__(self, other):
+            return mycmp(self.obj, other.obj) >= 0
+        def __ne__(self, other):
+            return mycmp(self.obj, other.obj) != 0
+        def __hash__(self):
+            raise TypeError('hash not implemented')
+    return K
diff --git a/Lib/pstats.py b/Lib/pstats.py
index e2fee37..14c4606 100644
--- a/Lib/pstats.py
+++ b/Lib/pstats.py
@@ -37,6 +37,7 @@ import os
 import time
 import marshal
 import re
+from functools import cmp_to_key
 
 __all__ = ["Stats"]
 
@@ -226,7 +227,7 @@ class Stats:
             stats_list.append((cc, nc, tt, ct) + func +
                               (func_std_string(func), func))
 
-        stats_list.sort(key=CmpToKey(TupleComp(sort_tuple).compare))
+        stats_list.sort(key=cmp_to_key(TupleComp(sort_tuple).compare))
 
         self.fcn_list = fcn_list = []
         for tuple in stats_list:
@@ -458,15 +459,6 @@ class TupleComp:
                 return direction
         return 0
 
-def CmpToKey(mycmp):
-    'Convert a cmp= function into a key= function'
-    class K(object):
-        def __init__(self, obj):
-            self.obj = obj
-        def __lt__(self, other):
-            return mycmp(self.obj, other.obj) == -1
-    return K
-
 
 #**************************************************************************
 # func_name is a triple (file:string, line:int, name:string)
diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py
index ae47dae..5cc2a50 100644
--- a/Lib/test/test_functools.py
+++ b/Lib/test/test_functools.py
@@ -364,7 +364,89 @@ class TestReduce(unittest.TestCase):
         d = {"one": 1, "two": 2, "three": 3}
         self.assertEqual(self.func(add, d), "".join(d.keys()))
 
-
+class TestCmpToKey(unittest.TestCase):
+    def test_cmp_to_key(self):
+        def mycmp(x, y):
+            return y - x
+        self.assertEqual(sorted(range(5), key=functools.cmp_to_key(mycmp)),
+                         [4, 3, 2, 1, 0])
+
+    def test_hash(self):
+        def mycmp(x, y):
+            return y - x
+        key = functools.cmp_to_key(mycmp)
+        k = key(10)
+        self.assertRaises(TypeError, hash(k))
+
+class TestTotalOrdering(unittest.TestCase):
+
+    def test_total_ordering_lt(self):
+        @functools.total_ordering
+        class A:
+            def __init__(self, value):
+                self.value = value
+            def __lt__(self, other):
+                return self.value < other.value
+        self.assert_(A(1) < A(2))
+        self.assert_(A(2) > A(1))
+        self.assert_(A(1) <= A(2))
+        self.assert_(A(2) >= A(1))
+        self.assert_(A(2) <= A(2))
+        self.assert_(A(2) >= A(2))
+
+    def test_total_ordering_le(self):
+        @functools.total_ordering
+        class A:
+            def __init__(self, value):
+                self.value = value
+            def __le__(self, other):
+                return self.value <= other.value
+        self.assert_(A(1) < A(2))
+        self.assert_(A(2) > A(1))
+        self.assert_(A(1) <= A(2))
+        self.assert_(A(2) >= A(1))
+        self.assert_(A(2) <= A(2))
+        self.assert_(A(2) >= A(2))
+
+    def test_total_ordering_gt(self):
+        @functools.total_ordering
+        class A:
+            def __init__(self, value):
+                self.value = value
+            def __gt__(self, other):
+                return self.value > other.value
+        self.assert_(A(1) < A(2))
+        self.assert_(A(2) > A(1))
+        self.assert_(A(1) <= A(2))
+        self.assert_(A(2) >= A(1))
+        self.assert_(A(2) <= A(2))
+        self.assert_(A(2) >= A(2))
+
+    def test_total_ordering_ge(self):
+        @functools.total_ordering
+        class A:
+            def __init__(self, value):
+                self.value = value
+            def __ge__(self, other):
+                return self.value >= other.value
+        self.assert_(A(1) < A(2))
+        self.assert_(A(2) > A(1))
+        self.assert_(A(1) <= A(2))
+        self.assert_(A(2) >= A(1))
+        self.assert_(A(2) <= A(2))
+        self.assert_(A(2) >= A(2))
+
+    def test_total_ordering_no_overwrite(self):
+        # new methods should not overwrite existing
+        @functools.total_ordering
+        class A(int):
+            raise Exception()
+        self.assert_(A(1) < A(2))
+        self.assert_(A(2) > A(1))
+        self.assert_(A(1) <= A(2))
+        self.assert_(A(2) >= A(1))
+        self.assert_(A(2) <= A(2))
+        self.assert_(A(2) >= A(2))
 
 
 def test_main(verbose=None):
diff --git a/Lib/unittest/loader.py b/Lib/unittest/loader.py
index 5d11b6e..f00f38d 100644
--- a/Lib/unittest/loader.py
+++ b/Lib/unittest/loader.py
@@ -5,6 +5,7 @@ import re
 import sys
 import traceback
 import types
+import functools
 
 from fnmatch import fnmatch
 
@@ -141,7 +142,7 @@ class TestLoader(object):
         testFnNames = testFnNames = list(filter(isTestMethod,
                                                 dir(testCaseClass)))
         if self.sortTestMethodsUsing:
-            testFnNames.sort(key=util.CmpToKey(self.sortTestMethodsUsing))
+            testFnNames.sort(key=functools.cmp_to_key(self.sortTestMethodsUsing))
         return testFnNames
 
     def discover(self, start_dir, pattern='test*.py', top_level_dir=None):
diff --git a/Lib/unittest/util.py b/Lib/unittest/util.py
index 736c202..ea8a68d 100644
--- a/Lib/unittest/util.py
+++ b/Lib/unittest/util.py
@@ -70,15 +70,6 @@ def unorderable_list_difference(expected, actual):
     # anything left in actual is unexpected
     return missing, actual
 
-def CmpToKey(mycmp):
-    'Convert a cmp= function into a key= function'
-    class K(object):
-        def __init__(self, obj, *args):
-            self.obj = obj
-        def __lt__(self, other):
-            return mycmp(self.obj, other.obj) == -1
-    return K
-
 def three_way_cmp(x, y):
     """Return -1 if x < y, 0 if x == y and 1 if x > y"""
     return (x > y) - (x < y)
diff --git a/Misc/NEWS b/Misc/NEWS
index 7c23e26..c11f3c7 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -303,6 +303,8 @@ C-API
 Library
 -------
 
+- Add functools.total_ordering() and functools.cmp_to_key().
+
 - Issue #8257: The Decimal construct now accepts a float instance
   directly, converting that float to a Decimal of equal value: