text:
The Way of the Java/Iteration

Multiple assignment
I have not said much about it, but it is legal in Java to make more than one assignment to the same variable. The effect of the second assignment is to replace the old value of the variable with a new value.

The output of this program is 57, because the first time we print fred his value is 5, and the second time his value is 7.

This kind of multiple assignment is the reason I described variables as a container for values. When you assign a value to a variable, you change the contents of the container.

When there are multiple assignments to a variable, it is especially important to distinguish between an assignment statement and a statement of equality. Because Java uses the = symbol for assignment, it is tempting to interpret a statement like a = b as a statement of equality. (a==b) is a statement of equality!

First of all, equality is commutative, and assignment is not. For example, in mathematics if a = b then b = a. But in Java, a = 7 is a legal assignment statement, and 7 = a; is not.

Furthermore, in mathematics, a statement of equality is true for all time. If a==b now, then a will always equal b. In a computer program, however, variables are intrinsically inconsistent. In Java, an assignment statement can make two variables equal, but they do not have to stay that way!

The third line changes the value of a but it does not change the value of b, and so they are no longer equal. In many programming languages an alternate symbol is used for assignment, such as <- or :=, in order to avoid this confusion.

Although multiple assignment is frequently useful, you should use it with caution. If the values of variables are changing constantly in different parts of the program, it can make the code difficult to read and debug.

Loops
One of the things computers are often used for is the automation of repetitive tasks. Repeating identical or similar tasks without making errors is something that computers do well and people do poorly.

We have already seen programs that use recursion to perform repetition, such as nLines and countdown. This type of repetition is called iteration, and Java provides several language features that make it easier to write iterative programs.

The two features we are going to look at are the while statement and the for statement.

The while statement
Using a while statement, we can rewrite countdown:

