x3-java-collections.tex

\section{The Java Collections Library}
\label{sec:java-coll-libr}

In real day-to-day Java programming, programmers do not usually create
their own dynamic structures. The Java core library provides several
structures that are fit for most purposes. Now that you understand
pointers, inheritance, and generics, it is the right time to introduce
them.

The so-called Java Collections Library is a series of interfaces and
classes in package \verb+java.util+. In order to use them, you will
need to import them. For example, to use interface \verb+List+ and
class \verb+ArrayList+ you will need to add to the beginning of your
class file the following lines:

\begin{verbatim}
    import java.util.ArrayList;
    import java.util.List;
\end{verbatim}

The benefits of using the dynamic structures from the Java Collections
Library are twofold. First, it will
save effort on your part because you do not have to create these
structures again and again. Second, and more important, it will make
it easier for your code to 
communicate with other people's code because you will be using the same
interfaces and classes. 

\subsection*{Important: where to get more information?}
\label{sec:important:-where-get}

The Java Collections Library is well documented on the main
JavaDoc. You can find it by looking up ``java collections'' in your
favourite search engine. You can also look up specific classes or
interfaces easily, e.g.~''java list'' will lead you to the
documentation on the \verb+List+ interface. 

\subsection{Collection}
\label{sec:collection}

A \verb+Collection<E>+ is just a group of elements. This is the most
general interface. This interface is extended by \verb+List<E>+,
\verb+Set<E>+, and \verb+Queue<E>+. 

\subsection{Set}
\label{sec:set}

A \verb+Set<E>+ is a collection that cannot contain duplicate
elements. If an element is added to a set that already contains it,
nothing happens. The most commonly used implementation is
\verb+HashSet<E>+. A typical idiom to create a new set is:

\begin{verbatim}
    Set<MyClass> classSet = new HashSet<MyClass>();
\end{verbatim}

When the order of the elements is important (e.g.~for iterating
through the interface, see below), a useful implementing class may be
\verb+TreeSet<E>+. 

\subsection{List}
\label{sec:lists}

A \verb+List<E>+ is a collection of elements, maybe with duplicate
elements. 
%
A list provides methods to access
elements at specific indeces (\verb+.get(int)+) and to search for
the index of an element (e.g.~\verb+indexOf(Object)+). 
%
A list usually keeps the order in which elements are added to it; 
% A list does not need to be sorted, but it keeps the order in which
% elements were added to it. 
This means that elements that were added earlier come before
elements that were added later. 
%

The most commonly-used implementation is \verb+ArrayList<E>+, although
\verb+LinkedList<E>+ may be useful in some situations. A typical idiom to
create a new list is:

\begin{verbatim}
     List<MyClass> classList = new ArrayList<MyClass>();
\end{verbatim}

There is also a
class \verb+Vector<E>+ that is an old, synchronised, more complicated
implementation of interface \verb+List<E>+. It should not be
used (except maybe in multi-threaded applications). \verb+Vector<E>+ was
part of Java 1.0\footnote{Strictly speaking, it was Vector because
  Java 1.0 did not have generics.}; 
since the Collections Library was introduced in
Java~2, \verb+ArrayList<E>+ (and \verb+LinkedList<E>+)
is a better fit for most situations. 

\subsection{Queue}
\label{sec:queue}

A \verb+Queue<E>+ is a FIFO structure in which the first elements coming
in are the first elements coming out. The exception to this rule may
be the use of priorities, which allows some elements to come out
before other elements that have been longer in the queue. The most
common implementations of queues are \verb+LinkedList<E>+ and
\verb+PriorityQueue<E>+. A typical idiom to
create a new queue is:

\begin{verbatim}
     Queue<MyClass> classQueue = new LinkedList<MyClass>();
\end{verbatim}

\subsection{Stack}
\label{sec:stack}

A \verb+Stack<E>+ is a LIFO structure in which the last element coming in
is the first element coming out. 

\verb+Stack<E>+ is a special case in Java because they existed before the
Collections Library was introduced in Java 2 (like \verb+Vector<E>+, its
parent class) and it is a specific class, instead of being an
interface that is implemented by one or more classes. A typical idiom to
create a new stack is:

\begin{verbatim}
     Stack<MyClass> classStack = new Stack<MyClass>();
\end{verbatim}

\subsection{Map}
\label{sec:maps}

A \verb+Map<K,V>+ is an object that links pairs of keys and values. In
the Java Collections Library, a map cannot link the same key to two
different values, i.e.~it cannot contain duplicate keys. The most
typical implementation is \verb+HashMap<K,V>+ (in some cases, a
\verb+TreeMap+ may be useful, e.g.~if the order of keys is
important). A typical idiom to
create a new map is:

\begin{verbatim}
     Map<KeyClass,ValueClass> classMap = new HashMap<KeyClass,ValueClass>();
\end{verbatim}



\subsection{Operations with collections}
\label{sec:oper-with-coll}

All operations with collections are documented in their respective
JavaDocs. The operations that add or remove
elements from the collection are those most commonly used. 
There are also methods to add or remove
a lot of elements in bulk (e.g.~add all the element in a set to a list),
and to convert from collections to arrays and viceversa. You should
look a the JavaDoc and get familiarised with them.  We are going
to comment here only on two special cases, but very important to know. 

\subsubsection{Iterators}
\label{sec:iterators}

Every collection implements the method \verb+iterator()+. This method
returns an \verb+Iterator<T>+ for the collection. 

An iterator can be used to move through the collection. Iterators
implement two (sometimes three) simple methods: 

\begin{description}
\item[hasNext()] Returns true if there are more elements to go
  through.
\item[next()] Moves to the next element.
\end{description}

A typical idiom to use iterators is as follows: 

\begin{verbatim}
    // Assuming there is a collection (list, set, etc) of MyClass called "elements"
    for (Iterator itr = elements.iterator(); itr.hasNext(); ) {
        MyClass next = itr.next();
        next.doSomething();
    }
\end{verbatim}

First, you get an iterator for your collection. Then,
while there are more elements to look at,
you repeat the loop: take next element, do something with it, then go
for the next\ldots

\subsubsection{for-each}
\label{sec:each}

Since Java 5, the above loop can be written more succintly as: 

\begin{verbatim}
    // Assuming there is a collection (list, set, etc) of MyClass called "elements"
    for (MyClass next : elements) {
        next.doSomething();
    }    
\end{verbatim}

This is read ``for each object of class MyClass in 'elements',
do\ldots''. Much shorter and clearer, isn't it? 

It is important to bear in mind, though,
that there is a bit of magic happening behind the scenes when you use
a for-each loop. The objects on the right-hand side of the
colon~(``:'') must implement the \verb+Iterable+ interface or be an
array. If it is an \verb+Iterable+ (any class, as long as it
implements that interface), then Java will convert this construct into
the idiom in Section~\ref{sec:iterators}; 
if it is an array, Java will convert it into a loop
that uses an integer index to traverse it. 

\subsection{Practice}
\label{sec:practice}

Rewrite the code of your hospital manager or your supermarket to use
Java's \verb+List+'s and one of its implementations. Then use a
for-each loop to traverse the list of patients or customer and print
their names on the screen. 


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "xx-java-collections"
%%% End: