Beginning Algorithms (2006)

Chapter 2

filterBackwards();

}

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

}

private void filterBackwards() {

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

}

}

The FilterIterator can now be used to traverse any data structure supporting iterators. All you need to do is create an appropriate predicate to do the specific filtering you require.

How It Works

The filter iterator class implements the Iterator interface, of course, and holds the iterator to be wrapped and the predicate to use for filtering. The constructor first checks to make sure that neither argument is null before assigning them to instance variables for later use. The two methods isDone() and current() need do nothing more than delegate to their respective methods on the underlying iterator. This works because the underlying iterator is always kept in a state such that only an object that is allowed by the predicate is the current object.

The real work of the iterator is performed when one of the traversal methods is called. Anytime first(), next(), last(), or previous() is invoked, the predicate must be used to include or exclude values as appropriate while still maintaining the semantics of the iterator:

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

}

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

}

private void filterForwards() {

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

}

}

34

Iteration and Recursion

When filterForwards is called, it is assumed that the underlying iterator will already have been positioned to an element from which to start searching. The method then loops, calling next() until either there are no more elements or a matching element is found. Notice that in all cases, you call methods on the underlying iterator directly. This prevents unnecessary looping, most likely resulting in abnormal program termination in extreme cases.

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

}

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

}

private void filterBackwards() {

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

}

}

As you did for first() and next(), last() and previous() call their respective methods on the wrapped class before invoking filterBackwards to find an element that satisfies the predicate.

Recursion

“To understand recursion, we first need to understand recursion.” — Anonymous

Imagine a file system such as the one on your computer. As you probably know, a file system has a root directory with many subdirectories (and files), which in turn have more subdirectories (and files). This directory structure is often referred to as a directory tree — a tree has a root and branches (directories) and leaves (files). Figure 2-1 shows a file system represented as a tree. Notice how it is like an inverted tree, however, with the root at the top and the leaves at the bottom.

One of the interesting things about “trees” in the computing sense is that each branch looks just like another, smaller tree. Figure 2-2 shows the same tree as before, this time highlighting one of the branches. Notice how the structure is similar to the bigger tree.

35

Chapter 2

/

dev

fd0

tty0

tmp

var

Figure 2-1: A directory structure represented as a tree.

This characteristic, whereby some things look the same at different granularities or magnifications, can be applied to solving problems as well. Anytime a problem can be broken down like this into smaller components that look just like the larger one (divide and conquer) is precisely when recursion comes into its own. In a sense, recursion is the ultimate re-use pattern: a method that calls itself.

36

Iteration and Recursion

/

dev

fd0

tty0

tmp

var

Figure 2-2: Branches of a tree are themselves trees.

Recursive Directory Tree Printer Example

Let’s continue with the file system analogy and write a program to print the contents of an entire directory tree. More often than not, the examples used to demonstrate recursion involve finding prime numbers, fibonacci numbers, and possibly even solving mazes — hardly things you are likely to encounter on a daily basis.

Besides simply printing the names, let’s also format the output so that each file and subdirectory is indented under its parent — like a text version of Windows Explorer or Mac OS X Finder. Given what you know about the structure of file systems, you should be able to construct a recursive algorithm to traverse the directory structure by breaking the problem down in such a way that the solution works at one level and then calls itself for each deeper level in the directory tree.

37

Chapter 2

Naturally, you need to start with a class; and as you probably want to run this program from the command line, you will need a main method:

package com.wrox.algorithms.iteration;

import java.io.File;

public final class RecursiveDirectoryTreePrinter { private static final String SPACES = “ “;

public static void main(String[] args) { assert args != null : “args can’t be null”;

if (args.length != 1) {

System.err.println(“Usage: RecursiveDirectoryTreePrinter <dir>”); System.exit(4);

}

print(new File(args[0]), “”);

}

...

}

Our program requires the name of a single directory (or file) to be passed on the command line. After performing some rudimentary checking, main() then constructs a java.io.File from the first argument and passes it to a print() method.

Notice that the second argument in the method call is an empty string. This will be used by print() to indent the output, but in this case, because it’s the first level of the directory tree you are printing, you don’t want any indenting at all, hence the “”. The constant SPACES (defined as two spaces) will be used later to increase the indentation.

The print() method accepts a single File and a string that will be used when indenting the output:

public static void print(File file, String indent) { assert file != null : “file can’t be null”; assert indent != null : “indent can’t be null”;

System.out.print(indent);

System.out.println(file.getName());

if (file.isDirectory()) { print(file.listFiles(), indent + SPACES);

}

}

The code itself is straightforward. First the indentation is printed, followed by the name of the file and a new line. If the file represents a directory (in Java, File objects are used for both individual files and directories), you call a different print() method to process the list of files contained within and the indentation to use them.

38

Iteration and Recursion

Because you are about to nest another level down in the tree, you want to increase the amount of indentation — that is, print everything shifted a couple of spaces to the right. You can achieve this by taking the current indentation and appending the value of the constant SPACES. At first, the indentation would be an empty string, in which case it will increase to two spaces, then four spaces, then six, and so on, thereby causing the printed output to be shifted right each time.

Now, as indicated, the method listFiles() returns an array; and as you don’t have a version of print() that accepts one of those yet, let’s create one:

public static void print(File[] files, String indent) { assert files != null : “files can’t be null”;

for (int i = 0; i < files.length; ++i) { print(files[i], indent);

}

}

This method iterates over the array, calling the original print() method for each file.

