# Collections (Data Structure Library)

# Predefined Libraries

- Standard data-structure solutions.
- Similar to C++ Standard Template Library.
- Don't rewrite structures already available: linked lists, hash tables, expanding arrays, balanced binary search trees, etc.
- Do write structures specialized to your problem domain.
- Versions
  - <ver 1.2: Legacy versions still used some (esp Vector)
  - ver 1.2-1.4: Collections without generics (templaces).
  - Java 5 (1.5) has generics, similar to C++ templates.
- Non-standard packages fill gaps in Collections, eg, Apache Jakarta Commons Collections.

# Basic Data Structures

Containers - hold values
  - Arrays - In language. Stores elements at numbered positions.
  - Lists - Sequential elements (ArrayList and LinkedList)
  - Sets - Single copy of elements (TreeSet and HashSet)
  - Maps - Key-value pairs. (HashMap and TreeMap).
  - Misc others.
Iterators
  Pass over the elements of data structures.
Algorithms
  Manipulate data structures (sorting, searching, ...).

All classes are in java.util.* unless otherwise specified.

# Objects only

- No primitives can be stored in Collections.
  - Use wrapper classes (Integer, Float, ...) or your own class.
  - Wrapper classes are immutable, which may be a problem.
  - Bad: Performance, inconvenience.
- Pre Java 5: All elements are type `Object`
  - Upcasting is automatic.
  - Ugly: Only Objects come back out. Requires downcasting.
  - Insecure: Mixed types can potentially be added to a Collection.
- Java 5 Generics
  - Like C++ templates.
  - Compiler change only -- same Java Virtual Machine is used.
  - More secure -- adding different types is extremely difficult.
  - Automatic downcasting makes code much more readable.
  - "Autoboxing" hides conversion between primitive types and their wrapper classes. Problems lurking here?

# Class Hierarchy

    Collections class contains useful static methods.
    AbstractCollection implements Collection
        AbstractList implements List
            ArrayList implements RandomAccess
            AbstractSequentialList
                LinkedList
            Vector implements RandomAccess
                Stack
        AbstractSet implements Set
            HashSet
                LinkedHashSet
            TreeSet implements SortedSet
    AbstractMap implements Map
        HashMap
            LinkedHashMap
        TreeMap implements SortedMap
        WeakHashMap
        IdentityHashMap

# Interface Hierarchy

    Collection
        Set
            SortedSet
        List
    Map
        SortedMap
    Map.Entry
    Iterator
        ListIterator
    Comparator
    RandomAccess   // Marker interface

# java.util.Collections Class static methods

    binarySearch(List, Object)
    binarySearch(List, Object, Comparator)
    copy(List dest, List src)
    fill(List, Object)
    indexOfSublist(List src, List target)
    max(Collection)               min also
    max(Collection, Comparator)   min also
    replaceAll(List, Object oldval, Object newval)
    reverse(List)
    rotate(List, distance)
    shuffle(List)
    sort(List)
    sort(List, Comparator)   O(N log N), stable
    swap(List, i, j)
    synchronizedCollection(Collection)
    synchronizedList(List)  same for Map, SortedMap, Set, SortedSet
    unmodifiableCollection(Collection)
    unmodifiableList(List)  same for Map, SortedMap, Set, SortedSet

# Collection Interface Methods

    add(Object)
    add(Collection)
    clear()
    contains(Object)
    containsAll(Collection)
    isEmpty()
    iterator()
    remove(Object)
    removeAll(Collection)
    retailAll(Collection)
    size()
    toArray()
    toArray(Object[])

# List Interface with two concrete implementations

- List interface specifies common methods.
  - ArrayList - Expandable array. Access O(1). Insertions/Deletions O(n).
  - LinkedList - Linked list implementation. Access O(N). Insertions/deletions O(1).

# Set Interface with two concrete implementations

- Set interface specifies common methods.
  - TreeSet - Balanced binary tree. Insert/access O(log N). Sorted.
  - HashSet - Hash table. Insert/access O(1). Unsorted.

# Map Interface with two concrete implementations

- Map interface specifies common methods.
  - TreeMap - Balanced binary tree. Insert/access O(log N). Sorted by key.
  - HashMap - Hash table. Insert/access O(1). Unsorted.
    - LinkedHashMap - Iterator produced elements in insertion order.
  - WeakHashMap - If no references to key object, can delete entry.
  - IdentityHashMap - Compare by key reference identity, not hashcode.

# Map Interface methods

    clear()
    containsKey(Object)
    containsValue(Object)
    entrySet()  returns Set of Map.Entry elements.
    get(Object key)
    isEmpty()
    keySet()    returns Set of keys
    put(Object key, Object value)
    putAll(Map)
    remove(Object key)
    size()
    values()   returns Collection view of values.

# Iterator Interface

    public interface Iterator {
        public booean hasNext();  // true if there are more elements.
        public Object next();     // returns next element.
        public void   remove();   // Removes last element returned by next. Optional.
    }

Typical pattern pre Java 5.

    List names = new ArrayList();
    names.add("Bill");
    names.add("Jill");   //  Strings will get upcast to Object in the ArrayList.
    ...
    Iterator it = names.iterator();
    while (it.hasNext()) {
       String aName = (String)(it.next());
       ...
    }

Must cast the Object that comes out of the data structure to the type we need, eg, String in this case.

# Iterator Interface

Typical pattern in Java 5.

    List<String> names = new ArrayList<String>();
    names.add("Bill");
    names.add("Jill");
    . . .
    Iterator<String> it = names.iterator();
    while (it.hasNext()) {
       String aName = it.next();
       .  ..
    }

Or using the new Java 5 for loop.

    . . .
    for (String aName : names {
       . . .
    }

# ListIterator Interface

In addition to `hasNext()` and `next()`, has the following. A ListIterator is always between elements. The operation applies to the most recently accessed element, either from either `next()` or `previous*(`.

    add(Object)
    hasPrevious()  // true if there is a previous element
    previous()     // return previous element
    set(Object)    // changes value of most recent (prev/next) element.

# Comparator Interface

When sorting objects, there is usually no obviously natural way to compare them (exception: Strings). You often need to supply a Comparator object when sorting data strucutures.

    public interface Comparator {
        public int compareTo(Object a, Object b); // <0, 0, or >0
    }

See Example - Word Frequency lines 105 and 123.

Similar to Comparable interface, as in String.

    public interface Comparable {
        public int compareTo(Object b); // <0, 0, or >0
    }

# End