CS61B(10): Subtype Polymorphism vs. HoFs

Posted on | In , |

This is the lecture note of CS61B - Lecture 10.

⛱️ In this lecture, we will talk about Polymorphism of Java, and continue discussing HoFs deeply.

But before starting today's lecture, firstly, we will review concepts of the previous lecture with a puzzle.

Subtype Polymorphism

In the rest of this lecture, we will think about how to code the second approach in Java.

DIY Comparison

Suppose we want to write a function max() that returns the max of any array, regardless of type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static Object max(Object[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        // the following line is wrong!
        if (items[i] > items[maxDex]) {    
            maxDex = i;
        }
    }
    return items[maxDex];
}

public static void main(String[] args) {
    Dog[] dogs = {new Dog("Elyse", 3), new Dog("Sture", 9),
                    new Dog("Benjamin", 15)};
    Dog maxDog = (Dog) max(dogs);
    maxDog.bark();
}

To fix the error above, one approach is to write a max method in Dog class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static Dog maxDog(Dog[] dogs) {
    if (dogs == null || dogs.length == 0) {
        return null;
    }

    Dog maxDog = dogs[0];
    for (Dog d : dogs) {
        if (d.size > maxDog.size) {
            maxDog = d;        	
        }
    }

    return maxDog;
}

But this is a bad way. What if we want to compare apples instead of dogs? Or cats, horses ...... 🤢

So we need another way !

We have already known that objects cannot be compared to other objects with >, <, == etc. In this case, inheritance/HoFs can help us.

Solution:

Create an interface that guarantees a comparison method:

1
2
3
4
5
6
7
8
public interface OurComparable {
    /** Returns 
     * 1) negative number if this < o;
     * 2) 0 if this equals o;
     * 3) positive number if this > o
     */
    int compareTo(Object o);
}

Our dog class should implement the defined interface：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Dog implements OurComparable {
    public String name;
    private int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Object o) {
        Dog uddaDog = (Dog) o;
        return this.size - uddaDog.size;
    }

    public void bark() {
        System.out.println(name + " says: bark");
    }
}

Define the function:

1
2
3
4
5
6
7
8
9
10
11
12
public class Maximizer {
	public static OurComparable max(OurComparable[] items) {
		int maxDex = 0;
		for (int i = 0; i < items.length; i += 1) {
		    int cmp = items[i].compareTo(items[maxDex]);
                if (cmp > 0) {
                    maxDex = i;
                }
		}
		return items[maxDex];
	} 
} 
1
2
3
4
5
6
7
8
9
10
11
public class HoFDemo {
    public static void main(String[] args) {
        Dog[] dogs = {
            new Dog("Elyse", 3), 
            new Dog("Sture", 9), 
            new Dog("Benjamin",15)
            };
        Dog maxDog = (Dog) Maximizer.max(dogs);
        maxDog.bark();
    }
}

Now, try to answer 2 quizzes. Hope you can finish them correctly.

Answer: quiz 1: B quiz 2: A

built-in Comparable Interface

Although the built OurComparable works, it has some flaws. In the real world, we use a built-in interface named Comparable .

1
2
3
4
5
6
/**
 * @source: https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html
 */
public interface Comparable<T> {
     public int compareTo(T obj);
}

Rewrite the previous problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Dog implements Comparable<Dog> {
    public String name;
    private int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Dog o) {
        return this.size - o.size;
    }

    public void bark() {
        System.out.println(name + " says: bark");
    }
}

Comparators

We do not always want to compare objects in the same way every time, that is where Comparator comes in.

Sometimes, maybe you actually want to sort them in a different way, like sorting them alphabetically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    public String name;
    private int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Dog o) {
        return this.size - o.size;
    }

    public void bark() {
        System.out.println(name + " says: bark");
    }

    private static class NameComparator implements Comparator<Dog> {
        @Override
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);
        }
    }

    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Comparator;

public class DogLauncher {
    public static void main(String[] args) {
		Dog d1 = new Dog("Elyse", 3);
		Dog d2 = new Dog("Sture", 9);
		Dog d3 = new Dog("Benjamin", 15);
        Dog[] dogs = {d1, d2, d3};
        Dog maxDog = (Dog) Maximizer.max(dogs);
        maxDog.bark();  // Benjamin bark

	    Comparator<Dog> nc = Dog.getNameComparator();
        if (nc.compare(d1, d2) > 0) {  // id d1 comes later than d2 in the alphabet
        	d1.bark();
        } else {
        	d2.bark();
        }
    }
}

The only difference between Comparable and Comparator is that Comparable says "I wanna compare myself to other object", while Comparator compares two other objects.