Beginning Algorithms (2006)

Chapter 1

but if all you have is the command line, you can run the preceding test with the following command (you will need to have junit.jar on your classpath, of course):

java junit.textui.TestRunner com.wrox.algorithms.queues.RandomListQueueTest

Running the graphical version is just as easy:

java junit.swingui.TestRunner com.wrox.algorithms.queues.RandomListQueueTest

JUnit can also be used from within many tools, such as Ant or Maven, that you use to build your software. Including the running of a good unit test suite with every build of your software will make your development life a lot easier and your software a lot more robust, so check out the JUnit website for all the details.

Test-Driven Development

All the algorithms and data structures we present in the book include unit tests that ensure that the code works as expected. In fact, the unit tests were written before the code existed to be tested! This may seem a little strange, but if you’re going to be exposed to unit testing, you also need to be aware of an increasingly popular technique being practiced by developers who care about the quality of the code they write: test-driven development.

The term test-driven development was coined by Kent Beck, the creator of eXtreme Programming. Kent has written several books on the subject of eXtreme Programming in general, and test-driven development in particular. The basic idea is that your development efforts take on a rhythm, switching between writing some test code, writing some production code, and cleaning up the code to make it as well designed as possible (refactoring). This rhythm creates a constant feeling of forward progress as you build your software, while building up a solid suite of unit tests that protect against bugs caused by changes to the code by you or someone else further down the track.

If while reading this book you decide that unit testing is something you want to include in your own code, you can check out several books that specialize in this topic. Check Appendix A for our recommendations.

Summar y

In this chapter, you learned the following:

Algorithms are found in everyday life.

Algorithms are central to most computer systems.

What is meant by algorithm complexity.

Algorithms can be compared in terms of their complexity.

Big-O notation can be used to broadly classify algorithms based on their complexity.

What unit testing is and why it is important.

How to write unit tests using Junit.

14

2

Iteration and Recursion

Iteration and recursion are two fundamental concepts without which it would be impossible to do much, if anything, useful in computing. Sorting names, calculating credit-card transaction totals, and printing order line items all require that each record, each data point, be processed to achieve the desired result.

Iteration is simply the repetition of processing steps. How many repetitions are required can be determined by many different factors. For example, to calculate the total of your stock portfolio, you would iterate over your stock holdings, keeping a running total until each holding has been processed. In this case, the number of repetitions is determined by how many holdings you happen to have. Recursion is another technique for solving problems. Recursion can often, though not always, be a more natural way of expressing an algorithm than iteration. If you’ve done any programming at all, you probably already know what recursion is — you just didn’t know you knew.

A recursive algorithm involves a method or function calling itself. It does this by breaking a problem into smaller and smaller parts, each looking very similar to the larger part yet finer grained. This can be a difficult concept to grasp at first.

You will find that algorithms tend to fall naturally into one category or the other; they are most easily expressed either iteratively or recursively. Having said this, it is fair to say that recursive algorithms are fewer and farther between than iterative ones for most practical applications. In this chapter, we assume you are familiar with how to construct loops, make method calls, and so on, and so we instead concentrate on how iteration and recursion are used to solve problems.

This chapter describes the following:

How iteration is used to perform calculations

How iteration is used to process arrays

How to abstract the problem of iteration from simple arrays to more complex data structures

How recursion is another technique for solving similar problems

Chapter 2

Performing Calculations

Iteration can be used to perform calculations. Possibly one of the simplest examples of this is to raise one number (the base) to the power of another (the exponent): baseexp . This involves repeatedly multiplying the base by itself as many times as defined by the exponent. For example: 32 = 3 × 3 = 9 and 106 = 10 × 10 × 10 × 10 × 10 × 10 = 1,000,000.

In this section, you’ll implement a class, PowerCalculator, with a single method, calculate, that takes two parameters — an integer base and an exponent — and returns the value of the base raised to the power of the exponent. Although it’s possible to use a negative exponent, for the purposes of this example you can assume that only exponents greater than or equal to zero will be used.

Try It Out

Testing Calculations

The general case is pretty straightforward, but a few special rules should be considered, which are documented and codified as tests to ensure that the final implementation works as expected.

