Transcript ADTs, Collection Interface, Java Collections API

Collection, Iterable, and Iterator Interfaces
•
•
•
•
The Collection Interface and its Hierarchy
The Iterable and Iterator Interfaces
For-each Loops with Iterable Collections
Introduction to Exercise 1
1
The Collection Interface
• Any class that implements the Collection
interface can contain a group of objects
• The type of objects that a Collection class
contains can be specified using generics <T>
• ArrayList class implements Collection
• Hence, polymorphism allows us to do these:
ArrayList<String> a = new ArrayList<String>();
Collection<String> c = a; // widening
ArrayList<String> d = (ArrayList<String>) c;
2
Collection Interface Methods
boolean add(T o)
addAll(Collection c)
void clear()
boolean contains(T o)
boolean containsAll(Collection c)
boolean equals(Object o)
int hashCode()
boolean isEmpty()
3
Collection Interface Methods
Iterator iterator()
boolean remove(T o)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
int size()
Object [] toArray()
4
ArrayList Unique Methods
• Any methods involving indexing:
void add(int index, T o)
boolean addAll(int index, Collection c)
T get(int index)
int indexOf(T element)
int lastIndexOf(T element)
T remove(int index)
T set(int index, T element)
• Indexing is NOT a feature of all collections
• It is a unique feature of the ArrayList class
5
The Collection Interface Hierarchy
• Typically, the Collection interface is not
implemented directly by a class
• There is a hierarchy of interfaces that
extend the Collection interface
• Each subclass of the Collection interface
is designed to support a specific model for
access to the contents of the collection
– List, Set, Stack, Queue, etc.
6
The Collection Interface Hierarchy
<<interface>>
Iterable
<<interface>>
Collection
<<interface>>
List
<<interface>>
Set
<<interface>>
SortedSet
<<interface>>
Queue
7
The Collection Class Hierarchy
<<interface>>
List
<<abstract>>
AbstractList
<<abstract>>
AbstractCollection
<<abstract>>
AbstractSet
<<interface>>
Collection
<<abstract>>
AbstractQueue
ArrayList
8
Iterating over a Collection
• Many times, we need to write code that
retrieves the elements of a collection in a
fashion according to its access model
• In Java, we refer to this as iterating over
the collection
• Collection extends Iterable
(which is another interface) so let’s look at
what that means
9
Iterable Objects and Iterators
• An Iterable object allows you obtain an Iterator
object to retrieve objects from it
Iterator<T> iterator() returns an Iterator
object to access this Iterable group of objects
• An Iterator object allows you to retrieve a
sequence of T objects using two methods:
boolean hasNext() returns true if there are more
objects of type T available in the group
T next() returns the next T object from the group
10
Iterable Objects and Iterators
• Classes in the Java standard class library
that implement the Collection interface are
Iterable OR you can implement Iterable in
a class that you define (Project 1)
• If bookList is an object of an Iterable
class that contains Book objects, we can
retrieve all the available Book objects in
either of two ways:
11
Iterable Objects and Loops
• We can obtain an Iterator object from an
Iterable object and use it to retrieve all the
items from the Iterable object indirectly:
Iterator<Book> itr = bookList.iterator();
while (itr.hasNext())
System.out.println (itr.next());
• The Java 5.0 for-each loop simplifies the
repetitive processing of the items available
from an Iterable object
for (Book myBook : bookList)
System.out.println (myBook);
12
Iterators and Loops
• If bookList is an object of an Iterator
class that contains Book objects, you can
access all the available objects directly:
while (bookList.hasNext())
System.out.println (bookList.next());
• You can not use a “for-each” loop on an
object of a class that only implements
Iterator but does not implement Iterable
13
Use of Exceptions
• In some cases, there may be constraints
that prevent the execution of a method for
a specific instance of a collection object
• For example, a remove operation can not
be performed on a collection that is empty
• A remove method for a set collection may
be coded to check for an empty set
• If an empty set is found, it may throw an
EmptySetException
14
Use of Exceptions
• Hence, a method of a collection object may have a throws
clause in its header
T remove() throws EmptySetException
• To throw an exception, the method uses:
throw new EmptySetException(“string”);
• The exception itself is defined as a class:
public class EmptySetException
extends RuntimeException
{
public EmptySetException (String set)
{
super ("The " + set + " is empty.");
}
}
15
Introduction to Exercise 1
• Sudoku puzzles are quite the rage today
• Solving a Sudoku puzzle involves filling a set
of numbers into an NxN array so there is
exactly one number of each value 1-N in
each row, column, and N1/2xN1/2 box
• You won’t need to write a program that
solves Sudoku puzzles!
• In Exercise 1, you will write a program that
validates the solution of a Sudoku puzzle.
16
Introduction to Exercise 1
• In Exercise 1, you need to implement:
– An Iterable class to contain the N2 cells of a Sudoku
puzzle and a Cell class to represent each cell
– An Iterator class that returns arrays of cells in the order of
their rows, columns, and N1/2xN1/2 boxes
– An isSolution method that iterates over the puzzle and
determines if each row, column, and N1/2xN1/2 box is valid
• The Iterator will return each cell three times:
– In its row
– In its column
– In its N1/2xN1/2 box
17
UML Class Diagram for Project 1
<<interface>>
Iterable
+ iterator() : Iterator
SudokuValidator
<<interface>>
Iterator
+ main (args: String [ ] ) : void
- isSolution(puzzle : Sudoku) : bool
<<uses>>
<<uses>>
+ hasNext() : bool
+ next() : Object
+ remove() : void
<<instantiates>>
Cell
Sudoku
- puzzle : Cell [ ] [ ]
- Sudoku()
+ Sudoku(file : Scanner)
+ toString () : String
- value : int
SudokuIterator
<<uses>> - puzzle : Cell [ ][ ]
- Cell()
- cursor : int
+Cell(value : int)
{See assignment text}
+setValue(value : int)
- SudokuIterator ()
+getValue() : int
+ SudokuIterator
(puzzle : Cell [ ][ ])
<<instantiates>>
18
Introduction to Project 1
• To loop through a two dimensional array
using for statements is relatively intuitive:
Cell [][] puzzle = new Cell[size][size];
...
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
//statements using puzzle[i][j]
• It is obvious that this algorithm is O(n2) for
n = size
19
Introduction to Project 1
• If an Iterator on a collection with an internal
NxN array returns one element each time,
the algorithm appears to have only one loop
and be O(n), but it is not!
• The code using the Iterator object has:
while (iterator.hasNext())
//statements using iterator.next()
• The hasNext() method returns true N2 times
• The next() method returns N2 times - each
time with another Cell from the NxN array
20
• Hence, it is O(N2) with respect to N
Introduction to Project 1
• However, in Project 1 with an NxN array:
• hasNext( ) returns true 3xN times
• next( ) returns a one dimensional Cell [ ] of
length N for N rows, N columns, and N boxes
• The iteration process g(N) is 3xN and is O(n)
• However, the code calling the hasNext( ) and
next ( ) methods processes N elements each
time for overall g(N) = 3NxN or O(N2) again
21
Introduction to Project 1
• For a “rows only” SudokuIterator class:
• Class Header could be:
public class SudokuIterator implements Iterator<Cell[]>
{
private Cell [][] puzzle;
private int SIZE;
private int cursor;
• Constructor could be:
public SudokuIterator(Cell [][] puzzle)
{
this.puzzle = puzzle;
SIZE = puzzle.length;
cursor = 0;
}
22
Introduction to Project 1
• For a “rows only” Interator class:
• Code in Iterator hasNext method could be:
public boolean hasNext()
{
return cursor < SIZE;
}
• Code in Iterator next method could be:
public Cell [] next()
{
value = puzzle[cursor];
cursor++;
return value;
}
23