The battle of the container frameworks: which should you use?

We compare ObjectSpace's JGL and Sun's Collections Framework to help you pick the best option

1 2 3 4 5 Page 2
Page 2 of 5

public interface Container {

Object add(Object object) // Add an object to myself. If appropriate, // return the object that displaced it, // otherwise return null. void clear() // Remove all of my objects. Object clone() // Return a shallow copy of myself. int maxSize() // Return the maximum number of objects // that I can contain. int size() // Return the number of objects that I contain. boolean isEmpty() // Return true if I contain no objects.

Enumeration elements() // Return an Enumeration of the components // in this container. ForwardIterator start() // Return an iterator positioned at my first item. ForwardIterator finish() // Return an iterator positioned immediately // after my last item.

Object remove(Enumeration pos) // Remove the element at a particular position. int remove(Enumeration first, Enumeration last) // Remove the elements in // the specified range. }

Listing 1. ObjectSpace JGL's Container interface

public interface Collection {

// Basic Operations boolean add(Object o) // (Optional) Ensures that this Collection // contains the specified element. int size() // Returns the number of elements in this Collection. boolean isEmpty() // Returns true if this Collection contains no elements. boolean contains(Object o) // Returns true if this Collection contains // the specified element. boolean remove(Object o) // (Optional) Removes a single instance of // the specified element from this Collection, // if it is present. Iterator iterator() // Returns an Iterator over the elements // in this Collection.

// Bulk Operations boolean addAll(Collection c) // (Optional) Adds all of the elements in the // specified Collection to this Collection. boolean containsAll(Collection c) // Returns true if this Collection contains // all of the elements in the specified Collection. boolean removeAll(Collection c) // (Optional) Removes from this Collection all // of its elements that are contained in the // specified Collection. boolean retainAll(Collection c) // (Optional) Retains only the elements in this // Collection that are contained in the specified // Collection. void clear() // (Optional) Removes all of the elements from // this Collection.

// Bulk Operations Object[] toArray() // Returns an array containing all of the elements // in this Collection. Object[] toArray(Object[] a) // Returns an array containing all of the elements // in this Collection, whose runtime type is that // of the specified array. }

Listing 2. Sun Collections Framework's Collection interface

Scrutinizing Listings 1 and 2 unearths a whole catalog of important differences. Table 4 effectively highlights these differences in a side-by-side comparison, with particular attention given to the semantics of the methods.

JGL Container

Shared By Both

Collections's Collection
Object add(Object object)

Yes(1)

boolean add(Object o)
void clear()

Yes

void clear()
boolean isEmpty()

Yes

boolean isEmpty()
int size()

Yes

int size()
Enumeration elements()

Yes(2)

Iterator iterator()
ForwardIterator start()

No

 
ForwardIterator finish()

No

 
int maxSize()

No

 
Object remove(Enumeration pos)

No

 
int remove(Enumeration first, Enumeration last)

No

 
String toString()

No

 
 

No

boolean addAll(Collection c)
 

No

boolean contains(Object o)
 

No

boolean containsAll(Collection c)
 

No

boolean remove(Object o)
 

No

boolean removeAll(Collection c)
 

No

boolean retainAll(Collection c)
 

No

Object[] toArray()
 

No

Object[] toArray(Object[] a)

Table 4. Direct semantics-based comparison of interfaces Container (JGL) and Collection (Collections Framework)