Begin by creating the test class itself, which does little more than extend TestCase:

package com.wrox.algorithms.iteration;

import junit.framework.TestCase;

public class PowerCalculatorTest extends TestCase {

...

}

The first rule involves raising the base to the power of zero. In all cases, this should result in the value of 1:

public void testAnythingRaisedToThePowerOfZeroIsOne() { PowerCalculator calculator = PowerCalculator.INSTANCE;

assertEquals(1, calculator.calculate(0, 0));

assertEquals(1, calculator.calculate(1, 0)); assertEquals(1, calculator.calculate(27, 0)); assertEquals(1, calculator.calculate(143, 0));

}

The next rule involves raising the base to the power of one. In this case, the result should always be the base itself:

public void testAnythingRaisedToThePowerOfOneIsItself() { PowerCalculator calculator = PowerCalculator.INSTANCE;

assertEquals(0, calculator.calculate(0, 1));

assertEquals(1, calculator.calculate(1, 1)); assertEquals(27, calculator.calculate(27, 1)); assertEquals(143, calculator.calculate(143, 1));

}

16

Iteration and Recursion

Finally, you arrive at the general case:

public void testAritrary() {

PowerCalculator calculator = PowerCalculator.INSTANCE;

assertEquals(0, calculator.calculate(0, 2)); assertEquals(1, calculator.calculate(1, 2));

assertEquals(4, calculator.calculate(2, 2));

assertEquals(8, calculator.calculate(2, 3)); assertEquals(27, calculator.calculate(3, 3));

}

How It Works

The first rule makes a number of calculations, each with different values, and ensures that the calculation returns 1 in all cases. Notice that even 0 raised to the power of zero is actually 1!

Also in the second rule, you perform a number of calculations with varying base values but this time using an exponent of 1.

This time, the outcome of the calculation is tested using a number of different combinations of base and exponent.

Try It Out

Implementing the Calculator

Having coded the tests, you can now implement the actual calculator:

package com.wrox.algorithms.iteration;

public final class PowerCalculator {

public static final PowerCalculator INSTANCE = new PowerCalculator();

private PowerCalculator() {

}

public int calculate(int base, int exponent) { assert exponent >= 0 : “exponent can’t be < 0”;

int result = 1;

for (int i = 0; i < exponent; ++i) { result *= base;

}

return result;

}

}

How It Works

The calculate() method first checks to ensure that the exponent is valid (remember that you don’t allow negative values) and initializes the result to 1. Then comes the iteration in the form of a for loop. If the exponent was 0, the loop would terminate without performing any multiplication and the result

17

Chapter 2

would still be 1 — anything raised to the power of zero is one. If the exponent was 1, the loop would make a single pass, multiplying the initial result by the base and returning to the caller — a number raised to the power of one is the number itself. For values of the exponent larger than this, the loop will continue, multiplying the result by the base as many times as specified.

A private constructor is used in order to prevent instances of the class from being constructed from outside the class itself. Instead, a single instance can be accessed via the constant INSTANCE. This is an example of the Singleton design pattern [Gamma, 1995].

Processing Arrays

Besides performing calculations, iteration is also used to process arrays. Imagine you wanted to apply a discount to a group of orders. The following code snippet iterates over an array of orders, applying a specified discount to each:

Order[] orders = ...;

for (int i = 0; i < orders.length; ++i) { orders[i].applyDiscount(percentage);

}

We first initialize our index variable with the position of the first element (int i = 0) and continue incrementing it (++i) until reaching the last element (i < orders.length – 1), applying the percentage. Notice that each iteration compares the value of the index variable with the length of the array.

Sometimes you may wish to process an array in reverse. For example, you may need to print a list of names in reverse order. The following code snippet iterates backward over an array of customers, printing the name of each:

Customer[] customers = ...;

for (int i = customers.length – 1; i >= 0; --i) { System.out.println(customers[i].getName());

}

This time, initialize the index and continue decrementing ( time through the loop.

variable to the position of the last element (int i = customers.length – 1) --i) until reaching the first (i >= 0), printing the customer’s name each

Using Iterators to Overcome Array-based Problems

