Sep 25: ArrayLists and Inheritance


Code discussed in lecture

ArrayLists

Our Java construct of the day is the ArrayList.

As the Array chapter in the book demonstrates, getting to a particular item in an array is fast and easy if you know its subscript. So is changing a particular value. However, inserting and deleting items at some position becomes hard, because the items after that position must all be moved forward or backward one position. Futhermore, an array has a fixed length. If we need to save fewer items then the length of the array the last ones are empty (or at least hold meaningless values). If the array is full and we want to add more items we are out of luck.

An ArrayList gets around these problems. It is a class. The way to definite its type is to include a class name in angle brackets:

ArrayList<Pixel> lst; is a list that can contain only references to objects in the class Pixel. (This is a new addition in Java 5.0 called generics. Before that the type of ArrayList was Object. This meant that whenever you removed something from an ArrayList you had to cast it to what it really was.)

You can find all the methods that work on an ArrayList and other useful information in the ArrayList entry in the Java documentation. The most important methods for ArrayList<E> (where E is the type) are:

In methods contains, indexOf, and the version of remove that takes an Object as its parameter the test is o.equals(elmt) (where elmt is an element in the list) if o is not null, and == otherwise. (Note that we use equals rather than == to test equality of objects.)

I have modified the Picture class to add a method that reduces the number of colors in an image to 8. It does this by first splitting the pixels into those whose red value is above a threshold (the high pixels) and those whose red value is not (the low pixels). It then sets the red value in the high pixels to the average red value in the high pixels, and sets the red value in the low pixels to the average red value in the low pixels. It then repeats the process for blue and green.

This is not as good a method of picking 8 colors as k-means, which you will use in PS-1. But it demonstrates a typical use of ArrayLists. We don't know how many of the pixels will be high pixels and how many will be low pixels. Therefore we create an ArrayList for each set and add each pixel to one or the other. We then go through the lists to find average values and again to set the color values of the pixels. You can see how this is done in Picture.java.

Here is the image for beach.jpg and the image after calling reduceTo8.

Image of a beach Image of a beach using 8 colors

Here is bridge.jpg and the image after calling reduceTo8.

Image of a bridge Image of a bridge using 8 colors

ArrayLists have an unfortunate restriction - they can only hold references to objects, not primitive types. So what can you do if you want an ArrayList of ints or doubles or boolean? Java provides wrapper classes for the eight primitive types. The class names are Byte, Short, Integer, Long, Float, Double, Character, and Boolean. It also provides operations autoboxing and unboxing. If we have the code:

ArrayList<Integer> integerList = new ArrayList<Integer>(); integerList.add(3); int n = integerList.get(0); everything works correctly, because Java automatically converts an int to an Integer or an Integer to an int when these operations are needed. (To do this "by hand" you convert an int i to an Integer by saying new Integer(i). You get the integer value out of the Integer referenced by n by calling a method: n.intValue(). The other wrapper classes are similar.)

This means that while technically ArrayLists can only hold objects you can in practice add and remove primitive types from them.

A suggestion: only use autoboxing and unboxing in the sorts of ways that you see above: passing primitive arguments to parameters that expect objects, passing wrapper class objects to parameters that expect primitives, assigning primitives to variables that are of the wrapper class type, or assigning wrapper class objects to variables of primitive type. If you start combining Integer and int variables in expressions you have to understand how things get converted, and that can get complicated.

Even in these cases you need to be careful due to overloading of functions. Note that lst.remove(3) removes the item at index 3 from lst, while lst.remove(new Integer(3)) removes the first Integer whose intValue is 3 from the list.

Inheritance

We have already seen several of the key ideas of object-oriented programming. The most important one we have yet to see is inheritance.

Inheritance is a way to create new classes from existing classes. We call the existing class the superclass and the new class created from it the subclass. With inheritance, each object of the subclass "inherits" the instance variables and methods of the superclass. That way, we don't have to write these methods for the subclass unless we want to.

Of course, we'll want to write some methods in the subclass, for if we don't, the subclass is exactly the same as the superclass and there would have been no point in creating the subclass. Compared to objects of the superclass, objects of the subclass have additional specialization.

You may recall that earlier, we used interfaces to provide polymorphism: the ability of an object reference to refer to more than one type of object. We will see that inheritance gives us another, very powerful, way to achieve polymorphism. So now we have two ways to achieve polymorphism: interfaces and inheritance.

The Golden Rule of Inheritance

I'll give you some generalities about superclasses and subclasses that seem abstract at the moment, but we'll see a little later how they apply to object-oriented programming by specific examples.

If there is one thing you should remember about inheritance, it is

Use inheritance to model "is-a" relationships and only "is-a" relationships.

