Loops & Arrays

Oftentimes we run into situations where we would like to repeat the same computation multiple times. As an example, consider a program which computes the power of one number raised to another. We know that 3^8 is equivalent to 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3. This would be easy enough to hard code¹. We could write the following Java program:

1: public class Pow{
2:     public static void main(String[] args){
3:         int val = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3;
4:         System.out.printf("3^8 = %d\n", val);
5:     }
6: }

And it works well enough, printing the expected 3^8 = 6561. But what if 3 and 8 weren't constant values, but variables? If I replace 3 with x:

1: public class Pow{
2:     public static void main(String[] args){
3:         int x = 3;
4:         int y = 10;
5:         int val = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3;
6:         System.out.printf("%d^%d = %d\n", x, y, val);
7:     }
8: }

If we run the above, we don't get the expected 3^10 = 59049, but 3^10 = 6561! It's clear that because Line 5 does not adapt to the fact that the target power has changed there can be no alteration in the computational task. One way we can fix this is with looping.

There are three looping constructs provided by the Java programming language, two of which are slight variatios on the foundational while loop. The syntax of a while loop is as follows:

1: while(condition)
2:   block; // Do this

Pretty simple! While a certain condition is met, i.e. the expression resolves to true, the instructions in the block will be executed. Once the instructions in the block have been exhausted the condition is checked again. If it is met the instructions start over (hence the "loop"); if the condition is not met the next set of instructions outside of the loop will be executed.

Here's how we can modify the power example to work with a while loop:

 1: public class Pow{
 2:     public static void main(String[] args){
 3:         int x = 3;       // Base
 4:         int y = 10;      // Target power
 5:         int pow = 1;     // Starting accumulator value
 6:         int i = 0;       // Iterator
 7:         while(i < y){    // Conditional check
 8:             pow = pow * x; // Computation
 9:             i = i + 1;     // Incrementing i to eventually satisfy looping condition
10:         }
11:         System.out.printf("%d^%d = %d\n", x, y, pow);
12:     }
13: }

There's a lot going on here. First, you'll notice there are two more variables: pow and i. pow is an accumulator which stores the partial result of each computational step needed to get the final power value. i acts as a tally that keeps track of how many loops have been performed. Additionally, you can see that there's some new logic: a conditional operator i < y and a code block. The conditional is used to limit the number of loops performed (more on this later), and the code block is for defining a set of computations to be performed each loop. Here, the code block is multiplying the pow accumulator with the base x and incrementing the i loop tally. We can trace the value at the end of every loop for each variable in a table to keep track of what's happening:

After the 10th loop completes the conditional is checked on final time. Since i is now equal to 10 the expression i < 10 resolves to false and control is transferred to the first block outside of the loop, which is the print function call.

The last looping structure provided by Java is likely also it's most famous: the for loop. The syntax for the for loop is as follows:

1: for(expr1 ; expr2 ; expr3)
2:   block; // Do something

expr1 is the declaration expression. It is where you can define or set a variable at the entrance of the for loop. expr2 is the conditional expression. It is where you can place the conditional check that will be used to determine if another loop will be completed. expr3 is the increment expression. It is used for performing an additional operation at the end of the loop that is not included in the block body. expr1, expr2, and expr3 are all optional.

When expr2 is not present it will be treated as a true value. This means that for(;;) is equivalent to a while(true) statement.

Here is an example of the power program with a for loop:

 1: public class Pow{
 2:     public static void main(String[] args){
 3:         int x = 3;                          // Base
 4:         int y = 10;                         // Target power
 5:         int pow = 1;                        // Starting accumulator value
 6:         for(int i = 0; i < y; i = i + 1){ // Declaration, conditional check, and increment expression
 7:             pow = pow * x;                // Computation
 8:         }
 9:         System.out.printf("%d^%d = %d\n", x, y, pow);
10:     }
11: }

Both Listing 4 and Listing 11 are functionally equivalent². The obvious change is that the loop tallying variable, i, has been declared in expr1 and is incremented in expr3. Everything else is identical.

Many people prefer to write for loops over while loops due to convenience. From the compiler's perspective, it often does not matter.

Additions like the for loop and the do while loop can be classified as syntactic sugar. They do not provide additional functionality for the language, but they provide stylisitic benefits.

