Start Concurrent: A Gentle Introduction to Concurrent Programming

One problem you might be worrying about is how to display the simulation. In Chapter 15 you’ll learn how to make a graphical user interface (GUI) that can display a grid of cells in black and white and much more interesting things as well. For now, the main tool that we can use for output is still the terminal. The output method we recommend is printing an asterisk ('*') for a living cell and a space (' ') for a dead one. In this way you can easily see the patterns form on the screen and change over time.

The classic terminal isn’t very big. For this reason, we suggest that you set the height of your simulation to 24 rows and the width of your simulation to 80 columns. These dimensions conform to the most ancient terminal sizes. If your terminal screen is much larger, you can change the width and height later to perform a larger simulation. No matter how large the display for the game is, the ideal size of the game. Because our size is so limited, we must deal with the problem of a cell on the boundary. Anything beyond the boundaries should be counted as dead. Thus, a cell right on the edge of the simulation grid can have a maximum of 5 neighbors. A cell in one of the four corners can only have 3 neighbors.

In order to give the appearance of smooth transitions, you need to print out each new generation of cells quickly, and in the same locations as the previous generation. Simply printing one set after another will not achieve this effect unless your terminal screen is exactly 24 rows tall. So, you will need to clear the screen each time. In an effort to be platform independent, Java does not provide an easy way to clear the terminal screen. A quick and simple hack is to simply print out 100 blank lines before printing the next generation. This hack will work as long as your terminal is not significantly more than 100 rows in height. If it is, you’ll need to print a larger number of blank rows.

Finally, you need to wait a short period of time between generations so that the user can see each configuration before it’s cleared away and replaced by the next one. The simplest way to do this is by having your program go to sleep for a short period of time, a tenth of a second as we suggested before. The code to make your program sleep for that amount of time is:

We’ll explain this code in much greater detail in Chapter 13. The key item of importance is the number passed into the sleep() method. This value is the number of milliseconds you want your program to sleep. 100 milliseconds is, of course, one tenth of a second.

In order to simulate the Game of Life, we need to store information, namely the liveness or deadness of cells, in a grid. First, we need to discuss the simpler task of storing data in a list.

Now that we’ve defined these attributes, we can say that an array is a homogeneous, static data structure with random access. An array is homogeneous because it can only hold a list of a single type of data, such as int, double, or String. An array is static because it has a fixed length that is set only when the array is instantiated. An array also has random access because jumping to any element in the array is fast and takes about the same amount of time as jumping to any other.

An array is a list of a specific type of elements that has length n, a length specified when the array is created. Each of the n elements is indexed using a number between 0 and n - 1]. Once again, zero-based counting rears its ugly head. Consider the following list of items: {9, 4, 2, 1, 6, 8, 3}

If this list is stored in an array, the first element, 9, would have index 0, 4 would have index 1, and so on, finishing at 3 with an index of 6, although the total number of items is 7. Not all languages use zero-based counting for array indexes, but many do, including C, C++, and Java. The reason that languages like C originally used zero-based counting for indexes is that the variable corresponding to the array is an address inside the computer’s memory giving the first element in the array. Thus, an index of 0 is 0 times the size of an element added to the starting address, and an index of 5 is 5 times the size of an element added to the starting address. So, zero-based indexes gave a quick way for the program to compute where in memory a given element of an array is.

To create an array, you usually need to create an array variable first. Remember that an array is a homogeneous data structure, meaning that it can only store elements of a single type. When you create an array variable, you have to specify what that type is. To declare an array variable, you use the type it’s going to hold, followed by square brackets ([]), followed by the name of the variable. For example, if you want to create an array called numbers that can hold integers, you would type the following.

If you have some C or C++ programming experience, you might be used to the brackets being on the other side of the variable, like so.

In Java, both declarations are perfectly legal and equivalent. However, the first declaration is preferred from a stylistic perspective. It follows the pattern of using the type (an array of int values in this case) followed by the variable name as the syntax for a declaration.

As we said, arrays are also static data structures, meaning that their length is fixed at the time of their creation. Yet we didn’t specify a length above. This declaration has not yet created an array, just a variable that can point at an array. In the second half of this chapter, we will further discuss this difference between the way an array is created and the way an int or any other variable of primitive type is created. To actually create the array, we need to use another step, involving the keyword new. Here’s how we instantiate an array of int type with 10 elements.

We use the keyword new, followed by the type of element, followed by the number of elements the array can hold in square brackets. This new array is stored into numbers. In other words, the variable numbers is now a name for the array. Commonly, the two steps of declaring and instantiating an array will be combined into one line of code.

It’s always possible to separate the two steps. In some cases, a single variable might be used to point at an array of one particular length, then changed to point at an array of another length, and so on, as below.

