Loops

You have seen that conditional code is like a fork in the path of program execution. Extending this analogy, a loop is like an eddy or a whirlpool. No, wait, that can't be right... paths don't have whirlpools. The analogy has broken down. At any rate, a loop is a piece of code that is executed repeatedly. The number of repetitions can be some preset value, or the loop can run on and on until a condition is met.

We will begin with while loops, and then move on to for loops. We will also look at several techniques for enhancing loop behavior: breaking, continuing, and nesting.

While Loops

A while loop is a chunk of code that is executed repeatedly until a certain condition is met. The format for a while loop is

while (expression)   loop_body 

The expression must be of the boolean type. The loop body is the code to be repeated. This can be either a single statement or a block of code enclosed in curly brackets. Initially the expression is evaluated, and if its value is true, the loop body is executed once. Then the expression is evaluated again, and if its value is still true, the loop body is executed once again. This happens again and again and again. Eventually (we hope), the expression evaluates to false. When this happens, the loop body is not executed anymore. Instead, control jumps to the code immediately after the loop body.

This explanation might seem paradoxical. If the while loop is to be of any use, the expression must initially evaluate to true. Otherwise, the loop body won't be executed at all. But if the expression is indeed initially true, how can the loop ever terminate?

The answer is that either the expression or the loop body must modify the data from which the expression is calculated. Let's look at a few examples of how this works.

First, here is a useless loop that prints too many messages:

int x = 23; while (x > 0)   System.out.println("Still going!");

This loop runs forever or until you press Ctrl+C to terminate the program, whichever comes first. This example demonstrates the need to somehow modify the data that constitutes the expression.

The next example is more useful. The following code prints the numbers 1 through 10:

int counter = 1; while (counter <= 10) {   System.out.println("counter = " + counter);   counter += 1; }

You can use a pre-increment or post-increment operator to make this code slightly more terse:

int counter = 1; while (counter <= 10) {   System.out.println("counter = " + counter);   counter++; }

The next example prints out consecutive square numbers that are less than 1,000:

int counter = 1; while (counter*counter < 1000) {   System.out.println(counter * counter);   counter++; }

This example points out a useful feature of while loops: You don't need to know beforehand how many passes you want to make through the loop body. You could certainly find a calculator, figure out that the square root of 1,000 is 31.6227766..., and write the following:

int counter = 1; while (counter <= 31) {   System.out.println(counter * counter);   counter++; }

This approach works, but it violates the spirit of making the computer compute. If you're programming a computer, you shouldn't have to reach for a calculator. With the next-to-last version of the example, you take advantage of the fact that you don't have to know how many passes you're going to make through a while loop. You just have to be able to know when you're done.

While loops are the first of several kinds of loops that we will present in this chapter. Loops are powerful because a few lines of source code can cause the computer to execute a very large number of instructions.

The WhileLab animated illustration demonstrates while loops. To run the program, type java loops.WhileLab. You see a display that shows a while loop with two assignment lines in its body, as shown in Figure 5.1.

Figure 5.1: While Lab: initial display

The loop uses variables a and b. As the code executes, their values are displayed and updated. Click on the Step button to animate the next line of code. Click on the Run button to animate the entire loop. You can click on Step Lightspeed or Run Lightspeed to bypass the animation and just see the result. When the animation is finished, click Reset to start again.

You can type in your own values for the initial values of a and b, for the test expression, and for the new values that are assigned to a and b within the loop. Figure 5.2 shows While Lab with a slightly modified test expression.

Figure 5.2: While Lab with modified test expression

Figure 5.3 shows the result of executing the configuration shown in Figure 5.2.

Figure 5.3: While Lab after execution

Try typing in different values for b <= ?? in the test expression. (If you enter a large number, the loop will be executed a large number of times, so you probably want to execute with the Run Lightspeed button rather than the Run button.) As you vary the limit on b, what do you notice about the final value of a?

Try configuring WhileLab's code display so that the code computes the following results (which can be in either a or b, whichever you prefer):

• The sum of the numbers 1 through 500, inclusive.

• The sum of the even numbers from 50 through 60, inclusive.

• The product of the first five odd numbers.

Now that you have some experience with while loops, we can look at a variation on the theme: do-while loops.

