Friday, 29 October 2010

List of interface and classes in collections

Covering the interface one by one
Covering the classes
  • HashSet and TreeSet Classes
  • ArrayList and LinkList Classes
  • HashMap and TreeMap Classes
  • Vector and Stack classes

Wednesday, 27 October 2010

Class Objects as Type Literals

Class objects can be used as type specifications too, at runtime. For instance, you can create a generified method like this:

public static <T> T getInstance(Class<T> theClass)
throws IllegalAccessException, InstantiationException {

return theClass.newInstance();
}

Here are a few examples of calls to the getInstance() method:

String string   = getInstance(String.class);

MyClass myClass = getInstance(MyClass.class);

As you can see the return type changes depending on what class object you pass in as parameter to the method. This can be quite handy in database API's like Butterfly Persistence where you read objects from a database. Here is an example method definition:

public static <T> T read(Class<T> theClass, String sql)
throws IllegalAccessException, InstantiationException {

//execute SQL.

T o = theClass.newInstance();
//set properties via reflection.

return o;
}

Here is how you would call the read() method:

Driver employee   = read(Driver.class, "select * from drivers where id=1");

Vehicle vehicle = read(Vehicle.class, "select * from vehicles where id=1");

Upper Bounded Wildcards in generics

Suppose we want to write a generic method which takes a list and print it only when it contains elements subclassing one particular class. So here we need upper bound.
It is possible to set the upper bound of the wildcard like this:
List<? extends Vehicle> vehicles = new ArrayList<? extends Vehicle>();    

In this example I have specified the upper bound to be the class Vehicle. I can now define the printElements() method like this:

public void printElements(List<? extends Vehicle> elements){
for(Vehicle o : elements){
System.out.println(o);
}
}

As you can see it is now safe to cast each element in the list to a Vehicle, as it is done by the new for loop inside the method.
Furthermore, it is now safe to call the method using a List<Car> instance, provided that Car extends Vehicle. Here is an example:
List<Car> elements = new ArrayList<Car>
// ... add Car elements to the list.

printElements(elements);

But, even when using a wildcard with an upper bound it is not safe to write to the List. After all, a Car is always a Vehicle, but a Vehicle is not always a Car.

The type parameterization <? extends E> is called an "upper bounded wildcard" because it defines a type that could be any type so long as it is bounded by the superclass E. It provides covariant relationship such that the referenced object's (eg. Car ) type parameter is a subclass ofVehicle's type parameter

Wildcards in Generics

We just saw here about generic methods. But how generic are they?
Suppose we have to write a generic method which takes list of elements and prints elements onto screen. Element can be String, Integer,Object...So one can think of using object as type parameter. But this will be a mistake. See here for this.
So solution is wildcards.

Wildcards

The wildcard operator is a solution to the problem explained above.
The character '?' is a wild-card character and it stands for any Java type. It can be java.lang.Object type or some other type. It is just a place-holder that tells that it can be assigned with any type. Considering this case, the following are now valid syntaxes. 

List<?> anyObjects = null; 

List<Integer> integers = new ArrayList<Integer>();
anyObjects = integers;

List<Double> doubles = new ArrayList<Double>();
anyObjects = doubles;


Here is how you write a generic List using the wildcard operator:

List<?> listOfUnknown = new ArrayList<?>();    

Generic method using wildcards
We can now define the printElements() method like this:

public void printElements(List<?> elements){
for(Object o : elements){
System.out.println(o);
}
}
 
You can call the printElements() with any generified List instance. For instance:
List<String> elements = new ArrayList<String>
// ... add String elements to the list.

printElements(elements); 
 
When you upcast a List<String> to a List<?> you can now read all elements of the List<?> safely as Object instances. But you still cannot insert elements into the List<?>. The ? could represent any type, and thus it would be possible to insert types that did not match the original definition of the List.

Generics and Subtyping

Let’s test our understanding of generics. Is the following code snippet legal?

List<String> ls = new ArrayList<String>(); //1
List<Object> lo = ls; //2


Line 1 is certainly legal. The trickier part of the question is line 2. This boils down
to the question: is a List of String a List of Object. Most people’s instinct is to answer:
“sure!”.
Well, take a look at the next few lines:

lo.add(new Object()); // 3
String s = ls.get(0); // 4: attempts to assign an Object to a String!