Here, the variable numbers starts off pointing at no array. Next, it’s made to point at a new array with 10 elements. Then, it’s made to point at a new array with 100 elements, ignoring the 10 element array. Finally, it’s made to point at an array with 1,000 elements, ignoring the 100 element array. Remember, the arrays themselves are static; their lengths can’t change. The array type variables, however, can point at different arrays with different lengths, provided that they’re still the right type (in this case, arrays of int values).

What values are inside the array when it’s first created? Let’s return to the case where numbers points at a new array with 10 elements. Each of those elements contains the int value 0, as shown below.

Whenever an array is instantiated, each of its n elements is set to some default value. For int, long, short, and byte this value is 0. For double and float, this value is 0.0. For char, this value is '\0', a special unprintable character. For boolean, this value is false. For String or any other reference type, this value is null, a special value that means there’s no object.

It’s also possible to use a list to initialize an array. For example, we can create an array of type double that contains the values 0.5, 1.0, 1.5, 2.0, and 2.5 using the following code.

This line of code is equivalent to using the new keyword to create a double array with 5 elements and then setting each to the values shown.

To use a value in an array, you must index into the array, using the square brackets once again. Returning to the example of the int array numbers with length 10, we can read the value at index 4 from the array and print it out.

Until some other value has been stored there, the value of numbers[4] is 0, and so 0 is all that will be printed out. We can set the value at numbers[4] to 17 as follows.

Then, if we try to print out numbers[4], 17 will be printed. The contents of the numbers array will look like this.

The key thing to understand about indexing into an array is that it gives you an element of the specified type. In other words, numbers[4] is an int variable in every possible sense. You can read its value. You can change its value. You can pass it into a method. It can be used anywhere a normal int can be used, as in the following example.

Executing this code will store 17 into x and 17.0 into y. Then, the product of those two, 289, will be stored into numbers[9]. Remember, in Java, the type on the left and the type on the right of the assignment operator (=) must match, except in cases of automatic casting, like storing an int value into a double variable. Since they have the same type, it makes sense to store an element of an int array like numbers[4] into an int variable like x. However, an array of int values can’t be stored into an int type.

This code will cause a compiler error. What would it mean? You can’t put a list of variables into a single variable. And the converse is true as well.

This code will also cause a compiler error. A single value can’t be stored into a whole list. You would have to specify an index where it can be stored. Furthermore, you must be careful to specify a legal index. No negative index will ever be legal, and neither will an index greater than or equal to the number of elements in the array.

This code will compile correctly. If you remember, we instantiated the array that numbers points at to have 10 elements, numbered 0 through 9. Thus, we are trying to store 99 into the element that is one index after the last legal element. As a result, Java will cause an error called an ArrayIndexOutOfBoundsException to happen, which will crash your program.

One reason to use arrays is to avoid declaring 10 separate variables just to have 10 int values to work with. But once you have the array, you’ll often need an automated way to process it. Any of the three kinds of loops provides a powerful tool for performing operations on an array, but the for loop is an especially good match. Here is an example of a for loop that sets the values in an array to their indexes.

This sample of code shows how easy it is to iterate over every element in an array with a for loop, but it has a flaw in its style. Note that the number 100 is used twice: once in the instantiation of the array and a second time in the termination condition of the for loop. This fragment of code works fine, but if the programmer changes the length of values to be 50 or 500, the bounds of the for loop will also need to change. Furthermore, the length of the array might be determined by user input.

To make the code both more robust and readable, we can use the length field of the values array for the bound of the for loop.

The length field gives the length of the array that values points to. If the programmer wants to instantiate the array with a different length, that’s fine. The length field will always reflect the correct value. Whenever possible, use the length field of arrays in your code. Note that the length field is read-only. If you try to set values.length to a specific value, your code will not compile.

Setting the values in an array is only one possible task you can perform with a loop. Let’s assume that an array of type double named data has been declared, instantiated, and filled with user input. We could sum all its elements using the following code. A more elegant way to do the same summation is discussed in Section 6.9.1.

So far, we’ve only discussed operations on the values in an array. It is important to realize that the order of those values can be equally important. We’re going to create an array of char type named letters, initialized with some values, and then reverse the order of the array.

Of course, we could have printed out the array elements in reverse order without changing their order, but we wanted to reverse them, perhaps because we will need them reversed in the future.

With arrays and loops, we can process a lot of data, but testing programs that process a lot of data can be tedious. Instead of typing data into the terminal, we can read data from a file. In Java, file I/O is a messy process that involves several objects and method calls. We’re going to talk about it in depth in Chapter 20, but for now we can use a quick and easy workaround.

