Beginning Algorithms (2006)

Chapter 2

Try It Out

Implementing the Array Iterator

With the tests in place, you can now move on to implementing the array iterator itself. The iterator will need to implement the Iterator interface in addition to holding a reference to the underlying array.

If you assume that the iterator always operates over the entire length of an array, from start to finish, then the only other information you need to store is the current position. However, you may often wish to only provide access to a portion of the array. For this, the iterator will need to hold the bounds — the upper and lower positions — of the array that are relevant to the client of the iterator:

package com.wrox.algorithms.iteration;

public class ArrayIterator implements Iterator { private final Object[] _array;

private final int _start; private final int _end; private int _current = -1;

public ArrayIterator(Object[] array, int start, int length) { assert array != null : “array can’t be null”;

assert start >= 0 : “start can’t be < 0”;

assert start < array.length : “start can’t be > array.length”; assert length >= 0 : “length can’t be < 0”;

_array = array; _first = start;

_last = start + length - 1;

assert _last < array.length : “start + length can’t be > array.length”;

}

...

}

Besides iterating over portions of an array, there will of course be times when you want to iterate over the entire array. As a convenience, it’s a good idea to also provide a constructor that takes an array as its only argument and calculates the starting and ending positions for you:

public ArrayIterator(Object[] array) {

assert array != null : “array can’t be null”; _array = array;

_first = 0;

_last = array.length - 1;

}

Now that you have the array and have calculated the upper and lower bounds, implementing first() and last() couldn’t be easier:

public void first() {

_current = _first;

24

Iteration and Recursion

}

public void last() { _current = _last;

}

Traversing forward and backward is much the same as when directly accessing arrays:

public void next() { ++_current;

}

public void previous() { --_current;

}

Use the method isDone() to determine whether there are more elements to process. In this case, you can work this out by determining whether the current position falls within the bounds calculated in the constructor:

public boolean isDone() {

return _current < _first || _current > _last;

}

If the current position is before the first or after the last, then there are no more elements and the iterator is finished.

Finally, you implement current() to retrieve the value of the current element within the array:

public Object current() throws IteratorOutOfBoundsException { if (isDone()) {

throw new IteratorOutOfBoundsException();

}

return _array[_current];

}

How It Works

As you can see in the first code block of the preceding example, there is a reference to the underlying array as well as variables to hold the current, first, and last element positions (0, 1, 2, . . .). There is also quite a bit of checking to ensure that the values of the arguments make sense. It would be invalid, for example, for the caller to pass an array of length 10 and a starting position of 20.

Moving on, you already know the position of the first and last elements, so it’s simply a matter of setting the current position appropriately. To move forward, you increment the current position; and to move backward, you decrement it.

Notice how you ensure that there is actually a value to return by first calling isDone(). Then, assuming there is a value to return, you use the current position as an index in exactly the same way as when directly accessing the array yourself.

25

Chapter 2

A Reverse Iterator

Sometimes you will want to reverse the iteration order without changing the code that processes the values. Imagine an array of names that is sorted in ascending order, A to Z, and displayed to the user somehow. If the user chose to view the names sorted in descending order, Z to A, you might have to re-sort the array or at the very least implement some code that traversed the array backward from the end. With a reverse iterator, however, the same behavior can be achieved without re-sorting and without duplicated code. When the application calls first(), the reverse iterator actually calls last() on the underlying iterator. When the application calls next(), the underlying iterator’s previous() method is invoked, and so on. In this way, the behavior of the iterator can be reversed without changing the client code that displays the results, and without re-sorting the array, which could be quite processing intensive, as you will see later in this book when you write some sorting algorithms.

Try It Out

Testing the Reverse Iterator

The tests for the reverse iterator are straightforward. There are two main scenarios to test: forward iteration becomes backward, and vice-versa. In both cases, you can use the same test data and just iterate in the appropriate direction. Because you’ve just tested and implemented an array iterator, use it to test the reverse iterator:

