Transcript 04 – Abstract Classes and Interfaces

05 - Containers
-------------- DRAFT COPY ------------------------
Container



A container allows objects to be stored and retrieved.
There are different types of collections according to the
additional services and behaviour they implement
Ordered
Duplicates
Bags
NO
YES
Sets
NO
NO
Lists
YES
YES
Maps
NO
key value pairs key
unique for each
element
Bags are not included in the Java Standard Library.
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
2
-------------- DRAFT COPY ------------------------
The Container Class Hierarchy
interface
Map
interface
Set
interface
Collection
AbstractCollection
AbstractSet
HashSet
Extract from the
Java Standard
Library hierarchy
for Containers
interface
List
AbstractList
Vector
class HashSet extends AbstractSet implements Set … { … }
© S. Uchitel, 2004
Vector
-------------- DRAFT COPY ------------------------
3
-------------- DRAFT COPY ------------------------
java.util.Collection <<Interface>>
interface Collection { // This is only a subset of the methods
boolean add(Object o) ;
boolean remove(Object o);
boolean contains(Object o);
// How do you think this is implemented?
boolean isEmpty();
Iterator iterator();
// Returns an iterator over the elements
int size();
// Returns the number of elements
// … many other methods
}
Refer to the Java Documentation
for the full definition!
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
4
-------------- DRAFT COPY ------------------------
What is an Iterator?

Iterator – An interface which permits iteration
over the elements of a collection:
interface Iterator {
// This is only a subset of the methods
boolean hasNext(Object o);
Object next() ;
boolean remove(Object o);
}
© S. Uchitel, 2004
// … many other methods
-------------- DRAFT COPY ------------------------
5
-------------- DRAFT COPY ------------------------
Collections and Iterators: Examples
public printStudents(Collection students) {
Iterator myIterator = students.iterator();
while (myIterator.hasNext()) {
Student s = (Student) myIterator.next();
System.out.println(s.name);
}
Why is this casting needed?
Is it up or down?
Are we guaranteed success?
public findAndPrintName(Collection c, String login) {
Iterator myIterator = c.iterator();
while (myIterator.hasNext()) {
Student s = (Student) myIterator.next();
if (s.getLogin().equals(login))
System.out.println(s.name);
// Once found I continue to search. I do not
// assume the collection is a set.
}
}
© S. Uchitel,
2004
-------------- DRAFT COPY ------------------------
6
-------------- DRAFT COPY ------------------------
Sets




A set is a Collection that cannot
contain duplicate elements
Interestingly, the interface set
does not add anything to the
collection interface. However, it is
documented differently (the pre
and post conditions of the methods
change)
Elements compared with
equals(Object o).
See the Java documentation for
interface Set
© S. Uchitel, 2004
interface
Set
interface
SortedSet
AbstractSet
TreeSet
-------------- DRAFT COPY ------------------------
HashSet
7
-------------- DRAFT COPY ------------------------
Sets: Example
public Set getUndergraduateStudents(Set students) {
// Returns a set with all undergraduates
// that are in set students.
Note that parameter type Set
Set undergrads = new HashSet();
//Why not “new Set();”?
decouples us from the method
user’s choice of implementation
for the set of students
Iterator myIterator = students.iterator();
while (myIterator.hasNext()) {
Object o = myIterator.next();
if (o.instanceOf(Undergraduate))
undergrads.add(o);
}
Note that the actual type returned (HashSet)
is a subclass of the return type declared (Set)
return undergrads;
}
© S. Uchitel, 2004
Decouples method user from our choice
implementation for the set of undergraduates
-------------- DRAFT COPY ------------------------
8
-------------- DRAFT COPY ------------------------
Sets and Equality: Example
public class Book {
protected int isdn;
protected String title;
Book(int isdn, String title) {
this.isdn = isdn;
this.title = title
}
public boolean equals(Book b) {
return (isdn == b.isdn)
}
}
© S. Uchitel, 2004
public void example() {
Set s = new HashSet();
Book b = new Book(1, “Kenya”);
s.add();
//s.size() is 1
s.add(new Book(2, “Haskell”));
//s.size() is 2
s.add(new Book(1, “Java”));
//s.size() is 2
s.add(new Book(3, “Haskell”));
//s.size() is 3
s.remove(b);
//s.size() is 2
s.add(new Book(1, “Java”));
//s.size() is 3
}
-------------- DRAFT COPY ------------------------
9
-------------- DRAFT COPY ------------------------
Sorted Sets

Some Collections are sorted



To sort the elements of a collection one needs to
either:



see SortedSet Interface (includes first(), last() and others)
see the TreeSet implementations
have "Comparable" elements, or
provide a "Comparator" function to the sorted collection
upon creation.
Comparable elements implement:
public interface Comparable {
public int compareTo(Object o); /* returns > 0 if this greater than
o, 0 if equal or < 0 if this less than o */
} // NB. Must be consistent with equals()
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
10
-------------- DRAFT COPY ------------------------
Ordered Sets: Example
public class Book implements Comparable {
protected int isdn;
protected String title;
Book(int isdn, String title) {...}
public boolean equals(Book b) {...}
public void print() {
System.out.print(isdn + “:” + title);
}
public int compareTo(Object o);
if (o.instanceOf(Book)
return (isdn–((Book) o).isdn));
else
return –1;
}
}
© S. Uchitel, 2004
public void easySort(Set books) {
SortedSet s = new TreeSet();
s.addAll(books);
myIt = s.iterator();
while (myIt.hasNext()) {
Book b = (Book) myIt.next();
b.print();
}
}
11
-------------- DRAFT COPY ------------------------
-------------- DRAFT COPY ------------------------
Lists


