A. Intro

Learning Goals

The focus of today's lab is inheritance, a mechanism that allows a class to be defined that differs only slightly from an existing class. Inheritance provides numerous benefits. In particular, programmers can take advantage of already written correct code and avoid reinventing the wheel.

A related concept is polymorphism, where a variable may store values of its subclasses. The procedure for de-tangling an instance of polymorphism can be somewhat complicated, so there are numerous exercises that provide you with practice.

Inheritance can also be used to organize an already existing bunch of similar classes. From this situation emerges the concepts of abstract classes and interfaces. Both provide a way to require that certain methods be included in a given class without specifying how they are implemented. Later, the fully implemented methods can be called "under the table", for example to compare two elements of an array. We think this is neat.

To get started , download the code for Lab 6 and create a new Eclipse project out of it.

B. Inheritance

Review of Inheritance from CS 61A

You learned in CS 61A that a programmer can set up one class to inherit characteristics (methods and instance variables) from another. This is typically done to reuse most of an already-defined class that needs an extra method, or that requires a method to behave slightly differently.

Inheritance Terminology

We will refer to the inheriting class as the subclass of its parent or superclass, and say that the subclass extends the superclass. Methods in the superclass can be redefined in the subclass. This is called overriding the methods.

In Java, we set up inheritance in a class's header, using the keyword extends. You may have noticed examples of its use already this semester; it looks something like this:

public class SubClass extends SuperClass {
    ...
}

or

public class Dog extends Animal {
    ...
}

or

public class Dalmatian extends Dog {
    ...
}

Note: If a class has the keyword final in its header, then it cannot have any subclasses.

Discussion: Review the Lingo

There was a lot of lingo on the last step. Discuss each of the following terms with your partner to make sure you both understand what they mean. Then post a definition of each in your own words to the discussion. Check out your classmates' posts to see if they match your intuition.

• subclass
• superclass
• extends
• overrides

Exercise: Extending the Counter Class

Here's an example of inheritance. Recall the Counter class from earlier in the course. Note: this version is slightly modified from version we used before.

public class Counter {
    int myCount;
    public Counter ( ) {
        myCount = 0;
    }
    public void increment ( ) {
        myCount++;
    }
    public void reset ( ) {
        myCount = 0;
    }
    public int value ( ) {
        return myCount;
    }
}

Let's revisit the example of the mod N counter. Remember before that to create ModNCounter.java we just wrote over the file Counter.java. Another way to set up ModNCounter.java is to have it inherit from Counter.java. Write a new version of ModNCounter.java that uses inheritance. You only have to replace the constructor and one other method; all others should be inherited.

Once you're done, check that you can use all the methods correctly, even ones that you never directly defined in ModNCounter. For instance:

ModNCounter modCounter = new ModNCounter(3);
modCounter.increment();
System.out.println(modCounter.value()); // prints 1
modCounter.reset();
modCounter.increment();
System.out.println(modCounter.value()); // still prints 1

Also check that the mod functionality works.

ModNCounter modCounter = new ModNCounter(3);
modCounter.increment();
modCounter.increment();
modCounter.increment();
modCounter.increment();
System.out.println(modCounter.value()); // prints 1

Exercise: Private Fields and Inheritance

The Counter class we just considered was modified. The original version is below and has a private instance variable myCount. Edit your Counter.java file so that it matches the code seen below.

public class Counter {

    private int myCount;

    public Counter ( ) {
        myCount = 0;
    }

    public void increment ( ) {
        myCount++;
    }

    public void reset ( ) {
        myCount = 0;
    }

    public int value ( ) {
        return myCount;
    }
}

Subclasses do not have access to the private variables of their superclasses. So, actually ModNCounter cannot have access to the private instance variable myCount. This restriction makes sense. A programmer defining a variable as private presumably intends that access to the variable be limited. However, if all you had to do to gain access to a private variable was to define a subclass of the class containing it, it would be easy to subvert the limited access.

