This loop fills an array with zeroes:

for (int i = 0; i < values.length; i++)
{
   values[i] = 0;
}

Here, we fill an array list with squares (0, 1, 4, 9, 16, . . .). Note that the element with index 0 contains 0², the element with index 1 contains 1², and so on.

for (int i = 0; i < values.size(); i++)
{
   values.set(i, i * i);
}

To compute the sum of all elements, simply keep a running total.

double total = 0;
for (double element : values)
{
   total = total + element;
}

To obtain the average, divide by the number of elements:

double average = total / values.size(); // For an array list

Be sure to check that the size is not zero.

Suppose you want to find how many accounts of a certain type you have. Then you must go through the entire collection and increment a counter each time you find a match. Here we count the number of accounts whose balance is at least as much as a given threshold:

public class Bank
{
   private ArrayList<BankAccount> accounts;

   public int count(double atLeast)
   {
      int matches = 0;
      for (BankAccount account : accounts)
      {
         if (account.getBalance() >= atLeast) matches++; // Found a match
      }
      return matches;
   }
   ...
}

Suppose you want to find the account with the largest balance in the bank. Keep a candidate for the maximum. If you find an element with a larger value, then replace the candidate with that value. When you have reached the end of the sequence, you have found the maximum.

There is just one problem. When you visit the starting element, you don't yet have a candidate for the maximum. One way to overcome that is to set the candidate to the starting element and make the first comparison with the next element.

BankAccount largestYet = accounts.get(0);
for (int i = 1; i < accounts.size(); i++)
{
   BankAccount a = accounts.get(i);
   if (a.getBalance() > largestYet.getBalance())
      largestYet = a;
}
return largestYet;

Here we use an explicit for loop because the loop no longer visits all elements—it skips the starting element.

Of course, this approach works only if there is at least one element. It doesn't make a lot of sense to ask for the largest element of an empty collection. We can return null in that case:

if (accounts.size() == 0) return null;
BankAccount largestYet = accounts.get(0);
...

See Exercises R7.5 and R7.6 for slight modifications to this algorithm.

To compute the minimum of a data set, keep a candidate for the minimum and replace it whenever you encounter a smaller value. At the end of the sequence, you have found the minimum.

Suppose you want to know whether there is a bank account with a particular account number in your bank. Simply inspect each element until you find a match or reach the end of the sequence. Note that the loop might fail to find an answer, namely if none of the accounts match. This search process is called a linear search.

public class Bank
{
    ...
   public BankAccount find(int accountNumber)
   {
      for (BankAccount account : accounts)
      {
         if (account.getAccountNumber() == accountNumber) // Found a match
            return account;
      }
      return null; // No match in the entire array list
   }
   ...
}

Note that the method returns null if no match is found.

You often need to locate the position of an element so that you can replace or remove it. Use a variation of the linear search algorithm, but remember the position instead of the matching element. Here we locate the position of the first element that is larger than 100.

int pos = 0;
boolean found = false;
while (pos < values.size() && !found)
{
   if (values.get(pos) > 100)
   {
      found = true;
   }
   else
   {
      pos++;
   }
}
if (found) { System.out.println("Position: " + pos); }
else { System.out.println("Not found"); }

Removing an element from an array list is very easy—simply use the remove method. With an array, you have to work harder.

Suppose you want to remove the element with index pos from the array values. First off, you need to keep a companion variable for tracking the number of elements in the array, as explained in Section 7.5.

If the elements in the array are not in any particular order, simply overwrite the element to be removed with the last element of the array, then decrement the variable tracking the size of the array. (See Figure 9.)

values[pos] = values[valuesSize - 1];
valuesSize--;

The situation is more complex if the order of the elements matters. Then you must move all elements following the element to be removed to a lower index, and then decrement the variable holding the size of the array. (See Figure 10.)

Figure 7.9. Removing an Element in an Unordered Array

Figure 7.10. Removing an Element in an Ordered Array

for (int i = pos; i < valuesSize - 1; i++)
{
   values[i] = values[i + 1];
}
valuesSize--;