Ordered collection which may contain
duplicate elements
Provide operations for



Positional access – manipulate elements based on
their numerical position in the list
Search
Extended iterator
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
12
-------------- DRAFT COPY ------------------------
Lists
interface
List
AbstractList
Vector
ArrayList
AbstractSequentialList
Stack
SubList
LinkedList
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
13
-------------- DRAFT COPY ------------------------
List <<interface>>
public interface List extends Collection {
void add(int index, Object o);
Object get(int index); // Returns the element at index
int indexOf(Object o); /* Returns the index in this list of the first
occurrence of the specified element, or -1 if
this list does not contain this element */
int lastIndexOf(Object o) ;
ListIterator listIterator() ;
// Returns a list iterator - guaranteed order
ListIterator listIterator(int index) ;
Object remove(int index) ;
Object set(int index, Object element); // replace element at index
List subList(int fromIndex, int toIndex) ; // returns sublist between indexes
// …
}
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
14
-------------- DRAFT COPY ------------------------
ListIterator <<interface>>
public interface ListIterator extends Iterator {
void add(Object o) ;
boolean hasPrevious() ;
int nextIndex() ;
// Returns the index of the next element
Object previous() ;
int previousIndex() ;
// Returns the index of the previous element
void set(Object o);
// Replaces the element at the current index
}
What do alternate
calls to next and
previous return?
0
1
© S. Uchitel, 2004
2
3
4
5
Index
-------------- DRAFT COPY ------------------------
15
-------------- DRAFT COPY ------------------------
List: Example
// Swap two elements with index i and j in a list
public static void swap(List l, int i, int j) {
Object tmp = l.get(i); l.set(i, l.get(j)); l.set(j, tmp);
}
// Sort elements on add. Requires elements to implement Comparable
class MySortedSet {
private LinkedList _obj = new LinkedList();
public boolean add(Object o) {
Comparable c = (Comparable) o; // run time error if this fails
ListIterator i = _obj.listIterator();
while (i.hasNext()) {
int val = c.compareTo(i.next());
if (val == 0) { return false; /* Object already exists*/ }
if (val < 0) {_obj.add(i.previousIndex(),o); return true; }
}
_obj.addLast(o); return true;
}
}
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
16
-------------- DRAFT COPY ------------------------
Maps



Stores pairs of objects: <key, value>
They are not a subclass of Container
Map Interface:





void put(Object key, Object value)
Object get(Object key)
Set keySet() <- Keys are unique
Collection values() <- A value could be paired to
several keys
Careful: if you modify the object returned by
keySet() or values() you are tinkering with
the internal representation of the map!
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
17
-------------- DRAFT COPY ------------------------
Maps: Example
public class Registrations {
Map regs = new HashMap();
...
public register(Student s, Course c) {
Set mySet;
if (!regs.keySet().contains(c)) {
//Map has no set of registered students for course c
mySet = new HashSet();
regs.put(c, mySet); //Associate empty set to course c
}
else {//Get set of students registered for c
mySet = (Set) regs.get(c);
}
//mySet is the set of registered students for course c
mySet.add(s); //Add student to set of registered students for c
}
Note that there is no need to do
regs.put(c, mySet) to update the map. Why?
18
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
-------------- DRAFT COPY ------------------------
Summary Implementations
Hash
Table
Set
Interfaces
© S. Uchitel, 2004
HashSet
List
Map
Resizable
Array
Balanced
Tree
TreeSet
ArrayList
HashMap
Linked
List
LinkedList
TreeMap
-------------- DRAFT COPY ------------------------
19
-------------- DRAFT COPY ------------------------
Checklist








Collections
Bags vs. Sets vs. Lists vs. Maps
The Java Collections Hierarchy: Interfaces,
Abstract Classes and Concrete Classes
Iterators
Sets and equality
Sorted sets and the Comparable interface
Lists and ListIterators
Maps
© S. Uchitel, 2004
-------------- DRAFT COPY ------------------------
20