Java,
Week 5

Week 3 met polymorphism as dynamic dispatch. This lecture widens the word: polymorphism is also about code that works for any type that has the right capability. It then shows why simulating that with the Object class works, but only half well, which is the reason Java added generics.

1.1Two meanings of polymorphism

1.2Polymorphic reverse

Every Java array of objects is an Object[] (arrays are subtypes in the same direction as their elements, more on that in the next lecture). So one function, written against Object[], reverses an array of anything:

public class Main {
    public static void reverse(Object[] arr) {
        int n = arr.length;

        for (int i = 0; i < n / 2; ++i) {
            Object temp = arr[i];
            arr[i] = arr[(n - 1) - i];
            arr[(n - 1) - i] = temp;
        }
    }

    public static void main(String[] args) {
        String[] s = { "a", "b", "c", "d" };
        Integer[] n = { 1, 2, 3 };
        reverse(s);                       // a String[] is an Object[]
        reverse(n);                       // so is an Integer[]
        System.out.println(java.util.Arrays.toString(s));
        System.out.println(java.util.Arrays.toString(n));
    }
}

[d, c, b, a]
[3, 2, 1]

public class Main {
    public static void reverse(Object[] arr) {
        int n = arr.length;

        for (int i = 0, i < n / 2; ++i) {
            Object temp = arr[i];
            arr[i] = arr[(n - 1) - i];
            arr[(n - 1) - i] = temp;
        }
    }

    public static void main(String[] args) { }
}

Main.java:5: error: ';' expected
        for (int i = 0, i < n / 2; ++i) {
                         ^
Main.java:5: error: > or ',' expected
        for (int i = 0, i < n / 2; ++i) {
                              ^
2 errors

One limit: a function over Object[] takes arrays of objects only. An int[] is not an Object[], because int is a basic type, not an object (the wrapper classes of Lecture 5 are the way round that):

public class Main {
    public static void reverse(Object[] arr) { }

    public static void main(String[] args) {
        int[] a = { 1, 2, 3 };
        reverse(a);
    }
}

Main.java:6: error: incompatible types: int[] cannot be converted to Object[]
        reverse(a);
                ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

1.3Polymorphic find: == or equals?

To find an element we need an equality check. The lecture writes arr[i] == o and comments that "== translates to Object.equals()". That is not what Java does. On objects, == compares references: are these the very same object? Only equals() asks whether two objects are equal in state (Week 3, once a class overrides it). The difference matters as soon as the key is a separate object:

public class Main {
    public static int find(Object[] arr, Object o) {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] == o) return i;          // the lecture's test: == on references
        }
        return -1;
    }

    public static int findEq(Object[] arr, Object o) {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i].equals(o)) return i;     // the capability we really need
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] names = { "Asha", "Ravi", new String("Meena") };
        Object key = new String("Ravi");        // equal to "Ravi", but a different object

        System.out.println(find(names, key));
        System.out.println(findEq(names, key));
    }
}

-1
1

So the lecture's find misses "Ravi" (it returns -1), while the version that calls equals finds it at index 1. The lecture's version seems to work on string literals only because identical literals are stored once and shared, so the two sides really are the same object (extra):

public class Main {
    public static int find(Object[] arr, Object o) {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] == o) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] names = { "Asha", "Ravi", "Meena" };
        System.out.println(find(names, "Ravi"));     // both literals: the very same object
    }
}

1

1.4Polymorphic sort: use an interface

For sorting, interfaces capture the capability: the Comparable interface from Week 4 with its cmp method, and one quicksort(Comparable[] a) that compares with a[i].cmp(a[j]). Any class that implements Comparable can be sorted:

public class Main {
    public static void main(String[] args) {
        Person[] p = { new Person("Ravi", 41), new Person("Asha", 29), new Person("Meena", 35) };
        SortFunctions.quicksort(p);
        System.out.println(java.util.Arrays.toString(p));
    }
}

[Asha (29), Meena (35), Ravi (41)]

1.5Type consistency: copying one array into another

A polymorphic function to copy an array. The lecture asks for two things: the target array must be type compatible with the source, and type errors should be flagged at compile time.

• With parameters Object[] src, Object[] target, copying dates into an array of employees must not be allowed.
• More generally the source can be a subtype of the target (an ETicket is a Ticket) but the converse is illegal.

What really happens with Object[] parameters is different, and worth seeing. The allowed direction works:

public class Copy {
    public static void arraycopy(Object[] src, Object[] target) {
        int limit = Math.min(src.length, target.length);
        for (int i = 0; i < limit; ++i) {
            target[i] = src[i];
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Ticket[] tktarr = new Ticket[3];
        ETicket[] etktarr = { new ETicket(), new ETicket(), new ETicket() };

        Copy.arraycopy(etktarr, tktarr);     // source is a subtype of the target: allowed
        System.out.println(java.util.Arrays.toString(tktarr));
    }
}

[ETicket, ETicket, ETicket]

Copying dates into employees compiles (both are Object[]), and fails at run time with an ArrayStoreException, as soon as a real element has to be stored:

public class Main {
    public static void main(String[] args) {
        Date[] datearr = { new Date(), new Date() };
        Employee[] emparr = new Employee[10];

        Copy.arraycopy(datearr, emparr);     // compiles: both are Object[]
    }
}

Exception in thread "main" java.lang.ArrayStoreException: Date
	at Copy.arraycopy(Copy.java:5)
	at Main.main(Main.java:6)

Notice the word real. The lecture's picture uses freshly created arrays, full of null, and copying null into any array is always fine, so that exact code runs without any error:

public class Main {
    public static void main(String[] args) {
        Date[] datearr = new Date[10];        // ten null slots
        Employee[] emparr = new Employee[10];

        Copy.arraycopy(datearr, emparr);      // as in the lecture's picture
        System.out.println("no error: only nulls were copied");
    }
}

no error: only nulls were copied

And the "illegal" direction (supertype array into subtype array) is also accepted by the compiler for Object[] parameters; it fails at run time the moment a plain Ticket meets an ETicket[] slot:

public class Main {
    public static void main(String[] args) {
        Ticket[] tktarr = { new Ticket(), new Ticket() };
        ETicket[] etktarr = new ETicket[2];

        Copy.arraycopy(tktarr, etktarr);     // the lecture calls this illegal
    }
}

Exception in thread "main" java.lang.ArrayStoreException: Ticket
	at Copy.arraycopy(Copy.java:5)
	at Main.main(Main.java:6)

1.6Polymorphic data structures

Arrays, lists and the like should allow arbitrary elements. A polymorphic list stores values of type Object: insert(Object newdata) in, Object head() out.

Problem 1: type information is lost, so casts are needed

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        Ticket t1, t2;

        t1 = new Ticket();
        list.insert(t1);
        t2 = (Ticket) (list.head());          // head() returns an Object: a cast is needed
        System.out.println(t2);
    }
}

Ticket

Leave the cast out and the compiler objects, because head() only promises an Object:

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(new Ticket());
        Ticket t = list.head();
    }
}

Main.java:5: error: incompatible types: Object cannot be converted to Ticket
        Ticket t = list.head();
                            ^
1 error

Problem 2: the list need not be homogeneous

