A. Intro

Learning Goals

The first focus of this lab will be to introduce you to object oriented programming, a programming paradigm that focuses on objects, which are containers of data, and how these objects interact with one another. Objects are instances of different classes. Java is an object oriented language, so it is necessary to understand how objects work in order to make full use of the language.

Related to objects and classes is the concept of 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, meaning many forms. In Java, this refers to how an object can have different forms or types. The procedure for untangling an instance of polymorphism can be somewhat complicated, so there are numerous exercises that provide you with practice.

We will talk about static and dynamic type, which is related to polymorphism in Java. Static vs dynamic type can be a tricky subject, so there are also many exercises in this lab to allow you to practice.

The last focus of today's lab is to wrap up loose ends from yesterday's lab, particularly concerning scope, which determines where a variable can be accessed. When programming, you will need to think about scope in order to organize your code and ensure its correctness. You'll also use the IntelliJ debugger to look for issues in code.

To get started, pull the code for Lab 4 and create a new IntelliJ project as usual.

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.

• 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 the version we used before.

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

Suppose we want a mod N counter, a counter where count is calculated mod N. One way to create ModNCounter.java is to just copy over the file Counter.java and modify it. However, this creates redundancies in our code. Instead, we can set up ModNCounter.java 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

Suppose we modify Counter.java to be as below and with a private instance variable count. Edit your Counter.java file so that it matches the code seen below.

public class Counter {

    private int count;

    public Counter() {
        count = 0;
    }

    public void increment() {
        count++;
    }

    public void reset() {
        count = 0;
    }

    public int value() {
        return count;
    }
}

Subclasses do not have access to the private variables of their superclasses. So, actually ModNCounter cannot have access to the private instance variable count. 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 count variable is private. Do not create a new count 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 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 super(); 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, you must explicitly 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" (poly) and "forms" (morphe). 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;
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
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

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

with

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. At compile time, the compiler, which wants to catch typing inconsistencies and other possibilities for error, asks can 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 in a later 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. 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 return 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
for (int k = 0; k < a.size(); k++) {
    System.out.println(a.get(k));
}

Remember this used the toString methods defined in TracedPoint, Point, and String. 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, and String, 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. Scope

When we reference a variable in any way during the execution of a method - for example, to increment by saying something like counter = counter + 1 - the Java run time environment must do variable look-up. This is when scoping comes into play. Java adheres to a tiered look-up system, and checks for the existence of variables in this order:

1. Local scope. This is the current method body and we'll discuss this in a bit more detail below.
2. Current instance scope, the fields directly available in the type of the object pointed to by this. Typically (but not always, because of polymorphism!), this is also the class the method currently being executed is defined in.
3. Any classes that the current class inherits from. How this works has been talked about extensively above.

Consider the following code snippet, which can also be found as Swap.java without the comments:

public class Swap {
    int counter = 0;            // instance variable
    int counter2 = 0;           // instance variable
    static int counter3 = 0;    // static, is a class variable

    /* swap() iterates through the array from the start_index and
       swaps elements forward if they are in descending order with respect
       to the next element, and then prints out the number of swaps. */
    public int swap(int[] arr, int start_index) {   // beginning of method block
        while (start_index < arr.length - 1) {          // beginning of while block
            int counter = 0;                        // local variable, available inside while loop
            if (arr[start_index] > arr[start_index+1]) {
                int temporary = arr[start_index];   // available inside if statement
                arr[start_index] = arr[start_index+1];
                arr[start_index+1] = temporary;
                counter = counter + 1;              // references local variable counter
                counter2 = counter2 + 2;            // references instance variable
                counter3 = counter3 + 1;            // references class variable
            }
            start_index = start_index + 1;          // references local variable start_index
        }                                           // end of while block
        System.out.println("Swapped " + counter + " times.");
        return counter;
    }                                               // end of method block

    public static void main(String[] args) {
        Swap s = new Swap();
        int[] arr = {3, 2, 6, 1, 4};
        s.swap(arr, 0);     // expect to swap 3 times, (3, 2), (6, 1) and (6, 4)
                            // -> arr is {2, 3, 1, 4, 6}
        s.swap(arr, 0);     // expect to swap 1 time -> arr is {2, 1, 3, 4, 6}
    }
}

Let's talk first about local scope. Any time you see a pair of matching curly braces with statements inside (so not including the curly braces around the class definition), that defines a block. Examples of this are method definitions, while statements, for loops, if statements, and so on.