  1. The semantics of the respective add() methods aren't identical, but they are close enough in practice.
  2. Although the names of the methods differ, the semantics of Container.elements() and Collection.iterator() are essentially identical (that is, to return an iterator over the container).

The striking aspect of this comparison of methods dictated by JGL's Container and Sun's Collection interfaces is how little they have in common. Since these interfaces determine in many ways the "logical look and feel" of their respective frameworks, it follows that the frameworks themselves are quite different.

The methods common to both interfaces are the absolute essence of containerhood: adding new elements (add()), emptying a container (clear()), size determination (size()), and obtaining an iterator over the container (elements() or iterator()).

To spoil the simplicity of the previous statement, Collections specifies that its add() and clear() methods are optional (by "optional," Sun means that such methods may throw UnsupportedOperationException to signal clients that these methods aren't a logical part of some implementation of the Collection interface.) These "optional" methods introduce a fairly major and unwelcome complexity at such a high level in the framework. (E.g., How can I know whether a Collection object obtained at runtime from an external system will let me add objects to it? and Do I have to wrap all my Collections code with try-catchUnsupportedOperationException?, and so on.)

Leaving the interface similarities behind, if you study the differences between JGL's Container and the Collections Framework's Collection, you'll see in particular that the element removal methods vary significantly. JGL uses its iterators to identify (or "point to") one or more candidate elements for removal, while Collections identifies elements for removal using the elements themselves (cfr. argument passing by reference and by value). Clearly, the performance of the two approaches will, in general, be very different. Iterator-based removal should be very quick (often of the order of O(1)), while object-based removal will often be slow to very slow (since removal needs to find the object first. With many container implementations, this search will have to be an expensive O(n) sequential search). From an abstraction point of view, however, the Collections approach is higher-level, and therefore more programmer-friendly.

A second difference between Container and Collection stems from the difference in philosophies that spawned the two frameworks. JGL's Container interface contains less "algorithmic" functionality (methods to find elements, remove elements, and so on.) than does the Collections Framework's Collection interface. This is because JGL aims to decouple containers as much as possible from any algorithms that may operate on the containers. On the other hand, the Collections Framework doesn't regard algorithms as first-class citizens, so it doesn't have any philosophical objections to including extra algorithms in its primordial Collection container interface. For example, Collection.addAll(), Collection.removeAll(), and Collection.retainAll() are essentially set operations (in the mathematical sense). JGL offers more generic set operations in its separate algorithms class SetOperations. Also in contrast with Collections, JGL's SetOperations class contains a complete series of set operations (difference, symmetric difference, intersection and union).

Iterator interface hierarchies

Both JGL's Container and the Collections Framework's Collection interfaces specify methods to return an iterator over a container. While JGL and Collections iterators both are incarnations of the general object-oriented Iterator design pattern (as defined by the classic "Gang of Four" book, Design Patterns, [Addison-Wesley, 1995]), iterators are used differently by the two frameworks. Studying the iterator interface hierarchies and the definition of the most important iterator interfaces will explain why their uses differ in practice.

Figures 4 and 5 depict the iterator interface hierarchies for JGL and Collections.

Figure 4. JGL iterator interface hierarchy
Figure 5. Collections iterator interface hierarchy

Figures 4 and 5 clearly show that Collections is a lot simpler than JGL when it comes to iterators. JGL's overly complex approach to iterators often leads to programmer's headache (due to the numerous permutations of incompatible iterator types -- if an algorithm requires a RandomAccessIterator, but all you have is a ForwardIterator, you're stuck). The Collections approach greatly reduces this problem. The flip-side, of course, is that the reduced number of iterator types in Collections will prevent iterator implementations in that framework from being performance-optimized to the same extent as those in JGL. However, as the entire Java phenomenon is proving so convincingly, concentrating on correctness before performance is the right approach; so the Collections iterators approach is undoubtedly superior to JGL's.

Iterator Interface APIs

As far as actual iterator APIs are concerned, Figures 6 and 7 further confirm that JGL iterators are a lot more complex than Collection iterators.

Figure 6. JGL iterator interfaces APIs.

If you look closely at JGL interfaces InputIterator and OutputIterator, and their multiply-inheriting subinterface ForwardIterator, you should notice some object-oriented heresy: both InputIterator and OutputIterator contain methods advance() and advance(int n). These methods ought to be factored out and moved to a higher level in the hierarchy. Secondly, since these iterator-advancing methods logically seem to belong to ForwardIterator, which is lower in the hierarchy, it's clear that JGL's iterator hierarchy is rather messy right out of the starting block. Further complicating the JGL iterator picture is the recent non-backward-compatible addition (between JGL 2.0 and JGL 3.0) of method isCompatibleWith() in InputIterator, resulting in lots of JGL 2.0 code breaking en route to JGL 3.0.

Figure 7 depicts the refreshing simplicity and internal symmetry of the Collections Framework's iterator API.

Figure 7. Collections Iterator and ListIterator interface APIs

Interface Iterator basically is the same as java.util's Enumeration interface, with element removal thrown in. Interface Iterator's subinterface, ListIterator, is roughly equivalent to JGL's most flexible iterator, RandomAccessIterator. Table 5 attempts a best-fit comparison of ListIterator and RandomAccessIterator.

JGL RandomAccessIterator

Shared By Both

Collections ListIterator
boolean hasMoreElements()

Yes

boolean hasNext()
Object nextElement()

Yes

Object next()
int index()

Yes

int nextIndex(), int previousIndex()
void put(Object)

Yes(1)

void set(Object o)
boolean atBegin()

Almost

boolean hasPrevious()
boolean atEnd()

Almost

boolean hasNext()
 

No

Object previous()
 

No

void add(Object o)
 

No

void remove()
void put(int offset, Object object)

No

 
Object get()

No

 
Object get(int offset)

No

 
void advance()

No

 
void advance(int)

No

 
void retreat()

No

 
void retreat(int n)

No

 
int distance(ForwardIterator iterator)

No

 
boolean less(RandomAccessIterator iterator)

No

 
Container getContainer()

No

 
boolean isCompatibleWith(InputIterator)

No

 
Object clone()

No

 

Table 5. Direct semantics-based comparison of interfaces RandomAccessIterator (JGL) and ListIterator (Sun).

  1. The semantics of RandomAccessIterator.put() and ListIterator.set() aren't identical, but they're close enough in practice.

The interface hierarchy and API differences between JGL's and the Collections Framework's iterator approach is further complicated by the fact that the fundamental iterator semantics aren't the same in both frameworks. First of all, JGL iterators conceptually point directly at an element, whereas Collections iterators point between elements. This difference leads to JGL's get()/put()and advance()/retreat() methods as opposed to Collections's shorter next()/previous() methods.

Secondly, Collections iterators are able to alter the size of a collection by removing elements (and adding elements, in the case of ListIterators), while normal JGL iterators support only element overwriting (which never changes the size of a container). The latter is understandable if you consider that JGL iterators are used as abstract pointers (in the C/C++ sense) to elements within containers.

Acting on container subranges

JGL relies a lot on this particular "pointers view" of iterators since it lets users pass two iterators as a means of specifying a subrange of a container. When you remove an element from a JGL container, any iterators pointing into this container normally are invalidated. So, clearly, JGL doesn't let its iterators remove or add elements because such a capability would sabotage most of its range-based algorithms. Roughly half of JGL's algorithm entry points support the operation of an algorithm on a subrange of a container, instead of operating on the entire container. (There is one important exception to this "JGL iterators can't change the size of a container" rule: jgl.util's InsertIterator does allow you to insert new elements in a container, by way of a Container's add() method. Sophisticated developers can effectively use this less-than-elementary iterator.)

Collections uses a much cleaner approach to container subranges: Every List can generate a range view of some part of itself, using the following method:

List List.subList(int fromIndex, int toIndex)

As you can see from the method's signature, though, obtaining range views works only for Lists, not all Collections. Nevertheless, this elegant approach allows Collections to do away with any subrange-specific methods (such methods form roughly half of all JGL algorithm methods!).

Container Implementations

Both frameworks provide general-purpose implementations of their respective core container interfaces. Table 6 shows that Collections isn't far behind JGL when it comes to concrete, usable container classes.

1 2 3 4 5 Page 2
Page 2 of 5