Nothing stops a Date from going into a list meant for tickets. The mistake stays hidden until someone casts the wrong thing:

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        Ticket t = new Ticket();
        Date d = new Date();
        list.insert(t);
        list.insert(d);                       // nothing stops a Date going into a list of tickets

        Ticket first = (Ticket) list.head();  // the Date comes out first
    }
}

Exception in thread "main" java.lang.ClassCastException: class Date cannot be cast to class Ticket (Date and Ticket are in unnamed module of loader 'app')
	at Main.main(Main.java:9)

1.7Generic programming in Java: the way out

• Java added generic programming to address both problems.
• Classes and functions can have type parameters: class LinearList<T> holds values of type T; public T head() returns a value of the same type T as the enclosing class.
• We can describe subclass relationships between type variables: public <S extends T, T> void arraycopy(S[] src, T[] target).

1.8Lecture summary

• Polymorphism usually means dynamic dispatch; more generally it means behaviour that depends only on specific capabilities (structural polymorphism).
• Java simulates it with the class hierarchy: Object[] for reverse and find, an interface (Comparable) for sort.
• Arrays and lists of Object lose type information (casts) and may be heterogeneous.
• Generics are Java's answer.

Lecture 1 ended with a promise: classes and functions can take type parameters. This lecture shows how. A type variable lets the compiler see the relation between types (for example "the target array has the same element type as the source"), which the Object trick could not express.

2.1Generic methods: the type quantifier

public class Main {
    public static <T> void reverse(T[] arr) {
        T temp;
        int n = arr.length;

        for (int i = 0; i < n / 2; ++i) {
            temp = arr[i];
            arr[i] = arr[(n - 1) - i];
            arr[(n - 1) - i] = temp;
        }
    }

    public static void main(String[] args) {
        String[] s = { "a", "b", "c" };
        Integer[] n = { 1, 2, 3, 4 };
        reverse(s);                        // T is String here
        reverse(n);                        // T is Integer here
        System.out.println(java.util.Arrays.toString(s));
        System.out.println(java.util.Arrays.toString(n));
    }
}

[c, b, a]
[4, 3, 2, 1]

Nothing is declared for T at the call. The compiler infers it from the argument: String for the first call, Integer for the second.

2.2Polymorphic find, and a claim that needs a correction

The lecture writes public <T> int find(T[] arr, T o) and says: "searching for a value of incompatible type is now a compile-time error". For arrays that is not what happens. The compiler is allowed to pick T as a common supertype of the two arguments, and String and Integer share supertypes (Object, Comparable, Serializable), so the call is accepted and simply finds nothing:

public class Main {
    public static <T> int find(T[] arr, T o) {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i].equals(o)) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] names = { "Asha", "Ravi", "Meena" };
        System.out.println(find(names, "Ravi"));
        System.out.println(find(names, 42));       // the lecture says this is a compile error
    }
}

1
-1

The error does appear when you fix T yourself, or when the container is invariant (a List<T>, see Lecture 3), because then T cannot widen:

public class Main {
    public static <T> int find(T[] arr, T o) {
        return -1;
    }

    public static void main(String[] args) {
        String[] names = { "Asha", "Ravi", "Meena" };
        System.out.println(Main.<String>find(names, 42));   // say T = String yourself
    }
}

Main.java:8: error: incompatible types: int cannot be converted to String
        System.out.println(Main.<String>find(names, 42));   // say T = String yourself
                                                    ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

import java.util.List;

public class Main {
    public static <T> int find(List<T> list, T o) {
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i).equals(o)) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        List<String> names = List.of("Asha", "Ravi", "Meena");
        System.out.println(find(names, "Ravi"));
        System.out.println(find(names, 42));
    }
}

Main.java:14: error: method find in class Main cannot be applied to given types;
        System.out.println(find(names, 42));
                           ^
  required: List<T>,T
  found:    List<String>,int
  reason: inference variable T has incompatible bounds
    equality constraints: String
    lower bounds: Integer
  where T is a type-variable:
    T extends Object declared in method <T>find(List<T>,T)
1 error

2.3Polymorphic arraycopy

Version 1: identical types (the slide's claim)

The slide: <T> arraycopy(T[] src, T[] target), "source and target types must be identical". Two things to know. First, the slide writes public <T> static void, and Java insists the quantifier comes after the modifiers, right before the return type:

public class Main {
    public <T> static void arraycopy(T[] src, T[] target) { }

    public static void main(String[] args) { }
}

Main.java:2: error: illegal start of type
    public <T> static void arraycopy(T[] src, T[] target) { }
               ^
1 error

The correct order is public static <T> void. Second, the types need not be identical. Because of the inference we just saw, T can become Object, and dates copy into employees without a compile error, failing at run time exactly as in Lecture 1:

public class Main {
    public static <T> void arraycopy(T[] src, T[] target) {
        int limit = Math.min(src.length, target.length);
        for (int i = 0; i < limit; ++i) {
            target[i] = src[i];
        }
    }

    public static void main(String[] args) {
        Date[] datearr = { new Date() };
        Employee[] emparr = new Employee[1];
        arraycopy(datearr, emparr);           // compiles: T is inferred as Object
    }
}

Exception in thread "main" java.lang.ArrayStoreException: Date
	at Main.arraycopy(Main.java:5)
	at Main.main(Main.java:12)

Version 2: a more generous copy, source extends target

Use two type variables and say how they relate: <S extends T, T> means "for every pair of types S and T where S is a subtype of T". The source array is an S[], the target a T[]:

public class Main {
    public static <S extends T, T> void arraycopy(S[] src, T[] target) {
        int limit = Math.min(src.length, target.length);
        for (int i = 0; i < limit; ++i) {
            target[i] = src[i];
        }
    }

    public static void main(String[] args) {
        Ticket[] tktarr = new Ticket[2];
        ETicket[] etktarr = { new ETicket(), new ETicket() };

        arraycopy(etktarr, tktarr);           // S = ETicket extends T = Ticket: allowed
        System.out.println(java.util.Arrays.toString(tktarr));
    }
}

[ETicket, ETicket]

public class Main {
    public static <S extends T, T> void arraycopy(T[] src, T[] target) {   // the slide: S is never used
        int limit = Math.min(src.length, target.length);
        for (int i = 0; i < limit; ++i) {
            target[i] = src[i];
        }
    }

    public static void main(String[] args) {
        Ticket[] tktarr = { new Ticket() };
        ETicket[] etktarr = new ETicket[1];
        arraycopy(tktarr, etktarr);           // compiles: nothing relates S to the arrays
    }
}

Exception in thread "main" java.lang.ArrayStoreException: Ticket
	at Main.arraycopy(Main.java:5)
	at Main.main(Main.java:12)

The corrected form (S[] src) is the one above. Even so, with arrays the compiler does not fully stop the converse, because an ETicket[] is also a Ticket[] (covariance, Lecture 3), so T can simply be chosen as Ticket for both and the call compiles:

public class Main {
    public static <S extends T, T> void arraycopy(S[] src, T[] target) {
        int limit = Math.min(src.length, target.length);
        for (int i = 0; i < limit; ++i) {
            target[i] = src[i];
        }
    }

    public static void main(String[] args) {
        Ticket[] tktarr = { new Ticket(), new Ticket() };
        ETicket[] etktarr = new ETicket[2];

        arraycopy(tktarr, etktarr);           // the wrong direction: does it compile?
    }
}

Exception in thread "main" java.lang.ArrayStoreException: Ticket
	at Main.arraycopy(Main.java:5)
	at Main.main(Main.java:13)

With generic collections, which do not have this covariance, the same constraint is enforced at compile time, as the lecture intends:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static <S extends T, T> void copy(List<S> src, List<T> target) {
        for (S x : src) {
            target.add(x);
        }
    }

    public static void main(String[] args) {
        List<ETicket> etickets = new ArrayList<>();
        etickets.add(new ETicket());
        List<Ticket> tickets = new ArrayList<>();

        copy(etickets, tickets);              // ETicket extends Ticket: fine
        System.out.println(tickets);
    }
}

