~ number: 6 ~ title: Collections, Iterators, and Meta-iterators
- Introduction to Collections
- Building a Set (finger exercise)
- Introduction to Iterators
- Programming Task: EveryOtherWord.java
- Programming Task: Meta-Iteration through Filters
- Working on Old Exams
Java Collections are pretty handy. In this lab, we'll give a closer look at Collections and Iterators, which we saw in lab 3.
Let's start by looking more closely at the declaration, instantiation, and utilization of Collections, which we've already seen is a bit syntactically strange. For example, to instantiate a list of ints, add the number 5, then get it back, we might write:
List<Integer> s;
s = new ArrayList<Integer>();
s.add(5);
int x = s.get(0); /* gets the five back */
There are three funny things about the syntax above:
- Angle bracket notation to denote the type of the item that goes in the collection. For now at least, you should always use angle brackets for both the declaration and the instantiation. We'll see later in this lab and in this course that angle bracket notation can be used in situations other than using a Collection.
- If you're creating a Collection of primitives you should use the wrapper type (e.g. Integer, Double, Character) instead of the primitive type (e.g. int, double, char).
- The retrieval method of our List returns an Integer, but thanks to
Java magic, the value we want is automatically unwrapped into an
int. For example, the following is valid Java code
int x = new Integer(5)
.
Create a new file SetDemo.java. Do not write tests. It should:
- Declare a Set that holds Strings.
- Instantiate this set by using the constructor of a specific Set implementation. For a list, go to the official Java documentation and look for "All Known Implementing Classes:". You'll need to Google/Bing/Altavista your way to the docs.
- Add the strings "papa", "bear", "mama", "bear", "baby", "bear".
- Print the set. You should observe there are only four items.
You will need the Java documentation to find a concrete set implementation to implement, as well as the name of the method for putting things into a set. Do not ask a lab TA unless you are really stuck. The point here is to self-sufficiently be able to find this sort of information. Don't forget that all objects have a toString() method (not necessarily a useful one, but everything has one at least).
As we saw in lab 3, an iterator is an object whose purpose is to traverse the values in a collection of objects (here we mean the abstract notion of a collection, not necessarily a capital C Collection as defined in Java), yielding them one at a time to the iterator's client. The standard Java library defines a standard interface that iterators can implement:
package java.util;
public interface Iterator<Value> {
/** Returns true iff this iterator has another value to deliver. */
boolean hasNext();
/** Returns the next value from this iterator, and advances to
* the next.
* Precondition: hasNext() must be true.
*/
Value next();
/** Remove the last value delivered by next() from the
* underlying collection of values being iterated over.
* Optional method. May be called at most once per call to
* to next().
*/
void remove();
}
While in principle a collection could itself implement the iterator
interface, this would result in very strange code. Instead,
collections that wish to support iteration typically provide an
Iterator
method that returns an appropriate iterator.
For example, if L is a List<String>
, you can write
for (Iterator<String> i = L.iterator(); i.hasNext();) {
String value = i.next();
System.out.print(value + " ");
}
This code would print out each item in the list, one at a time. An alternate way of writing this code is as follows:
Iterator<String> i = L.iterator();
while (i.hasNext()) {
String value = i.next();
System.out.print(value + " ");
}
In the code above, the List
class provides an iterator
method that
returns an object of type Iterator<String>
. But what is an Iterator
exactly? Well, it's simply an instance of a class that implements the
Iterator interface defined above, i.e. implements Iterator
, and
concomitantly provides a next()
, hasNext()
, and remove()
method.
In fact, we can go look at the
source code of the List interface, but of course since List
is an interface, this
method is abstract and we won't learn much.
Java provides an AbstractList
class that provides default
implementations for many List
methods (much like we saw in Lecture
11 with the Reader
interface). Looking at the source of
AbstractList.iterator(), we see
that this method just returns a new object of type Itr
, where Itr
is some nested non-static class (non-static
nested classes are called inner classes; see Lecture 12).
If we look at the
source code for the Itr inner class
we can see its definition. I don't expect this code to make a great
deal of sense to you, but you should observe that it implements the
iterator
interface and does have a next()
, hasNext()
, and
remove()
method as required by the interface.
Iterating through interfaces using next
and hasNext
would be tedious to have to write every time, and thus Java has introduced a special
syntax for this Java programming idiom known as the Iterable
interface. If L has a type that implements Iterable<String>
(as
List<String>
does), then the loops above may be written
for (String value: L) { System.out.print(value + " "); }
The Iterable
interface is really simple. A class that implements it
must simply provide an iterator method that provides an Iterator
.
package java.lang;
public interface Iterable<Value> {
/** Returns an iterator over my values. */
Iterator<Value> iterator();
}
To summarize: An Iterator
is an object that provides a next()
,
hasNext()
, and remove()
method. Iterators are intended to provide a
way to step through some sort of data structure one item at a time. If
you have access to an iterator to some collection, you can use the
next()
and hasNext()
methods to go through it step by step.
Using next()
and hasNext()
is tedious, so if a class declares itself
as implementing iterable, you can use the : operator to iterate
instead. To follow the iterable contract, the class that impleennts
iterable must provides a method that provides an iterator that allows
iteration through that object.
Food for thought: Why doesn't the List class just implement Iterator itself?
Fill in the everyOtherWord method of EveryOtherWord such that it performs the task described in its comment and passes the test in main(). Do not change anything in the file other than the everyOtherWord method, except that you may import the Iterator class (though this is not necessary). You shouldn't need any helper methods.
As we saw in EveryOtherWord, we don't always want to iterate in exactly the way that the available iterator tells us. One approach is to write special purpose methods (e.g. everyOtherWord) that generate a new Iterable that contain all the items we require. This is fine as long as we have the memory and time to spend on building this iterable, which may potentially be quite large and slow to construct.
An alternate approach is to use an intermediary class that will feed us the items we want, one at a time. These are often referred to as filters.
Open up the Filter
abstract class in the utils
package. You'll see
that it acts as a middleman between client code and some Iterator
.
Specifically, if you look at the hasNext()
method, you'll see that it
keeps calling next()
on the underlying Iterator until the keep()
method returns true.
Concrete implementations of the Filter
class will implement a keep()
method that results in the desired behavior. For example, a filter
designed to only return every other item would return true for every
other call to keep.
Start by completing the implementations of TrivialFilter
and
AlternatingFilter
so that they pass the TestFilter
test. You might
find the FilterClient
class to be useful for manually testing your
implementations.
As an optional but highly recommended exercise, complete an
implementation of MonotonicFilter
that passes the TestFilter
test.
As optional exercises for enrichment, complete an implementation of
PredicateFilter
that passes the TestFilter
test, and attempt the
challenges in FilterClient.java
.
If you have extra time, start working through problems from the <a old exams to begin preparation for the midterm.