Coming up Next: The Syntax Lectures

In the next three lectures, we’ll build an Array based implementation of a Map, and along the way, learn some new syntax.

  1. Autoboxing, promotion, immutability, generics
  2. Exceptions, Iterables/Iterators
  3. Access control, equals, other loose ends
  4. Wildcards, type upper bounds, covariance (not in the scope of the class).

Generics

For the most part, using generics is pretty straightforward.

  • Generic classes require us to provide one or more actual type arguments.
1
2
3
4
5
6
7
8
9
10
import java.util.ArrayList;

public class BasicArrayList {
    public static void main(String[] args) {
        ArrayList<String> L = new ArrayList<String>(); // actual type argument: String. In Java 8: No longer necessary at instantiation if also declaring a variable at the same time.
        L.add("potato");
        L.add("ketchup");
        String first = L.get(0);
    }
}

We cannot use primitive types as actual type arguments.

  • Code below causes a compile time error.
1
2
3
4
5
6
7
8
9
10
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);
    }
}
1
2
3
4
5
6
7
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.

wrapper

Reference Types as Actual Type Arguments

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

1
2
3
4
5
6
7
8
9
10
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();
    }
}

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

Autoboxing

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

1
2
3
4
5
6
7
8
9
10
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);
    }
}

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.

Wrapper types and primitives can be used almost interchangeably.

  • If Java code expects a wrapper type and gets a primitive, it is autoboxed.
1
2
3
4
5
6
public static void blah(Integer x) {
   System.out.println(x);
}

int x = 20;
blah(x);
  • If the code expects a primitive and gets a wrapper, it is unboxed.
1
2
3
4
5
6
public static void blahPrimitive(int x) {
   System.out.println(x);
}

Integer x = new Integer(20);
blahPrimitive(x);

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.

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.
1
2
3
4
5
6
7
8
9
public final class Integer extends Number implements Comparable<Integer> {

   private final int value;  

   public Integer(int value) {
       this.value = value;
   }
   ...
}

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
2
3
4
public static void bleepblorp() {  
   Integer x = new Integer(5);
   System.out.println(x);
}

160 bits: 64 + 96 for object

answer

Another Type of Conversion: Primitive Widening

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 “widened”.
  • Code below is fine since double is wider than int.
1
2
3
4
5
6
public static void blahDouble(double x) {
   System.out.println(“double: “ + x);
}

int x = 20;
blahDouble(x);

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

1
2
3
4
5
public static void blahInt(int x) {
   System.out.println(“int: “ + x);
}
double x = 20;
blahInt((int) x)

Immutability

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.
1
2
3
4
5
6
7
8
9
10
11
12
public class Date {
    public final int month;
    public final int day;
    public final int year;
    private boolean contrived = true;

    public Date(int m, int d, int y) {
        month = m;
        day = d;
        year = y;
    }
}

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

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

  • Analogy: Immutable classes have some buttons you can press / windows you can look inside. Results are ALWAYS the same, no matter what.

Disadvantage: Must create a new object anytime anything changes.

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

Example:

1
public final ArrayDeque<String> d = new ArrayDeque<String>();

The d variable can never change, but the referenced deque can!

Defining Generic Classes

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 a list of all keys.
  • size(): Returns number of keys.

Ok to ignore resizing for this exercise.

  • In lecture, I’ll just show the answer, but you might find implementing it useful. See study guide for this lecture for starter code.
1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
  ...
}

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 List<Keys> keys() {
  ... /* See code */
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ArrayMap<K, V> { // Generic type variables
    private K[] keys;
    private V[] values;
    private int size;

    public ArrayMap() {
        keys = (K[]) new Object[100];
        values = (V[]) new Object[100];
        size = 0;
    }
  ...
}

ArrayMap<Integer, String> ismap = new ArrayMap<Integer, String>(); // Actual type argument
    ismap.put(5, "hello");
    ismap.put(10, "ketchup");

A Mysterious Error Appears

1
2
3
4
5
6
7
@Test
    public void test() {
        ArrayMap<Integer, Integer> am = new ArrayMap<Integer, Integer>();
        am.put(2, 5);
        int expected = 5;
        assertEquals(expected, am.get(2));
    }
1
2
3
4
5
$ 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

The Issue:

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

Which automatic conversions are needed to call assertEquals(long, long)?

  1. Widen expected to long.
  2. Unbox am.get(2).
  3. Widen the unboxed am.get(2) to long.

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

Only one conversion needed (unless you count Integer → Object)

  • Autobox “expected” into an Integer.

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

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

Many possible answers, one of them is:

1
2
3
4
5
6
7
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

Goal: Create a class MapHelper with two methods:

  • get(Map61B, key): Returns the value corresponding to the given key in the map if it exists, otherwise null.
    • Unlike the ArrayMap’s get method, which crashes if the key doesn’t exist.
  • maxKey(Map61B): Returns the maximum of all keys in the given ArrayMap. Works only if keys can be compared.

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

1
2
3
4
5
6
public static <X, Zerp> Zerp get(ArrayMap<X, Zerp> am, X key) {
        if (am.containsKey(key)) {
            return am.get(key);
        }
        return null ''
    }

The first <X, Zerp> is formal type parameter definitions. Zerp is return type. (whatever that is)

  • 泛型类，是在实例化类的时候指明泛型的具体类型；泛型方法，是在调用方法的时候指明泛型的具体类型。
  • 泛型类中的使用了泛型的成员方法并不是泛型方法。只有声明了<T>的方法才是泛型方法。
  • 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前。
  • 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符。
  • 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符。
  • 静态方法不可以访问类上定义的泛型，如果静态方法操作的应用数据类型不确定，可以将泛型定义在方法上。

g

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

1
2
ArrayMap<Integer, String> ismap = new ArrayMap<Integer, String>();
System.out.println(MapHelper.get(ismap, 5))

The Issue with Generic Methods

We had the code below with a major problem: Cannot compare Ks using >>. (… though due to auto-unboxing: numerical wrapper types can be compared with >)

1
2
3
4
5
6
7
8
9
10
public static <K, V> K maxKey(ArrayMap<K, V> map) {
        List<K> keylist = map.keys();
        K largest = keylist.get(0);
        for (K k : keylist) {
            if (k > largest) {
                largest = k;
            }
        }
        return largest;
    }
1
2
3
4
5
6
7
8
9
10
public static <K, V> K maxKey(ArrayMap<K, V> map) {
        List<K> keylist = map.keys();
        K largest = keylist.get(0);
        for (K k : keylist) {
            if (k.compareTo(largest) > 0) {
                largest = k;
            }
        }
        return largest;
    }

New problem: K’s don’t necessarily have a compareTo method.

Type Upper Bounds to The Rescue

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

1
2
3
4
5
public static <K extends OurComparable, V> K maxKey(ArrayMap<K, V> am) {
   ...
        if (k.compareTo(largest) > 0) {
   ...
}

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