[ETicket]

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static <S extends T, T> void copy(List<S> src, List<T> target) { }

    public static void main(String[] args) {
        List<Ticket> tickets = new ArrayList<>();
        List<ETicket> etickets = new ArrayList<>();

        copy(tickets, etickets);              // the wrong direction, now with Lists
    }
}

Main.java:11: error: method copy in class Main cannot be applied to given types;
        copy(tickets, etickets);              // the wrong direction, now with Lists
        ^
  required: List<S>,List<T>
  found:    List<Ticket>,List<ETicket>
  reason: inference variable T has incompatible bounds
    equality constraints: ETicket
    lower bounds: S,Ticket
  where S,T are type-variables:
    S extends T declared in method <S,T>copy(List<S>,List<T>)
    T extends Object declared in method <S,T>copy(List<S>,List<T>)
1 error

2.4Generic classes: a polymorphic list

Put the parameter on the class: class LinkedList<T>. Then T applies to the whole class. The T in the inner Node is the same T, and so are the return value of head() and the argument of insert(). The code uses the Iterator<T> interface from Week 4, made generic too:

public class LinkedList<T> {
    private int size;
    private Node first;

    public T head() {
        T returnval = null;
        if (first != null) {
            returnval = first.data;
            first = first.next;
            size--;
        }
        return returnval;
    }

    public void insert(T newdata) {
        Node n = new Node(newdata);
        n.next = first;
        first = n;
        size++;
    }

    public int size() {
        return size;
    }

    public Iterator<T> get_iterator() {
        return new Iter();
    }

    private class Node {
        private T data;                      // the same T as the class's
        private Node next;

        private Node(T data) {
            this.data = data;
        }
    }

    private class Iter implements Iterator<T> {
        private Node position = first;

        public boolean has_next() {
            return position != null;
        }

        public T get_next() {
            T d = position.data;
            position = position.next;
            return d;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList<Ticket> ticketList = new LinkedList<Ticket>();
        LinkedList<Date> dateList = new LinkedList<Date>();

        Ticket t = new Ticket();
        Date d = new Date();

        ticketList.insert(t);
        dateList.insert(d);

        Ticket back = ticketList.head();      // no cast: head() returns a Ticket
        System.out.println(back);
        System.out.println(dateList.head());
    }
}

Ticket
Date

Both problems of Lecture 1 are gone: head() returns a Ticket with no cast, and a list is tied to one element type at the point where it is created. The word instantiate means giving the class a concrete type, as in new LinkedList<Ticket>(). Putting the wrong thing in is now a compile-time error:

public class Main {
    public static void main(String[] args) {
        LinkedList<Ticket> ticketList = new LinkedList<Ticket>();
        ticketList.insert(new Date());        // a Date into a list of tickets
    }
}

Main.java:4: error: incompatible types: Date cannot be converted to Ticket
        ticketList.insert(new Date());        // a Date into a list of tickets
                          ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

public class Main {
    public static void main(String[] args) {
        LinkedList<String> a = new LinkedList<String>();   // the lecture's form
        LinkedList<String> b = new LinkedList<>();         // (extra) the compiler fills in the type
        a.insert("x");
        b.insert("y");
        System.out.println(a.head() + b.head());
    }
}

xy

2.5Careful: do not hide a type variable

Inside class LinkedList<T>, writing public <T> void insert(T newData) introduces a brand new T for this method. The quantifier <T> masks the class's T. The element type of the list and the argument of insert are now unrelated, and the compiler refuses to put one into a Node:

public class LinkedList<T> {
    private int size;
    private Node first;

    public <T> void insert(T newdata) {      // a NEW T: it hides the class's T
        Node n = new Node(newdata);
        n.next = first;
        first = n;
        size++;
    }

    private class Node {
        private T data;
        private Node next;

        private Node(T data) {
            this.data = data;
        }
    }
}

LinkedList.java:6: error: incompatible types: T#1 cannot be converted to T#2
        Node n = new Node(newdata);
                          ^
  where T#1,T#2 are type-variables:
    T#1 extends Object declared in method <T#1>insert(T#1)
    T#2 extends Object declared in class LinkedList
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Read the error: T#1 is the method's variable, T#2 the class's. If nothing inside the method needed the class's T, the code would compile and the list would quietly accept anything, which defeats the purpose of the type parameter (extra):

public class LinkedList<T> {
    private Object first;
    private int count;

    public <T> void insert(T newdata) {      // hides the class's T
        first = newdata;
        count++;
    }

    public int count() { return count; }
}

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<String>();
        names.insert("fine");
        names.insert(42);                    // no longer protected
        System.out.println(names.count());
    }
}

2

2.6Extra: bounds on a single variable

extends works on one variable too. If the body needs a capability, say so in the bound: <T extends Comparable<T>> means "any T that can compare itself with another T". Anything else is rejected at compile time:

public class Main {
    public static <T extends Comparable<T>> T max(T a, T b) {
        return a.compareTo(b) >= 0 ? a : b;       // T must be able to compare itself
    }

    public static void main(String[] args) {
        System.out.println(max(3, 9));
        System.out.println(max("pear", "apple"));
        System.out.println(max(2.5, 1.5));
    }
}

9
pear
2.5

public class Main {
    public static <T extends Comparable<T>> T max(T a, T b) {
        return a.compareTo(b) >= 0 ? a : b;
    }

    public static void main(String[] args) {
        Object x = max(new Object(), new Object());
    }
}

Main.java:7: error: method max in class Main cannot be applied to given types;
        Object x = max(new Object(), new Object());
                   ^
  required: T,T
  found:    Object,Object
  reason: inference variable T has incompatible bounds
    upper bounds: Comparable<T>
    lower bounds: Object
  where T is a type-variable:
    T extends Comparable<T> declared in method <T>max(T,T)
1 error

2.7Lecture summary

• Generics bring structural polymorphism into Java through type variables.
• Classes and functions take type parameters: class LinearList<T> holds values of any one type T; T head() returns that same T.
• Relations between type variables: <S extends T, T>.
• Do not accidentally hide a class type variable with a method's <T>.

If String is a subtype of Object, is LinkedList<String> a subtype of LinkedList<Object>? Arrays say yes; generics say no. This lecture explains why, and the tools (generic methods and wildcards) that let one function accept lists of many element types safely.

3.1Arrays are covariant

