Arraylist primitive types

The ArrayList class is a Java class that you can use to store lists of objects. You can also store objects in an array, but arrays have a couple of obvious problems.

• To create an array, you have to specify a size for the array. Sometimes you won't know what size array you will need at the instant you create the array.
• Although it is possible to resize arrays by creating a new, larger array and copying data over from the old array, doing this is clunky and awkward.

The primary goal of the Java ArrayList class is to provide a class that replicates many of the features of arrays, while adding some new features that are designed to work around the problems listed above.

Basics of ArrayLists

To create an ArrayList object you use the following syntax.

ArrayList A = new ArrayList[];

Here Type is the type that you are planning to store in the ArrayList. For example, to make an ArrayList that can hold Strings you would do

ArrayList B = new ArrayList[];

A fundamental limitation of ArrayLists is that they can only hold objects, and not primitive types such as ints.

ArrayList C = new ArrayList[]; // Illegal - int is not an object type

The workaround for this is that Java provides a class equivalent for every one of the primitive types. For example, there is an Integer class corresponding to the int type and a Double class corresponding to the double type, and so on. The first step to being able to store a list of ints in an ArrayList is to instead create an ArrayList that can hold a list of Integer objects:

ArrayList D = new ArrayList[]; // OK - Integer is an object type

When you create an ArrayList, the list you get is initially empty. To add new items to the end of the ArrayList you use the add[] method:

ArrayList B = new ArrayList[]; // B starts out empty. B.add["Hello"]; // B now has size 1 B.add["World"]; // B new has size 2

Adding items to an ArrayList of Integers is similar:

ArrayList D = new ArrayList[]; D.add[new Integer[3]]; // D now has size 1 D.add[new Integer[15]]; // D now has size 2

An alternative way to add ints to an ArrayList is to use the autoboxing feature. This feature automatically converts primitive types into their object equivalents:

ArrayList D = new ArrayList[]; D.add[3]; // D now has size 1 D.add[15]; // D now has size 2

To retrieve items from an ArrayList, use the get[] method.

ArrayList D = new ArrayList[]; D.add[3]; D.add[15]; int x = D.get[1]; // x is now 15

To determine the size of an ArrayList, use the size[] method.

ArrayList D = new ArrayList[]; D.add[3]; D.add[15]; D.add[-46]; for[int n = 0;n < D.size[];n++] System.out.println[D.get[n]];

To replace an existing value with a new value, use the set[] method:

ArrayList D = new ArrayList[]; D.add[3]; // Location 0 is 3 D.add[15]; D.add[-46]; D.set[0,22]; // Location 0 is now 22

Along with being to add items and have the list resize automatically to accomodate them, you can also remove items and have the list shrink automatically each time you remove an item. To remove an item, use the remove[] method with the index of the item you want to remove. For example, to remove the last item in an ArrayList you would do

D.remove[D.size[] - 1];

As we have just seen in Subsection 7.2.4, we can easily encode the dynamic array pattern into a class, but it looks like we need a different class for each data type. In fact, Java has a feature called "parameterized types" that makes it possible to avoid the multitude of classes, and Java has a single class named ArrayList that implements the dynamic array pattern for all data types.

Java has a standard type with the rather odd name ArrayList that represents dynamic arrays of Strings. Similarly, there is a type ArrayList that can be used to represent dynamic arrays of Buttons. And if Player is a class representing players in a game, then the type ArrayList can be used to represent a dynamic array of Players.

It might look like we still have a multitude of classes here, but in fact there is only one class, the ArrayList class, defined in the package java.util. But ArrayList is a parameterized type. A parameterized type can take a type parameter, so that from the single class ArrayList, we get a multitude of types including ArrayList, ArrayList, and in fact ArrayList for any object type T. The type parameter T must be an object type such as a class name or an interface name. It cannot be a primitive type. This means that, unfortunately, you can not have an ArrayList of int or an ArrayList of char.

Consider the type ArrayList. As a type, it can be used to declare variables, such as

ArrayList namelist;

It can also be used as the type of a formal parameter in a subroutine definition, or as the return type of a subroutine. It can be used with the new operator to create objects:

namelist = new ArrayList[];

The object created in this way is of type ArrayList and represents a dynamic list of strings. It has instance methods such as namelist.add[str] for adding a String to the list, namelist.get[i] for getting the string at index i, and namelist.size[] for getting the number of items currently in the list.

But we can also use ArrayList with other types. If Player is a class representing players in a game, we can create a list of players with

ArrayList playerList = new ArrayList[];

Then to add a player, plr, to the game, we just have to say playerList.add[plr]. And we can remove player number k with playerList.remove[k].

Furthermore if playerList is a local variable, then its declaration can be abbreviated [in Java 10 or later] to

var playlerList = new ArrayList[];

using the alternative declaration syntax that was covered in Subsection 4.8.2. The Java compiler uses the initial value that is assigned to playerList to deduce that its type is ArrayList.

When you use a type such as ArrayList, the compiler will ensure that only objects of type T can be added to the list. An attempt to add an object that is not of type T will be a syntax error, and the program will not compile. However, note that objects belonging to a subclass of T can be added to the list, since objects belonging to a subclass of T are still considered to be of type T. Thus, for example, a variable of type ArrayList can be used to hold objects of type BorderPane, TilePane, GridPane, or any other subclass of Pane. [Of course, this is the same way arrays work: An object of type T[] can hold objects belonging to any subclass of T.] Similarly, if T is an interface, then any object that implements interface T can be added to the list.

