Start Concurrent: A Gentle Introduction to Concurrent Programming

17. Polymorphism

…how strange it is to be anything at all.

— Neutral Milk Hotel

17.1. Problem: Banking account with a vengeance

In Chapter 14, we introduced the SynchronizedAccount class that guarantees that checking the balance, making deposits, and making withdrawals will all be safe even in a multi-threaded environment. Unfortunately, SynchronizedAccount provides few of the options a full bank account should have. The problem we present to you now is to create an entire line of bank accounts which all inherit from SynchronizedAccount. Because of inheritance, all accounts will at least have getBalance(), deposit(), and withdraw() methods.

You must create three new account classes. The constructor for each class must take a String which gives the name of the person opening the account and a double which gives the starting balance of the account. The first of these classes is CheckingAccount. The rules for the checking account implemented by this class are simply that the customer is charged $10 every month that the account is open. The second class is DirectDepositAccount. This account is very similar to the basic checking account except that an additional method directDeposit() has been added. On its own, directDeposit() appears to operate like deposit(); however, if a direct deposit has been made in the last month, no service fee will be charged to the account.

The SavingsAccount class operates somewhat differently. In addition to a name and a starting balance, the constructor for a SavingsAccount takes a double which gives the annual interest rate the account earns. Each month the balance is checked. If the balance of the account is greater than $0, the account earns interest corresponding to 1/12 of the annual rate. However, if the balance is below $1,000, a $25 service fee is charged each month, regardless of how low the balance becomes.

In Chapter 11 you were exposed to concepts surrounding inheritance in object-oriented programming. We now return to these concepts and explore them further. In the first place, concurrency is on the table now, and you must be careful to keep your derived classes thread safe. In the second, we’ll discuss the full breadth of inheritance. The tools we describe here are intended to allow you to solve this extended bank account problem (and indeed many other problems) with as little code as possible.

17.2. Concepts: Polymorphism

Perhaps the most important reason for inheritance is code reuse. When you can successfully reuse existing code, you’re not just saving the time of writing new code. You’re also leveraging the quality and correctness of the existing code. For example, when you create your own class which extends Thread, you’re confident that all the thread mechanisms work properly.

You can reuse code by taking a class that does something you like, say the Racecar class, and enhance it in some way, perhaps so that it becomes the TurboRacecar class. If you use the TurboRacecar class on its own, your code reuse is through simple inheritance. If you use TurboRacecar objects with a RaceTrack class, which was written to take Racecar objects as input, you’ve entered the realm of polymorphism. Polymorphism means that the same method can be used on different types of objects without being rewritten. In Java, polymorphism works by allowing the programmer to use a child class in any place where a parent class could have been used.

17.2.1. The is-a relationship

Consider the two following class definitions.

public class Racecar {
    public double getTopSpeed() { return 200.0; }   
    public int getHorsepower() { return 700; }
    public double speed = 0;
}

public class TurboRacecar extends Racecar {
    public int getHorsepower() { return 1100; }
}

Now, imagine that a RaceTrack has an addCar(Racecar car) method which adds a Racecar to the list of cars on the track. When the cars begin racing, the RaceTrack object will query the cars to see how much horsepower they have. A Racecar object will return 700 when getHorsepower() is called, but a TurboRacecar will return 1100.

Even through the TurboRacecar doesn’t have an explicit getTopSpeed() method, it inherits one from Racecar. Like all derived classes in Java, TurboRacecar has all the methods and fields that Racecar does. This relationship is called an is-a relationship because every TurboRacecar is a Racecar in the sense that you can use a TurboRacecar whenever a Racecar is required.

17.2.2. Dynamic binding

There’s a little bit of magic that makes polymorphism work. When you compile your code, the RaceTrack doesn’t know which getHorsePower() method will eventually get called. Only at run time does it query the object in question and, if it’s a TurboRacecar, use the overridden method that returns 1100. This feature of Java is called dynamic binding. Not every object oriented programming language supports dynamic binding. C++ actually allows the programmer to specify whether or not a method is dynamically bound.

Only methods are dynamically bound in Java. Fields are statically bound. Consider the following re-definitions of Racecar and TurboRacecar.

