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 the details of the 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 the guest to the set)
void addGuest(String newGuestName) {
this.guests = ....;
}
// check whether a guest is coming (use hasElt() to see if
// the guest is in the set)
boolean isComing(String name) {
return ...;
}
// return the number of guests in the guest list
int numGuests(){
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, to allow for one of [LinkedList, BST, AVL].
// an EventGuests that uses LinkedLists under the hood ____ guestsLists = new EventGuests(new ...); // an EventGuests that uses BSTs under the hood ____ guestsBSTs = new EventGuests(new ...); // an EventGuests that uses AVL trees under the hood ____ guestsAVLs = new EventGuests(new ...);In other words, the choice between LinkedLists, BSTs, and AVL trees is made entirely outside the EventGuests class, not fixed within it.
Hint: consider making an interface for ISet that requires the three set methods addElt(), hasElt(), and size(). Figure out how to (a) hook BSTs or AVL's up to this interface, and (b) how to make LinkedLists satisfy this interface (since LinkedList is a built-in class, you'll have to handle this one a little bit differently). In a class hierarchy, interfaces can extend other interfaces.
To make the exercise more concrete, here's the BST code from last week, modified to hold String as the element type. See if you can put all the pieces together (the BST code, your new ISet interface, the completed EventGuests class, and an Examples class) in a way that chooses the BST implementation of a set.