A. Intro

Learning Goals

Today we're going to learn about the more advanced features of Java's inheritance system, namely Abstract Classes and Interfaces. These two constructs allow us to make a more complicated system of class interrelations than we have seen previously, and the correct utilization of both concepts is key to being able to write generalizable and neat code.

Once introduced, we will use these two concepts to explain the workings of the Java Collections Framework, to which many of the Data Structures you have encountered belong. Finally, you'll get some practice making your own version of an ArrayList!

To get started , pull the code for Lab 9 and create a new IntelliJ project out of it.

B. Abstract Classes

Motivation

Consider now the task of using inheritance to organize an already existing group of similar classes. An example is described in chapter 8 of Head First Java; here are the classes.

• Animal, with methods makeNoise, eat, sleep, and roam
• Feline, with method roam
• Canine, with method roam
• Lion, Tiger, Cat, Wolf, and Dog, all with methods makeNoise and eat

The "is a" relationships among these classes suggest the following inheritance structure:

Classes Feline and Canine override Animal's roam method and inherit Animal's makeNoise, eat, and sleep methods, taking advantage of duplication among these classes. Lion, Tiger, Cat, Wolf, and Dog override makeNoise and eat, and inherit the sleep (indirectly from Animal) and roam methods from Feline and Canine.

Now we have a question. How do Animals eat, or sleep, or make noise? Well, it depends on what kind of animal we are instantiating, because they're all different. This suggests that it doesn't make any sense to instantiate an Animal object. But we need to have the Animal class to take advantage of polymorphism. What to do?

Abstract classes

Java provides a feature called an abstract class to handle this problem. An abstract class cannot be instantiated; it can only be extended. It typically contains abstract methods that must be overridden by the extending class. In this way, Java allows us to enforce the provision of a class without supplying any details about how that class will work; those details are supplied in the extending class.

We declare an abstract class by adding the keyword abstract to the class header, e.g.

public abstract class Animal {
    ...
}

We similarly declare an abstract method by adding abstract to the method header, and in addition providing no body for the method (we just end the declaration with a semicolon).

public abstract class Animal {
    ...
    public abstract void eat ( );
    public abstract void sleep ( );
    public abstract void makeNoise ( );
    public abstract void roam ( );
}

An abstract class may include non-abstract methods as well. However, any class that has an abstract method must be an abstract class.

Abstract Classes in Java Libraries

The various Java libraries contain several abstract classes. For example, the class Number in java.lang is the superclass of Integer and BigInteger (arbitrarily long integers), among others. Here's a declaration for Number:

public abstract class Number {

    public byte byteValue ( );  // Returns the value of the specified number as a byte.
    public abstract double doubleValue ( );  // Returns the value of the specified number as a double.
    public abstract float floatValue ( );  // Returns the value of the specified number as a float.
    public abstract int intValue ( );  // Returns the value of the specified number as an int.
    public abstract long longValue ( );  // Returns the value of the specified number as a long.
    public short shortValue ( );  // Returns the value of the specified number as a short.
}

Anything that wants to extend a Number is required to have all of those methods described above, but it can implement them any way that they want (as well as have additional methods).

Abstract Dates

As an example, Date.java is an abstract class to represent calendar dates (in a non-leap year), along with two concrete classes that extend it.

public class FrenchRevolutionaryDate extends Date {

    // In a nonleap year in the French Revolutionary Calendar,
    // the first twelve months have 30 days and month 13 has five days.

    public FrenchRevolutionaryDate (int year, int month, int dayOfMonth) {
        super (year, month, dayOfMonth);
    }

    @Override
    public int dayOfYear ( ) {
        return (month()-1) * 30 + dayOfMonth ( );
    }
}

public class GregorianDate extends Date {

    public static int [ ] monthLengths = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public GregorianDate (int year, int month, int dayOfMonth) {
        super (year, month, dayOfMonth);
    }

    @Override
    public int dayOfYear ( ) {
        int rtnValue = 0;
        for (int m=0; m<month()-1; m++) {
            rtnValue += monthLengths[m];
        }
        return rtnValue + dayOfMonth ( );
    }
}