public class StaticRacecar {
    public static final double TOP_SPEED = 200.0;   
    public static final int HORSEPOWER = 700;
    public double speed = 0;
}

public class StaticTurboRacecar extends StaticRacecar {
    public static final int HORSEPOWER = 1100;
}

Assume that RaceTrack contains a method which prints out the horsepower of a StaticRacecar like so:

public void printHorsepower(StaticRacecar car) {
    System.out.print(car.HORSEPOWER);
}

Even if you pass an object of type StaticTurboRacecar to the printHorsepower() method, the value 700 will be printed out every time. In Java, all fields, whether normal, static, or final are statically bound, meaning that the variable type determines which field will be used at compile time. In contrast, dynamic binding means that the true type of the object (not the reference variable pointing to it) determines the method that will be called at run time. Dynamic binding applies only to regular instance methods. As their name implies, static methods are statically bound, determined at compile time by reference type.

Exercise 17.1
Exercise 17.2

17.2.3. General vs. specific

Another way to look at inheritance is as a statement of specialization and generalization. A TurboRacecar is a specific kind of Racecar while Racecar is a general category that TurboRacecar belongs to.

The rules of Java say that you can always use a more specific version of a class than you need but never a more general one. You can use a TurboRacecar any time you need a Racecar but never use a Racecar when you need a TurboRacecar. A square will do the job of a rectangle, but a rectangle will not always be suitable when a square is needed.

Consider the following two classes:

public class Vehicle {
	public void travel(String destination) {
		System.out.println("Traveling to " + destination + "!");
	}
}

public class RocketShip extends Vehicle {
	public void blastOff() {
		System.out.println("10, 9, 8, 7, 6, 5, 4, 3, 2, 1 *ROAR*");
	}
}

Here’s a method that requires a RocketShip but only uses its travel() method.

public void takeVacation(RocketShip ship, String destination) {
    ship.travel(destination);
}

It seems as though we should be able to pass any Vehicle to the takeVacation() method because the only method in ship used by takeVacation() is travel(). However, the programmer specified that the parameter should be a RocketShip, and Java plays it safe. Just because it looks like there won’t be a problem, Java isn’t going to take any chances on passing an overly general Vehicle when a RocketShip is required. If Java took chances, a problem could arise if the takeVacation() method was overridden by a method that did call ship.blastOff().

In summary, you can pass a RocketShip to a method which takes a Vehicle or store a RocketShip into an array of Vehicles, but not the reverse. Java usually gives a compile time error if you try to put something too general into a location that’s too specific, but there are some situations which are so tricky that Java doesn’t catch the error until run time. Arrays, specifically, can cause problems. Examine the following code snippet.

Vehicle[] transportation = new RocketShip[100];
transportation[0] = new Vehicle();

On the first line, we’re using a Vehicle array reference to store an array of 100 RocketShip references. But, in the second line, we try to store a Vehicle into an array that’s really a RocketShip array, even though it looks to the compiler like a Vehicle array. Doing so will compile but throw an ArrayStoreException at run time.

17.3. Syntax: Inheritance tools in Java

So far, we’ve described polymorphism in Java with a conceptual focus. In our previous examples, the only language tool needed to use polymorphism was the extends keyword which you’re now well familiar with. There are a number of other tools designed to help you structure class hierarchies and enforce design decisions.

17.3.1. Abstract classes and methods

One such tool is abstract classes. An abstract class is one which can never be instantiated. In order to use an abstract class, it’s necessary to make a child class from it. To create an abstract class, you simply add the abstract keyword to its definition, as in the following example.

public abstract class Useless {
    protected int variable;
    
    public Useless(int input) {
        variable = input;
    }
    
    public void print() {
        System.out.println(variable);
    }
}

This class is useless for a number of reasons. For one thing, there’s no way to find out the value of variable except by printing it out. Furthermore, there’s no way to change the value of variable after the object’s been created. Finally, since an abstract class can’t be instantiated, the following code snippet will not compile.

Useless thing = new Useless(14);

Instead, we must create a new class that extends Useless.

public class Useful extends Useless {
	public Useful(int value) {
		super(value);
	}
	
    public int getVariable() { return variable; }
    
    public void setVariable(int value) {
        variable = value;
    }
}

Then, we can instantiate an object of type Useful and use it for something.