To insert an element into an array list, simply use the add method.

In this section, you will see how to insert an element into an array. Note that you need a companion variable for tracking the array size, as explained in Section 7.5. If the order of the elements does not matter, you can simply insert new elements at the end, incrementing the variable tracking the size.

if (valuesSize < values.length)
{
   values[valuesSize] = newElement;
   valuesSize++;
}

It is more work to insert an element at a particular position in the middle of an array. First, move all elements above the insertion location to a higher index. Then insert the new element.

Note the order of the movement: When you remove an element, you first move the next element down to a lower index, then the one after that, until you finally get to the end of the array. When you insert an element, you start at the end of the array, move that element to a higher index, then move the one before that, and so on until you finally get to the insertion location (see Figure 12).

if (valuesSize < values.length)
{
   for (int i = valuesSize; i > pos; i--)
   {
      values[i] = values[i - 1];
   }
   values[pos] = newElement;
   valuesSize++;
}

Figure 7.11. Inserting an Element in an Unordered Array

Figure 7.12. Inserting an Element in an Ordered Array

Array variables work just like object variables—they hold a reference to the actual array. If you copy the reference, you get another reference to the same array (see Figure 13):

double[] values = new double[6];
. . . // Fill array
double[] prices = values;

If you want to make a true copy of an array, call the Arrays.copyOf method.

double[] prices = Arrays.copyOf(values, values.length);

Another use for Arrays.copyOf is to grow an array that has run out of space. The following statement has the effect of doubling the length of an array:

values = Arrays.copyOf(values, 2 * values.length);

See Figure 14.

For example, here is how you can read an arbitrarily long sequence numbers into an array, without running out of space:

int valuesSize = 0;
while (in.hasNextDouble())
{
   if (valuesSize == values.length)
      values = Arrays.copyOf(values, 2 * values.length);
   values[valuesSize] = in.nextDouble();
   valuesSize++;
}

Figure 7.13. Copying an Array Reference vs. Copying an Array

Figure 7.14. Growing an Array

When you display the elements of an array or array list, you usually want to separate them, often with commas or vertical lines, like this:

Ann | Bob | Cindy

Note that there is one fewer separator than there are elements. Print the separator before each element except the initial one (with index 0):

for (int i = 0; i < names.size(); i++)
{
   if (i > 0)
   {
      System.out.print(" | ");
   }
   System.out.print(names.get(i));
}

The following sample program implements a Bank class that stores an array list of bank accounts. The methods of the Bank class use some of the algorithms that we have discussed in this section.

ch07/bank/Bank.java

1 import java.util.ArrayList;
2
3 /**
4    This bank contains a collection of bank accounts.
5 */
6 public class Bank
7 {
8    private ArrayList<BankAccount> accounts;
9
10    /**
11       Constructs a bank with no bank accounts.
12    */
13    public Bank()
14    {
15       accounts = new ArrayList<BankAccount>();
16    }
17
18    /**
19       Adds an account to this bank.
20       @param a the account to add
21    */
22    public void addAccount(BankAccount a)
23    {
24        accounts.add(a);
25    }
26
27    /**
28       Gets the sum of the balances of all accounts in this bank.
29       @return the sum of the balances
30    */
31    public double getTotalBalance()
32    {
33       double total = 0;
34       for (BankAccount a : accounts)
35       {
36           total = total + a.getBalance();
37       }
38       return total;
39    }
40
41    /**
42       Counts the number of bank accounts whose balance is at
43       least a given value.
44       @param atLeast the balance required to count an account
45       @return the number of accounts having at least the given balance
46    */
47    public int countBalancesAtLeast(double atLeast)
48    {
49       int matches = 0;
50       for (BankAccount a : accounts)
51       {
52         if (a.getBalance() >= atLeast) matches++; // Found a match
53       }
54       return matches;
55    }
56

57    /**
58         Finds a bank account with a given number.
59         @param accountNumber the number to find
60         @return the account with the given number, or null if there
61         is no such account
62    */
63    public BankAccount find(int accountNumber)
64    {
65         for (BankAccount a : accounts)
66         {
67            if (a.getAccountNumber() == accountNumber) // Found a match
68               return a;
69         }
70         return null; // No match in the entire array list
71    }
72
73    /**
74         Gets the bank account with the largest balance.
75         @return the account with the largest balance, or null if the
76         bank has no accounts
77    */
78    public BankAccount getMaximum()
79    {
80         if (accounts.size() == 0) return null;
81         BankAccount largestYet = accounts.get(0);
82         for (int i = 1; i < accounts.size(); i++)
83         {
84            BankAccount a = accounts.get(i);
85            if (a.getBalance() > largestYet.getBalance())
86               largestYet = a;
87         }
88         return largestYet;
89    }
90 }

