Transcript 12_Collections

Collections Framework
A collections framework is a unified architecture for representing and
manipulating collections. All collections frameworks contain:
•Interfaces:
– abstract data types representing collections.
• allow collections to be manipulated independently of the details of their
representation.
•Implementations:
– concrete implementations of the collection interfaces. In essence, these are
reusable data structures.
•Algorithms:
– methods that perform useful computations on objects that implement
collection interfaces
• e.g. searching and sorting,.
• polymorphic
• reusable functionality
1
Java Collections
The Collections framework includes classes that implement
Collection, and are thus able to be declared using a specific
type
Concrete implementations:
Set
List
SortedSet
SortedMap
TreeSet
ArrayList
Vector
Collections
Map
HashSet
LinkedList
Arrays
These allow programmers to focus on the abstract, logical properties,
ignoring implementation details.
2
Collections Interfaces
Interfaces
Collection
Set extends Collection
implemented by HashSet, TreeSet
SortedSet extends Set
implemented by TreeSet
List extends Collection
implemented by ArrayList, LinkedList
Map
implemented by HashMap, TreeMap
SortedMap extends Map
implemented by TreeMap
Note Class HashSet corresponds to Hashtable in JDK 1.1 and class
ArrayList corresponds to Vector in JDK 1.1. But these older classes are
no longer needed.
3
Collections Interfaces
Collections represent possibly duplicated, unordered collections of objects:
public interface Collection {
int size();
boolean isEmpty();
boolean contains(Object obj);
boolean add(Object obj);
boolean remove(Object obj);
Iterator iterator();
}
.
Iterators (cf. string tokenizers) are used to inspect each element of a collection in turn.
public interface Iterator {
boolean hasNext();
Object next();
}
Basic iterator usage:
Collection c; ...; Iterator it = c.iterator();
while (it.hasNext()) { /* use it.next() */ }
4
Collections Class: Set
Sets represent duplicate-free, unordered collections of objects.
public
interface Set extends Collection
.
boolean containsAll(Collection c);
void addAll(Collection c);
void retainAll(Collection c);
void removeAll(Collection c);
{
//
//
//
//
subset
union
intersection
difference
// Plus methods inherited from class Collection
}
These additional methods correspond to set-theoretic operations as
follows. Suppose S and T are variables of type Set. Then:
S.contains(x)
is equivalent to
S.containsAll(T) is equivalent to
S.addAll(T)
is equivalent to
S.retainAll(T) is equivalent to
S.removeAll(T) is equivalent to
x
S
S
S
S