Useless item = new Useful(14);
item.print();

Note that, in accordance with the rules of Java, we can store an object with the more specific type Useful into a reference with the more general type Useless. Even though Java knows that the object it points to will never actually be a Useless object, it’s perfectly legal to have a Useless reference. You can use abstract classes in this way to provide a base class with some fundamental fields and methods that all other classes in a particular hierarchy need. By using the keyword abstract, you’re marking the class as template for other classes instead of as a class that will be used directly.

Exercise 17.3

Methods can be abstract as well. If you have an abstract class, you can create a method header which describes a method that all non-abstract children classes must implement, as shown below.

public abstract class Sequence {
    protected int number;
    protected final int CONSTANT;
    
    public Sequence(int number, int constant) {
        this.number = number;
        CONSTANT = constant;
    }
    
    public abstract int getNextValue();
}

This abstract class is supposed to be a template for classes which can produce some sequence of numbers. Note that there’s no body for the getNextValue() method. It simply ends with a semicolon. Every non-abstract derived class must implement a getNextValue() method to produce the next number in the sequence. For example, we could implement an arithmetic or a geometric sequence as follows.

public class ArithmeticSequence extends Sequence {
	public ArithmeticSequence(int firstTerm, int difference) {
		super(firstTerm, difference);
	}	
	
    public int getNextValue() {
        number += CONSTANT;
        return number;
    }
}

public class GeometricSequence extends Sequence {
	public GeometricSequence(int firstTerm, int ratio) {
		super(firstTerm, ratio);
	}
	
    public int getNextValue() {
        number *= CONSTANT;
        return number;
    }
}

The Sequence class doesn’t specify how the sequence of numbers should be generated, but any derived class must implement the getNextValue() method in order to compile. By using an abstract class, we don’t have to create a base class which generates a meaningless sequence of numbers just for the sake of establishing the getNextValue() method. Abstract classes are like interfaces in that they can force the programmer who’s extending them to implement particular methods, but unlike interfaces they can also define fields and methods of any kind.

Example 17.1 Bank account abstract class

Here’s a more involved example of an abstract class that gives a first step toward solving the bank account with a vengeance problem posed at the beginning of the chapter.

import java.util.Calendar; (1)

public abstract class BankAccount extends SynchronizedAccount { (2)
    private String name;
    private Calendar lastAccess;
    private int monthsPassed = 0;

1	The first step is to import the `Calendar` class for some date tools we’re going to use later.
2	We extend `SynchronizedAccount` and declare the new class to be abstract. In this example, we don’t use any abstract methods, but since each bank account has unique characteristics, we don’t want people to be able to create a generic `BankAccount`.

    public BankAccount(String name, double balance) throws InterruptedException {
        this.name = name;
        changeBalance(balance);
        lastAccess = Calendar.getInstance();        
    }
    
    public String getName() { return name; }
    
    protected Calendar getLastAccess() { return lastAccess; }
    
    protected int getMonthsPassed() { return monthsPassed; }

The constructor and the accessors should be what you expect to see. Note that calling the static method Calendar.getInstance() is the correct way to get a Calendar object with the current date and time.

    public final double getBalance() throws InterruptedException {      
        update();       
        return super.getBalance();
    }
    
    public final void deposit(double amount) throws InterruptedException {
        update();
        super.deposit(amount);        
    }
    
    public final boolean withdraw(double amount) throws InterruptedException {
        update();       
        return super.withdraw(amount);
    }

Then come the balance checking and changing methods. Each calls its parent method after calling an update() method we discuss below.

    protected synchronized void update() throws InterruptedException {
        Calendar current = Calendar.getInstance();
        int months = 12*(current.get(Calendar.YEAR) -
			lastAccess.get(Calendar.YEAR)) + (current.get(Calendar.MONTH) -
			lastAccess.get(Calendar.MONTH));
        if(months > 0) {
			lastAccess = current;
			monthsPassed = months;
        }
    }
}

Other than adding String for a name associated with the account, the update() method is the other major addition made in BankAccount. Each time update() is called, the number of months since the last access is stored in the field monthsPast and the timestamp of the last access is stored in lastAccess. We didn’t need these time features before, but issues like earning interest or paying monthly service charges will make them necessary. This method is synchronized so that the two fields associated with the last access are updated atomically.