Although array-based iteration is useful when dealing with very simple data structures, it is quite difficult to construct generalized algorithms that do much more than process every element of an array from start to finish. For example, suppose you want to process only every second item; include or exclude specific values based on some selection criteria; or even process the items in reverse order as shown earlier. Being tied to arrays also makes it difficult to write applications that operate on databases or files without first copying the data into an array for processing.

18

Iteration and Recursion

Using simple array-based iteration not only ties algorithms to using arrays, but also requires that the logic for determining which elements stay, which go, and in which order to process them, is known in advance. Even worse, if you need to perform the iteration in more than one place in your code, you will likely end up duplicating the logic. This clearly isn’t a very extensible approach. Instead, what’s needed is a way to separate the logic for selecting the data from the code that actually processes it.

An iterator (also known as an enumerator) solves these problems by providing a generic interface for looping over a set of data so that the underlying data structure or storage mechanism — such as an array, database, and so on — is hidden. Whereas simple iteration generally requires you to write specific code to handle where the data is sourced from or even what kind of ordering or preprocessing is required, an iterator enables you to write simpler, more generic algorithms.

Iterator Operations

An iterator provides a number of operations for traversing and accessing data. Looking at the operations listed in Table 2-1, you will notice there are methods for traversing backward as well as forward.

Remember that an iterator is a concept, not an implementation. Java itself already defines an Iterator interface as part of the standard Java Collections Framework. The iterator we define here, however, is noticeably and deliberately different from the standard Java version, and instead conforms more closely to the iterator discussed in Design Patterns [Gamma, 1995].

Table 2-1: Iterator Operations

Operation	Description
previous	Positions to the previous item. Throws UnsupportedOperationExcep-
	tion if not implemented.
isDone	Determines whether the iterator refers to an item. Returns true if the end
	has been reached; otherwise, returns false to indicate more items need to
	be processed.
current	Obtains the value of the current item. Throws IteratorOutOfBoundsEx-
	ception if there is no current item.

Most methods can potentially throw an UnsupportedOperationException. Not all data structures allow traversing the data in both directions, nor does it always make sense. For this reason, it is acceptable for any of the traversal methods — first(), last(), next(), and previous() — to throw an UnsupportedOperationException to indicate this missing or unimplemented behavior.

You should also leave the behavior of calling current() before either first() or last() has been called undefined. Some iterator implementations may well position to the first item, while others may require you to call first() or last(). In any event, relying on this behavior is considered to be programming by coincidence and should be avoided. Instead, when using iterators, be sure to follow one of the idioms described in the “Iterator Idioms” section, later in the chapter.

19

Chapter 2

The Iterator Interface

From the operations just described, you can create the following Java interface:

package com.wrox.algorithms.iteration;

public interface Iterator { public void first();

public void last();

public boolean isDone();

public void next();

public void previous();

public Object current() throws IteratorOutOfBoundsException;

}

As demonstrated, you have quite literally translated the operations into a Java interface, one method per operation.

You also need to define the exception that will be thrown if an attempt is made to access the current item when there are no more items to process:

package com.wrox.algorithms.iteration;

public class IteratorOutOfBoundsException extends RuntimeException {

}

Because accessing an iterator out-of-bounds is considered a programming error, it can be coded around. For this reason, it’s a good idea to make IteratorOutOfBoundsException extend RuntimeException, making it a so-called unchecked exception. This ensures that client code need not handle the exception. In fact, if you adhere to the idioms discussed soon, you should almost never see an IteratorOutOfBoundsException.

The Iterable Interface

In addition to the Iterator interface, you’ll also create another interface that provides a generic way to obtain an iterator from any data structure that supports it:

package com.wrox.algorithms.iteration;

public interface Iterable { public Iterator iterator();

}

The Iterable interface defines a single method — iterator() — that obtains an iterator over the data contained in whatever the underlying data structure contains. Although not used in this chapter, the Iterable interface enables code that only needs to iterate over the contents of a data structure to treat all those that implement it in the same way, irrespective of the underlying implementation.

20

Iteration and Recursion

Iterator Idioms