(Note: We can use the keyword protected instead of private if we want to allow subclasses to access the variables, but not allow any other classes. However, this is discouraged because of the problem described above. In general, it is good style to make your variables as restricted as possible.)

Modify ModNCounter to work even when Counter's myCount variable is private. Do not create a new myCount variable in ModNCounter, or override any more than the constructor and one method. This may be a bit tricky!

Hint: If a subclass overrides a method from its superclass, it can still call the original method (if it is public) by prefacing the method name with the super keyword.

Exercise: Extending the Point Class

We can extend classes that we haven't written ourselves — such as those in the Java API — provided they aren't declared as final. Here's an example of extending the Point class (which we worked with earlier) from the java.awt library.

Some classes provide "setter" methods. Setter methods allow you to change the values of instance variables, even if they are private (because the method is public). A useful debugging aid is to override a setter method to produce informative output every time the object's state changes.

The setter method for the Point class is named move; the call

p.move (27, 13);

changes the x coordinate to 27 and the y coordinate to 13 in the Point referenced by p. Given below is the framework for a TracedPoint class intended to intercept calls to move and print information about the pre- and post-change state of the Point along with doing the move. You are to complete and test the framework after reading a note about super in the next step.

import java.awt.*;
public class TracedPoint extends Point {

    public TracedPoint (int x, int y) {
        super (x, y);
    }

    // Your move method goes here.

    public static void main (String [ ] args) {
        TracedPoint p1 = new TracedPoint (5, 6);
        p1.move (3, 4); // prints: "point moved from (5,6) to (3,4)
        p1.move (9, 10); // prints: "point moved from (3,4) to (9,10)

        TracedPoint p2 = new TracedPoint (25, 30);
        p2.move (45, 50); // prints: "point moved from (25,30) to (45,50)

        System.out.println ("p1 is " + p1);
        System.out.println ("p2 is " + p2);
    }
}

A Note About the TracedPoint Constructor

When constructing a subclass object, you must always construct its superclass first.

In the constructor of a subclass, Java automatically supplies a call to the superclass constructor with no arguments. For example, If you write a TracedPoint constructor, it will automatically call Point(); before running the first line of the TracedPoint constructor.

If you want to call a constructor of the superclass other than the no-argument constructor, use the super keyword as shown below.

public class TracedPoint extends Point {

    public TracedPoint (int x, int y) {
       super (x, y);
    }

    // ...
}

This calls the two int constructors of Point. The super keyword must be used on the first line of the constructor.

An aside: similar to how you use super, you can also use the keyword this as a constructor. this calls other constructor methods within the same class. For example, if you wanted the zero-argument constructor for TracedPoint to initialize a traced point at (0, 0), you could write:

public TracedPoint(){
    this(0, 0);
}

Reminder: Another way to use super

The super keyword has another use besides for constructors. It also allows you to call superclass methods that the subclass has overriden. Use it similarly to how you would use the this keyword.

this.method(); // calls the method in the current class
super.method(); // calls the method in the parent class

Now implement TracedPoint and take advantage of the superclass's methods and variables as much as possible rather than reinventing the wheel.

C. Static and Dynamic Type

Introduction to Polymorphism

We saw earlier that inheritance provides a way to reuse existing classes (Counter and Point), implementing small changes in behavior by overriding existing methods in the superclass or by adding new methods in the subclass. Inheritance also, however, makes it possible for us to design general data structures and methods using polymorphism.

The word "polymorphism" comes from the Greek words for "many" and "forms". In the context of object-oriented programming, it means that a given object can be regarded either as an instance of its own class, as an instance of its superclass, as an instance of its superclass's superclass, and so on up the hierarchy. In particular, where a given reference type is requested for a method argument or needed for a return type, we can supply instead an instance of any subclass of that reference type. That's because inheritance implements an "is-a" relationship: for example, a TracedPoint is a Point with some extra properties. As an example, imagine you have the following method in some class (not necessarily Point or TracedPoint):

public static void moveTo79 (Point p) {
    p.move (7, 9);
}

