Generic programming in Java

Madhavan Mukund
[Link]

Programming Concepts using Java

Week 5
Structural polymorphism
Functions that depends only a specific capabilities
Reverse an array/list — should work for any type
Search for an element in an array/list — need equality check
Sort an array/list — need to compare values

May need to impose constraints on types of arguments

Copying an array needs source type to extend target type

Polymorphic data structures

Hold values of an arbitrary type
Homogenous
Should not have to cast return values

Madhavan Mukund Generic programming in Java Programming Concepts using Java 2/6
Java Generics
Use type variables

Madhavan Mukund Generic programming in Java Programming Concepts using Java 3/6
Java Generics
Use type variables
public <T> void reverse (T[] objarr){
Polymorphic reverse in Java T tempobj;
Type quantifier before return type int len = [Link];
“For every type T . . . ” for (i = 0; i < n/2; i++){
tempobj = objarr[i];
objarr[i] = objarr[(n-1)-i];
objarr[(n-1)-i] = tempobj;
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 3/6
Java Generics
Use type variables
public <T> int find (T[] objarr, T o){
Polymorphic reverse in Java int i;
Type quantifier before return type for (i = 0; i < [Link]; i++){
“For every type T . . . ” if (objarr[i] == o) {return i};
}
Polymorphic find in Java return (-1);
}
Searching for a value of incompatible
type is now a compile-time error

Madhavan Mukund Generic programming in Java Programming Concepts using Java 3/6
Java Generics
Use type variables
public static <T> void arraycopy (T[] src,
Polymorphic reverse in Java T[] tgt){
Type quantifier before return type int i,limit;
“For every type T . . . ” limit = [Link]([Link],[Link]);
for (i = 0; i < limit; i++){
Polymorphic find in Java tgt[i] = src[i];
}
Searching for a value of incompatible }
type is now a compile-time error
Polymorphic arraycopy
Source and target types must be identical

Madhavan Mukund Generic programming in Java Programming Concepts using Java 3/6
Java Generics
Use type variables
public static <S extends T,T>
Polymorphic reverse in Java void arraycopy (S[] src,
Type quantifier before return type T[] tgt){
int i,limit;
“For every type T . . . ”
limit = [Link]([Link],[Link]);
Polymorphic find in Java for (i = 0; i < limit; i++){
tgt[i] = src[i];
Searching for a value of incompatible }
type is now a compile-time error }
Polymorphic arraycopy
Source and target types must be identical
A more generous arraycopy
Source and target types may be different
Source type must extend target type

Madhavan Mukund Generic programming in Java Programming Concepts using Java 3/6
Polymorphic data structures
A polymorphic list public class LinkedList<T>{
private int size;
private Node first;

public T head(){
T returnval;
...
return(returnval);
}

public void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 4/6
Polymorphic data structures
A polymorphic list public class LinkedList<T>{
private int size;
The type parameter T applies to the private Node first;
class as a whole
public T head(){
T returnval;
...
return(returnval);
}

public void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 4/6
Polymorphic data structures
A polymorphic list public class LinkedList<T>{
private int size;
The type parameter T applies to the private Node first;
class as a whole
public T head(){
Internally, the T in Node is the same T T returnval;
...
return(returnval);
}

public void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 4/6
Polymorphic data structures
A polymorphic list public class LinkedList<T>{
private int size;
The type parameter T applies to the private Node first;
class as a whole
public T head(){
Internally, the T in Node is the same T T returnval;
...
Also the return value of head() and return(returnval);
}
the argument of insert()
public void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 4/6
Polymorphic data structures
A polymorphic list public class LinkedList<T>{
...
The type parameter T applies to the }
class as a whole
LinkedList<Ticket> ticketlist =
Internally, the T in Node is the same T new LinkedList<Ticket>();
LinkedList<Date> datelist =
Also the return value of head() and new LinkedList<Date>();
the argument of insert()
Ticket t = new Ticket();
Instantiate generic classes using Date d = new Date();
concrete type [Link](t);
[Link](d);

Madhavan Mukund Generic programming in Java Programming Concepts using Java 4/6
Polymorphic data structures
Be careful not to accidentally hide a public class LinkedList<T>{
type variable private int size;
private Node first;
public <T> void
insert(T newdata){...} public T head(){
T returnval;
...
return(returnval);
}

public <T> void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 5/6
Polymorphic data structures
Be careful not to accidentally hide a public class LinkedList<T>{
type variable private int size;
private Node first;
public <T> void
insert(T newdata){...} public T head(){
T returnval;
T in the argument of insert() is a ...
new T return(returnval);
}

public <T> void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 5/6
Polymorphic data structures
Be careful not to accidentally hide a public class LinkedList<T>{
type variable private int size;
private Node first;
public <T> void
insert(T newdata){...} public T head(){
T returnval;
T in the argument of insert() is a ...
new T return(returnval);
}
Quantifier <T> masks the type
parameter T of LinkedList public <T> void insert(T newdata){...}

private class Node {

private T data;
private Node next;
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 5/6
Polymorphic data structures
Be careful not to accidentally hide a public class LinkedList<T>{
type variable private int size;
private Node first;
public <T> void
insert(T newdata){...} public T head(){
T returnval;
T in the argument of insert() is a ...
new T return(returnval);
}
Quantifier <T> masks the type
parameter T of LinkedList public <T> void insert(T newdata){...}

Contrast with private class Node {

private T data;
public <T> static void
private Node next;
arraycopy (T[] src, T[] tgt){...}
...
}
}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 5/6
Summary

Generics introduce structural polymorphism into Java through type variables

Classes and functions can have type parameters
class LinearList<T> holds values of an arbitrary type T
public T head(){...} returns a value of same type T used when creating the list

Can describe subclass relationships between type variables

public static <S extends T,T> void arraycopy (S[] src, T[] tgt){...}

Be careful not to accidentally hide type variables

public <T> void insert(T newdata){...} inside class LinearList<T>
vs
public <T> static void arraycopy (T[] src, T[] tgt){...}

Madhavan Mukund Generic programming in Java Programming Concepts using Java 6/6