This chapter addresses the following question: suppose that a variable holds a collection of objects; what code should you write to examine its elements? Technically speaking, this question is asking about iterables and iteration. A collection is an iterable, and the mechanism for examining its elements is iteration. The question can be rephrased as “How should I iterate through an iterable?”
Java supports multiple ways to iterate through an iterable, which can be divided into two categories: external iteration, in which you write a loop that examines each element of the iterable; and internal iteration, in which you call a method to perform the loop for you. This chapter covers the programming issues related to both uses of iteration, as well as the design issues of how to write classes that support iteration.
Iterators
Suppose that you have a variable L that holds a collection of objects. What code should you write to print its elements? One possibility is to write the following loop:
for (int i=0; i<L.size(); i++)
System.out.println(L.get(i));
There are two reasons why this code is not very good. First, it violates the rule of Abstraction because it uses the method get, which is only supported by collections that implement List. Second, it will execute much less efficiently in some List implementations than in others. In particular, the get method for ArrayList performs a constant-time array access whereas the get method for LinkedList searches the chain of nodes. Consequently, the loop will execute in linear time if L implements ArrayList but in quadratic time if L implements LinkedList.
The way to address both issues is to provide each collection class with methods that are specifically dedicated to iteration. In Java these methods are called hasNext and next. The method hasNext returns a boolean indicating whether an unexamined element remains. The method next returns one of the unexamined elements. These methods solve the first issue because they can be implemented for any kind of collection, not just lists; they solve the second issue because each class can have its own implementation of these methods, tuned to be as efficient as possible.
Where should these methods live? Recall from Figure 2-3 that the root of the collection hierarchy is the interface Iterable. All collections are iterables. These methods should be associated with Iterable, but how? The obvious design is to add the methods to the Iterable interface, meaning that each collection object would have its own hasNext and next methods. Under this design, the code to print the contents of a list L would look like this:
// Warning: This code is not legal Java.
while (L.hasNext())
System.out.println(L.next());
This design is unsatisfactory because it can allow incorrect behavior to occur. Listing 6-1 provides an example. The noDuplicates method is intended to return true if its argument list has no duplicates. The code calls the helper method isUnique, which should return true if a specified string appears exactly once in the list. The idea is noDuplicates iterates through each string in L, calling isUnique for each one and returning false if isUnique ever returns false. The method isUnique also iterates through L, returning true if it finds exactly one occurrence of string s.
Incorrect behavior occurs because both methods iterate through L concurrently. The first time through the noDuplicates loop, the code examines the first element of L and calls isUnique. That method will iterate through L (starting with the second element) and return back to noDuplicates after having read all of L. Therefore, the second time through the noDuplicates loop the call to L.hasNext will immediately return false, and noDuplicates will exit prematurely.
The only way for this algorithm to work correctly is if both methods can iterate through L independently. That is, the functionality to iterate though a list must be separate from the list itself. Java takes this approach, moving the methods hasNext and next to a separate interface called Iterator.
The Iterable interface (and thus every collection) has a method iterator; each call to iterator returns a new Iterator object. For example, the following code prints the elements of L:
Iterator<String> iter = L.iterator();
while (iter.hasNext())
System.out.println(iter.next());
It may seem awkward to create an Iterator object each time you need to iterate through a collection, but that is how Java separates the iteration from the collection. When a method creates an Iterator object for a collection, the method is guaranteed that its iteration will be independent of any other iteration of the collection. (And if some other method happens to modify the iterable while your iteration is still in progress, Java will throw a ConcurrentModificationException to inform you that your iteration has become invalid.)
Listing 6-2 gives the correct code for NoDuplicates. Note that each method has its own iterator. In fact, isUnique creates a new iterator for L each time it is called.
This section explores some classes that implement Iterator. An iterator class needs to implement the hasNext and next methods. It need not be associated with an iterable. Listing 6-3 gives a very simple example of a “stand alone” iterator class named RandomIterator. The intent of this class is to generate arbitrarily many random numbers. Its next method returns another random integer and its hasNext method always returns true.
public class RandomIterator implements Iterator<Integer> {
private Random rand = new Random();
public boolean hasNext() {
return true;
}
public Integer next() {
return rand.nextInt();
}
}
Listing 6-3
The RandomIterator Class
The code in Listing 6-4 tests RandomIterator. It generates random integers, savings them in a hash set and stopping when a duplicate occurs. It then prints the number of nonduplicate integers that were generated.
Iterator<Integer> iter = new RandomIterator();
Set<Integer> nums = new HashSet<>();
boolean dupNotFound = true;
while (dupNotFound)
dupNotFound = nums.add(iter.next());
System.out.println(nums.size());
Listing 6-4
Using the RandomIterator Class
Listing 6-5 gives another example of an iterator class, named PrimeIterator. This class generates the first N prime numbers, where N is specified in the constructor. The code for next calculates the value of the next prime and keeps track of how many primes have been generated. The code for hasNext returns false as soon as the indicated number of primes has been generated. The code of Listing 6-6 tests this class by printing the first 20 primes.
public class PrimeIterator implements Iterator<Integer> {
private int current = 1;
private int howmany;
private int count = 0;
public PrimeIterator(int howmany) {
this.howmany = howmany;
}
public boolean hasNext() {
return count < howmany;
}
public Integer next() {
current++;
while (!isPrime(current)) // Loop until
current++; // you find a prime.
count++;
return current;
}
private boolean isPrime(int n) {
for (int i=2; i*i<=n; i++)
if (n%i == 0)
return false;
return true;
}
}
Listing 6-5
The PrimeIterator Class
Iterator<Integer> iter = new PrimeIterator(20);
while (iter.hasNext()) {
int p = iter.next();
System.out.println(p);
}
Listing 6-6
Printing the First 20 Primes
Now suppose that you want to create a class PrimeCollection whose objects denote a collection of the first N primes for some N. The easiest way to create a class that implements Collection is to extend the abstract class AbstractCollection. To do so you need to implement its abstract methods size and iterator. The code for PrimeCollection appears in Listing 6-7. It uses the PrimeIterator class to implement the iterator method.
public class PrimeCollection
extends AbstractCollection<Integer> {
private int size;
public PrimeCollection(int size) {
this.size = size;
}
public int size() {
return size;
}
public Iterator<Integer> iterator() {
return new PrimeIterator(size);
}
}
Listing 6-7
The PrimeCollection Class
A PrimeCollection object has a very interesting feature—its collection of primes is not stored within the object, nor are they stored within its iterator. Instead, the primes are generated by the iterator, on demand. Some people find it difficult to grasp the idea that a Collection object doesn’t need to actually hold a collection. Instead, it only needs to act as if it does, by implementing the methods of the interface. This is the beauty of encapsulation.
The easy way to create a class that implements List is to extend AbstractList and implement its two abstract methods size and get. The code for AbstractList implements the remaining methods of the List interface. The class RangeList from Listing 3-11 was such an example.
The iterator method is one of the methods implemented by AbstractList. Listing 6-8 gives a simplified implementation of the method. Its code creates and returns a new AbstractListIterator object. The object holds a reference to the list and its current position in the list. Its next method calls the list’s get method to retrieve the element from the list at the current position, and increments the current position. Its hasNext method calls the list’s size method to determine when there are no more elements.
public abstract class AbstractList<T> {
public abstract T get(int n);
public abstract int size();
public Iterator<T> iterator() {
return new AbstractListIterator<T>(this);
}
... // code for the other List methods
}
class AbstractListIterator<T> implements Iterator<T> {
private int current = 0;
private AbstractList<T> list;
public AbstractListIterator(AbstractList<T> list) {
this.list = list;
}
public boolean hasNext() {
return current < list.size();
}
public T next() {
T val = list.get(current);
current++;
return val;
}
}
Listing 6-8
Simplified Code for the AbstractList and AbstractListIterator Classes
Note that this implementation of iterator uses the get method, and therefore will exhibit the same inefficient behavior as the code at the very beginning of this chapter. As a result, whenever you create a class by extending AbstractList, you must decide if it makes sense to overwrite the default implementation of iterator with a more efficient one.
The Iterator Pattern
Figure 6-1 depicts the relationship between the classes and interfaces mentioned in the previous section. The interface Iterable, its two sub-interfaces, and three implementing classes constitute the shaded hierarchy on the left side of the diagram; Iterator and its three implementing classes form the hierarchy on the right side.
Figure 6-1
Examples of the iterator pattern
This separation between the Iterable and Iterator hierarchies is known as the iterator pattern. The iterator pattern asserts that every class that implements Iterable should be coupled to a corresponding class that implements Iterator. The Java collection class library was specifically designed to satisfy the iterator pattern.
The parallel hierarchies of the iterator pattern bear a strong resemblance to the parallel hierarchies of the factory pattern, as shown in Figure 5-2. This resemblance is not coincidental. An iterable can be thought of as an “iterator factory.” Given an Iterable object L, each call to L.iterator() creates a new Iterator object customized with the elements of L.
Designing Iterable Classes
An iterable class need not be a collection; it just needs to be a class for which the iterator method is meaningful. For an example, consider the banking demo. Suppose that you want to write programs to analyze the accounts held by the Bank class. These programs may involve tasks such as finding the distribution of account balances, the number of accounts of a given type, and so on. Here are three design options you could choose from.
Your first option is to modify Bank so that it has a new method for each analytical task. This option makes it easy to write the analysis programs, since the Bank class will be doing all the work. The problem is that you will have to modify the Bank class to handle each new requirement, violating the Open/Closed rule. The modifications would also cause Bank to be bloated with specialized methods, violating the Single Responsibility rule.
Your second design option is to realize that Bank already has a method that returns the information about its accounts, namely toString. Each of your analysis programs can call toString, extract the desired information from the returned string, and process it as needed. For example, suppose that the bank’s toString method returns the string shown in Listing 6-9. Each line except the first describes an account. To find the balance of each account, the analysis program can look for the number following “balance=” on each line. To find the foreign accounts, it can look for the string “is foreign”. And so on.
The bank has 3 accounts.
Savings account 0: balance=3333, is foreign, fee=500
Regular checking account 1: balance=6666, is domestic, fee=0
Interest checking account 2: balance=9999, is domestic, fee=0
Listing 6-9
Output of the Bank’s toString Method
This technique is known as screen scraping. The term refers to the case when a program extracts information from the HTML contents of a web page. Screen scraping is an option of last resort. It is difficult to perform and will break when the format of the toString output changes.
The third and only good option is to modify the Bank class to have one (or more) general-purpose methods that clients can use to extract information. The iterator method is a good choice here. It allows clients to iterate through the desired accounts without breaking the encapsulated implementation of the account information. (For example, the clients won’t be able to discover that the accounts are stored in a map.)
Version 15 of the banking demo makes this modification. The Bank class now implements Iterable<BankAccount>, which means that it must supply an iterator method that returns BankAccount objects. Listing 6-10 gives the relevant changes to Bank.
public class Bank implements Iterable<BankAccount> {
...
public Iterator<BankAccount> iterator() {
return accounts.values().iterator();
}
}
Listing 6-10
The Version 15 Bank Class
Version 15 of the banking demo also has two new classes, IteratorAccountStats and StreamAccountStats, which are clients of Bank. The methods in these classes support two prototypical tasks: printing and finding the maximum balance of some selected accounts. These classes contain multiple methods for the two tasks, in order to illustrate different programming techniques. The remainder of this chapter examines the methods in these classes and the techniques behind them.
External Iteration
Iterators are the fundamental way to examine the elements of an iterable. Listing 6-11 shows the basic idiom for traversing an iterable. The examples in the previous sections of this chapter all used this idiom.
Iterable<E> c = ...
Iterator<E> iter = c.iterator();
while (iter.hasNext()) {
E e = iter.next();
... // process e
}
Listing 6-11
The Basic Idiom for Using Iterators
Listing 6-12 gives the code for the methods printAccounts1 and maxBalance1 from the IteratorAccountStats class. Both methods use the basic idiom to iterate through the iterable class Bank. The method printAccounts1 prints all bank accounts and maxBalance1 returns the maximum balance of the accounts.
public void printAccounts1() {
Iterator<BankAccount> iter = bank.iterator();
while (iter.hasNext()) {
BankAccount ba = iter.next();
System.out.println(ba);
}
}
public int maxBalance1() {
Iterator<BankAccount> iter = bank.iterator();
int max = 0;
while (iter.hasNext()) {
BankAccount ba = iter.next();
int balance = ba.getBalance();
if (balance > max)
max = balance;
}
return max;
}
Listing 6-12
The printAccounts1 and maxBalance1 Methods
This idiom is so common that Java has a syntax specifically designed to simplify it. This syntax is the for-each loop. For example, the following loop is equivalent to the code of Listing 6-11.
for (E e : c) {
... // process e
}
The variable c in the above for-each loop can be any Iterable; it need not be a collection. Listing 6-13 gives the code for methods printAccounts2 and maxBalance2 of IteratorAccountStats. These methods revise their earlier versions, replacing the explicit iterator methods with a for-each loop. Note that the code is significantly easier to read and understand, primarily because it no longer mentions iterators explicitly.
public void printAccounts2() {
for (BankAccount ba : bank)
System.out.println(ba);
}
public int maxBalance2() {
int max = 0;
for (BankAccount ba : bank) {
int balance = ba.getBalance();
if (balance > max)
max = balance;
}
return max;
}
Listing 6-13
The Methods printAccounts2 and maxBalance2
Although the for-each loop simplifies the use of iterators, it is not always applicable. The issue is that a for-each loop hides its calls to the iterator’s next method, so there is no way to control when that method will be called. Here are two situations where such control is needed.
The first situation is finding the maximum element in an iterable. Listing 6-14 gives code for the method findMax, which rewrites the method from Listing 2-9 to use iterators.
public BankAccount findMax(Iterable<BankAccount> bank) {
Iterator<BankAccount> iter = bank.iterator();
BankAccount max = iter.next();
while (iter.hasNext()) {
BankAccount ba = iter.next();
if (ba.compareTo(max) > 0)
max = ba;
}
return max;
}
Listing 6-14
Using an Iterator to Find the Maximum Element
This code uses the first element of the iterator to initialize the variable max, and then loops through the remaining elements. Such a strategy is not possible with a for-each loop. The solution shown in Listing 6-15 initializes max to null. Unfortunately, it must check max for null each time through the loop, which is unsatisfactory.
public BankAccount findMax(Iterable<BankAccount> bank) {
BankAccount max = null;
for (BankAccount ba : bank)
if (max == null || ba.compareTo(max) > 0)
max = ba;
return max;
}
Listing 6-15
Using a for-each Loop to Find the Maximum Element
The second situation is when you want to interleave the elements of two collections. Listing 6-16 shows how to perform this task using explicit iterators. I know of no good way to rewrite this code using for-each loops.
Iterator<String> iter1 = c1.iterator();
Iterator<String> iter2 = c2.iterator();
Iterator<String> current = iter1;
while (current.hasNext()) {
String s = current.next();
// process s
current = (current == iter1) ? iter2 : iter1;
}
Listing 6-16
Interleaving Access to Two Collections
Internal Iteration
Each of the examples in the previous section used a loop to traverse its iterator. This looping was performed in two different ways: by calling the iterator methods explicitly, or by using a for-each loop. Both ways are examples of external iteration, because in each case the client writes the loop.
It is also possible to traverse the elements of an iterable object without writing a loop. This technique is called internal iteration. For example, the method addInterest in Bank performs internal iteration for the client, invisibly looping through the bank’s accounts.
The addInterest method is an internal iterator that is specialized to perform a single task. The Java Iterable interface has the default method forEach, which can be used for general-purpose internal iteration. The argument to forEach is an object that implements the Consumer interface. This interface, which also is part of the Java library, has a single void method accept and is defined as follows:
interface Consumer<T> {
void accept(T t);
}
The purpose of the accept method is to perform an action to its argument object. Listing 6-17 gives an example of the creation and use of a Consumer object. Its first statement creates the Consumer object and saves a reference to it in the variable action. The Consumer object’s accept method prints its BankAccount argument. The second statement obtains a reference to bank account 123, and saves in the variable x. The third statement performs the action on the specified account. In other words, the statement prints account 123.
Consumer<BankAccount> action = ba -> System.out.println(ba);
BankAccount x = bank.getAccount(123);
action.accept(x);
Listing 6-17
Creating and Using a Consumer Object
An iterable’s forEach method performs an action on every object of the iterable’s iterator; this action is defined by the Consumer object that is the argument to forEach. Listing 6-18 gives the code for the method printAccounts3, which uses forEach to print every element generated by the bank’s iterator.
The interesting feature of listing 6-18 is that there is no explicit loop. Instead, the looping is performed internally within the forEach method. Listing 6-19 gives a simplified version of the Iterable interface, showing how the forEach method might perform its loop.
public interface Iterable<T> {
Iterator<T> iterator();
default void forEach(Consumer<T> action) {
Iterator<T> iter = iterator();
while (iter.hasNext())
action.apply(iter.next());
}
}
Listing 6-19
A Simplified Iterable Interface
The Visitor Pattern
The Consumer object that is passed to the forEach method is called a visitor. As the forEach method encounters each element of the iterable, the Consumer object “visits” that element. This visitation could involve printing the element (as in printAccounts3), modifying it, or any other action that can be expressed as a Consumer.
The beauty of the forEach method is that it separates the code for visiting an element (the Consumer object) from the code to iterate through the elements. This separation is called the visitor pattern.
The demo class IteratorAccountStats has a method visit1 that generalizes printAccounts3 so that its argument can be any visitor. Its code appears in Listing 6-20. The statements in Listing 6-21 illustrate its use.
public void visit1(Consumer<BankAccount> action) {
bank.forEach(action);
}
Listing 6-20
The Method visit1
// Print all accounts
visit1(ba -> System.out.println(ba));
// Add interest to all accounts
visit1(ba -> ba.addInterest());
// Print the balance of all domestic accounts
visit1(ba -> { if (!ba.isForeign())
System.out.println(ba.getBalance()); });
Listing 6-21
Uses of the visit1 Method
The problem with the visit1 method is that it only applies to void actions—that is, actions that do not return a value. For example, it is not possible to use visit1 to calculate the maximum account balance. To achieve this functionality, the definition of a visitor must also have a method that calculates a return value. Java does not have such a visitor interface in its library, but it is easy enough to create one. See Listing 6-22.
public interface Visitor<T,R> extends Consumer<T> {
R result();
}
Listing 6-22
The Visitor Interface
This interface defines a visitor to be a consumer with the additional method result. A visitor has two generic types: Type T is the type of the elements it visits, and type R is the type of the result value.
Listing 6-23 gives code for the visitor class MaxBalanceVisitor, whose objects calculate the maximum balance of the accounts they visit. The variable max holds the maximum balance encountered so far. The accept method examines the balance of the currently-visited account and updates max if appropriate. The result method returns the final value of max.
public class MaxBalanceVisitor
implements Visitor<BankAccount,Integer> {
private int max = 0;
public void accept(BankAccount ba) {
int bal = ba.getBalance();
if (bal > max)
max = bal;
}
public Integer result() {
return max;
}
}
Listing 6-23
The Class MaxBalanceVisitor
IteratorAccountStats contains two methods that use a visitor to find the maximum bank account balance. Their code appears in Listing 6-24. The method maxBalance3a creates a MaxBalanceVisitor object. The method maxBalance3b defines the equivalent visitor object inline. Since the Visitor interface has two nondefault methods, maxBalance3b cannot define its visitor using a lambda expression; instead, it must use an anonymous inner class. Note that a Visitor object can be legitimately passed to the forEach method because Visitor is a subtype of Consumer.
public int maxBalance3a() {
Visitor<BankAccount,Integer> v = new MaxBalanceVisitor();
bank.forEach(v);
return v.result();
}
public int maxBalance3b() {
Visitor<BankAccount,Integer> v =
new Visitor<BankAccount,Integer>() {
private int max = 0;
public void accept(BankAccount ba) {
int bal = ba.getBalance();
if (bal > max)
max = bal;
}
public Integer result() {
return max;
}
};
bank.forEach(v);
return v.result();
}
Listing 6-24
The maxBalance3a and maxBalance3b Methods
Listing 6-25 gives the code for the method visit2, which generalizes visit1 so that its argument is a Visitor object instead of a Consumer object. Listing 6-26 gives the code for the method maxBalance3c, which uses visit2 to find the maximum account balance.
public <R> R visit2(Visitor<BankAccount, R> action) {
bank.forEach(action);
return action.result();
}
Listing 6-25
The visit2 Method
public int maxBalance3c() {
return visit2(new MaxBalanceVisitor());
}
Listing 6-26
The maxBalance3c Method
Predicates
The previous section presented several methods that traversed the bank’s iterator. Each method visited all the accounts, printing them or finding their maximum balance.
Suppose now that you want to write code to visit only some of the accounts; for example, suppose you want to print the domestic accounts. It might be an unwelcome surprise to discover that none of these methods will be of any use. Instead, you will need to write a new method, such as the method shown in Listing 6-27.
public void printDomesticAccounts() {
for (BankAccount ba : bank)
if (!ba.isForeign())
System.out.println(ba);
}
Listing 6-27
Printing the Domestic Accounts
Note that this method contains most of the same code as printAccounts2, in violation of the Don’t Repeat Yourself rule. Moreover, you will need to write a new method whenever you are interested in another subset of the accounts. This situation is unacceptable.
The solution is to rewrite the printAccounts and maxBalance methods to have an argument that specifies the desired subset of accounts. The Java library has the interface Predicate for this purpose. It has a method test, whose return value indicates whether the specified object satisfies the predicate. The Predicate interface is defined as follows:
interface Predicate<T> {
boolean test(T t);
}
Since the interface is functional (that is, it has a single method), classes that implement Predicate can be defined by lambda expressions. For example, consider Listing 6-28. Its first statement creates a predicate that specifies accounts having a balance greater than $100. Its second statement obtains a reference to account 123. Its third statement uses the predicate to determine if the balance of that account is greater than $100, and prints it if it does.
Predicate<BankAccount> pred = ba -> ba.getBalance() > 10000;
BankAccount x = bank.getAccount(123);
if (pred.test(x))
System.out.println(x);
Listing 6-28
Creating and Using a Predicate
Listing 6-29 gives code for the methods printAccounts4 and maxBalance4 of InteratorAccountStats. These methods take an arbitrary predicate as their argument and use that predicate to restrict the bank accounts they visit.
public void printAccounts4(Predicate<BankAccount> pred) {
for (BankAccount ba : bank)
if (pred.test(ba))
System.out.println(ba);
}
public int maxBalance4(Predicate<BankAccount> pred) {
int max = 0;
for (BankAccount ba : bank) {
if (pred.test(ba)) {
int balance = ba.getBalance();
if (balance > max)
max = balance;
}
}
return max;
}
Listing 6-29
The printAccounts4 and maxBalance4 Methods
Predicates can also be embedded into the visitor pattern. Method printAccounts5 creates a Consumer object that visits each account. If the account satisfies the predicate then it prints the account. See Listing 6-30.
public void printAccounts5(Predicate<BankAccount> pred) {
Consumer<BankAccount> action =
ba -> { if (pred.test(ba))
System.out.println(ba);
};
bank.forEach(action);
}
Listing 6-30
The printAccounts5 Method
The statements in Listing 6-31 illustrate three uses of printAccounts5. They print the accounts having a balance greater than $100, the domestic accounts, and all accounts.
Predicate<BankAccount> p = ba -> ba.getBalance() > 10000;
printAccounts5(p);
printAccounts5(ba->!ba.isForeign());
printAccounts5(ba->true);
Listing 6-31
Using the printAccounts5 Method
Listing 6-32 gives code for the method maxBalance5, which creates a Consumer object that incorporates both its argument predicate and its visitor.
public int maxBalance5(Predicate<BankAccount> pred) {
Visitor<BankAccount,Integer> r = new MaxBalanceVisitor();
Consumer<BankAccount> action =
ba -> {if (pred.test(ba))
r.accept(ba);};
bank.forEach(action);
return r.result();
}
Listing 6-32
The maxBalance5 Method
The following statement shows how to use maxBalance5 to return the maximum balance of the domestic accounts.
int max = maxBalance5(ba->!ba.isForeign());
This ability to combine a predicate with a consumer can be generalized. The method visit3 takes two arguments: a predicate and a consumer. The arguments to method visit4 are a predicate and a visitor. Each method visits those elements that satisfy the predicate. The code for both methods appears in Listing 6-33.
public void visit3(Predicate<BankAccount> pred,
Consumer<BankAccount> action) {
bank.forEach(ba -> {if (pred.test(ba))
action.accept(ba);});
}
public <R> R visit4(Predicate<BankAccount> pred,
Visitor<BankAccount, R> action) {
bank.forEach(ba -> {if (pred.test(ba))
action.accept(ba);});
return action.result();
}
Listing 6-33
The visit3 and visit4 Methods
The code in Listing 6-34 illustrates the use of visit3 and visit4. The first statement prints the balance of all domestic accounts whose balance is over $50. The second statement assigns the maximum balance of the domestic accounts to variable max.
This section examines the Stream interface from the Java library. A Stream object is similar to an iterator, in that its methods allow you to iterate through a group of elements. The difference is that the Stream provides additional methods that simplify the use of internal iteration.
The code for Stream and six of its methods appears in Listing 6-35. The iterator method converts the stream into an iterator, so that clients can use the hasNext and next methods for external iteration. This method is not commonly used and exists only for the rare cases where internal iteration is not possible.
interface Stream<T> {
Iterator<T> iterator();
void forEach(Consumer<T> cons);
Stream<T> filter(Predicate<T> p);
<R> Stream<R> map(Function<T,R> f);
T reduce(T id, BinaryOperator<T> op);
boolean anyMatch(Predicate<T> p);
...
}
Listing 6-35
The Stream Interface
The other stream methods support internal iteration. The forEach method is the same as the forEach method of Iterator. The methods filter, map, reduce, and anyMatch will be discussed soon.
Objects that implement Stream are called collection streams. The elements of a collection stream come from a collection or something that can be viewed as a collection (such as an array). A collection stream has no relationship whatsoever to the byte streams discussed in Chapter 3.
The Collection interface contains the method stream, which creates a Stream object whose elements are the elements of the collection. This is the most common way to get a collection stream. A noncollection class (such as Bank) can also implement the stream method. Typically, the stream method for such a class calls the stream method of one of its collections. For example, the Bank class in the version 15 banking demo implements the method stream. Listing 6-36 gives the relevant code.
public class Bank implements Iterable<BankAccount> {
private Map<Integer,BankAccount> accounts;
...
public Stream<BankAccount> stream() {
return accounts.values().stream();
}
}
Listing 6-36
The version 15 Bank Class
The class StreamAcctStats in the version 15 banking demo illustrates the use of several Stream methods. The code for printAccounts6 appears in Listing 6-37. It uses the Stream methods filter and forEach to print the bank accounts satisfying the given predicate.
public void printAccounts6(Predicate<BankAccount> pred) {
Stream<BankAccount> s1 = bank.stream();
Stream<BankAccount> s2 = s1.filter(pred);
s2.forEach(ba->System.out.println(ba));
}
Listing 6-37
The printAccounts6 Method
The forEach method behaves the same as the corresponding method in Iterable. The filter method transforms one stream to another. It takes a predicate as an argument and returns a new stream containing the elements that satisfy the predicate. In Listing 6-37, stream s2 contains those accounts from s1 that satisfy the predicate. Note how the filter method uses internal iteration to do what you otherwise would need a loop and an if-statement to do.
Because Java syntax allows method calls to be composed, it is possible to rewrite printAccounts6 so that the filter method is called by the output of the stream method. See Listing 6-38.
public void printAccounts6(Predicate<BankAccount> pred) {
Stream<BankAccount> s = bank.stream().filter(pred);
s.forEach(ba->System.out.println(ba));
}
Listing 6-38
A Revised Version of the Method printAccounts6
In fact, you could even rewrite printAccounts6 so that all method calls occur in a single statement. In this case you don’t need the Stream variable s. See Listing 6-39.
public void printAccounts6(Predicate<BankAccount> pred) {
bank.stream().filter(pred).forEach(
ba->System.out.println(ba));
}
Listing 6-39
Another Revsion of printAccounts6
This code is not particularly readable. However, it becomes nicely readable if it is rewritten so that each method call is on a different line. This is what the method printAccounts7 does. Its code appears in Listing 6-40.
public void printAccounts7(Predicate<BankAccount> pred) {
bank.stream()
.filter(pred)
.forEach(ba->System.out.println(ba));
}
Listing 6-40
The Method printAccounts7
This programming style is called fluent. A fluent expression consists of several composed method calls. You can think of each method call as a transformation of one object to another. For example, Listing 6-41 gives a fluent statement that prints the bank accounts having a balance between $10 and $20.
bank.stream()
.filter(ba -> ba.getBalance() >= 1000)
.filter(ba -> ba.getBalance() <= 2000)
.forEach(ba->System.out.println(ba));
Listing 6-41
A Fluent Statement
The filter method transforms a stream into another stream that contains a subset of the original elements. Another form of transformation is produced by the method map. The argument to map is an object that implements the Function interface. This interface, which is part of the Java library, has a single method apply and is defined as follows:
interface Function<T,R> {
R apply(T t);
...
}
The apply method transforms an object of type T to an object of type R. The map method calls apply for each element in the input stream and returns the stream consisting of the transformed elements. You can use lambda expressions to create Function objects. For example, consider the following statement. The lambda expression transforms a BankAccount object to an integer that denotes its balance. The map method therefore returns a stream containing the balances of each account.
Stream<Integer> balances = bank.stream()
.map(ba -> ba.getBalance());
It is also useful to be able to construct a “return value” from a stream. This operation is called reducing the stream. The Stream interface has the method reduce for this purpose. For example, Listing 6-42 gives the code for the maxBalance4 method of StreamAcctStats.
public int maxBalance4(Predicate<BankAccount> pred) {
return bank.stream()
.filter(pred)
.map(ba->ba.getBalance())
.reduce(0, (x,y)->Math.max(x,y));
}
Listing 6-42
The Method maxBalance4
The reduce method has two arguments. The first argument is the initial value of the reduction. The second argument is the reduction method, which reduces two values into a single value. The reduce method repeatedly calls its reduction method for each element of the stream. Its algorithm is given in Listing 6-43, where x is the initial value of the reduction and r is the reduction method.
1. Set currentval = x.
2. For each element e in the stream:
currentval = r(currentval, e).
3. Return currentval.
Listing 6-43
The Reduction Algorithm
The Stream interface also has reduction methods that search for elements that match a given predicate. Three of these methods are allMatch, anyMatch, and findFirst. The code of Listing 6-44 uses anyMatch to determine if there is an account having a balance greater than $1,000.
boolean result =
bank.stream()
.anyMatch(ba->ba.getBalance() > 100000);
Listing 6-44
Using the anyMatch Method
Collection streams are the building blocks of map-reduce programs. Map-reduce programming is an effective, commonly used way to process Big data applications. Map-reduce programs have the structure given in Listing 6-45.
1. Obtain an initial collection stream.
2. Transform the stream, filtering and mapping its contents until you get a stream containing the values you care about.
3. Reduce that stream to get the answer you want.
Listing 6-45
The Structure of a Map-Reduce Program
Map-reduce programming has two advantages. First, it allows you to divide your problem into a sequence of small transformations. People find this coding style easy to write, and easy to debug. Note that map-reduce code has no assignment statements and no control structures.
The second advantage is that you can easily change the code to run in parallel. Each collection has a method parallelStream as well as stream. Given a collection, if you use the parallelStream method to create the stream then the resulting stream will execute in parallel. That’s it! The Java parallelSteam method does all the hard work behind the scenes.
Summary
An iterator generates a sequence of elements. It has the two methods next and hasNext. The method next returns the next element in the iterator and hasNext indicates whether the iterator has more elements left. An iterable is an object that has an associated iterator. Collections are the most common examples of iterables.
The iterator pattern organizes the iterable and iterator classes into separate, parallel hierarchies, with each iterable class having a corresponding iterator class. The Java library contains the interfaces Iterable and Iterator for exactly this purpose. Iterable declares the method iterator, which returns the Iterator object associated with that iterable.
The most fundamental way to iterate through an iterable L is to use the following basic idiom:
Iterator<T> iter = L.iterator();
while (iter.hasNext()) {
T t = iter.next();
process(t); // some code that uses t
}
Java has a special syntax for this idiom, called the for-each loop.The above code can be written more succinctly using the following for-each loop:
for (T t : L) {
process(t);
}
Explicitly looping through the elements of an iterator is called external iteration. A method that encapsulates the looping (such as the bank’s addInterest method) is said to perform internal iteration. The Java Iterable interface has a general-purpose internal iteration method called forEach. The argument to forEach is a Consumer object that specifies the body of the iteration loop. Using forEach, the preceding code can be written as follows:
L.forEach(t->process(t));
The Consumer object is said to visit each element of the iterable. The forEach method separates the specification of the visitor from the specification of the looping. This separation is called the visitor pattern.
Collection streams are a way to simplify the use of the visitor pattern. Instead of expressing iteration via a single visitor having a complex body, you can use the collection stream methods to express the iteration as a sequence of small transformations. Each transformation is itself a visitor that performs a limited action, such as a filter or a map. This technique is the foundation of map-reduce programming. The idea is that writing several small transformations is much simpler, more compact, and less error-prone than writing a single large one.
The use of collection streams, however, raises the question of efficiency. If the stream transformations were to execute sequentially, each via its own iteration loop, then a map-reduce program would take far more time than a traditional program that made a single iteration through the elements. Collection streams will be useful only if their transformations can be coalesced somehow. The technique for doing so is interesting, and will be discussed in Chapter 8.