ch07/bank/BankTester.java

1 /**
2    This program tests the Bank class.
3 */
4 public class BankTester
5 {
6    public static void main(String[] args)
7    {
8        Bank firstBankOfJava = new Bank();
9        firstBankOfJava.addAccount(new BankAccount(1001, 20000));
10        firstBankOfJava.addAccount(new BankAccount(1015, 10000));
11        firstBankOfJava.addAccount(new BankAccount(1729, 15000));
12
13        double threshold = 15000;
14        int count = firstBankOfJava.countBalancesAtLeast(threshold);
15        System.out.println("Count: " + count);
16        System.out.println("Expected: 2");
17
18        int accountNumber = 1015;
19        BankAccount account = firstBankOfJava.find(accountNumber);
20        if (account == null)
21          System.out.println("No matching account");

22        else
23           System.out.println("Balance of matching account: "
24              + account.getBalance());
25        System.out.println("Expected: 10000");
26
27        BankAccount max = firstBankOfJava.getMaximum();
28        System.out.println("Account with largest balance: "
29              + max.getAccountNumber());
30        System.out.println("Expected: 1001");
31    }
32 }

Program Run

Count: 2
Expected: 2
Balance of matching account: 10000.0
Expected: 10000
Account with largest balance: 1001
Expected: 1001

13. Would it be possible to use a "for each" loop in the getMaximum method?

14. When printing separators, we skipped the separator before the initial element. Rewrite the loop so that the separator is printed after each element, except for the last element.

15. The following replacement has been suggested for the algorithm in Section 7.6.10.

System.out.print(names.get(0));
for (int i = 1; i < names.size(); i++) System.out.print(" | " + names.get(i));

What is problematic about this suggestion?

Arrays.toString(values)

[32, 54, 67.5, 29, 35, 47.5]

System.out.println("values=" + Arrays.toString(values));

System.out.println(names); // Prints [Ann, Bob, Cindy]

8 7 8.5 9.5 7 5 10

Worked Example 7.1:Rolling the Dice

This Worked Example shows how to analyze a set of die tosses to see whether the die is "fair".

Use arrays for collecting values.

Use array lists for managing collections whose size can change.

Use wrapper classes when working with array lists of numbers.

Use the enhanced for loop to visit all elements of a collection.

Work with arrays that are partially filled.

Be able to use common array algorithms.

Describe the process of regression testing.

Use two-dimensional arrays for data that is arranged in rows and columns.

java.lang.Boolean                           java.util.ArrayList<E>
   booleanValue                                add
java.lang.Double                               get
   doubleValue                                 remove
java.lang.Integer                              set
    intValue                                   size
java.util.Arrays
   copyOf
   toString

R7.1 What is an index? What are the bounds of an array or array list? What is a bounds error?

R7.2 Write a program that contains a bounds error. Run the program. What happens on your computer? How does the error message help you locate the error?

R7.3 Write Java code for a loop that simultaneously computes the maximum and minimum values of an array list. Use an array list of accounts as an example.

R7.4 Write a loop that reads 10 strings and inserts them into an array list. Write a second loop that prints out the strings in the opposite order from which they were entered.