17.3.2. Final classes and methods

If you look at the previous example carefully, you’ll notice that the methods getBalance(), deposit(), and withdraw() were each declared with the keyword final. You’ve seen this keyword used to declare constants before. The meaning that final has for methods is similar to what it means for constants (and almost the opposite of abstract). A method which is declared final can’t be overridden by child classes. If you’re designing a class hierarchy and you want to lock a method into doing a specific thing and never changing, this is the way to do it.

Like abstract, the keyword final can be applied to a class as well. If you want to prevent a class from being extended further, apply the final keyword to its definition. You might not find yourself using this feature of Java very often. It’s primarily useful in situations where a large body of code has been designed to make use of a specific class. Making child classes from that class could cause unexpected problems.

The most common example of a final class is the String class. Consider the following.

public class SuperString extends String {}

This code will give a compiler error. String is perfect the way it is (or so the Java designers have decided). Use of the final keyword for classes, methods, and especially to specify constants allows the compiler to do performance optimizations that would otherwise be impossible.

17.3.3. Casting

Polymorphism gives us greater power and flexibility when writing code. For example, we can make a Vehicle array and store child class objects of Vehicle inside, like so.

Vehicle[] vehicles = new Vehicle[5];
vehicles[0] = new Skateboard();
vehicles[1] = new RocketShip();
vehicles[2] = new SteamBoat();
vehicles[3] = new Car();
vehicles[4] = new Skateboard;

This process could be infinitely more complex. We could be reading data out of a file and dynamically creating different kinds of Vehicle objects, but the final product of an array of Vehicle objects is the important thing. Now, we can run through the array with a loop and have the code magically work for each kind of Vehicle.

for(int i = 0; i < vehicles.length; i++)
    vehicles[i].travel("Prague");

Each Vehicle will travel to Prague as it should. The only trouble is that we’ve hidden some information from the compiler. We know that vehicles[1] is a RocketShip, but we can’t treat it like one.

vehicles[1].blastOff();

This code won’t compile.

RocketShip ship = vehicles[1];

This code won’t compile either. In both cases, we must use an explicit cast to tell the compiler that the object really is a RocketShip.

((RocketShip)vehicles[1]).blastOff();
RocketShip ship = (RocketShip)vehicles[1];

Now, both lines of code work. The compiler is always conservative. It never makes guesses about the type of something. Consider the following.

Vehicle ship = new RocketShip();
ship.blastOff();

Even though ship must be a RocketShip, Java doesn’t assume that it is. The compiler uses the reference type Vehicle to do the check and will refuse to compile. Casting allows us to use our human insights to overcome the shortsightedness of the compiler. Unfortunately, there’s no guarantee that human insights are correct. What happens if you cast improperly?

Vehicle vehicle = new Skateboard();
RocketShip ship = (RocketShip)vehicle;
ship.blastOff();

In this example, we’re trying to cast a Skateboard into a RocketShip. At compile time, no errors will be found. Because we use explicit casting, the compiler assumes that we, powerful human beings that we are, know what we’re doing. The error will happen at run time while executing the second line. Java will try to cast vehicle into a RocketShip, fail, and throw a ClassCastException.

Java provides some additional tools to make casting easier. One of these is the instanceof keyword which can be used to test if an object is an instance of a particular class (or one of its derived classes). For example, we can make an object execute a special command if we know that the object is capable of it.

public void visitDenver(Vehicle vehicle) {
    if(vehicle instanceof RocketShip)
        ((RocketShip)vehicle).blastOff();
    vehicle.travel("Denver");
}

Even inside this if statement where it must be the case that vehicle is a RocketShip, we still must perform an explicit cast. Sometimes instanceof is not precise enough. If you must be sure that the object in question is a particular class and not just one of its child classes, you can use the getClass() method on any object and compare it to the static class object. Using this tool, we can rewrite the former example to be more specific.

public void visitDenver(Vehicle vehicle) {
    if(vehicle.getClass() ==  RocketShip.class)
        ((RocketShip)vehicle).blastOff();
    vehicle.travel("Denver");
}

This version of the code will only call blastOff() for objects of class RocketShip and not for objects of a child class like FusionPoweredRocketShip.

