Chapter 7: Generic Programming
Outline
■ Generic class
■ Generic method
■ Subtype & wildcard
■ Retrictions & limitations
■ Generic class & Inheritance
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 2/48
What is Generic Programming?
■ Generic programming means to write code that can be
reused for objects of many different types
❑ List of DictionaryEntries / pets
❑ Sorting Integers / Dictionary entries
■ Before JDK 5.0, generic programming in Java was
always achieved with inheritance.
❑ What we have been doing:
public class MyList {// items could be objects of any classes
public void add(Object o) {…}
public Object getFirst() {…}
...
}
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 3/48
Defining the idea Behind Java Generics
◼ Generic Types:
◼ “generic class or interface
◼ which is parameterized over
types”
◼ Generic Methods:
◼ “Method featuring type
parameters”
◼ [Link]
◼ [Link] is a parameterized (or
generic) type?
◼ [Link] is a parameterized (or generic)
method?
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 4/48
Why Bother?
Simplify notations (?) by
eliminating need for explicit
casting every time
List list
= new ArrayList();
[Link]("hello");
String s = (String) [Link](0);
List<String> list
= new ArrayList<String>();
[Link]("hello");
String s = [Link](0);
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 5/48
Why Bother?
Stronger Type Checking
Less bugs
?
List list = new ArrayList();
What happens if
[Link]("hello");
!
[Link](new Integer(42));
Runtime Exception
String s = (String) [Link](0);
Integer s = (Integer) [Link](1);
Integer s = (String) [Link](1);
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 6/48
Why Bother?
Encourages programmers to
write generic classes
e.g.
• Originally meant to support Java Collections
▪ A List of <Integer> has the same underlying logic as a List of
<Double>
• Usable now by anyone to produce better code
▪ Define the concept of List of <something>
1
1
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 7/48
Is it possible to
do Generic
Programming
w/o Generics?
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 8/48
Consider this…
public class Box {
private Object object;
public void set(Object object)
{ [Link] = object; }
public Object get()
{ return object; }
}
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 9/48
Let’s try it out!
public static void main(String[] argv){
Box b = new Box();
Integer n1 = new Integer(42);
[Link](n1);
Double n2 = [Link]();
}
? How do we fix
this?
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 10/48
Now, Let’s fix it!
public static void main(String[] argv){
Box b = new Box();
? What is wrong Integer n1 = new Integer(42);
with this?
[Link](n1);
Why
Bother? Double n2 = (Double)[Link]();
}
Problem = Java does not know that this
instance of Box is meant to
store only Integer objects
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 11/48
New Plan!
◼ We need a way to enable Java to
check our code for such
inconsistencies
What does this mean?
🡪 Rely on the compiler / runtime to
validate types usage
make necessary type castings
…
🡪 Add information to the code to help them do so (Add
information to the code to help the compiler/runtime do so)
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 12/48
Introducing… Generic Types! See the difference?
public class Box { public class Box<T> {
private Object object; private T t;
public void set(Object object) public void set(T t)
{ [Link] = object; } { this.t = t; }
public Object get() public T get()
{ return object; } { return t; }
} }
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 13/48
Anatomy of a Generic Type
Formal Type
Class / Interface Parameters
Section <…>
public class Box<T> {
Formal Type private T t;
Parameters
Type Variables
public void set(T t)
non-primitive type,
{ this.t = t; }
array type,
other type variable
public T get()
Used wherever a { return t; }
data type would be
}
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 14/48
Naming Conventions for Formal Type Parameters
◼ E - Element (used extensively by the Java Collections
Framework)
◼ K - Key
◼ N - Number
◼ T - Type
◼ V - Value
◼ S,U,V etc. - 2nd, 3rd, 4th types
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 15/48
How to Instantiate a Generic Class
Parameterized Type;
i.e. instantiation of a
generic type
Box<Integer> integerBox = new Box<Integer>();
Actual Type
Box<Integer> integerBox = new Box<>(); Type Argument
Argument
Since Java 7+
“Type Inference”
? What is Type
Inference?
21
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 16/48
What happens if we do not use <> at all?
Raw types!
public class Box<T> {
public void set(T t) { /* ... */ } Legacy code < JDK 5.0
// ...
}
When using raw types, you
essentially get pre-generics
Box rawBox = new Box(); behavior — a Box gives you
Objects
public class Box<T> { Type Erasure converts
parameterized types into
public void set(T t) { /* ... */ } raw types
?
// ...
} What is Type
Erasure?
Box rawBox = new Box<Integer>(); 22
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 17/48
Two problems with using inheritance
◼ 1. A cast is necessary whenever you retrieve a value:
//items could be objects of any classes
public class MyList {
public void add(Object o) {…}
public Object getFirst() {…}
}
MyList myPets = new MyList();
Animal a = (Animal) [Link]();
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 18/48
Two problems with using inheritance
▪ 2. There is no error checking. You can add objects of any class.
public c l a s s MyList { // items could be objects of any cla s s e s
public void add(Object o) {…}
public Object g e t F i r s t ( ) {…}
...
} [Link](new I n t e g e r ( 3 ) ) ;
. . .
Animal a = (Animal) [Link]();
❑ We might want an animal list to contain Cats and Cows,
but we do not want a cat list to contain Animals or Cows
■ ➔ run-time error, undesirable
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 19/48
Using generic classes
■ Many Java library classes have been made generic, they
can be used in a way that indicates the type of object they
hold.
❑ ArrayList of Cat objects <Cat> added
ArrayList<Cat> myPets = new ArrayList<Cat>();
[Link](new C a t ( ) ) ;
[Link](new C a t ( ) ) ;
[Link](new Dog()); // compile-time e r r o r ! type mismatch
Cat cat = [Link](0); // no cast required! . . .
compiler knows that add() and get()
methods take and return Cat, and so it can
do type checking at compile time
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 20/48
Generic Class
■ A generic class is a class with one or more type parameters
that indicate the element type
Type parameter T,
public c l a s s Pair<T>
enclosed in angle brackets < >
{
private T f i r s t ;
private T second;
public Pa i r ( ) { f i r s t = n u l l ; second = n u l l ; }
public Pair(T f i r s t , T second)
{ t h i s . f i r s t = f i r s t ; [Link] = second; }
public T g e t F i r s t ( ) { return f i r s t ; }
public T getSecond() { return second; }
public void s e t F i r s t ( T newValue) { f i r s t = newValue; }
public void setSecond(T newValue) { second = newValue; }
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 21/48
Example
public c l a s s Pair<T>
{
private T f i r s t ;
private T second;
public Pa i r ( ) { f i r s t = n u l l ; second = n u l l ; }
public Pair(T f i r s t , T second)
{ t h i s . f i r s t = f i r s t ; [Link] = second; }
public T g e t F i r s t ( ) { return f i r s t ; }
public T getSecond() { return second; }
public void s e t F i r s t ( T newValue) { f i r s t = newValue; }
public void setSecond(T newValue) { second = newValue; }
}
...
Pair<String> mm = new Pair<String> ( " 1 s t " , " 2 n d " ) ;
[Link]([Link]() + " , " + [Link]());
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 22/48
More than one type parameters
public c l a s s Pair<T, U>
{
private T f i r s t ;
private U second;
public Pa i r ( ) { f i r s t = n u l l ; second = n u l l ; }
public Pair(T f i r s t , U second)
{ t h i s . f i r s t = f i r s t ; [Link] = second; }
public T g e t F i r s t ( ) { return f i r s t ; }
public U getSecond() { return second; }
public void s e t F i r s t ( T newValue) { f i r s t = newValue; } public
void setSecond(U newValue) { second = newValue; }
}
...
Pa i r < S t r i n g , Integer> mm = new Pa i r < S t r i n g , Integer> ( " 1 s t " , 1 ) ;
[Link]([Link]() + " , " + [Link]());
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 23/48
Generic method
■ A generic method is one with type parameters
❑ inside an ordinary class or generic class
cla s s ArrayAlg {
public s t a t i c <T> T getMiddle(T[] a){
return a[[Link] / 2 ] ; }
}
■ Usage:
❑ Concrete type is specified in the method call
S t r i n g [ ] names = { "John", " Q . " , " P u b l i c " } ;
String middle = ArrayAlg.<String>getMiddle(names);
❑ Or concrete type can often be omitted. When?
S t r i n g [ ] names = { "John", " Q . " , " P u b l i c " } ;
String middle = [Link](names);
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 24/48
Bounds for Type parameters
c l a s s ArrayAlg {
public s t a t i c <T> T min(T[] a ) // almost correct
{
i f (a == n u l l || [Link] == 0 ) return n u l l ;
T smallest = a [ 0 ] ;
f o r ( i n t i = 1 ; i < [Link]; i + + )
i f ([Link](a[i]) > 0)
smallest = a [ i ] ;
return smallest; What if T does not provide compareTo()
} method?
}
Solution: restrict T to a class that implements the Comparable Interface — a
standard interface with a single method: compareTo().
...
public s t a t i c <T extends Comparable> T min(T[] a)
//the r e s t i s the same as before
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 25/48
Bounds for Type Parameters
Syntax: <T extends BoundingType>
■ T and BoundingType can be interface or class
❑ T is a subtype of BoundingType
■ There can be more than one BoundingType
<T extends Comparable &Serializable>
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 26/48
Bounds for Type Parameters
c l a s s ArrayAlg{
/**
Gets the minimum and maximum of an array of objects of type T.
@param a an array of objects of type T
@return a p a i r with the min and max value, or
n u l l i f a i s n u l l or empty
*/
public s t a t i c <T extends Comparable> Pair<T> minmax(T[] a){
i f (a == n u l l || [Link] == 0) return n u l l ;
T min = a [ 0 ] ;
T max = a [ 0 ] ;
f o r ( i n t i = 1; i < [Link]; i + + )
{
i f ([Link](a[i]) > 0) min = a [ i ] ;
i f ([Link](a[i]) < 0) max = a [ i ] ;
}
return new Pair<T>(min, max);
}
} ...
String[] words = { "Mary", "had", "a", "little", "lamb" };
Pair<String> mm = [Link](words);
[Link]("min = " + [Link]());
[Link]("max = " + [Link]());
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 27/48
Restrictions and Limitations
■ Before JDK 5.0, primitive types cannot be substituted for a type
parameter
❑ Pair<int> or Pair<double>… unaccepted (compile error)
❑ Use wrapper classes instead
■ Pair<Integer> or Pair<Double>
■ From JDK 5.0 on, wrappers are automatically used.
■ Runtime type inquiry
❑ instanceof and getClass() ignore type parameter
❑ (a instanceof Pair<String>) and
(a instanceof Pair<T>) give the same value
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 28/48
Inheritance and Generic Types
■ No relationship!
Animal Pair<Animal>
No relationship
Cat Pair<Cat>
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 29/48
Wildcards
■ To specify a Pair capable of holding some subtype of
Animal:
❑ Pair<? extends Animal> aPair = ...;
...
Pair<Cat> catBuddies = new Pair<Cat>(tomCat, timCat);
Pair<? extends Animal> wildcardBuddies = catBuddies; // OK
Animal someAnimal = new Cow();
Cow someCow = new Cow();
[Link](someAnimal); // compile-time error
[Link](someCow); // compile-time error
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 30/48
Exercise
■ Write a generic method that sorts an array in ascending order
c l a s s ArrayAlg {
public s t a t i c . . . s o r t ( T [ ] a){ //sort a
}
public static <T extends Comparable<T>> void sort (T[] a) {
int n = [Link];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j].compareTo(a[j + 1]) > 0) {
// Swap if greater
T temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp;
}
}
}
}
■ Example of client code
...
S t r i n g [ ] names = { " Joh n " , " Pe t e r " , " Joe " } ;
ArrayAlg.<String>sort(names); // ( " J o e " , "John", " Pe t e r " )
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 31/48
Exercise
c l a s s ArrayAlg {
public s t a t i c <T extends Comparable> void s o r t ( T [ ] a)
Write {
a generic method that sorts an array in
ascending f o r ( i norder
t i = 0 ; i < a .le n gth () - 1 ; i + + )
f o r ( i n t j = i + 1 ; j < a . l e n g t h ( ) ; j++)
i f (a[i].compareTo(a[j]) > 0 ) {
T temp = a [ i ] ;
a [ i ] = a [ j ] ; a [ j ] = temp;
}
}
}
...
S t r i n g [ ] names = { " Joh n " , " Pe t e r " , " Joe " } ;
ArrayAlg.<String>sort(names); // ( " J o e " , "John", " Pe t e r " )
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 32/48
BÀI TẬP
◼ Viết phương thức Generic tìm phần tử lớn nhất trong
mảng
◼ Yêu cầu:
• Viết một phương thức generic để tìm phần tử lớn nhất
trong một mảng.
• Không sử dụng phương thức [Link]() hoặc
[Link]().
◼ Gợi ý:
• Dùng <T extends Comparable<T>> để đảm bảo kiểu dữ
liệu có thể so sánh được
Khoa
KhoaCNTT
CNTT –– Trường
ĐH NôngĐH Nông
Lâm Lâm01/2016
TP. HCM TP. HCM 33/48
