Unit 5: Iteration with Loops

5.0. Overview

There are two abilities we need to be able to write programs, and those are handled by two corresponding control structures that we need to write our programs. We need the ability to branch (handled by if-else conditionals), and the ability to iterate (handled by while and for loops).

Up this point we've dealt with two things that have each had their own challenges. The first challenge was developing an understanding of boolean statements: the if statement, the if-else statement, and variations on these, including a switch-style series of alternatives, and nested if-else statements that allow us to drill down through multiple options.

The second challenge was navigating "object-oriented design", and learning to write programs that implemented classes, methods, and testers.

In this unit, we turn our attention to loops. Computers specialize in repetitive operations which can be repeated very quickly, so understanding how to write loops—and how to write loops well—is at the very heart of programming.

Let's get started.

1. while loops, do loops, Debugging
2. for loops
3. Sentinel Values, Common Loop Algorithms
4. Nested Loops
5. Random Numbers, Simulations

5.1. Overview: while loops, do loops, Debugging

There are two major types of techniques for repeating, or iterating, sections of code. The first, and the most powerful, is the while loop.

5.1.1. Intro to Iteration

The if statement has to do with making decisions, and it's the first kind of control structure that we have in Java to alter the flow of our instructions.

The second kind of control structure we're going to have in our toolbox is the loop, which allows us to make our computers repeat sequences of code, many many times, very very fast. Once we have our branching and our looping control structures in place, we are going to be able to write some amazing code!

5.1.2. The while loop

There are basically three types of loops that we're going to work with in Java, although technically, any programming language only needs one. The most fundamental type of loop—the most powerful, the most versatile—is the while loop.

while (<boolean condition>)
{
    <statement;>
    <statement;>
    <statement;>
}

int i = 0;
while (i < 4)
{
    System.out.println(i);
    i++;
}

The while-loop is sometimes called a conditional loop—it continues to repeat as long as a condition evaluates as true.

Here's another example of a conditional loop.

Scanner in = new Scanner(System.in);
System.out.print("Wanna play a game (y/n)?");
String response = in.nextLine();
while (!response.equalsIgnoreCase("n"))
{
    int rand = (int) (Math.random() * 3);
    if (rand == 0)        
    { 
        System.out.println("You're amazing!"); 
    }
    else if (rand == 1)   
    { 
        System.out.println("I think you're awesome."); 
    }
    else                  
    { 
        System.out.println("I know you can do this!"); 
    }
    System.out.print("Wanna play again (y/n)?");
    response = in.nextLine();
}
System.out.println("Goodbye");

5.1.3. Off-by-One Errors

There are a number of important aspects to programming a loop that we have control over. In the example below, for example, we design the loop based on:

• the initial value of i? (0, or 1?)
• the comparison operator (<, or <=?)
• the final value (10000? 10001?)
• the order of the statements in the loop (do I print i first and then increment, or do I increment first and then print?)

These factors all affect the loop's operation.

int i = 0;
while (i < 10000)
{
    System.out.println(i);
    i++;
}

Off-by-one errors typically happen during the first iteration or the last iteration of the loop, so it's important to check the status of variables at those times especially carefully. If you do find that there's a problem with the loop, you're strongly discouraged from just randomly altering your loop parameters. A program that doesn't behave as expected reveals that you don't perfectly understand how it works—better to make the effort to analyze it and make a repair that you understand rather than just changing something and "seeing what happens."

// loopA
int i = 0;
while (i < 11)
{
    i++;
    System.out.println(i);
}

// loopB
int i = 1;
while (i <= 11)
{
    System.out.println(i);
    i++;
}

// loopC
int i = 1;
while (i < 12)
{
    System.out.println(i);
    i++;
}

// loopD
int i = 0;
while (i < 11)
{
    System.out.println(i + 1);
    i++;
}

5.1.4. The Investment class

Continuing with out interest in things financial, take a moment to make sure you understand the Investment class here.

Identify the instance variables, the constructors, the accessor methods, and the mutator methods. Run through the class by hand to make sure you understand how the program works.

/**
 * A class to monitor the growth of an invetment that accumulates
 * interest at a fixed annual rate.
 * 
 * @author Horstmann
 * @version 2005?
 */
public class Investment
{
    private double initialBalance;
    private double balance;
    private int years;