The assignment is fine, but it makes a hole. The variable ticketarr promises "an array of tickets", while the object behind it only accepts ETickets. Storing a plain Ticket passes the compiler and fails when the program runs:

public class Main {
    public static void main(String[] args) {
        ETicket[] elecarr = new ETicket[10];
        Ticket[] ticketarr = elecarr;           // OK: ETicket[] is a subtype of Ticket[]
        System.out.println(ticketarr.length);

        ticketarr[5] = new Ticket();            // the compiler is happy ...
    }
}

10
Exception in thread "main" java.lang.ArrayStoreException: Ticket
	at Main.main(Main.java:7)

3.2Generic classes are not covariant

Generics close that hole by refusing the assignment altogether. LinkedList<String> is not compatible with LinkedList<Object>. Types with different arguments are unrelated ("invariant"):

public class Main {
    public static void main(String[] args) {
        LinkedList<String> strings = new LinkedList<String>();
        LinkedList<Object> objects = strings;
    }
}

Main.java:4: error: incompatible types: LinkedList<String> cannot be converted to LinkedList<Object>
        LinkedList<Object> objects = strings;
                                     ^
1 error

Why is that sensible? If the assignment were allowed, you could write objects.insert(new Date()) through the LinkedList<Object> name while the real list holds only strings: the same hole as for arrays, but now with no run-time check to catch it (Lecture 5 explains why: the element type is erased).

3.3The problem: printing any list

We want one printList that works for a list of anything. Since everything is an Object, the obvious try is a parameter of type LinkedList<Object>. It does not accept a list of strings:

public class Main {
    public static void printList(LinkedList<Object> l) {
        Iterator<Object> i = l.get_iterator();
        while (i.has_next()) {
            System.out.println(i.get_next());
        }
    }

    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<String>();
        names.insert("Asha");
        printList(names);
    }
}

Main.java:12: error: incompatible types: LinkedList<String> cannot be converted to LinkedList<Object>
        printList(names);
                  ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

3.4Fix 1: a generic method

Introduce a type variable: <T> void printList(LinkedList<T> l) means "for every type T, take a LinkedList<T>". Every concrete list type now fits. The body never needs T itself: a variable of type Object is enough to walk the list.

public class Main {
    public static <T> void printList(LinkedList<T> l) {
        Object o;
        Iterator<T> i = l.get_iterator();

        while (i.has_next()) {
            o = i.get_next();                    // T itself is never needed: Object is enough
            System.out.println(o);
        }
    }

    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<String>();
        names.insert("Asha");
        names.insert("Ravi");
        LinkedList<Integer> nums = new LinkedList<Integer>();
        nums.insert(7);

        printList(names);                        // T = String
        printList(nums);                         // T = Integer
    }
}

Ravi
Asha
7

The output order is Ravi then Asha: this list inserts at the front, so the last inserted comes out first (Week 4 code).

3.5Fix 2: the wildcard ?

public class Main {
    public static void printList(LinkedList<?> l) {
        Object o;
        Iterator<?> i = l.get_iterator();

        while (i.has_next()) {
            o = i.get_next();
            System.out.println(o);
        }
    }

    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<String>();
        names.insert("Asha");
        LinkedList<Integer> nums = new LinkedList<Integer>();
        nums.insert(7);

        printList(names);
        printList(nums);
    }
}

Asha
7

Same result as the generic method, with no quantifier to write. The compiler even knows that anything coming out of a ? list is at least an Object, which is why Object o = i.get_next() is legal.

Variables of a wildcard type, and the one restriction

You may declare a variable LinkedList<?> l and point it at a list of strings. But you must be careful about putting things in: the compiler cannot guarantee that the thing matches the unknown element type.

public class Main {
    public static void main(String[] args) {
        LinkedList<?> l = new LinkedList<String>();   // allowed: a variable of a wildcard type
        l.insert(new Object());                       // but we may not put things in
    }
}

Main.java:4: error: incompatible types: Object cannot be converted to CAP#1
        l.insert(new Object());                       // but we may not put things in
                 ^
  where CAP#1 is a fresh type-variable:
    CAP#1 extends Object from capture of ?
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Two things are still allowed: inserting null (it belongs to every type) and reading, which gives you an Object:

public class Main {
    public static void main(String[] args) {
        LinkedList<?> l = new LinkedList<String>();
        l.insert(null);                               // null belongs to every type
        Object o = l.head();                          // reading gives an Object
        System.out.println(o);
    }
}

null

3.6Bounded wildcards

Suppose Circle, Square and Rectangle all extend Shape, which has draw() that every subclass overrides. We want drawAll to take a list of anything Shape-compatible. Put a bound on the wildcard: LinkedList<? extends Shape>.

public class Main {
    public static void drawAll(LinkedList<? extends Shape> l) {
        Object o;
        Iterator<? extends Shape> i = l.get_iterator();

        while (i.has_next()) {
            o = i.get_next();
            o.draw();                                 // the lecture's body
        }
    }

    public static void main(String[] args) { }
}

Main.java:8: error: cannot find symbol
            o.draw();                                 // the lecture's body
             ^
  symbol:   method draw()
  location: variable o of type Object
1 error

That is exactly the point of the bound: with ? extends Shape the compiler knows every element is at least a Shape, so the local variable should be a Shape:

public class Main {
    public static void drawAll(LinkedList<? extends Shape> l) {
        Iterator<? extends Shape> i = l.get_iterator();

        while (i.has_next()) {
            Shape s = i.get_next();                   // anything in the list is at least a Shape
            s.draw();
        }
    }

    public static void main(String[] args) {
        LinkedList<Circle> circles = new LinkedList<Circle>();
        circles.insert(new Circle());
        LinkedList<Square> squares = new LinkedList<Square>();
        squares.insert(new Square());

        drawAll(circles);
        drawAll(squares);
    }
}

circle
square

3.7Copying a list: extends and super

The slide's goal is listcopy: copy every element of one list into another. The source must hold things that fit into the target. As written, the slide's header <? extends T, T> is not legal Java: a wildcard cannot be declared in the quantifier list.

public class Main {
    public static <? extends T, T> void listcopy(LinkedList<?> src, LinkedList<T> tgt) { }

    public static void main(String[] args) { }
}

Main.java:2: error: <identifier> expected
    public static <? extends T, T> void listcopy(LinkedList<?> src, LinkedList<T> tgt) { }
                   ^
Main.java:2: error: <identifier> expected
    public static <? extends T, T> void listcopy(LinkedList<?> src, LinkedList<T> tgt) { }
                              ^
Main.java:2: error: ';' expected
    public static <? extends T, T> void listcopy(LinkedList<?> src, LinkedList<T> tgt) { }
                                 ^
3 errors

Wildcards go inside the parameter types, and the variable they bound is declared normally. Here the bound is on the source list, and the loop inserts what it reads into the target. The second version reverses the constraint with super: the target may be a list of any supertype of T:

public class Main {
    // reads from src (a producer of T's), writes to tgt
    public static <T> void listcopy(LinkedList<? extends T> src, LinkedList<T> tgt) {
        Iterator<? extends T> i = src.get_iterator();
        while (i.has_next()) {
            tgt.insert(i.get_next());
        }
    }