Loops can be nested within one another. For example, if I wanted to print out a 4x3 grid of asterixes I could write:

 1: public class NestedLoop{
 2:     public static void main(String[] args){
 3:         for(int i = 0; i < 4; i++){
 4:             for(int j = 0; j < 3; j++){
 5:                 System.out.printf("*");
 6:             }
 7:             System.out.printf("\n");
 8:         }
 9:     }
10: }

There are many situations where nested for loops are desirable, particularly with complex data structures.

We can use the break statement that we learned about with the switch statement. break will immediately transfer control out of the loop to the next block available as if the condition failed. If we did not want our power function to iterate anymore if pow was greater than 100:

 1: public class Pow{
 2:     public static void main(String[] args){
 3:         int x = 3;          // Base
 4:         int y = 10;         // Target power
 5:         int pow = 1;        // Starting accumulator value
 6:         int i = 0;          // Iterator
 7:         while(i < y){       // Conditional check
 8:             pow = pow * x;  // Computation
 9:             if(pow > 100)
10:                 break;      // Exists the loop
11:             i = i + 1;      // Incrementing i to eventually satisfy looping condition
12:         }
13:         System.out.printf("%d^%d = %d\n", x, y, pow);
14:     }
15: }

I leave it as an exercise to you to see what happens when the above is ran.

Similarly to the break keyword, the continue keyword alters the control flow of a loop. When a continue is reached control flow will be transferred to the "end" of the loop. For a while loop that means the conditional will immediately be rechecked. For a for loop that means the increment expression will be performed then the conditional will be checked. Here is a for loop that sums up all even numbers from 1 to 100:

 1: public class ContinueLoop{
 2:     public static void main(String[] args){
 3:         int sum = 0;
 4:         for(int i = 0; i < 100; i++){
 5:             if(i % 2 == 1)
 6:                 continue;
 7:             sum = sum + i;
 8:         }
 9:         System.out.printf("sum = %d\n", pow);
10:     }
11: }

Arrays refer to a special sort of type which represent contiguosly allocated nonempty values. Arrays have a base, or element, type associated with them. For example, we can define an integer array, arr, with ten elements using the following syntax: int arr[] = new int[10]. Unlike C, arrays are guaranteed to have set default values. We do also have the option to set array values as well. Let's have a look:

 1: public class UninitArray{
 2:     public static void main(String[] args){
 3:         int arr[] = new int[5];                  // Declaring an int array of 5 elements
 4:         for(int i = 0; i < 5; i++)
 5:               System.out.printf("%d\n", arr[i]); // The [] are used for selecting an element
 6:           int arr_z[] = new int[]{1,2,3,4,5};    // Declaring a new array with initialized values
 7:           for(int i = 0; i < 5; i++)
 8:               System.out.printf("%d\n", arr_z[i]);
 9:     }
10: }

And after we compile and run the above:

 1: josephraskind@stargazer:/tmp/arrays$ javac UninitArray.java; java UninitArray
 2: 0
 3: 0
 4: 0
 5: 0
 6: 0
 7: 1
 8: 2
 9: 3
10: 4
11: 5

Lines 2-6 print out the elements of the unitialized, default-value array. Lines 7-11 print out the elements of the initialized array.

Arrays are contiguous in memory. This means that there is an entire block of memory reserved for the elements of that array side-by-side. When I write int x[] = new int[5], that means that on my machine 20 bytes are reserved for the array x (5 4 byte ints). We can see this in code:

 1: import sun.misc.Unsafe;
 2: import java.lang.reflect.Field;
 3: 
 4: public class ContiguousArray {
 5:     public static void main(String[] args) throws Exception {
 6:         Unsafe unsafe = getUnsafe();
 7: 
 8:         int[] arr = {1, 2, 3, 4, 5};
 9: 
10:         long scale = unsafe.arrayIndexScale(int[].class);
11:         long base  = unsafe.arrayBaseOffset(int[].class); // Objects have header information
12: 
13:         // Get the actual base address of the arr instance
14:         Object[] holder = new Object[]{arr};
15:         long arrAddress = unsafe.getLong(arr, unsafe.arrayBaseOffset(Object[].class));
16: 
17:         System.out.println("Element size (bytes): " + scale);
18:         System.out.println("Array size (bytes):   " + (scale * arr.length));
19:         System.out.println();
20: 
21:         for (int i = 0; i < arr.length; i++) {
22:             long address = arrAddress + base + (scale * i);
23:             System.out.printf("address 0x%x: %d%n", address, arr[i]);
24:         }
25:     }
26: 
27:     private static Unsafe getUnsafe() throws Exception {
28:         Field f = Unsafe.class.getDeclaredField("theUnsafe");
29:         f.setAccessible(true);
30:         return (Unsafe) f.get(null);
31:     }
32: }

