Lab 4 Advanced: Avoiding instanceof and Interfaces for Sets
1 Lab Objectives
To let you try writing complex functions without instanceof
To give you practice with layers of interfaces, using sets as an example
If you don’t know instanceof, you can skip the first set of questions and just start with the "Interfaces extending interfaces" section. They don’t depend on each other.
2 Programming without instanceof
In class on Monday, we started looking at binary search trees in Java. Writing the remElt method is an interesting case study in OO design, because the method behavior changes based on how many children are on the node with the element to be removed.
Start from the BST code from Monday. Implement the remElt method on these classes. Your challenge is to do it without using instanceof or any method that acts like instanceof (such as an isEmpty method added to each BST class).
(This method is actually a good example of when instanceof is a lot cleaner than the alternative. BUT, it is a very good example to use to test your OO design skills, and whether you really understand the idea of method calls take the place of asking about the types of your classes.)
3 Interfaces extending interfaces
If you finish remElt, think about the following problem about how to allow code to be flexible on choices of specific data structures.
Assume someone is writing an application that maintains a set of names of people (as single strings) who plan to attend a large event. We’ve omitted some types and details of methods:
// A class for storing guests at a (potentially large) event) |
class EventGuests { |
______ guests; |
|
EventGuests(_____ guests) { |
this.guests = guests; |
} |
|
// record a new guest as coming (add to the set) |
________ addGuest(String newGuestName) { |
return ...; |
} |
|
// check whether a guest is coming (in the set) |
boolean isComing(String name) { |
return ...; |
} |
} |
The developer isn’t sure which data structure will end up being the best fit for how the application gets used, so she wants to leave the specific choice of data structure flexible. For now, she thinks she’ll use either a LinkedList or a BST (but she knows other options will also be presented in lecture later this week).
Your task is to figure out how to write the EventGuests class such that the developer can choose between using BSTs or Linked Lists to store the set of guests at the time of calling the EventGuests constructor. So you should be able to write code something like the following:
// an eventguests that uses LinkedLists under the hood |
____ GuestsLists = new EventGuests(new ...); |
// an eventguests that uses BSTs under the hood |
____ GuestsBSTs = new EventGuests(new ...); |
|
In other words, the choice between LinkedLists and BSTs is made entirely outside the PartyGuests class, not fixed within it.
(If you need a hint, consider making an interface for ISet that has our four addElt, remElt etc methods. Figure out how (a) hook BSTs up to this interface, and (b) how to make LinkedLists satisfy this interface. Look up the use of extends between interfaces, if you haven’t seen that idea before.)