Exercise: A nextDate Method

Add an abstract method named nextDate to the Date class. nextDate returns the result of advancing this date by one day. It should not change this date. Then modify the other two classes accordingly. Make sure to test out your methods to be sure that they're right!

C. Interfaces

Interfaces

In addition to abstract classes, Java provides a similar construct called an interface. An interface is like an abstract class except it only has public abstract methods and public default methods (similar to an abstract class, but must be explicitly declared), and it cannot have instance variables (except for constants - public static final fields).

For example, the interface named Iterator in java.util names four method headers:

public boolean hasNext ( )
public Object next ( )
default void remove ( )

default void forEachRemaining(Consumer action)

The last of which is a new feature in Java8 that we won't be talking about right now.

A class can implement an interface by supplying definitions for all its methods. In Java, we add the phrase

implements interfaceName

to the class header. For example:

public class IteratorClass implements Iterator {
    ...

    // Return true if there are more elements to be iterated through
    // and false otherwise.
    public boolean hasNext ( ) {
        ...
    }

    // Return the next element in the iteration sequence.
    // Precondition: hasNext ( );
    public Object next ( ) {
        ...
    }

    // Remove the object most recently returned.
    // Precondition: next has been called.
    // (This is an optional method, so the body can be empty.)
    public void remove ( ) {
        ...
    }

    // other methods
}

Why use an interface, if they are more restricted than abstract classes? It turns out that interfaces have an additional advantage: a class can implement multiple interfaces, but it can only extend one class, abstract or not.

For example, the Java Integer class implements both the Serializable and Comparable<Integer> interfaces.

Interfaces can also extend other interfaces by using the extends keyword. This means that the extending interface is inheriting the behavior of the other interface. Interfaces cannot use the implements keyword because only classes can implement interfaces.

Motivation for Interfaces

You've probably been told before that for a certain class in college you need to have a computer. You probably weren't told what kind of computer you had to have, what company it was from, how much RAM it had, even whether it was a Mac or a PC, you were just told you needed "a computer". This is because the specifics of the machine you owned didn't matter, all that matter is what it could do. For the purposes of that class, it might have been important that this computer could:

1) Go on the internet
2) Use a word processor
3) Print things

If it could do those three things, it was good enough. Actually what type of computer it was or what else it could do didn't matter.

This is the fundamental idea of interfaces in Java. Sometimes requiring what an object can do is more important that requiring it be a certain type of object. What follows now is a more techincal example of why interfaces are useful.

Say we have the following two classes:

    public class Computer {
        ...
        public String lookUpDefinition(String wordToLookUp) {
            // Do some stuff and returns a defintion found on Google
        }
        ...
    }

    public class Dictionary {
        ...
        public String lookUpDefinition(String wordToLookUp) {
            // Flip through some pages and return a definition
        }
        ...
    }

Now let's say you wanted to make a class ConfusedStudent, which represents a student who doesn't know what the word 'syzygy' means, and who wants to look it up:

    public class ConfusedStudent {
        ...
        static String whatDoesSyzygyMean (? wordKnower){
            return wordKnower.lookUpDefinition("syzygy");
        }
        ...
    }

Notice that there is a question mark above. What type should I specify wordKnower as belonging to? I could make the ? a Computer, but then I couldn't look the word up in a Dictionary (which isn't true), I could make the ? a Dictionary, but the same problem would occur. I could replace ? with Object and be able to pass either in, but then the compiler would complain because, generally speaking, a Object doesn't have a lookUpDefinition method.

Before we might have fixed this problem by making one a subclass of the other, but that doesn't work here, there really isn't any is-a relationship between Computers and Dictionarys.

Interfaces to the rescue! Let's define an interface:

    public interface thingThatKnowsWords {
        public String lookUpDefinition(String wordToLookUp);
    }

And let us rewrite the three classes above so they look like this:

    public class Computer implements thingThatKnowsWords {
        ...
        public String lookUpDefinition(String wordToLookUp) {
            // Do some stuff and returns a defintion found on Google
        }
        ...
    }

    public class Dictionary implements thingThatKnowsWords {
        ...
        public String lookUpDefinition(String wordToLookUp) {
            // Flip through some pages and return a definition
        }
        ...
    }

    public class ConfusedStudent {
        ...
        static String whatDoesSyzygyMean (thingThatKnowsWords wordKnower){
            return wordKnower.lookUpDefinition("syzygy");
        }
        ...
    }