An object of type ArrayList has all of the instance methods that you would expect in a dynamic array implementation. Here are some of the most useful. Suppose that list is a variable of type ArrayList. Then we have:

• list.size[] — This function returns the current size of the list, that is, the number of items currently in the list. The only valid positions in the list are numbers in the range 0 to list.size[]-1. Note that the size can be zero. A call to the default constructor new ArrayList[] creates a list of size zero.
• list.add[obj] — Adds an object onto the end of the list, increasing the size by 1. The parameter, obj, can refer to an object of type T, or it can be null.
• list.get[N] — This function returns the value stored at position N in the list. The return type of this function is T.  N must be an integer in the range 0 to list.size[]-1. If N is outside this range, an error of type IndexOutOfBoundsException occurs. Calling this function is similar to referring to A[N] for an array, A, except that you can't use list.get[N] on the left side of an assignment statement.
• list.set[N, obj] — Assigns the object, obj, to position N in the ArrayList, replacing the item previously stored at position N. The parameter obj must be of type T. The integer N must be in the range from 0 to list.size[]-1. A call to this function is equivalent to the command A[N] = obj for an array A.
• list.clear[] — Removes all items from the list, setting its size to zero.
• list.remove[N] — For an integer, N, this removes the N-th item in the ArrayList. N must be in the range 0 to list.size[]-1. Any items in the list that come after the removed item are moved up one position. The size of the list decreases by 1.
• list.remove[obj] — If the specified object occurs somewhere in the list, it is removed from the list. Any items in the list that come after the removed item are moved up one position. The size of the ArrayList decreases by 1. If obj occurs more than once in the list, only the first copy is removed. If obj does not occur in the list, nothing happens; this is not an error.
• list.indexOf[obj] — A function that searches for the object, obj, in the list. If the object is found in the list, then the first position number where it is found is returned. If the object is not found, then -1 is returned.

For the last two methods listed here, obj is compared to an item in the list by calling obj.equals[item], unless obj is null. This means, for example, that strings are tested for equality by checking the contents of the strings, not their location in memory.

Java comes with several parameterized classes representing different data structures. Those classes make up the Java Collection Framework. Here we consider only ArrayList, but we will return to this important topic in much more detail in Chapter 10.

By the way, ArrayList can also be used as a non-parametrized type. This means that you can declare variables and create objects of type ArrayList such as

ArrayList list = new ArrayList[];

The effect of this is similar to declaring list to be of type ArrayList. That is, list can hold any object that belongs to a subclass of Object. Since every class is a subclass of Object, this means that any object can be stored in list.

As I have already noted, parameterized types don't work with the primitive types. There is no such thing as "ArrayList". However, this limitation turns out not to be very limiting after all, because of the so-called wrapper classes such as Integer and Character.

We have already briefly encountered the classes Double and Integer in Section 2.5. These classes contain the static methods Double.parseDouble[] and Integer.parseInteger[] that are used to convert strings to numerical values, and they contain constants such as Integer.MAX_VALUE and Double.NaN. We have also encountered the Character class in some examples, with the static method Character.isLetter[], that can be used to test whether a given value of type char is a letter. There is a similar class for each of the other primitive types, Long, Short, Byte, Float, and Boolean. These classes are wrapper classes. Although they contain useful static members, they have another use as well: They are used for representing primitive type values as objects.

Remember that the primitive types are not classes, and values of primitive type are not objects. However, sometimes it's useful to treat a primitive value as if it were an object. This is true, for example, when you would like to store primitive type values in an ArrayList. You can't do that literally, but you can "wrap" the primitive type value in an object belonging to one of the wrapper classes.

For example, an object of type Double contains a single instance variable, of type double. The object is a "wrapper" for the double value. You can create an object that wraps the double value 6.0221415e23 with

Double d = new Double[6.0221415e23];

The value of d contains the same information as the value of type double, but it is an object. If you want to retrieve the double value that is wrapped in the object, you can call the function d.doubleValue[]. Similarly, you can wrap an int in an object of type Integer, a boolean value in an object of type Boolean, and so on.

Actually, instead of calling the constructor, new Double[x], it is preferable to use the static method Double.valueOf[x], which does essentially the same thing; that is, it returns an object of type Double that wraps the double value x. The advantage is that if Double.valueOf[] is called more than once with the same parameter, value, it has the option of returning the same object each time. After the first call with that parameter, it can reuse the same object in subsequent calls with the same parameter. This is OK because objects of type Double are immutable, so two objects that start out with the same value are guaranteed to be identical forever. Double.valueOf is a kind of "factory method" like those we saw for Color and Font in Section 6.2. Each of the wrapper classes has a similar factory method: Integer.valueOf[n], Character.valueOf[ch], and so on.

To make the wrapper classes even easier to use, there is automatic conversion between a primitive type and the corresponding wrapper class. For example, if you use a value of type int in a context that requires an object of type Integer, the int will automatically be wrapped in an Integer object. If you say

Integer answer = 42;

the computer will silently read this as if it were

Integer answer = Integer.valueOf[42];

