Midterm 1

Students with no prior Java experience (1/5)

Students with 4/5 or 5/5 prior Java experience

Midterm 1

Students with a B-, B, or B+ in 61A

Students with a A-, A, or A+ in 61A

Prior Sem.

Fall 2014: 17 points

Spring 2015: 35 points

Spring 2016: 40 points

Overall

Fairly happy with the midterm, but there were not enough C-level problems.

• Results: Someone with a C-level understanding got < 10% instead of 25%.
• Massively demoralizing… I know!

​

Test score shadowing exists.

• If you do relatively better on your final, you can get points back. See website for more more details.

Spring 2016: 40 points

Announcements Lec 13, 14, 15

Next 3 lectures are various bits of Java syntax, less of a coherent story.

• Lec 13 (today): Generics, Immutability
• Lec 14: Exceptions, Access Control other than private/public
• Lec 15: Iterables/Iterators, Static Classes, other loose ends

​

HW1: Chance to get more practice with the topics in lectures 12-15.

CS61B, Spring 2015

Lecture 13: Generics, Conversion, Promotion

• Generic Basics, Autoboxing
• Immutability, Promotion
• Defining Generic Classes
• Generic Methods, Comparables

Generics

For the most part, using generics is pretty straightforward.

• Generic classes require us to provide one or more actual type arguments.

​

​

​

import java.util.ArrayList;��public class BasicArrayList {� public static void main(String[] args) {� ArrayList<String> L = new ArrayList<String>();� L.add("potato");� L.add("ketchup");

String first = L.get(0);�}

}

actual type argument: String.

Primitives Cannot Be Used as Actual Type Arguments

We cannot use primitive types as actual type arguments.

• Code below causes a compile time error.

import java.util.ArrayList;��public class BasicArrayList {� public static void main(String[] args) {� ArrayList<int> L = new ArrayList<int>();� L.add(5);� L.add(6);

int first = L.get(0);�}

}

jug ~/temp

$ javac BasicArrayList.java

BasicArrayList.java:5: error: unexpected type

ArrayList<int> L = new ArrayList<int>();

^

required: reference

found: int

​

​

Reference Types

Reminder: Java has 8 primitive types. All other types are reference types.

​

For each primitive type, there is a corresponding reference type called a wrapper class.

• For example, boolean’s wrapper class is Boolean.

​

Reference Types as Actual Type Arguments

Solution: Use wrapper type as actual type parameter instead of primitive type.

​

​

​

​

​

​

​

​

​

Conversion between int and Integer is annoying, so in Java 1.5 they introduced...

import java.util.ArrayList;��public class BasicArrayList {� public static void main(String[] args) {� ArrayList<Integer> L = new ArrayList<Integer>();� L.add(new Integer(5));� L.add(new Integer(6));

int first = L.get(0).valueOf();�}

}

Autoboxing

Autoboxing (auto-unboxing): Implicit conversions between wrapper/primitives.

​

​

​

​

​

​

​

​

​

Code above works even though we’re passing an int into an Integer parameter, and assigning a return value of type Integer to an int.

import java.util.ArrayList;��public class BasicArrayList {� public static void main(String[] args) {� ArrayList<Integer> L = new ArrayList<Integer>();� L.add(5);� L.add(6);

int first = L.get(0);�}

}

Autoboxing and Unboxing

Wrapper types and primitives can be used almost interchangeably.

• If Java code expects a wrapper type and gets a primitive, it is autoboxed.

​

​

• If the code expects a primitive and gets a wrapper, it is unboxed.

​

​

Some notes:

• Arrays are never autoboxed/unboxed, e.g. an Integer[] cannot be used in place of an int[] (or vice versa).
• Autoboxing / unboxing incurs a measurable performance impact!
• Wrapper types use MUCH more memory than primitive types.

public static void blah(Integer x) {

System.out.println(x);

}

​

int x = 20;

blah(x);

public static void blahPrimitive(int x) {

System.out.println(x);

}

​

Integer x = new Integer(20);

blahPrimitive(x);

Wrapper Types Are (Mostly) Just Like Any Class

You can read the source code to all built-in Java libraries.

• e.g. google “grepcode java Integer” yields this link.
• Integer has no magic powers except autoboxing/auto-unboxing.

​

​

​

public final class Integer

extends Number implements Comparable<Integer> {

​

private final int value;

​

public Integer(int value) {

this.value = value;

}

...

}

Wrapper Type Memory (PollEv.com/jhug text JHUG to 37607?)

​

Assuming:

• Addresses are 64 bits.
• ints are 32 bits.
• All Java objects take 64 bits + their fields.

​

How much total memory is used by bleepblorp to store its local variables?

1. 32 bits.
2. 64 bits.
3. 96 bits.
4. 128 bits.
5. 160 bits.

public static void bleepblorp() {

Integer x = new Integer(5);

System.out.println(x);

}

​

Related Concept: Promotion

A similar thing happens when moving from a primitive type with a narrower range to a wider range.

• In this case, we say the value is promoted.
• Code below is fine since double is wider than int.

​

​

​

To move from a wider format to a narrower format, must use casting:

​

​

​

Full details here: http://docs.oracle.com/javase/specs/jls/se8/html/jls-5.html

​

​

​

public static void blahDouble(double x) {

System.out.println(“double: “ + x);

}

​

int x = 20;

blahDouble(x);

public static void blahInt(int x) {

System.out.println(“int: “ + x);

}

​

double x = 20;

blahInt((int) x);

Immutability

Immutable Data Types

An immutable data type is one for which an instance cannot change in any observable way after instantiation.

​

Examples:

• Mutable: ArrayDeque, Planet.
• Immutable: Integer, String, Date.

