INHERITANCE

In Lab 3, you modified several methods in the SList class so that a "tail" reference could keep track of the end of the list, thereby speeding up the insertEnd() method.

We could have accomplished the same result without modifying SList--by creating a new class that inherits all the properties of SList, and then changing only the methods that need to change. Let's create a new class called TailList that inherits the fields and methods of the original SList class.

1
2
3
4
public class TailList extends SList {
    // The "head" and "size" fields are inherited from SList.
    private SListNode tail;
}

This code declares a TailList class that behaves just like the SList class, but has an additional field "tail" not present in the SList class. TailList is said to be a subclass of SList, and SList is the superclass of TailList. A TailList has three fields: head, size, and tail.

A subclass can modify or augment a superclass in at least three ways:

  1. It can declare new fields.
  2. It can declare new methods.
  3. It can override old methods with new implementations.

We've already seen an example of the first. Let's try out the third. The advantage of TailList is that it can perform the insertEnd() method much more quickly than a tail-less SList can. So, let's write a new insertEnd() for TailList, which will override SList's old, slow insertEnd() method.

1
2
3
4
5
public void insertEnd(Object obj) {
    // Your solution to Lab 3 goes here.
    this.tail.next = new SListNode(obj);
    this.tail = this.tail.next;
}

The isEmpty(), length(), nth(), and toString() methods of SList do not need any changes on account of the tail reference. These methods are inherited from SList, and there's no need to rewrite them.

Inheritance and Constructors

What happens when we construct a TailList? Java executes a TailList constructor, as you would expect, but first it executes the code in the SList() constructor. The TailList constructor should initialize fields unique to TailList. It can also modify the work done by SList() if appropriate.

1
2
3
4
public TailList() {
    // SList() constructor called automatically; sets size = 0, head = null
    tail = null;
}

The zero-parameter SList() constructor is always called by default, regardless of the parameters passed to the TailList constructor. To change this default behavior, the TailList constructor can explicitly call any constructor for its superclass by using the super keyword.

1
2
3
4
public TailList(int x) {
    super(x);
    tail = null;
}

The call to super() must be the first statement in the constructor. If a constructor has no explicit call to super, and its (nearest) superclass has no zero-parameter constructor, a compile-time error occurs. There is no way to tell Java not to call a superclass constructor. You have only the power to choose which of the superclass constructors is called.

Invoking Overridden Methods

Sometimes you want to override a method, yet still be able to call the method implemented in the superclass. The following example shows how to do this. Below, we want to reuse the code in SList.insertFront, but we also need to adjust the tail reference.

1
2
3
4
5
6
7
public void insertFront(Object obj) {
    super.insertFront(obj); // Insert at the front of the list.
    if (size == 1) { // If necessary,
    tail = head; // adjust the tail reference.
    }
}
}

Unlike superclass constructor invocations, ordinary superclass method invocations need not be the first statement in a method.

The protected Keyword

I lied when I said that we don't need to modify SList. One change is necessary. The head and size fields in SList must be declared protected, not private.

1
2
3
4
5
6
public class SList {
    protected SListNode head;
    protected int size;

    [Method definitions.]
}

protected is a level of protection somewhere between public and private. A protected field is visible to the declaring class and all its subclasses, but not to other classes. private fields aren't even visible to the subclasses.

If head and size are declared private, the method TailList.insertFront can't access them and won't compile. If they're declared protected, insertFront can access them because TailList is a subclass of SList.

When you write an ADT, if you think somebody might someday want to write a subclass of it, declare its vulnerable fields protected, unless you have a reason for not wanting subclasses to see them. Helper methods often should be declared "protected" as well.

Class Hierarchies

Subclasses can have subclasses. Subclassing is transitive: if Proletariat is a subclass of Worker, and Student is a subclass of Proletariat, then Student is a subclass of Worker. Furthermore, every class is a subclass of the Object class (including Java's built-in classes like String and BufferedReader.) Object is at the top of every class hierarchy.

hierarchy

That's why the item field in each listnode is of type Object: it can reference any object of any class. (It can't reference a primitive type, though.)

Dynamic Method Lookup

Here's where inheritance gets interesting. Any TailList can masquerade as an SList. An object of class TailList can be assigned to a variable of type SList--but the reverse is not true. Every TailList is an SList, but not every SList is a TailList. It merits repeating:

!!! Every TailList IS an SList. !!! For example:

1
2
SList s = new TailList(); // Groovy.
TailList t = new SList(); // COMPILE-TIME ERROR.

Memorize the following two definitions.

Static type: The type of a variable.
Dynamic type: The class of the object the variable references.

In the code above, the static type of s is SList, and the dynamic type of s is TailList. Henceforth, I will often just say "type" for static type and "class" for dynamic type. (Dynamic type can be subclass of static type.)

When we invoke an overridden method, Java calls the method for the object's dynamic type, regardless of the variable's static type.

1
2
3
4
SList s = new TailList();
s.insertEnd(obj); // Calls TailList.insertEnd()
s = new SList();
s.insertEnd(obj); // Calls SList.insertEnd()

