Inheritance and Polymorphism
Table of Contents
1. Inheritance
In lists, we implemented many versions of a dynamic list. Say we wanted to implement a static method longest that would return the longest String in a list of strings. We can use overloading to achieve this for every type of list:
public static String longest(AList<String> list) {
// -- snip --
}
public static String longest(SLList<String> list) {
// -- snip --
}
However, this quickly gets unwieldy the more “types of lists” you have: you need to copy-paste the same method over and over again for each new type of list, even though the fundamental method calls are the same.
We can obtain some inspiration from languages. In languages, we have a concept of hypernyms: a word that serves as an umbrella term for many more specific terms. For example, “dog” is a hypernym of “poodle,” “malamute,” “yorkie,” etc. These subterms are known as hyponyms of “dog.”
1.1. Interfaces
Java’s analogue of hypernyms are interfaces. Since AList and SLList and clearly both lists, we can specify a List61B interface. The idea is that an interface specifies what a list is able to do, but not how it does it:
public interface List61B<Item> {
public void addFirst(Item x);
public void addLast(Item y);
public Item getFirst();
public Item getLast();
public Item removeLast();
public Item get(int i);
public void insert(Item x, int position);
public int size();
}
Now, any class that implements this List61B interface must also implement these methods:
public class AList<Item> implements List61B<Item> {
// -- snip --
}
Now, instead of having a lot of different longest methods, we can just write:
public static String longest(List61B<String> list) {
// --snip --
}
1.1.1. Default Methods
We can also specify the implementation of methods in an interface using default methods. For example, we can git every List61B a print method like so:
public interface List61B<Item> {
// -- snip --
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
1.2. Extending Classes
When a class is a hyponym of an interface, we used implements. But, if we want a class to be a hyponym of another class, we use extends:
An extended class inherits all the members of the parent class, except for private members that are inaccessible. Additionally, when constructing the subclass, the super() constructor for the parent class will be called implicitly:
public class RotatingLL<Item> extends LinkedList<Item> {
public static void main(String[] args) {
RotatingLL<Integer> rsl = new RotatingLL<>();
rsl.addLast(10); rsl.addLast(11); rsl.addLast(12); rsl.addLast(13);
/* Rotates from [10, 11, 12, 13] to [13, 10, 11, 12] */
rsl.rotateLeft();
rsl.print();
}
/** Rotates list to the left. */
public void rotateLeft() {
Item oldFirst = removeFirst();
addLast(oldFirst);
}
}
1.3. Overrides
If a subclass has a method with the exact same signature as in the superclass, we say the subclass overrides the method:
public class AList<Item> implements List61B<Item> {
// -- snip --
@Override // optional, but provides useful compiler errors
public void addLast(Item x) {
// -- snip --
}
}
This is different from overloading, which is when methods have the same name but different signatures.
If a subclass implements an interface, that subclass must override all of the functions not implemented in the interface. This is because the interface relies on each subclass to actually implement its methods.
1.4. Object Methods
All classes are hyponyms of Object. This means that there are always a set of Object methods that work on any class.
1.4.1. toString()
The toString() method provides a string representation of an object. For example, System.out.println(Object x) calls x.toString() to get a string representation of the object in order to print it:
public String toString() {
return getClass().getName() + "@" + Integer.toHexString(hashCode());
}
1.4.2. equals()
We know that the operator == and equals() operate differently. The operator == compares the bits of the data represented, which means that for classes, it is comparing memory addresses. This causes two instances of a class that contain the same value to be different under the == operator:
Set<Integer> javaset = Set.of(5, 23, 42);
Set<Integer> javaset2 = Set.of(5, 23, 42);
IO.println(javaset == javaset2); // false
IO.println(javaset.equals(javaset2)); // true
On the other hand, we can implement the equals() method to check the actual values in the class:
@Override
public boolean equals(Object o) {
if (o instanceof Dog other) {
return this.size == other.size;
}
return false;
}
The default implementation of equals just uses ==, so we usually override it and write our own for our custom classes.
2. Polymorphism
Polymorphism is the ability in programming to present the same programming interface for differing underlying forms. In Python, we used function passing to achieve different behaviors for different types of input, but in Java, we typically use inheritance. For example, overloading an operator to handle different types of inputs is a type of polymorphism.
2.1. Comparables
Say we have a list of Dog, and we wish to find the one with maximum size:
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);
However, an error message occurs here because Collections.max doesn’t know how to compare two dogs. In Java, we must specify that Dog implements the Comparable interface. Looking at the source code for Comparable, we see:
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);
}
So, we must implement this interface in our Dog class:
public class Dog implements Comparable<Dog> {
// -- snip --
@Override
public int compareTo(Dog other) {
return size - other.size;
}
}
The flavor of polymorphism that we’ve used here is called subtype polymorphism. A supertype (Comparable) specifies the capability, and a subtype overrides the supertype’s abstract method.
2.2. Comparators
The term natural order is sometimes used to refer to the ordering implied by the comapreTo method. Suppose, however, that we wish to order some objects by something other than the natural order.
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 class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}