package com.wrox.algorithms.iteration;

import junit.framework.TestCase;

public class ReverseIteratorTest extends TestCase {

private static final Object[] ARRAY = new Object[] {“A”, “B”, “C”};

...

}

The test class itself defines an array that can be used by each of the test cases. Now, test that the reverse iterator returns the elements of this array in the appropriate order:

public void testForwardsIterationBecomesBackwards() {

ReverseIterator iterator = new ReverseIterator(new ArrayIterator(ARRAY));

iterator.first();

assertFalse(iterator.isDone()); assertSame(ARRAY[2], iterator.current());

iterator.next();

assertFalse(iterator.isDone()); assertSame(ARRAY[1], iterator.current());

iterator.next();

assertFalse(iterator.isDone()); assertSame(ARRAY[0], iterator.current());

iterator.next();

assertTrue(iterator.isDone());

26

Iteration and Recursion

try { iterator.current(); fail();

} catch (IteratorOutOfBoundsException e) { // expected

}

}

Notice that although you are iterating forward through the array from start to finish, the values returned are in reverse order. If it wasn’t apparent before, it is hoped that you can now see what a powerful construct this is. Imagine that the array you’re iterating over is a list of data in sorted order. You can now reverse the sort order without actually re-sorting(!):

public void testBackwardsIterationBecomesForwards() {

ReverseIterator iterator = new ReverseIterator(new ArrayIterator(ARRAY));

iterator.last();

assertFalse(iterator.isDone()); assertSame(ARRAY[0], iterator.current());

iterator.previous();

assertFalse(iterator.isDone()); assertSame(ARRAY[1], iterator.current());

iterator.previous();

assertFalse(iterator.isDone()); assertSame(ARRAY[2], iterator.current());

iterator.previous();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

}catch (IteratorOutOfBoundsException e) {

//expected

}

}

How It Works

The first test case ensures that when calling first() and next() on the reverse iterator, you actually get the last and previous elements of the array, respectively.

The second test makes sure that iterating backward over an array actually returns the items from the underlying iterator from start to finish.

The last test is structurally very similar to the previous test, but this time you’re calling last() and previous() instead of first() and next(), and, of course, checking that the values are returned from start to finish.

Now you’re ready to put the reverse iterator into practice, as shown in the next Try It Out.

27

Chapter 2

Try It Out

Implementing the Reverse Iterator

Implementing the reverse iterator is very easy indeed: Just invert the behavior of calls to the traversal methods, first, last, next, and previous:

Because of this simplicity, we’ve chosen to present the entire class in one piece, rather than break it up into individual methods as we usually do.

package com.wrox.algorithms.iteration;

public class ReverseIterator implements Iterator { private final Iterator _iterator;

public ReverseIterator(Iterator iterator) {

assert iterator != null : “iterator can’t be null”; _iterator = iterator;

}

public boolean isDone() { return _iterator.isDone();

}

public Object current() throws IteratorOutOfBoundsException { return _iterator.current();

}

public void first() { _iterator.last();

}

public void last() { _iterator.first();

}

public void next() { _iterator.previous();

}

public void previous() { _iterator.next();

}

}

How It Works

Besides implementing the Iterator interface, the class also holds the iterator to reverse its behavior. As you can see, calls to isDone() and current() are delegated directly. The remaining methods, first(), last(), next(), and previous(), then redirect to their opposite number — last(), first(), next(), and previous(), respectively — thereby reversing the direction of iteration.

A Filtering Iterator

One of the more interesting and useful advantages of using iterators is the capability to wrap or decorate (see the Decorator pattern [Gamma, 1995]) another iterator to filter the return values. This could be as

28

Iteration and Recursion

simple as only returning every second value, or something more sophisticated such as processing the results of a database query to further remove unwanted values. Imagine a scenario whereby in addition to the database query selection criteria, the client was also able to perform some filtering of its own.

