Java Collection Framework

In Chapter 9 we studied two different collections: one collection represented a fixed number of investments (Portfolio) and the second collection represented a variable number of credit cards (GlobalCredit).

Collections are used often when writing code. It would be very tedious and error prone if a client had to create their own collection classes. Java provides a set of software components that are used to represent and manipulate collections of any object type. The Java Collection Framework is made up of:

• interfaces: these define what methods the various types of collections support
• classes: these implement the interfaces
• algorithms: these are the methods that operate on collections (such as sorting a collection and searching a collection)

The official tutorial for Java collections is here.

UML Diagram

The UML diagram for the Collection interface hierarchy is shown below:

UML Diagram

The Collections Framework also includes a hierarchy of interfaces that are not rooted at Collection; nevertheless, the Map interface is an important part of the Collections Framework.

Collection Interface

A Collection represents a group of objects where each object is called an element of the collection. The interface defines the most general operations that a client can ask a collection to perform:

public interface Collection< E > extends Iterable< E >
{
   // Basic operations
   int size();
   boolean isEmpty();
   boolean contains(Object element);
   boolean add(E element);                      //optional
   boolean remove(Object element);              //optional
   Iterator< E > iterator();

   // Bulk operations
   boolean containsAll(Collection< ? > c);
   boolean addAll(Collection< ? extends E > c); //optional
   boolean removeAll(Collection< ? > c);        //optional
   boolean retainAll(Collection< ? > c);        //optional
   void clear();                                //optional

   // Array operations
   Object[] toArray();
   < T > T[] toArray(T[] a);
}

A Problem of Type

Recall that GlobalCredit was a collection of credit cards and Portfolio was a collection of investments. In general, a collection needs to be able to hold elements of some type E.

How might we create a collection that can hold any type E? We know that every class has Object at the root of its inheritance hierarchy, so a possible solution is to create a collection that holds Object references. There are two significant problems with this approach.

The first problem is that every class is substitutable for Object. This means that a client can put anything into a collection that holds Object references. If the client creates a collection of Strings there is nothing preventing the client from adding a Fraction to the collection.

The second problem is that such a collection will always return a reference to an Object whenever the client retrieves an element from the collection. This means that the client must always try to cast the type of the retrieved element to do anything remotely useful.

Generics

The designer of the Java language solved the problem by creating a mechanism called generics that allows the client to specify the type of element to use. Suppose you wanted to create a collection of strings:

      Collection< String > someStrings = new ArrayList< String >();
      
      // add a string
      someStrings.add("Hey this works!");
      
      // get a string
      String s = ((List< String >) someStrings).get(0);

Here's how you read the notation:

You can only use generics if the class or interface is declared as a generic interface (ie. don't try this with Fraction or String).

List Interface

A List is a collection that holds its elements in numbered sequence. A client of List can control where each element is inserted into the list and can access elements by their integer index.

public interface List< E > extends Collection< E > 
{
    // Positional access
    E get(int index);
    E set(int index, E element);         //optional
    boolean add(E element);              //optional
    void add(int index, E element);      //optional
    E remove(int index);                 //optional
    boolean addAll(int index,
        Collection< ? extends E> c );    //optional

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Iteration
    ListIterator< E > listIterator();
    ListIterator< E > listIterator(int index);

    // Range-view
    List< E > subList(int from, int to);
}

Portfolio has some of the features of the List interface.

Set Interface

A Set is a collection that cannot contain duplicates. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2).

The Set interface is identical to the Collection interface.

Map Interface

A Map maps a key to a value (ie. it is table). For example, a phonebook maps a name (the key) to a phonenumber (the value). Another example is a real-valued mathematical function (like y = x2) which maps a real number x (the key) to a real number y (the value).

A map cannot contain duplicate keys, and each key can map to only one value; however, different keys can map to the same value.

A map requires two types, one for the key and one for the value. Furthermore, a map does not contain elements like the other collections; it contains pairs of keys and value. This is the reason why Map does not extend Collection.

Map Interface

Because a map uses keys to look up values, its interface is different from that of the other collections:

public interface Map< K,V >
{
   // Basic operations
   V put(K key, V value);
   V get(Object key);
   V remove(Object key);
   boolean containsKey(Object key);
   boolean containsValue(Object value);
   int size();
   boolean isEmpty();

   // Bulk operations
   void putAll(Map< ? extends K, ? extends V > m);
   void clear();

   // Collection Views
   public Set< K > keySet();
   public Collection< V > values();
   public Set< Map.Entry< K,V > > entrySet();

   // Interface for entrySet elements
   public interface Entry 
   {
      K getKey();
      V getValue();
      V setValue(V value);
   }
}

Summary of Interfaces

• List — a numbered sequence of elements
• Set — contains elements with no duplicates in no particular order (from the client point of view)
• Map — contains key-value pairs with no duplicate keys

To Do For Next Lecture

Read Chapter 10.2.