Transcript Ch. 21 Generics

Chapter 21 Generics
Chapter 11 Object-Oriented Design
Chapter 20 Lists, Stacks, Queues, Trees, and Heaps
Chapter 21 Generics
Chapter 22 Java Collections Framework
Chapter 19 Recursion
Chapter 23 Algorithm Efficiency and Sorting
1
Objectives









To use generic classes and interfaces (§21.2).
To declare generic classes and interfaces (§21.3).
To understand why generic types can improve reliability
and robustness (§21.3).
To declare and use generic methods and bounded generic
types (§21.4).
To use raw types for backward compatibility (§21.5).
To know wildcard types and understand why they are
necessary (§21.6).
To understand that all instances of a generic class share the
same runtime class file (§21.7).
To convert legacy code using JDK 1.5 generics (§21.8).
To design and implement a generic matrix class (§21.9).
2
Example: Pre_Java5
3
See these warnings before?
Warnings from last compilations
<program> uses unchecked or unsafe operations
Recompile with –Xlint unchecked for details
4
Why Do You Get a Warning?
public class TestArrayList {
public static void main(String[] args) {
// Create a list to store cities
java.util.ArrayList cityList = new java.util.ArrayList();
// Add some cities in the list
cityList.add("London");
}
To understand the compile
}
warning on this line, you need to
learn JDK 1.5 generics.
5
ArrayList
public ArrayList() Constructs an empty list with an initial
capacity of ten.
add
public boolean add(E e) Appends the specified element to the end
of this list.
Specified by:add in interface Collection<E>Specified by:add in
interface List<E>Overrides:add in class AbstractList<E>
Parameters:e - element to be appended to this list Returns:true
(as specified by Collection.add(E))
6
Generic Type
package java.lang;
package java.lang;
public interface Comaprable {
public int compareTo(Object o)
}
public interface Comaprable<T> {
public int compareTo(T o)
}
(b) JDK 1.5
(a) Prior to JDK 1.5
Runtime error
Comparable c = new Date();
System.out.println(c.compareTo("red"));
Generic Instantiation
Comparable<Date> c = new Date();
System.out.println(c.compareTo("red"));
(a) Prior to JDK 1.5
Improves
reliability
Restricts
to type
Date
(b) JDK 1.5
Compile error
7
Generic ArrayList in JDK 1.5
java.util.ArrayList
java.util.ArrayList<E>
+ArrayList()
+ArrayList()
+add(o: Object) : void
+add(o: E) : void
+add(index: int, o: Object) : void
+add(index: int, o: E) : void
+clear(): void
+clear(): void
+contains(o: Object): boolean
+contains(o: Object): boolean
+get(index: int) : Object
+get(index: int) : E
+indexOf(o: Object) : int
+indexOf(o: Object) : int
+isEmpty(): boolean
+isEmpty(): boolean
+lastIndexOf(o: Object) : int
+lastIndexOf(o: Object) : int
+remove(o: Object): boolean
+remove(o: Object): boolean
+size(): int
+size(): int
+remove(index: int) : boolean
+remove(index: int) : boolean
+set(index: int, o: Object) : Object
+set(index: int, o: E) : E
(a) ArrayList before JDK 1.5
(b) ArrayList in JDK 1.5
8
Fix the Warning in BJ_Java5
import java.util.*;
public class TestArrayListNew {
public static void main(String[] args) {
ArrayList<String> cityList = new ArrayList<String>();
// Add some cities in the list
cityList.add("London"); }
}
Tells compiler that Strings are
expected.
No compile warning on this line.
9
No Casting Needed – Boxing and Unboxing
ArrayList<Double> list = new ArrayList<Double>();
list.add(5.5); // 5.5 is automatically converted to new Double(5.5)
list.add(3.0); // 3.0 is automatically converted to new Double(3.0)
Double doubleObject = list.get(0); // No casting is needed
double d = list.get(1); // Automatically converted to double
10
Declaring Generic Classes and Interfaces
GenericStack<E>
-elements: E[]
An array to store elements.
-size: int
The number of the elements in this stack.
+GenericStack()
Creates an empty stack with default initial capacity 16.
+GenericStack(initialCapacity:
int)
Creates an empty stack with the specified initial
capacity.
+getSize(): int
Returns the number of elements in this stack.
+peek(): E
Returns the top element in this stack.
+pop(): E
Returns and removes the top element in this stack.
+push(o: E): E
Adds a new element to the top of this stack.
+isEmpty(): boolean
Return true if the stack is empty.
BJ_GenericStack
11
To print elements of different types
Before Java5
public class PreJava5MethodDemo {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York", "Austin"};
PreJava5MethodDemo.print(integers);
PreJava5MethodDemo.print(strings);
}
// Provide two overloaded methods
public static void print(Integer[] list) { // . . . }
public static void print(String[] list) { // . . . }
}
12
To print elements of different types
From Java5 with Generic Methods
public class GenericMethodDemo {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York", "Austin"};
GenericMethodDemo.<Integer>print(integers);
GenericMethodDemo.<String>print(strings);
}
public static <E> void print(E[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
}
13
Generic Methods
public static <E> void print(E[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}// versus
public static void print(Object[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
14
Can I specify the type as say <F>?
public class GenericMethodDemoF {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York", "Austin"};
GenericMethodDemo.<Integer>print(integers);
GenericMethodDemo.<String>print(strings);
}
public static <F> void print(F[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
}
15
Can I specify subtypes?
Suppose we want to restrict to Circle and Rectangle objects
only in class BoundedTypeDemo
16
Bounded Generic Type
public static void main(String[] args ) {
Rectangle rectangle = new Rectangle(2, 2);
Circle9 circle = new Circle9(2);
System.out.println("Same area? " + equalArea(rectangle,
circle));
}
// Want to restrict to subclasses of GeometricObject
public static <E extends GeometricObject> boolean
equalArea(E object1, E object2) {
return object1.findArea() == object2.findArea();
}
17
Bounded Generic Type
 See
BJ_BoundedType
18
Raw Type and Backward
Compatibility
// raw type
GenericStack stack = new GenericStack();
This is roughly equivalent to
GenericStack<Object> stack = new GenericStack<Object>();
19
Raw Type: Compile? Run? Safe? Why?
// Max.java: Find a maximum object
public class Max {
/** Return the maximum between two objects */
public static Comparable max(Comparable o1, Comparable o2) {
if (o1.compareTo(o2) > 0)
return o1;
else
return o2;
} // see also the code in BJ_Max around compareTo
public static void main(String[] args) {
System.out.println("max is " + Max.max("Welcome", 23));
Max.max("Welcome",
23);
}
}
20
Runtime Exception on running
class Max:
Exception in thread "main" java.lang.ClassCastException:
java.lang.Integer cannot be cast to java.lang.String
at java.lang.String.compareTo(String.java:92)
at Max.max(Max.java:9)
at Max.main(Max.java:17)
21
Make it Safe – See class BJ_Max1
// Max1.java: Find a maximum object
public class Max1 {
/** Return the maximum between two objects */
public static <E extends Comparable<E>> E max(E o1, E o2) {
if (o1.compareTo(o2) > 0)
return o1;
else
return o2;
}
}
Max.max("Welcome", 23);
22
Compilation error instead
23
Wildcards
Why wildcards are necessary? See this example.
WildCardDemo1
?
? Extends T
? Super T
WildCardDemo2
unbounded wildcard
bounded wildcard
lower bound wildcard:
WildCardDemo3
24
25
WildCardDemo1
public class WildCardDemo1 {
public static void main(String[] args ) {
GenericStack<Integer> intStack = new
GenericStack<Integer>();
intStack.push(1); // 1 is autoboxed into new Integer(1)
intStack.push(2);
intStack.push(-2);
System.out.println("The max number is " +
max(intStack));
}
26
WildCardDemo1.max
/** Find the maximum in a stack of numbers */
public static double max(GenericStack<Number> stack) {
/** intStack is an instance of GenericStack<Integer> but
NOT GenericStack<Number> */
double max = stack.pop().doubleValue(); // initialize max
while (!stack.isEmpty()) {
double value = stack.pop().doubleValue();
if (value > max)
max = value;
}
return max;
}
27
/** <?> means any subtype of Object and associated with GenericStack */
public class WildCardDemo2 {
public static void main(String[] args ) {
GenericStack<Integer> intStack = new GenericStack<Integer>();
intStack.push(1); // 1 is autoboxed into new Integer(1)
intStack.push(2);
intStack.push(-2);
print(intStack);
System.out.println();
}
// Print objects and empties the stack
public static void print(GenericStack<?> stack) {
/**
1st form: ^^^ unbounded wildcard,
same as ? extends Object */
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
}
28
/** <?> means any subtype of Object and associated with GenericStack */
public class WildCardDemo2A {
public static void main(String[] args ) {
GenericStack<Integer> intStack = new GenericStack<Integer>();
intStack.push(1); // 1 is autoboxed into new Integer(1)
intStack.push(2);
intStack.push(-2);
print(intStack);
System.out.println();
}
// Print objects and empties the stack
public static void print(GenericStack<? extends Number> stack) {
/**
2nd form: ^^^^^^^^^^^^^^^^^^ bounded wildcard,
Number or subtype */
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
}
29
WildCardDemo3 <? super T>
/** <? super T> represents type T or supertype of T */
public class WildCardDemo3 {
public static void main(String[] args) {
GenericStack<String> stack1 = new GenericStack<String>();
GenericStack<Object> stack2 = new GenericStack<Object>();
stack2.push("Java");
stack2.push(2);
stack1.push("Sun");
add(stack1, stack2);
WildCardDemo2.print(stack2);
System.out.println();
}
30
GenericStack<? super T>
/** Pop each element of stack1 and push it on stack2 */
public static <T> void add( GenericStack<T> stack1,
GenericStack<? super T> stack2) {
/** 3rd form ^^^^^^^^^^^ type T or super type of T. Here
Object is super type of String
will compile fine.*/
while (!stack1.isEmpty())
stack2.push(stack1.pop());
}
}
31
Watch out
 What
if we replace
 GenericStack<? super T> stack2) {
 in line 15 of GenericStack3 by
 GenericStack<T> stack2) {
?
 Reasoning: Only Strings are in stack1, but
String is subclass of Object. Must we declare
stack2 as GenericStack<? super T> ?
32
Answer – NO!
 Change
the code in WildCardDemo3A
 and compile
<T>add( GenericStack<T>, GenericStack<T>) in
 WildCardDemo3A cannot be applied to
 (GenericStack<java.lang.String> stack1,
 GenericStack<java.lang.Object> stack2)

33
Generic Types and Wildcard Types
Object
Object
?
? super E
A<? extends B>
E
E’s subclass
A<?>
E’s superclass
? extends E
A<B’s subclass>
A<B>
A<? super B>
A<B’s superclass>
34
Erasure and Restrictions on Generics
Implementation of Generics
- type erasure.
- Compiler uses the generic type information to
compile the code, but erases it afterwards.
- Hence generic information is not available at run
time.
- Reason: To enable the generic code to be
backward-compatible with the legacy code that uses
raw types.
35
Compile Time Checking
Example:
-Compiler checks whether generics is used
correctly for the code in (a);
-Translates it into the equivalent code in (b) for
runtime use. The code in (b) uses the raw type.
ArrayList<String> list = new ArrayList<String>();
list.add("Oklahoma");
String state = list.get(0);
(a)
ArrayList list = new ArrayList();
list.add("Oklahoma");
String state = (String)(list.get(0));
(b)
36
Important Facts
It is important to note that a generic class is
shared by all its instances regardless of its
actual generic type.
GenericStack<String> stack1 = new GenericStack<String>();
GenericStack<Integer> stack2 = new GenericStack<Integer>();
Although GenericStack<String> and
GenericStack<Integer> are two types, but there is
only one class GenericStack loaded into the JVM.
37
Restrictions on Generics

Restriction 1: Cannot Create an Instance of a Generic
Type. (i.e., new E()).

Restriction 2: Generic Array Creation is Not Allowed.
(i.e., new E[100]).

Restriction 3: A Generic Type Parameter of a Class Is
Not Allowed in a Static Context.

Restriction 4: Exception Classes Cannot be Generic.
38
Restriction 1
 Restriction
1: Cannot Create an Instance of
a Generic Type.
E
Object = new E(); // wrong
 Reason:
new E(); is run at runtime but the
generic type E is not available at runtime.
39
Restriction 2
 Restriction
2: Generic Array Creation is Not
Allowed.
 E[] elements = new E[100]; // wrong
 There is no E class
 Circumvent:
 E[] elements = (E[]) new Object[100];
 But warning is unavoidable
40
Restriction 2 example
ArrayList<String>[] list = new ArrayList<String>[10]
//wrong
ArrayList<String>[] list = (ArrayList<String>[]) new
ArrayList[10]; // to circumvent
// But still compiler warning
41
Restriction 3
 Restriction
3: A Generic Type Parameter of
a Class Is Not Allowed in a Static Context.
 Reason: All instance of a generic class have
the same runtime class, static (class)
variables and method are shared by all
instances. Hence it is illegal to refer to a
generic type parameter for a class in static
method or field.
42
Restriction 3
 public
class Teste <E> {
public static void m(E obj1) //illegal
}


– public static E obj; // illegal
}
43
Restriction 4
 Restriction
4: Exception Classes Cannot be
Generic.
 Reason: A generic class may not extend
java.util.Throwable
44
Restriction 4
public class MyException<T> extends Exception {
--} // illegal
try {
...
}
Catch (MyException<T> ex) {
...
} /* JVM would have to match the type in runtime but
the type is not available at runtime. */
45
Now repeat TestArrayList
 See
BJ_TestArrayListNew
46