Transcript 04.Collections - Calvin College

Collections
Joel Adams and Jeremy Frens
Calvin College
(1/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Review: The API
We’ve seen that classes can be organized into hierarchies…
We’ve also seen that the Java API provides documentation…
The API lets you easily find:
 What methods are defined within a class
 What methods are inherited from its superclass
 What methods are inherited from its superclass
 …
 What methods are inherited from the Object class.
The API is an invaluable resource for Java programmers.
(2/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
javadoc
How is the Java API created and maintained?
Java distributions include a utility called javadoc that
automatically generates HTML API-style pages for a class.
javadoc scans a .java file for special javadoc comments:
and within those comments,
scans for javadoc tags:
Running javadoc on that
file will then generate
documentation pages similar
to those of the API.
(3/21)
2003 Joel C. Adams. All Rights Reserved.
/**
@author <i>Adams</i>
@version 1.0
@param Siemens
@param Dematic
@return Java
@see Frens
*/
Dept of Computer Science
Calvin College
Exercise: Part I
Work through Part I of today’s exercise:
1. Examine the javadoc comments in the source files below:
2. Then run javadoc on them.
3. Then use your browser to examine
the HTML files javadoc generated.
Name.java
PhoneNumber.java
Person.java
Employee.java
4. Make the suggested modifications to the source files,
repeat steps 2 & 3 to see view the changes.
(4/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
javadoc Tags
As of version 1.4.2, javadoc looks for these tags:
@author
@docRoot
@deprecated
@exception
@inheritDoc
@link
@linkPlain
@param
@return
@see
@serial
@serialData
@serialField
@since
@throws
@value
@version
Javadoc also lets you create your own custom tags via doclets…
@see http://java.sun.com/j2se/1.4.2/docs/tooldocs/javadoc/index.html
(5/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Interfaces
In addition to the class, Java also supports the interface …
A Java class can extend just 1 superclass (single inheritance)
A Java class can implement multiple interfaces…
So what is an interface?
 A set of requirements that:
• Classes wanting to conform to the interface must implement; and
• Users of such classes can assume have been implemented.
Uses the keyword interface in place of class
Implementers use the keyword implements
instead of extends
An alternative means of declaring a handle.
(6/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Interface Example
Java provides a Comparable interface:
public interface Comparable {
public int compareTo(Object other);
}
We could update our Employee class by adding:
class Employee extends Person implements Comparable {
public int compareTo(Object other) {
if (other instanceof Employee) {
Employee emp = (Employee) other;
if (myID < emp.getID()) { return -1; }
else if (myID > emp.getID()) { return 1; }
else { return 0; }
} else { return 1; }
} ...
}
(7/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Interface Example (Ct’d)
If a data structure stores Comparable references (handles),
any item in it can be sent the compareTo() message…
Java’s java.util.Arrays class provides these methods:
 sort(), that uses compareTo() to implement a refined
version of the quicksort algorithm;
 binarySearch(), that uses compareTo() to search a
sorted array using the binary search algorithm;
 equals(), that uses compareTo() to determine whether
or not two arrays are equal;
…
We’ll see more of interfaces later.
(8/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Exercise: Part II
Work through Part II of today’s exercise…
1. Follow the directions to implement the Comparable
interface on the class files for Part II.
2. Use the provided Driver to verify
your code.
3. Compare the result of == and equals(). Make sure you
understand why what you observe is happening.
(9/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Containers
The package java.util has Java’s container classes…
 Classes that "contain" (store references to) objects…
AbstractCollection
AbstractList
Abstract
Sequential
List
LinkedList
(10/21)
AbstractMap
AbstractSet
ArrayList
HashSet
HashMap
TreeMap
TreeSet
The “leaf” classes are called the concrete
containers, because they are not abstract.
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
The Container Interfaces
Collection is an interface that other interfaces extend:
«interface»
Collection
«interface»
List
«interface»
Set
«interface»
SortedSet
«interface»
Map
«interface»
Iterator
«interface»
SortedMap
«interface»
ListIterator
You can put(aKey, anObject)
and get(aKey) via a Map…
You can add(anObject) toYou can visit the values in either
a Collection…
using an Iterator…
(11/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
The Collections Framework
Each of the Collections classes implements one or more interfaces….
(12/21)
Class
Implements Interfaces
LinkedList
Cloneable, Collection, List,
Serializable
ArrayList
Cloneable, Collection, List,
RandomAccess, Serializable
HashSet
Cloneable, Collection,
Serializable, Set
TreeSet
Cloneable, Collection,
Serializable, Set, SortedSet
HashMap
Cloneable, Map, Serializable
TreeMap
Cloneable, Map, Serializable,
SortedMap
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Lists
The ArrayList and LinkedList classes implement List
List list1 = new ArrayList(),
list2 = new LinkedList();
// empty; cap. 10
// empty
We can send either object any message from the List API:
list1.add( anObject );
list2.add( anObject );
// O(1)
// O(1)
list1.remove( someObject );
list2.remove( someObject );
// O(n)+O(n)
// O(n)+O(1)
int i = list1.indexOf( anObject ),
// O(n)
j = list2.indexOf( anotherObject ); // O(n)
Object obj1 = list1.get(i),
obj2 = list2.get(j);
...
(13/21)
2003 Joel C. Adams. All Rights Reserved.
// O(1)
// O(n)
Dept of Computer Science
Calvin College
Iterators
… can be used to traverse any of the containers:
Iterator it = list2.iterator();
while ( it.hasNext() ) {
Object obj = it.next();
// do something with obj
}
// like i++
Gotcha: remove() removes the last thing next() returned:
Iterator it1 = list1.iterator(),
it2 = list2.iterator();
it1.next(); it1.remove(); // O(n)
it2.next(); it2.remove(); // O(1)
The ListIterator interface specifies additional operations
that are useful for manipulating LinkedList objects.
(14/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Sets
If the order in which objects are stored doesn’t matter,
then a Set may be the appropriate container…
HashSet hs = new HashSet(); // uses hashCode()
TreeSet ts = new TreeSet(); // uses compareTo()
add(), remove() are used manipulate either kind of Set:
hs.add( anObject );
ts.add( anObject );
hs.remove( anObject );
ts.remove( anObject );
A HashSet stores objects in a hash table (an array of linked
lists), and tries to achieve O(1) access time.
A TreeSet stores objects in a red-black tree (a self-balancing
binary search tree), guaranteeing O(lg(n)) access time.
(15/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Maps
A Set requires an exact copy to do a lookup…
A Map lets you lookup using partial information (a key).
HashMap hm = new HashMap();
TreeMap tm = new TreeMap();
// uses hashing
// uses r-b tree
A Map (aka a dictionary) stores (key, value) pairs:
hm.put( new Integer(emp1.getID() ), emp1);
tm.put( new Integer(emp2.getID() ), emp2);
The value part can then be accessed using the key part:
Employee e1 = (Employee)hm.get( new Integer(anID) );
Employee e2 = (Employee)tm.get( new Integer(anotherID) );
...
hm.remove( new Integer(anID) );
tm.remove( new Integer(anotherID) );
(16/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
The Collections Class
… provides methods that manipulate containers, including:
binarySearch(aList, key)
// return index of key
copy(srcList, destList)
// copy srcList into destList
fill(aList, obj)
// replace all values with obj
max(aCollection)
// return maximum value
min(aCollection)
// return minimum value
replaceAll(aList, old, new) // replace each instance of old with new
reverse(aList)
// reverse the order of values
rotate(aList, i)
// rotate values i positions
shuffle(aList)
// randomly reorder values
sort(aList)
// order values (using Comparable)
swap(aList, i, j)
// swap the values at indices i and j
and many more (see the Collections API)…
(17/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
UML Notation
… represents interface implementation with dashed arrows:
Collection
List
AbstractList
*
AbstractCollection
Random
Access
Abstract ArrayList
Sequential
List
*
Map
Set
Sorted
AbstractSet Set
HashSet
TreeSet
*
Sorted
AbstractMap Map
HashMap
TreeMap
* == Cloneable, Serializeable
LinkedList
(18/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
*
Legacy Classes
Java also provides “legacy” containers that have been a part
of the language since before the collections framework:
List
Map
AbstractList
Dictionary
Deprecated
HashTable
Like HashMap, with all
accesses synchronized
(thread-safe, slow)
Vector
Stack
Like ArrayList,
with all accesses
synchronized
(thread-safe, slow)
An array-based LIFO
(push, pop, peek, …)
Properties
A (String,String) map;
save/load via a file;
secondary defaults table
These do not reflect good object-oriented design…
(19/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Summary
Javadoc provides a convenient way to create hypertext
documentation for a class and its methods.
Java supports only single inheritance, but a class can
implement multiple interfaces.
The java.util package provides several container classes:
ArrayList LinkedList HashSet TreeSet HashMap TreeMap
plus the legacy classes (some of which are deprecated).
These can be used as is, or extended to build other traditional
data structures (Stack, Queue, PriorityQueue, …)
(20/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College
Exercise: Part III
Use the time remaining to complete Part III of today’s
exercise (anything you do not finish is homework).
(21/21)
2003 Joel C. Adams. All Rights Reserved.
Dept of Computer Science
Calvin College