    /**
     * Constructs an Investment object with a given starting balance
     * @param aBalance the starting balance
     * @param aRate the interest rate in percent 
     */
    public Investment(double theInitialBalance)
    {
        initialBalance = theInitialBalance;
    }

    /**
     * Accumulates interest until a target balance is reached
     * @param  targetBalance the desired balance
     */
    public void waitForBalance(double rate, double targetBalance)
    {
        years = 0;
        balance = initialBalance;
        while (balance < targetBalance)
        {
            years++;
            double thisYearsInterest = balance * rate / 100;
            balance += thisYearsInterest;
            System.out.println(balance);
        }
    }
    
    /**
     * Gets the current investment balance
     * @return the current balance
     */
    public double getBalance()
    {
        return balance;
    }
    
    /**
     * Gets number of years investment has accumulated interest
     * @return the number of years since investment started
     */
    public int getYears()
    {
        return years;
    }
}

5.1.5. Using a Debugger

Three things you need to know when using a debugger.

A better strategy, if you're using an IDE, is to use the included Debugger. Here's the basic process, in 3 steps.

1. Set a breakpoint
   In BlueJ, click on the line number of a statement so that a Stop appears at that location. Your program will run normally until you hit that breakpoint, and you can Inspect the state of various variables at that point. When you're ready to continue, click Continue.
   In a complex program, you may wish to set multiple breakpoints to inspect what's happening at various parts of your program.
2. Step
   If you've hit a breakpoint, rather than hitting Continue you can choose to Step through various instructions. This has the effect of executing the instructions in that call/module one at a time, so you can see what's happening to your variables as you go.
   But what if those instructions include method calls?
3. Step into
   Click on Step into to descend into a method call to see what's happening there.

5.1.6. Debugging Strategy

You don't want to use a debugger all the time, every time, to go through a program. That takes too much time. But if you're stuck and can't figure something out, the debugger allows you to follow the flow of your program and quickly find problems.

The best strategy is to set a breakpoint just before where you think your program is blowing up. Run the program, and then Step through statements until you see the failure. Then do it all again, but Step Into the method that you think might be causing you problems. This "divide-and-conquer" strategy should help you nail down your problem pretty quickly.

5.1.7. do loops

A standard while loop checks the condition before doing something, but sometimes you want to do something first, and then check some boolean condition.

do
{
    <statement;>
    <statement;>
    <statement;>
}
while (<boolean expression>);

Example: Get a user's input and then see if it's valid. The loop below will continue asking a user's age until he/she enters an age that is a positive value.

do
{
    System.out.print("Enter your age: ");
    userAge = in.nextInt();
}
while (userAge <= 0);

The do loop can be useful and logical to use in certain situations, but most people seem to prefer writing a standard while loop with a structure that is equivalent to the do loop's operation.

double value;
// *** Conditional One ***
do
{
    System.out.print("Enter a positive number: ");
    value = in.nextDouble();
}
while (value <= 0);
    

// *** Conditional Two ***
                 
System.out.print("Enter a positive number: ");
value = in.nextDouble();
while (value <= 0)
{
    System.out.print("Error: Please enter a positive number: ");
    value = in.nextDouble();
}


// *** Conditional Three ***
   
boolean done = false;
while (!done)
{
    System.out.print("Enter a positive number: ");
    value = in.nextDouble();
    if (value > 0) 
        done = true;
}
       
    
// *** Conditional Four ***
                 
while (true)
{
    System.out.print("Enter a positive number: ");
    value = in.nextDouble();
    if (value > 0) 
        break;
}        
                

5.2. Overview - for loops

Although a conditional loop like the while loop is all that is necessary to write programs, we often need a loop that will count through some series of values. The for loop is another type of loop that is very handy for creating unconditional loops that iterate a value over some known range of values.

5.2.1. The for loop

As we've said, the while loop is sufficient for any looping needs you might have, but there's one type of while loop that is so common, most languages have an additional structure for it: the for loop. If you need to count up or down from some value, to a terminal value, a for loop is what you should probably use.

We've already seen how you can count with a while loop:

// while-loop to count from 0 to 99
int i = 0;
while (i < 100)
{
    System.out.println(i);
    i++;
}

Here's how you'd do the same thing with a for loop:

// for-loop to count from 0 to 99
for (int i = 0; i < 100; i++)
{
    System.out.println(i);
}

Note that if the counting variable i has already been declared, you don't have to declare it in the body of the loop.