What does this mean? Suppose we have two classes: A is the superclass of B (which is therefore the subclass). If we have used inheritance correctly, then

  1. Every object of class B is also an object of class A.
  2. The set of objects of class B is a subset of the objects of class A.
  3. Every method that can be called on an object of class A, can also be called on an object of class B. (However, the results of the call may be very different.)
  4. Objects of class B are like objects of class A, but with additional specialization.

The BankAccount class

For our first example of inheritance, we will look at bank accounts. BankAccount.java is a basic bank account class. It has an instance variable balance that holds the current balance. It has two constructors. The first creates a new account with a balance of 0.00. The second takes in an initialAmount and uses that for the initial balance.

The BankAccount class also has a set of useful methods:

public void deposit(double amount) public void withdraw(double amount) public double getBalance() public void transfer(BankAccount other, double amount) public String toString() The deposit, withdraw, and getBalance methods do what you would expect. The transfer method transfers amount from the current bank account (referenced by this) to the bank account referenced by other. The method toString converts the information about the bank account to a String. (Recall that every object in Java has a toString method defined for it, and System.out.println uses toString to print the value of the object.)

We have seen much more complicated examples of classes. Perhaps the most interesting characteristic of our BankAccount class is the calls to withdraw and deposit within transfer. We could have written this method differently:

public void transfer(BankAccount other, double amount) { balance -= amount; other.balance += amount; } (Here's an example of a method being able to refer to private instance variables of another object in the same class. This capability has nothing to do with inheritance, but it's good to remember that methods of a class can always access instance variables of any object in the class for which they have a reference.) But instead, we chose to write it with method calls. Why? If something changes about the way the withdrawals or deposits are done (for example, if we have the withdraw method check for overdrawn accounts) then transfer will automatically use the modifed methods. Abstraction works in our favor even within a class.

Banks offer many kinds accounts, though. A savings account pays periodic interest. A checking account may have transaction fees for deposits and withdrawals. A time deposit account may have an interest penalty for early withdrawal. We could write a separate class for each of these variants of bank accounts. We would reproduce a lot of code, however. All of these different accounts have a balance, and they all have to deal with deposits, withdrawals, getting the account balance, transfers, and converting their contents to a String. Much of the code will be identical or only slightly modified.

It is this situation that inheritance was designed to deal with. The goal is to "inherit" the instance variable balance and the various methods. Methods can be used as is, if they already do the right thing. If not, they can be overridden by writing new versions of some of the methods for the new account types. These new versions, however, can call the old versions to help them out if they need to.

The SavingsAccount class

Our first subclass is SavingsAccount, defined in SavingsAccount.java. A savings account is just like a basic bank account, except that it pays interest. All the methods for the BankAccount class work fine for the SavingsAccount class. The SavingsAccount class has to add an instance variable interestRate and a method addPeriodicInterest, but otherwise it is just a BankAccount.

We indicate that SavingsAccount is a subclass of BankAccount by adding the words extends Bankaccount at the end of the header of the class declaration. Because SavingsAccount is a subclass of BankAccount, SavingsAccount will have copies of all the instance variables and methods of BankAccount. It can then add the declaration for the new instance variable interestRate and the new method addPeriodicInterest. Thus, every SavingsAccount object has two instance variables:

A couple of complications arise, however. First, although every SavingsAccount object has an instance variable balance, because this instance variable is private to BankAccount, no methods of SavingsAccount are allowed to access it directly. This restriction may seem strange at first, and there is in fact a way to let a subclass have direct access to instance variables of the superclass. The trick is to use protected access instead of private access when declaring the instance variable in the superclass. We will discuss this idea later. But we can deal with private instance variables in the superclass in the same way that any other class would: access them indirectly via methods.

The addPeriodicInterest method demonstrates this idea. The getBalance and deposit methods of BankAccount give indirect access to balance, and they are all that are needed to write addPeriodicInterest. But how is it determined what methods getBalance and deposit refer to?

Let's look at deposit. We know that the method call deposit is really an abbreviation for this.deposit. We first look in the SavingsAccount class to see whether SavingsAccount defines a deposit method. It does not. And so we look into the superclass BankAccount. Because we find a definition of deposit there, we need look no further. If we had not found deposit in the BankAccount class, then we would look at BankAccount's superclass, if there is one. Eventually, we either find a superclass that defines the deposit method or we don't. If we do, we use the first superclass that defines the method. If we don't, then we have an error: we have called a method not defined for the class.

The constructors get a bit trickier. We cannot see (and in general may not even know the names of) the private instance variables in BankAccount. How do we initialize them in our constructors?

It turns out that a constructor for the superclass (BankAccount) will always be called in the subclass (SavingsAccount) constructors. The only questions are which superclass constructor is called (recall that BankAccount has two constructors), and whether the call is explicit or implicit.