Can you see how this is recursive? Recall that the first print() method — the one that takes a single file — calls the second print() method, the one that takes an array, which in turn calls the first method, and so on. This would go on forever but for the fact that eventually the second print() method runs out of files — that is, it reaches the end of the array — and returns.

The following code shows some sample output from running this program over the directory tree containing the code for this book:

Beginning Algorithms

build

classes

com

wrox

algorithms

iteration

ArrayIterator.class

ArrayIteratorTest.class

Iterator.class

IteratorOutOfBoundsException.class

RecursiveDirectoryTreePrinter.class

ReverseIterator.class

ReverseIteratorTest.class

SingletonIterator.class

SingletonIteratorTest.class

src build.xml conf

build.properties checkstyle-header.txt checkstyle-main.xml checkstyle-test.xml checkstyle.xsl simian.xsl

lib

39

Chapter 2

antlr-2.7.2.jar checkstyle-3.5.jar checkstyle-optional-3.5.jar commons-beanutils.jar commons-collections-3.1.jar getopt.jar

jakarta-oro.jar jakarta-regexp.jar jamaica-tools.jar junit-3.8.1.jar simian-2.2.2.jar

main com

wrox algorithms

iteration ArrayIterator.java Iterator.java

IteratorOutOfBoundsException.java

RecursiveDirectoryTreePrinter.java

ReverseIterator.java

SingletonIterator.java

As you can see, the output is nicely formatted with appropriate indentation each time the contents of a directory are printed. It is hoped that this has demonstrated, in a practical way, how recursion can be used to solve some kinds of problems.

Any problem that can be solved recursively can also be solved iteratively, although doing so can sometimes be rather difficult and cumbersome, requiring data structures that have not been covered yet, such as stacks (see Chapter 5).

Anatomy of a Recursive Algorithm

No matter what the problem, a recursive algorithm can usually be broken down into two parts: a base case and a general case. Let’s reexamine the previous example and identify these elements.

The Base Case

In the example, when you encounter a single file, you are dealing with the problem at the smallest level of granularity necessary to perform whatever action the algorithm has been designed to do; in this case, print its name. This is known as the base case.

The base case, therefore, is that part of the problem that you can easily solve without requiring any more recursion. It is also the halting case that prevents the recursion from continuing forever.

A StackOverflowException while executing a recursive algorithm is often an indication of a missing or insufficient termination condition, causing your program to make more and more nested calls until eventually it runs out of memory. Of course, it might also indicate that the problem you are trying to solve is too large for the computing resources you have available!

40

Iteration and Recursion

The General Case

The general case, being what happens most of the time, is where the recursive call is made. In the example, the first recursive call occurs when you encounter a file that represents a directory. Having printed its name, you then wish to process all the files contained within the directory, so you call the second print() method.

The second print() method then calls back on the first print()method for each file found in the directory.

Using two methods that call each other recursively like this is also known as mutual recursion.

Summar y

Iteration and recursion are fundamental to implementing any algorithm. In fact, the rest of this book relies heavily on these two concepts so it is important that you fully understand them before continuing.

This chapter demonstrated the following:

Iteration lends itself more readily to solving some problems while for others recursion can seem more natural.

Iteration is a very simple, straightforward approach to solving many common problems such as performing calculations and processing arrays.

Simple array-based iteration doesn’t scale particularly well in most real-world applications. To overcome this, we introduced the concept of an iterator and discussed several different types of iterators.

Recursion uses a divide-and-conquer approach whereby a method makes repeated, nested calls to itself. It is often a better choice for processing nested data structures.

Many problems can be solved using either iteration or recursion.

Exercises

You will find sample answers to these exercises (and all of the exercises from other chapters as well) in Appendix D, “Exercise Answers.”

1.Create an iterator that only returns the value of every nth element, where n is any integer greater than zero.

2.Create a predicate that performs a Boolean AND (&&) of two other predicates.

3.Re-implement PowerCalculator using recursion instead of iteration.

4.Replace the use of arrays with iterators in the recursive directory tree printer.

5.Create an iterator that holds only a single value.

6.Create an empty iterator that is always done.

41

3

Lists

Now that you are familiar with iteration and some of the basics of algorithms, it is time to move on to your first complex data structure. Lists are the most fundamental data structure upon which most other data structures are built and many more algorithms must operate.

It’s not hard to find examples of lists in the real world: shopping lists, to-do lists, train timetables, order forms, even this “list of lists.” Much like arrays, lists are generally useful in most applications you will write. In fact, lists make a great substitute for the use of arrays — it is usually possible (and more often than not desirable) to entirely replace your use of arrays with lists in all but the most memory-sensitive/time-critical applications.

This chapter starts by introducing the basic operations of a list. From there, it heads straight into the tests before covering two different list implementations: array lists and linked lists. Both implementations conform to a common interface but have quite different characteristics. These differences can affect how and when you use them in your applications. By the end of this chapter, you will be familiar with the following:

What lists are

What lists look like

How lists are used

How lists are implemented

Understanding Lists

A list is an ordered collection of elements supporting random access to each element, much like an array — you can query a list to get the value contained at any arbitrary element. Lists also preserve insertion order so that, assuming there are no intervening modifications, a given list will always return the same value for the same position. Like arrays, lists make no attempt to preserve the uniqueness of values, meaning a list may contain duplicate values. For example, if you had a list containing the values “swimming”, “cycling”, and “dancing” and you were to add “swimming” again, you would now find that the list had grown to include two copies of “swimming”. The