If you create a text file using a simple text editor, you can redirect the file as input to a program. Everything you’ve written in the text file is treated as if it were being typed into the command line by a person. To do so, you type the command using java to run your class file normally, type the < sign, and then type the name of the file you want to use as input. For example, if you have a text file called numbers.txt that you want to use as input to a program stored in Summer.class, you could do so as follows.

Redirecting input this way is not a part of Java. Instead, it’s a feature of the terminal running under your OS. Not all operating systems support input redirection, but virtually every flavor of Linux and Unix do, as well as the Windows command line and the macOS terminal. We could write the program mentioned above and give it the simple task of summing all the numbers it gets as input.

Now, we can type out a file with a list of numbers in it and save it as numbers.txt. To conform with the program we wrote, we should also put the total count of numbers as the first value in the file. You can put each number on a separate line or just leave a space between each one. As long as they are separated by white space, the Scanner object will take care of the rest. You’ll have to type the numbers into the file once, but then you can test your program over and over with the same file.

If you do run the program with the file you’ve created, you’ll notice that the program still prompts you once for the total count of numbers and then prompts you many times to enter the next number. With redirected input, all that text runs together in a bizarre way. All the input is coming from numbers.txt. If you expect a program to read strictly from redirected input, you can design your code a little differently. For one thing, you don’t need to have explicit prompts for the user. For another, you can use a number of special methods from the Scanner class. The Scanner class has a several methods like hasNextInt() and hasNextDouble(). These methods will examine the input and see if there is another legal int or double and return true or false accordingly. If you expect a file to have only a long sequence of int values, you can use hasNextInt() to determine if you’ve reached the end of the file or not. Using hasNextInt(), we can simplify the program and remove the expectation that the first number gives the total count of numbers.

On the other hand, you might be interested in the output of a program. The output could be very long or it might take a lot of time to produce or you might want to store it permanently. For these situations, it is possible to redirect output as well. Instead of printing to the screen, you can send the output to a file of your choosing. The syntax for this operation is just like the syntax for input redirection except that you use the > sign instead of <. To run QuietSummer with input from numbers.txt and output to sum.txt, we could do the following.

java QuietSummer < numbers.txt > sum.txt

You would be free to examine sum.txt at any time with your text editor of choice. When using output redirection, it makes more sense to run QuietSummer than Summer. If we had run Summer, all of that unnecessary output prompting the user to enter numbers would be saved in sum.txt.

When declaring a two-dimensional array, the main difference from a one-dimensional array is an extra pair of brackets. If we wish to declare a two-dimensional array of type int in which we could store values like the table of distances above, we would do so as follows.

As with one-dimensional arrays, it’s legal to put the brackets on the other side of the variable identifier or, even more bizarrely, have a pair on each side.

Once the array is declared, it must still be instantiated using the new keyword before it can be used. This time we will use two pairs of brackets, with the number in the first pair specifying the number of rows and the number in the second pair specifying the number of columns.

After the instantiation, we will have 5 rows and 5 columns, giving a total of 25 locations where int values can be stored. Indexing these locations is done by specifying row and column values in the brackets. So, to fill up the table with the distances between cities given above we can use the following tedious code.

You’ll notice that we did not specify values for distances[0][0], distances[1][1], distances[2][2], distances[3][3], or distances[4][4], since each of these already has the default value of 0.

Much more often, multidimensional array manipulation will use nested for loops. For example, we could create an array with 3 rows and 4 columns, and then assign values to those locations such that they were numbered increasing across each row.

This code would result in an array filled up like the following table.

The bounds for the outer for loop in this example uses values.length, giving the total number of rows. Then, the inner for loops uses values[i].length, which is the length (number of columns) of the current row. In this case, all the rows of the array have the same number of columns, but this is not always true, as we’ll discuss later.

All array variables are reference type variables, not simple values like most of the types we have discussed so far. A reference variable is a name for an object. You might recall that we described the difference between reference types and primitive types in Section 3.2, but the only reference type we’ve considered in detail is String.

More than one reference variable can point at the same object. When one object has more than one name, this is called aliasing. The String type is immutable, meaning that an object of type String cannot change its contents. Arrays, however, are mutable, which means that aliasing can cause unexpected results. Here is a simple example with one-dimensional array aliasing.

Surprisingly, the value printed out will be 17. The variables array1 and array2 are references to the same fundamental array. Unlike primitive values, the complete contents of array1 are not copied to array2. Only one array exists because only one array has been created by the new keyword. When index 3 of array2 is updated, index 3 of array1 changes as well, because the two variables are simply two names for the same array.

Sometimes this reference feature of Java allows us to write code that is confusing or has unexpected consequences. However, the benefit is that we can assign one array to another without incurring the expense of copying the entire array. If you create an array with 1,000,000 elements, copying that array several times could get expensive in terms of program running time.