int i;
for (i = 0; i < n; i++)
{
    <statement;>
    <statement;>
    <statement;>
}

for (int i = 1; i < n; i++)
{
    <statement;>
    <statement;>
    <statement;>
}

public class MillionAdder
{
    public static void main(String[] args)
    {
        int sum = 0;
        for (int i = 1; i <= 1000000; i++)
            sum = sum + i;
        System.out.println(sum);
    }
}

For really big integers, you'll need to investigate the slow but powerful BigInteger class.

Just as with while loops, you'll need to be careful to avoid off-by-one errors when writing your for loops!

5.2.2. Using loops for different objectives

Up to this point, we've played a bit with the two main types of loops in Java: the while loop, and the for loop.

int vowelCount = 0;
for (int i = 0; i < word.length(); i++)
{
    if (word.substring(i, i+1).equals("a") ||
        word.substring(i, i+1).equals("e") ||
        word.substring(i, i+1).equals("i") ||
        word.substring(i, i+1).equals("o") ||
        word.substring(i, i+1).equals("u"))
    vowelCount++;
}
System.out.println(vowelCount);

5.3. Overview - Sentinel Values, Common Loop Algorithms

We've discussed while loops and for loops, and seen a few simple examples of how they might be used. Let's take a look at some of the ways that loops are commonly used.

5.3.1. Sentinel values

A sentinel keeps watch, and sentinel values are values that are watched for in a loop to find out when the loop should complete.

System.out.print("Enter a value, Q to quit: ");
String input = in.next();  // get the value
while (!input.equals("Q"))
{
   int numericValue = Integer.parseInt(input);
   ...
   System.out.print("Enter another value, Q to quit: ");
   input = in.next();  // get the value
}
System.out.println("Done with the loop!");

5.3.2. The break and continue statements

The idea of checking values in the middle of the loop in the "loop-and-a-half" structure above strikes some people as inelegant, and not the cleanest way to code these situations.

One useful alternative involves a break statement in the middle of the loop:

while (true)
{
    System.out.print("Enter a value, Q to quit: ");
    String input = in.next();  // get the value
    if (input.equalsIgnoreCase("Q"))
        break;      // used to immediately exit a while, for, or do loop
    else
    {
        int numericValue = Integer.parseInt(input);
        ...
    }
}

Our textbook doesn't use break statements this way, but it's a very common strategy for lots of coders, and allowed by Java.

5.3.3. Common Loop Algorithms

As you might expect, loops are used for a lot of different "standard tasks" in program. Here are some of the most common.

5.3.3.1. Keeping a Running Total of Values

We often need to sum up a series of values. A variable called sum here does just that:

Scanner in = new Scanner(System.in);
double sum = 0;
System.out.print("Enter a numeric value ('q' to quit): ");
String value = in.next();
while (!value.equalsIgnoreCase('q'))
{
    sum = sum + Double.parseDouble(value);
    System.out.print("Enter another value ('q' to quit): ");
    value = in.next();
}
System.out.println("The sum of your values: " + sum);

5.3.3.2. Counting Matching Data

Sometimes we need to identify which items in a sequence match a certain requirement—counting vowels, for example:

String greeting = "Hello, World!";
int vowelCount = 0;
for (int i = 0; i < greeting.length(); i++)
{
    if (greeting.substring(i, i+1).equals("a") ||
        greeting.substring(i, i+1).equals("e") ||
        greeting.substring(i, i+1).equals("i") ||
        greeting.substring(i, i+1).equals("o") ||
        greeting.substring(i, i+1).equals("u"))
    {
        vowelCount++;
    }
}
System.out.println("There were " + vowelCount + vowels.");

5.3.3.3. Data Validation / Error-Trapping

Sometimes we need to validate data that the user has entered, or make sure that the user hasn't entered data that will cause our program to crash.

System.out.print("Enter a positive integer: ");
int value = in.nextInt();
while (value < 0)
{
    System.out.print("Error--Please enter a value greater than 0: ");
    value = in.nextInt();
}
System.out.println("You entered the value " + value + ". Thank you!");

5.3.3.4. Finding the Maximum or Minimum in a Series of Values

Being able to find the largest or smallest value in a series turns out to be enormously useful.

Scanner in = new Scanner(System.in);
int maximum = Integer.MIN_VALUE;  # This smallest possible value
System.out.print("Enter a numeric value ('q' to quit): ");
String value = in.next();
while (!value.equalsIgnoreCase('q'))
{
    if (Integer.parseInt(value) > maximum)
        maximum = Integer.parseInt(value);
    System.out.print("Enter another value ('q' to quit): ");
    value = in.next();
}
System.out.println("The largest value was: " + maximum);

5.3.3.5. Modifying a String value

Objects of the String class are immutable—a String cannot be modified. String methods can return a modified version of a String, but the original String itself isn't changed.

String expr = "Hello!";
System.out.println(expr);                 // prints "Hello!"
System.out.println(expr.toUpperCase());   // prints "HELLO!"
System.out.println(expr);                 // prints "Hello!"

Although a String value can't be modified, a String variable can be set to point to a different String. So:

String expr = "Hello!";
System.out.println(expr);                 // prints "Hello!"
expr = expr.toUpperCase());               // changes the value of expr
System.out.println(expr);                 // prints "HELLO!"