Our problem is solved! We're allowed to do this, because Java lets us choose an interface as the static type of a method parameter, and this way we can use either a Dictionary or a Computer (since they both implement thingThatKnowsWords)!

Interfaces are a programmer's life

When a class implements an interface, it is giving a guarantee that it can perform a certain functionality, as defined by the interface it implements. You'll find that the idea of an interface is actually very central to software engineering in general. When you're asked to implement a set of methods to perform some specific task, that's implementing an interface. When you try to split up a group project or assignment into separate parts that will work together assuming each person implements their class correctly, and you build off the assumption that your partner(s) classes are already working, you're using these split-up parts as an interface. Using interfaces is all about not knowing the actual implementation, but instead utilizing the input-to-output, defined behavior given by the interface; implementing an interface to specification like you are asked for assignments and projects is about making sure the program you write under some interface gives the correct output for all inputs.

D. Collection Classes

Lets turn now to a very useful example of what we've just been talking about.

Collections

Collection classes represent collections of data. Most of the data structures we will study the rest of this class are used to represent collections. At the most general level, pretty much anything you use to store muliple items at once is going to fufill the requirements to be a collection. The most commonly used collections are sets and lists, but there are many others. The group of all collection classes is organized using interfaces!.

The Collection Interface

At the root of the organization is the Collection interface. This interface specifies methods like isEmpty(), or add(Object o), among many others. All collection classes implement Collection in one way or another. Four important types of collections are the Set and the List, both of which you've encountered, and the Queue and Deque which you'll meet shortly.

The Set Interface

A set is a group of items with no duplicates. The Set interface does not require ordering (e.g. HashSet), but sets can be ordered (TreeSet, ConcurrentSkipListSet). Sets support (at least) the following operations:

1. Initialization (with a constructor)
2. Adding an element to the set if it's not already there
3. Removing an element from the set
4. Checking whether a given item is in the set
5. Checking whether the set is empty

For example, a set of nonnegative integers may be represented as a boolean array with element k being true if k is in the set and false otherwise, but there are many other ways to implement a Set.

It's important to realize that a Set, although a sub-interface of Collection, is itself an interface, and might be defined like this:

    public interface Set extends Collection {
        ...
    }

This is because, as we just mentioned, there are multiple objects, that might work in very different ways, all of which fufill the requirement of being a Set.

The List Interface

Lists differ from sets in that elements have positions within in the List, duplicates are allowed, and all lists are ordered. Thus, they support the following operations:

1. Initialization (with a constructor)
2. Adding an element at a given position or at the end of the list
3. Removing an element at a given position or at the end of the list
4. Checking whether a given item is in the set
5. Identifying the value at a given position in the list
6. Checking whether the list is empty

Implementation of a list normally involves storing the elements of the list explicitly. One might use an array whose 0th element is the first list item, and so forth. Similarly to a Set, a List is an interface that might be defined like this:

    public interface List extends Collection {
        ...
    }

Collection Constructors

There are several ways to initialize instance variables (as detailed in our readings from Head First Java):

1. Using assignments in the main method (chapters 2-4)
2. Using "setter" methods (chapters 4, 5)
3. Using constructors (chapter 9)

In general, the most preferable by far of these ways is the last one. By convention, the constructor of a class initializes the instance variables of the class in such a way that the resulting object is internally consistent and complete.

Exercise: Complete a Set Implementation

If one partner has been coding for the whole lab, switch places.

The file SimpleCollection.java contains a simplified version of the Collection interface which only accepts integers as members. The files SimpleSet.java and SimpleList.java contain simplified versions of the Set and List collections. Read all three files so you can understand how interfaces and inheritence are being used here, as well as to understand what each of the interfaces require.

The file BooleanSet.java is an incomplete implementation of the SimpleSet interface that only allows for positive integers. Your job is to complete and test the BooleanSet class.

