Each class in a well-designed program denotes a distinct concept with its own set of responsibilities. Nevertheless, it is possible for two (or more) classes to share some common functionality. For example, the Java classes HashMap and TreeMap are distinct implementations of the concept of a “map,” and both support the methods get, put, keySet, and so on. The ability of a program to take advantage of this commonality is known as polymorphism .
This chapter explores the use of polymorphism in Java. Java supports polymorphism via the concept of an interface. All the techniques in this chapter use interfaces. In fact, polymorphism is so useful that most of the techniques in this book involve interfaces in some way.
It can be argued that polymorphism is the most important design concept in object-oriented programming. A solid understanding of polymorphism (and interfaces) is critical for any good Java programmer.
The Need for Polymorphism
When authorizing a loan, a checking account needs a balance of two thirds the loan amount, whereas savings accounts require only one half the loan amount.
The bank gives periodic interest to savings accounts but not checking accounts.
The toString method of an account will return “Savings Account” or “Checking Account,” as appropriate.
Using a Variable to Hold the Type of an Account
Although this code is a straightforward modification to BankAccount, it has two significant problems. First, the if-statements are inefficient. Every time one of the revised methods gets called, it must go through the conditions in its if-statement to determine what code to execute. Moreover, increasing the number of account types will cause these methods to execute more and more slowly.
Second (and more importantly), the code is difficult to modify and thus violates the fundamental design principle. Each time that another account type is added, another condition must be added to each if-statement. This is tedious, time-consuming, and error prone. If you forget to update one of the methods correctly, the resulting bug might be difficult to find.
The way to avoid this if-statement problem is to use a separate class for each type of account. Call these classes SavingsAccount and CheckingAccount. The advantage is that each class can have its own implementation of the methods, so there is no need for an if-statement. Moreover, whenever you need to add another type of bank account you can simply create a new class.
But how then does the Bank class deal with multiple account classes? You don’t want the bank to hold a separate map for each type of account because that will just introduce other modifiability problems. For example, suppose that there are several account types that give interest, with each account type having its own map. The code for the addInterest method will need to loop through each map individually, which means that each new account type will require you to add a new loop to the method.
However, BankAccount is now an interface, whose objects can be from either SavingsAccount or CheckingAccount. The next section explains how to implement such a polymorphic map in Java.
Interfaces
A Java interface is primarily a named set of method headers. (Interfaces also have other features that will be discussed later in the chapter.) An interface is similar to the API of a class. The difference is that a class’s API is inferred from its public methods, whereas an interface specifies the API explicitly without providing any code.
The Version 5 BankAccount Interface
The keyword abstract indicates that the method declaration contains only the method’s header and tells the compiler that its code will be specified elsewhere. The abstract and public keywords are optional in an interface declaration because interface methods are public and abstract by default. In the rest of the book I will follow common convention and omit the public abstract keywords from interface method headers.
The code for an interface’s methods is supplied by classes that implement the interface. Suppose that I is an interface. A class indicates its intent to implement I by adding the clause implements I to its header. If a class implements an interface then it is obligated to implement all methods declared by that interface. The compiler will generate an error if the class does not contain those methods.
The Version 5 SavingsAccount Class
The Version 5 CheckingAccount Class
In general, a class may implement any number of interfaces. Its only obligation is to have code for each method of each interface that it implements. A class is also free to have methods in addition to the ones required by its implemented interfaces. For example, SavingsAccount has the public method addInterest, which is not part of its BankAccount interface.
An interface is denoted in a class diagram by a rectangle, similarly to a class. The name of the interface goes in the rectangle. To distinguish an interface from a class, the annotation “<<interface>>” appears above its name. The interface name and its methods are italicized to emphasize that they are abstract.
Reference Types
This section examines how interfaces affect the typing of variables in a Java program. Each Java variable has a declared type, and this type determines the kind of value the variable can hold. If a variable holds a basic value (such as an int or a float) then its type is said to be a primitive type . If the variable holds an object reference then its type is said to be a reference type .
The first statement stores a SavingsAccount reference in the class-typed variable sa. This statement is legal because the class of the object reference is the same as the type of the variable. The second statement stores a SavingsAccount reference in the interface-typed variable ba. This statement is also legal because the class of the object reference implements the type of the variable.
The first two statements are legal because SavingsAccount has the public methods deposit and addInterest. Similarly, the third statement is legal because deposit is declared in BankAccount. The last statement is not legal because addInterest is not part of the BankAccount interface.
This example points out that storing an object reference in an interface-typed variable can “cripple” it. Variables sa and ba both hold similar SavingsAccount references. However, sa can call addInterest whereas ba cannot.
The Version 5 Bank Class
Consider the method newAccount . It now has an additional parameter, which is an integer denoting the account type. The value 1 denotes a savings account and 2 denotes a checking account. The method creates an object of the specified class and stores a reference to it in the variable ba. Because this variable has the type BankAccount, it can hold a reference to either a SavingsAccount or a CheckingAccount object. Consequently, both savings and checking accounts can be stored in the accounts map.
Now consider the method getBalance . Since its variable ba is interface-typed, the method does not know whether the account it gets from the map is a savings account or a checking account. But it doesn’t need to know. The method simply calls ba.getBalance, which will execute the code of whichever object ba refers to. The omitted methods are similarly polymorphic.
The method addInterest is more complex than the other methods. An understanding of this method requires knowing about type safety, which will be discussed next.
Type Safety
Testing Type Safety
The first statement stores a reference to a SavingsAccount object in a SavingsAccount variable. This is clearly type-safe. The second statement stores a reference to a CheckingAccount object in a BankAccount variable. This is type-safe because CheckingAccount implements BankAccount. The third statement stores the reference held by sa1 into a BankAccount variable. Since sa1 has the type SavingsAccount, the compiler can infer that its reference must be to a SavingsAccount object and thus can be safely stored in ba2 (because SavingsAccount implements BankAccount).
The fourth statement is clearly not type-safe because Bank does not implement BankAccount. The variable ba2 in the fifth statement has the type BankAccount, so the compiler infers that its object reference could be from either SavingsAccount or CheckingAccount. Since a CheckingAccount reference cannot be stored in a SavingsAccount variable, the statement is not type-safe. The fact that ba2 actually holds a reference to a SavingsAccount object is irrelevant.
Type Casting
It should be clear that the second statement is type-safe because the two statements, taken together, imply that variable sa will hold a SavingsAccount reference. However, the compiler does not look at the first statement when compiling the second one. It knows only that variable ba is of type BankAccount and thus could be holding a CheckingAccount value. It therefore generates a compiler error.
The typecast assures the compiler that the code really is type-safe, and that you assume all responsibility for any incorrect behavior. The compiler then obeys your request and compiles the statement. If you are wrong then the program will throw a ClassCastException at runtime.
It is now possible to consider the addInterest method from Listing 2-5. This method iterates through all the accounts but adds interest only to the savings accounts. Since the elements of the variable accounts are of type BankAccount, and BankAccount does not have an addInterest method, some fancy footwork is needed to ensure type-safety.
The method calls the Java instanceof operator. This operator returns true if the object reference on its left side can be cast to the type on its right side. By calling instanceof on each BankAccount object, the method determines which objects are of type SavingsAccount. It then uses a typecast to create an object reference of type SavingsAccount, which can then call the addInterest method.
This code compiles correctly, and if the map contains only savings accounts then this code will run correctly. However, if ba ever refers to a CheckingAccount object then the typecast will throw a ClassCastException at runtime.
This code will not compile because variable ba is of type BankAccount and is therefore not allowed to call the addInterest method. The compiler considers the method call to be unsafe even though it will only be called when ba refers to a SavingsAccount object.
Transparency
The technique of combining a call to instanceof with a typecast gives correct results, but it violates the fundamental design principle. The problem is that the code specifically mentions class names. If the bank adds another account type that also gives interest (such as a “money market account”) then you would need to modify the addInterest method to deal with it.
The if-statement problem is rearing its ugly head again. Each time a new kind of account is created, you will need to examine every relevant portion of the program to decide whether that new class needs to be added to the if-statement. For large programs, this is a daunting task that has potential for the creation of many bugs.
The way to eliminate these problems is to add the addInterest method to the BankAccount interface. Then the addInterest method of Bank could call addInterest on each of its accounts without caring which class they belonged to. Such a design is called transparent because the class of an object reference is invisible (i.e., transparent) to a client. We express these ideas in the following rule, called the rule of Transparency:
The Rule of Transparency
A client should be able to use an interface without needing to know the classes that implement that interface.
An important side effect of transparency is that it can reduce coupling between classes. In particular, note that the addInterest method no longer causes a dependency on SavingsAccount. The newAccount method is now the only place in Bank that mentions SavingsAccount and CheckingAccount. Eliminating these dependencies is a worthy goal, but involves the ability to remove the calls to the constructors. Techniques for doing so will be covered in Chapter 5.
The Open-Closed Rule
You would write a new class MoneyMarketAccount that implemented the BankAccount interface.
You would modify the newAccount method of BankClient to display a different message to the user, indicating the account type for MoneyMarketAccount.
You would modify the newAccount method in Bank to create new MoneyMarketAccount objects.
These changes fall into two categories: modification , in which existing classes change; and extension, in which new classes are written. In general, modification tends to be the source of bugs, whereas extension leads to a relatively bug-free “plug and play” situation. This insight leads to the following rule, called the Open/Closed rule:
The Open/Closed Rule
To the extent possible, a program should be open for extension but closed for modification.
The Open/Closed rule is an ideal. Most changes to a program will involve some form of modification; the goal is to limit this modification as much as possible. For example, of the three tasks listed previously, the first one requires the most work but can be implemented using extension. The remaining two tasks require relatively small modifications. The techniques of Chapter 5 will make it possible to further reduce the modifications required for these two tasks.
The Comparable Interface
Suppose that the bank has asked you to modify the banking demo so that bank accounts can be compared according to their balances. That is, it wants ba1 > ba2 if ba1 has more money than ba2.
The call x.compareTo(y) returns a number greater than 0 if x>y, a value less than 0 if x<y, and 0 if x=y. Many classes from the Java library are comparable.
The Version 6 SavingsAccount Class
The compareTo method needs to return a positive number if bal1>bal2 and a negative number if bal2>bal1. Subtracting the two balances has the desired effect. If the two balances are equal then the method uses their account numbers to arbitrarily break the tie. Thus the method will return 0 only if the comparison is between objects corresponding to the same account. This is the expected behavior of any compareTo method.
The CompareSavingsAccounts Class
The first way to find the largest account is to call the local method findMax , which performs a linear search of the list. It initializes the current maximum to be the first element. The call to compareTo compares each remaining element with the current maximum; if that element is larger then it becomes the new current maximum.
The second way to find the largest account is to use the Java library method Collections.max. That method implicitly calls compareTo for each element of the list.
The main point of this example is that the program is able to find the account having the largest balance without ever explicitly mentioning account balances. All references to the balance occur in the compareTo method.
Subtypes
The CompareBankAccounts Class
The Version 6 BankAccount Interface
The extends keyword indicates that if a class implements BankAccount then it must also implement Comparable<BankAccount>. Consequently, the classes SavingsAccount and CheckingAccount no longer need to explicitly implement Comparable<BankAccount> in their headers because they now implement the interface implicitly from BankAccount. With this change, CompareBankAccounts compiles and executes correctly.
The Java Collection Library
An Iterable object has a method iterator, which enables a client to iterate through the elements of the group. Chapter 6 discusses iteration in detail.
A Collection object is iterable, but it also has methods to add, remove, and search for its elements.
A List object is a collection whose elements have a linear order, similar to an array. It has methods to add, remove, and modify an element at a specified slot.
A Queue object is a collection whose elements also have a linear order. However, its methods only allow a client to add an element at the rear, and to remove and examine the element at the front.
A Set object is a collection that cannot have duplicate elements. It has the same methods as Collection but the add method is responsible for checking for duplicates.
A SortedSet object is a set whose elements are in sorted order. It has methods for finding the first and last elements according to this order, and methods for creating the subset of the elements earlier than a given element or the elements after a given element.
The Java library also contains several classes that implement these interfaces. Figure 2-3 shows the following four classes.
ArrayList
The class ArrayList implements List, and thus also Collection and Iterable. Its code uses an underlying array to store the list elements, which gets resized as the list expands. The class has the methods trimToSize and ensureCapacity, which allow a client to manually adjust the size of the underlying array.
LinkedList
Like ArrayList , the class LinkedList implements List (and Collection and Iterable). It uses an underlying chain of nodes to store the list elements. Unlike ArrayList, it also implements Queue. The reason is that its chain implementation allows for fast removal from the front of the list, which is important for an efficient implementation of Queue.
HashSet
The class HashSet implements Set (and Collection and Iterable). It uses a hash table to avoid inserting duplicate elements.
TreeSet
The class TreeSet implements SortedSet (as well as Set, Collection, and Iterable). It uses a search tree to store elements in sorted order.
The Liskov Substitution Principle
The type hierarchy of Figure 2-3 seems quite natural and perhaps even obvious. However, significant effort went into the crafting of the hierarchy. An interesting discussion of some of the subtler design issues appears in the Java Collections API Design FAQ, which is available at the URL https://docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html .
In general, how does one go about designing a type hierarchy? The guiding principle is called the Liskov Substitution Principle (often abbreviated as LSP). This rule is named for Barbara Liskov, who first formulated it.
The Liskov Substitution Principle
If type X extends type Y then an object of type X can always be used wherever an object of type Y is expected.
For example, consider the fact that List extends Collection. The LSP implies that List objects can substitute for Collection objects. In other words, if someone asks you for a collection then you can reasonably give them a list because the list has all the methods it needs to behave as a collection. Conversely, the LSP implies that Collection should not extend List. If someone asks you for a list then you could not give them a collection, because collections are not necessarily sequential and do not support the corresponding list methods.
Another way to understand the LSP is to examine the intended relationship between an interface and an interface it extends. For example, consider my initial description of the collection interfaces. I said that “a set is a collection that ...,” “a sorted set is a set that ...,” and so on.
In other words, each interface “is” the type that it extends, with added functionality. Such a relationship is called an IS-A relationship , and we say “Set IS-A Collection,” “SortedSet IS-A Set,” and so on. A good rule of thumb is that if you can understand a type hierarchy in terms of IS-A relationships then it satisfies the LSP.
Should SortedSet extend List?
Why isn’t there an interface SortedList?
Should Queue extend List? Should List extend Queue?
Why have the interface Set if it doesn’t provide any added functionality?
Here are the answers.
Should SortedSet Extend List?
At first glance it seems like a sorted set is fairly similar to a list. After all, its sort order determines a sequentiality: given a value n, there is a well-defined nth element. The list’s get method could be useful for accessing any element by its current slot.
The problem is that a sorted set’s modification methods would have undesirable side effects. For example, if you use the set method to change the value of the nth element then that element might change its position in the sort order (possibly along with several other elements). And it doesn’t make sense to use the add method to insert a new element into a specific slot because the slot of each new element is determined by its sort order.
Thus, a sorted set cannot do everything that a list can, which means that SortedSet cannot extend List without violating the LSP.
Why Isn’t There an Interface SortedList?
Such an interface seems reasonable. The only question is where it would go in the hierarchy. If SortedList extends List then you run into the same problem that occurred with SortedSet—namely, there is no good way for SortedList to implement the set and add methods of List. The best option is to have SortedList extend Collection, and provide additional list-like methods for accessing elements according to their slot. This would satisfy the LSP.
So why doesn’t the Java library have the interface SortedList? Most likely, the designers of the library decided that such an interface would not be that useful, and omitting it resulted in a more streamlined hierarchy.
Should Queue Extend List? Should List Extend Queue?
Queue cannot extend List because a list can access all its elements directly and insert anywhere, whereas a queue can only access the element at the front and insert at the rear.
A more interesting question is whether List should extend Queue. List methods can do everything that Queue methods can do, and more. Thus one can argue that lists are more general than queues; that is, List IS-A Queue. Declaring that List implements Queue would not violate the LSP.
The designers, on the other hand, felt that this functional relationship between lists and queues is somewhat coincidental and not very useful in practice. Conceptually, lists and queues are different beasts; nobody thinks of a list as being a more functional queue. Thus there is no such IS-A relationship and no such subtype declaration in Java.
Why Have the Interface Set if It Doesn’t Provide any Added Functionality?
This question is related to the List IS-A Queue question. Conceptually, Set and Collection are two distinct types with a clear IS-A relationship: Set IS-A Collection . Although Set does not introduce any new methods, it does alter the meaning of the add method, and that is significant enough (and useful enough) to warrant a distinct type.
The Rule of Abstraction
The DataManager1 Class
Although this class executes correctly, it is poorly designed. Its problem is that it works only for data stored in ArrayList objects. This restriction is unnecessary because there is nothing in the code that applies only to array lists.
The Class DataManager2 Class
The added flexibility of class DataManager2 results from the fact that it is dependent on the interface List, which is more abstract than the DataManager1 dependency on ArrayList. This insight is true in general, and can be expressed as the following rule of Abstraction.
The Rule of Abstraction
A class’s dependencies should be as abstract as possible.
This rule suggests that a designer should examine each dependency in a design to see if it can be made more abstract. A special case of this rule is known as “Program to Interfaces,” which asserts that it is always better to depend on an interface than a class.
The DataManager3 Class
The rule of Abstraction can also be applied to the banking demo. Consider for example the dependency between Bank and HashMap. A Bank object has the variable accounts, which maps an account number to the corresponding BankAccount object. The type of the variable is HashMap<Integer,BankAccount>. The rule of Abstraction suggests that the variable should have the type Map<Integer,BankAccount> instead. That statement is changed in the version 6 code.
Adding Code to an Interface
At the beginning of this chapter I defined an interface to be a set of method headers, similar to an API. Under this definition, an interface cannot contain code. The Java 8 release loosened this restriction so that an interface can define methods, although it still cannot declare variables. This section examines the consequences of this new ability.
The Version 6 BankAccount Interface
Both methods are examples of convenience methods . A convenience method does not introduce any new functionality. Instead, it leverages existing functionality for the convenience of clients. The method createSavingsWithDeposit creates a savings account having a specified initial balance. The method isEmpty returns true if the account’s balance is zero, and false otherwise.
Interface methods are either static or default. A static method has the keyword static, which means the same as it does in a class. A default method is nonstatic. The keyword default indicates that an implementing class may override the code if it wishes. The idea is that the interface provides a generic implementation of the method that is guaranteed to work for all implementing classes. But a specific class may be able to provide a better, more efficient implementation. For example, suppose that a money-market savings account requires a minimum balance of $100. Then it knows that the account will never be empty, and so it can overwrite the default isEmpty method to one that immediately returns false without having to examine the balance.
The Old Way to Sort a List
Code for the Sort Method
Although this code will work for any list, it has the overhead of copying the list elements to an array and back. This overhead is wasted time for some list implementations. An array list, for example, saves its list elements in an array, so it would be more efficient to sort that array directly. This situation means that a truly efficient list sorting method cannot be transparent. It would need to determine how the list is implemented and then use a sorting algorithm specific to that implementation.
A Default Sort Method for List
The second, and more important benefit is that lists can be handled transparently. The default implementation of sort works for all implementations of List. However, any particular List implementation (such as ArrayList) can choose to override this method with a more efficient implementation of its own.
Summary
A program can now declare variables of type I, which can then hold references to either C1 or C2 objects without caring which class they actually refer to.
The rule of Transparency states that a client should be able to use an interface without needing to know the classes that implement that interface.
The Open/Closed rule states that programs should be structured so that they can be revised by creating new classes instead of modifying existing ones.
The Liskov Substitution Principle (LSP) specifies when it is meaningful for one interface to be a subtype of another. In particular, X should be a subtype of Y only if an object of type X can always be used wherever an object of type Y is expected.
The rule of Abstraction states that a class’s dependencies should be as abstract as possible.