So, if you want to modify a string, you need to create a new string with the modifications, and then reset the original String variable to the modified version.

/**
 * This program demonstrates how a program
 * can process Strings.
 */
public class ERemover
{
    /**
     * This static method removes the letter "e" from any
     * expression sent in, and returns the modified result.
     * @param in a String value, potentially with some "e" letters in it
     * @return the same String, with "e" characters removed
     */
    public static String removeE(String in)
    {
        String result = "";
        for (int i = 0; i < in.length(); i++)
        {
            if (!in.substring(i, i+1).equalsIgnoreCase("e"))
                result += in.substring(i, i+1);
        }
        return result;
    }

    /**
     * This main method demonstrates modifying a String variable
     * to point to a different String.
     */
    public static void main(String[] args)
    {
        String original = "Happy Halloween, everybody!";
        System.out.println(original);
        String compressed = removeE(original);
        System.out.println(compressed);
    }
}

5.3.4. Sequential Data Analysis

Take a look at this DataSet class that calculates information about a set of values entered by the user.

/**
   DataSet.java
   Computes the average of a set of data values.
   @author Cay Horstmann
   @version Java Concepts 5th Edition
*/

public class DataSet
{
    private double maximum;
    private int count;
    private double sum;
   
    /**
        Constructs an empty data set.
    */
    public DataSet()
    {
        sum = 0;
        count = 0;
        maximum = 0;
    }

    /**
    Adds a data value to the data set
    @param x a data value
    */
    public void add(double x)
    {
        sum = sum + x;
        if (count == 0 || maximum < x) maximum = x;
        count++;
    }
    
    /**
    Gets the average of the added data.
    @return the average or 0 if no data has been added
    */
    public double getAverage()
    {
        if (count == 0) return 0;
        else return sum / count;
    }
    
    /**
        Gets the largest of the added data.
        @return the maximum or 0 if no data has been added
    */
    public double getMaximum()
    {
        return maximum;
    }
}

Analyzing the code, we can see how it works. Let's see how a runner program might interact with this class, getting input from the user via a Scanner, and using a sentinel value to manage that interaction:

/**
   Compute the average and maximum of a set of
   input values.
*/

import java.util.Scanner;

public class DataAnalyzer
{
   public static void main(String[] args)
   {
        Scanner in = new Scanner(System.in);
        DataSet data = new DataSet();
        
        boolean done = false;
        while(!done)
        {
            System.out.print("Enter value, Q to quit: ");
            String input = in.next();
            if (input.equalsIgnoreCase("Q"))
            {
                done = true;
            }
            else
            {
                double x = Double.parseDouble(input);
                data.add(x);
            }
        }

        System.out.println("Average: " + data.getAverage());
        System.out.println("Maximum: " + data.getMaximum());
   }
}

5.3.5. Finding primes

2
3  
5  
7  
11  
13  
17  
19

// Code from PrimeRunner
PrimeGenerator pGen = new PrimeGenerator(); // constructs new PrimeGenerator
System.out.println(pGen.nextPrime());       // prints out 2
System.out.println(pGen.nextPrime());       // prints out 3
for (int i = 0; i < 5; i++)                 // will run 5 times
{
    System.out.println(pGen.nextPrime());   // prints 5, 7, 11, 13, 17
}

public class PrimeGenerator
{
   // instance variables
   private int candidate;

