Python sorting objects of user defined class

2017-03-11
#python

The most common way of sorting collections of custom objects in Python is to provide key function that is used to extract a comparison key from each element:

sorted("Case insensitive Sorting is here".split(), key=str.lower)

But sorted function compares objects by its nature, and it is possible to define comparison operators for your class t make sorted work automatically.

Documentation guarantees that sorting uses only __lt__() method:

The sort routines are guaranteed to use __lt__() when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method.

But it is recommended to define all comparison methods for your class for the sake of safety and code completeness. It can be done with total_ordering decorator from the functools standard module. Lets look at class:

import functools

@functools.total_ordering
class Point:

    def __init__(self, x, y):
        self.x, self.y = x, y

    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

Example usage:

points = [Point(x, y) for x in range(2, 0, -1) for y in range(3, 0, -1)]

print('Not sorted:', ', '.join(map('({0.x}, {0.y})'.format, points)))
print('Sorted:', ', '.join(map('({0.x}, {0.y})'.format, sorted(points))))

will produce output:

Not sorted: (2, 3), (2, 2), (2, 1), (1, 3), (1, 2), (1, 1)
Sorted: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)

total_ordering decorator is excessive here, but may be useful in the future. What it does? It completes remaining comparison methods from implemented ones. So you implement __eq__ and __lt__, it complements __le__, __gt__, __ge__. Or you implement __eq__ and __le__, it complements __lt__, __gt__, __ge__. And so on. It requires __eq__ and one other comparison method to be defined.

Essential part of the generator code is:

def total_ordering(cls):
    """Class decorator that fills in missing ordering methods"""
    # Find user-defined comparisons (not those inherited from object).
    roots = [op for op in _convert if getattr(cls, op, None) is not getattr(object, op, None)]
    if not roots:
        raise ValueError('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
            setattr(cls, opname, opfunc)
    return cls

where _convert is dict of predefined implementations of comparison methods via each other. Code gets all defined is cls comparison methods, prefers one (if several are defined) and defines other methods.