Computer Science II -- Week 8

Introduction

Last week we started looking at inheritance. This week we'll continue talking about inheritance and polymorphism, and introduce interfaces as well.

Note that the links from this page are to handouts that will be distributed the night of class.  Only print out those handouts if you could not attend class.

Main topics this week:

Programming Assignment 2 Executable Due
Programming Assignment 3 Assigned
Quiz
Polymorphism
Dynamic Binding
Deeper Inheritance Hierarchies and Polymorphism
Problem Solving with Polymorphism
Abstract Classes and Methods
Interfaces
Problem Solving with Interfaces
Interface Exercise
Java Inheritance Hierarchy
Next Week

Programming Assignment 2 Executable Due

You must turn in your source code for programming assignment 2 today for full credit.   If you turn it in later than tonight, there will be a 10% penalty.

Programming Assignment 3 Assigned

Programming assignment 3 is assigned this week.  For next week you will need to turn in an inheritance hierarchy design for the assignment.

Quiz

This will be a short quiz asking you to design an inheritance hierarchy based on a problem description.  You may not use your book, notes, or the student manual.  This is an individual activity.

Polymorphism

Last week we looked at using inheritance to create a Square class by extending a Rectangle class.  We needed to override the setWidth and setHeight methods on the Rectangle class to cause the Square class to behave appropriately (the width and height of a square should always be the same).

Inheritance is powerful as a means of code reuse, but that is not all that is possible with inheritance.  Polymorphism is a powerful concept that allows us to write very general code that is easy to modify.  The mechanism that makes polymorphism poossible in Java is this:

An object reference to a base class can actually point to an instance of a derived class.

This means that the following code is legal in Java:

Rectangle r = new Square ();

The object reference r is supposed to point to instances of Rectangle.  But because Rectangle is a base class, the reference r can also point to any class that is derived from Rectangle. 

How does this help us write general code?  Consider our shape drawing program.   To allow the user to draw Rectangles, we would need to remember all the Rectangles the user had drawn, so we would probably have an array of Rectangles.  If we wanted to add Squares, we would have to add another array of Squares, and duplicate any code that dealt with the array of Rectangles.  For example, a method to draw all the Rectangles:

public static void draw (Rectangle [] array)
{
  for (int i = 0; i < array.length; i++)
    array [i].draw ();
}

would need duplicated and modified to handle Squares. 

Polymorphism allows us to avoid this sort of duplication.  Since an object reference to a Rectangle can also point to a Square, we can put Squares into our Rectangle array.  So the same method that deals with drawing Rectangles can draw Squares.   This means that we are writing our code to deal with the general case of the base class.  When we add more derived classes, most of the code does not have to change.   The only code that needs to change when we add more derived classes is the code that creates the derived class in the first place.

So if we have an array of Rectangles, but some of the array elements contain Squares, and we call our draw method above, what happens?  You can see from the code that the draw method is called for each element of the array.  But what if the Square class had overridden the draw method from Rectangle?  Would the Rectangle draw method get called or would the Square draw method get called? 

The answer is that Java figures out which type of object is really being pointed to, and calls the draw method on that object.  This is the essence of polymorphism: we call a method on what we think is a base class, but the method call might do something different from what we expect if it is overridden in a derived class. 

Dynamic Binding

How does Java figure out which method to call?  Consider the following code:

Rectangle r = new Square ();

someFunction (r);

where someFunction looks like:

public static void someFunction (Rectangle r)
{
  r.draw ();
}

How does Java know what method to call?  We said that if Square overrode the Rectangle draw method, the Square draw method would be called.  But when does Java know this?  At compile-time, all Java knows is that the draw method is being called through an object reference to Rectangle.  But at compile-time, Java doesn't know if the object being pointed to is a Rectangle or a Square.  So Java has to wait until the program is running to know which method to call. 

This is called dynamic binding, or run-time binding, because Java cannot figure out which method to call until the program is running. 

Deeper Inheritance Hierarchies and Polymorphism

So far we've looked at polymorphism with a single base class and a single derived class.  But what if we have a deep inheritance hierarchy (e.g. Square derives from Rectangle which derives from Shape).  If we have the following code:

Shape s = new Square ();

s.draw ();

which draw method is called?  There is an algorithm that will show you which draw method will get called.  If you draw the inheritance hierarchy with the base class at the top and the derived class at the bottom, you can start at the bottom most derived class. 

current = bottommost derived class

while (current does not have a draw method)
    current = base class of parent

call current.draw ()

Eventually a draw method will be found, and that one used.  The important part is that it starts at the derived class and works its way up trying to find a matching draw method.

Problem Solving with Polymorphism

We'll review the student manual reading on problem solving with polymorphism

Abstract Classes and Methods