   /**
    * Constructor for objects of class PrimeGenerator
    */
   public PrimeGenerator()
   {
       // initialise instance variables
       candidate = 1;  // not really, but seeds the method
   }

   /**
    * nextPrime identifies the next prime in the sequence, 
    * and returns it
    * @return    the next prime in the sequence
    */
   public int nextPrime()
   {
       boolean isPrime = false; // seed
       while (!isPrime)
       {
           isPrime = true; // assume positive
           candidate++; // start checking at next value
           for (int i = 2; i <= Math.sqrt(candidate); i++)
           {
               if (candidate % i == 0)
               {
                   isPrime = false;
                   break;
               }
           }
       }
       return candidate;
   }
}

5.4. Overview - Nested Loops

We've had a good chance to look at how we can use loops to quickly work through a series of values.

Often we'll need to use a looping structure as the body of a larger, outer loop. Such loops are said to be nested.

5.4.1. Nested loops

Just as we can nest if-else statements inside other if-else statements to work on multiple levels of a problem, we can nest loops inside other loops.

Pseudocode example: Going through a document word by word

for (each word in sentence)
{
    for (each letter in this word)
    {
        // do something
    }
}

Pseudocode example: finding the total assets of a bank

double sum = 0;
for (each client at bank)
{
    for (each account for this client)
    {
        sum = sum + this account
    }
}

5.4.2. Nested counting loops

One very common type of loop pattern involves using two loops to work through a 2-dimensional grid or table.

Generally:

for (each row in the table)
{
    for (each column in a row)
    {
        // do something
    }
}

/**
 * Boxy class creates a box of a given dimension.
 * 
 * @author Richard White 
 * @version 2013-10-24
 */
public class Boxy
{
    private int dimension;  // instance variable

    /**
     * Constructor for objects of class Boxy
     * @param theDimension the width and height of the box
     */
    public Boxy(int theDimension)
    {
        dimension = theDimension;
    }


    /**
     * printIt method displays a text version of the box
     */
    public void printIt()
    {
        for (int row = 0; row < dimension; row++)
        {
            for (int col = 0; col < dimension; col++)
            {
                System.out.print("[]");
            }
            System.out.println(); // go down to next line
        }
    }
        
    
    /**
     * toString method returns a text version of the box
     * @return a string encoding of the box
     */
    public String toString()
    {
        String theBox = "";
        
        for (int row = 0; row < dimension; row++)
        {
            for (int col = 0; col < dimension; col++)
            {
                theBox += "[]";
            }
            theBox += "\n"; // go down to next line
        }
        return theBox;
    }
}

5.5. Overview - Random numbers, Simulations

We've had a good chance to look at how we can use the two types of loops—conditional (while loops) and unconditional (for loops).

Now let's look at a new type of program that will make good use of what we've learned: models, or simulations.

5.5.1. Random Numbers and Simulators

5.5.2. Getting Random Integers

To get pseudo-random numbers in a Java program, there are two common strategies.

5.5.2.1. The Math.random() method

System.out.println(Math.random());      →      0.341889604189878
System.out.println(Math.random());      →      0.5569208907430896

In many simulations we need to create an integer value within some range of values: 1-6 for a dice roll, for example. We can return any desired range of values by manipulating the result returned by Math.random():

int dieRoll = (int) (Math.random() * 6) + 1;

What's going on here?

1. Math.random() creates a random double between 0 and 0.9999999999999999.
2. That value is multiplied by 6 to yield a double number between 0 and 5.999999999999994.
3. We add 1 to that value to get a double number between 1 and 6.999999999999994.
4. We cast that value as an int to get an integer between 1 and 6 that is stored in the int variable dieRoll.

This strategy for creating integers within a given range is very common.

5.5.2.2. The Random package

The Random package contains a more extensive collection of utilities that allow you to work with random and pseudorandom values. Use of that package is not required for this class, although you'll see it used in examples in our textbook, so it helps to know how to create a Random object.

import java.util.Random;  // The Random package
    
// create a random number generator instance
Random generator = new Random();

// get either a random integer in the range 0 to n-1:
int randNum1 = generator.nextInt(n);

// ... or a random Double in the between 0 (inclusive) and 1 (exclusive)
double randNum2 = generator.nextDouble();

int aDieRoll = generator.nextInt(6) + 1;

5.5.3. Writing a simulation