Grade by Grade
A. Programming Concepts and Skills · Data Types, Files and Expressions

Making Objects Comparable

A1.3 A1.5 A4.3About 70 minutes
Learning goals
  • I can explain what the Comparable interface means in Java and how Python achieves the same with comparison methods.
  • I can write __eq__ and __lt__ (with @total_ordering) so that objects can be compared, sorted and passed to max and min.
  • I can use @dataclass(order=True), key functions and cmp_to_key to order records and objects.
  • I can check that a comparison is a consistent total order.

Words to know

Comparable interface
In Java, a promise that a class has a compareTo(other) method returning negative, zero or positive, so its objects have a natural order.
natural ordering
The default order of a type, used by sorted() with no key (numbers by size, strings by code point, a comparable class by its own rule).
rich comparison methods
Python's special methods __lt__, __le__, __eq__, __ne__, __gt__, __ge__ that define <, <=, ==, !=, >, >= for a class.
`@total_ordering`
A decorator from functools that builds the remaining comparison methods from __eq__ and one of __lt__, __le__, __gt__ or __ge__.
Comparator
A separate object or function that defines an ordering from outside a class (Java Comparator; Python key or cmp_to_key).
total order
An ordering in which any two items can be compared and the rules (irreflexive, antisymmetric, transitive) always hold.
`NotImplemented`
A special value a comparison method returns when it cannot compare with the other object's type, so Python can try something else or raise TypeError.

Teaching objects to line up

Python knows how to compare numbers and strings. It has no idea how to compare two race results, two software versions or two report-card grades. Try sorted() on a list of ordinary objects and you get TypeError: '<' not supported.

The curriculum calls the fix the comparable interface: a class declares how its objects are ordered, and from then on every sorting and searching tool works on them. In this lesson you will do that in Python, see how it maps to Java's Comparable, and learn the rules every ordering must obey.

compared as stringscompared as number tuples1.10.01.9.3"1" (49) < "9" (57), so "1.10.0" < "1.9.3"wrong!11001931 = 1, then 10 > 9, so (1, 10, 0) > (1, 9, 3)correct
Software version numbers compared two ways. As text, the first difference is the character "1" versus "9", which gives the wrong answer. As tuples of integers, the parts are compared as numbers, so version 1.10.0 is correctly newer than 1.9.3.

Comparison methods

When Python evaluates a < b, it calls a.__lt__(b). When it evaluates a == b, it calls a.__eq__(b). So to make a class comparable:

  1. Write __eq__ (equal contents).
  2. Write __lt__ (less than).
  3. Put @total_ordering above the class so Python derives <=, > and >=.

Inside each method, check the other object's type with isinstance. If it is not something you know how to compare, return NotImplemented (not False). Python then reports a clear TypeError instead of a wrong answer.

sorted, list.sort, min and max only need <, so once __lt__ exists, they all work.

from functools import total_ordering
@total_ordering
class Version:
"""A software version such as 1.10.2, ordered numerically part by part."""
def __init__(self, text):
self.parts = tuple(int(p) for p in text.split("."))
def __eq__(self, other):
if not isinstance(other, Version):
return NotImplemented
return self.parts == other.parts
def __lt__(self, other):
if not isinstance(other, Version):
return NotImplemented
return self.parts < other.parts
def __repr__(self):
return "Version('" + ".".join(str(p) for p in self.parts) + "')"
a, b = Version("1.10.0"), Version("1.9.3")
print(a > b, a == Version("1.10.0"), a <= b)
releases = [Version(t) for t in ["1.10.0", "1.9.3", "1.2.10", "1.2.9"]]
print(sorted(releases))
print(max(releases))

Making a class comparable. We write __eq__ and __lt__; @total_ordering fills in <=, > and >= from them. Now sorted, max and min work on Version objects directly. Output, line by line: True True False | [Version('1.2.9'), Version('1.2.10'), Version('1.9.3'), Version('1.10.0')] | Version('1.10.0')

JavaPythonclass V implements Comparable<V>class V: (no interface needed)int compareTo(V other)def __lt__(self, other)boolean equals(Object o)def __eq__(self, other)Collections.sort(list)sorted(lst) or lst.sort()Comparator (separate rule)key= or functools.cmp_to_key
The same idea in two languages. Java's Comparable interface asks a class for one compareTo method that returns negative, zero or positive. Python asks for comparison methods such as __lt__ and __eq__. A separate rule for ordering is a Comparator in Java and a key function in Python.

