Lab 9: Collections, Interfaces and Abstract Classes

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 ArrayList!

To get started, pull the code for Lab 9 and create a new IntelliJ project for 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.

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

Animal hierarchy

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, how do Animals eat, or sleep, or make noise? 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 because it is the broadest descriptor for all of these classes. 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 which contains only the method header, no implementation, and must be overridden by the extending class. In this way, Java allows us to enforce the provision of a class (such as Animal from our example) without supplying any details about how that class will work; those details are supplied in the extending class (such as Lion or Wolf).

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

public abstract class Animal {
    ...
}

An abstract method is declared by adding abstract to the method header and ending the declaration with a semicolon. Notice that no implementation of the method is provided!

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 at least one 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, among others. Whereas Integer is a wrapper class for Java's int primitive, BigInteger represents an arbitrarily long integer. 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). From a design point of view this makes sense as the underlying implementations of Integer and BigInteger (since they both serve different purposes) and thus performing actions such as intValue() will also differ.

Abstract Dates

As an example, Date.java is an abstract class to represent calendar dates (we will ignore leap years), 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 new date that is the result of advancing this date by one day. It should not change this date. Then modify the other two classes accordingly so that they follow their respective conventions for dates. Make sure to test out your methods to be sure that they behave as you expect them to!

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 default methods must be explicitly declared as such), 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<? super E> action)

The first two are abstract methods while the last two are default methods which will have their own implementations. Also, the last of these uses a new feature in Java8 that we will discuss in a later lab.

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 mattered is what it could do. For the purposes of that class, it might have been important that this computer could:

This is the fundamental idea of interfaces (and polymorphism in a broader sense) 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 technical 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 definition found on Google
        }
        ...
    }

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

You want 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 we specify wordKnower as belonging to? We could make the ? a Computer, but then we couldn't look the word up in a Dictionary (which isn't true). We could make the ? a Dictionary, but the same problem would occur. We could replace ? with Object and be able to pass either in, but then the compiler would complain because, generally speaking, an Object doesn't have a lookUpDefinition method since not all Objects are able to look up definitions.

Before we might have fixed this problem by making one a subclass of the other, but that doesn't make sense 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. Often when working on a group project, a good approach is to split the work into parts that will be integrated together at the end. In order to allow work to be done in parallel, it is important to establish what each part will accomplish and how it will interact with other parts so that they can be merged together without issue. Establishing what each of these parts will do and how they interact with other parts is essentially treating each part 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 multiple items at once is going to fulfill 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 in Java 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 List, which you've encountered, Set, Stack and Queue, which you'll be introduced to in a future lab.

The Set Interface

SetMarbles

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 fulfill the requirement of being a Set.

The List Interface

SequenceBunnies

Lists differ from sets in that elements have positions within 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 collection interfaces. Read all three files so you can understand how interfaces and inheritance 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. It maintains uniqueness of elements in the set by storing a boolean array contains. Your job is to complete and test the BooleanSet class. This version of the SimpleSet interface only deals with positive integers and uses a boolean array to keep track of what values are currently in the Set. Check the example below:

SetBooleanArray

E. FixedSizeList Class

Main Idea

Now consider a class to represent a List of integers, both positive and negative. Using an array gives a reasonable implementation of a list, but unlike the arrays in Python, Java arrays cannot grow or shrink in size. We will need to start out with as much room as we think we will need. 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 are initially filled with zeros. Consequently, 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 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.

IntSequence

Exercise: FixedSizeList constructor

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

Exercise: Simple FixedSizeList methods

Fill out the following three methods to the FixedSizeList class:

/** Returns true if the list is empty, else false. */
public boolean isEmpty()

/** Returns the number of items in the list. */
public int size()

/** Returns the integer stored at the i-th index in the list. */
public int get(int i)

Note: There is a distinction between size and capacity.

Note: If someone asks to get an index that does not exist, you should throw a ListException with an informative error message. We've provided a 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!

Exercise: FixedSizeList::add method

Fix the two-argument add method so that it works properly. Also fill out the one-argument add method which adds the item to the end of the list.

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

Exercise: FixedSizeList::contains method

Fill out the FixedSizeList's' contains method.

Exercise: 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 covered four key points in this lab: inheritance, polymorphism, abstract classes, and interfaces. Here are some suggestions for further exploration.

Submission and Checklist

Here's a quick summary of what you need to do for this lab:

Make sure to submit the three date files, BooleanSet.java, FixedSizeList.java, and ResizableList.java