We can call moveTo79 and pass in either a Point object or a TracedPoint object. And if we pass in a TracedPoint object, the code will use the move method that you implemented in TracedPoint!

Discussion: Thinking about Polymorphism

Would you expect the substitution mechanism to work in reverse? For example, would the following code work?

public static void anotherMoveTo79 (TracedPoint tp){
    tp.move(7, 9);
}

...

Point p = new Point(3, 4);
anotherMoveTo79(p);

Briefly discuss with your partner why you would expect this to work, or not. Then try it out for yourself and see!

Polymorphic Data Structures

The java.util class library contains several collection classes that take advantage of polymorphism and are therefore able to store a variety of types of objects. We will examine the ArrayList class as an example. It represents an expandable array-like structure. (It's described in chapter 6 of Head First Java.)

To declare an ArrayList reference, specify both the ArrayList class name and also the class of objects that the ArrayList will contain in angle brackets. For example,

ArrayList<String> values;

declares a reference to an ArrayList that contains only String objects. Similarly, to construct an ArrayList object, you need to supply the element class name in angle brackets,

ArrayList<String> values = new ArrayList<String> ( );

What happens if you don't specify the angled brackets?:

ArrayList values = new ArrayList();

It turns out, this is equivalent to ArrayList<Object>.

ArrayList methods include the following.

// Add an object to the end of the ArrayList.
// The return value is always true (and is therefore
// usually ignored) since there aren't any circumstances
// that the add could fail.
boolean add (Object o);

// Return the object at the given position in the ArrayList.
Object get (int index);

// Return the number of elements that have been added
// to the ArrayList; similar to the myCount information in
// the IntSequence class.
int size ( );

// Return true if the ArrayList contains the given object,
// and return false if not.
boolean contains (Object o);

The class Object is the root of the inheritance hierarchy—every class inherits from Object (primitives, however, do not), at least indirectly—so these operations provide a data structure that can store objects of any type.

Here's an example:

ArrayList<Object> a = new ArrayList<Object> ( );
a.add (new TracedPoint (5, 6));
a.add (new Point (10, 11));
a.add ("abcd"); // a String object
IntSequence seq = new IntSequence (3);
seq.add (5);
seq.add (4);
seq.add (3);
a.add (seq);
for (int k=0; k<a.size( ); k++) {
    System.out.println (a.get (k));
}

The output is

TracedPoint[x=5,y=6]
java.awt.Point[x=10,y=11]
abcd
5 4 3

showing that each object's own toString method was used to construct the corresponding output line. Notice it did not use the toString method defined in the Object class.

A Problem

Unfortunately, elements of an ArrayList seem to selectively forget some of their methods. Given the following code,

Point p = new Point (3, 4);
TracedPoint tp = new TracedPoint (5, 6);
ArrayList<Object> a = new ArrayList<Object> ( );
a.add (p);
a.add (tp);
// Move both points to (7, 9).
for (int k=0; k<a.size( ); k++) {
    a.get(k).move (7, 9);
}

the compiler claims that

Cannot resolve symbol
symbol  : method move (int,int)
location: class java.lang.Object
    a.get(k).move (7, 9);

It appears that the Java compiler is looking not at the Point and TracedPoint classes to find the move method, but at the Object class.

A Solution?

Try replacing the line

a.get(k).move (7, 9);

by

Point p2 = a.get(k);
p2.move (7, 9);

First discuss with your partner whether you expect this to work and why. Then try it out.

Polymorphic Method Selection

The Java compiler and runtime system have to resolve two questions that arise when polymorphism is used. The compiler, which wants to catch typing inconsistencies and other possibilities for error, asks whether a method with a given name can be invoked on a given object. Once the compiler has answered "yes" to that question, the runtime system needs to find which of the possible versions of that method is the right one to invoke.

To explore exactly how this works, we have to introduce some new terminology: static type and dynamic type.

Static and Dynamic Type

So far in the class, most of the variable instantiations you've seen have been in a form like

Dog d = new Dog();

where the class name Dog appears twice. Now suppose that Dog extends the class Animal. Because of polymorphism, we are allowed to do something like:

Animal d = new Dog();

This means a variable can have two different types associated with it. The one on the left of the equals sign, Animal, is referred to as the static type of the variable. It is the type that the reference is declared as. The one on the right of the equals sign, Dog, is referred to as the dynamic type of the variable. It is the type of the object that is constructed.

The static type of a variable is allowed to be the same as the dynamic type, or the superclass of the dynamic type (or the superclass's superclass, and so on). However, the static type cannot be a subclass of the dynamic type (as you saw earlier). The static type can also be an interface that the dynamic type implements, which we'll discuss later in the lab.

What the Compiler Does

To determine the legality of a method call such as

p.move(7, 9);

the compiler first examines the static type of p (as opposed to the dynamic type). If the static type of p contains a move method that takes two integers as arguments (or one of its superclasses does), then the statement is legal, and the code is allowed to run. If not, compiler error results. Similarly, for a statement like

a.get(1).move(7,9);

the compiler examines the type of a.get(1), then searches for a move method either in the corresponding class or one of its superclasses. According to the online documentation for ArrayList, the get method returns an Object, and this is what the compiler sees as the static type. Objects don't have a move method; thus we get the error message we saw earlier.

We just considered an alternate approach:

Point p = a.get(1);
p.move(7,9);

The statement p.move(7,9); would work fine; p is a reference of type Point, and the Point class has a move method. The compiler's complaint arises from the assignment statement; it objects to the attempt to take a reference to an Object and store it in a Point reference. Since almost all Objects are not Points, hopefully it makes sense that the compiler won't allow this. What would happen if the ArrayList stored an object other than a Point at position 1?

We, however, are smarter than the Java compiler. If we know that we have only inserted Points and TracedPoints into the ArrayList, we know that they have move methods. We communicate this information to the compiler by a type cast, putting a class name in parentheses immediately preceding a reference or reference expression. A type cast temporarily changes the static type of a variable, and tells the compiler to trust us the programmer that it will work.

Here's how we would successfully call the move methods of the array list elements.

for (int k=0; k<a.size( ); k++) {
    ((Point) a.get(k)).move (7, 9);
}

All the compiler knows is that a.get(k) returns a reference to an Object. The cast temporarily changes the static type, causing the reference to be interpreted as a Point, which allows the compiler to find a move method.

What Happens at Run Time

Once the compiler is satisfied that a move method is available for an object, the runtime system then selects the most specialized move method to call based on the dynamic type. For an object with dynamic type Point, it uses the Point move method. For an object with dynamic type TracedPoint, it uses the TracedPoint move method.

We just considered the code

ArrayList<Object> a = new ArrayList<Object> ( );
a.add (new TracedPoint (5, 6));
a.add (new Point (10, 11));
a.add ("abcd"); // a String object
IntSequence seq = new IntSequence (3);
seq.add (5);
seq.add (4);
seq.add (3);
a.add (seq);
for (int k=0; k<a.size( ); k++) {
    System.out.println (a.get (k));
}

Remember this used the toString methods defined in TracedPoint, Point, String, and IntSequence. Why did this work? The compiler was satisfied, because even though all of the a.get(k) have static type Object, the Object class does define a toString method. Then the runtime system looked at the dynamic type of the different a.get(k), which were TracedPoint, Point, String, and IntSequence, and used the toString method it found there.

A mantra to help understand this: an object always remembers how it was constructed, and chooses a method from the class of which it is an instance.

Two caveats:

• If you're trying to call a static method, only the static type is used
• The method used at runtime must be a direct override of the method found at static time. It cannot be an overload. This means the method signature must match exactly (both the name of the method and argument list must match).

Self-test: Identify Static Types

Point p;

What is the static type of p?

Suppose you define the following method inside the TracedPoint class:

public static void printPoint (Point p){
    System.out.println(p)
}

Then you run the following code

TracedPoint tp = new TracedPoint(2, 3);
printPoint(tp);

What is the static type of the variable inside the method printPoint?

Suppose you define the following method inside the TracedPoint class.

public void printX(){
    System.out.println(this.x);
}

What is the static type of this inside the method?

Suppose you have the following code snippet:

ArrayList<Point> points = new ArrayList<Point>();
points.add(new TracedPoint(1, 2));

What is the static type of points.get(0)?

What is the static type of (TracedPoint)(points.get(0))?

Self-test: Polymorphism Puzzles

Consider the class definitions below.

public class Superclass {

    public void print ( ) {
        System.out.println ("super");
    }
}

public class Subclass extends Superclass {

    public void print ( ) {
        System.out.println ("sub");
    }
}

Now determine whether the following program segment prints "super", prints "sub", results in a compile-time error, or results in a run-time error.

Superclass obj1 = new Subclass ( );
obj1.print ( );

Choose one answer.

Do the same for the following program segment.

Subclass obj2 = new Superclass ( );
obj2.print ( );

Choose one answer.

Do the same for the following.

Superclass obj3 = new Superclass ( );
((Subclass) obj3).print ( );

Choose one answer.

Do the same for the following.

Subclass obj4 = new Subclass ( );
((Superclass) obj4).print ( );

Choose one answer.

Typing Summary

Every object has a type—its dynamic type. Every container (variable, parameter, literal, return from function call, and operator expression) has a static type. Static types are "known to the compiler" because you declare them. Here's an example.

int[] A = new int[2];
Object x = A; // All references are Objects
A[k] = 0;     // Static type of A is array...
x[k+1] = 1;   // But static type of x is not an array: ERROR

The compiler figures out that not every Object is an array. If we know that x contains an array value, we tell the compiler that with a type cast.

((int [ ]) x)[k+1] = 1;

Once the compiler is satisfied, we'll be working with dynamic types at run time. Any object remembers how it was created, and thus its dynamic type is what's used to determine which method to call or variable to use.

D. Abstract Classes

Motivation

In all the cases we've seen so far, we have started with a class that's useful in its own right (Counter, Point, and IntSequence) and used inheritance to produce a class with extra functionality.

Consider now the slightly different task of using inheritance to organize an already existing bunch 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.

Any class that has an abstract method must be an abstract class, however.

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.
}

Most of the abstract classes in java.util are used in connection with collection classes, for example, sets and lists. The Java library javax.swing, which provides facilities for implementing graphical user interfaces, includes a variety of abstract classes that help to design platform-independent interfaces.

Abstract Dates

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

public abstract class Date {

    public abstract int dayOfYear ( );

    private int myDayOfMonth;
    private int myMonth;
    private int myYear;

    public Date (int year, int month, int dayOfMonth) {
        myDayOfMonth = dayOfMonth;
        myMonth = month;
        myYear = year;
    }

    public int dayOfMonth ( ) {
        return myDayOfMonth;
    }

    public int month ( ) {
        return myMonth;
    }

    public int year ( ) {
        return myYear;
    }

    public String toString ( ) {
        return "" + myDayOfMonth + "/" + myMonth + "/" + myYear;
    }
}

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 ( );
    }
}