The best rule of thumb for understanding reference types is that there is only one actual object for every call to new. The primary exception to this rule is that uses of new can be hidden from the user when they’re in method calls.

At the end of this code, the reference pronoun will point to an object containing the String "He". The substring() method invokes new internally, generating a new String object completely separate from the String referenced by greeting. This code may look unusual because we’re explicitly using new to make a String object containing "Hello". The String class is different from every other class because it can be instantiated without using the new keyword. The line String greeting = "Hello"; implicitly calls new to create an object containing the String "Hello" and functions nearly the same as the similar line above.

We’re ashamed to say that we’ve lied to you. In Java, there’s no such thing as a true multidimensional array! Instead, the examples of two-dimensional and three-dimensional arrays we’ve given above are actually arrays of arrays (of arrays). Thinking about multidimensional arrays in this way can give the programmer more flexibility.

If we return to the definition of the two-dimensional array with 3 rows and 4 columns, we can instantiate each row separately instead of as a block.

This code is functionally equivalent to the earlier code that instantiated all 12 locations at once. The same could be done with a three-dimensional array or higher. We can specify the length of each row independently, and, more bizarrely, we can give each row a different length. A multidimensional array whose rows have different lengths is called a ragged array.

A ragged array is usually unnecessary. The main reason to use a ragged array is to save space, when you have tabular data in which the lengths of each row vary a great deal. If the lengths of the rows vary only a little, it’s probably not worth the extra hassle. However, if some rows have 10 elements and others have 1,000,000, the space saved can be significant.

We can apply the idea of ragged arrays to the table of distances between cities. If you examine this table, you’ll notice that about half the data in it is repeated, because the distance from Chicago to Los Angeles is the same as the distance from Los Angeles to Chicago, and so on. We can store the data in a triangular shape to keep only the unique distance information.

We could create this table in code by doing the following.

With this table a user cannot simply type in distances[0][4] and hope to get the distance from New York to Phoenix. Instead, we have to be careful to make sure that the index of the first city is never larger than the index of the second city. If we’re reading in the indexes of the cities from a user, we can write some code to do this check. Let city1 and city2, respectively, contain the indexes of the cities the user wants to use to find the distances between.

If we wanted to be even cleverer, we could eliminate the zero entries from the table, but then the ragged array would have one fewer row than the original two-dimensional array.

Even one-dimensional arrays make many new errors possible. Below we list two of the most common mistakes made with both one-dimensional and multidimensional arrays.

In Chapter 5 we described three loops: while loops, for loops, and do-while loops. Although these are the only three loops in Java, there’s a special form of the for loop designed for use with arrays (and some other data structures). This construct is often called the enhanced for loop.

An enhanced for loop does not have the three-part header of a regular for loop. Instead, it’s designed to iterate over the contents of an array or other list. Inside its parentheses is a declaration of a variable with the same type as the elements of the array, then a colon (:), then the name of the array. Consider the following example of an enhanced for loop used to sum the values of an array of int values called array. As with all loops in Java, braces are optional if there’s only one executable statement in the loop.

This code functions in exactly the same way as the traditional for loop we would use to solve the same problem.

The advantage of the enhanced for loop is that it’s shorter and clearer. There’s also no worry about being off by one with your indexes. The enhanced for loop iterates over every element in the array, no indexes needed!

Enhanced for loops can be nested or used inside of other loops. Consider the following nested enhanced for loops that print out all possible chess pieces, in both black and white colors.

Enhanced for loops do have a few drawbacks. For one, they’re designed for iterating through an entire array. It’s ugly to try to make them stop early, and it’s impossible to make them go back to previous values. They’re also only designed for read access, not write access. The variable in the header of the enhanced for loop takes on each value in the array in turn, but assigning values to that variable has no effect on the underlying array. Consider the following for loop that assigns 5 to every value in array.

This kind of assignment is impossible in an enhanced for loop. The “equivalent” enhanced for loop does nothing. It assigns 5 to the local variable value but never changes the contents of array.

While enhanced for loops are great for arrays, they can also be used for any data structure that implements the Iterable interface. We discuss interfaces in Chapter 10 and dynamic data structures in Chapter 18 and Chapter 19.

The designers of the Java API knew that arrays were important and added a special Arrays class to manipulate them.

This class has a number of static methods that can be used to search for values in arrays, make copies of arrays, copy selected ranges of arrays, test arrays for equality, fill arrays with specific values, sort arrays, convert an entire array into a String representation, and more. The signatures of the methods below are given for double arrays, but most methods are overloaded to work with all primitive types and reference types.

Consult the API for more information. Even though tasks like fill() are simple, it’s worth using the method from Arrays instead of writing your own. The methods in the Java API have often been tuned for speed and use special instructions that are not accessible to regular Java programmers.