    // the constraint reversed with super: tgt may be a list of any supertype of T
    public static <T> void listcopy2(LinkedList<T> src, LinkedList<? super T> tgt) {
        Iterator<T> i = src.get_iterator();
        while (i.has_next()) {
            tgt.insert(i.get_next());
        }
    }

    public static void main(String[] args) {
        LinkedList<Circle> circles = new LinkedList<Circle>();
        circles.insert(new Circle());
        circles.insert(new Circle());

        LinkedList<Shape> shapes = new LinkedList<Shape>();
        listcopy(circles, shapes);                    // Circle extends Shape
        System.out.println(shapes.size());

        LinkedList<Object> things = new LinkedList<Object>();
        listcopy2(circles, things);                   // Object is a supertype of Circle
        System.out.println(things.size());
    }
}

2
2

The wrong direction (shapes into a list of circles) is refused:

public class Main {
    public static <T> void listcopy(LinkedList<? extends T> src, LinkedList<T> tgt) { }

    public static void main(String[] args) {
        LinkedList<Shape> shapes = new LinkedList<Shape>();
        LinkedList<Circle> circles = new LinkedList<Circle>();

        listcopy(shapes, circles);                    // a list of Shapes into a list of Circles
    }
}

Main.java:8: error: method listcopy in class Main cannot be applied to given types;
        listcopy(shapes, circles);                    // a list of Shapes into a list of Circles
        ^
  required: LinkedList<? extends T>,LinkedList<T>
  found:    LinkedList<Shape>,LinkedList<Circle>
  reason: inference variable T has incompatible bounds
    equality constraints: Circle
    lower bounds: Shape
  where T is a type-variable:
    T extends Object declared in method <T>listcopy(LinkedList<? extends T>,LinkedList<T>)
1 error

3.8Extra: which wildcard when? "producer extends, consumer super"

public class Main {
    public static void main(String[] args) {
        LinkedList<Circle> circles = new LinkedList<Circle>();
        circles.insert(new Circle());

        LinkedList<? extends Shape> producer = circles;   // good for reading
        Shape s = producer.head();                        // ok: it is at least a Shape
        s.draw();
        // producer.insert(new Circle());                  // not allowed: which kind of Shape list is it?

        LinkedList<? super Circle> consumer = new LinkedList<Shape>();   // good for writing
        consumer.insert(new Circle());                    // ok: a Circle fits any supertype list
        Object o = consumer.head();                       // reading only gives an Object
        System.out.println(o instanceof Circle);
    }
}

circle
true

And you cannot write into a producer:

public class Main {
    public static void main(String[] args) {
        LinkedList<? extends Shape> producer = new LinkedList<Circle>();
        producer.insert(new Circle());
    }
}

Main.java:4: error: incompatible types: Circle cannot be converted to CAP#1
        producer.insert(new Circle());
                        ^
  where CAP#1 is a fresh type-variable:
    CAP#1 extends Shape from capture of ? extends Shape
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

3.9Lecture summary

• Java generics are not covariant, unlike arrays.
• You cannot substitute Object for T to get the most general type.
• Instead use a type quantifier <T> or the wildcard ?.
• A wildcard fits wherever T is not required inside the function: not for the return type, not to declare local variables.
• Wildcards can be bounded: LinkedList<? extends T> and LinkedList<? super T>.

So far a program only uses its classes. Reflection lets a program look at its own structure while it runs: which class is this object, which methods does the class have, call that one. Tools such as IDEs and debuggers are built on it.

4.1What reflection is

Wikipedia, as the lecture quotes it: reflection is "the ability of a process to examine, introspect, and modify its own structure". Two components:

4.2Introspection: which class is this object?

When the class is known in advance, instanceof is enough:

public class Main {
    public static void main(String[] args) {
        Employee e = new Manager("Ravi", 2000, "Meena");
        if (e instanceof Manager) {                       // we knew the class in advance
            System.out.println("e is a Manager");
        }
        System.out.println(e instanceof Employee);         // a Manager is also an Employee
    }
}

e is a Manager
true

Now the harder question: write classequal(o1, o2), true exactly when both objects belong to the same class. Two ideas fail:

• instanceof: we would have to test against every class that exists, and that set is not even fixed.
• A generic type variable: o1 instanceof T is syntactically disallowed (Lecture 5 explains why).

getClass()

Every object can say what its class is: getClass() returns an object of type Class that encodes the class information. Compare two such objects with ==:

public class Main {
    public static boolean classequal(Object o1, Object o2) {
        return o1.getClass() == o2.getClass();            // java.lang: no import needed
    }

    public static void main(String[] args) {
        Employee a = new Employee("Asha", 1000);
        Employee b = new Employee("Meena", 1500);
        Employee m = new Manager("Ravi", 2000, "Meena");

        System.out.println(classequal(a, b));
        System.out.println(classequal(a, m));              // an Employee and a Manager
        System.out.println(classequal("x", "y"));
        System.out.println(m instanceof Employee);         // instanceof is true for subclasses ...
        System.out.println(m.getClass() == Employee.class); // ... getClass() is the exact class
    }
}

true
false
true
true
false

import java.lang.reflect;

public class Main {
    public static void main(String[] args) { }
}

Main.java:1: error: cannot find symbol
import java.lang.reflect;
                ^
  symbol:   class reflect
  location: package java.lang
1 error

4.3The class Class

For each class the JVM has loaded, Java creates one object of type Class with the information about it. This is reification: representing an abstract idea (the class) in a concrete form (an object you can hold, pass and query). It is also why == works on class objects: there is exactly one per class.

public class Main {
    public static void main(String[] args) {
        Employee e = new Manager("Ravi", 2000, "Meena");
        Class c = e.getClass();                            // an object of the class Class
        System.out.println(c.getName());
        System.out.println(c.getSuperclass().getName());
        System.out.println(c.getSuperclass().getSuperclass().getName());

        Employee other = new Manager("Asha", 1000, "Sam");
        System.out.println(c == other.getClass());         // one Class object per class
    }
}

Manager
Employee
java.lang.Object
true

Creating objects at run time

From a Class object we can build a new instance of that class: "make another object like this one". The lecture calls c.newInstance(). That method works, but has been deprecated since Java 9 (the compiler warns); the replacement goes through the no-argument constructor:

public class Main {
    public static void main(String[] args) throws Exception {
        Plain p = new Plain();
        Class c = p.getClass();
        Object o = c.newInstance();                        // the lecture's call
        System.out.println(o);
    }
}

a Plain made at run time

Note: Main.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.

public class Main {
    public static void main(String[] args) throws Exception {
        Plain p = new Plain();
        Class<?> c = p.getClass();
        Object o = c.getDeclaredConstructor().newInstance();       // the modern spelling
        System.out.println(o);

        Object o2 = Class.forName("Plain").getDeclaredConstructor().newInstance();   // from a name
        System.out.println(o2);
    }
}

a Plain made at run time
a Plain made at run time

