Taming The Wildcard Generics

Have you ever tried to work with List<? extends Number>? You get this list from some smart program, and then try to do something with this collection. Only to find out that you cannot add anything to it. Why cannot you? You open books, you look up on Google, you go to java.sun.com, and finally you figure out that it is not a “generics bug”, but a regular, normal behavior. Here is the reason why:

Suppose some method produced an ArrayList<Integer>, and returns it disguised as List<? extends Number> - there is nothing wrong with it. But then the receiver, knowing only that it is a List of something extending Number, tries to add a Number to the list, namely, a Double – can it be legal? Of course not, because the original container expects only Integers, You cannot legally do it – some other method still expects this to be a List of Integers.

When the code is executed, all the generics information is erased, so that this kind of checking is done during compilation time. And during compilation time there seems to be no way, in the code that receives List<? extends Number>, to figure out what is the actual type of elements inside. We just do not know; all we know is that if you extract an element, you will get a superclass of Number. That’s why it is impossible to allow to add anything at all to such a list.

Interesting, right? One can easily remove elements from such a collection, but cannot add anything. You are not allowed, for List<? extends T> list to do list.add(T t) – but it is okay to remove elements from the list. The same is true for a Collection<T>, for a Map<K,V>.

I had a slightly different problem to solve: having a collection of collections, produce a virtual collection that lists all the component collections.

What does it mean that the collection is virtual? It means that no collection object exists – it may be a view into some other collection, or a class that behaves as if it contains elements, while actually it does not. Take a look at Collections.synchronizedList() – it returns a synchronized (thread-safe) list backed by the specified list. No significant amount of additional memory is allocated when you wrap a list using this method; and if the original list changes, the synchronized list will change accordingly – and vice versa.

Note that this kind of wrapper does not in any way influence the objects contained in the list – they are the same objects; the changes are in the methods that we use to access them.

The Problem

So, this is what I wanted to accomplish: having a Collection<? extends Collection<? extends T>>, produce a virtual Collection<T> - a collection that would change when components are changing, from which we could remove elements and to which we could add elements.

The desired collection should contain all the elements from the component collections; I want to be able to remove the elements (meaning, they are removed from components); I want to find a way to add elements to my resulting collection.

Note that this is not a flat collection produced from a tree represented as a collection of collections of collections, etc. Flattening happens on just one level: we had a collection of collections of type T, and produce a collection of type T.

One more natural requirement is that, when I list the elements of the resulting collection, they will be listed in a natural order: first, elements of the first component are listed, as if we were scanning the component itself, then the second one, etc., till the last element of the last component.

The functional difference between an Iterable<T> and a Collection<T> is essentially that with a Collection one can get its size and add elements. Of course, to calculate the size of a compound collection one has to add up the sizes of its components. Yes, the size can be changing while we count – but the same can happen to an ordinary collection as well, so we should not be too surprised.

A Collection<T> has actually two addition methods: add(T element) and addAll(Collection<? extends T>). Remember, the intention is to create a virtual, live collection, which means that we are not interested in making a copy of the collection passed to addAll() method. We want to use the collection itself.

But when we add an individual element, T element, we cannot add it to any original component.

It is easy to introduce a compound collection class that can shrink but cannot grow; let’s call it ShrinkingCompoundCollection. It works as described above, by scanning through individual components; deletion as I said above, is fine, but addition cannot be implemented..

The Solution

Let’s denote the original upper level collection of collections as A, and its components as Ai. Since we cannot touch neither any of Ai, nor the original collection A, we have to have two “overflow” collections. One, upper level, collection will receive all the collections that are being added using addAll() method. Let’s denote this upper level collection as B, and its components as Bk. When listing elements of the whole compound collection or calculating the size of the compound collection, we have to scan through all the Ai, and then through all the Bj.

The first component of B, Collection<T> B0, has to be added when B is created. This component will accept all individual elements added by calling add(T element).

So, we have the following structure: a collection C consisting of A and B; each one consists of “elementary” collections with elements of type either T or ? extends T. Now, have not you noticed that we have tree levels, instead of two. How do we handle this? By iteration. Let’s denote as F the operation of removing one layer of indirection, that is, the conversion of Collection<? extends Collection<? extends T>> to Collection<T>. Applying this operation to C, which is a Collection<Collection<? extends Collection<? extends T>>>, we get a Collection<Collection<? extends T>>; applying F to the resulting collection, we get the required Collection<T>.

How do we do it, if we are supposed to use a constructor? I never heard of recursive constructors yet. Well, actually we do not need much of recursion.

Watch my hands. Having a Collection<? extends Collection<? extends T>> A, and having created an “overflow” LinkedList<? extends Collection<? extends T>>, produce a collection out of these two, and pass it to a ShrinkingCollection constructor. The constructor returns a new Collection<? extends Collection<? extends T>>, the first element of which we know, it is our LinkedList.B. Add to it an “individual overflow list”, LinkedList<T> B0, and pass the resulting parameter again to super.constructor. We have built a Collection<T>, which is an instance of ShrinkingCompoundCollection<T>, and we know how to add to it collections and individual instances of T.

Q.E.D.