This is called dynamic method lookup, because Java automatically looks up the right method for a given object at run-time. Why is it interesting? (Static method check when compile)

WHY DYNAMIC METHOD LOOKUP MATTERS (Worth reading and rereading)

Suppose you have a method (in any class) that sorts an SList using only SList method calls (but doesn't construct any SLists). Your method now sorts TailLists too, with no changes. Suppose you've written a class--let's call it RunLengthEncoding--that uses SLists extensively. By changing the constructors so that they create TailLists instead of SLists, your class immediately realizes the performance improvement that TailLists provide--without changing anything else in the RunLengthEncoding class.

Subtleties of Inheritance

  1. Suppose we write a new method in the TailList class called eatTail(). We can't call eatTail on an SList. We can't even call eatTail on a variable of type SList that references a TailList.

    1
    2
    3
    4
    TailList t = new TailList();
    t.eatTail(); // Groovy.
    SList s = new TailList(); // Groovy--every TailList is an SList.
    s.eatTail(); // COMPILE-TIME ERROR.

    Why? Because not every object of class SList has an "eatTail()" method, so Java can't use dynamic method lookup on the variable s.

    But if we define eatTail() in SList instead, the statements above compile and run without errors, even if no eatTail() method is defined in class TailList. (TailList inherits eatTail() from SList.)

  2. I pointed out earlier that you can't assign an SList object to a TailList variable. The rules are more complicated when you assign one variable to another.

    1
    2
    3
    4
    5
    6
    7
    SList s;
    TailList t = new TailList();
    s = t; // Groovy.
    t = s; // COMPILE-TIME ERROR.
    t = (TailList) s; // Groovy.
    s = new SList();
    t = (TailList) s; // RUN-TIME ERROR: ClassCastException.

    Why does the compiler reject t = s, but accept t = (TailList) s? It refuses t = s because not every SList is a TailList, and it wants you to confirm that you're not making a thoughtless mistake. The cast in the latter statement is your way of reassuring the compiler that you've designed the program to make sure that the SList s will always be a TailList.

    If you're wrong, Java will find out when you run the program, and will crash with a ClassCastException error message. The error occurs only at run-time because Java cannot tell in advance what class of object s will reference.

    Recall that SLists store items of type Object. When they're recovered, they usually have to be cast back to a more specific type before they can be used. Suppose we have a list of Integers. Recall that nth() returns type Object.

    1
    2
    int x = t.nth(1).intValue(); // COMPILE-TIME ERROR.
    int y = ( (Integer) t.nth(1) ).intValue(); // Groovy.

    Some methods are defined on every Object, though.

    1
    String z = t.nth(1).toString(); // Groovy.

  3. Java has an instanceof operator that tells you whether an object is of a specific class. WARNING: The o in instanceof is not capitalized.

    1
    2
    3
    if (s instanceof TailList) {
        t = (TailList) s;
    }

    This instanceof operation will return false if s is null or doesn't reference a TailList. It returns true if s references a TailList object--even if it's a subclass of TailList.

  4. More Dynamic Method Selection, Overloading vs. Overriding.

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
public interface Animal {
    default void greet(Animal a) {
        System.out.println("hello animal");
    }

    default void sniff(Animal a) {
        System.out.println("sniff animal");
    }

    default void flatter(Animal a) {
        System.out.println("u r cool animal");
    }
}

public class Dog implements Animal {
    public void sniff(Animal a) {
        System.out.println("dog sniff animal");
    }

    void flatter(Dog a) {
        System.out.println("u r cool dog");
    }

    void bark(){
        System.out.println("wooooo");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
Animal a = new Dog();
Dog d = new Dog();
a.greet(d);   // "hello animal"
a.sniff(d);   // "dog sniff animal"
d.flatter(d); // "u r cool dog"
a.flatter(d); // “u r cool animal”
d.bark(); // "wooooo"
a.bark(); //TestDog.java:30: cannot find symbol
        // symbol  : method bark()
        // location: class Animal
                // b.bark();
                // ^
((Dog) a).bark(); // "wooooo"

flatter is overloaded, not overridden!
Animal does not have bark() method!

The Method Selection Algorithm

Consider the function call foo.bar(x1), where foo has static type TPrime, and x1 has static type T1.

At compile time, the compiler verifies that TPrime has a method that can handle T1. It then records the signature of this method.

Note: If there are multiple methods that can handle T1, the compiler records the “most specific” one. For example, if T1=Dog, and TPrime has bar(Dog) and bar(Animal), it will record bar(Dog).

At runtime, if foo’s dynamic type overrides the recorded signature, use the overridden method. Otherwise, use TPrime’s version of the method.

for each LOOPS

Java has a for each loop for iterating through the elements of an array.

1
2
3
4
int[] array = {7, 12, 3, 8, 4, 9};
for (int i : array) {
    System.out.print(i + " "); // The out put is "7 12 3 8 4 9 "
}

Note that i is not iterating from 0 to 5; it's taking on the value of each array element in turn. You can iterate over arrays of any type this way.

1
2
3
4
String concat = "";
for (String s : stringArray) {
    concat = concat + s;
}

For some reason, the type declaration must be in the for statement. The compiler barfs if you try

1
2
int i;
for (i : array) // You cannot write in this way!

Default Methods In Java

Before Java 8, interfaces could have only abstract methods. The implementation of these methods has to be provided in a separate class. So, if a new method is to be added in an interface then its implementation code has to be provided in the class implementing the same interface. To overcome this issue, Java 8 has introduced the concept of default methods which allow the interfaces to have methods with implementation without affecting the classes that implement the interface.

Use the default keyword to specify a method that subclasses should inherit from an interface.

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
// A simple program to Test Interface default
// methods in java
interface TestInterface
{
    // abstract method
    public void square(int a);

    // default method
    default void show()
    {
      System.out.println("Default Method Executed");
    }
}

class TestClass implements TestInterface
{
    // implementation of square abstract method
    public void square(int a)
    {
        System.out.println(a*a);
    }

    public static void main(String args[])
    {
        TestClass d = new TestClass();
        d.square(4);

        // default method executed
        d.show();
    }
}

Interface vs. Implementation Inheritance

Interface Inheritance (a.k.a. what):

  • Allows you to generalize code in a powerful, simple way.

Implementation Inheritance (a.k.a. how):

  • Allows code-reuse: Subclasses can rely on superclasses or interfaces.
    • Example: print() implemented in List61B.java.
    • Gives another dimension of control to subclass designers: Can decide whether or not to override default implementations.

Important: In both cases, we specify “is-a” relationships, not “has-a”.

  • Good: Dog implements Animal, SLList implements List61B.
  • Bad: Cat implements Claw, Set implements SLList.

The Dangers of Implementation Inheritance

Particular Dangers of Implementation Inheritance

  • Makes it harder to keep track of where something was actually implemented (though a good IDE makes this better).
  • Rules for resolving conflicts can be arcane. Won’t cover in 61B.
    • Example: What if two interfaces both give conflicting default methods?
  • Encourages overly complex code (especially with novices).
    • Common mistake: Has-a vs. Is-a!
  • Breaks encapsulation!
    • What is encapsulation? See next week.

Implementation Inheritance: Extends

Because of extends, RotatingSLList inherits all members of SLList:

  • All instance and static variables. (Now the static variables are shared)
  • All methods.
  • All nested classes.

Constructors are not inherited.

Suppose we want to build an SLList that:

  • Remembers all Items that have been destroyed by removeLast.
  • Has an additional method printLostItems(), which prints all deleted items.
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
public static void main(String[] args) {
    VengefulSLList<Integer> vs1 = new VengefulSLList<Integer>();
    vs1.addLast(1);
    vs1.addLast(5);
    vs1.addLast(10);
    vs1.addLast(13);      /* [1, 5, 10, 13] */
    vs1.removeLast();     /* 13 gets deleted. */
    vs1.removeLast();     /* 10 gets deleted. */
    System.out.print("The fallen are: ");
    vs1.printLostItems(); /* Should print 10 and 13. */
}

public class VengefulSLList<Item> extends SLList<Item> {
    private SLList<Item> deletedItems;
    public VengefulSLList() {
       deletedItems = new SLList<Item>();
    }
  
    @Override
    public Item removeLast() {
        Item oldBack = super.removeLast(); // calls Superclass’s version of removeLast()
        deletedItems.addLast(oldBack);
        return oldBack;
    }

    public void printLostItems() {
        deletedItems.print();
    }
}

Note: Java syntax disallows super.super.

Constructors are not inherited. However, the rules of Java say that all constructors must start with a call to one of the super class’s constructors.

  • Idea: If every VengefulSLList is-an SLList, every VengefulSLList must be set up like an SLList.
    • If you didn’t call SLList constructor, sentinel would be null. Very bad.
  • You can explicitly call the constructor with the keyword super (no dot).
  • If you don’t explicitly call the constructor, Java will automatically do it for you.
1
2
3
public VengefulSLList() {
   deletedItems = new SLList<Item>();
}
1
2
3
4
public VengefulSLList() {
   super(); // must call first!
   deletedItems = new SLList<Item>();
}

These constructors are exactly equivalent.

If you want to use a super constructor other than the no-argument constructor, can give parameters to super.

1
2
3
4
public VengefulSLList(Item x) {
   super(x); //calls SLList(Item x)
   deletedItems = new SLList<Item>();
}
1
2
3
public VengefulSLList(Item x) {
   deletedItems = new SLList<Item>();
}

Not equivalent! Code below makes implicit call to super(), not super(x).

As it happens, every type in Java is a descendant of the Object class.

Important Note: extends should only be used for is-a (hypernymic) relationships!

Common mistake is to use it for “has-a” relationships. (a.k.a. meronymic).

  • Possible to subclass SLList to build a Set, but conceptually weird, e.g. get(i) doesn’t make sense, because sets are not ordered.