Collections in Java

Arrays

Has special language support Iterator Collection Set List Map

Iterators

Collections (also called containers)

The composite design pattern, revisited

OOP: Collections

Array, Example
class Car{}; Car[] cars1; Car[] cars2 = new Car[10]; // minimal dummy class // null reference // null references

for (int i = 0; i < cars2.length; i++) cars2[i] = new Car(); // aggregated initialization Car[] cars3 = {new Car(), new Car(), new Car(), new Car()}; cars1 = cars3;

Helper class java.util.Arrays

Search and sort: binarySearch(), sort() Comparison: equals() Instantiation: fill() Conversion: asList()
2

OOP: Collections

Array
Most efficient way to hold references to objects.
data index

Car Car
0 1 2

Car
3 4 5

Car
6 7

Advantages

Knows the type it holds, i.e., compile-time type checking Knows its size, i.e., ask for the length Can hold primitive types directly Automatic bondary checking, raises exceptions if violated Only hold one type of objects (including primitives) Fixed size
3

Disadvantages

OOP: Collections

Overview of Collection
A collection is a group of data manipulate as a single object.
Corresponds to a bag.

Insulate client programs from the implementation.

array, linked list, hash table, balanced binary tree, red-black tree, etc.

Can grow dynamically Contain only Objects (reference types)

i.e., no primitive data types, fixed in Java 5.0 (autoboxing/unboxing)

Heterogeneous Can be thread safe (concurrent access) Can be not-modifiable Like C++'s Standard Template Library (STL)
4

OOP: Collections

Collection Interfaces
Collections are primarily defined through a set of interfaces.

Supported by a set of classes that implement the interfaces

Collection

Map

Set

List

Interfaces are used of flexibility reasons

Not tightened to an implementation

OOP: Collections

The Iterator Interface

The idea: Select each element in a collection in turns

Hide the underlying collection can be bag, set, list, or map

Collection isEmpty() add() remove() ...

list

Iterator hasNext() next() remove()

Another nice design pattern. Iterators are fail-fast

Exception thrown if collection is modified externally, i.e., not via the iterator (multi-threading).
6

OOP: Collections

The Iterator Interface, cont.

// the interface definition interface Iterator { boolean hasNext(); Object next(); // note "one-way" traffic void remove(); // Optional }

// an example using iterators public static void main (String[] args){ ArrayList cars = new ArrayList(); for (int i = 0; i < 12; i++) cars.add (new Car()); Iterator it = cars.iterator(); while (it.hasNext()) System.out.println ((Car)it.next()); }
OOP: Collections 7

The Collection Interface

public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator(); // Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // boolean removeAll(Collection c); // boolean retainAll(Collection c); // void clear(); // // Array Operations Object[] toArray(); Object[] toArray(Object a[]); }
OOP: Collections 8

Optional Optional Optional Optional

The Composite Design Pattern, revisited

Client

use Component print() add() remove() components Single print() List print() add() remove() for all components c c.print()

Component is an abstract class Single typically called leaf List typically called composite
OOP: Collections 9

Implementation of the Compsite Pattern

import java.util.*; public class List extends Component{ private ArrayList comp; // previously array + int counter /** Constructor */ public List(){ comp = new ArrayList(); /* variable size */ } /** Print */ public void print(){ Iterator i = comp.iterator(); // previously for loop while(i.hasNext()){ Component c = (Component)i.next(); c.print(); } } /** Add */ public void add(Component c){ comp.add(c); } /** Remove */ public void remove(Component c){ comp.remove(c); // previously not implemented } }
OOP: Collections 10

Evaluation of the Composite Design Pattern

Made List and Single classes look alike when printing from
the client's point of view.

The main objective! Can call dummy add/remove methods on these instances (FIXED using abstract class)

Can make instances of Component class, not the intension

Can call add/remove method of Single objects, not the

intension. (CANNOT BE FIXED). Fixed length, not the intension. (FIXED using collection instead of array) Added remove method very simple with collections. Nice design! And now complete!

OOP: Collections

11

The Collection Annoyance, Java 1.4

import java.util.*; // skeleton classes class Apple { private int weight; } class Banana{ private int length;} public class CollectionAnnoyance{ public static void main(String[] args){ Collection c = new ArrayList(); for(int i = 0; i < 10; i++){ c.add(new Apple(i)); // note upcast } c.add(new Banana()); // ups // c.add(c); // ups ups do not try this at home! Iterator i = c.iterator(); while (i.hasNext()){ Apple a = (Apple) i.next(); // note downcast } } }
OOP: Collections 12

The Set Interface

Corresponds to the mathematical definition of a set (no
duplicates are allowed). {e1, e2, ... ,en} {7, 3, 6, 4} {Holland, China, Brazil}

Compared to the Collection interface

Interface is identical. Every constructor must create a collection without duplicates. The operation add cannot add an element already in the set. The method call set1.equals(set2) works at follows

set1 set2, and set2 set1

OOP: Collections

13

Set Idioms
set1 set2

set1.addAll(set2) set1.retainAll(set2) set1.removeAll(set2)

set1 set2

set1 set2

OOP: Collections

14

HashSet and TreeSet Classes

HashSet and TreeSet implement the Set interface HashSet

Implemented using a hash table No ordering of elements add, remove, and contains methods constant time complexity O(c), c = constant

TreeSet

Implemented using a tree structure. Guarantees ordering of elements. add, remove, and contains methods logarithmic time complexity O(log (n)), n = number of elements in collection
15

OOP: Collections

HashSet, Example
// [Source: java.sun.com] import java.util.*; public class FindDups { public static void main(String args[]){ Set s = new HashSet(); for (int i = 0; i < args.length; i++){ if (!s.add(args[i])) System.out.println("Duplicate detected: " + args[i]); } System.out.print(s.size() + " distinct words detected: "); System.out.println(s); } }

OOP: Collections

16

The List Interface

The List interface corresponds to an order bag of elements.
<e1, e2, ... ,en> <3, 1, 7, 1> <1, 1, 3, 7> <Holland, China, Brazil> Extensions compared to the Collection interface

Access to elements via indexes, like arrays

add(int, Object), get(int), remove(int), set(int, Object) (note set = replace bad name for the method) indexOf(Object), lastIndexOf(Object)

Search for elements

Specialized Iterator, call ListIterator Extraction of sublist

subList(int fromIndex, int toIndex)

17

OOP: Collections

The List Interface, cont.

Further requirements compared to the Collection Interface add(Object)

adds at the end of the list removes at the start of the list the ordering of the elements is taken into consideration list1.equals(list2) implies that list1.hashCode()==list2.hashCode()

remove(Object)

list1.equals(list2)

Extra requirements to the method hashCode.

OOP: Collections

18

The List Interface, cont.

public interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); void add(int index, Object element); Object remove(int index); boolean addAll(int index, Collection c); // Search int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator listIterator(); ListIterator listIterator(int index); // Range-view List subList(int from, int to); // // // // Optional Optional Optional Optional

}
OOP: Collections 19

