Lesson 7. Legacy Elements
In this lesson you will learn about legacy elements of Java. Java is a continually evolving language. The original release of Java was immature with respect to both its language features and its class library. Over the years, Sun has added to the language and class library in attempts to provide a more robust platform. Sun has removed little. The result is that Java contains many features that Sun recommends you no longer use.
J2SE 5.0 introduces many new language elements, some that aspire to replace existing Java elements. As the most relevant example, the designers of Java changed the means of iterating through a collection in 5.0. Previously, the language supported iteration through a combination of the class library and procedural looping constructs. Now, the Java language directly supports iteration with the for-each loop.
In this lesson, you will learn about many Java elements that come from its syntactical grandparent, the C language. These elements are largely procedural in nature but are still necessary in order to provide a fully functional programming language. Nonetheless, most of the time you should be able to use constructs that are more object-oriented instead of the legacy elements in this lesson.
While I downplay the use of these legacy elements, you must understand them in order to fully master Java. They remain the underpinnings of the Java language. In many circumstances, you will be forced to use them. And in some cases, they still provide the best solution to the problem at hand.
Some of the legacy elements you will learn about include:
• for, while, and do loops
• looping control statements
• legacy collections
• iterators
• casting
• arrays
• varargs
Each of these elements, with the exception of varargs, has been around since the advent of Java. The concept of collections, Iterators, and wrapper classes are object-oriented constructs. Everything else derives from the C language. The switch statement that you learned in Lesson 6 is also a legacy element that was derived from C.
Looping Constructs
The for loop as you have learned it provides a means of iterating through a collection and operating on each element.
You will need more general-purpose looping. Perhaps you need to execute a body of code infinitely, loop until some condition is met, or send a message ten times. Java meets these needs with three looping constructs: while, do, and for.
Breaking Up a Student's Name
Currently, the Student class supports constructing a student with a single string that represents the student's name. You need to modify the Student class so that it can break apart a single string into its constituent name parts. For example, the Student class should be able to break the name string “Robert Cecil Martin” into a first name “Robert,” a middle name “Cecil,” and a last name “Martin.”
The class should also assume that a string with two name parts represents a first and last name and that a string with one name part represents a last name only.
First, modify the existing testCreate method defined in StudentTest:
You'll need to add fields and create getter methods in Student:
The modified Student constructor code shows your intent of how to solve the problem:
public Student(String fullName) {
this.name = fullName;
credits = 0;
List<String> nameParts = split(fullName);
setName(nameParts);
}
Programming by intention is a useful technique that helps you figure out what you need to do before you figure out how you are going to do it.1 It can be viewed as decomposing the problem into smaller abstractions. You can put these abstractions into code before actually implementing the abstractions. Here, you know that you need to split the full name into different parts, but you don't yet know how.
1 [Astels2003], p. 45.
Use programming by intention to break down a problem into a number of smaller goals.
Once you have figured out how to split the string into a list of up to three name parts, the implementation of setName is straightforward. It involves a few if-else statements. Each if conditional tests the number of name parts available in the list of tokens:
The setName code always sets a value into lastName. However, it does not always set the value of firstName or middleName. You will need to ensure that these fields are properly initialized in Student:
private String firstName = "";
private String middleName = "";
private String lastName;
The while Loop
As usual, Java gives you several ways to solve the problem of splitting the name. You'll start with a more “classic,” more tedious approach. You will loop through each character in the name, looking for space characters, using them to determine where one name part ends and the next name part begins. Later you'll learn a couple of simpler, more-object-oriented solutions.
The split method needs to take the full name as an argument and return a list of tokens as a result. You will use a while loop to derive each token in turn from the string and add it to the result list.
You use the while loop to execute a statement or block of code as long as a condition holds true.
In this example, after Java initializes an index counter to 0, it executes the while loop. As long as the index is less than the string length (index < string.length()), Java executes the body of the while loop (all code between the braces following the while conditional).
The body in this example extracts the character at the current index from the string. It tests whether the character is a space (' ') or not. If not, the character is appended to the current StringBuffer instance. If so, and if there are any characters in the current StringBuffer, the contents of the StringBuffer represent a complete word and are added to the results. A new StringBuffer, to represent a new word, is created and assigned to the word reference.
Each time the body of the while loop completes, control is transferred back up to the while loop conditional. Once the conditional returns a false result, the while loop terminates. Control is then transferred to the statement immediately following the while loop body. In the example, the statement immediately following is an if statement that ensures that the last word extracted becomes part of the results.
The modified test should pass.
Refactoring
The setName method is a bit repetitive. You can refactor it by taking advantage of having the name parts in a list that you can manipulate.
You actually create more lines of code overall with this solution. But you eliminate the duplication and hard-coded indexes rampant in setName. Further, you produce a generic method, removeLast, that later may be a useful abstraction.
The for Loop
Looping using a counter and a limit, as in the previous example, is a common operation. You can more succinctly express this operation by using a variant of the for loop. The for loop allows you to combine three common loop parts into one declaration. Each for loop declaration contains:
• initialization code
• a conditional expression representing whether or not to continue execution of the loop
• an update expression that the Java VM executes each time the loop terminates
You separate each of these three sections in the for loop declaration using a semicolon.
The classic use of a for loop is to execute a body of code a certain number of times. Typically, but not necessarily, the initialization code sets an index to 0, the conditional tests that the index is less than a limit, and the update expression increments the counter by one.
In the for loop example, the initialization code declares index as an int and initializes it to 0. The conditional tests that index is less than the number of characters in the String argument. As long as the condition holds true, Java executes the body of the loop. Subsequent to each time Java executes the loop, Java increments index (index++); it then transfers control back to the conditional. Once the conditional returns false, Java transfers control to the statement following the for loop body.
In the example, Java executes the body of the for loop once for each character in the input string. The index value ranges from zero up to the number of characters in the input string minus one.
Multiple Initialization and Update Expressions in the for Loop
Both the initialization and update code sections allow for multiple expressions separated by commas. The countChars method,2 which returns the number of occurrences of a specified character within a string, shows how you can initialize both the variables i and count to 0.
2 This method and several other methods in this lesson such as the upcoming method isPalindrome, have nothing to do with the student information system. They are here to help demonstrate some of the lesser-seen nuances of Java syntax.
The use of the letter i as a for loop index variable is an extremely common idiom. It is one of the few commonly accepted standards that allows you to abbreviate a variable name. Most developers prefer to use i over a full word such as index.
The following method, isPalindrome, returns true if a string reads backward the same as forward. It shows how you can declare and initialize more than one variable in the initialization code. The method also shows multiple expressions—incrementing forward and decrementing backward—in the update step.
A local variable that you declare in the initialization code of a for loop is valid only for the scope of the for loop. Thus, in the countChars method, you must declare count prior to the loop, since you return count after the for loop.
Java stipulates that “if you have a local variable declaration, each part of the expression after a comma is expected to be a part of that local variable declaration.”3 So while it would be nice to be able to recode countChars to declare i and only initialize count, Java expects the following initialization code to declare both i and count.
3 [Arnold2000].
But since you already declared count before the for loop, the Java compiler rejects the attempt:
count is already defined in countChars(java.lang.String,char)
All three parts of the for loop declaration—initialization, conditional, and update expression—are optional. If you omit the conditional, Java executes the loop infinitely. The following for statement is a common idiom for an infinite loop:
for (;;) {
}
A more expressive way to create an infinite loop is to use a while loop:
while (true) {
}
As mentioned, the most common use for for loops is to count from 0 up to n – 1, where n is the number of elements in a collection. Nothing prohibits you from creating for loops that work differently. The isPalindrome method shows how you can count upward at the same time as counting downward.
Another language test shows how you can have the update expression do something other than decrement or increment the index:
The do Loop
The do loop works like a while loop, except that the conditional to be tested appears at the end of the loop body. You use a do loop to ensure that the you execute the body of a loop at least once.
In the thirteenth century, Leonardo Fibonacci came up with a numeric sequence to represent how rabbits multiply.4 The Fibonacci sequence starts with 0 and 1. Each subsequent number in the sequence is the sum of the two preceding numbers in the sequence. The test and code below demonstrate an implementation of the Fibonacci function using a do loop.
Comparing Java Loops
A way exists to code any looping need using any one of the three loop variants. The following test and three methods show three techniques for displaying a list of numbers separated by commas.
As this example shows, you will find that one of the loop variants is usually more appropriate than the other two. Here, a for loop is best suited since the loop is centered around counting needs.
If you have no need to maintain a counter or other incrementing variable, the while loop will usually suffice. Most of the time, you want to test a condition each and every time upon entry to a loop. You will use the do loop far less frequently. The need to always execute the loop at least once before testing the condition is less common.
Refactoring
isPalindrome
The isPalindrome method expends almost twice as much effort as necessary to determine whether a string is a palindrome. While normally you shouldn't worry about performance until it is a problem, an algorithm should be clean. Doing something unnecessarily in an algorithm demonstrates poor understanding of the problem. It can also confuse future developers.
You only need to traverse the string up to its middle. The current implementation traverses the string for its entire length, which means that all or almost all characters are compared twice. A better implementation:
Fibonacci and Recursion
Java supports recursive method calls. A recursive method is one that calls itself. A more elegant solution for the Fibonacci sequence uses recursion:
Be cautious when using recursion! Make sure you have a way of “breaking” the recursion, otherwise your method will recurse infinitely. You can often use a guard clause for this purpose, as in the fib method (which has two guard clauses).
Looping Control Statements
Java provides additional means for altering control flow within a loop: the continue statement, the break statement, the labeled break statement, and the labeled continue statement.
The break Statement
You may want to prematurely terminate the execution of a loop. If the Java VM encounters a break statement within the body of a loop, it immediately transfers control to the statement following the loop body.
The String class defines a trim method that removes blank characters5 from both ends of a String. You will define another String utility that trims blank characters from only the end of a String.
5 It actually removes whitespace, which includes space characters as well as tab, new line, form feed, and carriage return characters.
The continue Statement
When it encounters a continue statement, Java immediately transfers control to the conditional expression of a loop.
The example calculates the average GPA for part-time students enrolled in a course session. The test, as implemented in SessionTest:
The implementation (in Session) demonstrates use of the continue statement to skip students that are not part-time.
You can easily rewrite this (and most) uses of continue using if-else statements. Sometimes the use of continue provides the more-elegant, easy-to-read presentation.
Labeled break and continue Statements
The labeled break and continue statements allow you to transfer control when you have more complex nesting.
The first example tests a labeled break. Don't let the interesting declaration of table scare you. List<List<Integer>> declares a list into which you can put lists bound to the Integer type.
If you did not associate the search label with the break statement in this example, Java would break out of only the innermost for loop (the one with the expression Integer num: row). Instead, the break statement causes looping to terminate from the search label, representing the outermost loop in this example.
The labeled continue statement works similarly, except the Java VM transfers control to the loop with the label instead of breaking from the loop with the label.
There are few situations where your solution will require labeled break or continue statements. In most cases, you can easily restructure code to eliminate them, either by use of if-else statements or, even better, by decomposition of methods into smaller, more composed methods. Use the labeled statements only when the solution is easier to comprehend.
The Ternary Operator
Lesson 5 introduced the if statement. Often you want to assign a value to a variable or return a value from a method based on the results of an if conditional. For example:
For simple conditional expressions that must return a new value, Java provides a shortcut form known as the ternary operator. The ternary operator compacts the if-else statement into a single expression. The general form of the ternary operator is:
conditional ? true-value : false-value
If conditional returns the value true, the result of the entire expression is true-value. Otherwise the result of the entire expression is false-value. Using the ternary operator, you can rewrite the previous code to produce a message as:
If the value of sessions is 1, the parenthesized ternary expression returns the String "one", otherwise it returns "many". This result string is then used as part of the larger string concatenation.
The ternary operator is a holdover from the language C. Do not use the ternary operator as a general replacement for the if statement! The best use of the ternary operator is for simple, single-line expressions like the one shown here. If you have more complex needs, or if the code won't fit on a single line, you're better off using an if statement. Abuse of the ternary operator can result in cryptic code that is more costly to maintain.
Legacy Collections
Prior to the SDK version 1.2, there was no collections “framework” in Java. Java contained two main workhorse collections—java.util.Vector and java.util.Hashtable6—that still exist today. The analogous classes in modern Java are respectively java.util.ArrayList and java.util.HashMap. The class java.util.HashMap provides similar functionality as the class java.util.EnumMap, with which you are already familiar. Refer to Lesson 9 for more information on HashMap.
6 There were only two other collection classes: BitSit and Stack (a subclass of Vector). Both were minimally useful.
Both Vector and Hashtable are concrete; they implement no common interfaces. They incorporate support for multithreaded programming7 by default, a choice that often results in unnecessary overhead. Unfortunately, today you will still encounter a large amount of code that uses or requires use of the Vector class.
7 See Lesson 13 for a discussion of multithreaded programming.
Since there were no corresponding interfaces for these classes in the initial versions of Java, you were forced to assign Vector or Hashtable instances to a reference to an implementation class:
Vector names = new Vector();
With the introduction of the collections framework, Sun retrofitted the Vector class to implement the List interface and the Hashtable class to implement the Map interface. You might for some reason be stuck with continuing to use a Vector or Hashtable. If so, you may be able to migrate to a modern approach by assigning the instance to an interface reference:
List names = new Vector();
Map dictionary = new Hashtable();
Sun also retrofitted Vector and Hashtable so that they are parameterized types. You can thus code:
List<String> names = new Vector<String>();
Map<Student.Grade,String> dictionary =
new Hashtable<Student.Grade,String>();
Iterators
You have learned to use the for-each loop to iterate through each element in a collection. This form of the for loop is a new construct, introduced in J2SE 5.0.
Prior to the for-each loop, the preferred way to iterate through a collection was to ask it for a java.util.Iterator object. An Iterator object maintains an internal pointer to an element in the collection. You can ask an iterator to return the next available element in the collection. After returning an element from the collection, an Iterator advances its internal pointer to refer to the next available element. You can also ask an iterator whether or not there are more elements in a collection.
As an example, rewrite the averageGpaForPartTimeStudents method shown earlier in this lesson to use an Iterator object and a for loop instead of a for-each loop:
You usually obtain an Iterator by sending the message iterator to the collection. You assign the Iterator object to an Iterator reference that you bind to the type of object stored within the collection. Here, you bind the Iterator to the type Student, which is what the students collection stores.
The Iterator interface defines three methods: hasNext, next, and remove (which is optional and infrequently needed). The hasNext method returns true if there are any elements remaining in the collection that have not yet been returned. The next method returns the next available element from the collection and advances the internal pointer.
The legacy collections Vector and Hashtable use an analogous technique known as enumeration. The solution is virtually the same, only the names are different. Redefine the students instance variable in Session to be a Vector.
Instead of asking for an Iterator using the iterator method, you ask for an Enumeration by using the elements method. You test whether there are more elements available using hasMoreElements instead of hasNext. You retrieve the next element using nextElement instead of next. Sun introduced the Iterator in response to many complaints about the unnecessary verbosity of the class name Enumeration and its method names.
Since Vector implements the List interface, you can send a Vector the iterator message to obtain an Iterator instead of an Enumeration.
Revert your Session code to use modern collections and the for-each loop.
Iterators and the for-each Loop
The for-each loop construct is built upon the Iterator construct. In order to be able to loop through a collection, the collection must be able to return an Iterator object when sent the iterator message. The for-each loop recognizes whether a collection is iterable or not by seeing if the collection implements the java.lang.Iterable interface.
In this upcoming example, you will modify the Session class to support iterating through its collection of students.
Code the following test in SessionTest:
When you compile, you will receive an error, since Session does not yet support the ability to be iterated over.
foreach not applicable to expression type
for (Student student: session)
^
You must change the Session class to implement the Iterable interface. Since you want the for-each loop to recognize that it is iterating over a collection containing only Student types, you must bind the Iterable interface to the Student type.
Now you only need to implement the iterator method in Session. Since Session merely encapsulates an ArrayList of students, there is no reason that the iterator method can't simply return the ArrayList's Iterator object.
public Iterator<Student> iterator() {
return students.iterator();
}
Casting
The need for casting of references occurs when you, the programmer, know that an object is of a certain type but the compiler couldn't possibly know what the type is. Casting allows you to tell the compiler that it can safely assign an object of one type to a reference of a different type.
Sun's introduction of parameterized types removed much of the need for casting in Java. Prior to J2SE 5.0, since the collection classes in Java did not support parameterized types, everything that went into a collection had to go in as an Object reference, as shown by the signature for the add method in the List interface:
public boolean add(Object o)
Since everything went in as an Object, you could only retrieve it as an -Object:
public Object get(int index)
You, the developer, knew you were stuffing Student objects into a collection, but the collection could only store Object references to the Students. When you went to retrieve the objects from the collection, you knew that the collection stored Student objects. This meant that you typically cast the Object references back to Student references as you retrieved them from the collection.
To cast, precede a target expression with the reference type that you want to cast it to, in parentheses:
Student student = (Student)students.get(0);
In this example, the target is the result of the entire expression students.get(0). You could have parenthesized the target to be more explicit:
(Student)(students.get(0));
Note the absence of any spaces between the cast and the target. While you may interject spaces between a cast and its target, the more commonly accepted style specifies no spaces.
It is important to understand that casting does nothing to change the target object. The cast to Student type only creates a new reference to the same memory location. Since this new reference is of type Student, the Java compiler will then allow you to send Student-specific messages to the object via the reference. Without casting, you would only be able to send messages defined in Object to the Student object.
Using parameterized types, there are few reasons to cast object references. If you find yourself casting, determine if there is a way to avoid casting by using parameterized types.
As an exercise, the following test demonstrates the “old way” of iterating through a collection—without a for-each loop and without parameterized types. Note that this code will still work under J2SE 5.0, although you may receive warnings because you are not using the parameterized collection types.
Casting Primitive Types
You cannot cast primitive types to reference types or vice versa.
There is another form of casting that you will still need to use in order to convert numeric types. I will discuss numeric conversion in Lesson 10 on mathematics.
Wrapper Classes
The student system must store student charges in a collection to be totaled later. Each charge is an int that represents the number of cents a student spent on an item.
Remember that primitive types are not objects—they do not inherit from the class java.lang.Object. The java.util.List interface only supplies an add method that takes a reference type as a argument. It does not supply overloaded add methods for each of the primitive types.
In order to store the int charge in a collection, then, you must convert it to an object. You accomplish this by storing the int in a wrapper object.
For each primitive type, java.lang defines a corresponding wrapper class.8
8 The table lists all available primitive types and corresponding wrappers. You will learn more about the unfamiliar types in Lesson 10.
Each wrapper class provides a constructor that takes a primitive of the appropriate type as argument. The wrapper stores this primitive and allows for extracting it using a corresponding getter method. In the case of the Integer wrapper, you extract the original int by sending the message intValue to the wrapper.
A test (in StudentTest) for the example:
public void testCharges() {
Student student = new Student("a");
student.addCharge(500);
student.addCharge(200);
student.addCharge(399);
assertEquals(1099, student.totalCharges());
}
If you had to write the implementation using pre-J2SE 5.0 code, it would look something like this:
The addCharge method shows how you would wrap the int in an instance of the Integer wrapper class in order to pass it to the add method of the charges collection. When iterating through the collection (in totalCharges), you would have to cast each retrieved Object to the Integer wrapper class. Only then would you be able to extract the original int value through use of the intValue method.
J2SE 5.0 simplifies the code through the use of parameterized types and the for-each loop.
In addition to allowing you to wrap a primitive, the wrapper classes provide many class methods that operate on primitives. Without the wrapper classes, these methods would have nowhere to go. You have already used the Character class method isWhitespace.
A further simplification of the code comes about from one of the new J2SE 5.0 features, autoboxing.
Autoboxing and Autounboxing
Autoboxing is the compiler's ability to automatically wrap, or “box” a primitive type in its corresponding wrapper class. Autoboxing only occurs when Java can find no method with a matching signature. A signature match occurs when the name and arguments of a message send match a method defined on the class of the object to which the message is being sent. An argument is considered to match if the types match exactly or if the type of the argument is a subtype of the argument type as declared in the method.
As an example, if Box declares a method as:
void add(List list) {... }
then any of the following message sends will resolve to this add method:
Box b = new Box();
b.add(new List());
b.add(new ArrayList());
The second add message send works because ArrayList is a subclass of List.
If Java finds no direct signature match, it attempts to find a signature match based on wrapping. Any method with an Object argument in the appropriate place is a match.
In the addCharge method, the explicit wrapping of the int into an Integer is no longer necessary:
public void addCharge(int charge) {
charges.add(charge);
}
It is important for you to understand that the wrapping does occur behind the scenes. Java creates a new Integer instance for each primitive value you wrap.
Autoboxing only occurs on arguments. It would be nice if autoboxing occurred anywhere you attempted to send a message to a primitive. This is not yet a capability, but it would allow expressions like:
6.toString() // this does not work
Autounboxing occurs when you attempt to use a wrapped primitive anywhere a primitive is expected. This is demonstrated in the following two tests:
The more useful application of autounboxing is when you extract elements from a collection bound to a primitive wrapper type. With both autoboxing and autounboxing, the charge code in Student becomes:
You will learn about addition capabilities of wrapper classes in Lesson 10 on mathematics.
Arrays
I have mentioned arrays several times in this book. An array is a fixed-size, contiguous set of slots in memory. Unlike an ArrayList or other collection object, an array can fill up, preventing you from adding more elements. The only way to add elements to a full array is to create a second larger array and copy all elements from the first array to the second array.
Java provides special syntactical support for arrays. Indirectly, you have been using arrays all along, in the form of the class ArrayList. An ArrayList stores all elements you add to it in a Java array. The ArrayList class also encapsulates the tedium of having to grow the array when you add too many elements.
The example here creates a new class named Performance, which CourseSession might use to track test scores for each student. The Performance class allows calculating the average across all tests.
The Performance class:
You store the scores for the tests in an int array named tests:
private int[] tests;
This declaration only says that the instance variable tests is of type int[] (you read this as “int array”). The braces are the indicator that this is an array. You use the braces to subscript, or index, the array. By subscripting the array, you tell Java the index of the element with which you wish to work.
Java allows you to declare an array with the braces following the variable.
private int tests[]; // don't declare arrays this way
Avoid this construct. Use of it will brand you as a C/C++ programmer (a fate worse than death in Java circles).
Neither of the two array declarations above allocate any memory. You will receive an error9 if you reference any of its (nonexistent) elements.
9 Specifically, a NullPointerException. See Lesson 8 for more information on exceptions.
When a Performance client calls setNumberOfTests, the assignment statement initializes the test array.
public void setNumberOfTests(int numberOfTests) {
tests = new int[numberOfTests];
}
You allocate an array using the new keyword. After the new keyword, you specify the type (int in this example) that the array will hold and the number of slots to allocate (numberOfTests).
Once you initialize an array, you can set a value into any of its slots. The type of the value must match the type of the array. For example, you can only set int values into an int[].
public void set(int testNumber, int score) {
tests[testNumber] = score;
}
The line of code in set assigns the value of score to the slot in the tests array that corresponds to the testNumber. Indexing of arrays is 0-based. The first slot is slot #0, the second slot #1, and so on.
The get method demonstrates accessing an element in an array at a particular index:
public int get(int testNumber) {
return tests[testNumber];
}
You can iterate an array like any other collection by using a for-each loop.
public double average() {
double total = 0.0;
for (int score: tests)
total += score;
return total / tests.length;
}
The average method also shows how you may access the number of elements in an array by using a special variable named length.
You can iterate an array using a classic for loop:
public double average() {
double total = 0.0;
for (int i = 0; i < tests.length; i++)
total += tests[i];
return total / tests.length;
}
You may declare an array as any type, reference or primitive. You might have an instance variable representing an array of Students:
private Student[] students;
Array Initialization
When you allocate an array, Java initializes its elements to the default value for the type. Java initializes all slots in an array of numerics to 0, to false in an array of booleans, and to null in an array of references.
Java provides special array initialization syntax that you can use at the time of array instantiation and/or declaration.
public void testInitialization() {
Performance performance = new Performance();
performance.setScores(75, 72, 90, 60);
assertEquals(74.25, performance.average(), tolerance);
}
The setScores method passes each of the four score arguments into an array initializer.
The array initializer in this example produces an array with four slots, each populated with an int value.
A shortcut that you can use as part of an array declaration assignment statement is:
int[] values = {1, 2, 3 };
You may terminate the list of values in an array initializer with a comma. The Java compiler ignores the final comma (it does not create an additional slot in the array). For example, the preceding declaration and initialization is equivalent to:
I coded the initialization on multiple lines to help demonstrate why this feature might be useful. It allows you to freely add to, remove from, and move elements around in the array initialization. You need not worry about leaving a comma after the last element; you can terminate each element with a comma.
When to Use Arrays
Prefer use of Java reference-type collections over native arrays. Your code will be simpler, closer to pure OO, and more flexible. It is easy to replace an ArrayList with a LinkedList, but it can be very costly to have to replace a native array with a LinkedList.
Some situations will force you into using arrays. Many existing APIs either return arrays or require arrays as arguments.
There are circumstances where arrays are more appropriate. Many mathematical algorithms and constructs (matrices, for example) are better implemented with arrays.
Accessing an element in an array is a matter of knowing which numbered slot it's in, multiplying by the slot size, and adding to some memory offset. The pseudo–memory diagram in Figure 7.1 shows a three-element int array. Java stores the starting location of the array in this example as 0x100. To access the third element of the array (x[2]), Java calculates the new memory location as:
0x100 starting address + 2nd slot * 4 bytes per slot
Figure 7.1. An Array in Memory
Each slot requires four bytes, since it takes four bytes to represent an int.10 The result is the address 0x108, where the element 55 can be found.
10 Java stores primitive types directly in the array. An array of objects would store a contiguous list of references to other locations in memory.
If you need the absolute fastest performance possible, an array provides a performance improvement over a collection class. However, prefer the use of collection classes over arrays. Always measure performance before arbitrarily converting use of a collection class to an array.
Prefer object-oriented collections over arrays.
Varargs
If you want to pass a variable number of similar-typed arguments to a method, you must first combine them into a collection. The setScores method above is restricted to four test scores; you would like to be able to pass any number of scores into a Performance object. Prior to J2SE 5.0, a standard idiom for doing so was to declare a new array on the fly:
public void testArrayParm() {
Performance performance = new Performance();
performance.setScores(new int[] {75, 72, 90, 60 });
assertEquals(74.25, performance.average(), tolerance);
}
The setScores method can then store the array directly:
public void setScores(int[] tests) {
this.tests = tests;
}
You might try to use the shorter array declaration/initialization syntax:
performance.setScores({ 75, 72, 90, 60 }); // this will not compile
but Java does not allow it.
J2SE 5.0 allows you to specify that a method takes a variable number of arguments. The arguments must appear at the end of the method argument list and must all be of the same type.
You declare the variability of a parameter with ellipses (...). Programmers familiar with C refer to this as a varargs declaration.
public void setScores(int... tests) {
this.tests = tests;
}
Method calls to setScores can now have a variable number of test scores:
public void testVariableMethodParms() {
Performance performance = new Performance();
performance.setScores(75, 72, 90, 60);
assertEquals(74.25, performance.average(), tolerance);
performance.setScores(100, 90);
assertEquals(95.0, performance.average(), tolerance);
}
When you execute a Java application, the VM passes command-line arguments to the main method as an array of String objects:
public static void main(String[] args)
You can declare the main method too as:
public static void main(String... args)
Multidimensional Arrays
Java also supports arrays of arrays, also known as multidimensional arrays. A classic use of multidimensional arrays is to represent matrices. You can create arrays that have up to 255 dimensions, but you will probably never need more than 3 dimensions. The following language test demonstrates how you allocate, populate, and access a two-dimensional array.
You do not need to allocate all dimensions at once. You can allocate dimensions starting at the left, leaving the rightmost dimensions unspecified. Later, you can allocate these rightmost dimensions. In testPartialDimensions, the code initially allocates matrix as an int array of three rows. Subsequently, it allocates each slot in the rows portion of the array to differing-sized int arrays of columns.
As shown in testPartialDimensions, Java does not restrict you to rectangular multidimensional arrays; you can make them jagged.
You can initialize multidimensional arrays using array initialization syntax. The following initialization produces an array that is equivalent to the array initialized by testPartialDimensions:
int[][] matrix2 = {{0 }, {1, 2 }, {3, 4, 5 }};
The Arrays Class
Since arrays are not objects, you cannot send messages to them. You can access the variable length to determine the size of an array, but Java provides it as special syntax.
The class java.util.Arrays gives you a number of class methods to perform common operations on arrays. Using the Arrays class, you can do the following with a single-dimensional array:
• perform binary searches (which assumes the array is in sorted order) (binarySearch)
• convert it to an object that implements the List interface (asList)
• compare it to another single-dimensional array of the same type (equals)
• obtain a hash code (see Lesson 9) (hashCode)
• fill each of its elements, or a subrange of its elements, with a specified value (fill)
• obtain a printable representation of the array (toString)
I'll discuss the equals method in more depth. For more information about the other methods, refer to the Java API documentation for more information on java.util.Arrays.
Arrays.equals
An array is a reference type, regardless of whether you declare it to contain primitives or references. If you create two separate arrays, the Java VM will store them in separate memory locations. This means that comparing the two arrays with == will result in false.
public void testArrayEquality() {
int[] a = {1, 2, 3 };
int[] b = {1, 2, 3 };
assertFalse(a == b);
}
Since an array is a reference, you can compare two arrays using the equals method. But even if you allocate both arrays to exactly same dimensions and populate them with exactly the same contents, the comparison will return false.
public void testArrayEquals() {
int[] a = {1, 2, 3 };
int[] b = {1, 2, 3 };
assertFalse(a.equals(b));
}
You can use the Arrays.equals method to compare the contents, not the memory location, of two arrays.
public void testArraysEquals() {
int[] a = {1, 2, 3 };
int[] b = {1, 2, 3 };
assertTrue(Arrays.equals(a, b));
}
Refactoring
Splitting a String
While either the hand-coded while loop or for loop in the Student method split will work, the resulting code is fairly complex. Java provides at least two more ways to break apart String objects into tokens. First, you will learn how to use the StringTokenizer class to break an input string into individual components, or tokens. The StringTokenizer class is considered a legacy class, meaning that Sun wants you to supplant its use with something better. That something better is the split method, defined on String. Once you have coded the solution using StringTokenizer, you will recode it to use String.split.
Up until Java 1.4, Sun recommended the StringTokenizer as the solution for tokenizing strings. You will still encounter a lot of code that uses StringTokenizer; that's why you'll learn it here. In Java 1.4, Sun introduced the regular expressions API. Regular expressions are specifications for pattern-matching against text. A robust, standardized language defines the patterns you can express with regular expressions. The newer String.split method uses a regular expression, making it far more effective than the StringTokenizer solution. For more information about the regular expressions API, see Additional Lesson III.
The constructor for the class java.util.StringTokenizer takes as parameters an input String and a String representing a list of character delimiters. StringTokenizer then breaks the input String into tokens, allowing you to iterate through each token in turn. The while loop provides the best mechanism for traversing these tokens:
Sending the message hasMoreTokens to a StringTokenizer returns false once there are no more tokens. The message nextToken returns the next token available. The StringTokenizer code uses the list of delimiters to determine what separates tokens. The example here uses only the space character to delineate tokens.
Splitting a String: String.split
The String class contains a split method that makes the job of tokenizing a full name even simpler than using StringTokenizer. Using String.split would allow you to eliminate your entire Student.split method with one line of code.
Here is a stab at the refactoring:
Part of your goal should be to make changes with as little impact to other code as possible. The single line of code that now appears in your split method seems like it should do the trick:
return Arrays.asList(name.split(" ")); // this doesn't work!
The split method takes a single parameter, the list of characters that represent word boundaries. It returns an array of words. The Arrays class method asList takes an array and returns a List representation of that array.
One would think that this line of code would be a suitable replacement for the previous code that constructed the list using StringTokenizer. But it -doesn't work. You will receive many JUnit errors indicating that the remove call in your removeLast method now generates something known as an UnsupportedOperationException.
The problem is in the Arrays method asList. According to the Java API documentation for asList, it returns a list backed by the array you pass as parameter. The list is a view onto the array, which does not go away. The list reflects any changes you make to the array.
Since the list is backed by an array, and since you cannot remove elements from an array, Java prohibits the remove call.
A solution that will work is to iterate through the results of split using a for-each loop. As with the StringTokenizer solution, you can add each word to a results array.
private List<String> split(String fullName) {
List<String> results = new ArrayList<String>();
for (String name: fullName.split(" "))
results.add(name);
return results;
}
The split method uses a Java feature known as regular expressions. A regular expression is a set of syntactical elements and symbols that is used to match text. You have likely used a simple form of regular expression when listing files in a directory. You use the asterisk (*) as a wildcard symbol to match any sequence of characters in a filename. See Additional Lesson III for an overview of the powerful regular expressions feature.
Exercises
- To see the different loop types in action, code the factorial algorithm (without using recursion). The definition of factorial:
if n is 0, n factorial = 1.
if n is 1, n factorial = 1.
if n is greater than one, n factorial is 1 * 2 * 3 * ... up to nCode the tests, then create a factorial method using a
whileloop. Next, modify the same method to pass the tests without using thewhilekeyword, but instead using the C-styleforloop. Finally, recode it again using thedo-whileloop. Notice the changes you must make in order to use the different loop structures. Also note that you only need one loop structure to solve any looping problem.a) Why would you prefer one loop structure over the others?
b) Which is shortest?
c) Which is the most appropriate to this problem? Why?
d) Replace the loop with
while (true) {and get the test to pass using the
breakkeyword to end the loop. - Demonstrate your understanding of the
continuekeyword. Create a method to return a string containing the numbers from 1 to n. Separate each pair of numbers with a single space. Append an asterisk to the numbers divisible by five. For example, setting n to 12 would result in the string:"1 2 3 4 5* 6 7 8 9 10* 11 12".
- a) Break the results of the string from the previous exercise into a Vector of substrings. Split the string on the space character. The string
"1 2 3 4 5* 6 7"would split into a Vector containing the strings"1","2","3","4","5*","6", and"7".b) Iterate through the elements of the vector using an Enumeration and recreate the string from Exercise #2.
c) Remove all parameterized type information, note the compiler errors, and correct the code where necessary.
- In an earlier exercise, you wrote a test to ensure that the list of valid moves for a given piece contained a set of squares. Simplify this assertion to something like:
Refactor other tests to use this mechanism.
- You may have noticed that the chess board you have spent so much time on is really a two-dimensional array of squares. Back up your Board class. Modify Board to use a two-dimensional array as its underlying data structure.
One bit of difficulty you may encounter is due to the fact that client code (such as Game and Pawn) uses the implementation specifics of the board. For this exercise, modify the client code to loop through the ranks and files of the two-dimensional array. This is a less-than-ideal situation: Normally you want to design a solid public interface to your class, one that does not change. When you change the implementation details of the Board class, the Game class should not be affected.
The alternative would be to dynamically convert the Piece two--dimensional array to a List of List of Piece objects each time a client wanted to iterate through it. But the best solution is to not require the client to do the iteration themselves. One sophisticated (and somewhat complex) solution to accomplish this involves the visitor design pattern. See the book Design Patterns11 for further information. For now, exposing the board's underlying two-dimensional array will -suffice.
Compare and contrast the two Board versions. Which is easier to read and understand? Which involves the least code?
- Make the Board class iterable, so that you can access the pieces (not including “no piece” objects) using a
for-eachloop. A complex solution would involve creating a separate Iterator class that tracks both a rank and file index. A simpler solution would involve looping through the board's matrix and adding each piece to a List object. You could then return the iterator from the List object.Once you have made the class iterable, go back and change any code that loops through all pieces to use a
for-eachloop. Look for opportunities to refactor code so that you use thefor-eachloop as much as possible. For example, if you haven't already, modify your code so that each Piece object stores its current rank and file. - Read the javadoc API for the ArrayList class and determine a way to simplify the last example in the chapter—the one that splits the student name and returns a List of name parts. It is possible to recode the
splitmethod without the use of a loop at all! Hint: Look at the constructors for ArrayList.