Busy Java Developer's Guide to Collections

ted.neward@newardassociates.com | Blog: http://blogs.newardassociates.com | Github: tedneward | LinkedIn: tedneward

Objectives

What are we here to do today?

JVM Collections: Design

How is it all arranged?

JVM Collections: Design

Collections API is broken into three parts

JVM Collections: Design

Interfaces

JVM Collections: Design

Implementations

JVM Collections: Design

Algorithms

Collections: Interfaces

The 'face' of the collection

Collections: Interfaces

Interfaces define programmer interaction with the collection

Collections: Interfaces

Collection

Collections: Interfaces

Iterable

Iterator

Collections: Interfaces

List

Collections: Interfaces

RandomAccess

Collections: Interfaces

ListIterator

Collections: Interfaces

Set

SortedSet

NavigableSet

Collections: Interfaces

Queue

java.util.concurrent.BlockingQueue

Collections: Interfaces

Deque

java.util.concurrent.BlockingDeque

Collections: Interfaces

Map

SortedMap

NavigableMap

Collections: Interfaces

java.util.concurrent.ConcurrentMap

Collections: Algorithms

Because not everything is an object

Collections: Algorithms

Knowing just the interfaces, we can write useful methods that manipulate, scan, sort and otherwise utilize the collection

Collections: Algorithms

Algorithm classes

Collections: Algorithms

NOTE

Collections: Implementations

Where rubber meets road

Collections: Implementations

Naming indicates implementation semantics and characteristics

Collections: Implementations

List implementations

Collections: Implementations

Set implementations:

Collections: Implementations

Queue implementations:

Collections: Implementations

Queue implementations (continued):

Collections: Implementations

Deque implementations:

Collections: Implementations

Map implementations

Collections: Implementations

Map implementations, continued:

Collections: Implementations

Custom implementations

Collections: Idioms

(Re)Thinking how you use them

Collections: Idioms

Always use the 1.2 Collections

Collections: Idioms

Always use the genericized form

Collections: Idioms

Program to the "highest" interface acceptable

Collections: Idioms

Use the bulk operations

Collections: Idioms

Prefer Collections to arrays

public class Person {
  /* instead of
  private Person[] children = ...;
      do instead: */
  private List<Person> children = ...;
}

Collections: Idioms

Prefer empty Collections instead of null

public class Person {
  /* instead of
  private List<Person> children = null;
      do instead: */
  private List<Person> children = new ArrayList<Person>(); // empty

  // Doing this means you never need check for null, reallocate,
  // or other array ugly-isms
  public void shesHavingABaby()
  {
    children.add(new Person(...));
  }
}

Collections: Idioms

Avoid "leaking" mutable Collections

public class Person {
  private List<Person> children = ...;
  /* instead of
  List<Person> getChildren() { return children; }
      do instead: */
  List<Person> getChildren() { return Collections.unmodifiableList(children); }
  /* or, depending on what you want, could also use:
  return new ArrayList(children); // or
  return new CopyOnWriteArrayList(children);
    */ 
}

Collections: Idioms

Printing/display

Collections: Idioms

Prefer for loops to iteration

List<Name> names = ...;
for (Iterator it = names.iterator(); it.hasNext(); ) {
  Name n = it.next();
  // use n
}

This helps avoid modifying the collection during iteration

Collections: Idioms

Better: Prefer enhanced for loops

List<Name> names = ...;
for (Name n : names) {
  // use n
}

This helps avoid modifying the collection during iteration

Collections: Idioms

... or eschew iteration altogether

List<Name> names = ...;
MyListOps.apply(new MyApplyFn<Name>() {
  public void apply(Name n) {
    // use n
  } 
}, names);

Collections: Idioms

Don't be afraid to create your own interfaces, algorithms or implementations

Collections: Idioms

SortedCollection

import java.util.*;

public interface SortedCollection<E> extends Collection<E> {
  public Comparator<E> getComparator();
  public void setComparator(Comparator<E> comp);
}

Collections: Idioms

ArraySortedCollection

public class ArraySortedCollection<E> 
  implements SortedCollection<E>, Iterable<E>
{
  private Comparator<E> comparator;
  private ArrayList<E> list;
      
  public ArraySortedCollection(Comparator<E> c) {
      this.list = new ArrayList<E>();
      this.comparator = c;
  }
  public ArraySortedCollection(Collection<? extends E> src, Comparator<E> c) {
      this.list = new ArrayList<E>(src);
      this.comparator = c;
      sortThis();
  }

  // ...

Collections: Idioms

ArraySortedCollection


  public Comparator<E> getComparator() { return comparator; }
  public void setComparator(Comparator<E> cmp) { comparator=cmp; sortThis(); }
  
  public boolean add(E e)
  { boolean r = list.add(e); sortThis(); return r; }
  public boolean addAll(Collection<? extends E> ec) 
  { boolean r = list.addAll(ec); sortThis(); return r; }
  public boolean remove(Object o)
  { boolean r = list.remove(o); sortThis(); return r; }
  public boolean removeAll(Collection<?> c)
  { boolean r = list.removeAll(c); sortThis(); return r; }
  public boolean retainAll(Collection<?> ec)
  { boolean r = list.retainAll(ec); sortThis(); return r; }

  // ...
}

Collections: Idioms

ArraySortedCollection

    public void clear() { list.clear(); }
  public boolean contains(Object o) { return list.contains(o); }
  public boolean containsAll(Collection <?> c) { return list.containsAll(c); }
  public boolean isEmpty() { return list.isEmpty(); }
  public Iterator<E> iterator() { return list.iterator(); }
  public int size() { return list.size(); }
  public Object[] toArray() { return list.toArray(); }
  public <T> T[] toArray(T[] a) { return list.toArray(a); }
  
  private void sortThis() {
      Collections.sort(list, comparator);
  }

  // . . .

Collections: Idioms

ArraySortedCollection

  public boolean equals(Object o) {
  if (o == this) return true;
      
  if (o instanceof ArraySortedCollection) {
    ArraySortedCollection<E> rhs = (ArraySortedCollection<E>)o;
    return this.list.equals(rhs.list);
  }
      
  return false;
}
public int hashCode() { return list.hashCode(); }
public String toString() { return list.toString(); }

Collections: Idioms

Or create "adapters" to the Collections API


public List columnAsList(final RowSet rs, final int column)
{
return new AbstractList() {
  public int size() { 
    try { rs.last(); return rs.getRow(); }
    catch (SQLException sqlEx) { /* Do something meaningful */ }
  }
  public Object get(int index) {
    if (index >= size()) throw new IndexOutOfBoundsException();
    try { rs.absolute(index + 1); return rs.getObject(column); }
    catch (SQLException sqlEx) { /* Do Something meaningful */ }
  }
};
}

Collections: Idioms

Use the predefined "manipulator" methods

Collections: Idioms

Or the "analytic" methods

Collections: Idioms

Provide natural and alternative sort orders

public class Person 
  implements Comparable
{
  /* Natural order sort */
  public int compareTo(Person rhs)
  { return BY_LASTNAME.compare(this, rhs); }

  public final static Comparator<Person> BY_LASTNAME =
    new Comparator<Person>() {
      public compare(Person lhs, Person rhs) {
        return lhs.getLastName().compare(rhs.getLastName());
      }
    };
  public final static Comparator<Person> BY_FIRSTNAME = ...;
  public final static Comparator<Person> BY_AGE = ...;
}

Collections: Idioms

Provide natural and alternative sort orders

Summary

Collections are powerful

But to truly use Collections powerfully...

Credentials

Who is this guy?