The first constructor for SavingsAccount has an implicit call of the superclass constructor. The only code appearing in the first constructor sets the instance variable interestRate. Because there is no explicit call to the superclass constructor, the Java compiler automatically inserts a call to the superclass's default constructor—the one with no parameters—as the first line of the subclass constructor. In this case, balance is initialized to 0.00 by the implicit call of the default constructor for BankAccount, and then interestRate is initialized by the constructor for SavingsAccount.

The second SavingsAccount constructor explicitly calls the superclass constructor by calling super(initialAmount) as its first line. We'll see several uses of the reserved word super in our bank account example. Here, we use it to call the one-parameter constructor of the superclass BankAccount. When a subclass constructor explicitly calls its superclass's constructor, this call must be the first line of the subclass constructor.

Let's return to the "golden rule" business above. We have made SavingsAccount a subclass of BankAccount. Have we fulfilled all four relationships that we said must hold?

  1. Is every savings account also a bank account? Yes.
  2. Is the set of savings accounts a subset of the set of bank accounts? Yes.
  3. If a method can be called on a bank account, can it also be called on a savings account? Yes.
  4. Is a savings account like a bank account, but with additional specialization? Yes, where the specialization is the ability to add interest.
It is important to note that these relationships go only one way. For example, is every bank account also a savings account? No, it is not true. Checking accounts are bank accounts that are not savings accounts. Or we can ask if a method call can be made a savings account, can it also be made on a bank account? No, for we can call addPeriodicInterest on savings accounts, but we cannot call it on all bank accounts.

It may be a bit confusing at first when you realize that a subclass may contain more instance variables and methods than the superclass. After a while, you get more comfortable with it.

The CheckingAccount class

The CheckingAccount.java class again is similar to the basic BankAccount class, but it incorporates transaction fees. In this implementation, the account owner gets FREE_TRANSACTIONS free transactions per month (3). After that, the account owner must pay a TRANSACTION_FEE for each additional transaction (50 cents). These fees are assessed at the end of each month. We have declared the constants FREE_TRANSACTIONS and TRANSACTION_FEE as static and final since they will never change (hence final) and they should be the same for all checking accounts (hence static).

Rather than worrying strictly about months, our implementation of the CheckingAccount class just worries about some period of unspecified length. The instance variable transactionCount counts the number of transactions that have occurred in the current period. To keep this variable up-to-date, we increment transactionCount every time we make a deposit or a withdrawal. The methods deposit and withdraw that are inherited from the superclass BankAccount do not handle incrementing transactionCount. We must therefore override these methods by writing new versions of them.

We can describe the desired behavior of CheckingAccount's withdraw method as

Do what the normal withdraw in BankAccount does, and then increment transactionCount.
Our implementation of withdraw in CheckingAccount does so. The code super.withdraw(amount); says to call the withdraw method of the superclass. (If we left off the super. it would try to call this.withdraw, which is the same method we are writing. This would be a recursive call, which would cause serious problems here.) Our implementation of the deposit method is analogous.

The new method deductFees takes care of transaction fees by computing the amount to be charged, withdrawing it from the account, and then setting transactionCount back to 0. It performs the withdrawal by calling super.withdraw. (In this case, just calling withdraw would also work. It would increase the number of transactions, but that gets immediately set back to 0. It is safer to use withdraw from the superclass, which does not deal with transaction fees.)

The TimeDepositAccount class

Our last class in this hierarchy of bank accounts is the TimeDepositAccount class in TimeDepositAccount.java. It is like the SavingsAccount class, except it has to charge a penalty for early withdrawal. Therefore it is a subclass of SavingsAccount. Note that it inherits the methods deposit, withdraw, getBalance, transfer, and toString from BankAccount. Why? The direct superclass of TimeDepositAccount is SavingsAccount, and these methods are not overridden in SavingsAccount. Therefore, they come from the superclass of SavingsAccount, which is BankAccount. On the other hand, TimeDepositAccount inherits the method addPeriodicInterest from SavingsAccount. For instance variables, TimeDepositAccount inherits balance from BankAccount, and it inherits interestRate from SavingsAccount; because they are private, neither of these inherited instance variables is directly accessible.

TimeDepositAccount overrides both addPeriodicInterest and withdraw. In both cases, much of the work is done by calls to super.addPeriodicInterest and super.withdraw.

A driver program that demonstrates polymorphism and dynamic binding

AccountTest.java exercises the bank account classes. It also shows that inheritance allows polymorphism and dynamic binding, as we are about to see. In this program, three accounts are created, one of each of our subclasses: Each of these objects is created using new and constructors.

Let's examine the method calls this program makes.

First is the call

momsSavings.deposit(10000.00); Because momsSavings references a SavingsAccount object, we first see whether SavingsAccount defines a deposit method. It doesn't, so we go to the SavingsAccount's superclass, BankAccount. That's where deposit is defined. We conclude that this call of deposit actually invokes the deposit method defined in the BankAccount class. We could use the debugger to confirm this observation.

Next is the call

momsSavings.transfer(harrysChecking, 2000); Like deposit, the method transfer is not defined in SavingsAccount, but it is defined in the superclass, BankAccount. Thus, what is invoked is BankAccount's transfer method.

But there's something even more interesting going on in this call. The first formal parameter to transfer—other—is declared to be a reference to BankAccount. But when we look at the corresponding actual parameter, it is harrysChecking, which is a reference to CheckingAccount. This is OK, because of what is called the subclass principle:

Any variable that is declared to be a reference to an object of a superclass may actually reference an object of a subclass.

This principle applies as well to the variable this within non-static methods.

In fact, we've been using the subclass principle already. When we called momsSavings.deposit, the deposit method expected this to be a reference to a BankAccount object, but it was actually a reference to a SavingsAccount object—the subclass principle at work!

Let's continue examining the call of transfer. It first calls withdraw on the same object—the one that momsSavings references—on which it was invoked. That part's easy. But then it calls deposit on the object that other references—and that's the CheckingAccount object referenced by harrysChecking. Here's where polymorphism and the related concept of dynamic binding come into play. Although the declaration of deposit says that other is a reference to a BankAccount object, the way that transfer was called, other is actually a reference to a CheckingAccount object. And so it is the deposit method in the CheckingAccount class that is actually invoked.

This example shows the idea of polymorphism and dynamic binding. We have multiple versions of a method, appearing in various places within an inheritance hierarchy. Regardless of what class a method call appears in, which method is actually called depends only on the class of the object it is called on.

The calls to harrysChecking.withdraw are now straightforward: they call the withdraw method of the CheckingAccount class.

Then there are three calls to the static method endOfMonth, and this method is overloaded. Version 1 takes a reference to a SavingsAccount, and version 2 takes a reference to a CheckingAccount. In the first call, the actual parameter is momsSavings, a reference to SavingsAccount, and so the version of endOfMonth actually invoked is version 1. In the second call, the actual parameter is collegeFund, a reference to TimeDepositAccount. We have no overloaded version of endOfMonth that takes a reference to TimeDepositAccount, but version 1 takes a reference to TimeDepositAccount's superclass SavingsAccount. We apply the subclass principle, which says that it's OK to invoke version 1 and substitute a reference to TimeDepositAccount in place of a reference to SavingsAccount. Finally, in the third call, the actual parameter is harrysChecking, a reference to CheckingAccount, and version 2 of endOfMonth is actually invoked.

We conclude by looking at the System.out.println calls. The first one has the actual parameter "Mom's savings. " + momsSavings. Here, the Java compiler calls momsSavings.toString in order to convert momsSavings to a String that it can concatenate with "Mom's savings. ". The only version of toString that we have implemented in this class hierarchy is in BankAccount, and so that is the method invoked. The same holds for all the other implicit calls to toString that occur in the System.out.println calls in this example.

Dynamic binding and overloading

Although dynamic binding and overloading seem similar, there is an important difference between the two concepts. The program AccountTest2.java illustrates the difference. It's the same as AccountTest.java, but with six lines changed: Something seems fishy here, doesn't it? Why is it OK to have momsSavings, collegeFund, and harrysChecking all declared as references to BankAccount and the calls to deposit, transfer, and withdraw work but the calls to endOfMonth require us to cast?

The difference is in how the calls are made. When we call deposit, transfer, or withdraw, the object reference is to the left of the dot, e.g., harrysChecking.withraw(200). When the reference is to the left of the dot, then and only then do we get dynamic binding. In other words, when the reference is to the left of the dot, the decision as to which method is actually called occurs at run time. When we call a non-static method but we don't supply a reference and a dot, then the method is called on this, and we still decide which method is called based on the type of the object that this references.

On the other hand, observe that in the calls to endOfMonth, the object reference is not to the left of the dot. Instead, it's a parameter. In this case, no dynamic binding occurs. The decision as to which method is called is made at compile time, and it is based on how the reference is declared. The decision has nothing to do with what kind of objects the references really refer to! We call this compile-time decision static binding. In AccountTest2.java, momsSavings, collegeFund, and harrysChecking are all declared as references to BankAccount, and there is no version of endOfMonth that takes BankAccount, or any superclass of BankAccount, as a parameter. Thus, we must cast each of these references to the appropriate class so that the compiler can make the proper decision at compile time.