Lab 3–Advanced: Eliminating Instanceof in Java

1 Lab Objectives

1. Explore proposals for eliminating instanceof from Java programs

If you do not already understand casts in Java, do at least the casting section of the standard lab before attempting this one (casts are part of the course outcomes; the material in this lab is not).

The binary search tree implementation we developed in class used a pair of methods to eliminate undesirable uses of instanceof in the remElt method. In this lab, we will consider two other proposed approaches, contrasting the strengths and limitations of each.

Several of the problems ask you to write down a couple of sentences describing your understanding of a problem. Doing these will make sure you understand the issues – take them seriously!. If you can’t put your understanding into words, you don’t understand the concept well enough yet. Ask for help either in lab or in office hours. If you are more comfortable in a language other than English, answer these first in your preferred language then try to translate them.

Before you start, download the BST implementation with instanceof to your computer.

2 Multiple Methods with Different Headers

Java allows you to define multiple methods with the same name but different argument types. When you call a method with actual arguments, Java uses the one with types that most precisely match those of the arguments. This is also part of dispatching.

When we created methods to eliminate instanceof in class, we created methods on different types of individual children (in other words, we called a method on the left child passing the right child as argument or vice versa). This raises a question though: what if we instead defined four helper methods in the DataBST class with the headers:

DataBST remParentNode(MtBST left, MtBST right){...}

DataBST remParentNode(MtBST left, DataBST right){...}

DataBST remParentNode(DataBST left, MtBST right){...}

DataBST remParentNode(DataBST left, DataBST right){...}

and rewrote remElt to do

public IBST remElt (int elt) {

if (elt == this.data)

return this.remParentNode(this.left, this.right);

...

}

Modify the code that uses instanceof to implement this suggestion. If it works, would you recommend this solution over the one in class? Why or why not? If it doesn’t work, explain clearly what goes wrong (i.e., don’t restate the error messages – instead, explain what Java is doing and why this solution is problematic in light of that).

3 Use A Different Data Definition

Perhaps we needed instanceof because we had the wrong data definition in the first place. Our approach created two kinds of trees: empty trees (MtBST) and non-empty trees (DataBST). Arguably, our DataBST fails to distinguish different kinds of data: there are Leaf nodes (have values but no children), Partial-leaf nodes (have value and only one child), and Internal nodes (have two children, each of which may be any kind of node). This would suggest that we instead had the following classes:

class Leaf implements INode {

int data;

// no other fields

}

class LeftOnly implements INode {

int data;

INode left;

// no other fields

}

class RightOnly implements INode {

int data;

INode right;

// no other fields

}

class Internal implements INode {

int data;

INode left;

INode right;

// no other fields

}

With INode and an MtBST class extending/implementing the IBST interface.

Such a code organization would seem to solve our instanceof problems, because the data would explicit capture whether the children were empty.

Explore this approach, fleshing out these classes to implement the BST operations. How does this approach compare to what we did in class? Would you recommend it? Why or why not? Answer in prose with crisp, technical answers.

4 Pulling it all Together

Summarize in prose your current understanding of the concern with using instanceOf and viable options for writing Java programs without it. Your goal is to balance the tension between exploiting dispatch, writing maintainable code, and enabling future extensions to code.

5 If You Finish Early

Go back and check that you are on top of the issues raised in the standard lab (as those are amenable to coverage on exams). Also make sure you understand the BST code from class thoroughly. You should be able to articulate where functions exploit the BST invariant and how functions preserve the BST invariant. Try writing answers to each of these down in prose. If you can’t write down clear, crisp statements, come see someone for help.