Exercise 17.6

17.3.4. Inheritance and exceptions

Beyond ClassCastException, there are a few other issues that come up when combining exceptions with inheritance. As you already know, an exception handler for a parent class will work for a child class. As such, when using multiple exception handlers, it’s necessary to order them from most specific to most general in terms of class hierarchy.

However, there’s another subtle rule that’s necessary to keep polymorphism functioning smoothly. Let’s consider a Fruit class with an eat() method that throws an UnripeFruitException.

public class Fruit {
    public void eat() throws UnripeFruitException {
        ...
    }
}

Almost any fruit can be unripe, and it can be unpleasant to try to eat such a fruit. But there are other things that can go wrong when eating fruit. Consider the Plum class derived from Fruit.

public class Plum extends Fruit {
    public void eat() throws UnripeFruitException, ChokingOnPitException {
        ...
    }
}

In the Plum class, the eat() method has been overridden to tackle the special ways that eating a plum is different from eating fruit in general. When eating a plum, you can make a mistake and try to swallow the pit, throwing, it seems, a ChokingOnPitException. This scenario seems natural, but it’s not allowed in Java.

The principle behind polymorphism is that a more specialized version of something can always be used in place of a more general version. Indeed, if you use a Plum in place of a Fruit, calling the eat() method is no problem. The problem only happens if a ChokingOnPitException is thrown. Code that was designed for Fruit objects knows nothing about a ChokingOnPitException, so there’s no way for such code to catch the exception and deal with the situation.

There’s nothing wrong with throwing exceptions on overridden methods. The rule is that the overriding method must throw a subset of the exceptions that the overridden method throws. This subset doesn’t need to be a proper subset, so it could be all, some, or none of the exceptions thrown by the overridden method. This rule demonstrates a concept called Hoare’s rule of consequence that pops up many times in programming language design. Essentially, if you start with something that works, you can tighten the requirements on the input (using a Plum instead of any Fruit) and loosen the requirements on the output (throwing fewer exceptions than were originally thrown), and it will still work.

Exercise 17.7

Example 17.2 More human than human

Here we have a few additional examples in a somewhat larger class hierarchy.

Figure 17.1 Animal class hierarchy.

public abstract class Animal {
    private boolean alive = true;
    private boolean happy = true;
    private final boolean warmBlooded;
    
    public Animal(boolean warmBlooded) {      
        this.warmBlooded = warmBlooded;
    }   
        
    public boolean isHappy() { return happy; }  
    
    public void setHappy(boolean value) { happy = value; }        
    
    public boolean isAlive() { return alive; }  
    
    public void die() { alive = false; }    
}

We begin with the abstract Animal class. This class gives a base definition for animals which includes whether the animal is alive, whether the animal is happy, and whether it’s warm-blooded (declared final because an animal can’t switch between warm-blooded and cold-blooded).

public abstract class Mammal extends Animal {
    public static final boolean MALE = false;
    public static final boolean FEMALE = true;
    private boolean gender;
    
    public Mammal(boolean gender) {
        super(true);
        this.gender = gender;
    }
    
    public boolean getGender() { return gender; }   

    public abstract String makeSound();
}

We then extend Animal into Mammal. All mammals are warm-blooded, which is reflected in the constructor call to the base class. In addition, it’s assumed that all mammals make some sound. Mammals generally also have well-defined genders. Like Animal, Mammal is an abstract class, and any non-abstract child of Mammal must implement makeSound().

public class Platypus extends Mammal {
    public Platypus(boolean gender) {
        super(gender);
    }

    public String makeSound() {
        return "Quack!";
    }   
    
    public Egg layEgg() {
        if(getGender() == FEMALE)
            return new Egg();
        else
            return null;
    }
    
    public void poison(Animal victim) {
        if(getGender() == MALE)
            victim.setHappy(false);                           
    }
}

The Platypus class extends Mammal and adds the unusual things that a platypus can do: laying eggs (if female) and poisoning other animals (if male).

public class Human extends Mammal {
    public Human(boolean gender, boolean happy) {
        super(gender);
        setHappy(happy);
    }

    public String makeSound() {
        return "Hello, world.";
    }
}