Do-While Loops

A while loop always tests its condition before executing its body. There may be times when you want to execute the body first, and then test. This is done with a do-while loop. The format of a do-while loop is

do   loop_body while (expression); 

As with ordinary while loops, the loop body can be either a single statement or a curly bracket-enclosed block. Note that the parenthetical expression must be followed by a semicolon.

When a do-while loop is executed, the loop body is executed. Then the expression is evaluated. If the expression evaluates to true, the loop body is executed again, the expression is evaluated again, and so on until eventually the expression value is false. At that point, execution of the loop is finished. As with ordinary while loops, you should write do-while code in such a way that during execution of the loop, the data constituting the expression changes so that at some point the expression's value can become false.

The code in the following example prints out the cube of x, and then increments x by 5, until x exceeds 100:

do {   System.out.println(x*x*x);   x += 5; } while (x <= 100);

The body of a do-while loop is always executed at least once. In the preceding example, at least one line will be printed out, even if the initial value of x is greater than 100.

Do-while loops are not very different from while loops. The main difference is that the body of a while loop might not ever be executed, whereas the body of a do-while loop will always be executed at least once.

Now let's look at for loops, which are useful when you know how many passes through the loop body you want.

For Loops

The following code, which uses a while loop to compute a value and print a message ten times, has a very common structure:

int z = 0; while (z < 10) {   int formula = z*z*z + z*z;   System.out.println(formula);   z++; }

The code first initializes z, and then it enters a while loop. Within the loop body, the first two lines perform the internal business of the loop, so to speak. The last line (z++) is concerned with updating the only data that changes from pass to pass in the loop. Figure 5.4 shows the structure of the loop.

Figure 5.4: A common loop usage

This structure (initializing before a loop, incrementing at the end of the loop body) is so common that there is a special kind of loop to support it. The for loop has the following format:

for (initialization; condition; update)   body

This for loop is exactly equivalent to

initialization; while (condition) {   body   update }

The for keyword must be followed by three items, known as the initialization, the condition, and the update. These are enclosed in parentheses and separated by semicolons. When the for loop is processed, the initialization is executed once. Then the condition, whose type must be boolean, is evaluated. If the condition is true, the loop body is executed. Then the condition is evaluated again, and so on until the condition is false. Notice that no matter how many times the loop body is executed (zero times, once, or multiple times) the initialization is executed exactly once.

