CSE 331: Section 8 — Subtypes and Generics (Solutions)

Task 1 — We Game to Please

Suppose that we have the following classes:

class Game {..}
class CardGame extends Game {..}
class VideoGame extends Game {..}
class GoFish extends CardGame {..}

and the following variables:

Object obj;
Game game;                 List<Game> games;
CardGame cardGame;         List<? extends CardGame> cardGames;
VideoGame videoGame;       List<VideoGame> videoGames;
GoFish goFish;             List<? super GoFish> goFishGames;

For each line of code below, state whether the call is legal or illegal. If it is illegal, briefly explain why.

cardGames.add(obj);

This is illegal since Object is not a subclass of any subclass of CardGame. (Object is a superclass of CardGame)
videoGames.add(obj);

This is illegal since Object is not a subclass of VideoGame.
goFishGames.add(obj);

This is illegal since our list may be of type i.e., List<Game> and Object cannot be cast down into a game.
goFishGames.add(goFish);

This is legal since goFish is castable into any of its superclasses.
cardGames.add(cardGame);

This is illegal since cardGames could be, e.g., List<GoFish>, and CardGame is not a subclass of GoFish.
goFishGames.add(null);

This is legal.
cardGame = cardGames.get(0);

This is legal since anything extending CardGame is castable to it.
videoGame = videoGames.get(0);

This is legal.
goFish = goFishGames.get(0);

This is illegal since goFishGames could be, e.g., List<Object>.
obj = goFishGames.get(0);

This is legal since anything is castable to Object.
goFish = cardGames.get(0);

This is illegal since cardGames could be, e.g., a CardGame.

Task 2 — A Compare to Remember

Answer each of the following questions about generic method declarations.

The first two parts use the type Comparable<T>, which is an interface containing only one method:

int compareTo(T other)

This function compares the object on which it is called, obj, and the passed-in object other. It returns -1 to indicate that obj comes before other, +1 to indicate that obj comes after other, and 0 if they can be placed in either order. (311 alert: the "before" relationship must be transitive, reflexive, and anti-symmetric.)

Consider the following alternative method declarations:
```
A: <E extends Comparable<E>> void randomize(Collection<E> vals)
B: <E extends Comparable<E>> void randomize(List<E> vals)
C: <E extends Comparable<? extends E>> void randomize(Collection<E> vals)
D: <E extends Comparable<? super E>> void randomize(List<E> vals)
```
Fill in the following table explaining the relationships between each pair of declarations. Write an "S" for if the declaration on left (the row) is stronger than the name on top (the column), a "W" if it is weaker, and a "---" if they are incomparable.

A B C D

A X S W ---

B W X W W

C S S X ---

D --- S --- X
The following type declaration is legal, but probably does not make sense. Why not?
```
Collection<? extends Comparable<?>>
```
This allows a collection of one type of object that are comparable to a different type of object. That means you can't actually compare elements of the collection to each other, e.g., for the purposes of sorting.
Consider the following alternative method declarations:
```
A: int find(Collection<?> sub, Collection<?> list)
B: int find(Collection<Object> sub, Collection<Object> list)
C: <T> int find(Collection<T> sub, Collection<T> list)
D: <T> int find(Collection<? extends T> sub, Collection<? super T> list)
```
Fill in the following table explaining the relationships between each pair of declarations. Write an "S" for if the declaration on left (the row) is stronger than the name on top (the column), a "W" if it is weaker, and a "---" if they are incomparable.

A B C D

A X S S S

B W X W W

C W S X W

D W S S X

	A	B	C	D
A	X	S	W	---
B	W	X	W	W
C	S	S	X	---
D	---	S	---	X

	A	B	C	D
A	X	S	S	S
B	W	X	W	W
C	W	S	X	W
D	W	S	S	X

Task 3 — Nothing Is Certain But Death and Maxes

/**
 * Represents a **mutable** integer set, or a collection of distinct integers.
 */
public interface MutableIntSet {
  /**
   * Determines whether n is in the set.
   * @param n the number to look for in the set
   * @return true if n is in the set, false otherwise
   */
  public boolean contains(int n);

  /**
   * Adds n to the set if not already present.
   * @param n the number to add to the new set.
   * @modifies obj
   * @effects obj is unchanged if obj_0 contains n
   * obj = n and obj_0 otherwise
   */
  public void add(int n);

  /**
   * Removes the desired int from the set. Returns true if successful,
   * false if the int isn't in this set.
   * @param n The int to remove.
   * @modifies obj
   * @effects if obj_0 contains n, obj = obj_0 with n removed.
   * If obj_0 does not contain n, obj = obj_0.
   * @return true if obj_0 contains n, false otherwise.
   */
  public boolean remove(int n);

  /**
   * Returns the size of this set
   * @return the number of elements contained in this set
   */
  public int size();

  /**
   * Returns the largest value in the set, which must be non-empty.
   * @requires len(obj) != 0
   * @return the largest integer in the set
   */
  public int max();
}

Revisit the specification of MutableIntSet. We are adding a max operation to the ADT that finds the largest element in the set.

In this problem, we will change the interface to store data other than integers by introducing a type parameter T for the type of data stored in the set.

Find all the places where "int" (or "Integer") appears in your interface. Which of these should be replaced by T's?

The parameter types for contains, add, and remove should be changed. The return type for max should be changed. The type parameter for the returned list in getSetAsListForTestingDoNotCallOrElse should be changed to List<T>.

The int return type in size should NOT be changed!
What bounds should we put on T?

Because of the max() method, it should be extends Comparable<T> (or even more general, extends Comparable<? super T>).

Next, we will make the change. Make MutableIntSet into a generic interface MutableSet that can store other types of data.

public interface MutableSet<T extends Comparable<T>> {
  public boolean contains(T n);

  public void add(T n);

  public boolean remove(T n);

  public int size();

  public T max();
}

Do the documentation/specifications still make sense? If not, what do we need to fix?

The main interface description is specific to integers; it should be changed to say elements. Several @param and @return descriptions specify "number" or "int" (e.g., in remove), which should be updated to "element." Lastly, the specification of max needs to clarify that "largest" is determined by calling compareTo() rather than a mathematical comparison operator.