Records that compare like tuples

For record-style classes (Lesson 7), @dataclass(order=True) writes all the comparison methods for you. It compares the fields in the order they are declared, exactly like comparing tuples: the first field decides, and later fields only break ties.

This means the order of the field list is a design decision. In the race example below, time comes first so the fastest runner sorts first, and the bib number breaks ties.

from dataclasses import dataclass
@dataclass(order=True)
class Entry:
"""A race result. Fields are compared in order: time first, then bib number."""
time_s: float
bib: int
name: str
results = [Entry(612.4, 31, "Noor"), Entry(598.0, 12, "Liam"),
Entry(612.4, 7, "Aiyana"), Entry(640.9, 3, "Mateo")]
for e in sorted(results):
print(e.time_s, e.bib, e.name)
print(Entry(598.0, 12, "Liam") == results[1])

@dataclass(order=True) makes records comparable like tuples: the first field decides, then the next breaks ties. Put the fields in the order you want them compared. Output, line by line: 598.0 12 Liam | 612.4 7 Aiyana | 612.4 31 Noor | 640.9 3 Mateo | True

Worked example

Example 1: Design a comparable Grade

Letter grades on a report are ordered F < D < C < B < A. Design a class Grade so that Grade("B") < Grade("A") is True and a list of grades can be sorted. Plain strings fail: "A" < "B" is True, which is the wrong way round.

  1. Choose a sort key inside the class: the position of the letter in "FDCBA". F is 0, A is 4.
  2. Store the letter, and compare keys: def __lt__(self, other): return ORDER.index(self.letter) < ORDER.index(other.letter) where ORDER = "FDCBA".
  3. Define __eq__ to compare letters, and add @total_ordering so >, <= and >= also work.
  4. Validate in __init__: raise ValueError if the letter is not in ORDER, so an impossible grade can never be compared.
  5. Now sorted([Grade("B"), Grade("A"), Grade("D")]) gives D, B, A, and max(...) gives A.

Compare by position in "FDCBA", not by the letter's code point. Define __eq__ and __lt__ and use @total_ordering.

Ordering from outside: comparators and keys

Sometimes a class needs several orders: a leaderboard by points, a roster by jersey number, a phone list by name. A class has only one natural order, so the others are given from outside:

  • In Java, you write a Comparator, an object with a compare(a, b) method.
  • In Python, you usually pass a key function: sorted(roster, key=lambda p: p.number).
  • If you already have a Java-style three-way compare function, functools.cmp_to_key adapts it to a key.

Python's sort is stable: items that compare equal keep their original relative order. That lets you sort by a secondary field first and then by the main field.

from functools import cmp_to_key
words = ["Moose", "beaver", "Loon", "caribou", "orca"]
def by_length_then_alpha(a, b):
"""Three-way comparison, like Java's Comparator.compare."""
if len(a) != len(b):
return len(a) - len(b)
x, y = a.casefold(), b.casefold()
return (x > y) - (x < y) # -1, 0 or 1
print(sorted(words, key=cmp_to_key(by_length_then_alpha)))
print(sorted(words, key=lambda w: (len(w), w.casefold())))

Two ways to give an ordering from outside the class. A Java-style three-way compare function needs cmp_to_key; a key function (Lesson 4) is usually simpler and faster. (x > y) - (x < y) turns two Booleans into −1, 0 or 1. Output, line by line: ['Loon', 'orca', 'Moose', 'beaver', 'caribou'] | ['Loon', 'orca', 'Moose', 'beaver', 'caribou']

Keep equality and ordering consistent

If a == b is True, then a < b and b < a should both be False. If your __eq__ compares names but your __lt__ compares times, two objects can be "equal" while one is "less" than the other, and searches and sorts will behave strangely. Base both methods on the same key, and document that key in the class docstring (A4.3).

Worked example

Example 2: Rules a comparison must follow