As with simple array-based iteration, there are two basic ways, or templates, for using iterators: either a while loop or a for loop. In either case, the procedure is similar: Once an iterator has been obtained — either by explicit construction or as an argument to a method — position to the beginning or end as appropriate. Then, while there are more items remaining, take each one and process it before moving on to the next (or previous).

Using a while loop enables you to perform quite a literal translation from the preceding text into code:

Iterator iterator = ...; iterator.first();

while (!iterator.isDone()) {

Object object = iterator.current();

...

iterator.next();

}

This way is particularly useful when an iterator has been passed as a parameter in a method call. In this case, the method may not need to call first() or last() if the iterator has already been positioned to the appropriate starting point.

The use of a for loop, however, is probably more familiar to you as it closely resembles the way you would normally iterate over an array:

Iterator iterator = ...;

for (iterator.first();!iterator.isDone(); iterator.next()) { Object object = iterator.current();

...

}

Notice how similar this is to array iteration: The initialization becomes a call to first(); the termination condition is a check of isDone(); and the increment is achieved by calling next().

Either idiom is encouraged, and both are used with more or less the same frequency in most real-world code you have seen. Whichever way you choose, or even if you choose to use both, remember to always call first() or last() before you call any other methods. Otherwise, results might be unreliable and depend on the implementation of the iterator.

Standard Iterators

In addition to the iterators provided by some of the data structures themselves later in this book, or even iterators you might create yourself, several standard implementations provide commonly used functionality. When combined with other iterators, these standard iterators enable you to write quite sophisticated algorithms for data processing.

21

Chapter 2

Array Iterator

The most obvious iterator implementation is one that wraps an array. By encapsulating an array within an iterator, you can start writing applications that operate on arrays now and still extend easily to other data structures in the future.

Try It Out

Testing the Array Iterator

The test for our array iterator will have the usual structure for a JUnit test case, as shown here:

package com.wrox.algorithms.iteration;

import junit.framework.TestCase;

public class ArrayIteratorTest extends TestCase {

...

}

One of the advantages of using iterators is that you don’t necessarily have to traverse an array from the start, nor do you need to traverse right to the end. Sometimes you may want to expose only a portion of an array. The first test you will write, therefore, is to ensure that you can construct an array iterator passing in the accessible bounds — in this case, a starting position and an element count. This enables you to create an iterator over all or part of an array using the same constructor:

public void testIterationRespectsBounds() {

Object[] array = new Object[] {“A”, “B”, “C”, “D”, “E”, “F”}; ArrayIterator iterator = new ArrayIterator(array, 1, 3);

iterator.first();

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

iterator.next();

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

iterator.next();

assertFalse(iterator.isDone()); assertSame(array[3], iterator.current());

iterator.next();

assertTrue(iterator.isDone()); try {

iterator.current();

fail();

}catch (IteratorOutOfBoundsException e) {

//expected

}

}

22

Iteration and Recursion

The next thing you want to test is iterating backward over the array — that is, starting at the last element and working your way toward the first element:

public void testBackwardsIteration() {

Object[] array = new Object[] {“A”, “B”, “C”}; ArrayIterator iterator = new ArrayIterator(array);

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

}

}

}

How It Works

In the first test, you begin by constructing an iterator, passing an array containing six elements. Notice, however, you have also passed a starting position of 1 (the second element) and an element count of 3. Based on this, you expect the iterator to return only the values “B”, “C”, and “D”. To test this, you position the iterator to the first item and ensure that its value is as expected — in this case, “B”. You then call next for each of the remaining elements: once for “C” and then again for “D”, after which, even though the underlying array has more elements, you expect the iterator to be done. The last part of the test ensures that calling current(), when there are no more items, throws an IteratorOutOfBoundsException.

In the last test, as in the previous test, you construct an iterator, passing in an array. This time, however, you allow the iterator to traverse all the elements of the array, rather than just a portion of them as before. You then position to the last item and work your way backward, calling previous() until you reach the first item. Again, once the iterator signals it is done, you check to ensure that current() throws an exception as expected.

That’s it. You could test for a few more scenarios, but for the most part that really is all you need in order to ensure the correct behavior of your array iterator. Now it’s time to put the array iterator into practice, which you do in the next Try It Out.

23