Announcements

Regrades are open on gradescope.

CS61B, Spring 2016

Lecture 14: Generics, Iteration, Exceptions

• Finishing up Generics
• Iteration
• Quick Look at Exceptions

Where We Left off Last Time

First, we built an ArrayMap class.

• Supports put, get, containsKey, keys methods.
• In an ideal world we’d also have a Map61B interface. That’ll come in a later lab.

ArrayMap<Integer, String> am = new ArrayMap<Integer, String>();

am.put(5, "hello");

am.put(10, "ketchup");

assertTrue(am.containsKey(5));

assertTrue(am.containsKey(10));

assertEquals("hello", am.get(5));

List<Integer> keys = am.keys();

Q: But wait… I thought this returned an array?

​

A: It did, but I changed the API to be a bit more conventional.

Where We Left off Last Time

Second, we started building a MapHelper class hoping to provide the following:

• get(key): Returns the item in the map if it exists, null otherwise.
• maxKey(): Returns the maximum of all keys. Works only if keys can be compared.
• allBark(): Makes all keys bark. Works only for keys of type Dog.

ArrayMap<String, Integer> am = new ArrayMap<String, Integer>();

am.put("hello", 5);

am.put("ketchup", 10);

assertEquals(5, MapHelper.get(am, "hello");

assertEquals(null, MapHelper.get(am, "moo");

assertEquals("ketchup", MapHelper.maxKey(am));

Changed from last lec.

Where We Left off Last Time

Second, we started building a MapHelper class hoping to provide the following:

• get(key): Returns the item in the map if it exists, null otherwise.
• maxKey(): Returns the maximum of all keys. Works only if keys can be compared.
• allBark(): Makes all keys bark. Works only for keys of type Dog.

ArrayMap<String, Integer> am = new ArrayMap<String, Integer>();

am.put("hello", 5);

am.put("ketchup", 10);

assertEquals(5, MapHelper.get(am, "hello");

assertEquals(null, MapHelper.get(am, "moo");

assertEquals("ketchup", MapHelper.maxKey(am));

MapHelper.java

Where We Left off in maxKey

We had the code below, with two problems:

• Major problem: Cannot compare JohnDeNeros using >.
• Only numerical primitives can be compared with >.
• Minor problem: JohnDeNero and HotDog make code hard to read.

public static <JohnDeNero, HotDog> JohnDeNero

maxKey(ArrayMap<JohnDeNero, HotDog> am) {

List<JohnDeNero> keys = am.keys();

JohnDeNero maxKey = keys.get(0);

for (int i = 0; i < keys.length; i += 1) {

if (keys.get(i) > maxKey)

}

}

… though due to auto-unboxing: numerical wrapper types can be compared with >

Where We Left off in maxKey

We had the code below, with two problems:

• Major problem: Cannot compare JohnDeNeros using >.
• Only numerical primitives can be compared with >.
• Minor problem: JohnDeNero and HotDog make code hard to read.

public static <K, V> K maxKey(ArrayMap<K, V> am) {

List<K> keys = am.keys();

K maxKey = keys.get(0);

for (int i = 0; i < keys.length; i += 1) {

if (keys.get(i) > maxKey)

}

}

Now let’s try the compareTo trick we did in an earlier lecture.

… though due to auto-unboxing: numerical wrapper types can be compared with >

Issue with The compareTo Approach

public static <K, V> K maxKey(ArrayMap<K, V> am) {

List<K> keys = am.keys();

K maxKey = keys.get(0);

for (int i = 0; i < keys.length; i += 1) {

int cmp = keys.get(i).compareTo(maxKey);

if (cmp > 0) {

maxKey = keys.get(i);

}

}

return maxKey;

}

​

$ javac MapHelper.java

MapHelper.java:14: error: cannot find symbol

int cmp = keys.get(i).compareTo(maxKey);

^

symbol: method compareTo(K)

location: class Object

​

​

​

​

​

Type Upper Bounds to The Rescue

Can use extends keyword as a type upper bound. Only allow use on ArrayMaps with OurComparable keys.

​

OurComparable

compareTo(OurComparable)

K

compareTo(OurComparable)

Note: Type lower bounds also exist, specified using the word super. Won’t cover in 61B.

public static <K extends OurComparable, V> K maxKey(ArrayMap<K, V> am) {

...

int cmp = keys.get(i).compareTo(maxKey);

...

}

​

Meaning: Any ArrayMap you give me must have actual parameter type that is a subtype of OurComparable.

A Better Type Upper Bound: Comparable

Can use extends keyword as a type upper bound. Only allow use on ArrayMaps with Comparable keys.

​

Built in Java interface: Comparable<T>

• Implemented by Integer, String, etc.

Comparable<T>

compareTo(T)

K

compareTo(K)

Note: Type lower bounds also exist, specified using the word super. Won’t cover in 61B.

public static <K extends Comparable<K>, V> K maxKey(ArrayMap<K, V> am) {

...

int cmp = keys.get(i).compareTo(maxKey);

...

}

​

Meaning: Any ArrayMap you give me must have actual parameter type that is a subtype of Comparable<T>.

A Quick Dip into Generic Hell

We started building a MapHelper class hoping to provide the following:

• get(key): Returns the item in the map if it exists.
• maxKey(): Returns the maximum of all keys. Works only if keys can be compared.
• allBark(): Makes all keys bark. Works only for keys of type Dog.
• New feature: Wildcard types. Moved to extra slides.

ArrayMap<Dog, Double> am2 = new ArrayMap<Dog, Double>();

am2.put(new Dog("frank"), 10);

am2.put(new FrenchDog("francis", 20);

MapHelper.allBark(am2);

​

​

MapHelper.java

Iteration

The Enhanced For Loop

We saw that Java allows us to iterate through Lists using a convenient shorthand syntax sometimes called the “foreach” or “enhanced for” loop.

• Let’s strip away the magic so we can build our own classes that support this.

​

​

List<Integer> friends =

new ArrayList<Integer>();

friends.add(5);

friends.add(23);

friends.add(42);

for (int x : friends) {

System.out.println(x);

}

​

Doing Things The Hard Way

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

List<Integer> friends =

new ArrayList<Integer>();

...

for (int x : friends) {

System.out.println(x);

}

​

public Iterator<E> iterator();

List.java:

List<Integer> friends =

new ArrayList<Integer>();

...

Iterator<Integer> seer

= friends.iterator();

​

while (seer.hasNext()) {

System.out.println(seer.next());

}

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

$ java IteratorDemo.java

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

True

$ java IteratorDemo.java

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

5

$ java IteratorDemo.java

5

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

True

$ java IteratorDemo.java

5

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

23

$ java IteratorDemo.java

5

23

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

True

$ java IteratorDemo.java

5

23

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

42

$ java IteratorDemo.java

5

23

42

How Iterators Work

An alternate, uglier way to iterate through a List is to use the iterator() method.

​

Iterator<Integer> seer

= friends.iterator();

while (seer.hasNext()) {

System.out.println(seer.next());

}

friends:

False

$ java IteratorDemo.java

5

23

42

The Secret of the Enhanced For Loop (No PollEv)

The secret: The code on the left is just shorthand for the code on the right. For code on left to work, which checks does the compiler need to do?

1. Does the List interface have an iterator() method?
2. Does the List interface have next/hasNext() methods?
3. Does the Iterator interface have an iterator method?
4. Does the Iterator interface have next/hasNext() methods?

for (int x : friends) {

System.out.println(x);

}

​

Iterator<Integer> seer

= friends.iterator();

​

while (seer.hasNext()) {

System.out.println(seer.next());

}

List<Integer> friends = new ArrayList<Integer>();

​

The Secret of the Enhanced For Loop

The code on the left is just shorthand for the code on the right. For this to work:

• Compiler checks that Lists have a method called iterator() that returns an Iterator<Integer>.
• Then, compiler checks that Iterators have:
• hasNext()
• next()

for (int x : friends) {

System.out.println(x);

}

​

Iterator<Integer> seer

= friends.iterator();

​

while (seer.hasNext()) {

System.out.println(seer.next());

}

List<Integer> friends = new ArrayList<Integer>();

​

The Iterable Interface

Compiler checks that Lists have a method called iterator() that returns an Iterator<Integer>.

• How: The List interface extends the Iterable interface, inheriting the abstract iterator() method*.

​

List<T>

Iterable<T>

public interface Iterable<T> {

Iterator<T> iterator();

}

​

public interface List<T> extends Iterable<T>{

...

}

​

*: Actually List extends Collection which extends Iterable, but this is close enough to the truth.

Also I’m omitting some default methods in the Iterable interface.

The Iterator Interface

Then, compiler checks that Iterators have hasNext and next()

• How: The Iterator interface specifies these abstract methods explicitly.

​

List<T>

Iterable<T>

package java.util;

public interface Iterator<T> {

boolean hasNext();

T next();

}

​

I’m omitting some default methods in the Iterator interface.

Iterator<T>

Iteration Using A Nested Class

First, let’s create a KeyIterator class that allows client programs to iterate through the keys of an ArrayMap.

A “client program" is just any program that uses our class.

MapHelper.java

Iteration Using A Nested Class

First, let’s create a KeyIterator class that allows client programs to iterate through the keys of an ArrayMap.

public class KeyIterator {

private int ptr;

public KeyIterator() {

ptr = 0;

}

public boolean hasNext() {

return (ptr != size);

}

public K next() {

K returnItem = keys[ptr];

ptr = ptr + 1;

return returnItem;

}

}

ArrayMap<String, Integer> am =

new ArrayMap<String, Integer>();

am.put("hello", 5);

am.put("syrups", 10);

ArrayMap.KeyIterator ami =

am.new KeyIterator();

​

​

while (ami.hasNext()) {

System.out.println(ami.next());

}

Instantiating nested classes requires dot notation.

ArrayMap.java

ArrayMapClient.java

For-each Iteration And ArrayMaps

To support the enhanced for loop, we need to make ArrayMap implement the Iterable interface.

public interface Iterable<T> {

Iterator<T> iterator();

}

​

public class ArrayMap<K, V> {

...

}

​

ArrayMap<K, V>

Iterable<T>

For-each Iteration And ArrayMaps

To support the enhanced for loop, we need to make ArrayMap implement the Iterable interface.

ArrayMap<K, V>

Iterable<T>

public interface Iterable<T> {

Iterator<T> iterator();

}

​

public class ArrayMap<K, V> implements Iterable<K>

@Override

public Iterator<T> iterator() {

return new KeyIterator();

}

}

​

For-each Iteration And ArrayMaps

Given our definition of KeyIterator earlier, the code below will not compile.

• Why?

ArrayMap<K, V>

Iterable<T>

public interface Iterable<T> {

Iterator<T> iterator();

}

​

public class ArrayMap<K, V> implements Iterable<K>

@Override

public Iterator<T> iterator() {

return new KeyIterator();

}

}

​

For-each Iteration And ArrayMaps

Given our definition of KeyIterator earlier, the code below will not compile.

• KeyIterator does not implement the Iterator interface.

public interface Iterable<T> {

Iterator<T> iterator();

}

​

public class ArrayMap<K, V> implements Iterable<K>

@Override

public Iterator<T> iterator() {

return new KeyIterator();

}

}

​

ArrayMap<K, V>

Iterable<T>

For-each Iteration And ArrayMaps

To complete our task, simply make KeyIterator extend Iterator.

KeyIterator<K>

Iterator<K>

package java.util;

public interface Iterator<T> {

boolean hasNext();

T next();

}

​

public class KeyIterator implements Iterator<K> {

private int ptr;

public KeyIterator() { ptr = 0; }

public boolean hasNext() { return (ptr != size); }

public K next() { ... }

}

Iteration Summary

Implement iterable interface to support enhanced for loop.

• iterator() method must return an object that implements the Iterator interface.

​

Part 5 of HW1 gives you a chance to try this out yourself.

A Quick Look at Exceptions

Exceptions

Basic idea:

• When something goes really wrong, break the normal flow of control.
• So far, we’ve only seen implicit exceptions, like the one below.

public static void main(String[] args) {

ArrayMap<String, Integer> am = new ArrayMap<String, Integer>();

am.put("hello", 5);

System.out.println(am.get("yolp"));

}

​

$ java ExceptionDemo

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1

at ArrayMap.get(ArrayMap.java:38)

at ExceptionDemo.main(ExceptionDemo.java:6)

​

​

Explicit Exceptions

We can also throw our own exceptions using the throw keyword.

• Can provide more informative message to a user.
• Can provide more information to some sort of error handling code.

public V get(K key) {

int location = findKey(key);

if (location < 0) { throw new IllegalArgumentException("Key " +

key + " does not exist in map."); }

return values[findKey(key)];

}

$ java ExceptionDemo

Exception in thread "main" java.lang.IllegalArgumentException: Key yolp does not exist in map.

at ArrayMap.get(ArrayMap.java:40)

at ExceptionDemo.main(ExceptionDemo.java:6)

​

​

Extra Slides

A Quick Dip into Generic Hell

Second, we started building a MapHelper class hoping to provide the following:

• get(key): Returns the item in the map if it exists.
• maxKey(): Returns the maximum of all keys. Works only if keys can be compared.
• allBark(): Makes all keys bark. Works only for keys of type Dog.

ArrayMap<Dog, Double> am2 = new ArrayMap<Dog, Double>();

am2.put(new Dog("frank"), 10);

am2.put(new FrenchDog("francis", 20);

MapHelper.allBark(am2);

​

​

MapHelper.java

Problem #1: Dealing with Types We Don’t Care about

Implementation below works, but only for ArrayMaps from Dog to Double.

public static void allBark(ArrayMap<Dog, Double> am) {

List<Dog> dogs = am.keys();

for (int i = 0; i < dogs.size(); i += 1) {

dogs.get(i).bark();

}

}

ArrayMap<Dog, Integer> am2 = new ArrayMap<Dog, Integer>();

am2.put(new Dog("frank"), 10);

am2.put(new FrenchDog("francis"), 20);

MapHelper.allBark(am2);

​

​

$ javac MapHelper.java

MapHelper.java:62: error: incompatible types: ArrayMap<Dog,Integer> cannot be converted to ArrayMap<Dog,Double>

Value types mismatch!

Problem #1: Dealing with Types We Don’t Care about

How could we fix the allBark method so that it works for any value type?

public static void allBark(ArrayMap<Dog, Double> am) {

List<Dog> dogs = am.keys();

for (int i = 0; i < dogs.size(); i += 1) {

dogs.get(i).bark();

}

}

ArrayMap<Dog, Integer> am2 = new ArrayMap<Dog, Integer>();

am2.put(new Dog("frank"), 10);

am2.put(new FrenchDog("francis"), 20);

MapHelper.allBark(am2);

​

​

$ javac MapHelper.java

MapHelper.java:62: error: incompatible types: ArrayMap<Dog,Integer> cannot be converted to ArrayMap<Dog,Double>

Value types mismatch!

Fix #1

Can add generic parameter to method to fix.

public static <V> void allBark(ArrayMap<Dog, V> am) {

List<Dog> dogs = am.keys();

for (int i = 0; i < dogs.size(); i += 1) {

dogs.get(i).bark();

}

}

Alternate Fix #1

Alternately: Use Wildcard character: ?

Basic idea:

• We don’t care about the actual type, since we never used V anywhere.
• This is a fairly advanced feature you’re unlikely to use in 61B. Will only appear on a midterm or final if it ends up being on a HW/lab/project.

public static void allBark(ArrayMap<Dog, ?> am) {

List<Dog> dogs = am.keys();

for (int i = 0; i < dogs.size(); i += 1) {

dogs.get(i).bark();

}

}

Fix #1 and Alternate Fix #1 are both perfectly acceptable!

Quick Aside: Code Optimization

Lists in Java support for-each loop, sometimes called enhanced for loop.

public static void allBark(ArrayMap<Dog, ?> am) {

for (Dog d : am.keys()) {

d.bark();

}

}

public static void allBark(ArrayMap<Dog, ?> am) {

List<Dog> dogs = am.keys();

for (int i = 0; i < dogs.size(); i += 1) {

dogs.get(i).bark();

}

}

Avoids need to iterate through list using indices.

Same output.

Problem #2: Covariance

Surprisingly, cannot pass an ArrayMap of FrenchDog keys!

public static void allBark(ArrayMap<Dog, ?> am) {

for (Dog d : am.keys()) {

d.bark();

}

}

ArrayMap<FrenchDog, Integer> am2 = new ArrayMap<FrenchDog, Integer>();

am2.put(new FrenchDog("francis"), 10);

am2.put(new FrenchDog("francis jr"), 20);

allBark(am2);

$ javac MapHelper.java

MapHelper.java:62: error: incompatible types: ArrayMap<FrenchDog,Integer> cannot be converted to ArrayMap<Dog,?>

Covariance

Arrays are covariant in Java, but generic types are invariant.

​

Arrays are covariant:

• A FrenchDog is-a Dog.
• An FrenchDog[] is-a Dog[].

​

Generic types are invariant:

• A List<FrenchDog> is NOT a List<Dog>.

​

This maddening feature is my least favorite part of Java.

• Leads to lots of syntactical contortions. See next slide.
• Why did Java designers do this to us? See extra slides.

FrenchDog

Dog

FrenchDog[]

Dog[]

List<FrenchDog>

List<Dog>

Fixing Problem #2

Two equivalent fixes:

• Approach 1: Add a generic type to our method.
• Approach 2: Add a bounded-wildcard (unlikely to use in 61B).

public static <K extends Dog> void allBark(ArrayMap<K, ?> am) {

for (Dog d : am.keys()) {

d.bark();

}

}

​

​

public static void allBark(ArrayMap<? extends Dog, ?> am) {

for (Dog d : am.keys()) {

d.bark();

}

}

Code never uses K so need to actually specify a generic type.

Generics Summary

We’ve now seen four new features of Java that make Generics more powerful:

• Autoboxing and auto-unboxing of primitive wrapper types.
• Promotion between primitive types.
• Specification of generic types for methods (before return type).
• Type upper bounds (e.g. K extends Comparable<K>)
• Wildcards: ?

​

A true understand of Java generics takes a long time and lots of practice.

• You won’t know all the details by the end of 61B.
• I promise not to ask questions about bounded wildcards or type erasure (see extra slides).

And yet there’s still more, e.g. public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {

Type Erasure

The secret: When you write

​

​

​

Javac compiles into a .class file matching the code below (with free casts):

​

​

​

​

Many confusing things about generics (including invariance) are ultimately explained by this fact. Connection to invariance is not obvious. Won’t cover in 61B.

Java is said to erase the type T from Foo.class!

Citations

Seer: http://www.clipartoday.com/_thumbs/022/Fantasy/astrology_crystal_190660_tnb.png

​

​

​

​