R7.5 Consider the algorithm that we used for determining the maximum value in an array list. We set largestYet to the starting element, which meant that we were no longer able to use the "for each" loop. An alternate approach is to initialize largestYet with null, then loop through all elements. Of course, inside the loop you need to test whether largestYet is still null. Modify the loop that finds the bank account with the largest balance, using this technique. Is this approach more or less efficient than the one used in the text?

R7.6 Consider another variation of the algorithm for determining the maximum value. Here, we compute the maximum value of an array of numbers.

double max = 0; // Contains an error!
for (double element : values)
{
   if (element > max) max = element;
}

However, this approach contains a subtle error. What is the error, and how can you fix it?

R7.7 For each of the following sets of values, write code that fills an array a with the values.

Use a loop when appropriate.

R7.8 Write a loop that fills an array a with 10 random numbers between 1 and 100. Write code (using one or more loops) to fill a with 10 different random numbers between 1 and 100.

R7.9 What is wrong with the following loop?

double[] values = new double[10];
for (int i = 1; i <= 10; i++) values[i] = i * i;

Explain two ways of fixing the error.

R7.10 Write a program that constructs an array of 20 integers and fills the first ten elements with the numbers 1, 4, 9, . . ., 100. Compile it and launch the debugger. After the array has been filled with three numbers, inspect it. What are the contents of the elements in the array beyond those that you filled?

R7.11 Rewrite the following loops without using the "for each" construct. Here, values has type double.

R7.12 Rewrite the following loops, using the "for each" construct. Here, values has type double.

R7.13 What is wrong with these statements for printing an array list with separators?

System.out.print(values.get(0));
for (int i = 1; i < values.size(); i++)
{
   System.out.print(", " + values.get(i));
}

R7.14 When finding the position of a match in Section 7.6.6, we used a while loop, not a for loop. What is wrong with using this loop instead?

for (pos = 0; pos < values.size() && !found; pos++)
{
   if (values.get(pos) > 100)
   {
      found = true;
   }
}

R7.15 When inserting an element into an array in Section 7.6.8, we moved the elements with larger index values, starting at the end of the array. Why is it wrong to start at the insertion location, like this?

for (int i = pos; i < size - 1; i++)
{
   values[i + 1] = values[i];
}

R7.16 In Section 7.6.9, we doubled the length of the array when growing it. Why didn't we just increase the size by one element?

R7.17 What are parallel arrays? Why are parallel arrays indications of poor programming? How can they be avoided?

R7.18 True or false?

R7.19 Define the terms regression testing and test suite.

R7.20 What is the debugging phenomenon known as cycling? What can you do to avoid it?

P7.1 Implement a class Purse. A purse contains a collection of coins. For simplicity, we will only store the coin names in an ArrayList<String>. (We will discuss a better representation in Chapter 8.) Supply a method

void addCoin(String coinName)

Add a method toString to the Purse class that prints the coins in the purse in the format

Purse[Quarter,Dime,Nickel,Dime]

P7.2 Write a method reverse that reverses the sequence of coins in a purse. Use the toString method of the preceding assignment to test your code. For example, if reverse is called with a purse

Purse[Quarter,Dime,Nickel,Dime]

then the purse is changed to

Purse[Dime,Nickel,Dime,Quarter]

P7.3 Add a method to the Purse class

public void transfer(Purse other)

that transfers the contents of one purse to another. For example, if a is

Purse[Quarter,Dime,Nickel,Dime]

and b is

Purse[Dime,Nickel]

then after the call a.transfer(b), a is

Purse[Quarter,Dime,Nickel,Dime,Dime,Nickel]

and b is empty.

P7.4 Write a method for the Purse class

public boolean sameContents(Purse other)

that checks whether the other purse has the same coins in the same order.

P7.5 Write a method for the Purse class

public boolean sameCoins(Purse other)

that checks whether the other purse has the same coins, perhaps in a different order. For example, the purses

Purse[Quarter,Dime,Nickel,Dime]

and

Purse[Nickel,Dime,Dime,Quarter]

should be considered equal.

You will probably need one or more helper methods.

