Announcements
Today’s lecture is not in scope for the midterm.
Subtype Polymorphism, Comparators, Comparables
2
Lecture 10
CS61B, Fall 2025 @ UC Berkeley
Josh Hug and Peyrin Kao
Polymorphism vs. Function Passing
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Goals for Today
Today we’re going to dig deeper into inheritance.
Let’s see some examples in Python.
Polymorphism Example in Python
In the code above, the Dog class overrides the > operator.
def get_the_max(x):
max_value = x[0]
for item in x:
if item > max_value:
max_value = item
return max_value
max_dog = get_the_max(doglist)
class Dog:
def __init__(self, name, size):
self.name = name
self.size = size
def __gt__(self, other):
return self.size > other.size
Function Passing Example in Python
In the code above, the get_the_max function accepts a key function.
Note: Strings have their own definition for >, so we also see here polymorphism.
def get_the_max(x, key):
max_value = x[0]
for item in x:
if key(item) > key(max_value):
max_value = item
return max_value
max_dog=get_the_max(doglist, name_len)
class Dog:
def __init__(self, name, size):
self.name = name
self.size = size
def __gt__(self, other):
return self.size > other.size
def name_len(dog):
return len(dog.name)
Goals for Today
Today we’re going to dig deeper into inheritance.
We’ll spend a lot of time today writing these two examples in Java.
Comparables
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Dogs
Consider the dogs below.
“Grigometh”, size: 200
“Clifford”, size: 9000
“Pelusa”, size: 5
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dogs
To find the maximum, we can use Collections.max. Let’s try this.
“Grigometh”, size: 200
“Clifford”, size: 9000
“Pelusa”, size: 5
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxDog = Collections.max(dogs);
Dogs
To find the maximum, we can use Collections.max. Let’s try this.
This results in the incomprehensible error message below.
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxDog = Collections.max(dogs);
Capability Specification in Java
Unlike Python, where we’d define a __gt__ method to overload the > operator, in Java, we have to specify that a Dog is something that can be compared.
Question: How do we specify that a class has a certain capability in Java?
Capability Specification in Java
Unlike Python, where we’d define a __gt__ method to overload the > operator, in Java, we have to specify that a Dog is something that can be compared.
Question: How do we specify that a class has a certain capability in Java?
The Comparable Interface
Unlike Python, where we’d define a __gt__ method to overload the > operator, in Java, we have to specify that a Dog is something that can be compared.
In Java, we will declare to the world that a Dog is-a Comparable.
Since almost all of Java is written in Java, we can go look at Comparable.java.
Comparable<Dog>
Dog
List61B
SLList
The Comparable Interface
Looking at Comparable.java, we see:
Note: The full file is 142 lines long, almost all of which is documentation. This is not uncommon with really important parts of the library. Documentation is important.
public interface Comparable<T> {
/**
* Compares this object with the specified object for order.
* Returns a negative integer, zero, or a positive integer
* as this object is less than, equal to, or greater than the
* specified object.
* ...
*/
public int compareTo(T o);
}
Implementing Comparable
Let’s implement the Comparable interface in Dog.java. This means:
Implementing Comparable
Let’s implement the Comparable interface in Dog.java. This means:
public class Dog implements Comparable<Dog> {
...
@Override
public int compareTo(Dog uddaDog) {
if (size > uddaDog.size) {
return 1;
}
if (size < uddaDog.size) {
return -1;
}
return 0;
}
}
“uddaDog” courtesy of Harry Alu of Ehu & Kai Adventures (on the Big Island).
Comparable<Dog>
Dog
Implementing Comparable (Better Approach)
A cleaner implementation is shown below.
public class Dog implements Comparable<Dog> {
...
@Override
public int compareTo(Dog uddaDog) {
return size - other.size;
}
}
Comparable<Dog>
Dog
Dogs
Now that we’ve implemented Comparable, the code below works fine!
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxDog = Collections.max(dogs);
Polymorphism vs. Operator Overloading
The flavor of polymorphism we’ve just employed is sometimes called subtype polymorphism.
This is very different than Python, where there is a common > operator which can be overloaded.
Other Examples of Subtype Polymorphism
Subtype polymorphism is a very common idiom in Java.
Other examples:
This is very different than Python, where there is a common > operator which can be overloaded.
Compilation Error Puzzle
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Interfaces Quiz #1: yellkey.com/itself
public class Dog
implements Comparable<Dog> {
...
public int compareTo(Dog o) {
return this.size
- o.size;
} ...
Q: If we omit compareTo(), which file will fail to compile?
public class DogLauncher {
public static void main(String[] args) {
...
Dog[] dogs = new Dog[]{d1, d2, d3};
System.out.println(Collections.max(dogs));
}
}
public interface Collections {
// the max function
...
int cmp = items[i].
compareTo(items[maxDex]);
...
}...
}
Interfaces Quiz #2: yellkey.com/record
public class Dog
implements Comparable<Dog> {
...
public int compareTo(Dog o) {
return this.size
- o.size;
} ...
Q: If we omit implements Comparable<Dog>, which file will fail to compile?
public class DogLauncher {
public static void main(String[] args) {
...
Dog[] dogs = new Dog[]{d1, d2, d3};
System.out.println(Collections.max(dogs));
}
}
public interface Collections {
// the max function
...
int cmp = items[i].
compareTo(items[maxDex]);
...
}...
}
Answers to Quiz
Problem 1: Dog will fail to compile because it does not implement all abstract methods required by Comparable interface. (And I suppose DogLauncher will fail as well since Dog.class doesn’t exist)
Problem 2: DogLauncher will fail, because it tries to pass things that are not Comparable, and Collections expects Comparables.
Comparators
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Natural Order
The term “Natural Order” is sometimes used to refer to the ordering implied by a Comparable’s compareTo method.
“Grigometh”, size: 200
“Clifford”, size: 9000
“Pelusa”, size: 5
Alternate Sorting
May wish to order objects in a different way.
“Grigometh”, size: 200
“Clifford”, size: 9000
“Pelusa”, size: 5
Reminder: Key Functions in Python
In Python, we achieved this goal using function passing.
By contrast, in Java, idiomatic code also uses subtype polymorphism.
def get_the_max(x, key):
max_value = x[0]
for item in x:
if key(item) > key(max_value):
max_value = item
return max_value
max_dog=get_the_max(doglist, name_len)
class Dog:
def __init__(self, name, size):
self.name = name
self.size = size
def __gt__(self, other):
return self.size > other.size
def name_len(dog):
return len(dog.name)
The Comparator Interface
Java provides a Comparator interface for objects that are designed for comparing other objects.
Let’s try building and using one for comparing Dogs based on name.
public interface Comparator<T> {
int compare(T o1, T o2);
...
}
Note: The Comparator interface has a LOT of default methods. We won’t talk about them.
Comparator<Dog>
A Name Comparator
Java provides a Comparator interface for objects that are designed for comparing other objects.
public interface Comparator<T> {
int compare(T o1, T o2);
...
}
public static class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}
Comparator<Dog>
NameComparator
Comparator Quiz
What will be the output of the code below?
A. Positive number B. Negative number C. Zero
Dog a = new Dog("Frank", 1);
Dog b = new Dog("Zeke", 1);
Comparator<Dog> nc = new Dog.NameComparator();
System.out.println(nc.compare(a, b));
public static class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}
Comparator Quiz
What will be the output of the code below?
The result will be a negative number: “Frank” is alphabetically less than “Zeke”.
Dog a = new Dog("Frank", 1);
Dog b = new Dog("Zeke", 1);
Comparator<Dog> nc = new Dog.NameComparator();
System.out.println(nc.compare(a, b));
public static class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}
Using a Comparator to Find the Maximum
We can use our name comparator to find the dog with the maximum name.
Compare with Python below (using length of name rather than name itself).
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());
def length_of_name(dog):
return len(dog.name)
dogs = [Dog("Grigometh", 10),
Dog("Pelusa", 5),
Dog("Clifford", 9000)]
max_dog = get_the_max(dogs, length_of_name)
This second argument is an object of type Comparator<Dog>
Using a Comparator to Find the Maximum
We can use our name comparator to find the dog with the maximum name.
Compare with Python below.
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());
def length_of_name(dog):
return len(dog.name)
dogs = [Dog("Grigometh", 10),
Dog("Pelusa", 5),
Dog("Clifford", 9000)]
max_dog = get_the_max(dogs, length_of_name)
In Python we often pass functions directly.
In Java we package our comparison function inside of a Comparator object. We rely on subtype polymorphism.
Awkward Instantiation
The NameComparator instantiation is awkward and aesthetically unpleasant (to me).
One fix is to add a static variable reference to a pre-instantiated NameComparator.
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());
Awkward Instantiation
The NameComparator instantiation is awkward and aesthetically unpleasant (to me).
One fix is to add a static variable reference to a pre-instantiated NameComparator. The usual naming convention is all caps:
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());
public static NameComparator NAME_COMPARATOR = new NameComparator();
Dog maxNameDog = Collections.max(dogs, Dog.NAME_COMPARATOR);
Bonus Slide: Lambdas
A more modern approach is to use a lambda to define the Comparator.
List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Comparator<Dog> dc = (d1, d2) -> d1.name.compareTo(d2.name);
Dog maxNameDog = Collections.max(dogs, dc);
Comparables vs. Comparators
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Comparables vs. Comparators
The Comparable interface specifies that a “natural order” exists.
The Comparator interface is used to compare extrinsically (by other classes).
Comparator<Dog>
NameComparator
Comparable<Dog>
Dog
SizeComparator
SpeedComparator
compareTo(Dog, Dog)
compare(Dog, Dog)
Summary
Lecture 10, CS61B, Fall 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Summary
Summary
Today we’ve seen polymorphism and function passing.
For comparing two objects using an intrinsic order:
Python is duck typed: Do not have to specify if > is available or not.
class Dog:
def __init__(self, name, size):
self.name = name
self.size = size
def __gt__(self, other):
return self.size > other.size
public class Dog implements Comparable<Dog> {
...
@Override
public int compareTo(Dog uddaDog) {
return size - other.size;
}
}
Comparable<T>
T
Summary
Today we’ve seen polymorphism and function passing.
For comparing two objects using an alternate order:
public static class NameComparator
implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}
class Dog:
def __init__(self, name, size):
self.name = name
self.size = size
def name_len(dog):
return len(dog.name)
max_dog=max(doglist, key=name_len)
Comparator<Dog>
NameComparator
Now For Something Completely Different
Lecture 10, CS61B, Fall 2025
Studying for the Exam
The exam is entirely writing code.
Important:
Can get extra practice on old exams.
Tips for Studying in General
Groups of people are WAY smarter than individual people.
Best way to study:
Only look at solutions when you feel totally done with a problem. Unlikely to learn nearly as much as from the metacognition of discussing with others.
Attendance Link