Sometimes you want a base class but you don't know enough to be able to write the implementation for the methods.  Consider our drawing program.  If we wanted to be able to draw circles and triangles, clearly Rectangle is not a good base class.   So we might have a base class named Shape.  Shape would contain all the methods that are in common with the derived classes, like the draw method.  But, a Shape cannot draw itself...the Shape class doesn't know enough to be able to draw itself (is it a square, triangle, or what?  The Shape class doesn't know). 

So we can use the abstract keyword to tell Java that we want a method, but we don't know enough to write the code for it.  For example:

public abstract Shape
{
  private double x;

  public void setX (double v)
  {
    x = v;
  }

  public double getX ()
  {
    return x;
  }

  public abstract void draw ();
}

Note that we declare the draw method abstract because we do not know enough to write the code for it.  All Shapes have an x coordinate, though, so we do know enough to write the code for the setX and getX methods. 

If we declare a method as abstract, we must also declare the class as abstract.   Failure to do so will result in a compile error from Java. 

Since an abstract class does not have some of its methods defined, we cannot create instances of the abstract class.  The following code will give a compile error in Java:

Shape s = new Shape ();

because we are trying to create an instance of an abstract class. 

Interfaces

Inheritance in Java only allows a derived class to have one base class.   Sometimes, though, the problem makes it look like two base classes would be useful.   For example, consider designing an inheritance hiearchy for dogs and cats.   They are both pets, so a good base class might be Pet.  But they are also both mammals...but not all pets are mammals (some people have lizards as pets).  So we cannot make Mammal a base class of Pet.  But dog and cat can only have one base class. 

Java solves this problem with interfaces.  An interface is a set of public methods that a class must implement.  But, like an abstract class, there is no implementation for those methods.  An abstract class could have implementations for some of the methods, but an interface has implementations for none of the methods. 

So an interface just says what methods a class must implement in order to be considered an instance of the interface.  Maybe to be a mammal, the object must be able to age and give birth.  So our Mammal interface might be:

public interface Mammal
{
  public void age ();
  public Mammal giveBirth ();
}

We say that a class that implements these methods implements the interface.  That is done by using the implements keyword.

public class Dog extends Pet implements Mammal
{
}

So Dog's base class it Pet, but it also implements the methods defined in the Mammal interface.  The interesting thing about interfaces is that the name of the interface can be used as an object reference.

Mammal m = new Dog ();

Even though Dog's base class is Pet, we can still use a reference to Mammal to refer to an instance of the Dog class.  A Mammal reference can point to any class that implements the Mammal interface.  This is quite similar to having Mammal be a base class, but we do not get any code reuse.

Interfaces can also contain data that is public, static, and final.  For example:

public interface Mammal
{
  public static final boolean WarmBlooded = true;

  public void age ();
  public Mammal giveBirth ();
}

This allows you to create constants that are designed for use with that interface.   A class that implements the interface inherits the constants.  A class that does not implement the interface can still use the constants by specifying the interface name.  For example:

System.out.println ("WarmBlooded: " + Mammal.WarmBlooded);

A class that implements an interface must implement all the methods of the interface.

Problem Solving with Interfaces

We'll review the student manual reading on problem solving with interfaces.

Interface Exercise

I will pass out a problem description, and you will design an inheritance hierarchy for the problem.  You will also have to design interfaces for the problem.  This will be a group exercise.

Java Inheritance Hierarchy

Now that you know about inheritance and polymorphism, you're ready to look at how all Java classes are related.  Remember that you can use things like the equals method on any class, even if you don't write the method.  If you don't write the method, Java gives you a default implementation.  But where does the default implementation come from?

The answer is that if you do not specifically give a Java class a base class, then it inherits from Object.  Object is a class in Java that all other Java classes inherit from.  For example:

public class Foo
{
  private int myData = 0;
}

We did not use the extends keyword for Foo, so it does not have a specific base class.   That means that Java will assume that we want to extend the Object class. 

Since a derived class inherits all the methods from its base class, this means that Foo contains all the methods that are available in the Object class.  One of those methods is the equals method.  That's where the default implementation of equals comes from.  The default implementation of equals does exactly the same thing as using ==.  If you want the equals method to do something different, you must override it yourself.  For example, for the Foo class, we might override the equals method like this:

public boolean equals (Object obj)
{
  if (this == obj)
    return true;

  if (obj == null)
    return false;

  if (! (obj instanceof Foo))
    return false;

  return myData == ((Foo) obj).myData;
}

Let's look at this line by line.  The purpose of the method is to return true if two instances of an object actually refer to the same object.  In the case of the Foo class, we say that two instance are equal if their myData values are equal. 

The first if statement checks to see if the two object references are in fact both pointing to the same instance.  If so, we do not need to go any farther, because an instance is always equal to itself. 

The second if statement checks to see if the reference passed in is null.  If so, it cannot be equal.

The third if statement asks if the object passed in is of type Foo.  If the object passed in is not of type Foo (say it is of type String), then the two objects cannot be equal, because one of them is definitely a Foo.

Once we know that we have two different instances of the Foo class, the final statment compares their data members to see if they are equal.

This might look confusing, but remember that you will can use this equals method with only minor modifications in your own classes.

This idea of every Java class being inherited from Object will become important next week when we talk about container classes and linked lists.

Next Week

Next week we will talk about container classes in Java and the linked list data structure.  Be sure to read the materials before class.