Also the second form: a class can be found by its name as a string, so the name can come from a file, a menu, or the network. That is how plug-in systems load classes they never saw at compile time. (The lecture's one-liner is Class.forName("Manager").newInstance(); either way the class needs a constructor with no arguments, which is why the example class here is a plain one.)

If the name matches no class, the program stops with ClassNotFoundException:

public class Main {
    public static void main(String[] args) throws Exception {
        Object o = Class.forName("NoSuchClass").getDeclaredConstructor().newInstance();
    }
}

Exception in thread "main" java.lang.ClassNotFoundException: NoSuchClass
	at java.base/jdk.internal.loader.BuiltinClassLoader.loadClass(BuiltinClassLoader.java:641)
	at java.base/jdk.internal.loader.ClassLoaders$AppClassLoader.loadClass(ClassLoaders.java:188)
	at java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:526)
	at java.base/java.lang.Class.forName0(Native Method)
	at java.base/java.lang.Class.forName(Class.java:423)
	at java.base/java.lang.Class.forName(Class.java:414)
	at Main.main(Main.java:3)

public class Main {
    public static void main(String[] args) {
        Object o = Class.forName("Plain").newInstance();
    }
}

Main.java:3: error: unreported exception ClassNotFoundException; must be caught or declared to be thrown
        Object o = Class.forName("Plain").newInstance();
                                ^
Main.java:3: error: unreported exception InstantiationException; must be caught or declared to be thrown
        Object o = Class.forName("Plain").newInstance();
                                                     ^
Note: Main.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
2 errors

4.4Constructors, methods and fields

From the Class object we can extract details about the class's constructors, methods and fields. Each of these has structure of its own:

Each returns an array. This listing prints the constructor parameters, then the methods, then the fields of Employee (which has a private name, a protected salary and a public level):

import java.lang.reflect.Constructor;
import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Class<?> c = Employee.class;

        Constructor<?>[] constructors = c.getConstructors();      // public constructors
        for (int i = 0; i < constructors.length; ++i) {
            Class<?>[] params = constructors[i].getParameterTypes();
            System.out.println("constructor takes " + Arrays.toString(params));
        }

        Method[] methods = c.getDeclaredMethods();               // declared in Employee itself
        Arrays.sort(methods, (a, b) -> a.getName().compareTo(b.getName()));
        for (Method m : methods) {
            System.out.println("method " + m.getName() + " returns " + m.getReturnType() + " takes " + Arrays.toString(m.getParameterTypes()));
        }

        Field[] fields = c.getFields();                          // public fields only
        for (Field f : fields) {
            System.out.println("field " + f.getName() + " : " + f.getType());
        }
    }
}

constructor takes [class java.lang.String, double]
method bonus returns double takes [float]
method getName returns class java.lang.String takes []
method secret returns void takes []
field level : int

• The constructor list shows only the public constructors (getConstructors()).
• The method list uses getDeclaredMethods() here, so it includes the private secret (more in 4.6). The lecture's getMethods() would list only public methods, but including those inherited from Object (toString, hashCode, wait ...).
• The field list shows only the public field level (getFields()).

public class Main {
    public static void main(String[] args) {
        Class<?> c = Employee.class;
        System.out.println(c.getDeclaredMethods().length);   // only what Employee itself declares
        System.out.println(c.getMethods().length);           // public ones, including those inherited from Object
    }
}

3
11

That is 3 methods declared in Employee versus 11 public methods including the inherited ones. So never rely on a fixed index like the slide's methods[3]: the order is not specified. Look methods up by name and parameter types instead (next section).

4.5Intercession: invoke methods, read and write fields

• method.invoke(obj, args): call that method on obj with the argument array args.
• field.get(obj): read the field's value from obj.
• field.set(obj, value): write it.

import java.lang.reflect.Field;
import java.lang.reflect.Method;

public class Main {
    public static void main(String[] args) throws Exception {
        Employee e = new Employee("Asha", 1000);
        Employee m = new Manager("Ravi", 2000, "Meena");

        Method bonus = Employee.class.getMethod("bonus", float.class);   // find it by name and types
        Object[] args5 = { 5.0f };
        System.out.println(bonus.invoke(e, args5));          // Employee's version
        System.out.println(bonus.invoke(m, args5));          // dispatch still sees a Manager: 1.5 times

        Field level = Employee.class.getField("level");
        System.out.println(level.get(e));                    // read the field
        level.set(e, 3);                                     // write the field
        System.out.println(e.level);
    }
}

50.0
150.0
1
3

Notice that invoking the Employee version of bonus on a Manager object still ran the Manager's code: 5% of 2000 is 100, times the Manager's 1.5, gives 150 (the Employee object gives 50 from salary 1000). invoke does ordinary dynamic dispatch.

4.6Reflection and security: private components

Can reflection see private methods and fields? The plain getters (getConstructors, getMethods, getFields) return only public members. Separate functions include the private ones:

• getDeclaredConstructors(), getDeclaredMethods(), getDeclaredFields()

Seeing a private member and using it are two different things. The listing counts the fields both ways, then tries to read the private name:

import java.lang.reflect.Field;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        Employee e = new Employee("Asha", 1000);
        Class<?> c = Employee.class;

        System.out.println(c.getFields().length);            // public fields: just level
        System.out.println(c.getDeclaredFields().length);    // all declared fields, private too

        Field name = c.getDeclaredField("name");
        System.out.println(name.get(e));
    }
}

1
3
Exception in thread "main" java.lang.IllegalAccessException: class Main cannot access a member of class Employee with modifiers "private"
	at java.base/jdk.internal.reflect.Reflection.newIllegalAccessException(Reflection.java:394)
	at java.base/java.lang.reflect.AccessibleObject.checkAccess(AccessibleObject.java:714)
	at java.base/java.lang.reflect.Field.checkAccess(Field.java:1156)
	at java.base/java.lang.reflect.Field.get(Field.java:441)
	at Main.main(Main.java:13)

Reading it is refused with IllegalAccessException. Access to private components can be restricted by external security policies (the lecture's point: this should not be open to every program). In ordinary code though, a program may explicitly lift the check on its own classes with setAccessible(true) (extra):

import java.lang.reflect.Field;

public class Main {
    public static void main(String[] args) throws Exception {
        Employee e = new Employee("Asha", 1000);
        Field name = Employee.class.getDeclaredField("name");

        name.setAccessible(true);                            // ask the JVM to lift the access check
        System.out.println(name.get(e));
        name.set(e, "Changed");
        System.out.println(e.getName());
    }
}

Asha
Changed

That works for your own classes. The JDK's internal classes are protected by the module system, which refuses even this:

import java.lang.reflect.Field;

public class Main {
    public static void main(String[] args) throws Exception {
        Field f = String.class.getDeclaredField("value");     // the char storage inside java.lang.String
        f.setAccessible(true);                                 // allowed for your own classes, not for the JDK's
    }
}

Exception in thread "main" java.lang.reflect.InaccessibleObjectException: Unable to make field private final byte[] java.lang.String.value accessible: module java.base does not "opens java.lang" to unnamed module @15db9742
	at java.base/java.lang.reflect.AccessibleObject.throwInaccessibleObjectException(AccessibleObject.java:391)
	at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:367)
	at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:315)
	at java.base/java.lang.reflect.Field.checkCanSetAccessible(Field.java:183)
	at java.base/java.lang.reflect.Field.setAccessible(Field.java:177)
	at Main.main(Main.java:6)

4.7Using reflection: BlueJ