The Human class also extends Mammal. Depending on the problem being solved, this class might warrant a great deal more specialization. Right now the main addition is taking happiness as an argument to the constructor since the default human state is not necessarily happiness.

public final class DavidBowie extends Human {
    public DavidBowie() {
        super(MALE, true);                
    }

    public String makeSound() {
        return "I always had a repulsive need to be something more than human.";
    }
}

Finally, the DavidBowie class extends Human and is declared a final class because it’s impossible to add anything to David Bowie.

Our examples have stretched fairly long in this chapter. It’s difficult to give strong motivation for some aspects of inheritance and polymorphism without a large class hierarchy. These tools are designed to help organize large bodies of code and should become more useful as the size of the problem you’re working on grows. One of the best examples of the success of inheritance is the Java API itself. The standard Java library is large and depends on inheritance a great deal.

17.4. Solution: Banking account with a vengeance

Now, we return to the specific problem given at the beginning of the chapter and give its solution. We’ve already given you the BankAccount abstract class which provides a lot of structure.

Figure 17.2 Bank account class hierarchy.

Program 17.1 Child class of BankAccount that models a normal checking account.

public class CheckingAccount extends BankAccount {
    public static final double FEE = 10;
    
    public CheckingAccount(String name, double balance)
        throws InterruptedException {
        super(name, balance);             
    }
    
    protected synchronized void update() throws InterruptedException {
        super.update();
        changeBalance(-getFee()*getMonthsPassed());
    }
    
    protected double getFee() { return FEE; }
}

The most basic account is the CheckingAccount. As you recall from the BankingAccount class, the getBalance(), deposit(), and withdraw() methods are all declared final. At first it seems as if there’s no way to change these methods to add the $10 service charge. However, each of those methods calls the update() method first to take care of any bookkeeping. By overriding the update() method, we can easily add the service charge. The new update() method calls the parent update() to calculate the passage of time, then it changes the balance based on the number of months that have passed.

The system we’ve adopted may seem unusual at first. Any time the balance is checked, deposited to, or withdrawn from, we call update(). By updating the account to reflect any months which may have passed before continuing on, we don’t have to write code which periodically updates each bank account. Each bank account is only updated if needed.

We were careful to mark update() as synchronized. Although the chance of an error happening is small, we make the update of the internal Calendar and the application of any fee atomic, just to be safe.

Note that we don’t use the constant FEE directly in update(). Instead, we call the getFee() method. The reason for this decision is due to the next class.

Program 17.2 Child class of CheckingAccount that models the behavior of accounts with direct deposits.

import java.util.Calendar;
public class DirectDepositAccount extends CheckingAccount {
    protected Calendar lastDirectDeposit;
    
    public DirectDepositAccount(String name, double balance)
        throws InterruptedException {
        super(name, balance);
        lastDirectDeposit = Calendar.getInstance();
    }
    
    public double getFee() {        
        Calendar current = Calendar.getInstance();
        int months = 12*(current.get(Calendar.YEAR) -
        lastDirectDeposit.get(Calendar.YEAR)) +
        (current.get(Calendar.MONTH) -
        lastDirectDeposit.get(Calendar.MONTH));
        if(months <= 1)
            return 0;
        else
            return super.getFee();
    }
    
    public void directDeposit(double amount) throws InterruptedException {
        deposit(amount);
        lastDirectDeposit = Calendar.getInstance();
    }
}

The DirectDepositAccount class extends the CheckingAccount class. Note that the update() method hasn’t been overridden. We’ve added another Calendar object to keep track of the last time a direct deposit was made. Then, we override the getFee() method. If there’s been a recent direct deposit, the fee is nothing; otherwise, it returns the fee from the CheckingAccount. Because of dynamic binding, the update() method defined in CheckingAccount will call this overridden getFee() method for DirectDepositAccount objects.

Program 17.3 Child class of BankAccount that models the behavior of a savings account.

public class SavingsAccount extends BankAccount {
    public static final double MINIMUM = 1000;
    public static final double FEE = 25;
    protected final double RATE;

    public SavingsAccount(String name, double balance, double rate)
        throws InterruptedException {
        super(name, balance);
        RATE = rate;        
    }
    
    protected double getFee() { return FEE; }
    
    protected double getMinimum() { return MINIMUM; }
    