Here we’ve aliased ls and lo. Accessing ls, a list of String, through the alias lo, we
can insert arbitrary objects into it. As a result ls does not hold just Strings anymore,
and when we try and get something out of it, we get a rude surprise.
The Java compiler will prevent this from happening of course. Line 2 will cause a
compile time error.
In general, if Foo is a subtype (subclass or subinterface) of Bar, and G is some
generic type declaration, it is not the case that G<Foo> is a subtype of G<Bar>.
This is probably the hardest thing you need to learn about generics, because it goes
against our deeply held intuitions.
So we had list of String not subtype of list of Objects.


The problem with that intuition is that it assumes that collections don’t change.
Our instinct takes these things to be immutable.
For example, if the department of motor vehicles supplies a list of drivers to the census
bureau, this seems reasonable. We think that a List<Driver> is a List<Person>,
assuming that Driver is a subtype of Person. In fact, what is being passed is a copy
of the registry of drivers. Otherwise, the census bureau could add new people who are
not drivers into the list, corrupting the DMV’s records.
In order to cope with this sort of situation, it’s useful to consider more flexible
generic types. The rules we’ve seen so far are quite restrictive.

Generic classes in java vs templates in C++

Here is a small excerpt from the definitions of the interfaces List and Iterator in package :
java.util:
public interface List<E> {
void add(E x);
Iterator<E> iterator();
}
public interface Iterator<E> {
E next();
boolean hasNext();
}

This should all be familiar, except for the stuff in angle brackets. Those are the
declarations of the formal type parameters of the interfaces List and Iterator.
Type parameters can be used throughout the generic declaration, pretty much where
you would use ordinary types (though there are some important restrictions.

In the introduction, we saw invocations of the generic type declaration List, such
as List<Integer>. In the invocation (usually called a parameterized type), all occurrences of the formal type parameter (E in this case) are replaced by the actual type argument (in this case, Integer).

You might imagine that List<Integer> stands for a version of List where E has been uniformly replaced by Integer:
public interface IntegerList {
void add(Integer x);
Iterator<Integer> iterator();
}

This intuition can be helpful, but it’s also misleading.
It is helpful, because the parameterized type List<Integer> does indeed have methods that look just like this expansion.
It is misleading, because the declaration of a generic is never actually expanded in this way. There aren’t multiple copies of the code: not in source, not in binary, not on disk and not in memory. If you are a C++ programmer, you’ll understand that this is very different than a C++ template.

A generic type declaration is compiled once and for all, and turned into a single class file, just like an ordinary class or interface declaration. Type parameters are analogous to the ordinary parameters used in methods or constructors. Much like a method has formal value parameters that describe the kinds of values it operates on, a generic declaration has formal type parameters. When a method is invoked, actual arguments are substituted for the formal parameters, and the method body is evaluated.
When a generic declaration is invoked, the actual type arguments are substituted for the formal type parameters.

The Motivation for Generics : dealing with casting of objects

Consider the following code:
List myIntList = new LinkedList(); // line no. 1
myIntList.add(new Integer(0)); // line no. 2
Integer x = (Integer) myIntList.iterator().next(); //line no. 3

The cast on line 3 is slightly annoying. Typically, the programmer knows what kind of data has been placed into a particular list. However, the cast is essential. The compiler can only guarantee that an Object will be returned by the iterator.
To ensure the assignment to a variable of type Integer is type safe, the cast is required.
Of course, the cast not only introduces clutter, it also introduces the possibility of a run time error, since the programmer might be mistaken.


Removing the cast
What if programmers could actually express their intent, and mark a list as being restricted to contain a particular data type?
This is the core idea behind generics.
Here is a version of the program fragment given above using generics:

List<Integer> myIntList = new LinkedList<Integer>(); // 1’
//OR
List<Integer> myIntList = new LinkedList(); // 1’

myIntList.add(new Integer(0)); //2’
Integer x = myIntList.iterator().next(); // 3’

Now, you might think that all we’ve accomplished is to move the clutter around.

Instead of a cast to Integer on line 3, we have Integer as a type parameter on line 1’. However, there is a very big difference here. The compiler can now check the type correctness of the program at compile-time. When we say that myIntList is declared with type List<Integer>, this tells us something about the variable myIntList, which holds true wherever and whenever it is used, and the compiler will guarantee it. In contrast, the cast tells us something the programmer thinks is true at a single point in the code.

The net effect, especially in large programs, is improved readability and robustness.

A big big note on Generics
Generics provides a sort of a syntactic sugar that might spare you some casting operation. But behind the scenes, after compilation the byte code is same. See Type Erasure with Generics to see how.