This version of the SimpleSet interface uses a boolean array to keep track of what values are in the Set. Check the example below:

E. FixedSizeList Class

Main Idea

Now consider a class to represent a List of an arbitrary number of integers, both positive and negative. An array is a reasonable implementation of the list. However, arrays in Java (unlike lists in Python) cannot grow or shrink in size, so we will need to start out with as much room as we think we will need. Thus, we should choose to start the array with a size greater than zero or one (perhaps something like 20).

However, this creates another concern because arrays of integers begin filled with zeros. Thus, we won't be able to tell the difference between a value zero in our list and a zero that is simply the default value the array was initialized with.

A solution is to store a counter int as an instance variable. The counter will tell us how many elements were placed into the array (i.e. how much of the array contains actually important integers). The rest of the array's contents do not matter. They can be 0 or any other number.

We implement this solution in a class named FixedSizeList. A partially filled example is pictured below. The shaded array cells represent default values. If the code is working correctly, the values in the shaded cells should never be examined.

Exercise: FixedSizeList constructor

Fill in the constructor in the FixedSizeList class to properly intialize all values.

Simple FixedSizeList methods

Fill out the following three methods to the FixedSizeList class:

1. public boolean isEmpty()

returns true when this list is empty and returns false otherwise

1. public int size()

returns the number of values in this list

Note: There is a distinction between size and capacity.

1. public int get(int i)

returns the value at the given position in the list

e.g. If the list contains 3, 1, and 4, get(0) returns 3.

Note: If someone asks to the get an index that does not exist, you should throw an ListException with an informative error message. We've provided an ListException for you. The same is true for any case where a method is called with incorrect input.

Self-test: Buggy add method

We've supplied you with a two-argument add method already, but it has a bug. Discuss the code with your partner until you're both satisfied you understand the bug. If you're having trouble finding it, try writing some tests!

FixedSizeList add

Fix the two-argument add method so that it works properly.

Note: If there is no more open spots in the array throw a ListException with an informative error message.

FixedSizeList contains method

Fill out the FixedSizeList contains method.

FixedSizeList Remove Methods

There are two different remove methods in FixedSizeList, remove (which it implements from SimpleCollection), that removes an integer if it is in the list, and removeIndex (which it implements from SimpleList), which removes whatever integer is at the specified index. Make sure you understand the difference between the two, then implement both.

Hint: If you've already completed removeIndex, and completed a certain helper method, remove can be done very easily.

Once you're done, congrats! You've implemented a simple version of an ArrayList.

F. We can do better

Exercise: A Better List

Recall that when add was called on an FixedSizeList that did not have any space left, the expected behavior was to throw an error. We can do better.

Create a ResizableList class that extends your FixedSizeList class (and therefore implements the SimpleList interface, which therefore implements the SimpleCollection interface ) Override any methods you need to override in ResizableList so that the ResizableList increases its capacity to accommodate for new elements. Additionally, override the constructor (since there no longer is any capacity!).

Make sure you fully understand how you're going to solve this problem before you start coding.

Hint: Resizing a list takes time, and you want to do it as infrequently as possible. A useful rule is to double the size of the list whenever you hit capacity, since this means that the frequency of resizing operations will go to never as the size of the list approaches infinity.

G. Conclusion

Summary

We hit four "high points" in this lab: inheritance, polymorphism, abstract classes, and interfaces. Here are some suggestions for further exploration.

• Why do toString and equals almost always have to be redefined?
• The java.util.Stack supports some methods that are decidedly unrelated to stacks (e.g. contains, get, and insertElementAt). How do we fix it?
• Remember the discussion about Computers and Dictionarys. What if we defined a class that inherited from both Computer and Dictionary (if you could). Then we could avoid the whole interface nonsense altogether! This is called multiple inheritance, and while many languages allow this (Python and C++ for example), Java developers decided this was a bad idea and did not allow it in Java. Why is this? What could go wrong? How does multiple inheritance work in these other languages?

Submission

Submit as lab09:

• Your four date java files
• BooleanSet.java
• ResizableList.java and FixedSizeList.java