P7.6 A Polygon is a closed curve made up from line segments that join the polygon's corner points. Implement a class Polygon with methods

public double perimeter()

and

public double area()

that compute the circumference and area of a polygon. To compute the perimeter, compute the distance between adjacent points, and total up the distances. The area of a polygon with corners (x₀, y₀), . . ., (x_n−1, y_n−1) is

As test cases, compute the perimeter and area of a rectangle and of a regular hexagon. Note: You need not draw the polygon –– that is done in Exercise P7.18.

P7.7 Write a program that reads a sequence of integers into an array and that computes the alternating sum of all elements in the array. For example, if the program is executed with the input data

then it computes

P7.8 Write a program that produces random permutations of the numbers 1 to 10. To generate a random permutation, you need to fill an array with the numbers 1 to 10 so that no two entries of the array have the same contents. You could do it by brute force, by calling Random.nextInt until it produces a value that is not yet in the array. Instead, you should implement a smart method. Make a second array and fill it with the numbers 1 to 10. Then pick one of those at random, remove it, and append it to the permutation array. Repeat 10 times. Implement a class PermutationGenerator with a method

int[] nextPermutation

P7.9 A run is a sequence of adjacent repeated values. Write a program that generates a sequence of 20 random die tosses and that prints the die values, marking the runs by including them in parentheses, like this:

1 2 (5 5) 3 1 2 4 3 (2 2 2 2) 3 6 (5 5) 6 3 1

Use the following pseudocode:

Set a boolean variable inRun to false.
For each valid index i in the array list
   If inRun
      If values[i] is different from the preceding value
         Print )
         inRun = false
   Else
      If values[i] is the same as the following value
         Print (
         inRun = true
   Print values[i]
If inRun, print )

P7.10 Write a program that generates a sequence of 20 random die tosses and that prints the die values, marking only the longest run, like this:

1 2 5 5 3 1 2 4 3 (2 2 2 2) 3 6 5 5 6 3 1

If there is more than one run of maximum length, mark the first one.

P7.11 It is a well-researched fact that men in a restroom generally prefer to maximize their distance from already occupied stalls, by occupying the middle of the longest sequence of unoccupied places.

For example, consider the situation where ten stalls are empty.

_ _ _ _ _ _ _ _ _ _

The first visitor will occupy a middle position:

_ _ _ _ _ X _ _ _ _

The next visitor will be in the middle of the empty area at the left.

_ _ X _ _ X _ _ _ _

Write a program that reads the number of stalls and then prints out diagrams in the format given above when the stalls become filled, one at a time. Hint: Use an array of boolean values to indicate whether a stall is occupied.

P7.12 In this assignment, you will model the game of Bulgarian Solitaire. The game starts with 45 cards. (They need not be playing cards. Unmarked index cards work just as well.) Randomly divide them into some number of piles of random size. For example, you might start with piles of size 20, 5, 1, 9, and 10. In each round, you take one card from each pile, forming a new pile with these cards. For example, the sample starting configuration would be transformed into piles of size 19, 4, 8, 10, and 5. The solitaire is over when the piles have size 1, 2, 3, 4, 5, 6, 7, 8, and 9, in some order. (It can be shown that you always end up with such a configuration.)

In your program, produce a random starting configuration and print it. Then keep applying the solitaire step and print the result. Stop when the solitaire final configu-ration is reached.

P7.13 Add a method getWinner to the TicTacToe class of Section 7.8. It should return "x" or "o" to indicate a winner, or " " if there is no winner yet. Recall that a winning position has three matching marks in a row, column, or diagonal.

P7.14 Write an application that plays tic-tac-toe. Your program should draw the game board, change players after every successful move, and pronounce the winner.

P7.15 Magic squares. An n × n matrix that is filled with the numbers 1, 2, 3, . . ., n² is a magic square if the sum of the elements in each row, in each column, and in the two diagonals is the same value. For example,

Write a program that reads in n² values from the keyboard and tests whether they form a magic square when arranged as a square matrix. You need to test three features:

If the size of the input is a square, test whether all numbers between 1 and n² are present. Then compute the row, column, and diagonal sums. Implement a class Square with methods

public void add(int i)
public boolean isMagic()

P7.16 Implement the following algorithm to construct magic n-by-n² squares; it works only if n is odd. Place a 1 in the middle of the bottom row. After k has been placed in the (i, j) square, place k + 1 into the square to the right and down, wrapping around the borders. However, if the square to the right and down has already been filled, or if you are in the lower-right corner, then you must move to the square straight up instead. Here is the 5 × 5 square that you get if you follow this method:

Write a program whose input is the number n and whose output is the magic square of order n if n is odd. Implement a class MagicSquare with a constructor that constructs the square and a toString method that returns a representation of the square.

P7.17 Implement a class Cloud that contains an array list of Point2D.Double objects. Support methods

public void add(Point2D.Double aPoint)
public void draw(Graphics2D g2)

Draw each point as a tiny circle.

Write a graphical application that draws a cloud of 100 random points.

P7.18 Implement a class Polygon that contains an array list of Point2D.Double objects. Support methods

public void add(Point2D.Double aPoint)
public void draw(Graphics2D g2)

Draw the polygon by joining adjacent points with a line, and then closing it up by joining the end and start points.

Write a graphical application that draws a square and a pentagon using two Polygon objects.

P7.19 Write a class Chart with methods

public void add(int value)
public void draw(Graphics2D g2)

that displays a stick chart of the added values, like this:

You may assume that the values are pixel positions.

P7.20 Write a class BarChart with methods

public void add(double value)
public void draw(Graphics2D g2)

that displays a chart of the added values. You may assume that all added values are positive. Stretch the bars so that they fill the entire area of the screen. You must figure out the maximum of the values, and then scale each bar.

P7.21 Improve the BarChart class of Exercise P7.20 to work correctly when the data contains negative values.

P7.22 Write a class PieChart with methods

public void add(double value)
public void draw(Graphics2D g2)

that displays a pie chart of the added values. You may assume that all data values are positive.

Project 7.1 Poker Simulator. In this assignment, you will implement a simulation of a popular casino game usually called video poker. The card deck contains 52 cards, 13 of each suit. At the beginning of the game, the deck is shuffled. You need to devise a fair method for shuffling. (It does not have to be efficient.) Then the top five cards of the deck are presented to the player. The player can reject none, some, or all of the cards. The rejected cards are replaced from the top of the deck. Now the hand is scored. Your program should pronounce it to be one of the following:

If you are so inclined, you can implement a wager. The player pays a JavaDollar for each game, and wins according to the following payout chart:

Project 7.2 The Game of Life is a well-known mathematical game that gives rise to amazingly complex behavior, although it can be specified by a few simple rules. (It is not actually a game in the traditional sense, with players competing for a win.) Here are the rules. The game is played on a rectangular board. Each square can be either empty or occupied. At the beginning, you can specify empty and occupied cells in some way; then the game runs automatically. In each generation, the next generation is computed. A new cell is born on an empty square if it is surrounded by exactly three occupied neighbor cells. A cell dies of overcrowding if it is surrounded by four or more neighbors, and it dies of loneliness if it is surrounded by zero or one neighbor. A neighbor is an occupant of an adjacent square to the left, right, top, or bottom or in a diagonal direction. Figure 16 shows a cell and its neighbor cells.

Many configurations show interesting behavior when subjected to these rules. Figure 17 shows a glider, observed over five generations. Note how it moves. After four generations, it is transformed into the identical shape, but located one square to the right and below.

One of the more amazing configurations is the glider gun: a complex collection of cells that, after 30 moves, turns back into itself and a glider (see Figure 18).

Program the game to eliminate the drudgery of computing successive generations by hand. Use a two-dimensional array to store the rectangular configuration. Write a program that shows successive generations of the game. You may get extra credit if you implement a graphical application that allows the user to add or remove cells by clicking with the mouse.

Figure 7.16. Neighborhood of a Cell

Figure 7.17. Glider

Figure 7.18. Glider Gun