After compiling and running the above:

1: Element size (bytes): 4
2: Array size (bytes):   20
3: 
4: address 0x200000011: 1
5: address 0x200000015: 2
6: address 0x200000019: 3
7: address 0x20000001d: 4
8: address 0x200000021: 5

You'll notice that every address is 4 spots higher than the last. Again, this is because each element is an int, and in Java an int is always 4 bytes.

Java provides another type of For Loop which the documentation calls an "enhanced for statement", but is colloquially referred to as a "For-Each Loop", that iterates over every element in a provided Array or Iterable object. For the time being, we'll ignore the latter and focus on the former. Given an array of five elements, I can use an enhanced for loop like so:

1: public class EnhancedFor{
2:     public static void main(String[] args){
3:           int arr[] = new int[]{1,2,3,4,5};
4:           for(int i: arr)
5:               System.out.printf("%d\n", i);
6:     }
7: }

Running and compiling we get:

josephraskind@stargazer:/tmp/arrays$ java EnhancedFor.java 
1
2
3
4
5

How does this work? Looking at the syntax we find:

for(localVariableDeclaration : Expression)
    statement

Where localVariableDeclaration is a variable whose type matches to the Expression on the right hand side of the :. Each loop represents a subsequent element in the Array until all elements have been exhausted. It is similar to the basic Python for loop.

It is best practice to always use an enhanced for loop whenever possible as it presents indexing errors by definition.

1. Rewrite the power program from Listing 4 using a for loop instead of a while loop. Then rewrite it again using a do while loop. Which version do you find most readable and why?

2. The chapter provides a trace table for Listing 4 showing the value of i and pow at the end of each loop. Construct a similar trace table by hand for the following program, then verify by running it:

   int x = 2;
   int y = 8;
   int pow = 1;
   int i = 0;
   while(i < y){
       pow = pow * x;
       i = i + 1;
   }
   

3. Write a for loop that computes the sum of all integers from 1 to 100. Then write the equivalent using a while loop. Verify both produce the same result.
4. The chapter states that for(;;) is equivalent to while(true). Write a Java program using each form that prints "looping…" exactly 5 times using a break statement to exit. Verify both behave identically.
5. Modify the even sum program from Listing 14 to instead sum all odd numbers from 1 to 100 using continue. What change do you need to make to the conditional? Verify your result.
6. The chapter notes that the compiler does not warn about infinite loops. Write a Java program containing an infinite loop as shown in Listing 5, compile it with javac, and confirm no warning is produced. Then use Ctrl+C in the terminal to kill it. What does Ctrl+C do at the OS level?
7. Write a for loop using the break keyword that finds the first integer greater than 1 whose square exceeds 500. Print both the integer and its square.
8. The chapter shows the bytecode output for the while loop in Listing 6. Compile the for loop version of the power program from Listing 11 with javac and inspect the bytecode with javap -c. Compare the output to Listing 6. Are they identical? What does this tell you about the relationship between for and while loops at the bytecode level?

9. Using nested loops as shown in Listing 12, write a Java program that prints the following multiplication table:

   1  2  3  4  5
   2  4  6  8  10
   3  6  9  12 15
   4  8  12 16 20
   5  10 15 20 25
   

10. The chapter states that all three expressions in a for loop are optional, as shown in Listing 10. Write three separate Java programs demonstrating this: one with expr1 omitted, one with expr3 omitted, and one with both omitted. In each case, what change must you make elsewhere to keep the program correct?
11. Declare a 3x4 int matrix as in Listing 19 and initialize it with values 1 through 12 using nested for loops. Then print every element using nested enhanced for loops. Compare the two loop styles—what does the enhanced for loop not give you access to that the regular for loop does?
12. Write a Java program that declares an int array of 10 elements and sets each element to its index multiplied by 2 using a regular for loop. Then use an enhanced for loop to print all elements. Why can you not use an enhanced for loop for the initialization step?
13. The chapter states that Java performs runtime bounds checking on arrays. Write a Java program that deliberately accesses an index beyond the end of an array and record the exception that is thrown. Then write the equivalent in terms of what would happen in C—why is Java's behavior safer? (If you do not have experience with C, then reflect on what might happen.)