Discussion: Reorganizing the Abstract Class

Another approach to the organization of the date classes is to eliminate the Date class entirely, copy its concrete methods into the GregorianDate class, and have FrenchRevolutionaryDate extend the updated GregorianDate class. Discuss with your partner the pros and cons of using this organization. Then add a discussion post about it.

Exercise: A nextDate Method

First, if you haven't switched which partner is at the computer yet during this lab, please switch now.

Then, 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!

E. 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 abstract methods (it cannot have non-abstract methods), and it cannot have instance variables (except for constants). Because all methods in an interface must be abstract, adding the abstract keyword is redundant, so it may be omitted.

Essentially, an interface is a collection of method header declarations. For example, the interface named Iterator in java.util names three method headers:

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

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

Some of you may know that Apple has requirements for the user interface of programs that run on the Macintosh. For instance, each program that involves editing data is supposed to supply a "File" menu that includes elements "Open", "Close", and "Print". A program that obeys the guidelines presents a consistent interface to the user and is deemed "Mac-like". A program that doesn't obey the guidelines is "un-Mac-like", and may be harder to learn and use as a result.

Java interfaces support the same kind of consistency for programmers as the Macintosh user interface guidelines do for users. By specifying method headers, they tell the programmer exactly what to name his or her methods in order to coordinate with other parts of the Java class libraries.