For loops are useful when you know beforehand how many times you want the loop body to be executed. (They are especially useful when you're processing arrays, which will be presented in the next chapter.) When you don't know beforehand how many times the body should execute, you are generally better off using a while loop because your code will be less complicated.

Usually, the initialization involves setting the value of a single variable, often to zero. The condition is usually a test on the value of that variable, and the update increments the variable. For example, the following code prints out a message 10 times:

int i; for (i=0; i<10; i++)   System.out.println("DANGER!"); 

In this code, the variable i is used just to regulate the number of passes through the loop body. Since it does not appear in the body, we could have chosen any name for the variable, but it is conventional to use i (or j if i is in use). A variable used in this way (regulating the number of passes through the loop body, but otherwise playing little or no role in the body) is called a loop counter. We could have initialized i to any value, as long as the value in the condition was 10 greater than that, but it is conventional to start a loop counter at 0. If you follow these conventions, and we strongly recommend that you do so, people who read your code will have a good chance of understanding your intentions.

The initialization and update portions of a for loop can have multiple parts, separated by commas. For example, the following code prints out the areas of rectangles whose bases range from 5 to 10 inches, and whose heights are 2 inches more than the base:

int base, height; for (base=5, height=7; base<=10; base++, height++) {   int area = base * height;   System.out.println(area + " square inches"); }

Here, both the initialization and the update have multiple parts.

Breaking and Continuing

Usually a loop runs until its condition is false. However, there may be times when you want to terminate the loop prematurely. This is called breaking out of the loop.

As an example of loop breaking, imagine you are writing a payroll program for a small company. The company has 100 employees whose ID numbers are 1001 through 1100. A method called getPayAmount, which takes an employee ID as its argument, returns the amount of money the employee should be paid. Another method called printCheck, which has an employee ID and an amount as its arguments, prints the specified employee's paycheck. A variable called balance keeps track of how much money the company has in the bank.

The following code prints everybody's paycheck and keeps track of the bank balance:

int id; for (id=1001; id<=1100; id++) {   float pay = getPayAmount(id);   printCheck(id, pay);   balance -= pay; }

The problem with this code is that it doesn't take precautions against using up all the money in the bank account. The following code uses a break statement to terminate the loop as soon as there isn't enough money left to cover the next paycheck:

int id; for (id=1001; id<=1100; id++) {   float pay = getPayAmount(id);   if (balance-pay < 0)     break;   printCheck(id, pay);   balance -= pay; }

The break statement causes immediate termination of the loop. Execution continues with the first line of code following the loop. You can break out of any kind of loop: do, do-while, and for. Note that this application of break is unrelated to using break to terminate a case in a switch block. The two situations are very different.

There might be times when you want to terminate not the entire loop, but just the current pass through the loop. You do this with the continue statement. The following example uses continue in a loop that prints out the square and cube of every number from 1 through 20, except 8:

int i; for (i=1; i<=20; i++) {   if (i == 8)     continue;   int squared = i * i;   int cubed = squared * i;   System.out.println(squared + ", " + cubed); }

The continue statement causes control to jump to the end of the loop body. Then the update (i++) is executed, the condition is checked, and perhaps more passes are made through the loop body. In other words, the current pass through the loop body is terminated prematurely. As with break statements, you can use continue statements with do and do-while loops as well as with for loops.

The continue statement allows you to improve on the preceding paycheck example, which broke out of the loop as soon as you couldn't afford to pay a salary. This was possibly unfair to the workers who had not yet been paid. After all, the employee who caused the break might have had the highest salary in the company. Even if there was not enough money to pay that person, there might still be enough left to pay someone else. So a more fair version of the program would be

int id; for (id=1001; id<=1100; id++) {   float pay = getPayAmount(id);   if (balance-pay < 0)     continue;   printCheck(id, pay);   balance -= pay; }

The only difference between this version and the previous one is the replacement of break with continue. Now the loop never terminates prematurely, although some passes through loop body might do so.

Nesting

The body of a loop can contain any valid Java code, including another loop, which can itself contain any valid Java code, including another loop, and so on. The technique of putting a loop within a loop is called nesting.

As an example of loop nesting, suppose you are writing code to generate frames for an animated movie. Assume that a frame consists of a grid of 1000 x 1000 pixels. (Pixel is an abbreviation for picture element. A pixel is a tiny dot of color, almost too small to see. If you hold a magnifying glass up to your computer screen, you can see the individual pixels.) Assume also that there is a method called computePixel, which takes as arguments the horizontal and vertical positions of the pixel whose color value is to be computed. Fortunately, computePixel also stores the color value in the appropriate place, so all you have to worry about here is calling the method with the right arguments.

The following code uses nested for loops to call computePixel for every pixel position:

1. int x, y;  // x = horiz, y = vert 2. for (y=0; y<1000; y++) 3.   for (x=0; x<1000; x++) 4.     computePixel(x, y);

It is conventional to use x as a variable name for representing horizontal positions, and y for representing vertical positions. Line 2 says that the outer loop body will be executed with y ranging from 0 through 999. The outer loop body is lines 3 and 4. Line 3 says that the inner loop body, which is line 4, will be executed with x ranging from 0 through 999. So the first value pair passed to computePixel at line 4 will be (0, 0), followed by (1, 0), and then (2, 0), and then (3, 0), and so on up to (999, 0). Those thousand calls are the first pass through the outer loop. Then y is incremented from 0 to 1 and compared to 1,000. Since y is found to be still less than 1,000, the second pass through the outer loop begins: computePixel is called with arguments of (0, 1), (1, 1), through (999, 1). Every pass through the outer loop entails a thousand passes through the inner loop, until finally computePixel is called with arguments of (999, 999). At this point, the outer loop's condition is false, so the outer loop is finally done.

The body of the outer loop is two lines long (lines 3 and 4), but due to a technicality, the lines do not have to be enclosed in curly brackets. This is because, technically speaking, lines 3 and 4 are a single statement: a for loop. Only bodies consisting of multiple statements need to be enclosed in curly brackets. The precise definition of a statement is extremely intricate, but statements are easy to recognize because they end with semicolons. So you can get away with omitting curly brackets in this example, although you should indent responsibly to make it clear to readers that you are using a nested loop. However, it does no harm to add the curly brackets anyway (it's okay to have a block that contains just a single statement). The curly brackets do not affect execution speed, and they make the code a bit more readable, as you can see here:

1. int x, y;  // x = horiz, y = vert 2. for (y=0; y<1000; y++) 3. { 4.   for (x=0; x<1000; x++) 5.   { 6.     computePixel(x, y); 7.   } 8. }

The NestedLoopLab animated illustration lets you use loops to draw cycloids. Cycloids are beautiful, complex geometric shapes. If you have ever played with a Spirograph, you have already appreciated cycloids. You could create some wonderful images with a Spirograph by drawing several curves in the same space but varying the curves' orientation or some other feature. If you have done this, you have performed a repetitive complicated task, varying features from one repetition to the next. In other words, you have done something that can be modeled with a loop, or possibly with nested loops.

A cycloid is the curve traced out by a point on a circle (the roller) as it rolls without slipping around the inside of a larger circle (the gasket). The roller always touches the gasket at one point, as shown in Figure 5.5.

Figure 5.5: A cycloid

The ratio between the size of the roller and the size of the gasket determines the number of lobes the curve will have. The ratio in Figure 5.5 is 1:4, so the curve has 4 lobes.

The inset is the distance from the tracing point to the rim of the roller. NestedLoopLab uses arbitrary inset units of 0 through 10, where 0 is the rim of the roller and 10 is the center. The orientation is the point of initial contact between the roller and the gasket, measured in clockwise degrees from straight up.

NestedLoopLab lets you select a ratio and color. You also choose a loop style. The default is no loop, but you can choose Loop to select a loop that varies the inset or the orientation. For really sophisticated images, you can use nested loops that vary the inset and the orientation, in either order. The Color choice lets you leave the color constant or vary the color in any of the loops

To launch NestedLoopLab, type java loops.NestedLoopLab. You will first see the display shown in Figure 5.6.

Figure 5.6: NestedLoopLab: initial display

Figure 5.7 shows NestedLoopLab with a ratio of 8:15 and a small inset.

Figure 5.7: NestedLoopLab: 8:15

In Figure 5.8, the configuration uses a loop, with the inset ranging from 0–6.

Figure 5.8: NestedLoopLab with a loop

Figure 5.9: NestedLoopLab with nested loops

Now try it for yourself. Enjoy! You can use the File ‚ Gallery menu to view a few sample patterns. If you come up with a really spectacular image, please e-mail its settings to me at www.sybex.com so we can include it in future revisions of the gallery.

Labeled break and Labeled continue

Breaking out of a hierarchy of nested loops can be difficult. It might happen that code in an inner loop detects a condition that should cause an outer loop to be terminated. For example, you might use three nested loops to print paychecks for every employee in every department in every division of a large company. (Each department uses its own set of employee IDs, starting from zero.) The getPayAmount method now takes three arguments: division, department, and ID. Let's assume another feature for this method: The if statement will return a negative value if the corporate database that it consults is down. When this happens, paycheck processing should be terminated at once.

The following code would not be correct:

 1. int    divn, dept, nDepartments, nEmployees, id;  2. float  pay;  3. 4. for (divn=0; divn <nDivisions; divn ++)  5. {  6.   nDepartments = getDepartmentCount(divn);  7.   for (dept=0; dept <nDepartments; dept ++)  8.   {  9.     nEmployees = getEmployeeCount(divn, dept); 10.     for (id=0; id<nEmployees; id++) 11.     { 12.       pay = getPayAmount(divn, dept, id); 13.       if (pay < 0) 14.         break; 15.       printCheck(divn, dept, id, pay); 16.       balance -= pay; 17.     } 18.   } 19. }

The code assumes the presence of methods that return the number of departments in a division (getDepartmentCount) and the number of employees in a department (getEmployeeCount). It also assumes that nDivisions has been preset to the number of divisions in the company. The variable names nDivisions, nDepartments, and nEmployees mean, of course, the number of divisions, the number of departments, and the number of employees. This kind of naming convention is common and useful.

Unfortunately, the code doesn't work. The break keyword breaks out of the immediately enclosing loop, not out of all loops. So the break at line 14 just breaks out of the innermost loop (lines 10-17). Processing then continues with the next department because we are still in the middle loop (lines 7-18).

There is a simple but clumsy solution, which is shown in the following code. The innermost loop, when it detects a database problem, sets a boolean variable to true. The middle and outer loops have to check this variable and do their own break if it is true. Incidentally, a boolean variable that's used in this way to indicate program status is often called a flag. Here is the correct but clumsy code:

 1. int      divn, dept, nDepartments, nEmployees, id;  2. float    pay;  3. boolean  trouble = false;  4.  5. for (divn=0; divn <nDivisions; divn ++)  6. {  7.   nDepartments = getDepartmentCount(divn);  8.   for (dept=0; dept <nDepartments; dept ++)  9.   { 10.     nEmployees = getEmployeeCount(divn, dept); 11.     for (id=0; id<nEmployees; id++) 12.     { 13.       pay = getPayAmount(divn, dept, id); 14.       if (pay < 0) 15.       { 16.         trouble = true; 17.         break; 18.       } 19.       printCheck(divn, dept, id, pay); 20.       balance -= pay; 21.     }                  // End of inner loop 22.     if (trouble) 23.       break; 24.   }                    // End of middle loop 25.   if (trouble) 26.     break; 27. }                      // End of outer loop

The code is difficult to read, which is a good indicator of code that is needlessly complicated. The solution is Java's labeled break feature. This feature lets you assign a name, or label, to any for, while, or do-while loop. The label is any valid identifier (so you just need to follow the same rules that govern variable or method names). The label, followed by a colon, appears just before the for, while, or do keyword. Now you can break out of the labeled loop, even from code in a loop nested inside the labeled loop, by adding the loop's label after the break keyword.

The following code elegantly fixes the paycheck program by using a labeled loop and a labeled break:

 1. int    divn, dept, nDepartments, nEmployees, id;  2. float  pay;  3.  4. bigloop: for (divn=0; divn <nDivisions; divn ++)  5. {  6.   nDepartments = getDepartmentCount(divn);  7.   for (dept=0; dept <nDepartments; dept ++)  8.   {  9.     nEmployees = getEmployeeCount(divn, dept); 10.     for (id=0; id<nEmployees; id++) 11.     { 12.       pay = getPayAmount(divn, dept, id); 13.       if (pay < 0) 14.         break bigloop; 15.       printCheck(divn, dept, id, pay); 16.       balance -= pay; 17.     } 18.   } 19. } 

Now line 14 causes the outermost loop to break.

Java also provides a labeled continue feature. The statement continue label; terminates the current pass through the labeled loop. If the label were omitted, the current pass through the innermost loop would terminate instead.

Loops and Scope

The previous chapter introduced the concept of scope. As a reminder, a variable's scope is the block (inside curly brackets) that most tightly encloses the variable's declaration. The variable has definition only within its scope. Outside the scope, the variable's name may be reused, but the name refers to a different piece of data with its own scope.

With the introduction of loops, you begin to use code that can consist of blocks nested in blocks nested in blocks, and so on. This raises the issue of where variables should be declared. A good rule of thumb is that a variable's scope should be as small as possible. This means that if a variable is used only in a loop, it should be declared inside the loop.

For example, in the paycheck code of the previous section, you declared float pay outside the outermost loop, even though it is only used in the innermost loop. A clear approach would be to eliminate the declaration on line 2 and change the innermost loop to the following:

     for (id=0; id<nEmployees; id++)      {        float pay = getPayAmount(divn, dept, id);        if (pay < 0)          break bigloop;        printCheck(divn, dept, id, pay);        balance -= pay;      }

Now anyone who reads the code and wonders where pay is used only has to think about five lines.

You are allowed to declare a variable in the initialization statement of a for loop. Thus, the following is allowed (and, in fact, is encouraged):

for (int i=0; i<10; i++) {   // Loop body   // More loop body }

The scope of i is the body of the loop.