    protected synchronized void update() throws InterruptedException {
        super.update(); 
        int months = getMonthsPassed();
        for(int i = 0; i < months; i++) {
            if(getBalance() > 0)
                changeBalance(getBalance() * (1 + RATE/12));
            if(getBalance() < getMinimum())
                changeBalance(-getFee());
        }               
    }
}

There should be few surprises in the last class, SavingsAccount. The biggest difference is that we use a loop in the update() method to update the balance because the account could be gaining interest and also incurring fees. The interaction of the two operations might give a different result than applying each in a block for the backlog of months.

This set of classes might not resemble the way a real, commercial-grade banking application works. Nevertheless, with inheritance and polymorphism we were able to create bank accounts which do some complicated tasks with a relatively small amount of code. At the same time, we preserved thread safety so that these accounts can be used in concurrent environments.

17.5. Concurrency: Atomic libraries

This chapter has discussed using polymorphism to reuse code. To solve the banking account with a vengeance problem from the beginning of the chapter, we explored the process of extending several bank account classes to add additional features while working hard to maintain thread safety.

Code can be reused by extending classes with child classes or by using instances of existing classes as fields. There’s no single solution that’s best for every case. As in the bank account examples, it can be difficult to know when to apply the synchronized keyword to methods.

To lessen the load on the programmer, the Java API provides a library of atomic primitives in the java.util.concurrent.atomic package. These are classes with certain operations guaranteed to execute atomically. For example, the AtomicInteger class encapsulates the functionality of an int variable with atomic accesses. One of its methods is incrementAndGet(), which will atomically increment its internal value by 1 and return the result. Recall from Program 14.1 that even an operation as simple as ++ isn’t atomic. If many different threads try to increment a single variable, some of those increments can get lost, causing the final value to be less than it should be.

Example 17.3 AtomicInteger

We can use the AtomicInteger class to rewrite Program 14.1 so that no race condition occurs.

Program 17.4 Demonstrates the use of AtomicInteger.

import java.util.concurrent.atomic.*;

public class NoRaceCondition extends Thread {       
    private static AtomicInteger counter = new AtomicInteger(); 
    public static final int THREADS = 4;    
    public static final int COUNT = 1000000;        
    
    public static void main(String[] args) {                              
        NoRaceCondition[] threads = new NoRaceCondition[THREADS];           
        for(int i = 0; i < THREADS; i++) {
            threads[i] = new NoRaceCondition();
            threads[i].start();         
        }           
        try {
            for(int i = 0; i < THREADS; i++)
                threads[i].join();
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }           
        System.out.println("Counter:\t" + counter.get());          
    }   
    
    public void run() { 
        for(int i = 0; i < COUNT / THREADS; i++)
            counter.incrementAndGet();
    }
}

This program is identical to Program 14.1, except that the type of counter has been changed from int to AtomicInteger (and an appropriate import has been added). Consequently, the ++ operation was changed to an incrementAndGet() method call, and a get() method call was needed to get the final value. If you run this program, the final answer should always be 1,000,000, no matter what.

Exercise 17.10

The java.util.concurrent.atomic package includes AtomicBoolean and AtomicLong as well as AtomicInteger. Likewise, the AtomicIntegerArray and AtomicLongArray classes are included to perform atomic array accesses. For general purposes, the AtomicReference<V> class provides an atomic way to store a reference to any object. The <V> is a generic type parameter, which will be discussed in Chapter 18.

Although you could use the synchronized keyword to create each one of these classes yourself, the result wouldn’t be as efficient. The atomic classes use a special lock-free mechanism. Unlike the synchronized keyword which forces a thread to acquire a lock on a specific object, lock-free mechanisms are built on a compare-and-swap (CAS) hardware instruction. Thus, incrementing and the handful of other ways to update an atomic variable execute in one step because of special instructions on the CPU. Since there’s no waiting to acquire a lock or fighting over which thread has the lock, the operation is very fast. Many high performance concurrent applications depends on CAS implementations.

Exercise 17.11

17.6. Exercises

Conceptual Problems

Explain the difference between static binding and dynamic binding. In which situations does each apply?

Consider the following two classes.

public class Sale {
    public double discount = 0.25;
    
    public double getDiscount() {
        return discount;
    }
    