You can almost read a while statement as if it were English. What this means is, ''While n is greater than zero, continue printing the value of n and then reducing the value of n by 1. When you get to zero, print the word "Blastoff!"'''

More formally, the flow of execution for a while statement is as follows:
 * 1) Evaluate the condition in parentheses, yielding true or false.
 * 2) If the condition is false, exit the while statement and continue execution at the next statement.
 * 3) If the condition is true, execute each of the statements between the squiggly-brackets, and then go back to step 1.

This type of flow is called a loop because the third step loops back around to the top. Notice that if the condition is false the first time through the loop, the statements inside the loop are never executed. The statements inside the loop are sometimes called the body of the loop.

The body of the loop should change the value of one or more variables so that, eventually, the condition becomes false and the loop terminates. Otherwise the loop will repeat forever, which is called an infinite loop. An endless source of amusement for computer scientists is the observation that the directions on shampoo, Lather, rinse, repeat, are an infinite loop.

In the case of countdown, we can prove that the loop will terminate because we know that the value of n is finite, and we can see that the value of n gets smaller each time through the loop (each iteration), so eventually we have to get to zero. In other cases it is not so easy to tell:

The condition for this loop is n != 1, so the loop will continue until n is 1, which will make the condition false.

At each iteration, the program prints the value of n and then checks whether it is even or odd. If it is even, the value of n is divided by two. If it is odd, the value is replaced by n * 3 + 1. For example, if the starting value (the argument passed to sequence) is 3, the resulting sequence is: 3, 10, 5, 16, 8, 4, 2, 1.

Since n sometimes increases and sometimes decreases, there is no obvious proof that n will ever reach 1, or that the program will terminate. For some particular values of n, we can prove termination. For example, if the starting value is a power of two, then the value of n will be even every time through the loop, until we get to 1. The previous example ends with such a sequence, starting with 16.

Particular values aside, the interesting question is whether we can prove that this program terminates for all values of n. So far, no one has been able to prove it or disprove it!

Tables
One of the things loops are good for is generating and printing tabular data. For example, before computers were readily available, people had to calculate logarithms, sines and cosines, and other common mathematical functions by hand.

To make that easier, there were books containing long tables where you could find the values of various functions. Creating these tables was slow and boring, and the result tended to be full of errors.

When computers appeared on the scene, one of the initial reactions was, ''This is great! We can use the computers to generate the tables, so there will be no errors.'' That turned out to be true (mostly), but shortsighted. Soon thereafter computers (and calculators) were so pervasive that the tables became obsolete.

Well, almost. It turns out that for some operations, computers use tables of values to get an approximate answer, and then perform computations to improve the approximation. In some cases, there have been errors in the underlying tables, most famously in the table the original Intel Pentium used to perform floating-point division.

Although a log table is not as useful as it once was, it still makes a good example of iteration. The following program prints a sequence of values in the left column and their logarithms in the right column:

The output of this program is: 1.0  0.0 2.0   0.6931471805599453 3.0   1.0986122886681098 4.0   1.3862943611198906 5.0   1.6094379124341003 6.0   1.791759469228055 7.0   1.9459101490553132 8.0   2.0794415416798357 9.0   2.1972245773362196

Looking at these values, can you tell what base the log function uses by default?

Since powers of two are so important in computer science, we often want to find logarithms with respect to base 2. To find that, we have to use the following formula:

_2 x = log_e x / log_e 2

Changing the print statement to:

yields: 1.0  0.0 2.0   1.0 3.0   1.5849625007211563 4.0   2.0 5.0   2.321928094887362 6.0   2.584962500721156 7.0   2.807354922057604 8.0   3.0 9.0   3.1699250014423126

We can see that 1, 2, 4 and 8 are powers of two, because their logarithms base 2 are round numbers. If we wanted to find the logarithms of other powers of two, we could modify the program like this:

Now instead of adding something to x each time through the loop, which yields an arithmetic sequence, we multiply x by something, yielding a geometric sequence. The result is: 1.0  0.0 2.0   1.0 4.0   2.0 8.0   3.0 16.0   4.0 32.0   5.0 64.0   6.0

Log tables may not be useful any more, but for computer scientists, knowing the powers of two is! Some time when you have an idle moment, you should memorize the powers of two up to 65536 (that is 2^16).

Two-dimensional tables
A two-dimensional table is a table where you choose a row and a column and read the value at the intersection. A multiplication table is a good example. Let's say you wanted to print a multiplication table for the values from 1 to 6.

A good way to start is to write a simple loop that prints the multiples of 2, all on one line.

The first line initializes a variable named i, which is going to act as a loop counter. As the loop executes, the value of i increases from 1 to 6, and then when i is 7, the loop terminates. Each time through the loop, we print the value 2*i followed by three spaces. Since we are using the print command rather than println, all the output appears on a single line.

As I mentioned in Section printing, in some environments the output from print gets stored without being displayed until println is invoked. If the program terminates, and you forget to invoke println, you may never see the stored output.

The output of this program is: 2  4   6   8   10   12

So far, so good. The next step is to encapsulate and generalize.

Encapsulation and generalization
Encapsulation usually means taking a piece of code and wrapping it up in a method, allowing you to take advantage of all the things methods are good for. We have seen two examples of encapsulation, when we wrote printParity in Section alternative and isSingleDigit in Section boolean.

Generalization means taking something specific, like printing multiples of 2, and making it more general, like printing the multiples of any integer.

Here is a method that encapsulates the loop from the previous section and generalizes it to print multiples of n.

To encapsulate, all I had to do was add the first line, which declares the name, parameter, and return type. To generalize, all I had to do was replace the value 2 with the parameter n.

If I invoke this method with the argument 2, I get the same output as before. With argument 3, the output is: 3  6   9   12   15   18

and with argument 4, the output is: 4  8   12   16   20   24

By now you can probably guess how we are going to print a multiplication table: we'll invoke printMultiples repeatedly with different arguments. In fact, we are going to use another loop to iterate through the rows.

First of all, notice how similar this loop is to the one inside printMultiples. All I did was replace the print statement with a method invocation.

The output of this program is: 1  2   3   4   5   6 2   4   6   8   10   12 3   6   9   12   15   18 4   8   12   16   20   24 5   10   15   20   25   30 6   12   18   24   30   36

which is a (slightly sloppy) multiplication table. If the sloppiness bothers you, Java provides methods that give you more control over the format of the output, but I am not going to get into that here.

Methods
In the last section I mentioned all the things methods are good for. About this time, you might be wondering what exactly those things are. Here are some of the reasons methods are useful:
 * By giving a name to a sequence of statements, you make your program easier to read and debug.
 * Dividing a long program into methods allows you to separate parts of the program, debug them in isolation, and then compose them into a whole.
 * Methods facilitate both recursion and iteration.
 * Well-designed methods are often useful for many programs. Once you write and debug one, you can reuse it.

More encapsulation
To demonstrate encapsulation again, I'll take the code from the previous section and wrap it up in a method:

The process I am demonstrating is a common development plan. You develop code gradually by adding lines to main or someplace else, and then when you get it working, you extract it and wrap it up in a method.

The reason this is useful is that you sometimes do not know when you start writing exactly how to divide the program into methods. This approach lets you design as you go along.

Local variables
About this time, you might be wondering how we can use the same variable i in both printMultiples and printMultTable. Didn't I say that you can only declare a variable once? And doesn't it cause problems when one of the methods changes the value of the variable?

The answer to both questions is no, because the i in printMultiples and the i in printMultTable are not the same variable. They have the same name, but they do not refer to the same storage location, and changing the value of one of them has no effect on the other.

Variables that are declared inside a method definition are called local variables because they are local to their own methods. You cannot access a local variable from outside its home method, and you are free to have multiple variables with the same name, as long as they are not in the same method.

It is often a good idea to use different variable names in different methods, to avoid confusion, but there are good reasons to reuse names. For example, it is common to use the names i, j and k as loop variables. If you avoid using them in one method just because you used them somewhere else, you will probably make the program harder to read.

More generalization
As another example of generalization, imagine you wanted a program that would print a multiplication table of any size, not just the 6x6 table. You could add a parameter to printMultTable:

I replaced the value 6 with the parameter high. If I invoke printMultTable with the argument 7, I get: 1  2   3   4   5   6 2   4   6   8   10   12 3   6   9   12   15   18 4   8   12   16   20   24 5   10   15   20   25   30 6   12   18   24   30   36 7   14   21   28   35   42

which is fine, except that I probably want the table to be square (same number of rows and columns), which means I have to add another parameter to printMultiples, to specify how many columns the table should have.

Just to be annoying, I will also call this parameter high, demonstrating that different methods can have parameters with the same name (just like local variables):

and you get: 1 2  4 3   6   9 4   8   12   16 5   10   15   20   25 6   12   18   24   30   36 7   14   21   28   35   42   49

I'll leave it up to you to figure out how it works.

Glossary

 * loop A statement that executes repeatedly while or until some condition is satisfied.
 * infinite loop A loop whose condition is always true.
 * body The statements inside the loop.
 * iteration One pass through (execution of) the body of the loop, including the evaluation of the condition.
 * encapsulate To divide a large complex program into components (like methods) and isolate the components from each other (for example, by using local variables).
 * local variable A variable that is declared inside a method and that exists only within that method. Local variables cannot be accessed from outside their home method, and do not interfere with any other methods.
 * generalize To replace something unnecessarily specific (like a constant value) with something appropriately general (like a variable or parameter). Generalization makes code more versatile, more likely to be reused, and sometimes even easier to write.
 * development plan A process for developing a program. In this chapter, I demonstrated a style of development based on developing code to do simple, specific things, and then encapsulating and generalizing. In Section distance I demonstrated a technique I called incremental development. In later chapters I will suggest other styles of development.

title: The Way of the Java/Iteration


text:
The Way of the Java/Strings and things

Invoking methods on objects
In Section graphics we used a Graphics object to draw circles in a window, and I used the phrase invoke a method on an object, to refer to the statements like:

In this case drawOval is the method being invoked on the object named g. At the time I did not provide a definition of object, and I still cannot provide a complete definition, but it is time to try.

object
In Java and other object-oriented languages, objects are collections of related data that come with a set of methods. These methods operate on the objects, performing computations and sometimes modifying the object's data.

So far we have only seen one object, g, so this definition might not mean much yet. Another example is Strings. Strings are objects (and ints and doubles are not). Based on the definition of object, you might ask What is the data contained in a String object? and What are the methods we can invoke on String objects?

The data contained in a String object are the letters of the string. There are quite a few methods that operate on Strings, but I will only use a few in this book. The rest are documented at the java site

The first method we will look at is charAt, which allows you to extract letters from a String. In order to store the result, we need a variable type that can store individual letters (as opposed to strings). Individual letters are called characters, and the variable type that stores them is called char.

char
chars work just like the other types we have seen:

Character values appear in single quotes ('c'). Unlike string values (which appear in double quotes), character values can contain only a single letter or symbol.

Here is how the charAt method is used:

The syntax fruit.charAt indicates that I am invoking the charAt method on the object named fruit.

I am passing the argument 1 to this method, which indicates that I would like to know the first letter of the string. The result is a character, which is stored in a char named letter. When I print the value of letter, I get a surprise: a

"a" is not the first letter of "banana". Unless you are a computer scientist. For perverse reasons, computer scientists always start counting from zero. The 0th letter (zeroeth) of "banana" is "b". The 1th letter (oneth) is "a" and the 2th (twoeth) letter is "n".

If you want the zeroth letter of a string, you have to pass zero as an argument:

Length
The second String method we'll look at is length, which returns the number of characters in the string. For example:

length takes no arguments, as indicated by, and returns an integer, in this case 6. Notice that it is legal to have a variable with the same name as a method (although it can be confusing for human readers).

To find the last letter of a string, you might be tempted to try something like:

That won't work. The reason is that there is no 6th letter in "banana". Since we started counting at 0, the 6 letters are numbered from 0 to 5. To get the last character, you have to subtract 1 from length.

Traversal
A common thing to do with a string is start at the beginning, select each character in turn, do something to it, and continue until the end. This pattern of processing is called a traversal. A natural way to encode a traversal is with a while statement:

This loop traverses the string and prints each letter on a line by itself. Notice that the condition is index < fruit.length, which means that when index is equal to the length of the string, the condition is false and the body of the loop is not executed. The last character we access is the one with the index fruit.length-1.

The name of the loop variable is index. An index is a variable or value used to specify one member of an ordered set (in this case the set of characters in the string). The index indicates (hence the name) which one you want. The set has to be ordered so that each letter has an index and each index refers to a single character.

As an exercise, write a method that takes a String as an argument and that prints the letters backwards, all on one line.

Run-time errors
Way back in Section run-time I talked about run-time errors, which are errors that do not appear until a program has started running. In Java run-time errors are called exceptions.

So far, you probably have not seen many run-time errors, because we have not been doing many things that can cause one. Well, now we are. If you use the charAt command and you provide an index that is negative or greater than length-1, you will get an exception: specifically, a StringIndexOutOfBoundsException. Try it and see how it looks.

If your program causes an exception, it prints an error message indicating the type of exception and where in the program it occurred. Then the program terminates.

Reading documentation
If you go to:
 * http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html

and click on charAt, you get the following documentation (or something like it): public char charAt(int index) Returns the character at the specified index. An index ranges from 0 to length - 1. Parameters: index - the index of the character. Returns: the character at the specified index of this string. The first character is at index 0. Throws: StringIndexOutOfBoundsException if the index is out of range. verbatim

The first line is the method's prototype (see Section prototype), which indicates the name of the method, the type of the parameters, and the return type.

The next line describes what the method does. The next two lines explain the parameters and return values. In this case the explanations are a bit redundant, but the documentation is supposed to fit a standard format. The last line explains what exceptions, if any, can be caused by this method.

The indexOf method
In some ways, indexOf is the opposite of charAt. charAt takes an index and returns the character at that index. indexOf takes a character and finds the index where that character appears.

charAt fails if the index is out of range, and causes an exception. indexOf fails if the character does not appear in the string, and returns the value -1.

This finds the index of the letter 'a' in the string. In this case, the letter appears three times, so it is not obvious what indexOf should do. According to the documentation, it returns the index of the first appearance.

In order to find subsequent appearances, there is an alternate version of indexOf (for an explanation of this kind of overloading, see Section overloading). It takes a second argument that indicates where in the string to start looking. If we invoke

it will start at the twoeth letter (the first n) and find the second a, which is at index 3. If the letter happens to appear at the starting index, the starting index is the answer. Thus, returns 5. Based on the documentation, it is a little tricky to figure out what happens if the starting index is out of range:

indexOf returns the index of the first occurrence of the character in the character sequence represented by this object that is greater than or equal to fromIndex, or -1 if the character does not occur.

One way to figure out what this means is to try out a couple of cases. Here are the results of my experiments:
 * If the starting index is greater than or equal to length, the result is -1, indicating that the letter does not appear at any index greater than the starting index.
 * If the starting index is negative, the result is 1, indicating the first appearance of the letter at an index greater than the starting index.

If you go back and look at the documentation, you'll see that this behavior is consistent with the definition, even if it was not immediately obvious. Now that we have a better idea how indexOf works, we can use it as part of a program.

Looping and counting
The following program counts the number of times the letter 'a' appears in a string:

This program demonstrates a common idiom, called a counter. The variable count is initialized to zero and then incremented each time we find an 'a' (to increment is to increase by one; it is the opposite of decrement, and unrelated to excrement, which is a noun). When we exit the loop, count contains the result: the total number of a's.

As an exercise, encapsulate this code in a method named countLetters, and generalize it so that it accepts the string and the letter as arguments.

As a second exercise, rewrite the method so that it uses indexOf to locate the a's, rather than checking the characters one by one.

Increment and decrement operators
Incrementing and decrementing are such common operations that Java provides special operators for them. The ++ operator adds one to the current value of an int or char. -- subtracts one. Neither operator works on doubles, booleans or Strings.

Technically, it is legal to increment a variable and use it in an expression at the same time. For example, you might see something like:

Looking at this, it is not clear whether the increment will take effect before or after the value is printed. Because expressions like this tend to be confusing, I would discourage you from using them. In fact, to discourage you even more, I am not going to tell you what the result is. If you really want to know, you can try it.

Using the increment operators, we can rewrite the letter-counter:

It is a common error to write something like:

Unfortunately, this is syntactically legal, so the compiler will not warn you. The effect of this statement is to leave the value of index unchanged. This is often a difficult bug to track down.

Remember, you can write index = index +1;, or you can write index++;, but you should not mix them.

Character arithmetic
It may seem odd, but you can do arithmetic with characters! The expression 'a' + 1 yields the value 'b'. Similarly, if you have a variable named letter that contains a character, then letter - 'a' will tell you where in the alphabet it appears (keeping in mind that 'a' is the zeroeth letter of the alphabet and 'z' is the 25th).

This sort of thing is useful for converting between the characters that contain numbers, like '0', '1' and '2', and the corresponding integers. They are not the same thing. For example, if you try this:

you might expect the value 3, but depending on your environment, you might get 51, which is the ASCII code that is used to represent the character '3', or you might get something else altogether. To convert '3' to the corresponding integer value you can subtract '0':

Technically, in both of these examples the typecast ((int)) is unnecessary, since Java will convert type char to type int automatically. I included the typecasts to emphasize the difference between the types, and because I am a stickler about that sort of thing.

Since this conversion can be a little ugly, it is preferable to use the digit method in the Character class. For example:

converts letter to the corresponding digit, interpreting it as a base 10 number.

Another use for character arithmetic is to loop through the letters of the alphabet in order. For example, in Robert McCloskey's book Make Way for Ducklings, the names of the ducklings form an abecedarian series, something like Jack, Kack, Lack, Mack, Nack, Oack, Pack and Qack. Here is a loop that prints these names in order:

Notice that in addition to the arithmetic operators, we can also use the conditional operators on characters. The output of this program is: Jack Kack Lack Mack Nack Oack Pack Qack

Of course, that is not quite right because I have misspelled Ouack and Quack. As an exercise, modify the program to correct this error.

Typecasting for experts
Here is a puzzler: normally, the statement x++ is exactly equivalent to x = x + 1. Unless x is a char! In that case, x++ is legal, but x = x + 1 causes an error.

Try it out and see what the error message is, then see if you can figure out what is going on.

Strings are immutable
As you look over the documentation of the String methods, you might notice toUpperCase and toLowerCase. These methods are often a source of confusion, because it sounds like they have the effect of changing (or mutating) an existing string. Actually, neither these methods nor any others can change a string, because strings are immutable.

When you invoke toUpperCase on a String, you get a new String as a return value. For example:

After the second line is executed, upperName contains the value "ALAN TURING", but name still contains "Alan Turing".

Strings are incomparable
It is often necessary to compare strings to see if they are the same, or to see which comes first in alphabetical order. It would be nice if we could use the comparison operators, like == and >, but we cannot.

In order to compare Strings, we have to use the equals and compareTo methods. For example:

The syntax here is a little weird. To compare two things, you have to invoke a method on one of them and pass the other as an argument.

The return value from equals is straightforward enough; true if the strings contain the same characters, and false otherwise.

The return value from compareTo is a little odd. It is the difference between the first characters in the strings that differ. If the strings are equal, it is 0. If the first string (the one on which the method is invoked) comes first in the alphabet, the difference is negative. Otherwise, the difference is positive. In this case the return value is positive 8, because the second letter of Ada comes before the second letter of Alan by 8 letters.

Using compareTo is often tricky, and I never remember which way is which without looking it up, but the good news is that the interface is pretty standard for comparing many types of objects, so once you get it you are all set.

Just for completeness, I should admit that it is legal, but very seldom correct, to use the == operator with Strings. But what that means will not make sense until later, so for now, do not do it.

Glossary

 * object A collection of related data that comes with a set of methods that operate on it. The objects we have used so far are the Graphics object provided by the system, and Strings.
 * index A variable or value used to select one of the members of an ordered set, like a character from a string.
 * traverse To iterate through all the elements of a set performing a similar operation on each.
 * counter A variable used to count something, usually initialized to zero and then incremented.
 * increment Increase the value of a variable by one. The increment operator in Java is ++.
 * decrement Decrease the value of a variable by one. The decrement operator in Java is --.
 * exception A run time error. Exceptions cause the execution of a program to terminate.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: The Way of the Java/Strings and things


text:
The Way of the Java/Interesting objects

What is String?
Although Strings are objects, they are not very interesting ones, because:
 * They are immutable.
 * They have no instance variables.
 * You do not have to use the new construct to create one.

In this chapter, we are going to use two new object types that are part of the Java language: Point and Rectangle. Please note that these are not graphical objects that appear on the screen, but variables that contain data, just like ints and doubles. Like other variables, they can be used internally to perform computations.

The definitions of the Point and Rectangle classes are in the java.awt package, so we have to import them.

Packages
The built-in Java classes are divided into a number of packages, including java.lang, which contains almost all of the classes we have seen so far, and java.awt, which contains classes that pertain to the Java Abstract Window Toolkit (AWT), which contains classes for windows, buttons, graphics, etc.

In order to use a package, you have to import it, which is why the program in Section graphics starts with import java.awt.*. The * indicates that we want to import all the classes in the AWT package. If you want, you can name the classes you want to import explicitly, but there is no great advantage. The classes in java.lang are imported automatically, which is why most of our programs have not required an import statement.

All import statements appear at the beginning of the program, outside the class definition.

Point objects
At the most basic level, a point is two numbers (coordinates) that we treat collectively as a single object. In mathematical notation, points are often written in parentheses, with a comma separating the coordinates. For example, indicates the origin, and indicates the point units to the right and units up from the origin.

In Java, a point is represented by a Point object. To create a new point, you have to use the new command:

The first line is a conventional variable declaration: blank has type Point. The second line is kind of funny-looking; it invokes the new command, specifies the type of the new object, and provides arguments. It will probably not surprise you that the arguments are the coordinates of the new point.

The result of the new command is a reference to the new point. I'll explain references more later; for now the important thing is that the variable blank contains a the address of the newly-created object.

Taken together, all the variables, values, and objects in a program are called the state. Diagrams like this that show the state of the program are called state diagrams. As the program runs, the state changes, so you should think of a state diagram as a snapshot of a particular point in the execution.

Instance variables
The pieces of data that make up an object are sometimes called components, records, or fields. In Java they are called instance variables because each object, which is an instance of its type, has its own copy of the instance variables.

It is like the glove compartment of a car. Each car is an instance of the type car, and each car has its own glove compartment. If you asked me to get something from the glove compartment of your car, you would have to tell me which car is yours.

Similarly, if you want to read a value from an instance variable, you have to specify the object you want to get it from. In Java this is done using dot notation.

The expression blank.x means go to the object blank refers to, and get the value of x. In this case we assign that value to a local variable named x. Notice that there is no conflict between the local variable named x and the instance variable named x. The purpose of dot notation is to identify which variable you are referring to unambiguously.

You can use dot notation as part of any Java expression, so the following are legal.

The first line prints 3, 4; the second line calculates the value 25.

Objects as parameters
You can pass objects as parameters in the usual way. For example:

is a method that takes a point as an argument and prints it in the standard format. If you invoke printPoint (blank), it will print (3, 4). Actually, Java has a built-in method for printing Points. If you invoke System.out.println (blank), you get: java.awt.Point[x=3,y=4]

This is a standard format Java uses for printing objects. It prints the name of the type, followed by the contents of the object, including the names and values of the instance variables.

As a second example, we can rewrite the distance method from Section distance so that it takes two Points as parameters instead of four doubles.

The typecasts are not really necessary; I just added them as a reminder that the instance variables in a Point are integers.

Rectangles
Rectangles are similar to points, except that they have four instance variables, named x, y, width and height. Other than that, everything is pretty much the same.

creates a new Rectangle object and makes box refer to it.

If you print box, you get: java.awt.Rectangle[x=0,y=0,width=100,height=200]

Again, this is the result of a built-in Java method that knows how to print Rectangle objects.

Objects as return types
You can write methods that return objects. For example, findCenter takes a Rectangle as an argument and returns a Point that contains the coordinates of the center of the Rectangle:

Notice that you can use new to create a new object, and then immediately use the result as a return value.

Objects are mutable
You can change the contents of an object by making an assignment to one of its instance variables. For example, to move a rectangle without changing its size, you could modify the x and y values:

We could take this code and encapsulate it in a method, and generalize it to move the rectangle by any amount:

The variables dx and dy indicate how far to move the rectangle in each direction. Invoking this method has the effect of modifying the Rectangle that is passed as an argument. prints: java.awt.Rectangle[x=50,y=100,width=100,height=200].

Modifying objects by passing them as arguments to methods can be useful, but it can also make debugging more difficult because it is not always clear which method invocations do or do not modify their arguments. Later, I will discuss some pros and cons of this programming style.

In the meantime, we can enjoy the luxury of Java's built-in methods, which include translate, which does exactly the same thing as moveRect, although the syntax for invoking it is a little different. Instead of passing the Rectangle as an argument, we invoke translate on the Rectangle and pass only dx and dy as arguments.

The effect is exactly the same.

Aliasing
aliasing aliasing reference

Remember that when you make an assignment to an object variable, you are assigning a reference to an object. It is possible to have multiple variables that refer to the same object. For example, this code:

Both box1 and box2 refer or point to the same object. In other words, this object has two names, box1 and box2. When a person uses two names, it is called aliasing. Same thing with objects.

When two variables are aliased, any changes that affect one variable also affect the other. For example:

The first line prints 100, which is the width of the Rectangle referred to by box2. The second line invokes the grow method on box1, which expands the Rectangle by 50 pixels in every direction (see the documentation for more details).

As should be clear from this figure, whatever changes are made to box1 also apply to box2. Thus, the value printed by the third line is 200, the width of the expanded rectangle. (As an aside, it is perfectly legal for the coordinates of a Rectangle to be negative.)

As you can tell even from this simple example, code that involves aliasing can get confusing fast, and it can be very difficult to debug. In general, aliasing should be avoided or used with care.

null
When you create an object variable, remember that you are creating a reference to an object. Until you make the variable point to an object, the value of the variable is null. null is a special value in Java (and a Java keyword) that is used to mean no object.

The declaration Point blank; is equivalent to this initialization:

If you try to use a null object, either by accessing an instance variable or invoking a method, you will get a NullPointerException. The system will print an error message and terminate the program.

On the other hand, it is legal to pass a null object as an argument or receive one as a return value. In fact, it is common to do so, for example to represent an empty set or indicate an error condition.

Garbage collection
In Section aliasing we talked about what happens when more than one variable refers to the same object. What happens when no variable refers to an object? For example:

The first line creates a new Point object and makes blank refer to it. The second line changes blank so that instead of referring to the object, it refers to nothing (the null object).

If no one refers to an object, then no one can read or write any of its values, or invoke a method on it. In effect, it ceases to exist. We could keep the object in memory, but it would only waste space, so periodically as your program runs, the Java system looks for stranded objects and reclaims them, in a process called garbage collection. Later, the memory space occupied by the object will be available to be used as part of a new object.

You do not have to do anything to make garbage collection work, and in general you will not be aware of it.

Objects and primitives
There are two kinds of types in Java, primitive types and object types. Primitives, like int and boolean begin with lower-case letters; object types begin with upper-case letters. This distinction is useful because it reminds us of some of the differences between them:

When you declare a primitive variable, you get storage space for a primitive value. When you declare an object variable, you get a space for a reference to an object. In order to get space for the object itself, you have to use the new command.

If you do not initialize a primitive type, it is given a default value that depends on the type. For example, 0 for ints and true for booleans. The default value for object types is null, which indicates no object.

Primitive variables are well isolated in the sense that there is nothing you can do in one method that will affect a variable in another method. Object variables can be tricky to work with because they are not as well isolated. If you pass a reference to an object as an argument, the method you invoke might modify the object, in which case you will see the effect. The same is true when you invoke a method on an object. Of course, that can be a good thing, but you have to be aware of it.

There is one other difference between primitives and object types. You cannot add new primitives to the Java language (unless you get yourself on the standards committee), but you can create new object types! We'll see how in the next chapter.

Glossary

 * package: A collection of classes. The built-in Java classes are organized in packages.
 * AWT: The Abstract Window Toolkit, one of the biggest and most commonly-used Java packages.
 * instance: An example from a category. My cat is an instance of the category feline things. Every object is an instance of some class.
 * instance variable: One of the named data items that make up an object. Each object (instance) has its own copy of the instance variables for its class.
 * reference: A value that indicates an object. In a state diagram, a reference appears as an arrow.
 * aliasing: The condition when two or more variables refer to the same object.
 * garbage collection: The process of finding objects that have no references and reclaiming their storage space.
 * state: A complete description of all the variables and objects and their values, at a given point during the execution of a program.
 * state diagram: A snapshot of the state of a program, shown graphically.

title: The Way of the Java/Interesting objects


text:
The Way of the Java/Create your own objects

Class definitions and object types
Every time you write a class definition, you create a new Object type, with the same name as the class. Way back in Section hello, when we defined the class named Hello, we also created an object type named Hello. We didn't create any variables with type Hello, and we didn't use the new command to create any Hello objects, but we could have!

That example may not make any sense, since there is no reason to create a Hello object, and it is not clear what it would be good for if we did. In this chapter, we will look at some examples of class definitions that create useful new Object types.

Here are the most important ideas in this chapter:

with the same name.
 * Defining a new class also creates a new object type

it determines what instance variables the objects have and what methods can operate on them.
 * A class definition is like a template for objects:

is an instance of some class.
 * Every object belongs to some object type; hence, it

invokes a special method called a constructor to initialize the instance variables. You provide one or more constructors as part of the class definition.
 * When you invoke the new command to create an object, Java

class definition for that type.
 * Typically all the methods that operate on a type go in the

Here are some syntax issues about class definitions:

letter, which helps distinguish them from primitive types and variable names.
 * Class names (and hence object types) always begin with a capital

of the file must be the same as the name of the class, with the suffix .java. For example, the Time class is defined in the file named Time.java.
 * You usually put one class definition in each file, and the name

class. The startup class must contain a method named main, which is where the execution of the program begins. Other classes may have a method named main, but they will not be executed.
 * In any program, one class is designated as the startup

With those issues out of the way, let's look at an example of a user-defined type, Time.

Time
A common motivation for creating a new Object type is to take several related pieces of data and encapsulate them into an object that can be manipulated (passed as an argument, operated on) as a single unit. We have already seen two built-in types like this, Point and Rectangle.

Another example, which we will implement ourselves, is Time, which is used to record the time of day. The various pieces of information that form a time are the hour, minute and second. Because every Time object will contain these data, we need to create instance variables to hold them.

The first step is to decide what type each variable should be. It seems clear that hour and minute should be integers. Just to keep things interesting, let's make second a double, so we can record fractions of a second.

Instance variables are declared at the beginning of the class definition, outside of any method definition, like this:

class Time int hour, minute; double second;

All by itself, this code fragment is a legal class definition.

After declaring the instance variables, the next step is usually to define a constructor for the new class.

Constructors
The usual role of a constructor is to initialize the instance variables. The syntax for constructors is similar to that of other methods, with three exceptions:

the class.
 * The name of the constructor is the same as the name of

 * Constructors have no return type and no return value.

 * The keyword static is omitted.

Here is an example for the Time class:

public Time this.hour = 0; this.minute = 0; this.second = 0.0;

Notice that where you would expect to see a return type, between public and Time, there is nothing. That's how we (and the compiler) can tell that this is a constructor.

This constructor does not take any arguments, as indicated by the empty parentheses. Each line of the constructor initializes an instance variable to an arbitrary default value (in this case, midnight). The name this is a special keyword that is the name of the object we are creating. You can use this the same way you use the name of any other object. For example, you can read and write the instance variables of this, and you can pass this as an argument to other methods.

But you do not declare this and you do not use new to create it. In fact, you are not even allowed to make an assignment to it! this is created by the system; all you have to do is store values in its instance variables.

A common error when writing constructors is to put a return statement at the end. Resist the temptation.

More constructors
Constructors can be overloaded, just like other methods, which means that you can provide multiple constructors with different parameters. Java knows which constructor to invoke by matching the arguments of the new command with the parameters of the constructors.

It is very common to have one constructor that takes no arguments (shown above), and one constructor that takes a parameter list that is identical to the list of instance variables. For example:

public Time (int hour, int minute, double second) this.hour = hour; this.minute = minute; this.second = second;

The names and types of the parameters are exactly the same as the names and types of the instance variables. All the constructor does is copy the information from the parameters to the instance variables.

If you go back and look at the documentation for Points and Rectangles, you will see that both classes provide constructors like this. Overloading constructors provides the flexibility to create an object first and then fill in the blanks, or to collect all the information before creating the object.

So far this might not seem very interesting, and in fact it is not. Writing constructors is a boring, mechanical process. Once you have written two, you will find that you can churn them out in your sleep, just by looking at the list of instance variables.

Creating a new object
Although constructors look like methods, you never invoke them directly. Instead, when you use the new command, the system allocates space for the new object and then invokes your constructor to initialize the instance variables.

The following program demonstrates two ways to create and initialize Time objects:

class Time int hour, minute; double second; public Time this.hour = 0; this.minute = 0; this.second = 0.0;

public Time (int hour, int minute, double second) this.hour = hour; this.minute = minute; this.second = second; public static void main (String[] args) // one way to create and initialize a Time object Time t1 = new Time ; t1.hour = 11; t1.minute = 8; t1.second = 3.14159; System.out.println (t1); // another way to do the same thing Time t2 = new Time (11, 8, 3.14159); System.out.println (t2);

As an exercise, figure out the flow of execution through this program.

In main, the first time we invoke the new command, we provide no arguments, so Java invokes the first constructor. The next few lines assign values to each of the instance variables.

The second time we invoke the new command, we provide arguments that match the parameters of the second constructor. This way of initializing the instance variables is more concise (and slightly more efficient), but it can be harder to read, since it is not as clear which values are assigned to which instance variables.

Printing an object
The output of this program is:

Time@80cc7c0 Time@80cc807

When Java prints the value of a user-defined object type, it prints the name of the type and a special hexadecimal (base 16) code that is unique for each object. This code is not meaningful in itself; in fact, it can vary from machine to machine and even from run to run. But it can be useful for debugging, in case you want to keep track of individual objects.

In order to print objects in a way that is more meaningful to users (as opposed to programmers), you usually want to write a method called something like printTime:

public static void printTime (Time t)    System.out.println (t.hour + ":" + t.minute + ":" + t.second);

Compare this method to the version of printTime in Section time.

The output of this method, if we pass either t1 or t2 as an argument, is 11:8:3.14159. Although this is recognizable as a time, it is not quite in the standard format. For example, if the number of minutes or seconds is less than 10, we expect a leading 0 as a place-keeper. Also, we might want to drop the decimal part of the seconds. In other words, we want something like 11:08:03.

In most languages, there are simple ways to control the output format for numbers. In Java there are no simple ways.

Java provides very powerful tools for printing formatted things like times and dates, and also for interpreting formatted input. Unfortunately, these tools are not very easy to use, so I am going to leave them out of this book. If you want, though, you can take a look at the documentation for the Date class in the java.util package.

Operations on objects
Even though we can't print times in an optimal format, we can still write methods that manipulate Time objects. In the next few sections, I will demonstrate several of the possible interfaces for methods that operate on objects. For some operations, you will have a choice of several possible interfaces, so you should consider the pros and cons of each of these:

pure function: Takes objects and/or primitives as arguments but does not modify the objects. The return value is either a primitive or a new object created inside the method.

modifier: Takes objects as arguments and modifies some or all of them. Often returns void. void

fill-in method: One of the arguments is an empty object that gets filled in by the method. Technically, this is a type of modifier.

Pure functions
A method is considered a pure function if the result depends only on the arguments, and it has no side effects like modifying an argument or printing something. The only result of invoking a pure function is the return value.

One example is after, which compares two Times and returns a boolean that indicates whether the first operand comes after the second:

public static boolean after (Time time1, Time time2) if (time1.hour > time2.hour) return true; if (time1.hour < time2.hour) return false;

if (time1.minute > time2.minute) return true; if (time1.minute < time2.minute) return false;

if (time1.second > time2.second) return true; return false;

What is the result of this method if the two times are equal? Does that seem like the appropriate result for this method? If you were writing the documentation for this method, would you mention that case specifically?

A second example is addTime, which calculates the sum of two times. For example, if it is 9:14:30, and your breadmaker takes 3 hours and 35 minutes, you could use addTime to figure out when the bread will be done.

Here is a rough draft of this method that is not quite right:

public static Time addTime (Time t1, Time t2) Time sum = new Time ; sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second; return sum;

Although this method returns a Time object, it is not a constructor. You should go back and compare the syntax of a method like this with the syntax of a constructor, because it is easy to get confused.

Here is an example of how to use this method. If currentTime contains the current time and breadTime contains the amount of time it takes for your breadmaker to make bread, then you could use addTime to figure out when the bread will be done.

Time currentTime = new Time (9, 14, 30.0); Time breadTime = new Time (3, 35, 0.0); Time doneTime = addTime (currentTime, breadTime); printTime (doneTime);

The output of this program is 12:49:30.0, which is correct. On the other hand, there are cases where the result is not correct. Can you think of one?

The problem is that this method does not deal with cases where the number of seconds or minutes adds up to more than 60. In that case, we have to ``carry'' the extra seconds into the minutes column, or extra minutes into the hours column.

Here's a second, corrected version of this method.

public static Time addTime (Time t1, Time t2) Time sum = new Time ; sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second;

if (sum.second >= 60.0) sum.second -= 60.0; sum.minute += 1; if (sum.minute >= 60) sum.minute -= 60; sum.hour += 1; return sum;

Although it's correct, it's starting to get big. Later, I will suggest an alternate approach to this problem that will be much shorter.

This code demonstrates two operators we have not seen before, += and -=. These operators provide a concise way to increment and decrement variables. They are similar to ++ and --, except (1) they work on doubles as well as ints, and (2) the amount of the increment does not have to be 1. The statement sum.second -= 60.0; is equivalent to sum.second = sum.second - 60;

Modifiers
As an example of a modifier, consider increment, which adds a given number of seconds to a Time object. Again, a rough draft of this method looks like:

public static void increment (Time time, double secs) time.second += secs;

if (time.second >= 60.0) time.second -= 60.0; time.minute += 1; if (time.minute >= 60) time.minute -= 60; time.hour += 1;

The first line performs the basic operation; the remainder deals with the same cases we saw before.

Is this method correct? What happens if the argument secs is much greater than 60? In that case, it is not enough to subtract 60 once; we have to keep doing it until second is below 60. We can do that by simply replacing the if statements with while statements:

public static void increment (Time time, double secs) time.second += secs;

while (time.second >= 60.0) time.second -= 60.0; time.minute += 1; while (time.minute >= 60) time.minute -= 60; time.hour += 1;

This solution is correct, but not very efficient. Can you think of a solution that does not require iteration?

Fill-in methods
Occasionally you will see methods like addTime written with a different interface (different arguments and return values). Instead of creating a new object every time addTime is invoked, we could require the caller to provide an ``empty'' object where addTime should store the result. Compare the following with the previous version:

public static void addTimeFill (Time t1, Time t2, Time sum) sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second;

if (sum.second >= 60.0) sum.second -= 60.0; sum.minute += 1; if (sum.minute >= 60) sum.minute -= 60; sum.hour += 1;

One advantage of this approach is that the caller has the option of reusing the same object repeatedly to perform a series of additions. This can be slightly more efficient, although it can be confusing enough to cause subtle errors. For the vast majority of programming, it is worth spending a little run time to avoid a lot of debugging time.

Which is best?
Anything that can be done with modifiers and fill-in methods can also be done with pure functions. In fact, there are programming languages, called functional programming languages, that only allow pure functions. Some programmers believe that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. Nevertheless, there are times when modifiers are convenient, and some cases where functional programs are less efficient.

In general, I recommend that you write pure functions whenever it is reasonable to do so, and resort to modifiers only if there is a compelling advantage. This approach might be called a functional programming style.

Incremental development vs. planning
In this chapter I have demonstrated an approach to program development I refer to as rapid prototyping with iterative improvement. In each case, I wrote a rough draft (or prototype) that performed the basic calculation, and then tested it on a few cases, correcting flaws as I found them.

Although this approach can be effective, it can lead to code that is unnecessarily complicated---since it deals with many special cases---and unreliable---since it is hard to convince yourself that you have found all the errors.

An alternative is high-level planning, in which a little insight into the problem can make the programming much easier. In this case the insight is that a Time is really a three-digit number in base 60! The second is the ``ones column,'' the minute is the 60's column, and the hour is the 3600's column.

When we wrote addTime and increment, we were effectively doing addition in base 60, which is why we had to ``carry'' from one column to the next.

Thus an alternate approach to the whole problem is to convert Times into doubles and take advantage of the fact that the computer already knows how to do arithmetic with doubles. Here is a method that converts a Time into a double:

public static double convertToSeconds (Time t)    int minutes = t.hour * 60 + t.minute; double seconds = minutes * 60 + t.second; return seconds;

Now all we need is a way to convert from a double to a Time object. We could write a method to do it, but it might make more sense to write it as a third constructor:

public Time (double secs) this.hour = (int) (secs / 3600.0); secs -= this.hour * 3600.0; this.minute = (int) (secs / 60.0); secs -= this.minute * 60; this.second = secs;

This constructor is a little different from the others, since it involves some calculation along with assignments to the instance variables.

You might have to think a bit to convince yourself that the technique I am using to convert from one base to another is correct. Assuming you are convinced, we can use these methods to rewrite addTime:

public static Time addTime (Time t1, Time t2) double seconds = convertToSeconds (t1) + convertToSeconds (t2); return new Time (seconds);

This is much shorter than the original version, and it is much easier to demonstrate that it is correct (assuming, as usual, that the methods it invokes are correct). As an exercise, rewrite increment the same way.

Generalization
In some ways converting from base 60 to base 10 and back is harder than just dealing with times. Base conversion is more abstract; our intuition for dealing with times is better.

But if we have the insight to treat times as base 60 numbers, and make the investment of writing the conversion methods (convertToSeconds and the third constructor), we get a program that is shorter, easier to read and debug, and more reliable.

It is also easier to add more features later. For example, imagine subtracting two Times to find the duration between them. The naive approach would be to implement subtraction complete with borrowing. Using the conversion methods would be much easier.

Ironically, sometimes making a problem harder (more general) makes is easier (fewer special cases, fewer opportunities for error).

Algorithms
When you write a general solution for a class of problems, as opposed to a specific solution to a single problem, you have written an algorithm. I mentioned this word in Chapter 1, but did not define it carefully. It is not easy to define, so I will try a couple of approaches.

First, consider some things that are not algorithms. For example, when you learned to multiply single-digit numbers, you probably memorized the multiplication table. In effect, you memorized 100 specific solutions, so that knowledge is not really algorithmic.

But if you were lazy, you probably cheated by learning a few tricks. For example, to find the product of and 9, you can write as the first digit and  as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That's an algorithm!

Similarly, the techniques you learned for addition with carrying, subtraction with borrowing, and long division are all algorithms. One of the characteristics of algorithms is that they do not require any intelligence to carry out. They are mechanical processes in which each step follows from the last according to a simple set of rules.

In my opinion, it is embarrassing that humans spend so much time in school learning to execute algorithms that, quite literally, require no intelligence.

On the other hand, the process of designing algorithms is interesting, intellectually challenging, and a central part of what we call programming.

Some of the things that people do naturally, without difficulty or conscious thought, are the most difficult to express algorithmically. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm.

Later you will have the opportunity to design simple algorithms for a variety of problems.

Glossary
class: Previously, I defined a class as a collection of related methods. In this chapter we learned that a class definition is also a template for a new type of object.

instance: A member of a class. Every object is an instance of some class.

constructor: A special method that initializes the instance variables of a newly-constructed object.

project: A collection of one or more class definitions (one per file) that make up a program.

startup class: The class that contains the main method where execution of the program begins.

function: A method whose result depends only on its parameters, and that has no side-effects other than returning a value.

functional programming style: A style of program design in which the majority of methods are functions.

modifier: A method that changes one or more of the objects it receives as parameters, and usually returns void.

fill-in method: A type of method that takes an empty object as a parameter and fills in its instance variables instead of generating a return value. This type of method is usually not the best choice.

algorithm: A set of instructions for solving a class of problems by a mechanical process.


text:
The Way of the Java/Arrays

Arrays
arrays array type!array

An array is a set of values where each value is identified by an index. You can make an array of ints, doubles, or any other type, but all the values in an array have to have the same type.

Syntactically, array types look like other Java types except they are followed by []. For example, int[] is the type ``array of integers and double[] is the type ``array of doubles.

You can declare variables with these types in the usual ways:

verbatim int[] count; double[] values; verbatim

Until you initialize these variables, they are set to null. To create the array itself, use the new command.

verbatim count = new int[4]; values = new double[size]; verbatim

The first assignment makes count refer to an array of 4 integers; the second makes values refer to an array of doubles. The number of elements in values depends on size. You can use any integer expression as an array size.

null state diagram

The following figure shows how arrays are represented in state diagrams:

figure=figs/array.eps

The large numbers inside the boxes are the elements of the array. The small numbers outside the boxes are the indices used to identify each box. When you allocate a new array, the elements are initialized to zero.

Accessing elements
element array!element

To store values in the array, use the [] operator. For example count[0] refers to the ``zeroeth'' element of the array, and count[1] refers to the ``oneth'' element. You can use the [] operator anywhere in an expression:

verbatim count[0] = 7; count[1] = count[0] * 2; count[2]++; count[3] -= 60; verbatim

All of these are legal assignment statements. Here is the effect of this code fragment:

figure=figs/array2.eps

By now you should have noticed that the four elements of this array are numbered from 0 to 3, which means that there is no element with the index 4. This should sound familiar, since we saw the same thing with String indices. Nevertheless, it is a common error to go beyond the bounds of an array, which will cause an ArrayOutOfBoundsException. As with all exceptions, you get an error message and the program quits.

exception!ArrayOutOfBounds run-time error index expression

You can use any expression as an index, as long as it has type int. One of the most common ways to index an array is with a loop variable. For example:

verbatim int i = 0; while (i < 4) System.out.println (count[i]); i++; verbatim

This is a standard while loop that counts from 0 up to 4, and when the loop variable i is 4, the condition fails and the loop terminates. Thus, the body of the loop is only executed when i is 0, 1, 2 and 3.

loop loop variable variable!loop

Each time through the loop we use i as an index into the array, printing the ith element. This type of array traversal is very common. Arrays and loops go together like fava beans and a nice Chianti.

fava beans Chianti

Copying arrays
array!copying

When you copy an array variable, remember that you are copying a reference to the array. For example:

verbatim double[] a = new double [3]; double[] b = a; verbatim

This code creates one array of three doubles, and sets two different variables to refer to it. This situation is a form of aliasing.

figure=figs/array3.eps

Any changes in either array will be reflected in the other. This is not usually the behavior you want; instead, you should make a copy of the array, by allocating a new array and copying each element from one to the other.

verbatim double[] b = new double [3];

int i = 0; while (i < 4) b[i] = a[i]; i++; verbatim

for loops
The loops we have written so far have a number of elements in common. All of them start by initializing a variable; they have a test, or condition, that depends on that variable; and inside the loop they do something to that variable, like increment it.

loop!for for statement!for

This type of loop is so common that there is an alternate loop statement, called for, that expresses it more concisely. The general syntax looks like this:

verbatim for (INITIALIZER; CONDITION; INCREMENTOR) BODY verbatim

This statement is exactly equivalent to

verbatim INITIALIZER; while (CONDITION) BODY INCREMENTOR verbatim

except that it is more concise and, since it puts all the loop-related statements in one place, it is easier to read. For example:

verbatim for (int i = 0; i < 4; i++) System.out.println (count[i]); verbatim

is equivalent to

verbatim int i = 0; while (i < 4) System.out.println (count[i]); i++; verbatim

As an exercise, write a for loop to copy the elements of an array.

Arrays and objects
object!compared to array array!compared to object

In many ways, arrays behave like objects:

itemize

When you declare an array variable, you get a reference to an array.

You have to use the new command to create the array itself.

When you pass an array as an argument, you pass a reference, which means that the invoked method can change the contents of the array.

itemize

Some of the objects we have looked at, like Rectangles, are similar to arrays, in the sense that they are named collection of values. This raises the question, ``How is an array of 4 integers different from a Rectangle object?''

collection

If you go back to the definition of ``array'' at the beginning of the chapter, you will see one difference, which is that the elements of an array are identified by indices, whereas the elements (instance variables) of an object have names (like x, width, etc.).

Another difference between arrays and objects is that all the elements of an array have to be the same type. Although that is also true of Rectangles, we have seen other objects that have instance variables with different types (like Time).

Array length
length!array array!length

Actually, arrays do have one named instance variable: length. Not surprisingly, it contains the length of the array (number of elements). It is a good idea to use this value as the upper bound of a loop, rather than a constant value. That way, if the size of the array changes, you won't have to go through the program changing all the loops; they will work correctly for any size array.

verbatim for (int i = 0; i < a.length; i++) b[i] = a[i]; verbatim

The last time the body of the loop gets executed, i is a.length - 1, which is the index of the last element. When i is equal to a.length, the condition fails and the body is not executed, which is a good thing, since it would cause an exception. This code assumes that the array b contains at least as many elements as a.

As an exercise, write a method called cloneArray that takes an array of integers as a parameter, creates a new array that is the same size, copies the elements from the first array into the new one, and then returns a reference to the new array.

Random numbers
random pseudorandom random number deterministic nondeterministic

Most computer programs do the same thing every time they are executed, so they are said to be deterministic. Usually, determinism is a good thing, since we expect the same calculation to yield the same result. For some applications, though, we would like the computer to be unpredictable. Games are an obvious example, but there are many more.

Making a program truly nondeterministic turns out to be not so easy, but there are ways to make it at least seem nondeterministic. One of them is to generate random numbers and use them to determine the outcome of the program. Java provides a built-in method that generates pseudorandom numbers, which are not truly random in the mathematical sense, but for our purposes, they will do.

Check out the documentation of the random method in the Math class. The return value is a double between 0.0 and 1.0. Each time you invoke random you get a different randomly-generated number. To see a sample, run this loop:

verbatim for (int i = 0; i < 10; i++) double x = Math.random ; System.out.println (x); verbatim

To generate a random double between 0.0 and an upper bound like high, you can multiply x by high. How would you generate a random number between low and high? How would you generate a random integer?

Statistics
statistics distribution mean

The numbers generated by random are supposed to be distributed uniformly. If you have taken statistics, you know what that means. Among other things, it means that if we divide the range of possible values into equal sized ``buckets,'' and count the number of times a random value falls in each bucket, each bucket should get the same number of hits (eventually).

In the next few sections, we will write programs that generate a sequence of random numbers and check whether this property holds true.

Array of random numbers
The first step is to generate a large number of random values and store them in an array. By ``large number,'' of course, I mean 8. It's always a good idea to start with a manageable number, to help with debugging, and then increase it later.

The following method takes a single argument, the size of the array. It allocates a new array of doubles, fills it with random values, and returns a reference to the new array.

verbatim public static double[] randomArray (int n)    double[] a = new double[n]; for (int i = 0; i<a.length; i++) a[i] = Math.random ; return a; verbatim

The return type is double[], which means that this method returns an array of doubles. To test this method, it is convenient to have a method that prints the contents of an array.

verbatim public static void printArray (double[] a)    for (int i = 0; i<a.length; i++) System.out.println (a[i]); verbatim

The following code generates an array and prints it:

verbatim int numValues = 8; double[] array = randomArray (numValues); printArray (array); verbatim

On my machine the output is

verbatim 0.7344558779885422 0.6224282219647016 0.09591424515329172 0.2992298398883563 0.7736458103088713 0.7069110192991597 0.7042440765950522 0.977839532249852 verbatim

which is pretty random-looking. Your results may differ.

If these numbers are really random, we expect half of them to be greater than 0.5 and half to be less. In fact, six are greater than 0.5, so that's a little high.

If we divide the range into four buckets---from 0.0 to 0.25, 0.25 to 0.5, 0.5 to 0.75, and 0.75 to 1.0---we expect 2 values to fall in each bucket. In fact, we get 1, 1, 4, 2. Again, not exactly what we expected.

Do these results mean the values are not really random? It's hard to tell. With so few values, the chances are slim that we would get exactly what we expect. But as the number of values increases, the outcome should be more predictable.

To test this theory, we'll write some programs that divide the range into buckets and count the number of values in each.

Counting
traverse!array array!traverse looping and counting counter

A good approach to problems like this is to think of simple methods that are easy to write, and that might turn out to be useful. Then you can combine them into a solution. Of course, it is not easy to know ahead of time which methods are likely to be useful, but as you gain experience you will have a better idea.

Also, it is not always obvious what sort of things are easy to write, but a good approach is to look for subproblems that fit a pattern you have seen before.

Back in Section loopcount we looked at a loop that traversed a string and counted the number of times a given letter appeared. You can think of this program as an example of a pattern called ``traverse and count.'' The elements of this pattern are:

itemize

A set or container that can be traversed, like an array or a string.

A test that you can apply to each element in the container.

A counter that keeps track of how many elements pass the test.

itemize

In this case, I have a method in mind called inBucket that counts the number of elements in an array that fall in a given bucket. The parameters are the array and two doubles that specify the lower and upper bounds of the bucket.

verbatim public static int inBucket (double[] a, double low, double high) int count = 0; for (int i=0; i= low && a[i] < high) count++; return count; verbatim

I haven't been very careful about whether something equal to low or high falls in the bucket, but you can see from the code that low is in and high is out. That should prevent me from counting any elements twice.

Now, to divide the range into two pieces, we could write

verbatim int low = inBucket (a, 0.0, 0.5); int high = inBucket (a, 0.5, 1.0); verbatim

To divide it into four pieces:

verbatim int bucket1 = inBucket (a, 0.0, 0.25); int bucket2 = inBucket (a, 0.25, 0.5); int bucket3 = inBucket (a, 0.5, 0.75); int bucket4 = inBucket (a, 0.75, 1.0); verbatim

You might want to try out this program using a larger numValues. As numValues increases, are the numbers in each bucket levelling off?

Many buckets
bucket histogram

Of course, as the number of buckets increases, we don't want to have to rewrite the program, especially since the code is getting big and repetitive. Any time you find yourself doing something more than a few times, you should be looking for a way to automate it.

Let's say that we wanted 8 buckets. The width of each bucket would be one eighth of the range, which is 0.125. To count the number of values in each bucket, we need to be able to generate the bounds of each bucket automatically, and we need to have some place to store the 8 counts.

We can solve the first problem with a loop:

verbatim int numBuckets = 8; double bucketWidth = 1.0 / numBuckets;

for (int i = 0; i < numBuckets; i++) double low = i * bucketWidth; double high = low + bucketWidth; System.out.println (low + " to " + high); verbatim

This code uses the loop variable i to multiply by the bucket width, in order to find the low end of each bucket. The output of this loop is:

verbatim 0.0 to 0.125 0.125 to 0.25 0.25 to 0.375 0.375 to 0.5 0.5 to 0.625 0.625 to 0.75 0.75 to 0.875 0.875 to 1.0 verbatim

You can confirm that each bucket is the same width, that they don't overlap, and that they cover the whole range from 0.0 to 1.0.

Now we just need a way to store 8 integers, preferably so we can use an index to access each one. Immediately, you should be thinking ``array!''

What we want is an array of 8 integers, which we can allocate outside the loop; then, inside the loop, we'll invoke inBucket and store the result:

verbatim int numBuckets = 8; int[] buckets = new int [8]; double bucketWidth = 1.0 / numBuckets;

for (int i = 0; i<numBuckets; i++) double low = i * bucketWidth; double high = low + bucketWidth; //System.out.println (low + " to " + high);

buckets[i] = inBucket (a, low, high); verbatim

The tricky thing here is that I am using the loop variable as an index into the buckets array, in addition to using it to compute the range of each bucket.

This code works. I cranked the number of values up to 1000 and divided the range into 8 buckets. The output is:

verbatim 129 109 142 118 131 124 121 126 verbatim

which is pretty close to 125 in each bucket. At least, it's close enough that I can believe the random number generator is working.

A single-pass solution
Although this code works, it is not as efficient as it could be. Every time it invokes inBucket, it traverses the entire array. As the number of buckets increases, that gets to be a lot of traversals.

It would be better to make a single pass through the array, and for each value, compute which bucket it falls in. Then we could increment the appropriate counter.

In the previous section, we took an index, i, and multiplied it by the bucketWidth in order to find the lower bound of a given bucket. Now we want to take a value in the range 0.0 to 1.0, and find the index of the bucket where it falls.

Since this problem is the inverse of the previous problem we might guess that we should divide by the bucketwidth instead of multiplying. That guess is correct.

Remember that since bucketWidth = 1.0 / numBuckets, dividing by bucketWidth is the same as multiplying by numBuckets. If we take a number in the range 0.0 to 1.0 and multiply by numBuckets, we get a number in the range from 0.0 to numBuckets. If we round that number to the next lower integer, we get exactly what we are looking for---the index of the appropriate bucket.

verbatim int numBuckets = 8; int[] buckets = new int [8];

for (int i = 0; i < numValues; i++) int index = (int) (a[i] * numBuckets); buckets[index]++; verbatim

Here I am using a typecast to round the value down to the next integer and convert it to type int at the same time.

Is it possible for this calculation to produce an index that is out of range (either negative or greater than a.length-1)? If so, how would you fix it?

histogram

An array like buckets, that contains counts of the number of values in each range, is called a histogram. As an exercise, write a method called histogram that takes an array and a number of buckets as parameters, and that returns a histogram with the given number of buckets.

Glossary
description

[array:] A named collection of values, where all the values have the same type, and each value is identified by an index.

[collection:] Any data structure that contains a set of items or elements.

[element:] One of the values in an array. The [] operator selects elements of an array.

[index:] An integer variable or value used to indicate an element of an array.

[deterministic:] A program that does the same thing every time it is invoked.

[pseudorandom:] A sequence of numbers that appear to be random, but which are actually the product of a deterministic computation.

[histogram:] An array of integers where each integer counts the number of values that fall into a certain range.

array collection element index deterministic pseudorandom

description

title: The Way of the Java/Arrays