4 of 27

Subtypes

Strength

ADT B is a subtype of A if:

B has all the methods of A
Each method of B has a stronger spec than A’s corresponding methods

If B is a subtype of A, then B is stronger than A

A is a supertype of B

Ex: Every Unicorn is a Pony

class Pony {...}

class Unicorn extends Pony {...}

* not enforced by Java, but very important practice to only define subclasses that are also subtypes!

5 of 27

Type Bounds

Upper Bound: extends

Type argument passed in must be the same type or a subclass

Lower Bound: super

Type argument passed in must be the same type or a superclass

6 of 27

Type Constraints: Extends

Ex:

List<? extends Unicorn> unicorns = new ArrayList<Unicorn>()

unicorns = new ArrayList<Rarity> // okay!

unicorns = new ArrayList<RainbowDash> // error!

Pony

RainbowDash

Unicorn

Rarity

7 of 27

Type Constraints: Super

Ex:

List<? super Unicorn> ponies = new Arraylist<Pony>()

ponies = new ArrayList<Rarity> // error!

ponies = new ArrayList<Pony> // ok!

Pony

RainbowDash

Unicorn

Rarity

8 of 27

Type Constraints on Methods

Code can only use methods from type bounds

Can only call methods guaranteed to be there

Ex:

class PinkyPie<E extends Pony>{

public string magic(E arg) {

return arg.magic(); // error! (Pony not guaranteed to magic())

}

class Twilight<E extends Unicorn>{

public string magic(E arg) {

return arg.magic(); // okay! (Unicorn is guaranteed to magic())

}

Pony

RainbowDash

Unicorn

Rarity

9 of 27

Generics

Throughout this entire class we’ve been dealing with Lists of numbers, booleans, and pairs

type List := nil | cons(x: ℤ, L: List)
type BList := nil | cons(f: 𝔹, L: BList)
type PList := nil | cons(p: ℤ × ℤ, L: PList)

What if we wanted to create a definition for any list?

type List<A> := nil | cons(x: A, L: List<A>)

Ex:

class FastLastList<T> implements List<T> {

private List<T> list;

private T last;

}

10 of 27

Generic Methods

Ex: Summing a List of integers or doubles:

static <T extends Number> double sum(List<T> list) {

double result = 0;

for (T n : list) {

result += n.doubleValue(); // Legal since T extends

} Number

return result;

}

11 of 27

Wildcards: ?

?: Concise way of writing some generics

“? extends E”: ? is an anonymous subclass of E
“? super E”: ? is an anonymous superclass of E
“?” is an anonymous subclass of Object
Each “?” is independent from each other
Allows for flexible input types

? vs Object:

List<?> allows for Object, but also Integer, String, etc…
Cannot pass List<Integer> for List<Object>
Can pass List<Integer> as List<?>

12 of 27

T vs ?

Use T to explicitly define, control, and reuse a given type
Use ? for dynamic, non-reusable input types where you don’t need to know the exact type

Ex:

Both of these functions are equivalent:

<T1, T2> void foo(List<T1> list, List<T2> list2) {...}
void foo(List<?> list, List<?> list2) {...}

If you want both lists to have the same type, you must use T:

<T> void foo(List<T> list, List<T> list2) {...}

13 of 27

Task 1 – We Game To Please

class Game {..}

class CardGame extends Game {..}

class VideoGame extends Game {..}

class GoFish extends CardGame {..}

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);

Object obj;

Game game;

List<Game> games;

CardGame cardGame;

List<? extends CardGame> cardGames;

VideoGame videoGame; List<VideoGame> videoGames;

GoFish goFish;

List<? super GoFish> goFishGames;

14 of 27

Task 1 – We Game To Please

class Game {..}

class CardGame extends Game {..}

class VideoGame extends Game {..}

class GoFish extends CardGame {..}

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.

Object obj;

Game game;

List<Game> games;

CardGame cardGame;

List<? extends CardGame> cardGames;

VideoGame videoGame; List<VideoGame> videoGames;

GoFish goFish;

List<? super GoFish> goFishGames;

15 of 27

Task 1 – We Game To Please

class Game {..}

class CardGame extends Game {..}

class VideoGame extends Game {..}

class GoFish extends CardGame {..}

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

e) cardGames.add(cardGame);