    public void setDiscount(double value) {
        discount = value;
    }
}

public class Blowout extends Sale {
    public double discount = 0.5;
    
    public double getDiscount() {
        return discount;
    }
    
    public void setDiscount(double value) {
        discount = value;
    }
}

Given the following snippet of code, what’s the output and why?

Sale sale = new Blowout();
System.out.println(sale.discount);
System.out.println(sale.getDiscount);
Blowout blowout = (Blowout)sale;
System.out.println(blowout.discount);
sale.setDiscount(0.75);
System.out.println(sale.discount);

What are the differences and similarities between abstract classes and interfaces?

Assume that the Corn, Carrot, and Potato classes are all derived from Vegetable. Both Carrot and Potato classes have a peel() method, but Corn does not. Examine the following code and identify which line will cause an error and why.

Vegetable[] vegetables = new Vegetable[30];
for(int i = 0; i < vegetables.length; i += 3) {
    vegetables[i] = new Corn();
    vegetables[i + 1] = new Carrot();
    vegetables[i + 2] = new Potato();
}
int index = vegetables.length - 1;
Potato potato;
while(index >= 0) {
    potato = (Potato)vegetable[index];
    potato.peel();
	index--;
}

How many different structures can the keyword final be applied to in Java, and what does final mean in each case?

Assume that Quicksand is a child class of Danger.

What’s the output of the following code and why?

Quicksand quicksand = new Quicksand();
if(quicksand instanceof Danger) {
	System.out.printf("Run for your lives!");
if(quicksand.getClass() == Danger.class)
	System.out.printf("Run even faster!");
if(quicksand instanceof Quicksand) {
	System.out.printf("The more you struggle, the faster you'll sink!");
if(quicksand.getClass() == Quicksand.class)
	System.out.printf("You'll need to find a vine to escape!");

Consider the following two classes. What’s the problem that prevents compilation?

public class Snake {
	public void handle() throws BiteException {
		System.out.println("You handled a snake!");
		if(Math.random() > 0.9)
			throw new BiteException();
	}
}

public class Cobra extends Snake {
	public void handle() throws BiteException, PoisonException {
		System.out.println("You handled a cobra!");
		if(Math.random() > 0.8) {
			if(Math.random() > 0.2)
				throw new PoisonException();
			throw new BiteException();
		}
	}
}

Programming Practice

Update the solution from Section 11.5 so that it uses as many of the inheritance tools from this chapter as possible. Clearly, the Gate, UnaryOperator, and BinaryOperator classes should be marked abstract. Which methods should be abstract? Which methods or classes should be final?

Implement a program to assess income tax on normal employees, students, and international students using a class hierarchy. Normal employees pay a 6.2% social security tax and a 1.45% Medicare tax every year, but neither kind of student pays these taxes. All three groups pay normal income tax according to the following table.

Marginal Tax Rate	Income Bracket
10%	$0 - $9,700
12%	$9,701 - $39,475
22%	$39,476 - $84,200
24%	$84,201 - $160,725
32%	$160,726 - $204,100
35%	$204,101 - $510,300
37%	$510,301+

Tax is assessed at a given rate for every dollar in the range. For example, if someone makes $35,000, she pays 10% tax on the first $9,700 of her income and 12% on the remaining $25,300. The exception is international students whose country has a treaty with the U.S. so that they don’t have to pay tax on the first $50,000 of income.

Re-implement the original SynchronizedAccount class from Example 14.2 using atomic classes. For simplicity, you can change the balance type from double to AtomicInteger since there’s no AtomicDouble class. How much has this simplified the implementation? Is the readers field still necessary? Why or why not?

Experiments

Take Program 17.4 and increase COUNT to 100000000. Run it several times and time how long it takes to run to completion.

Then, take Program 14.1 and increase its COUNT to 100000000 as well. Change the body of the for loop inside the run() method so that count++; is inside of a synchronized block that uses RaceCondition.class as the lock. (The choice of RaceCondition.class is arbitrary, but it’s an object that all the threads can see.) In this way, the increment will occur atomically, since only the thread that has acquired the RaceCondition.class lock will be able to do the operation. Now, run this modified program several times and time it.

How different are the running times? They might be similar, depending on the implementation of locks and CAS on your OS and hardware platform.