=
=
=
S.
T.
S  T.
S  T.
S  T.
5
Example - Find distinct words
Print all distinct command line arguments to standard output.
class Words {
public static void main(String[] args) {
Set words = new HashSet(); // Set of words seen
// Add new command line arguments to words
for (int i = 0; i < args.length; i++) {
words.add(args[i]);
}
// Print elements of words one per line
// Cf. System.out.println(words);
Iterator it = words.iterator();
while (it.hasNext() ) {
System.out.println(it.next());
}
}
}
6
Example - Find distinct words
Usage:
$ java Words I am who I am
am
I
who
$
Note If we had used TreeSet (which implements SortedSet) instead of
HashSet , the set words would have been maintained in its natural
(alphabetical) order, and the output would have been ordered:
I
am
who
7
Example - Find repeated words
Print all command line arguments that occur more than once to standard
output.
class Words {
public static void main(String[] args) {
Set words = new HashSet(); // Set of all words
Set repWords = new HashSet(); // Set of repeated words
// Add new command line arguments to words
for (int i = 0; i < args.length; i++) {
String word = args[i];
if (repWords.contains(word)) {
/* skip */
} else if (words.contains(word)) {
repWords.add(word)
} else {
words.add(word);
}
}
// Print elements of repWords one per line
Iterator it = repWords.iterator();
while (it.hasNext() ) {
System.out.println(it.next());
}
}
}
8
Collections Class: List
Lists represent possibly duplicated, ordered collections of objects.
public interface List extends Collection {
Object get(int index);
Object set(int index, Object obj);
void add(int index, Object obj);
Object remove(int index);
List subList(int from, int to);
ListIterator listIterator();
// Plus methods inherited from class Collection
}
A list (or Vector in JDK 1.1) is like an array except that:
•
•
•
•
Its elements must be objects (not primitive types or arrays).
Its elements may be values of different types.
Its size can grow and shrink dynamically.
It can be efficient to add and remove elements in the middle of the list.
9
Example – Reverse a List in place
public void reverse (List objs) {
int i = 0, j = objs.size()-1;
while (i < j) {
// Exchange elements at positions i and j
Object tmp = objs.get(i);
objs.set(i, objs.get(j));
objs.set(j, tmp);
i++; j--;
}
}
10
Example – Return a List that is the reverse of another
Return a new list containing the elements of the given list in
reverse order.
public List reverse (List objs) {
List revObjs = new ArrayList(); // the new list
// Add elements to revObjs from the end of objs
for (int i = objs.size()-1; i >= 0; i--) {
revObjs.add(objs.get(i));//append to the end of
revObjs
}
return revObjs;
}
Note Collection parameters, local variables and results all have
interface types (e.g., List), not implementation types (e.g.
ArrayList).
11
Collections Class: Map
Maps represent finite mappings or functions from keys to values:
public interface Map {
int size();
boolean isEmpty();
Object put(Object key, Object value);
Object get(Object key);
Object remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
public Set keySet();
public Collection values();
public Set entrySet();
}
A map is equivalent to a set of (key, value) pairs. (Cf. a pair of parallel arrays, or
Dictionary in JDK 1.1.) The keys and values may be objects of any type. There
may be any (finite) number of (key, value) pairs. Each key must be distinct, but
different keys may map to the same value.
12
Example - Count distinct words
class CountWords {
public static final Integer ONE = new Integer(1);
public static void main(String[] args) {
Map map = new HashMap(); // Maps words to no. of occs.
for (int i = 0; i < args.length; i++) {
// Get number of occurrences of next word
Works
Integer value = (Integer) map.get(args[i]);
// Increment number of occurrences of word
if (value == null) {
map.put(args[i], ONE);
} else {
int val = value.intValue();
map.put(args[i], new Integer(val+1));
}
}
// Print number of occurrences of each word
System.out.println(map);
}
}
13
Example - Count distinct words (con’t.)
Another way to print the final value of map (version 2):
// Print values of map, one per line
Iterator it = map.keySet().iterator();
while (it.hasNext() ) {
Object key = it.next();
System.out.println(key + " = " + map.get(key));
}
And yet another way (version 3):
// Print values of map, one per line
Iterator it = map.entrySet().iterator();
while (it.hasNext() ) {
Map.Entry e = (Map.Entry) it.next();
System.out.println(e.getKey() + " = " +
e.getValue());
}
14
Example - Count distinct words (con’t.)
Usage (version 1):
$ java Words I am who I am
{am=2,who=1,I=2}
$
Usage (versions 2 and 3):
$ java Words I am who I am
am = 2
who = 1
I = 2
$
Note Again, if we had used TreeMap instead of HashMap, the keys would
have been processed (and printed) in their natural (alphabetical) order.
15
Example - Concordance
A concordance for a given text file is a listing of all words that
occur in the file, together with a list of all the pages (or lines)
on which each word occurs.
This requires a collection of collections.
•The outer collection has keys the words.
– Each (key,value) pair is a word and a List.
• The List holds the page numbers for that word
Simpler version: Concordance.java counts #times each
character occurs.
• Each (key,value) pair is a character and an integer .
See java/Collections/Concordance
16
Example - Library database
The collection of collection paradigm can be used to model a (book) library,
keeping track of loans of books by borrowers.
– Each person can borrow one or more books.
– Each book can only be borrowed by a single person (at one time).
•Can implement methods for:
– borrowing and returning books
• displaying which books have been borrowed by a given person
• determining which person has borrowed a given book.
model information about loans as two related maps, allowing greater clarity
and faster searches:
– person: a map from persons to lists (or sets) of books, and
– book:
an inverse map from books to persons.
17
Example - Library database (cont.)
Person map
p1
b2 b10 b5 b3
(book list)
b7 b12 b1
(new book in list)
p5
p3
…
Book map
p1
b10
(person)
…
18
Example - Library database (cont.)
Probably the most subtle method in the implementation using maps and
lists is the following. It requires careful study, using the diagram on the
previous slide.
// Pre: book b is not currently borrowed
// Post: person p has borrowed b
public void borrow (String p, String b) {
// Get books borrowed by person p
List books = (List) person.get(p);
if (books == null) {
// if none =>
books = new ArrayList(); // make it an empty list
person.put(p, books);
}
books.add(b);
// Add b to the books borrowed by p
// (No additional put is needed)
book.put(b, p); // Make p the borrower of b
}
p5
p5
p5
b3
19
The Collections Framework (cont.)
compare objects for equality:
– based on one or more of its components
– compute a hash code that depends on one or more components.
• the components form a key that uniquely identifies the object.
• must override the definitions of methods equals and hashCode inherited from
class Object.
class Book
public
public
public
...
public
if
{
String catref; // key for books
String title;
String author;
boolean equals (Object o) {
(o == null || ! (o instanceof Book))
return false;
else
return catref.equals(((Book) o).catref);
}
public int hashCode () {
return catref.hashCode();
}
}
20
Notes on the collections framework
1.
2.
3.
4.
5.
6.
Use the collections framework to implement sets, lists, dynamic arrays, and
maps.
Always import java.util.*;
Use interface types – Set, List, Map – for variables and parameters
Use implementation types – HashSet, ArrayList – only in constructors.
Lists, maps, etc., must contain objects, not primitive types or arrays.
Remember to specify values selected from collections and maps to the
appropriate type, e.g., if a list ints is known to contain values of type
Integer, then you should declare it
List<Integer> ints to avoid
casting:
Integer i = (Integer) ints.get(0);
7.
to retrieve the first integer. Omitting the cast is a compile-time error only if the
collections element type hasn’t been specified.
A class List is defined in both packages java.awt and java.util. It is thus
necessary to write, e.g., java.util.List in variable declarations and casts
when both packages are being used.
21
Notes on the collections framework (con’t)
8.
This method can transform arrays to lists:
Arrays.asList(Object[] a);
9.
Returns a list containing the objects of the array argument.
Use the following method to transform collections (e.g., sets and lists) to
arrays:
collection.toArray();
Returns an array containing the objects of the given collection.
10. Use the following constructor to create a list from any collection:
List list = new ArrayList(collection);
There is a simple constructor for LinkedList.
22