The lecture's example is BlueJ, a beginner's Java environment. It defines and compiles classes, then lets you create objects, invoke methods and examine state for the compiled code. It does this through Java's reflective capabilities, so BlueJ need not keep its own "debugging" information about each class.

4.8Limitations of Java reflection

Java reflection can inspect and use classes but cannot create or modify classes at run time. This is not possible:

public class Main {
    public static void main(String[] args) {
        Class c = new Class();
    }
}

Main.java:3: error: constructor Class in class Class<T> cannot be applied to given types;
        Class c = new Class();
                  ^
  required: ClassLoader,Class
  found:    no arguments
  reason: actual and formal argument lists differ in length
  where T is a type-variable:
    T extends Object declared in class Class
1 error

• An environment like BlueJ must invoke the Java compiler before it can use a new class.
• Contrast with Python: a class XYZ: statement can be executed at run time. Other object-oriented languages such as Smalltalk let you redefine methods at run time.

4.9Lecture summary

• Reflection = introspection (observe own state) + intercession (modify behaviour).
• getClass() gives the Class object; reification turns class information into data.
• Class lets you create instances (newInstance, forName) and list constructors, methods and fields.
• invoke, get and set use what was found.
• getDeclared... includes private members; access may be restricted by policy.
• Java cannot create or modify classes at run time.

Generics are checked by the compiler, but the running program does not see them: the type arguments are erased. That one fact explains a list of restrictions that look arbitrary until you see the cause. The lecture closes with the other consequence: generics work only with objects, so basic types need wrapper classes.

5.1Type erasure

The lecture writes the result as "LinkedList<T> becomes LinkedList<Object>" and "LinkedList<? extends Shape> becomes LinkedList<Shape>". That is a handy picture, but the precise statement is that the class itself loses its arguments (it is just LinkedList) and the type variable inside it is replaced by its bound: Object for a plain T, Shape for T extends Shape. A look through reflection confirms the bound:

public class Box<T extends Shape> {
    private T item;
    public void put(T x) { item = x; }
    public T get() { return item; }
}

import java.lang.reflect.Method;

public class Main {
    public static void main(String[] args) throws Exception {
        Method m = Box.class.getMethod("get");
        System.out.println(m.getReturnType().getName());          // erased to the upper bound
        Method p = Box.class.getMethod("put", Shape.class);
        System.out.println(p.getParameterTypes()[0].getName());
    }
}

Shape
Shape

5.2What erasure forbids

1. instanceof with a parameterised type, or with T

Since no information about T is preserved, the program cannot ask whether an object is a list of strings:

public class Main {
    public static void main(String[] args) {
        Object s = new LinkedList<String>();
        if (s instanceof LinkedList<String>) { }
    }
}

Main.java:4: error: Object cannot be safely cast to LinkedList<String>
        if (s instanceof LinkedList<String>) { }
            ^
1 error

public class Main {
    public static <T> void check(Object o) {
        if (o instanceof T) { }
    }

    public static void main(String[] args) { }
}

Main.java:3: error: Object cannot be safely cast to T
        if (o instanceof T) { }
            ^
  where T is a type-variable:
    T extends Object declared in method <T>check(Object)
1 error

What is allowed (extra): ask about the class alone, with the wildcard or the raw name, which claims nothing about the element type:

public class Main {
    public static void main(String[] args) {
        Object o = new LinkedList<String>();
        System.out.println(o instanceof LinkedList<?>);       // allowed: nothing is claimed about the element type
        System.out.println(o instanceof LinkedList);          // the raw class works too
    }
}

true
true

2. Erasure and overloading

The comparison below is true: the two lists have the same run-time class (this is the lecture's test, with real classes).

public class Main {
    public static void main(String[] args) {
        Object o1 = new LinkedList<Employee>();
        Object o2 = new LinkedList<Date>();

        if (o1.getClass() == o2.getClass()) {
            System.out.println("same class at run time");
        }
        System.out.println(o1.getClass().getName());
    }
}

same class at run time
LinkedList

A consequence: two methods whose signatures differ only in the type argument have the same signature after erasure, so they cannot overload each other:

public class Example {
    public void printlist(LinkedList<String> strList) { }
    public void printlist(LinkedList<Date> dateList) { }
}

Example.java:3: error: name clash: printlist(LinkedList<Date>) and printlist(LinkedList<String>) have the same erasure
    public void printlist(LinkedList<Date> dateList) { }
                ^
1 error

3. Arrays and generics

Remember the array covariance hole from Lecture 3. To avoid something similar, Java lets you declare a generic array T[] newarray but not create one:

public class Box<T> {
    private T[] items;

    public Box() {
        items = new T[100];                  // not allowed
    }
}

Box.java:5: error: generic array creation
        items = new T[100];                  // not allowed
                ^
1 error

Why? An array must know its real element type to run the ArrayStoreException check, but T is gone at run time, so there is nothing to put in the array object.

The ugly workaround

Create an Object[] and cast it: (T[]) new Object[100]. It compiles with a warning, and works as long as the array stays private to the class:

public class Box<T> {
    private T[] items;

    public Box() {
        items = (T[]) new Object[100];
    }
}

Note: Box.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

public class Box<T> {
    private T[] items;

    @SuppressWarnings("unchecked")
    public Box() {
        items = (T[]) new Object[100];       // the workaround: a cast, checked by nobody
    }

    public void put(int i, T x) { items[i] = x; }
    public T get(int i) { return items[i]; }
}

public class Main {
    public static void main(String[] args) {
        Box<String> b = new Box<String>();
        b.put(0, "hello");
        System.out.println(b.get(0));
    }
}

hello

The warning is real. The cast is not checked at run time, so if the class ever hands the array out typed as T[], the caller's Integer[] view meets an Object[] and fails (extra):

public class Main {
    public static void main(String[] args) {
        Box<Integer> b = new Box<Integer>();
        Integer[] a = b.raw();               // the compiler trusts T = Integer; at run time the array is Object[]
    }
}

Exception in thread "main" java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.Integer; ([Ljava.lang.Object; and [Ljava.lang.Integer; are in module java.base of loader 'bootstrap')
	at Main.main(Main.java:4)

5.3Wrapper classes

Because of erasure every type variable becomes Object at run time, and the basic types int, float, ... are not objects. So a type argument cannot be a basic type: no LinkedList<int>, no LinkedList<double>.

public class Main {
    public static void main(String[] args) {
        LinkedList<int> nums = new LinkedList<int>();
    }
}

Main.java:3: error: unexpected type
        LinkedList<int> nums = new LinkedList<int>();
                   ^
  required: reference
  found:    int
Main.java:3: error: unexpected type
        LinkedList<int> nums = new LinkedList<int>();
                                              ^
  required: reference
  found:    int
2 errors

The fix: each basic type has a wrapper class that holds one value of that type as an object (Integer for int, Double for double, Boolean, Character, ...). All wrappers other than Boolean and Character extend the class Number:

public class Main {
    public static void main(String[] args) {
        System.out.println(Number.class.isAssignableFrom(Integer.class));
        System.out.println(Number.class.isAssignableFrom(Double.class));
        System.out.println(Number.class.isAssignableFrom(Boolean.class));
        System.out.println(Number.class.isAssignableFrom(Character.class));
    }
}

true
true
false
false

Converting by hand

The slide shows Integer myx = Integer(x); to wrap and myx.intValue() to unwrap. The unwrap half is right (and so are byteValue(), doubleValue(), ...). The wrap half is not valid Java, because Integer(x) is not a method:

public class Main {
    public static void main(String[] args) {
        int x = 5;
        Integer myx = Integer(x);
    }
}

Main.java:4: error: cannot find symbol
        Integer myx = Integer(x);
                      ^
  symbol:   method Integer(int)
  location: class Main
1 error

The working spellings are Integer.valueOf(x) (preferred). new Integer(x) also compiles, but the constructor is deprecated for removal and the compiler warns:

public class Main {
    public static void main(String[] args) {
        int x = 5;
        Integer myx = new Integer(x);
    }
}

Main.java:4: warning: [removal] Integer(int) in Integer has been deprecated and marked for removal
        Integer myx = new Integer(x);
                      ^
1 warning

Autoboxing

public class Main {
    public static void main(String[] args) {
        int x = 5;
        Integer myx = Integer.valueOf(x);       // basic type -> wrapper
        int y = myx.intValue();                 // wrapper -> basic type
        System.out.println(y + " " + myx.doubleValue());

        Integer a = x;                          // autoboxing: the compiler writes valueOf for us
        int b = a;                              // unboxing: and intValue here
        System.out.println(a + b);

        Number n = 3.5;                         // Double extends Number
        System.out.println(n.intValue());
    }
}

5 5.0
10
3

So wrapper types are what you use in generic data structures, and autoboxing hides the conversion at the call site:

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> nums = new LinkedList<Integer>();
        nums.insert(5);                 // 5 is boxed to an Integer
        nums.insert(7);
        nums.insert(9);

        int total = 0;
        Iterator<Integer> i = nums.get_iterator();
        while (i.has_next()) {
            total += i.get_next();      // each Integer is unboxed
        }
        System.out.println(total);
    }
}

21

5.4Extra: two boxing traps

== on wrappers compares references

public class Main {
    public static void main(String[] args) {
        Integer a = 127, b = 127;
        Integer c = 1000, d = 1000;
        System.out.println(a == b);             // small values are cached: the same object
        System.out.println(c == d);             // large ones are not: two objects
        System.out.println(c.equals(d));        // compare wrappers with equals
    }
}

true
false
true

The first comparison is true only because small values (about -128 to 127) are cached and shared; larger ones are separate objects. Compare wrappers with equals(), exactly as in Lecture 1.

Unboxing null

public class Main {
    public static void main(String[] args) {
        Integer n = null;
        int x = n;                              // unboxing null
    }
}

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because "<local1>" is null
	at Main.main(Main.java:4)

A wrapper variable can be null; an int cannot. Unboxing a null throws a NullPointerException.

5.5Extra: raw types, the back door

Erasure also explains how old, pre-generics code still works: the raw name LinkedList (no argument) is still legal. Through it you can bypass the element check; the compiler only warns. The mistake then surfaces later, at an innocent line where the compiler had inserted a cast:

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<String>();
        LinkedList raw = names;                  // a raw type: the type parameter is dropped
        raw.insert(42);                          // compiles (with a warning): nobody checks

        String s = names.head();                 // the compiler inserted a cast to String
    }
}

Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
	at Main.main(Main.java:7)

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