ArrayList and LinkedList Classes

Both implement the List interface. ArrayList

Array based implementation Elements can be accessed directly via the get and set methods Default choice for simple sequence

LinkedList

Based on a double linked list Gives better performance on add and remove compared to ArrayList Gives poorer performance on get and set methods compared to ArrayList
20

OOP: Collections

ArrayList, Example
// [Source: java.sun.com] import java.util.*; public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i = 0; i < args.length; i++) l.add(args[i]); Collections.shuffle(l, new Random()); System.out.println(l); } }

OOP: Collections

21

The Map Interface

A Map is an object that maps keys to values. Also called an
associative array or a dictionary. {k1 v1, k2 v2, ... , kn vn}

Methods for adding and deleting

put(Object key, Object value) remove (Object key) get (Object key) keySet() // returns a Set values() // returns a Collection entrySet() // returns a Set
22

Methods for extraction objects

Methods to retrieve the keys, the values, and (key, value) pairs

OOP: Collections

The Map Interface, cont.

public interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // Collection Views public Set keySet(); public Collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); }

OOP: Collections

23

HashMap and TreeMap Classes

Both implement the Map interface. HashMap

The implementation is based on a hash table No ordering on (key, value) pairs

TreeMap

The implementation is based on red-black tree structure (key, value) pairs are ordered on the key

OOP: Collections

24

HashMap, Example
import java.util.*; public class Freq { private static final Integer ONE = new Integer(1); public static void main(String args[]) { Map m = new HashMap(); // Initialize frequency table from command line for (int i=0; i < args.length; i++) { Integer freq = (Integer) m.get(args[i]); m.put(args[i], (freq==null ? ONE : new Integer(freq.intValue() + 1))); } System.out.println(m.size()+ " distinct words detected:"); System.out.println(m); } }

OOP: Collections

25

Collection Interfaces and Classes

OOP: Collections

[Source: bruceeckel.com]

26

Collection Advantages and Disadvantages

Advantages Can hold different types of objects Resizable Same interface to many different implementations Simple Well-designed Disadvantages Can hold different types of objects Must cast to correct type Cannot do compile-time type checking. Must wrap primitive types to store these

Fixed in Java 5.0

OOP: Collections

27

The Collection Annoyance, Java 5.0

import java.util.*; // skeleton classes class Apple { private int weight; } class Banana{ private int length;} public class CollectionAnnoyance{ public static void main(String[] args){ Collection<Apple> c = new ArrayList<Apple>(); for(int i = 0; i < 10; i++){ c.add(new Apple(i)); // no upcast } //c.add(new Banana()); // compile-time error //c.add(c); // compile-time error Iterator i = c.iterator(); while (i.hasNext()){ Apple a = i.next(); // no downcast } } }
OOP: Collections 28

HashMap, Example, Java 5.0

import java.util.*; // [java.sun.com] // Prints a frequency table of the words on the command line public class Frequency { public static void main(String[] args) { // use Java 5.0 generics features Map<String, Integer> m = new TreeMap<String, Integer>(); // use new for each loop for (String word : args) { Integer freq = m.get(word); // automatic auto-boxing and unboxing m.put(word, (freq == null ? 1 : freq + 1)); } System.out.println(m); } }

OOP: Collections

29

Summary
Array

Holds objects of known type. Fixed size. Generalization of the array concept. Set of interfaces defined in Java for storing object. Multiple types of objects. Resizable. Introduced generics

Collections

Major changes to in Java 5

OOP: Collections

30

Static Methods on Collections

Collection

Search and sort: binarySearch(), sort() Reorganization: reverse(), shuffle() Wrappings: unModifiableCollection, synchonizedCollection

OOP: Collections

31

LinkedList, Example
import java.util.*; public class MyStack { private LinkedList list = new LinkedList(); public void push(Object o){ list.addFirst(o); } public Object top(){ return list.getFirst(); } public Object pop(){ return list.removeFirst(); } public static void main(String args[]) { Car myCar; MyStack s = new MyStack(); s.push (new Car()); myCar = (Car)s.pop(); } }
OOP: Collections 32

The ListIterator Interface

public interface ListIterator extends Iterator { boolean hasNext(); // from Iterator Object next(); // from Iterator boolean hasPrevious(); Object previous(); int nextIndex(); int previousIndex(); void remove(); void set(Object o); void add(Object o); } // from Iterator Optional // Optional // Optional

OOP: Collections

33