Lesson 6.3 Indefinite Loops

Why while?

Here's a condensed fragment of code from an applet named Indefinite.java. The Indefinite applet uses a simple "event-testing" loop similar to the one shown here. Take a look at this loop, and see if you can guess how many times it will execute.

An Indefinite Loop

int count = 0; output.setText("" + count); char randomChar = (char)(Math.random() * 128); while (randomChar != 'Q') {   output.setText("" + ++count);   randomChar = (char) (Math.random() * 128); } How many times will this loop execute? Press the Button and see!

When you press the button, the Indefinite applet will execute the loop shown here. Can you tell how many times this loop will execute? Probably not. That's why this kind of loop is called an indefinite loop. You can't tell by reading the source code how many repetitions it will make.

In the Indefinite applet, the character variable, randomChar, is assigned a value between 0 and 127, calculated by using the Math.random() method. In the loop that follows, randomChar is tested, and, if it is not equal to the character 'Q', then the loop body is entered, where the number of repetitions is incremented and displayed.

Even though this is not a counted loop, the body of the loop must still contain code that advances the loop's bound. If it does not, then, once entered, the loop will repeat for ever. In this example, we advance toward the loop's bound by calculating a new random character for randomChar. 

Back to Top

Sentinel Bounds

• When searching through text to find a character or word.
• When used as an "out-of-bounds" value that marks the end of input.

Sentinel Ranges

A sentinel doesn't always have to be a single value; it may include a range of values. For instance, here is a problem statement that calls for a sentinel loop, but a simple sentinel value would be insufficient:

Rather than just reading ahead, why don't you see if you can apply what you learned in Lesson 6.1, "A Loop-building Strategy", to create a loop that meets these requirements. When you're done, come on back here and we'll tackle it together.

Here are the questions you should ask yourself:

1. What is the loop's bounds?
2. What are the necessary bounds preconditions?
3. What are the necessary actions to advance toward the bounds?
4. What is the goal?
5. What are the goal preconditions?
6. What actions are necessary in the body to carry out the goal?
7. What postcondition actions are necessary to carry out the goal?

Back to Top

A Solution

• What is the loop's bounds?

The loop's bound is that a negative number was entered. The Java loop condition should look like this:



while (num >= 0)

• What are the necessary bounds preconditions?

The only precondition is that num holds a value. The value could come from reading a network stream, could be entered from the keyboard, or could be generated by a random number generator. The only hard-and-fast requirement is that num must be initialized in such a way that it is possible to either enter or to avoid the loop.



int num = getRandomNumber();

• What are the necessary actions to advance toward the bounds?

Inside the loop body, the value of num must change. You should read another number from the keyboard, or from the network stream, or, as we've done, generate another random number.

• What is the goal?
The loop's goal is simple. It should display the number of positive integers entered, the sum of the integers, and their average.
 
• What are the goal preconditions?
To meet the goal, you must have a counter, and a variable that can hold the sum. The counter can be an int, but the sum should be a double. Using an int for the sum would be inappropriate because summing just two very large integers would cause the variable to overflow.
 
• What actions are necessary in the loop body to carry out the goal?
• Each positive number should be added to the sum of the numbers.
• The count should be incremented for each number entered.

 
• What postcondition actions are necessary to carry out the goal?
• You must first check for a count of zero. If count is zero then no numbers were entered and you can't compute the average or sum.
• If count is greater than zero, then compute and display the sum, average, and count of numbers entered.

PositiveAverage.java - Here's an applet that follows this strategy to calculate the average of a stream of semi-random numbers. This example is a little different than the first example because, instead of using a single sentinel--the number zero, for instance--it uses a range of sentinels--any number less than zero--to mark the end of valid input.

The program loop below has been abbreviated to highlight the features of the loop. You can download the actual code from the hyperlink at the beginning of this section.

A Sentinel-Range Loop