The filter iterator works by wrapping another iterator and only returning values that satisfy some condition, known as a predicate. Each time the underlying iterator is called, the returned value is passed to the predicate to determine whether it should be kept or discarded. It is this continuous evaluation of values with the predicate that enables the data to be filtered.

The Predicate Class

You begin by creating an interface that represents a predicate:

package com.wrox.algorithms.iteration;

public interface Predicate {

public boolean evaluate(Object object);

}

The interface is very simple, containing just one method, evaluate(), that is called for each value, and returning a Boolean to indicate whether the value meets the selection criteria or not. If evaluate() returns true, then the value is to be included and thus returned from the filter iterator. Conversely, if the predicate returns false, then the value will be ignored, and treated as if it never existed.

Although simple, the predicate interface enables you to build very sophisticated filters. You can even implement predicates for AND (&&), OR (||), NOT (!), and so on, enabling the construction of any arbitrarily complex predicate you can think of.

Try It Out

Testing the Predicate Class

You will now write a number of tests to ensure that your filter iterator performs correctly. All you really need to do is ensure that the filter returns any value from the underlying iterator the predicate accepts. You will perform four tests: two combinations of forward and backward iteration — one in which the predicate accepts the values, and one in which the predicate rejects the values:

package com.wrox.algorithms.iteration;

import junit.framework.TestCase;

public class FilterIteratorTest extends TestCase { private static final Object[] ARRAY = {“A”, “B”, “C”};

...

}

You want to know that the predicate is called once for each item returned from the underlying iterator. For this, you create a predicate specifically for testing purposes:

private static final class DummyPredicate implements Predicate { private final Iterator _iterator;

private final boolean _result;

public DummyPredicate(boolean result, Iterator iterator) {

29

Chapter 2

_iterator = iterator; _result = result; _iterator.first();

}

public boolean evaluate(Object object) { assertSame(_iterator.current(), object);

_iterator.next(); return _result;

}

}

...

}

The first test is to ensure that the filter returns values the predicate accepts — evaluate() returns true — while iterating forward:

public void testForwardsIterationIncludesItemsWhenPredicateReturnsTrue() { Iterator expectedIterator = new ArrayIterator(ARRAY);

Iterator underlyingIterator = new ArrayIterator(ARRAY);

Iterator iterator = new FilterIterator(underlyingIterator, new DummyPredicate(true, expectedIterator));

iterator.first();

assertFalse(iterator.isDone()); assertSame(ARRAY[0], iterator.current());

iterator.next();

assertFalse(iterator.isDone()); assertSame(ARRAY[1], iterator.current());

iterator.next();

assertFalse(iterator.isDone()); assertSame(ARRAY[2], iterator.current());

iterator.next();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

} catch (IteratorOutOfBoundsException e) { // expected

}

assertTrue(expectedIterator.isDone());

assertTrue(underlyingIterator.isDone());

}

The next test is much simpler than the first. This time, you want to see what happens when the predicate rejects values — that is, evaluate() returns false:

30

Iteration and Recursion

public void testForwardsIterationExcludesItemsWhenPredicateReturnsFalse() { Iterator expectedIterator = new ArrayIterator(ARRAY);

Iterator underlyingIterator = new ArrayIterator(ARRAY);

Iterator iterator = new FilterIterator(underlyingIterator, new DummyPredicate(false, expectedIterator));

iterator.first();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

} catch (IteratorOutOfBoundsException e) { // expected

}

assertTrue(expectedIterator.isDone());

assertTrue(underlyingIterator.isDone());

}

The remaining two tests are almost identical to the first two except that the order of iteration has been reversed:

