Lab 3–Standard: Understanding Types and Casts in Java
1 Lab Objectives
Understand extended interfaces in Java
Understand casting in Java
Review the binary search tree implementation from class
The binary search tree implementation we developed in class had a lot of details in it, many of them essential to programming well in Java. This lab has you work with that code to understand those issues.
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.
This is a great lab to work on with other students, if you wish. Just make sure that everyone participates in explaining what you are observing in prose.
Before you start, download the BST implementation to your computer.
2 Understanding Casts
There are several places in which the implementation has to use casts to tell Java that an object should be viewed as a different type than what Java would have assumed. Your goal in this section is to understand why these casts are necessary.
In addElt within DataBST, there are casts on the BSTs returned from the recursive calls to addElt. Remove one of these casts and try to compile. What is the resulting error message trying to tell you?
Casts help resolve apparent inconsistencies in your code. Where is the inconsistency around the cast that you removed? To answer this, identify two concrete spots in the code that suggest to Java that the object you had a cast will have different types.
Once you have found an inconsistency between two spots A and B, there are three general ways you could try to eliminate it:
edit the type of A to match B
edit the type of B to match A
use a cast to make them consistent on individual objects when the program runs
Try each of the first two approaches – see where you would edit the code, and play with the cascade of errors as you try to make this work out (don’t worry about messing up the file – you can always download a clean copy). Make sure you can understand each error message you get as you change the code.
Summarize the problem that casts address in your own words.
3 Working with Extended Interfaces
At least some of the challenges we face in this implementation come from the fact that we have one interface (IBST) extending another (ISet). This led to some of the apparent inconsistencies in the types.
One way to avoid the casts of the previous section is to try to copy all the method headers from ISet to IBST. The starter file has a commented out line showing how you might do this.
Make that edit to the code. Try to compile and see what happens.
Remove the casts to IBST. What happens?
Do you think copying the headers to the IBST interface is a good idea? Why or why not? Think about the implications for maintaining the software long term, whether it actually saves work in the long run, etc.
4 Handling Errors
The implementation has to include a largestElt method in the MtBST class, even though this method does not make sense on an empty tree. Your goal in this section is to understand why that method is there.
Comment out the method and compile. The error should complain that MtBST does not satisfy the interface.
Comment the method out of the interface and try to compile. What error do you get now?
Based on these two errors, write down an explanation of why you need to include largestElt in the MtBST class. A good answer does not restate the messages. Instead, it should explain what Java needs and why including this method resolves the issue.
5 If You Finish Early
Spend time reviewing the BST code and make sure you understand it. 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, come see someone for help.