CS 61B: Lecture 10 Wednesday, February 12, 2014 Today's reading: All of Chapter 7, plus pp. 28-33, 250-257. 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. 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. public void insertEnd(Object obj) { // Your solution to Lab 3 goes here. } 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. 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. 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. 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". 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. Object / \ String Worker / \ Proletariat Bourgeoisie Superclasses appear above their subclasses. / \ | Student TA Professor 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: 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. When we invoke an overridden method, Java calls the method for the object's _dynamic_ type, regardless of the variable's static type. 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? ------------------------------------------------------------------------------- | 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. 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. 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. 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. 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. 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.