This is called autoboxing. It works in the other direction, too. For example, if d refers to an object of type Double, you can use d in a numerical expression such as 2*d. The double value inside d is automatically unboxed and multiplied by 2. Autoboxing and unboxing also apply to subroutine calls. For example, you can pass an actual parameter of type int to a subroutine that has a formal parameter of type Integer, and vice versa. In fact, autoboxing and unboxing make it possible in many circumstances to ignore the difference between primitive types and objects.

This is true in particular for parameterized types. Although there is no such thing as "ArrayList", there is ArrayList. An ArrayList holds objects of type Integer, but any object of type Integer really just represents an int value in a rather thin wrapper. Suppose that we have an object of type ArrayList:

ArrayList integerList; integerList = new ArrayList[];

Then we can, for example, add an object to integerList that represents the number 42:

integerList.add[ Integer.valueOf[42] ];

but because of autoboxing, we can actually say

integerList.add[ 42 ];

and the compiler will automatically wrap 42 in an object of type Integer before adding it to the list. Similarly, we can say

int num = integerList.get[3];

The value returned by integerList.get[3] is of type Integer but because of unboxing, the compiler will automatically convert the return value into an int, as if we had said

int num = integerList.get[3].intValue[];

So, in effect, we can pretty much use integerList as if it were a dynamic array of int rather than a dynamic array of Integer. Of course, a similar statement holds for lists of other wrapper classes such as ArrayList and ArrayList. [There is one issue that sometimes causes problems: A list can hold null values, and a null does not correspond to any primitive type value. This means, for example, that the statement "int num = integerList.get[3];" can produce a null pointer exception in the case where integerList.get[3] returns null. Unless you are sure that all the values in your list are non-null, you need to take this possibility into account.]

As a simple first example, we can redo ReverseWithDynamicArray.java, from the previous section, using an ArrayList instead of a custom dynamic array class. In this case, we want to store integers in the list, so we should use ArrayList. Here is the complete program:

import textio.TextIO; import java.util.ArrayList; /** * Reads a list of non-zero numbers from the user, then prints * out the input numbers in the reverse of the order in which * the were entered. There is no limit on the number of inputs. */ public class ReverseWithArrayList { public static void main[String[] args] { ArrayList list; list = new ArrayList[]; System.out.println["Enter some non-zero integers. Enter 0 to end."]; while [true] { System.out.print["? "]; int number = TextIO.getlnInt[]; if [number == 0] break; list.add[number]; } System.out.println[]; System.out.println["Your numbers in reverse are:"]; for [int i = list.size[] - 1; i >= 0; i--] { System.out.printf["%10d%n", list.get[i]]; } } }

As illustrated in this example, ArrayLists are commonly processed using for loops, in much the same way that arrays are processed. for example, the following loop prints out all the items for a variable namelist of type ArrayList:

for [ int i = 0; i < namelist.size[]; i++ ] { String item = namelist.get[i]; System.out.println[item]; }

You can also use for-each loops with ArrayLists, so this example could also be written

for [ String item : namelist ] { System.out.println[item]; }

When working with wrapper classes, the loop control variable in the for-each loop can be a primitive type variable. This works because of unboxing. For example, if numbers is of type ArrayList, then the following loop can be used to add up all the values in the list:

double sum = 0; for [ double num : numbers ] { sum = sum + num; }

This will work as long as none of the items in the list are null. If there is a possibility of null values, then you will want to use a loop control variable of type Double and test for nulls. For example, to add up all the non-null values in the list:

