Jenny Harlow

Navigation shortcuts: Wiki users:Jenny Harlow

---

Project

Designing a simple collections framework

Introduction

In COSC324 Wal emphasised the use of Collections for efficient programming. He pointed out some of the ways in which the Java Collections Framework uses design patterns (wrappers, iterators, factory methods), but also some of the glaring Arrghghgs (the OO term seems to be antipatterns) that there seem to be in the current design. Naturally we all nodded wisely and agreed that it is just terrible ... It's easy to criticise, but just how easy is it to design a collections suite?

This project will attempt to redesign part of the Java Collections Framework from the point of view of 'if we were starting again, what might we do'. The whole framework is huge, and includes many specialised features such as the java.util.concurrent classes. This project will focus on what we might consider to be the main everyday-usage collections - the ones that come into almost everything we might want to write: lists, sets, maps.

The Java Collection framework

A brief overview of the Java Collections framework

This diagram gives an overview of the main Java Collections framework interfaces and implementations.

Some of the main points which are relevant for this design study are:

• The Collections Framework uses generics. List and Set are Collection subtypes (formal type parameter E), Map (formal type parameters K and V) is not a Collection subtype and uses the Map.Entry type (a member interface of Map). The Collections Framework includes abstract classes, not shown in this diagram, which provide a 'skeletal implementation' of the interfaces to act as the basis for concrete implementations.

• Collection implements Iterable, which is what (transparently to the client) allows us to be able to use the for-each looping construct. Map does not implement Iterable and there is no map iterator in the Framework.

• The Collection type has non-altering methods including size(), isEmpty(), contains(E e). It also has collection-altering (what Java terms 'destructive methods') add(E e), remove(E e) (and addAll(...), removeAll(...) to be able to add or remove a whole Collection), and clear(). Map methods include size(), isEmpty(), containsKey(K k) and "destructive" methods put(K k, V v) (and putAll(...)) and remove(K k). The destructive methods are marked optional in the interface specification. This essentially means that an implmentation may choose not to support them. Java says:

"The 'destructive' methods contained in this interface, that is, the methods that modify the collection on which they operate, are specified to throw UnsupportedOperationException if this collection does not support the operation. If this is the case, these methods may, but are not required to, throw an UnsupportedOperationException if the invocation would have no effect on the collection."(Java SE 6.0 documentation)

• Similarly, if there are restrictions on the types of elements an implementation allows, then

  "attempting an operation on an ineligible element whose completion would not result in the insertion of an ineligible element into the collection may throw an exception or it may succeed, at the option of the implementation. Such exceptions are marked as "optional" in the specification for this interface."(Java SE 6.0 documentation)

• The Collection interface also includes the iterator() factory method, which returns an Iterator. Iterator methods include remove() as well as next() and hasNext(). remove() is not marked optional.

• The Collections class contains static methods which relate to collections, including Collection and Map types.
  • Some Collections methods apply only to particular collection types. In particular, many apply only to List types (sort(...), reverse(...), swap(...), shuffle(...), indexOfSublist(...), ...), shuffle(...), etc).
  • Collections also includes static factory methods providing 'wrappers', ie a view of the specified collection which interposes a layer between the client and methods of the underlying collection. Some wrappers (eg synchronisation wrappers) add functionality, some disable functionality. The unmodifiable wrappers are intended to provide a read-only view of a collection so that "attempts to modify the returned collection, whether direct or via its iterator, result in an UnsupportedOperationException."(Java SE 6.0 documentation). Specific wrapper factory methods for List, Set, Map etc are provided for wrapper family.
  • Some algorithms are 'destructive', and again

    "the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection."(Java SE 6.0 documentation)

Design study

Aims

My aim is to create a design for a collections framework that includes lists, sets and maps and provides equivalent functionality to the existing implementations.

Design issues

My initial thinking about this project made me realise that a major issue for Collections is contracts: Collections are for other programmers to use and so using and abiding by design by contract has to be just as important, if not more so, as conspicuous display of GoF-authorised design patterns. Am I claiming the design by contract is more important here than in some of the other projects? No, but I am saying that it is very very relevant when designing a framework whose sole purpose is to provide objects to be used by clients.

all things to all men

Optional extras

If I have time I am interested in the idea of a performance test suite for collections, running some standard tests and providing a summary of results.

Design Critique

Design Improvements

I have set up a separate page design scratch-pad for thoughts-in-progress that are too open-ended to have made it here yet.