​

​

The final keyword will help the compiler ensure immutability.

• final variable means you will assign a value once (either in constructor of class or in initializer).
• Not necessary to have final to be immutable (e.g. Dog with private varables).

​

Immutability

Advantage: Less to think about: Avoids bugs and makes debugging easier.

​

Disadvantage: Must create a new object anytime anything changes.

​

​

​

​

​

Warning: Declaring a reference as Final does not make object immutable.

• Example: public final ArrayDeque<String> d = new ArrayDeque<String>();
• The d variable can never change, but the referenced deque can!�

charAt(int i)

compareTo(String s)

concat(String s)

split(String r)

String

Defining Generic Classes

Goals

Goal 1: Create a class ArrayMap with the following methods:

• put(key, value): Associate key with value.
• containsKey(key): Checks to see if arraymap contains the key.
• get(key): Returns value, assuming key exists..
• keys(): Returns an array of keys.

​

Ok to ignore resizing for this exercise.

• In lecture, I’ll just show the answer, but you might find implementing it useful.

ArrayMap.java

ArrayMap (Basic Implementation)

Array implementation of a Map:

• Use an array as the core data structure.
• put(k, v): Finds the array index of k
• If -1, adds k and v to the last position of the arrays.
• If non-negative, sets the appropriate item in values array.

​

public class ArrayMap<K, V> {

private K[] keys;

private V[] values;

private int size;

public ArrayMap() {

keys = (K[]) new Object[100];

values = (V[]) new Object[100];

size = 0;

}

...

}

ArrayMap (Basic Implementation)

public void put(K key, V value) {

int i = getKeyIndex(key);

if (i > -1) {

values[i] = value; return; }

keys[size] = key;

values[size] = value;

size += 1;

}

​

public V get(K key) {

return values[findKey(key)];

}

public boolean

containsKey(K key) {

int i = findKey(key);

return (i > -1);

}

public K[] keys() {

return keys;

}

Using An ArrayMap

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

ismap.put(5, "hello");

ismap.put(10, "ketchup");

public class ArrayMap<K, V> {

private K[] keys;

private V[] values;

private int size;

public ArrayMap() {

keys = (K[]) new Object[100];

values = (V[]) new Object[100];

size = 0;

}

...

Actual type arguments

Generic type variables

A Mysterious Error Appears

​

​

The Issue:

• JUnit has many assertEquals functions including (int, int), (double, double), (Object, Object), etc.

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2));�}

$ javac ArrayMapTest.java

ArrayMapTest.java:11: error: reference to assertEquals is ambiguous

assertEquals(expected, am.get(2));

^

both method assertEquals(long,long) in Assert and method assertEquals(Object,Object) in Assert match

​

​

​

​

PollEv.com/jhug or text JHUG to 37607

Which automatic translations are needed to call assertEquals(double, double)?

1. Promote expected to double.
2. Autobox expected as a Double.
3. Autobox expected as an Integer.
4. Unbox am.get(2).
5. Promote the unboxed am.get(2) to double.

Hint, the actual call is: assertEquals(int, Integer)

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2));�}

There may be more than one right answer.

PollEv.com/jhug or text JHUG to 37607

Which automatic translations are needed to call assertEquals(double, double)?

• Promote expected to double.
• Autobox expected as a Double.
• Autobox expected as an Integer.
• Unbox am.get(2).
• Promote the unboxed am.get(2) to double.

Hint, the actual call is: assertEquals(int, Integer)

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2));�}

There may be more than one right answer.

Open Question

What automatic translations are needed to call assertEquals(Object, Object)?

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2)); }

Open Question

What automatic translations are needed to call assertEquals(Object, Object)?

​

​

​

​

​

Only one thing:

• Autobox expected into an Integer.

​

Even though this is ‘easier’ than the 3-step process needed to get to assertEquals(double, double), it’s still ambiguous and thus Java won’t let the code above compile.

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2)); }

Open Question

How do we get the code to compile, e.g. how do we resolve the ambiguity?

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2)); }

Open Question

How do we get the code to compile?

​

​

​

​

​

Many possible answers, one of them is:

​

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals(expected, am.get(2)); }

@Test�public void test() {� ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();� am.put(2, 5);� int expected = 5;� assertEquals((Integer) expected, am.get(2)); }

Generic Methods

Goals

Goal: Create a class MapHelper with three methods:

• get(key): Returns the item in the map if it exists.
• maxKey(): Returns the maximum of all keys. Works only if x and y contain comparable data.
• allBark(): Makes all keys bark. Works only for keys of type Dog.

Goals

Goal: Create a class MapHelper with three methods:

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

MapHelper.java

Generic Methods

Can create a method that operates on generic types by defining type parameters before the return type of the method:

​

​

​

​

​

In almost all circumstances, using a generic method requires no special syntax:

​

public static <X, Zerp> Zerp get(ArrayMap<X, Zerp> am, X key) {

if (am.containsKey(key)) {

return am.get(key);

}

return null;

}

Formal type parameter definitions.

Return type: Zerp (whatever that is)

ArrayMap<Integer, String> ismap =

new ArrayMap<Integer, String>();

System.out.println(MapHelper.get(ismap, 5));

It’s that easy.

Goals

Goal: Create a class MapHelper with three methods:

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

​

to be continued...

MapHelper.java

Citations

Drink:

http://hilanddairy.com/image-library/sites/default/files/styles/large/public/Hiland_GrapeDrink_Gal.jpg

​

Wrapper class image from Nanyang Technological University: https://www3.ntu.edu.sg/home/ehchua/programming/java/images/OOP_WrapperClass.png

​

​