Subtype Polymorphism, Comparators, Comparables, Generic Functions
1
Lecture 9
CS61B, Spring 2025 @ UC Berkeley
Josh Hug and Justin Yokota
Note
This is an almost entirely new lecture that synthesizes and modernizes some older 61B material. Sorry if it’s a bit rough around the edges.
Polymorphism vs. Function Passing
Lecture 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
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 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
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!
Note that if we print the maxDog, we’ll get weird output. Will cover this in the next lecture.
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 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
Summary
Interfaces Quiz #1: yellkey.com/note
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/instead
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 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
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 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
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)
Generic Functions (Warmup)
Lecture 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
Summary
Goal: Writing a Max Function
We’ve seen that Java provides a nice Collections.max function for us.
Let’s see how we can write such functions ourselves.
Selecting a Random Item
Suppose we want a function which picks a random item from an array. Some code is shown below:
public class RandomPicker {
public static String pickRandom(String[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
public class RandomPickerDemo {
public static void main(String[] args) {
String[] x = {"hi", "little", "cat"};
System.out.println(RandomPicker.pickRandom(x));
}
}
Selecting a Random Item
Let’s try to modify this function so that it takes an array of anything.
public class RandomPicker {
public static String pickRandom(String[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
Approach 1: Using Generics
Our first attempt is to use our syntax for generics for our RandomPicker class. Leads us to code like this:
Why doesn’t this code make sense? (Java won’t compile it)
public class RandomPicker<T> {
public static T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
Approach 1: Using Generics
Our first attempt is to use our syntax for generics for our RandomPicker class. Leads us to code like this:
Why doesn’t this code make sense? (Java won’t compile it)
public class RandomPicker<T> {
public static T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
Approach 1: Using Generics
If we make the method non-static and instantiate a RandomPicker, it’ll work.
public class RandomPicker<T> {
public T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
public class RandomPickerDemo {
public static void main(String[] args) {
String[] x = {"hi", "little", "cat"};
RandomPicker<String> rp = new RandomPicker<>();
System.out.println(rp.pickRandom(x));
}
}
Approach 1: Using Generics
If we make the method non-static and instantiate a RandomPicker, it’ll work.
public class RandomPickerDemo {
public static void main(String[] args) {
String[] x = {"hi", "little", "cat"};
RandomPicker<String> rp = new RandomPicker<>();
System.out.println(rp.pickRandom(x));
}
}
Approach 2: Make the Static Method Generic
The correct approach is to make the method itself generic.
public class RandomPicker {
public static <T> T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
Approach 2: Make the Static Method Generic
After making our pickRandom function generic, our RandomPickerDemo will work fine. Note we never actually say <String>, this is inferred by the compiler.
public class RandomPicker {
public static <T> T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
public class RandomPickerDemo {
public static void main(String[] args) {
String[] x = {"hi", "little", "cat"};
System.out.println(RandomPicker.pickRandom(x));
}
}
Primitive vs. Reference Types
Note: Our pickRandom function will not work with integers!
public class RandomPicker {
public static <T> T pickRandom(T[] x) {
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}
public class RandomPickerDemo {
public static void main(String[] args) {
int[] x = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(RandomPicker.pickRandom(x));
}
}
Primitive vs. Reference Types
Note: Our pickRandom function will not work with integers!
Libraries like Arrays.java end up with many different methods that are very similar:
Perhaps one day Project Valhalla will fix this chasm between primitive types and reference types.
Max Function and Type Bounds
Lecture 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
Summary
Wrapping up Max
Let’s wrap up today by finishing up our max function. We know it’ll start something like this.
public class Maximizer {
public static <T> T max(T[] items) {
}
}
Almost There
We know that if our type T is comparable, we can use compareTo, leading to the code shown below:
public class Maximizer {
public static <T> T max(T[] items) {
T maxItem = items[0];
for (int i = 0; i < items.length; i += 1) {
int cmp = items[i].compareTo(maxItem);
if (cmp > 0) {
maxItem = items[i];
}
}
return maxItem;
}
}
An Issue: Is T Comparable?
Unfortunately, Java doesn’t know if T has a compareTo method.
public class Maximizer {
public static <T> T max(T[] items) {
T maxItem = items[0];
for (int i = 0; i < items.length; i += 1) {
int cmp = items[i].compareTo(maxItem);
if (cmp > 0) {
maxItem = items[i];
}
}
return maxItem;
}
}
Letting Java Know T is-a Comparable<T> Using a Type Bound
We can add a so-called “type bound” to fix this problem.
public class Maximizer {
public static <T extends Comparable<T>> T max(T[] items) {
T maxItem = items[0];
for (int i = 0; i < items.length; i += 1) {
int cmp = items[i].compareTo(maxItem);
if (cmp > 0) {
maxItem = items[i];
}
}
return maxItem;
}
}
Letting Java Know T is-a Comparable<T> Using a Type Bound
We can add a so-called “type bound” to fix this problem.
public class Maximizer {
public static <T extends Comparable<T>> T max(T[] items) {
...
}
}
Comparable<T>
T
Bonus Slide:
An even better type bound is given below.
In practice, many Java libraries have messy signatures.
public class Maximizer {
public static <T extends Comparable<? super T>> T max(T[] items) {
...
}
}
Comparable<? super T>
T
Summary
Lecture 9, CS61B, Spring 2025
Polymorphism vs. Function Passing
Comparable and Comparators
Writing a Max Function
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
Summary
Code that actually uses Comparators and Comparables in complex ways results in declarations that can be hard to read.
Note: Java does support function passing. We will not cover this in 61B.
public class Maximizer {
public static <T extends Comparable<? super T>> T max(T[] items) {
...
}
}