For example, there is a sort method in java.util.Arrays. Sorting involves comparing array elements, so if you're sorting an array of objects of a certain class, that class needs to define some way to compare the objects in it. One does this by having the class implement the Comparable interface and supply a method named compareTo to do comparison between elements.

A programmer wanting to sort an array would probably not call compareTo directly. Instead, he or she would call Arrays.sort, which in turn would call the user-provided method. This is referred to as a callback, where you call a method of another class that you expect to call a method in your class.

Overall, think of an interface as specifiying a contract for any class that implements the interface, which then can be relied upon to supply the relevant methods for users of the class.

Exercise: Sorting Dates

Create a SimpleDate class to work with the following main method. You only need to implement a simple version that can work with the following main method.

public static void main (String [ ] args) {
    SimpleDate [ ] dArray = new SimpleDate [4];
    dArray[0] = new SimpleDate (5, 2); // 5/2
    dArray[1] = new SimpleDate (2, 9); // 2/9
    dArray[2] = new SimpleDate (6, 3); // 6/3
    dArray[3] = new SimpleDate (1, 11); // 1/11
    Arrays.sort (dArray);
    for (int k=0; k<dArray.length; k++) {
        System.out.println(dArray [k]);
    }
    // should print the dates in chronological order:
    // 1/11, 2/9, 5/2, 6/3
}