A student defines __lt__ for a Team class as "a team is less than another if it has fewer wins or fewer goals". Sorting a list of teams gives a different order each time the list starts in a different order. Explain why.

  1. Sorting algorithms assume the comparison is a consistent total order. Three rules matter:
  2. Irreflexive: a < a is never true. Antisymmetric: if a < b then not b < a. Transitive: if a < b and b < c then a < c.
  3. Team X (10 wins, 20 goals) and Team Y (8 wins, 30 goals): X < Y because X has fewer goals, and Y < X because Y has fewer wins. Both are "less" than each other, which breaks antisymmetry.
  4. When the rules break, the result depends on which pairs the algorithm happens to compare, so the output changes with the starting order.
  5. Fix: compare by wins first and goals only to break ties: return (self.wins, self.goals) < (other.wins, other.goals). Tuple comparison is lexicographic (Lesson 4), so it is always a valid total order.

The "or" rule is not a valid ordering (both X < Y and Y < X). Compare a tuple of keys instead.

Just for fun

Why did the two race results refuse to stand in line?

Nobody had told them who goes first. After a quick __lt__, they sorted themselves out.

Hands-on activity

Rank your playlist

You need: Python and a list of 8 songs, books or games you know, each with a title, a year and your rating out of 10.

  1. Write a dataclass Track with order=True whose fields make the natural order highest rating first (hint: store a field such as neg_rating first, or write __lt__ yourself).
  2. Add a Version-style __lt__ by hand to a second copy of the class, with @total_ordering, and check that both versions sort the same way.
  3. Sort the same list three other ways with key functions: by title ignoring case, by year (oldest first), and by year then title.
  4. Write one sentence explaining why "1.10" < "1.9" is True for strings and how your own class avoids that kind of mistake.

What to look for: correct use of @total_ordering with __eq__ and __lt__, NotImplemented for other types, and key functions that match each requested order.

Your turn

1

What method does Python call for a < b?

2

Using the Version class, is Version("2.0") > Version("1.99.9")?

3

Why should __lt__ return NotImplemented rather than False when other is not a Version?

4

With @dataclass(order=True) and fields (time_s, bib, name), which is smaller: Entry(600, 5, "Zoe") or Entry(600, 4, "Ada")?

5

Write a key that sorts Entry objects by name, ignoring case.

6

What does @total_ordering need you to write?

7

Which Java interface corresponds to defining __lt__ and __eq__ in Python?

More practice: warm-up

1

What does sorted() need from objects in order to sort them?

2

Which module provides total_ordering?

3

What does Java's compareTo return when the objects are equal?

4

Is Python's sort stable?

5

Which argument of sorted gives an ordering from outside the class?

More practice: on your own

1

Write __lt__ for a class Time with fields hour and minute (24-hour clock).

2

Using stability, sort results by name, and among equal names by time, using two calls to sort.

3

Write a three-way compare function cmp_grade(a, b) for grade letters ordered F < D < C < B < A.

4

Explain why @dataclass(order=True) on a class with fields (name, time_s) is probably a poor choice for race results.

5

A class defines __eq__ using name and __lt__ using score. Give two objects that show the inconsistency.

Challenge

1

Explain why a comparison must be transitive for sorting to work. Give a small example of a non-transitive "rock, paper, scissors" order and what happens if you sort by it.

2

Write a Version method that also handles versions with different numbers of parts, so that 1.2 equals 1.2.0. What change to __init__ does it?

3

Java's Integer.compare(a, b) is recommended instead of return a - b; inside compareTo. Use Lesson 5 to explain why.

Check your understanding

Quiz

1.

Which methods should you write before adding @total_ordering?

2.

Why does "1.10" < "1.9" give True?

3.

With @dataclass(order=True) and fields declared as score, name, what decides the order first?

4.

What should a comparison method return if other is a type it does not understand?

5.

Sorting the same objects gives a different order each time they start in a different order, even though no two of them are equal. What is the most likely cause?

6.

What is Python's closest equivalent to a Java Comparator?

For parents and teachers

Big idea: A1.3 mentions the "comparable interface" by name. In Java this is the Comparable interface; in Python, students achieve the same thing with comparison methods. Classes are documented with docstrings that state the ordering rule (A4.3), and the lists of objects continue A1.5.

How to help: ask your teen to explain why software versions 1.10 and 1.9 confuse a plain string sort, and how their class fixes it.

Common difficulties:

  • Returning False instead of NotImplemented for unknown types.
  • Forgetting __eq__ when using @total_ordering.
  • Writing "or" rules that break the ordering laws; compare tuples instead.
  • Putting dataclass fields in the wrong order when order=True.