CSE 331: Section 8 — Subtypes and Generics

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);
videoGames.add(obj);
goFishGames.add(obj);
goFishGames.add(goFish);
cardGames.add(cardGame);
goFishGames.add(null);
cardGame = cardGames.get(0);
videoGame = videoGames.get(0);
goFish = goFishGames.get(0);
obj = goFishGames.get(0);
goFish = cardGames.get(0);

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

B X

C X

D X
The following type declaration is legal, but probably does not make sense. Why not?
```
Collection<? extends Comparable<?>>
```
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

B X

C X

D 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?
What bounds should we put on T?
Next, we will make the change. Make MutableIntSet into a generic interface MutableSet that can store other types of data.
Do the documentation/specifications still make sense? If not, what do we need to fix?