Some details:

• To make this code compile, your SimpleDate class must implement Comparable<SimpleDate> (not just Comparable). Consult the Java API to find out what methods the Comparable<T> interface promises.
• The Arrays.sort method is found in java.util. Don't try to rewrite it; just use the version in the library. You may have to import it with import java.util.Arrays;.

F. A Better IntSequence

Exercise: A Better IntSequence

Recall that when add was called on an IntSequence that did not have any space left, the expected behavior was to print out an error message and then call System.exit(1). We can do better.

Create a ResizableIntSequence class that extends your IntSequence class from lab 5. Override the add and insert methods so that whenever either of these methods is called on a full ResizableIntSequence, the ResizableIntSequence increases its capacity to accomodate for the new elements.

Remember to write tests before you start coding your methods!

Discussion: Increasing Capacity

Once a ResizableIntSequence has reached its maximum capacity, by how many elements should its capacity be increased? 10? 1000? Something else? Explain your reasoning, and add a post about it to the discussion.

Discussion: Decreasing Capacity

Once you remove too many elements from a formerly very large ResizableIntSequence , it becomes wasteful for the ResizableIntSequence to keep around all of its unused space. Suppose the remove method decreased a ResizableIntSequence 's maximum capacity by some factor once its capacity reached some threshold (i.e. once it contained less than some small fraction of its maximum capacity).

What's a reasonable resizing capacity threshold, and by how much should we decrease a ResizeableIntSequence 's maximum capacity?

Exercise: One Last Step

Now override the remove method to dynamically decrease a ResizableIntSequence's maximum capacity once its capacity reaches some threshold.

ArrayLists

Congratulations! You've just implemented a basic version of an ArrayList<Integer>. ArrayList is Java's implementation of automatically resizing arrays. Note that unlike regular arrays, ArrayLists can only hold objects (so no primitives). We expect that you'll find this data structure incomprehensibly useful in the future. For more details on ArrayLists, you can check out Java's API.

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?
• What does the Java Collection Framework contain?

Submission

Submit as lab06:

• ModNCounter.java that works with the Counter class that has a private instance variable
• TracedPoint.java
• Your four date java files
• ResizableIntSequence.java and ResizableIntSequenceTest.java.

Reading

Read the following:

• HFJ pages 250 through 255, chapter 11, and Appendix B #4