Variables defined inside a block are local variables. These exist until the end of the block. This means that variables defined inside a method goes out of scope after the method finishes execution, and variables defined in an if statement or while loop go out of scope and are not accessible after the if statement or an iteration of the while loop. Finally, note that method arguments behave like local variables defined at the beginning of the method's execution. This can be seen in the example in the line start_index = start_index + 1.

Variables defined just inside the class are fields, and are used when look-up for a local variable fails. For example, when we say counter = counter + 1, we find counter as a local variable and do not look up the instance variable counter. However, when we say counter2 = counter2 + 2, we don't find a local variable counter2 and use the instance variable counter2.

When we define a local variable that has the same name as a field, like counter, counter now refers to the local variable and the only way to access the field is through this.counter. The Java compiler may give you a warning that the definition of counter hides a field. This can be ignored.

Take a moment to read through the code snippet above, and think about what is going on and going wrong. If you're not immediately sure, that's good! We'll walk through using the IntelliJ Debugger, which is an important and vital tool you'll be using throughout this class.

Exercise: Use the debugger to find the fix

You can set a breakpoint by clicking to the left of the line of code, as shown by the red dot here:

Then, when you run in Debug mode (the bug icon on the top right, right click the file name and go to debug, or run -> debug), when execution reaches the point where a breakpoint is specified, execution will stop and drop you into the debugger.

Notice how in "Variables", you can inspect the active variables and open them up. In the code display section, the values of variables will be shown. And circled in white are the control buttons. You can hover over them and see what they are labeled:

• Step into - if there's a function call on the current line, step into that function's execution. If there is none, behaves the same as step over.
• Step over - execute everything on the current line and move on to the next one.
• Force Step Into - You shouldn't need this.
• Step out of - If you're in a function call, finish the function call and go to the calling method.

Here we want to "Step Into", as we want to see what happens when Swap executes. Inside Swap, trying stepping and watching the course of execution. It might be helpful to watch the values of variables change and inspect which variables are available from the current context. Finally, one useful thing to notice is the stack trace:

Clicking on either method in the call trace will move the current view to that method's current context (that is, either line 11 of swap or line 23 of main in this example).

You'll want to use the debugger instead of print-statement debugging for most bugs, and especially in your larger projects. Learning to use it will save you valuable time in tracking down bugs.

Fix up Swap.java so that it behaves correctly and outputs the correct number of swaps.

Sidenote: The CS61BL IntelliJ Plugin

Additionally, the CS61BL plugin for IntelliJ that we had you install allows you to use the Java Visualizer in IntelliJ. This can also be a tool for you to use to debug programs. Note that while this will be helpful for smaller programs, for larger projects, it might not be possible for you to visualize everything.

To use the built-in visualizer, debug your code, setting breakpoints as necessary. When your code stops, you can click the Java Visualizer icon:

The Java Visualizer will appear, displaying the stack of the currently paused program:

Static

There's something that we've been kind of waving off up until now: the static keyword. In Java, static fields belong to the class instead of a particular instance. We call these static fields or class variables. During execution, only one instance of a static field exists throughout, no matter how many instances of the class are created. You can think of them as living in their own special space, away from each instance. Static fields can be referenced the same as instance variables from within a instance method. They can also be directly referenced as ClassName.staticVariable, or by the instance reference (although this is not recommended for style. For example, in the Swap class if we wanted to access counter3 could either write:

Swap s = new Swap();
System.out.println(Swap.counter3);
System.out.println(s.counter3);

and as you can see in the snippet above, within an instance method of inside Swap, it can be accessed just with its name, so long as it has not been hidden by a local variable.

Recall that methods can also be static. This just means the method does not belong to a specific instance, like instance methods do.

E. Conclusion

Summary

We hit four "high points" in this lab: object-oriented programming (OOP), inheritance, polymorphism, static and dynamic types, and scope. 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?

Deliverables

A quick recap of things you need to do to complete this lab:

• Read through the lab and try some of the discussion questions with your partner. Then try the self-test questions.
• Implement ModNCounter.java which inherits from Counter.java after having been edited to contain private instance variables.
• Implement TracedPoint.java which extends from the java.awt library.
• Fix Swap.java so that it correctly prints the number of swaps.
• Fill out the week 1 reflection to get the secret word and put it in Survey.java