ted.neward@newardassociates.com | Blog: http://blogs.newardassociates.com | Github: tedneward | LinkedIn: tedneward
Review Collections (API design; idioms and ideas for usage)
Look at Collections en masse
Examine a custom implementation
Learn to use Collections functionally (and why)
interfaces: abstract data types that represent collections
implementation: concrete implementations of the interfaces
algorithms: methods that perform useful operations (searching, sorting, etc) on collections
interfaces define abstract data types
a mathematical model for data types
defined by its behavior (semantics)
a theoretical concept, used in formal semantics and program verification
... but focuses entirely on operations
no implementations
which means certain semantics not defined by operation names/parameters cannot be enforced
some operations are documented as "optional"
... which means runtime UnsupportedOperationException
throws
... which is suboptimal
always implement an ADT interface
provides backing behavior for the collection
may optimize for different situations (speed, memory, space)
may enforce implied semantics (ordering)
generally defines iteration implementations
operations upon collections
collection-agnostic (within ADT limits)
defined as static methods on Collections
class
the interface represents the abstract data type (ADT) being used
essentially, what the collection offers by way of operations
it will be up to the implementation to guarantee some of the interface's promises
interfaces can't dictate implementation
generally this is as far as the developer goes in learning the Collections API... which is good!
inheritance implies specialization... which is good!
not all methods are required; those that are not present will throw UnsupportedOperationException
a.k.a. a "Bag"
a group of objects (elements)
unordered iteration
storage unspecified
implements Iterable
iteration: iterator()
basic operations
informational: size
, isEmpty
singular: contains
, add
, remove
bulk: containsAll
, addAll
, removeAll
, retainAll
, clear
no guarantees around ordering or uniqueness
can provide an Iterator when requested
allows use as the source of enhanced for-loop
a.k.a. "Cursor"
an object that represents a position in the collection
hasNext
, next
remove
(optional)
ordered collection of elements
allows duplication
provides four groups of operations
positional access: get
, set
, add
, remove
, addAll
search: indexOf
, lastIndexOf
iteration: listIterator
range: subList
specialized List<>
marker interface
indicates fast (generally constant time) random access
but fast-indexed implementation not enforceable
bidirectional iteration and access through the List
hasNext
, hasPrevious
next
, nextIndex
, previous
, previousIndex
add
, remove
set
a collection that contains no duplicate elements (e1.equals(e2) == true
)
no added interface methods (just an impl promise)
a Set
that provides a total ordering on its elements, either a natural order or an imposed one
first
, last
, headSet
, subSet
, tailSet
are order-based
a SortedSet
extended with navigation methods reporting closest matches for given search targets
ceiling
, floor
, higher
, lower
provide relative ops
descendingIterator
, descendingSet
typically order elements in FIFO order
add
/remove
/element
: throws exception on failure
offer
/poll
/peek
: returns special value on failure
NOTE: don't insert null
s into a Queue
!
"A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element."
linear collection that supports element insertion and removal at both ends
additionally supports blocking operations that wait for the deque to become non-empty when retrieving an element, and wait for space to become available in the deque when storing an element
NOTE: not a Collection
(does not extend that interface)
maps keys (K
) to values (V
)
cannot contain duplicate keys, and each key can map to at most one value
Map that further provides a total ordering on its keys, based either on natural order or imposed order
SortedMap extended with navigation methods returning the closest matches for given search targets
provides additional (atomic) methods
some algorithms are implemented as static methods on the Collections class
some will be extensions we/you create
interface Comparable
: provide natural ordering to a given class
interface Comparator
: provide external ordering for a given class
Arrays
provides toList()
, converting array to a List<>
Collections
emptyList
/Map
/Set
singleton
binarySearch
, sort
synchronized[ADT]
, unmodifiable[ADT]
returns new ADT in a synchronized or immutable wrapper instance
singleton[ADT]
returns unmodifiable Set
/List
/Map
containing only the single instance
This idea (using static methods on the Collections class) is similar to programming functionally
such as Haskell's List.map
particularly if you wrap incoming Collections in unmodifiable wrappers
ideas:
iteration: map, filter
composition/grouping: foldLeft, foldRight, ...
parallel variants of the above
"Array": backed by an array
"Linked": backed by a linked list
"Hash": backed by a hashtable or hashing storage
"Tree": backed by a red-black tree
"Enum": specialized for use by enum types
"LinkedHash": combination hashtable/list implementation with predictable insertion order
"Concurrent": supporting full concurrency of retrievals and adjustable expected concurrency for updates
"CopyOnWrite": mutative operation forces copy
ArrayList
implements RandomAccess
LinkedList
java.util.concurrent.CopyOnWriteArrayList
implements RandomAccess
HashSet
java.util.concurrent.ConcurrentSkipListSet
java.util.concurrent.CopyOnWriteArraySet
EnumSet
LinkedHashSet
TreeSet
ArrayDeque
java.util.concurrent.ArrayBlockingQueue
LinkedList
java.util.concurrent.ConcurrentLinkedQueue
java.util.concurrent.LinkedBlockingQueue
java.util.concurrent.DelayQueue
unbounded BlockingQueue
of Delayed
elements
element can only be taken when its delay is up
PriorityQueue
based on a priority heap; natural or imposed order
java.util.concurrent.PriorityBlockingQueue
java.util.concurrent.SynchronousQueue
each insert blocks until corresponding remove
ArrayDeque
LinkedBlockingDeque
HashMap
java.util.concurrent.ConcurrentHashMap
java.util.concurrent.ConcurrentSkipListMap
scalable concurrent ConcurrentNavigableMap
impl
EnumMap
IdentityHashMap
uses reference-equality (==) in place of object-equality (.equals) when comparing keys/values
LinkedHashMap
Properties
(
TreeMap
WeakHashMap
weak keys => entry is removed when key is GC'ed
much of the heavy lifting may already be done via Abstract...
classes
AbstractCollection
AbstractList
AbstractMap
AbstractQueue
AbstractSequentialList
AbstractSet
you need only implement abstract methods
additional work required depends on interface
Concurrent
, Blocking
, Sorted
, etc, will require additional work to guarantee semantics
aggressively refactor/replace your
Vector
s
Hashtable
s
and Enumeration
s
with
ArrayList
s
HashMap
s
and Iterator
s
type-safety is a good thing
let the compiler do the work
if you haven't figured out generics, it's well past time to learn
always prefer the interfaces as references
use the interface that provides desired semantics
Set
, SortedSet
, NavigableSet
, and so on
never put a concrete implementation except after an allocation/construction call
use the most "base" interface that meets your needs
Collection
instead of List
Set
instead of HashSet
Map
instead of HashMap
copying constructors
Arrays.asList
(which takes varargs!)
addAll()
is a "union" operation
removeAll()
is a "difference" operation
retainAll()
is a "intersection" operation
Prefer Collections to arrays
public class Person { /* instead of private Person[] children = ...; do instead: */ private List<Person> children = ...; }
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(...)); } }
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); */ }
all Collections support dumping the contents of the collection via toString() in "x, y, z" format
if you need your own, different, format
create a static method that takes the Collection as a parameter
... and dumps it, rather than repeating the iteration logic over and over again (DRY)
in short, write a new algorithm to do the printing
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
Better: Prefer enhanced for loops
List<Name> names = ...; for (Name n : names) { // use n }
This helps avoid modifying the collection during iteration
... or eschew iteration altogether
List<Name> names = ...; MyListOps.apply(new MyApplyFn<Name>() { public void apply(Name n) { // use n } }, names);
"Ring" is a circular list (no end during iteration)
"LinkedArray" is a "linked array" implementation
or combine other implementations
SortedCollection
import java.util.*; public interface SortedCollection<E> extends Collection<E> { public Comparator<E> getComparator(); public void setComparator(Comparator<E> comp); }
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(); } // ...
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; } // ... }
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); } // . . .
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(); }
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.shuffle(List , Random)
Collections.reverse(List)
Collections.rotate(List, int distance)
Collections.swap(List, int, int)
int Collections.frequency(Collection, Object)
Object Collections.max(Collection , Comparator)
Object Collections.min(Collection , Comparator)
int Collections.indexOfSubList(List, List)
int Collections.lastIndexOfSubList(List, List)
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 = ...; }
what about "reverse" order?
descending instead of ascending
Collections.reverseOrder(comparator)
use the right interface to describe your needs; try to "design generically"
use the right implementation (or build your own!) to provide the necessary speed/size/concurrency tradeoff
use algorithms to manipulate Collections
... you must learn to program functionally
Architect, Engineering Manager/Leader, "force multiplier"
http://www.newardassociates.com
http://blogs.newardassociates.com
Sr Distinguished Engineer, Capital One
Educative (http://educative.io) Author
Performance Management for Engineering Managers
Books
Developer Relations Activity Patterns (w/Woodruff, et al; APress, forthcoming)
Professional F# 2.0 (w/Erickson, et al; Wrox, 2010)
Effective Enterprise Java (Addison-Wesley, 2004)
SSCLI Essentials (w/Stutz, et al; OReilly, 2003)
Server-Based Java Programming (Manning, 2000)