This is illegal since cardGames could be, e.g., List<GoFish>, and CardGame is not a subclass of GoFish.

f) goFishGames.add(null);

This is legal.

g) cardGame = cardGames.get(0);

This is legal since anything extending CardGame is castable to it.

h) videoGame = videoGames.get(0);

This is legal.

Object obj;

Game game;

List<Game> games;

CardGame cardGame;

List<? extends CardGame> cardGames;

VideoGame videoGame; List<VideoGame> videoGames;

GoFish goFish;

List<? super GoFish> goFishGames;

16 of 27

Task 1 – We Game To Please

class Game {..}

class CardGame extends Game {..}

class VideoGame extends Game {..}

class GoFish extends CardGame {..}

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

i) goFish = goFishGames.get(0);

This is illegal since goFishGames could be, e.g., List<Object>.

j) obj = goFishGames.get(0);

This is legal since anything is castable to Object.

k) goFish = cardGames.get(0);

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

Object obj;

Game game;

List<Game> games;

CardGame cardGame;

List<? extends CardGame> cardGames;

VideoGame videoGame; List<VideoGame> videoGames;

GoFish goFish;

List<? super GoFish> goFishGames;

17 of 27

Generic Method Declarations

We can compare generic method declarations similarly to how we compare specifications:

Parameters = preconditions
Return types = postconditions

Strength rules:

A method is stronger if:

it accepts more argument types (weaker precondition)
it returns a more specific type (stronger postcondition)

A method is weaker if:

it accepts fewer argument types (stronger precondition)
it returns a less specific type (weaker postcondition)

18 of 27

Generics Control Strength

When comparing declarations, ask:

Which accepts more possible argument types?
Which enforces weaker type relationships?
Does one strictly accept more valid calls than the other?

If yes, it is stronger. (weaker precondition)

Guidelines:

extends → widens acceptable inputs → weaker precondition → stronger method
super→ widens acceptable inputs → weaker precondition → stronger method
<T> → ties types together → stronger type relationship
? → each ? is independent → weaker type relationship

If neither allows strictly more calls or has stronger guarantees → incomparable

19 of 27

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.)

20 of 27

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)

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)

21 of 27

Task 2 – A Compare To Remember

Answer each of the following questions about generic method declarations.

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)

a) Is A stronger, weaker, or incomparable to B? Briefly explain your answer:

A is stronger because it accepts Collections of any type, whereas you can only provide Lists of any type to B.

b) Is A stronger, weaker, or incomparable to C? Briefly explain your answer:

A is weaker because it only accepts types that are Comparable with themselves. Meanwhile, C accepts types that are Comparable with themselves or any subclasses

c) Is B stronger, weaker, or incomparable to D? Briefly explain your answer:

B is weaker because it only accepts types that are Comparable with themselves. Meanwhile, D accepts types that are Comparable with themselves or any superclass

d) Is C stronger, weaker, or incomparable to D? Briefly explain your answer:

C is incomparable because it’s not possible to compare the set of superclasses and subclasses with one another.

22 of 27

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)

b) 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.

23 of 27

Task 2 – A Compare To Remember

Answer each of the following questions about generic method declarations.

c) 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)

a) Is A stronger, weaker, or incomparable to B? Briefly explain your answer:

A is stronger because it accepts Collections of any type, whereas you can only provide Collections of Objects to B.

b) Is A stronger, weaker, or incomparable to C? Briefly explain your answer:

A is stronger because it accepts two Collections which can each have any type, whereas both Collections in C must have the same type.

c) Is B stronger, weaker, or incomparable to C? Briefly explain your answer:

B is weaker because it accepts two Collections of Objects, whereas C’s Collections can have any type.

d) Is C stronger, weaker, or incomparable to D? Briefly explain your answer:

C is weaker because its Collections must have the same type, whereas D’s sub Collection can have any type at or below T, and list can have any type at or above T.

24 of 27

Task 3 – Nothing Is Certain But Death and Maxes

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

/**

* 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();

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!

25 of 27

Task 3 – Nothing Is Certain But Death and Maxes

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

/**

* 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();

b) 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>).

26 of 27

Task 3 – Nothing Is Certain But Death and Maxes

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

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

import java.util.List;

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();

}

27 of 27

Task 3 – Nothing Is Certain But Death and Maxes

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

d) 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.