double sum; for [ Double num : numbers ] { if [ num != null ] { sum = sum + num; // Here, num is SAFELY unboxed to get a double. } }

For a more complete and useful example, we will look at the program SimplePaint2.java. This is a much improved version of SimplePaint.java from Subsection 6.3.3. In the new program, the user can sketch curves in a drawing area by clicking and dragging with the mouse. The user can select the drawing color using a menu. The background color of the drawing area can also be selected using a menu. And there is a "Control" menu that contains several commands: An "Undo" command, which removes the most recently drawn curve from the screen, a "Clear" command that removes all the curves, and a "Use Symmetry" checkbox that turns a symmetry feature on and off. Curves that are drawn by the user when the symmetry option is on are reflected horizontally and vertically to produce a symmetric pattern. [Symmetry is there just to look pretty.]

Unlike the original SimplePaint program, this new version uses a data structure to store information about the picture that has been drawn by the user. When the user selects a new background color, the canvas is filled with the new background color, and all of the curves that were there previously are redrawn on the new background. To do that, we need to store enough data to redraw all of the curves. Similarly, the Undo command is implemented by deleting the data for most recently drawn curve, and then redrawing the entire picture using the remaining data.

The data structure that we need is implemented using ArrayLists. The main data for a curve consists of a list of the points on the curve. This data is stored in an object of type ArrayList. [Point2D is standard class in package javafx.geometry. A Point2D can be constructed from two double values, giving the [x,y] coordinates of a point. A Point2D object, pt, has getter methods pt.getX[] and pt.getY[] that return the x and y coordinates.] But in addition to a list of points on a curve, to redraw the curve, we also need to know its color, and we need to know whether the symmetry option should be applied to the curve. All the data that is needed to redraw the curve is grouped into an object of type CurveData that is defined as a nested class in the program:

private static class CurveData { Color color; // The color of the curve. boolean symmetric; // Are horizontal and vertical reflections also drawn? ArrayList points; // The points on the curve. }

However, a picture can contain many curves, not just one, so to store all the data necessary to redraw the entire picture, we need a list of objects of type CurveData. For this list, the program uses an ArrayList, curves, declared as

ArrayList curves = new ArrayList[];

Here we have a list of objects, where each object contains a list of points as part of its data! Let's look at a few examples of processing this data structure. When the user clicks the mouse on the drawing surface, it's the start of a new curve, and a new CurveData object must be created. The instance variables in the new CurveData object must also be initialized. Here is the code from the mousePressed[] routine that does this, where currentCurve is a global variable of type CurveData:

currentCurve = new CurveData[]; // Create a new CurveData object. currentCurve.color = currentColor; // The color of a curve is taken from an // instance variable that represents the // currently selected drawing color. currentCurve.symmetric = useSymmetry; // The "symmetric" property of the curve // is also copied from the current value // of an instance variable, useSymmetry. currentCurve.points = new ArrayList[]; // A new point list object.

As the user drags the mouse, new points are added to currentCurve, and line segments of the curve are drawn between points as they are added. When the user releases the mouse, the curve is complete, and it is added to the list of curves by calling

curves.add[ currentCurve ];

When the user changes the background color or selects the "Undo" command, the picture has to be redrawn. The program has a redraw[] method that completely redraws the picture. That method uses the data in curves to draw all the curves. The basic structure is a for-each loop that processes the data for each individual curve in turn. This has the form:

for [ CurveData curve : curves ] { . . // Draw the curve represented by the object, curve, of type CurveData. . }

In the body of this loop, curve.points is a variable of type ArrayList that holds the list of points on the curve. The i-th point on the curve can be obtained by calling the get[] method of this list: curve.points.get[i]. This returns a value of type Point2D which has getter methods named getX[] and getY[]. We can refer directly to the x-coordinate of the i-th point as:

curve.points.get[i].getX[]

This might seem rather complicated, but it's a nice example of a complex name that specifies a path to a desired piece of data: Go to the object, curve. Inside curve, go to points. Inside points, get the i-th item. And from that item, get the x coordinate by calling its getX[] method. Here is the complete definition of the method that redraws the picture:

private void redraw[] { g.setFill[backgroundColor]; g.fillRect[0,0,canvas.getWidth[],canvas.getHeight[]]; for [ CurveData curve : curves ] { g.setStroke[curve.color]; for [int i = 1; i < curve.points.size[]; i++] { // Draw a line segment from point number i-1 to point number i. double x1 = curve.points.get[i-1].getX[]; double y1 = curve.points.get[i-1].getY[]; double x2 = curve.points.get[i].getX[]; double y2 = curve.points.get[i].getY[]; drawSegment[curve.symmetric,x1,y1,x2,y2]; } } }

drawSegment[] is a method that strokes the line segment from [x1,y1] to [x2,y2]. If the first parameter is true, it also draws the horizontal and vertical reflections of that segment.

I have mostly been interested here in discussing how the program uses ArrayList, but I encourage you to read the full source code, SimplePaint2.java, and to try out the program. In addition to serving as an example of using parameterized types, it also serves as another example of creating and using menus. You should be able to understand the entire program.

Page 2

Two array processing techniques that are particularly common are searching and sorting. Searching here refers to finding an item in the array that meets some specified criterion. Sorting refers to rearranging all the items in the array into increasing or decreasing order [where the meaning of increasing and decreasing can depend on the context]. We have seen in Subsection 7.2.2 that Java has some built-in methods for searching and sorting arrays. However, a computer science student should be familiar with the algorithms that are used in those methods. In this section, you will learn some algorithms for searching and sorting.

Sorting and searching are often discussed, in a theoretical sort of way, using an array of numbers as an example. In practical situations, though, more interesting types of data are usually involved. For example, the array might be a mailing list, and each element of the array might be an object containing a name and address. Given the name of a person, you might want to look up that person's address. This is an example of searching, since you want to find the object in the array that contains the given name. It would also be useful to be able to sort the array according to various criteria. One example of sorting would be ordering the elements of the array so that the names are in alphabetical order. Another example would be to order the elements of the array according to zip code before printing a set of mailing labels. [This kind of sorting can get you a cheaper postage rate on a large mailing.]

This example can be generalized to a more abstract situation in which we have an array that contains objects, and we want to search or sort the array based on the value of one of the instance variables in the objects. We can use some terminology here that originated in work with "databases," which are just large, organized collections of data. We refer to each of the objects in the array as a record. The instance variables in an object are then called fields of the record. In the mailing list example, each record would contain a name and address. The fields of the record might be the first name, last name, street address, state, city and zip code. For the purpose of searching or sorting, one of the fields is designated to be the key field. Searching then means finding a record in the array that has a specified value in its key field. Sorting means moving the records around in the array so that the key fields of the record are in increasing [or decreasing] order.

In this section, most of my examples follow the tradition of using arrays of numbers. But I'll also give a few examples using records and keys, to remind you of the more practical applications.

There is an obvious algorithm for searching for a particular item in an array: Look at each item in the array in turn, and check whether that item is the one you are looking for. If so, the search is finished. If you look at every item without finding the one you want, then you can be sure that the item is not in the array. It's easy to write a subroutine to implement this algorithm. Let's say the array that you want to search is an array of ints. Here is a method that will search the array for a specified integer. If the integer is found, the method returns the index of the location in the array where it is found. If the integer is not in the array, the method returns the value -1 as a signal that the integer could not be found:

/** * Searches the array A for the integer N. If N is not in the array, * then -1 is returned. If N is in the array, then the return value is * the first integer i that satisfies A[i] == N. */ static int find[int[] A, int N] { for [int index = 0; index < A.length; index++] { if [ A[index] == N ] return index; // N has been found at this index! } // If we get this far, then N has not been found // anywhere in the array. Return a value of -1. return -1; }

This method of searching an array by looking at each item in turn is called linear search. If nothing is known about the order of the items in the array, then there is really no better alternative algorithm. But if the elements in the array are known to be in increasing or decreasing order, then a much faster search algorithm can be used. An array in which the elements are in order is said to be sorted. Of course, it takes some work to sort an array, but if the array is to be searched many times, then the work done in sorting it can really pay off.

Binary search is a method for searching for a given item in a sorted array. Although the implementation is not trivial, the basic idea is simple: If you are searching for an item in a sorted list, then it is possible to eliminate half of the items in the list by inspecting a single item. For example, suppose that you are looking for the number 42 in a sorted array of 1000 integers. Let's assume that the array is sorted into increasing order. Suppose you check item number 500 in the array, and find that the item is 93. Since 42 is less than 93, and since the elements in the array are in increasing order, we can conclude that if 42 occurs in the array at all, then it must occur somewhere before location 500. All the locations numbered 500 or above contain values that are greater than or equal to 93. These locations can be eliminated as possible locations of the number 42.

The next obvious step is to check location 250. If the number at that location is, say, -21, then you can eliminate locations before 250 and limit further search to locations between 251 and 499. The next test will limit the search to about 125 locations, and the one after that to about 62. After just 10 steps, there is only one location left. This is a whole lot better than looking through every element in the array. If there were a million items, it would still take only 20 steps for binary search to search the array! [Mathematically, the number of steps is approximately equal to the logarithm, in the base 2, of the number of items in the array.]

In order to make binary search into a Java subroutine that searches an array A for an item N, we just have to keep track of the range of locations that could possibly contain N. At each step, as we eliminate possibilities, we reduce the size of this range. The basic operation is to look at the item in the middle of the range. If this item is greater than N, then the second half of the range can be eliminated. If it is less than N, then the first half of the range can be eliminated. If the number in the middle just happens to be N exactly, then the search is finished. If the size of the range decreases to zero, then the number N does not occur in the array. Here is a subroutine that implements this idea:

/** * Searches the array A for the integer N. * Precondition: A must be sorted into increasing order. * Postcondition: If N is in the array, then the return value, i, * satisfies A[i] == N. If N is not in the array, then the * return value is -1. */ static int binarySearch[int[] A, int N] { int lowestPossibleLoc = 0; int highestPossibleLoc = A.length - 1; while [highestPossibleLoc >= lowestPossibleLoc] { int middle = [lowestPossibleLoc + highestPossibleLoc] / 2; if [A[middle] == N] { // N has been found at this index! return middle; } else if [A[middle] > N] { // eliminate locations >= middle highestPossibleLoc = middle - 1; } else { // eliminate locations = 0] { // The name already exists, in position i in the array. // Just replace the old number at that position with the new. data[i].number = number; } else { // Add a new name/number pair to the array. If the array is // already full, first create a new, larger array. if [dataCount == data.length] { data = Arrays.copyOf[ data, 2*data.length ]; } PhoneEntry newEntry = new PhoneEntry[]; // Create a new pair. newEntry.name = name; newEntry.number = number; data[dataCount] = newEntry; // Add the new pair to the array. dataCount++; } } } // end class PhoneDirectory

The class defines a private instance method, find[], that uses linear search to find the position of a given name in the array of name/number pairs. The find[] method is used both in the getNumber[] method and in the putNumber[] method. Note in particular that putNumber[name,number] has to check whether the name is in the phone directory. If so, it just changes the number in the existing entry; if not, it has to create a new phone entry and add it to the array.

This class could use a lot of improvement. For one thing, it would be nice to use binary search instead of simple linear search in the getNumber method. However, we could only do that if the list of PhoneEntries were sorted into alphabetical order according to name. In fact, it's really not all that hard to keep the list of entries in sorted order, as you'll see in the next subsection.

I will mention that association lists are also called "maps," and Java has a standard parameterized type named Map that implements association lists for keys and values of any type. The implementation is much more efficient than anything you can do with basic arrays. You will encounter this class in Chapter 10.

We've seen that there are good reasons for sorting arrays. There are many algorithms available for doing so. One of the easiest to understand is the insertion sort algorithm. This technique is also applicable to the problem of keeping a list in sorted order as you add new items to the list. Let's consider that case first:

Suppose you have a sorted list and you want to add an item to that list. If you want to make sure that the modified list is still sorted, then the item must be inserted into the right location, with all the smaller items coming before it and all the bigger items after it. This will mean moving each of the bigger items up one space to make room for the new item.

/* * Precondition: itemsInArray is the number of items that are * stored in A. These items must be in increasing order * [A[0] 0; lastPlace--] { // Find the largest item among A[0], A[1], ..., // A[lastPlace], and move it into position lastPlace // by swapping it with the number that is currently // in position lastPlace. int maxLoc = 0; // Location of largest item seen so far. for [int j = 1; j A[maxLoc]] { // Since A[j] is bigger than the maximum we've seen // so far, j is the new location of the maximum value // we've seen so far. maxLoc = j; } } int temp = A[maxLoc]; // Swap largest item with A[lastPlace]. A[maxLoc] = A[lastPlace]; A[lastPlace] = temp; } // end of for loop }

A variation of selection sort is used in the Hand class that was introduced in Subsection 5.4.1. [By the way, you are finally in a position to fully understand the source code for the Hand class from that section; note that it uses ArrayList. The source file is Hand.java.]

In the Hand class, a hand of playing cards is represented by an ArrayList. The objects stored in the list are of type Card. A Card object contains instance methods getSuit[] and getValue[] that can be used to determine the suit and value of the card. In my sorting method, I actually create a new list and move the cards one-by-one from the old list to the new list. The cards are selected from the old list in increasing order. In the end, the new list becomes the hand and the old list is discarded. This is not the most efficient procedure. But hands of cards are so small that the inefficiency is negligible. Here is the code for sorting cards by suit:

/** * Sorts the cards in the hand so that cards of the same suit are * grouped together, and within a suit the cards are sorted by value. * Note that aces are considered to have the lowest value, 1. */ public void sortBySuit[] { ArrayList newHand = new ArrayList[]; while [hand.size[] > 0] { int pos = 0; // Position of minimal card. Card c = hand.get[0]; // Minimal card. for [int i = 1; i < hand.size[]; i++] { Card c1 = hand.get[i]; if [ c1.getSuit[] < c.getSuit[] || [c1.getSuit[] == c.getSuit[] && c1.getValue[] < c.getValue[]] ] { pos = i; // Update the minimal card and location. c = c1; } } hand.remove[pos]; // Remove card from original hand. newHand.add[c]; // Add card to the new hand. } hand = newHand; }

This example illustrates the fact that comparing items in a list is not usually as simple as using the operator "= j. We can store the data in a "triangular matrix":

It's easy enough to make a triangular array, if we create each row separately. To create a 7-by-7 triangular array of double, we can use the code segment

double[][] matrix = new double[7][]; // rows have not yet been created! for [int i = 0; i < 7; i++] { matrix[i] = new double[i+1]; // Create row i with i + 1 elements. }

We just have to remember that if we want to know the value of the matrix at [i,j], and if i = 0 && c-1 >= 0 && alive[r-1][c-1]] N++; // A cell at position [r-1,c-1] exists and is alive. if [r-1 >= 0 && alive[r-1][c]] N++; // A cell at position [r-1,c] exists and is alive. if [r-1 >= 0 && c+1 0 ? r-1 : GRID_SIZE-1; // [for "?:" see Subsection 2.5.5] below = r < GRID_SIZE-1 ? r+1 : 0; for [ int c = 0; c < GRID_SIZE; c++ ] { left = c > 0 ? c-1 : GRID_SIZE-1; right = c < GRID_SIZE-1 ? c+1 : 0; int n = 0; // number of alive cells in the 8 neighboring cells if [alive[above][left]] n++; if [alive[above][c]] n++; if [alive[above][right]] n++; if [alive[r][left]] n++; if [alive[r][right]] n++; if [alive[below][left]] n++; if [alive[below][c]] n++; if [alive[below][right]] n++; if [n == 3 || [alive[r][c] && n == 2]] newboard[r][c] = true; else newboard[r][c] = false; } } alive = newboard; }

Again, I urge you to check out the source code, Life.java, and try the program. Don't forget that you will also need MosaicCanvas.java.

As a final example for this chapter, we'll look at a more substantial example of using a 2D array. This is the longest program that we have encountered so far, with 745 lines of code. The program lets two users play checkers against each other. The checkers game is played on an eight-by-eight board, which is based on an example from Subsection 6.5.1. The players are called "red" and "black," after the color of their checkers. I'm not going to explain the rules of checkers here; possibly you can learn them by trying out the program.

In the program, a player moves by clicking on the piece that they want to move, and then clicking on the empty square to which it is to be moved. As an aid to the players, any square that the current player can legally click at a given time is highlighted with a brightly colored border. The square containing a piece that has been selected to be moved, if any, is surrounded by a yellow border. Other pieces that can legally be moved are surrounded by a cyan-colored border. If a piece has already been selected to be moved, each empty square that it can legally move to is highlighted with a green border. The game enforces the rule that if the current player can jump one of the opponent's pieces, then the player must jump. When a player's piece becomes a king, by reaching the opposite end of the board, a big white "K" is drawn on the piece. Here is a picture of the program early in a game. It is black's turn to move. Black has selected the piece in the yellow-outlined square to be moved. Black can click one of the squares outlined in green to complete the move, or can click one of the squares outlined in cyan to select a different piece to be moved.

I will only cover a part of the programming for this example. I encourage you to read the complete source code, Checkers.java. It's long and complex, but with some study, you should understand all the techniques that it uses. The program is a good example of state-based, event-driven, object-oriented programming.

The data about the pieces on the board are stored in a two-dimensional array. Because of the complexity of the program, I wanted to divide it into several classes. In addition to the main class, there are several nested classes. One of these classes is CheckersData, which handles the data for the board. It is not directly responsible for any part of the graphics or event-handling, but it provides methods that can be called by other classes that handle graphics and events. It is mainly this class that I want to talk about.

The CheckersData class has an instance variable named board of type int[][]. The value of board is set to "new int[8][8]", an 8-by-8 grid of integers. The values stored in the grid are defined as constants representing the possible contents of a square on a checkerboard:

static final int EMPTY = 0, // Value representing an empty square. RED = 1, // A regular red piece. RED_KING = 2, // A red king. BLACK = 3, // A regular black piece. BLACK_KING = 4; // A black king.

The constants RED and BLACK are also used in my program [or, perhaps, misused] to represent the two players in the game. When a game is started, the values in the array are set to represent the initial state of the board. The grid of values looks like

A regular black piece can only move "down" the grid. That is, the row number of the square it moves to must be greater than the row number of the square it comes from. A regular red piece can only move up the grid. Kings of either color can move in both directions.

One function of the CheckersData class is to take care of changes to the data structures that need to be made when one of the users moves a checker. An instance method named makeMove[] is provided to do this. When a player moves a piece from one square to another, the values of two elements in the array are changed. But that's not all. If the move is a jump, then the piece that was jumped is removed from the board. [The method checks whether the move is a jump by checking if the square to which the piece is moving is two rows away from the square where it starts.] Furthermore, a RED piece that moves to row 0 or a BLACK piece that moves to row 7 becomes a king. Putting all that into a subroutine is good programming: the rest of the program doesn't have to worry about any of these details. It just calls this makeMove[] method:

/** * Make the move from [fromRow,fromCol] to [toRow,toCol]. It is * ASSUMED that this move is legal! If the move is a jump, the * jumped piece is removed from the board. If a piece moves * to the last row on the opponent's side of the board, the * piece becomes a king. */ void makeMove[int fromRow, int fromCol, int toRow, int toCol] { board[toRow][toCol] = board[fromRow][fromCol]; // Move the piece. board[fromRow][fromCol] = EMPTY; // The square it moved from is now empty. if [fromRow - toRow == 2 || fromRow - toRow == -2] { // The move is a jump. Remove the jumped piece from the board. int jumpRow = [fromRow + toRow] / 2; // Row of the jumped piece. int jumpCol = [fromCol + toCol] / 2; // Column of the jumped piece. board[jumpRow][jumpCol] = EMPTY; } if [toRow == 0 && board[toRow][toCol] == RED] board[toRow][toCol] = RED_KING; // Red piece becomes a king. if [toRow == 7 && board[toRow][toCol] == BLACK] board[toRow][toCol] = BLACK_KING; // Black piece becomes a king. } // end makeMove[]

An even more important function of the CheckersData class is to find legal moves on the board. In my program, a move in a Checkers game is represented by an object belonging to the following class:

/** * A CheckersMove object represents a move in the game of * Checkers. It holds the row and column of the piece that is * to be moved and the row and column of the square to which * it is to be moved. [This class makes no guarantee that * the move is legal.] */ private static class CheckersMove { int fromRow, fromCol; // Position of piece to be moved. int toRow, toCol; // Square it is to move to. CheckersMove[int r1, int c1, int r2, int c2] { // Constructor. Set the values of the instance variables. fromRow = r1; fromCol = c1; toRow = r2; toCol = c2; } boolean isJump[] { // Test whether this move is a jump. It is assumed that // the move is legal. In a jump, the piece moves two // rows. [In a regular move, it only moves one row.] return [fromRow - toRow == 2 || fromRow - toRow == -2]; } } // end class CheckersMove.

The CheckersData class has an instance method which finds all the legal moves that are currently available for a specified player. This method is a function that returns an array of type CheckersMove[]. The array contains all the legal moves, represented as CheckersMove objects. The specification for this method reads

/** * Return an array containing all the legal CheckersMoves * for the specified player on the current board. If the player * has no legal moves, null is returned. The value of player * should be one of the constants RED or BLACK; if not, null * is returned. If the returned value is non-null, it consists * entirely of jump moves or entirely of regular moves, since * if the player can jump, only jumps are legal moves. */ CheckersMove[] getLegalMoves[int player]

A brief pseudocode algorithm for the method is

Start with an empty list of moves Find any legal jumps and add them to the list if there are no jumps: Find any other legal moves and add them to the list if the list is empty: return null else: return the list

Now, what is this "list"? We have to return the legal moves in an array. But since an array has a fixed size, we can't create the array until we know how many moves there are, and we don't know that until near the end of the method, after we've already made the list! A neat solution is to use an ArrayList instead of an array to hold the moves as we find them. In fact, I use an object defined by the parameterized type ArrayList so that the list is restricted to holding objects of type CheckersMove. As we add moves to the list, it will grow just as large as necessary. At the end of the method, we can create the array that we really want and copy the data into it:

Let "moves" be an empty ArrayList Find any legal jumps and add them to moves if moves.size[] is 0: // There are no legal jumps! Find any other legal moves and add them to moves if moves.size[] is 0: // There are no legal moves at all! return null else: Let moveArray be an array of CheckersMoves of length moves.size[] Copy the contents of moves into moveArray return moveArray

Now, how do we find the legal jumps or the legal moves? The information we need is in the board array, but it takes some work to extract it. We have to look through all the positions in the array and find the pieces that belong to the current player. For each piece, we have to check each square that it could conceivably move to, and check whether that would be a legal move. If we are looking for legal jumps, we want to look at squares that are two rows and two columns away from the piece. There are four squares to consider. Thus, the line in the algorithm that says "Find any legal jumps and add them to moves" expands to:

For each row of the board: For each column of the board: if one of the player's pieces is at this location: if it is legal to jump to row + 2, column + 2 add this move to moves if it is legal to jump to row - 2, column + 2 add this move to moves if it is legal to jump to row + 2, column - 2 add this move to moves if it is legal to jump to row - 2, column - 2 add this move to moves

The line that says "Find any other legal moves and add them to moves" expands to something similar, except that we have to look at the four squares that are one column and one row away from the piece. Testing whether a player can legally move from one given square to another given square is itself non-trivial. The square the player is moving to must actually be on the board, and it must be empty. Furthermore, regular red and black pieces can only move in one direction. I wrote the following utility method to check whether a player can make a given non-jump move:

/** * This is called by the getLegalMoves[] method to determine * whether the player can legally move from [r1,c1] to [r2,c2]. * It is ASSUMED that [r1,c1] contains one of the player's * pieces and that [r2,c2] is a neighboring square. */ private boolean canMove[int player, int r1, int c1, int r2, int c2] { if [r2 < 0 || r2 >= 8 || c2 < 0 || c2 >= 8] return false; // [r2,c2] is off the board. if [board[r2][c2] != EMPTY] return false; // [r2,c2] already contains a piece. if [player == RED] { if [board[r1][c1] == RED && r2 > r1] return false; // Regular red piece can only move down. return true; // The move is legal. } else { if [board[r1][c1] == BLACK && r2 < r1] return false; // Regular black piece can only move up. return true; // The move is legal. } } // end canMove[]

This method is called by my getLegalMoves[] method to check whether one of the possible moves that it has found is actually legal. I have a similar method that is called to check whether a jump is legal. In this case, I pass to the method the square containing the player's piece, the square that the player might move to, and the square between those two, which the player would be jumping over. The square that is being jumped must contain one of the opponent's pieces. This method has the specification:

/** * This is called by other methods to check whether * the player can legally jump from [r1,c1] to [r3,c3]. * It is assumed that the player has a piece at [r1,c1], that * [r3,c3] is a position that is 2 rows and 2 columns distant * from [r1,c1] and that [r2,c2] is the square between [r1,c1] * and [r3,c3]. */ private boolean canJump[int player, int r1, int c1, int r2, int c2, int r3, int c3] { . . .

Given all this, you should be in a position to understand the complete getLegalMoves[] method. It's a nice way to finish off this chapter, since it combines several topics that we've looked at: one-dimensional arrays, ArrayLists, and two-dimensional arrays:

CheckersMove[] getLegalMoves[int player] { if [player != RED && player != BLACK] return null; // [This will not happen in a correct program.] int playerKing; // The constant for a King belonging to the player. if [player == RED] playerKing = RED_KING; else playerKing = BLACK_KING; ArrayList moves = new ArrayList[]; // Moves will be stored in this list. /* First, check for any possible jumps. Look at each square on the board. If that square contains one of the player's pieces, look at a possible jump in each of the four directions from that square. If there is a legal jump in that direction, put it in the moves ArrayList. */ for [int row = 0; row < 8; row++] { for [int col = 0; col < 8; col++] { if [board[row][col] == player || board[row][col] == playerKing] { if [canJump[player, row, col, row+1, col+1, row+2, col+2]] moves.add[new CheckersMove[row, col, row+2, col+2]]; if [canJump[player, row, col, row-1, col+1, row-2, col+2]] moves.add[new CheckersMove[row, col, row-2, col+2]]; if [canJump[player, row, col, row+1, col-1, row+2, col-2]] moves.add[new CheckersMove[row, col, row+2, col-2]]; if [canJump[player, row, col, row-1, col-1, row-2, col-2]] moves.add[new CheckersMove[row, col, row-2, col-2]]; } } } /* If any jump moves were found, then the user must jump, so we don't add any regular moves. However, if no jumps were found, check for any legal regular moves. Look at each square on the board. If that square contains one of the player's pieces, look at a possible move in each of the four directions from that square. If there is a legal move in that direction, put it in the moves ArrayList. */ if [moves.size[] == 0] { for [int row = 0; row < 8; row++] { for [int col = 0; col < 8; col++] { if [board[row][col] == player || board[row][col] == playerKing] { if [canMove[player,row,col,row+1,col+1]] moves.add[new CheckersMove[row,col,row+1,col+1]]; if [canMove[player,row,col,row-1,col+1]] moves.add[new CheckersMove[row,col,row-1,col+1]]; if [canMove[player,row,col,row+1,col-1]] moves.add[new CheckersMove[row,col,row+1,col-1]]; if [canMove[player,row,col,row-1,col-1]] moves.add[new CheckersMove[row,col,row-1,col-1]]; } } } } /* If no legal moves have been found, return null. Otherwise, create an array just big enough to hold all the legal moves, copy the legal moves from the ArrayList into the array, and return the array. */ if [moves.size[] == 0] return null; else { CheckersMove[] moveArray = new CheckersMove[moves.size[]]; for [int i = 0; i < moves.size[]; i++] moveArray[i] = moves.get[i]; return moveArray; } } // end getLegalMoves

The checkers program is complex, and you can be sure that it didn't just fall together. It took a good deal of design work to decide what classes and objects would be used, what methods should be written, and what algorithms the methods should use. The complete source code is in the file Checkers.java. Take a look!

End of Chapter 7