CS61B(8): Inheritance, Implements

This is the lecture note of CS61B - Lecture 8.

A Real Problem

Recall SLList and AList we have implemented until now. They exactly have many same methods (signatures), although their data structures under the hood are totally different.

Now, suppose we’re writing a library to manipulate lists of words. We might want to write a function that finds the longest word from a list of words.

public class WordUtils {
    public static String longest(SLList<String> list) {
        // ...

        return list.get(maxId);
    }

    public static void main(String[] args) {
        SLList<String> L = new SLList<>();
        L.addLast("elk");
        L.addLast("are");
        L.addLast("watching");
        System.out.println(longest(L));   // watching

        AList<String> L2 = new AList<>();
        L2.addLast("elk");
        L2.addLast("are");
        L2.addLast("watching");
        System.out.println(longest(L2));   // Error: we can't pass AList to longest method
    }
}

/*
If X is a superclass of Y, then memory boxes for X may contain Y.
*/

Read the code above, I think you should understand why there is an error when calling longest method on an AList. Now, what should we do if we want the longest method can also handle AList beautifully?

To sovle this problem, you should know the knowledge of interface and inheritance.

Hypernyms, Hyponyms, and Interface Inheritance

• Hypernyms(上位词) represent abstraction.
• Hyponyms(下位词) represent details.

Java can help us build this hierarchy.

Now, turn back to the previous problem. We can solve it now.

public class WordUtils {
    public static String longest(List61B<String> list) {  // <-- change here
        // ...

        return list.get(maxId);
    }

    public static void main(String[] args) {
        SLList<String> L = new SLList<>();
        L.addLast("elk");
        L.addLast("are");
        L.addLast("watching");
        System.out.println(longest(L));   // watching

        AList<String> L2 = new AList<>();
        L2.addLast("elk");
        L2.addLast("are");
        L2.addLast("watching");
        System.out.println(longest(L2));   // watching
    }
}

Overriding vs. Overloading

##Interface Inheritance

In the last section, we said that subclass must override all methods of interface, otherwise it will fail to compile. In fact, this is not accurate.

public interface List61B<Item> {
    void addFirst(Item x);

    void addLast(Item y);
   
    Item getFirst();

    Item getLast();

    Item removeLast();

    Item get(int i);

    void insert(Item x, int position);

    int size();

    default void print() {
        for (int i = 0; i < size(); i += 1) {
            System.out.print(get(i) + " ");
        }
    System.out.println();
    }
}

If you don’t like the default method, you absolutely can override it. For example, the default print method is inefficient for SLList, so we override it:

public interface SLList<Item> implements List61B<Item> {

    // ...

    /** 
     * the default print method is inefficient for SLList, so we override it. 
     * */
    @Override
    public void print() {
        for (Node p = sentinel.next; p != null; p = p.next) {
            System.out.print(p.item + " ");     	
        }
    
        System.out.println();
    }
}

Static and Dynamic Type, Dynamic Method Selection

To wrap up above materials, let's do a puzzle.

Suppose we have classes defined below. Try to predict the results.

interface Animal {
    default void greet(Animal a) {
        print("hello animal"); }
    
    default void sniff(Animal a) {
        print("sniff animal"); }
        
    default void praise(Animal a) {
        print("u r cool animal"); }
}

class Dog implements Animal {
    void sniff(Animal a) {
        print("dog sniff animal"); }
  
    void praise(Dog a) {
        print("u r cool dog"); }
}

public class Test {
    public static void main(String[] args) {
        Animal a = new Dog();
        Dog d = new Dog();
        a.greet(d);
        a.sniff(d);
        d.praise(d);
        a.praise(d);
    }
}

Add annotation to the above code, and also give the answer.

public interface Animal {
    default void greet(Animal a) { 
        print("hello animal"); }
    
    default void sniff(Animal a) {
        print("sniff animal"); }
        
    default void praise(Animal a) {
        print("u r cool animal"); }
}

public class Dog implements Animal {
    @Override
    void sniff(Animal a) {
        print("dog sniff animal"); }

    // Overload
    void praise(Dog a) {
        print("u r cool dog"); }
}

public class Test {
    public static void main(String[] args) {
        Animal a = new Dog();  // static type:Animal; dynamic type: Dog
        Dog d = new Dog();  // static type & dynamic type: Dog
        
        a.greet(d);  // hello animal
        a.sniff(d);  // dog sniff animal
        d.praise(d);  // u r cool dog
        a.praise(d);  // u r cool animal
    }
}

The shocking answer is the last one, i.e. a.flatter(d); . Why?

There are some rules that you should apply when solving such problems.

• At compile time: we determine the signature S of the method to be called.
  • S is decided using ONLY static types
• At runtime: the dynamic type of the invoking object uses its method with this exact signature S.
  • By involing object, we mean the object whose method is invoked.

So,

• since a has Animal static type, a.greet(d) will call the default interface method greet;
• although a has Animal static type, the sniff method has be overriden in Dog class, so a.sniff(d) will call the dynamic type method sniff;
• since d has Dog static type, d.praise(d) will call the method praise from Dog class;
• notice praise method is not overriden, it's just overload, so since a has Animal static type, a.praise(d) will call the default interface method praise;

🦔 Related Slides: link here

Real World

Finally, let's go back to the real world.

We will use the Java's built-in List interface and several implementations, e.g. ArrayList, LinkedList, Stack, Vector etc. in our future works.

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class Examples {
    public static void main(String[] args) {
        List<Integer> L = new ArrayList<>();
        L.add(5);
        L.add(10);
        L.add(15);
        System.out.println(L);  // L.toString()

        List<Integer> L2 = new LinkedList<>();
    }
}

Reference: LINK