public void testBackwardssIterationIncludesItemsWhenPredicateReturnsTrue() { Iterator expectedIterator = new ReverseIterator(new ArrayIterator(ARRAY)); Iterator underlyingIterator = new ArrayIterator(ARRAY);

Iterator iterator = new FilterIterator(underlyingIterator, new DummyPredicate(true, expectedIterator));

iterator.last();

assertFalse(iterator.isDone()); assertSame(ARRAY[2], iterator.current());

iterator.previous();

assertFalse(iterator.isDone()); assertSame(ARRAY[1], iterator.current());

iterator.previous();

assertFalse(iterator.isDone()); assertSame(ARRAY[0], iterator.current());

iterator.previous();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

} catch (IteratorOutOfBoundsException e) { // expected

}

assertTrue(expectedIterator.isDone());

assertTrue(underlyingIterator.isDone());

31

Chapter 2

}

public void testBackwardsIterationExcludesItemsWhenPredicateReturnsFalse() { Iterator expectedIterator = new ReverseIterator(new ArrayIterator(ARRAY)); Iterator underlyingIterator = new ArrayIterator(ARRAY);

Iterator iterator = new FilterIterator(underlyingIterator, new DummyPredicate(false, expectedIterator));

iterator.last();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

} catch (IteratorOutOfBoundsException e) { // expected

}

assertTrue(expectedIterator.isDone());

assertTrue(underlyingIterator.isDone());

}

How It Works

Besides the test cases themselves, the test class contains little more than some simple test data. However, in order to test the filter iterator adequately, you need to confirm not only the expected iteration results, but also that the predicate is being called correctly.

The DummyPredicate inner class that you created for testing purposes in the second code block holds an iterator that will return the values in the same order as you expect the predicate to be called with. Each time evaluate() is called, you check to make sure that the correct value is being passed. In addition to checking the values, evaluate() also returns a predetermined result — set by the test cases — so that you can check what happens when the predicate accepts values and when it rejects values.

Next, you create the actual tests. You started by creating two iterators: one for the items you expect the predicate to be called with, and the other to provide the items to the filter in the first place. From these, you construct a filter iterator, passing in the underlying iterator and a dummy predicate configured to always accept the values passed to it for evaluation. Then you position the filter iterator to the first item, check that there is in fact an item to obtain, and that the value is as expected. The remainder of the test simply calls next() repeatedly until the iterator is complete, checking the results as it goes. Notice the last two assertions of the first test (in the third code block from the preceding Try it Out) that ensure that both the underlying iterator and the expected iterator have been exhausted.

The next test begins much the same as the previous test except you construct the predicate with a predetermined return value of false. After positioning the filter iterator to the first item, you expect it to be finished straightaway — the predicate is rejecting all values. Once again, however, you still expect both iterators to have been exhausted; and in particular, you expect the underlying iterator to have had all of its values inspected.

In the last test, notice the use of ReverseIterator; the dummy iterator still thinks that it’s iterating forward, but in reality it’s iterating backward.

32

Iteration and Recursion

Try It Out

Implementing the Predicate Class

With the tests in place, you can move straight into implementation. You’ve already defined the interface for predicates, so all you do now is create the filter iterator class itself:

package com.wrox.algorithms.iteration;

public class FilterIterator implements Iterator { private final Iterator _iterator;

private final Predicate _predicate;

public FilterIterator(Iterator iterator, Predicate predicate) { assert iterator != null : “iterator can’t be null”;

assert predicate != null : “predicate can’t be null”;

_iterator = iterator; _predicate = predicate;

}

public boolean isDone() { return _iterator.isDone();

}

public Object current() throws IteratorOutOfBoundsException { return _iterator.current();

}

...

}

In the case of first() and next(), the call is first delegated to the underlying iterator before searching forward from the current position to find a value that satisfies the filter:

public void first() { _iterator.first(); filterForwards();

}

public void next() { _iterator.next(); filterForwards();

}

private void filterForwards() {

while (!_iterator.isDone() && !_predicate.evaluate(_iterator.current())) { _iterator.next();

}

}

Finally, you add last() and previous(), which, not surprisingly, look very similar to first() and next():

public void last() {

_iterator.last();

33