// Precondition int     count = 0; double  sum   = 0.0; int num = getRandomNumber(); while (num >= 0) {   // Loop actions   output.setText("" + ++count);   sum += num;   num = getRandomNumber(); } // Postcondition if (count > 0) {   String s = "Count =";   s += fmt.format(count);   s += ", Sum = ";   s += fmt.format(sum);   s += ", Avg = ";   s += fmt.format(sum / count);   output.setText(s); } else {   output.setText("No numbers entered"); } Here's an applet named PositiveAverage that generates random numbers and then calculates the sum and average of the numbers generated. When a negative number is generated, the applet stops.

Back to Top

Primed and Inline Tests

• we've set up the value of the variable
• tested the value against the sentinel in the loop condition
• processed the variable as needed in the loop body
• updated the variable's value at the end of the loop body, just before returning to the loop test for the next repetition

Because assignment is an operator in Java, and not a statement, there is a much shorter and more concise way to write the same kind of sentinel loop. A loop employing an inline test is an extremely common Java idiom, and you should become familiar with it, even if you prefer the longer, more traditional primed loop.

Using an inline test, the loop in the preceding program can be rewritten like this:

An Inline-test Sentinel Loop

while ((num = getRandomNumber()) >= 0) {   // Loop actions   output.setText("" + ++count);   sum += num; }

Now, you only have to initialize num once--during the loop test--and not twice--before and at the end of the loop. 

Note the additional set of parentheses surrounding the assignment operation:

The parentheses are required because the precedence of the relational operator [>=] is higher than the precedence of the assignment operator. If you omit the parentheses, Java will call the getRandomNumber() method and compare the number it returns with zero, generating a boolean value. When it comes time to assign the boolean value to the variable num, however, Java will choke because num is an int, and you cannot assign a boolean value to an int.

Back to Top

Intentional & Necessary Bounds

To handle this problem, you need to add an additional item to your loop-building toolkit--you must learn to differentiate between intentional and necessary bounds. Here's the difference.

Suppose you want to search the String s, for the character c, and return the position where the value is found. Using a simple sentinel loop you could write:

This bounds, ch != c, is your intentional bounds. It is the sentinel value that will end your loop if all goes well. You can't just assume that all will go well, however. It is possible that:

1. The character c might not occur in the String s.
2. The String s may have no characters.

In this example, we can handle the first necessary bounds by changing the loop condition like this:

Adding necessary bounds to a loop condition means that the loop can end for two [or more] reasons, not just one. When you write the loop postcondition statements, you have to take this into account. 

For instance, after this loop terminates, you can determine whether the character c was found by testing ch, to see if it is equal to c. If ch == c, then the character c was found in the String s.

Back to Top

Bottom-Testing

In addition to the for and while loops, Java also has a loop that performs it's boolean test after the loop body, instead of before. This loop, the do-while loop, illustrated here [click image to enlarge], will always execute the statements inside its body at least once.

The body of the do-while loop appears between the keywords do [which precedes the loop body] and while. Like all loops, the body of the do-while loop can be a single statement, ending with a semicolon, or it can be a compound statement enclosed in braces. As with the other loops, you'll have a more fulfilling life if you train yourself to always use a compound [brace-delimited] loop body.

The do-while loop's boolean condition follows the while keyword. As with all selection and iteration statements in Java, the boolean condition must be enclosed in parentheses, which are part of the statement syntax. In the do-while loop, the boolean condition is followed by a semicolon. [Unlike the while loop, where following the condition with a semicolon can lead to subtle, hard to find bugs.]

The do-while loop is often employed by beginning programmers, because, for some reason, it seems more natural. If you find yourself in this situation, however, you should think twice. 99% of the time, a for loop or a while loop can be employed to better effect than using a do-while. In fact, except for salting your food, which should always be done before tasting, I can't think of a single situation where a test-at-the-bottom strategy is superior to "looking before you leap."

Something to Talk About

(In real life, you'd probably do this with an if statement bracketing the loop, but I'd like you to think about how to do it by adding a necessary bounds.)

Please continue to the next section of this lesson.

Back to Top