5.6Lecture summary

• Information about type variables is erased at run time: LinkedList<T> becomes LinkedList<Object>, or the bound.
• That limits reflection on generic types: you cannot write o instanceof LinkedList<String> or o instanceof T.
• You cannot overload using different instantiations of one generic type.
• You cannot instantiate arrays of a generic type.
• Built-in types must be boxed in wrapper types to be used with generics.

What is likely to be asked from Week 5, with 30-second answers, deeper explanations, a lecture-or-extra tag on each question, and code you can run.

Week 5 is the generics week, and interviewers love it: why generics exist, erasure, arrays versus generics, wildcards (extends and super), the "no generic arrays" rule, and the boxing traps. Every answer starts with a 30-second version. Each question is tagged From the lecture or Extra.

6.1Interview heat-map: what is most likely

6.2Generics and subtyping

LinkedList list = new LinkedList();   // holds Object
list.insert(new Ticket());
list.insert(new Date());          // nothing stops this
Ticket t = (Ticket) list.head();  // ClassCastException here

Exception in thread "main" java.lang.ClassCastException: class Date cannot be cast to class Ticket (Date and Ticket are in unnamed module of loader 'app')

Exception in thread "main" java.lang.ArrayStoreException: Ticket

Main.java:4: error: incompatible types: LinkedList<String> cannot be converted to LinkedList<Object>

static <T> void listcopy(LinkedList<? extends T> src,   // reads from src: extends
                          LinkedList<T> tgt) {
    ...
}

Main.java:4: error: incompatible types: Circle cannot be converted to CAP#1

static <T> void printList(LinkedList<T> l)   // T never used inside
static void printList(LinkedList<?> l)     // same, shorter

public class LinkedList<T> {
    public <T> void insert(T newdata) {   // a NEW T
        Node n = new Node(newdata);        // Node wants the class T
    }
}

LinkedList.java:6: error: incompatible types: T#1 cannot be converted to T#2

public static <T extends Comparable<T>> T max(T a, T b) {
    return a.compareTo(b) >= 0 ? a : b;
}

9  pear  2.5

6.3Erasure and arrays

same class at run time
LinkedList

Box.java:5: error: generic array creation

items = (T[]) new Object[100];   // warning: unchecked cast

Main.java:4: error: Object cannot be safely cast to LinkedList<String>

true  true

public class Example {
    public void printlist(LinkedList<String> strList) { }
    public void printlist(LinkedList<Date> dateList) { }
}

error: name clash: printlist(LinkedList<Date>) and printlist(LinkedList<String>) have the same erasure

LinkedList<String> names = new LinkedList<String>();
LinkedList raw = names;                  // a raw type: the type parameter is dropped
raw.insert(42);                          // compiles (with a warning): nobody checks

String s = names.head();                 // the compiler inserted a cast to String

Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')

Exception in thread "main" java.lang.ArrayStoreException: Date

no error: only nulls were copied

6.4Boxing and equality

Main.java:3: error: unexpected type

Integer a = 5;     // autoboxing: Integer.valueOf(5)
int b = a;         // unboxing:   a.intValue()

true  false  true

-1  1

true  false  true

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
nums.remove(1);                     // index 1
nums.remove(Integer.valueOf(30));   // the value 30

[10, 30]  [10]

6.5Reflection and polymorphism

true  false  true  true  false

true  false  true  true  false

1  3

Exception in thread "main" java.lang.IllegalAccessException: class Main cannot access a member of class Employee with modifiers "private"

Asha  Changed

Object o = Class.forName("Plain").getDeclaredConstructor().newInstance();

a Plain made at run time

Exception in thread "main" java.lang.ClassNotFoundException: NoSuchClass

Week 5 on one page: a lecture-by-lecture glance, key terms, the pairs to tell apart, the errors you can now read, a checklist and corrections to the source notes.

7.1Week 5 at a glance