The way of the program The goal of this book, and this class, is to teach you to think like a computer scientist. I like the way computer scientists think because they combine some of the best features of Mathematics, Engineering, and Natural Science. Like mathematicians, computer scientists use formal languages to denote ideas (specifically computations). Like engineers, they design things, assembling components into systems and evaluating tradeoffs among alternatives. Like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions. The single most important skill for a computer scientist is problem-solving. By that I mean the ability to formulate problems, think creatively about solutions, and express a solution clearly and accurately. As it turns out, the process of learning to program is an excellent opportunity to practice problem-solving skills. That's why this chapter is called ``The way of the program.'' On one level, you will be learning to program, which is a useful skill by itself. On another level you will use programming as a means to an end. As we go along, that end will become clearer. What is a programming language? programming language language!programming The programming language you will be learning is Java, which is relatively new (Sun released the first version in May, 1995). Java is an example of a high-level language; other high-level languages you might have heard of are Pascal, C, C++ and FORTRAN. As you might infer from the name ``high-level language,'' there are also low-level languages, sometimes referred to as machine language or assembly language. Loosely-speaking, computers can only execute programs written in low-level languages. Thus, programs written in a high-level language have to be translated before they can run. This translation takes some time, which is a small disadvantage of high-level languages. portable high-level language low-level language language!high-level language!low-level But the advantages are enormous. First, it is much easier to program in a high-level language; by ``easier'' I mean that the program takes less time to write, it's shorter and easier to read, and it's more likely to be correct. Secondly, high-level languages are portable, meaning that they can run on different kinds of computers with few or no modifications. Low-level programs can only run on one kind of computer, and have to be rewritten to run on another. Due to these advantages, almost all programs are written in high-level languages. Low-level languages are only used for a few special applications. compile interpret There are two ways to translate a program; interpreting or compiling. An interpreter is a program that reads a high-level program and does what it says. In effect, it translates the program line-by-line, alternately reading lines and carrying out commands. figure=figs/interpret.eps A compiler is a program that reads a high-level program and translates it all at once, before executing any of the commands. Often you compile the program as a separate step, and then execute the compiled code later. In this case, the high-level program is called the source code, and the translated program is called the object code or the executable. As an example, suppose you write a program in C. You might use a text editor to write the program (a text editor is a simple word processor). When the program is finished, you might save it in a file named program.c, where ``program'' is an arbitrary name you make up, and the suffix .c is a convention that indicates that the file contains C source code. Then, depending on what your programming environment is like, you might leave the text editor and run the compiler. The compiler would read your source code, translate it, and create a new file named program.o to contain the object code, or program.exe to contain the executable. figure=figs/compile.eps The Java language is unusual because it is both compiled and interpreted. Instead of translating Java programs into machine language, the Java compiler generates Java byte code. Byte code is easy (and fast) to interpret, like machine language, but it is also portable, like a high-level language. Thus, it is possible to compile a Java program on one machine, transfer the byte code to another machine over a network, and then interpret the byte code on the other machine. This ability is one of the advantages of Java over many other high-level languages. figure=figs/java.eps Although this process may seem complicated, the good news is that in most programming environments (sometimes called development environments), these steps are automated for you. Usually you will only have to write a program and type a single command to compile and run it. On the other hand, it is useful to know what the steps are that are happening in the background, so that if something goes wrong you can figure out what it is. What is a program? A program is a sequence of instructions that specifies how to perform a computation. The computation might be something mathematical, like solving a system of equations or finding the roots of a polynomial, but it can also be a symbolic computation, like searching and replacing text in a document or (strangely enough) compiling a program. statement The instructions (or commands, or statements) look different in different programming languages, but there are a few basic functions that appear in just about every language: description [input:] Get data from the keyboard, or a file, or some other device. [output:] Display data on the screen or send data to a file or other device. [math:] Perform basic mathematical operations like addition and multiplication. [testing:] Check for certain conditions and execute the appropriate sequence of statements. [repetition:] Perform some action repeatedly, usually with some variation. description Believe it or not, that's pretty much all there is to it. Every program you've ever used, no matter how complicated, is made up of functions that look more or less like these. Thus, one way to describe programming is the process of breaking a large, complex task up into smaller and smaller subtasks until eventually the subtasks are simple enough to be performed with one of these simple functions. What is debugging? debugging bug Programming is a complex process, and since it is done by human beings, it often leads to errors. For whimsical reasons, programming errors are called bugs and the process of tracking them down and correcting them is called debugging. There are a few different kinds of errors that can occur in a program, and it is useful to distinguish between them in order to track them down more quickly. Compile-time errors compile-time error error!compile-time The compiler can only translate a program if the program is syntactically correct; otherwise, the compilation fails and you will not be able to run your program. Syntax refers to the structure of your program and the rules about that structure. syntax For example, in English, a sentence must begin with a capital letter and end with a period. this sentence contains a syntax error. So does this one For most readers, a few syntax errors are not a significant problem, which is why we can read the poetry of e e cummings without spewing error messages. Compilers are not so forgiving. If there is a single syntax error anywhere in your program, the compiler will print an error message and quit, and you will not be able to run your program. To make matters worse, there are more syntax rules in Java than there are in English, and the error messages you get from the compiler are often not very helpful. During the first few weeks of your programming career, you will probably spend a lot of time tracking down syntax errors. As you gain experience, though, you will make fewer errors and find them faster. Run-time errors run-time run-time error error!run-time exception safe language language!safe The second type of error is a run-time error, so-called because the error does not appear until you run the program. In Java, run-time errors occur when the interpreter is running the byte code and something goes wrong. The good news for now is that Java tends to be a safe language, which means that run-time errors are rare, especially for the simple sorts of programs we will be writing for the next few weeks. Later on in the semester, you will probably start to see more run-time errors, especially when we start talking about objects and references (Chapter objects). In Java, run-time errors are called exceptions, and in most environments they appear as windows or dialog boxes that contain information about what happened and what the program was doing when it happened. This information is useful for debugging. Logic errors and semantics semantics logic error error!logic The third type of error is the logical or semantic error. If there is a logical error in your program, it will compile and run successfully, in the sense that the computer will not generate any error messages, but it will not do the right thing. It will do something else. Specifically, it will do what you told it to do. The problem is that the program you wrote is not the program you wanted to write. The meaning of the program (its semantics) is wrong. Identifying logical errors can be tricky, since it requires you to work backwards by looking at the output of the program and trying to figure out what it is doing. Experimental debugging One of the most important skills you will acquire in this class is debugging. Although it can be frustrating, debugging is one of the most intellectually rich, challenging, and interesting parts of programming. In some ways debugging is like detective work. You are confronted with clues and you have to infer the processes and events that lead to the results you see. Debugging is also like an experimental science. Once you have an idea what is going wrong, you modify your program and try again. If your hypothesis was correct, then you can predict the result of the modification, and you take a step closer to a working program. If your hypothesis was wrong, you have to come up with a new one. As Sherlock Holmes pointed out, ``When you have eliminated the impossible, whatever remains, however improbable, must be the truth.'' (from A. Conan Doyle's The Sign of Four). Holmes, Sherlock Doyle, Arthur Conan For some people, programming and debugging are the same thing. That is, programming is the process of gradually debugging a program until it does what you want. The idea is that you should always start with a working program that does something, and make small modifications, debugging them as you go, so that you always have a working program. For example, Linux is an operating system that contains thousands of lines of code, but it started out as a simple program Linus Torvalds used to explore the Intel 80386 chip. According to Larry Greenfield, ``One of Linus's earlier projects was a program that would switch between printing AAAA and BBBB. This later evolved to Linux'' (from The Linux Users' Guide Beta Version 1). Linux In later chapters I will make more suggestions about debugging and other programming practices. Formal and natural languages formal language natural language language!formal language!natural Natural languages are the languages that people speak, like English, Spanish, and French. They were not designed by people (although people try to impose some order on them); they evolved naturally. Formal languages are languages that are designed by people for specific applications. For example, the notation that mathematicians use is a formal language that is particularly good at denoting relationships among numbers and symbols. Chemists use a formal language to represent the chemical structure of molecules. And most importantly: quote Programming languages are formal languages that have been designed to express computations. quote As I mentioned before, formal languages tend to have strict rules about syntax. For example, is a syntactically correct mathematical statement, but is not. Also, is a syntactically correct chemical name, but is not. Syntax rules come in two flavors, pertaining to tokens and structure. Tokens are the basic elements of the language, like words and numbers and chemical elements. One of the problems with 3=+6 is that is not a legal token in mathematics (at least as far as I know). Similarly, is not legal because there is no element with the abbreviation . The second type of syntax error pertains to the structure of a statement; that is, the way the tokens are arranged. The statement 3=+6 is structurally illegal, because you can't have a plus sign immediately after an equals sign. Similarly, molecular formulas have to have subscripts after the element name, not before. When you read a sentence in English or a statement in a formal language, you have to figure out what the structure of the sentence is (although in a natural language you do this unconsciously). This process is called parsing. parse For example, when you hear the sentence, ``The other shoe fell,'' you understand that ``the other shoe'' is the subject and ``fell'' is the verb. Once you have parsed a sentence, you can figure out what it means, that is, the semantics of the sentence. Assuming that you know what a shoe is, and what it means to fall, you will understand the general implication of this sentence. Although formal and natural languages have many features in common---tokens, structure, syntax and semantics---there are many differences. ambiguity redundancy literalness description [ambiguity:] Natural languages are full of ambiguity, which people deal with by using contextual clues and other information. Formal languages are designed to be nearly or completely unambiguous, which means that any statement has exactly one meaning, regardless of context. [redundancy:] In order to make up for ambiguity and reduce misunderstandings, natural languages employ lots of redundancy. As a result, they are often verbose. Formal languages are less redundant and more concise. [literalness:] Natural languages are full of idiom and metaphor. If I say, ``The other shoe fell,'' there is probably no shoe and nothing falling. Formal languages mean exactly what they say. description People who grow up speaking a natural language (everyone) often have a hard time adjusting to formal languages. In some ways the difference between formal and natural language is like the difference between poetry and prose, but more so: poetry prose description [Poetry:] Words are used for their sounds as well as for their meaning, and the whole poem together creates an effect or emotional response. Ambiguity is not only common but often deliberate. [Prose:] The literal meaning of words is more important and the structure contributes more meaning. Prose is more amenable to analysis than poetry, but still often ambiguous. [Programs:] The meaning of a computer program is unambiguous and literal, and can be understood entirely by analysis of the tokens and structure. description Here are some suggestions for reading programs (and other formal languages). First, remember that formal languages are much more dense than natural languages, so it takes longer to read them. Also, the structure is very important, so it is usually not a good idea to read from top to bottom, left to right. Instead, learn to parse the program in your head, identifying the tokens and interpreting the structure. Finally, remember that the details matter. Little things like spelling errors and bad punctuation, which you can get away with in natural languages, can make a big difference in a formal language. The first program hello hello world Traditionally the first program people write in a new language is called ``Hello, World.'' because all it does is print the words ``Hello, World.'' In Java, this program looks like this: verbatim class Hello // main: generate some simple output public static void main (String[] args) System.out.println ("Hello, world."); verbatim Some people judge the quality of a programming language by the simplicity of the ``Hello, World.'' program. By this standard, Java does not do very well. Even the simplest program contains a number of features that are hard to explain to beginning programmers. We are going to ignore a lot of them for now, but I will explain a few. All programs are made up of class definitions, which have the form: verbatim class CLASSNAME public static void main (String[] args) STATEMENTS verbatim Here CLASSNAME indicates an arbitrary name that you make up. The class name in the example is Hello. class!name static In the second line, you should ignore the words public static void for now, but notice the word main. main is a special name that indicates the place in the program where execution begins. When the program runs, it starts by executing the first statement in main and it continues, in order, until it gets to the last statement, and then it quits. print statement!print There is no limit to the number of statements that can be in main, but the example contains only one. It is a print statement, meaning that it prints a message on the screen. It is a bit confusing that ``print'' sometimes means ``display something on the screen,'' and sometimes means ``send something to the printer.'' In this book I won't say much about sending things to the printer; we'll do all our printing on the screen. The command that prints things on the screen is System.out.println, and the thing between the parentheses is the thing that will get printed. At the end of the statement there is a semi-colon (;), which is required at the end of every statement. There are a few other things you should notice about the syntax of this program. First, Java uses squiggly-braces ( and ) to group things together. The outermost squiggly-braces (lines 1 and 8) contain the class definition, and the inner braces contain the definition of main. comment statement!comment Also, notice that line 3 begins with //. This indicates that this line contains a comment, which is a bit of English text that you can put in the middle of a program, usually to explain what the program does. When the compiler sees a //, it ignores everything from there until the end of the line. In the first lab you will compile and run this program, and also modify it in various ways in order to see what the syntax rules are, and to see what error messages the compiler generates when you violate one. Glossary description [problem-solving:] The process of formulating a problem, finding a solution, and expressing the solution. [high-level language:] A programming language like Java that is designed to be easy for humans to read and write. [low-level language:] A programming language that is designed to be easy for a computer to execute. Also called ``machine language'' or ``assembly language.'' [formal language:] Any of the languages people have designed for specific purposes, like representing mathematical ideas or computer programs. All programming languages are formal languages. [natural language:] Any of the languages people speak that have evolved naturally. [portability:] A property of a program that can run on more than one kind of computer. [interpret:] To execute a program in a high-level language by translating it one line at a time. [compile:] To translate a program in a high-level language into a low-level language, all at once, in preparation for later execution. [source code:] A program in a high-level language, before being compiled. [object code:] The output of the compiler, after translating the program. [executable:] Another name for object code that is ready to be executed. [byte code:] A special kind of object code used for Java programs. Byte code is similar to a low-level language, but it is portable, like a high-level language. [algorithm:] A general process for solving a category of problems. [bug:] An error in a program. [syntax:] The structure of a program. [semantics:] The meaning of a program. [parse:] To examine a program and analyze the syntactic structure. [syntax error:] An error in a program that makes it impossible to parse (and therefore impossible to compile). [exception:] An error in a program that makes it fail at run-time. Also called a run-time error. [logical error:] An error in a program that makes it do something other than what the programmer intended. [debugging:] The process of finding and removing any of the three kinds of errors. problem-solving high-level language low-level language formal language natural language interpret compile syntax semantics parse exception error debugging description Variables and types More printing print statement!print As I mentioned in the last chapter, you can put as many statements as you want in main. For example, to print more than one line: verbatim class Hello // main: generate some simple output public static void main (String[] args) System.out.println ("Hello, world."); // print one line System.out.println ("How are you?"); // print another verbatim Also, as you can see, it is legal to put comments at the end of a line, as well as on a line by themselves. String type!String The phrases that appear in quotation marks are called strings, because they are made up of a sequence (string) of letters. Actually, strings can contain any combination of letters, numbers, punctuation marks, and other special characters. newline println is short for ``print line,'' because after each line it adds a special character, called a newline, that causes the cursor to move to the next line of the display. The next time println is invoked, the new text appears on the next line. Often it is useful to display the output from multiple print statements all on one line. You can do this with the print command: verbatim class Hello // main: generate some simple output public static void main (String[] args) System.out.print ("Goodbye, "); System.out.println ("cruel world!"); verbatim In this case the output appears on a single line as Goodbye, cruel world!. Notice that there is a space between the word ``Goodbye'' and the second quotation mark. This space appears in the output, so it affects the behavior of the program. Spaces that appear outside of quotation marks generally do not affect the behavior of the program. For example, I could have written: verbatim class Hello public static void main (String[] args) System.out.print ("Goodbye, "); System.out.println ("cruel world!"); verbatim This program would compile and run just as well as the original. The breaks at the ends of lines (newlines) do not affect the program's behavior either, so I could have written: verbatim class Hello public static void main (String[] args) System.out.print ("Goodbye, "); System.out.println ("cruel world!"); verbatim That would work, too, although you have probably noticed that the program is getting harder and harder to read. Newlines and spaces are useful for organizing your program visually, making it easier to read the program and locate syntax errors. Variables variable value One of the most powerful features of a programming language is the ability to manipulate variables. A variable is a named location that stores a value. Values are things that can be printed and stored and (as we'll see later) operated on. The strings we have been printing ("Hello, World.", "Goodbye, ", etc.) are values. In order to store a value, you have to create a variable. Since the values we want to store are strings, we will declare that the new variable is a string: verbatim String fred; verbatim This statement is a declaration, because it declares that the variable named fred has the type String. Each variable has a type that determines what kind of values it can store. For example, the int type can store integers, and it will probably come as no surprise that the String type can store strings. declaration statement!declaration You will notice that some types begin with a capital letter and some with lower-case. We will learn the significance of this distinction later, but for now you should take care to get it right. There is no such type as Int or string, and the compiler will object if you try to make one up. To create an integer variable, the syntax is int bob;, where bob is the arbitrary name you made up for the variable. In general, you will want to make up variable names that indicate what you plan to do with the variable. For example, if you saw these variable declarations: verbatim String firstName; String lastName; int hour, minute; verbatim you could probably make a good guess at what values would be stored in them. This example also demonstrates the syntax for declaring multiple variables with the same type: hour and second are both integers (int type). Assignment assignment statement!assignment Now that we have created some variables, we would like to store values in them. We do that with an assignment statement. verbatim fred = "Hello."; // give fred the value "Hello." hour = 11; // assign the value 11 to hour minute = 59; // set minute to 59 verbatim This example shows three assignments, and the comments show three different ways people sometimes talk about assignment statements. The vocabulary can be confusing here, but the idea is straightforward: itemize When you declare a variable, you create a named storage location. When you make an assignment to a variable, you give it a value. itemize A common way to represent variables on paper is to draw a box with the name of the variable on the outside and the value of the variable on the inside. This figure shows the effect of the three assignment statements: figure=figs/assign.eps For each variable, the name of the variable appears outside the box and the value appears inside. As a general rule, a variable has to have the same type as the value you assign it. You cannot store a String in minute or an integer in fred. On the other hand, that rule can be confusing, because there are many ways that you can convert values from one type to another, and Java sometimes converts things automatically. So for now you should remember the general rule, and we'll talk about special cases later. Another source of confusion is that some strings look like integers, but they are not. For example, fred can contain the string "123", which is made up of the characters 1, 2 and 3, but that is not the same thing as the number 123. verbatim fred = "123"; // legal fred = 123; // not legal verbatim Printing variables printing You can print the value of a variable using the same commands we used to print Strings. verbatim class Hello public static void main (String[] args) String firstLine; firstLine = "Hello, again!"; System.out.println (firstLine); verbatim This program creates a variable named firstLine, assigns it the value "Hello, again!" and then prints that value. When we talk about ``printing a variable,'' we mean printing the value of the variable. To print the name of a variable, you have to put it in quotes. For example: System.out.println ("firstLine"); If you want to get a little tricky, you could write verbatim String firstLine; firstLine = "Hello, again!"; System.out.print ("The value of firstLine is "); System.out.println (firstLine); verbatim The output of this program is verbatim The value of firstLine is Hello, again! verbatim I am pleased to report that the syntax for printing a variable is the same regardless of the variable's type. verbatim int hour, minute; hour = 11; minute = 59; System.out.print ("The current time is "); System.out.print (hour); System.out.print (":"); System.out.print (minute); System.out.println ("."); verbatim The output of this program is The current time is 11:59. WARNING: It is common practice to use several print commands followed by a println, in order to put multiple values on the same line. But you have to be careful to remember the println at the end. In many environments, the output from print is stored without being displayed until the println command is invoked, at which point the entire line is displayed at once. If you omit println, the program may terminate without ever displaying the stored output! Keywords keyword A few sections ago, I said that you can make up any name you want for your variables, but that's not quite true. There are certain words that are reserved in Java because they are used by the compiler to parse the structure of your program, and if you use them as variable names, it will get confused. These words, called keywords, include public, class, void, int, and many more. The complete list is available at verbatim http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html verbatim This site, provided by Sun, includes Java documentation I will be referring to throughout the book. Rather than memorize the list, I would suggest that you take advantage of a feature provided in many Java development environments: code highlighting. As you type, different parts of your program should appear in different colors. For example, keywords might be blue, strings red, and other code black. If you type a variable name and it turns blue, watch out! You might get some strange behavior from the compiler. Operators operator Operators are special symbols that are used to represent simple computations like addition and multiplication. Most of the operators in Java do exactly what you would expect them to do, because they are common mathematical symbols. For example, the operator for adding two integers is +. The following are all legal Java expressions whose meaning is more or less obvious: verbatim 1+1 hour-1 hour*60 + minute minute/60 verbatim Expressions can contain both variable names and numbers. In each case the name of the variable is replaced with its value before the computation is performed. expression Addition, subtraction and multiplication all do what you expect, but you might be surprised by division. For example, the following program: verbatim int hour, minute; hour = 11; minute = 59; System.out.print ("Number of minutes since midnight: "); System.out.println (hour*60 + minute); System.out.print ("Fraction of the hour that has passed: "); System.out.println (minute/60); verbatim would generate the following output: verbatim Number of minutes since midnight: 719 Fraction of the hour that has passed: 0 verbatim The first line is what we expected, but the second line is odd. The value of the variable minute is 59, and 59 divided by 60 is 0.98333, not 0. The reason for the discrepancy is that Java is performing integer division. type!int integer division arithmetic!integer division!integer operand When both of the operands are integers (operands are the things operators operate on), the result must also be an integer, and by convention integer division always rounds down, even in cases like this where the next integer is so close. A possible alternative in this case is to calculate a percentage rather than a fraction: verbatim System.out.print ("Percentage of the hour that has passed: "); System.out.println (minute*100/60); verbatim The result is: verbatim Percentage of the hour that has passed: 98 verbatim Again the result is rounded down, but at least now the answer is approximately correct. In order to get an even more accurate answer, we could use a different type of variable, called floating-point, that is capable of storing fractional values. We'll get to that in the next chapter. Order of operations precedence order of operations When more than one operator appears in an expression the order of evaluation depends on the rules of precedence. A complete explanation of precedence can get complicated, but just to get you started: itemize Multiplication and division take precedence (happen before) addition and subtraction. So 2*3-1 yields 5, not 4, and 2/3-1 yields -1, not 1 (remember that in integer division 2/3 is 0). If the operators have the same precedence they are evaluated from left to right. So in the expression minute*100/60, the multiplication happens first, yielding 5900/60, which in turn yields 98. If the operations had gone from right to left, the result would be 59*1 which is 59, which is wrong. Any time you want to override the rules of precedence (or you are not sure what they are) you can use parentheses. Expressions in parentheses are evaluated first, so 2 * (3-1) is 4. You can also use parentheses to make an expression easier to read, as in (minute * 100) / 60, even though it doesn't change the result. itemize Operators for Strings string operator operator!string In general you cannot perform mathematical operations on Strings, even if the strings look like numbers. The following are illegal (if we know that fred has type String) verbatim fred - 1 "Hello"/123 fred * "Hello" verbatim By the way, can you tell by looking at those expressions whether fred is an integer or a string? Nope. The only way to tell the type of a variable is to look at the place where it is declared. concatenate Interestingly, the + operator does work with Strings, although it does not do exactly what you might expect. For Strings, the + operator represents concatenation, which means joining up the two operands by linking them end-to-end. So "Hello, " + "world." yields the string "Hello, world." and fred + "ism" adds the suffix ism to the end of whatever fred is, which is often handy for naming new forms of bigotry. Composition composition expression So far we have looked at the elements of a programming language---variables, expressions, and statements---in isolation, without talking about how to combine them. One of the most useful features of programming languages is their ability to take small building blocks and compose them. For example, we know how to multiply numbers and we know how to print; it turns out we can do both at the same time: verbatim System.out.println (17 * 3); verbatim Actually, I shouldn't say ``at the same time,'' since in reality the multiplication has to happen before the printing, but the point is that any expression, involving numbers, strings, and variables, can be used inside a print statement. We've already seen one example: verbatim System.out.println (hour*60 + minute); verbatim But you can also put arbitrary expressions on the right-hand side of an assignment statement: verbatim int percentage; percentage = (minute * 100) / 60; verbatim This ability may not seem so impressive now, but we will see other examples where composition makes it possible to express complex computations neatly and concisely. WARNING: There are limits on where you can use certain expressions; most notably, the left-hand side of an assignment statement has to be a variable name, not an expression. That's because the left side indicates the storage location where the result will go. Expressions do not represent storage locations, only values. So the following is illegal: minute+1 = hour;. Glossary description [variable:] A named storage location for values. All variables have a type, which is declared when the variable is created. [value:] A number or string (or other thing to be named later) that can be stored in a variable. Every value belongs to one type. [type:] A set of values. The type of a variable determines which values can be stored there. So far, the types we have seen are integers (int in Java) and strings (String in Java). [keyword:] A reserved word that is used by the compiler to parse programs. You cannot use keywords, like public, class and void as variable names. [statement:] A line of code that represents a command or action. So far, the statements we have seen are declarations, assignments, and print statements. [declaration:] A statement that creates a new variable and determines its type. [assignment:] A statement that assigns a value to a variable. [expression:] A combination of variables, operators and values that represents a single result value. Expressions also have types, as determined by their operators and operands. [operator:] A special symbol that represents a simple computation like addition, multiplication or string concatenation. [operand:] One of the values on which an operator operates. [precedence:] The order in which operations are evaluated. [concatenate:] To join two operands end-to-end. [composition:] The ability to combine simple expressions and statements into compound statements and expressions in order to represent complex computations concisely. variable value type keyword statement assignment expression operator concatenate operand composition description Methods Floating-point floating-point type!double double (floating-point) In the last chapter we had some problems dealing with numbers that were not integers. We worked around the problem by measuring percentages instead of fractions, but a more general solution is to use floating-point numbers, which can represent fractions as well as integers. In Java, the floating-point type is called double. You can create floating-point variables and assign values to them using the same syntax we used for the other types. For example: verbatim double pi; pi = 3.14159; verbatim It is also legal to declare a variable and assign a value to it at the same time: verbatim int x = 1; String empty = ""; double pi = 3.14159; verbatim In fact, this syntax is quite common. A combined declaration and assignment is sometimes called an initialization. initialization Although floating-point numbers are useful, they are often a source of confusion because there seems to be an overlap between integers and floating-point numbers. For example, if you have the value 1, is that an integer, a floating-point number, or both? Strictly speaking, Java distinguishes the integer value 1 from the floating-point value 1.0, even though they seem to be the same number. They belong to different types, and strictly speaking, you are not allowed to make assignments between types. For example, the following is illegal: verbatim int x = 1.1; verbatim because the variable on the left is an int and the value on the right is a double. But it is easy to forget this rule, especially because there are places where Java will automatically convert from one type to another. For example: verbatim double y = 1; verbatim should technically not be legal, but Java allows it by converting the int to a double automatically. This leniency is convenient, but it can cause problems; for example: verbatim double y = 1 / 3; verbatim You might expect the variable y to be given the value 0.333333, which is a legal floating-point value, but in fact it will get the value 0.0. The reason is that the expression on the right appears to be the ratio of two integers, so Java does integer division, which yields the integer value 0. Converted to floating-point, the result is 0.0. One way to solve this problem (once you figure out what it is) is to make the right-hand side a floating-point expression: verbatim double y = 1.0 / 3.0; verbatim This sets y to 0.333333, as expected. arithmetic!floating-point All the operations we have seen so far---addition, subtraction, multiplication, and division---also work on floating-point values, although you might be interested to know that the underlying mechanism is completely different. In fact, most processors have special hardware just for performing floating-point operations. Converting from double to int rounding rounding typecasting As I mentioned, Java converts ints to doubles automatically if necessary, because no information is lost in the translation. On the other hand, going from a double to an int requires rounding off. Java doesn't perform this operation automatically, in order to make sure that you, as the programmer, are aware of the loss of the fractional part of the number. The simplest way to convert a floating-point value to an integer is to use a typecast. Typecasting is so called because it allows you to take a value that belongs to one type and ``cast'' it into another type (in the sense of molding or reforming, not throwing). Unfortunately, the syntax for typecasting is ugly: you put the name of the type in parentheses and use it as an operator. For example, verbatim int x = (int) Math.PI; verbatim The (int) operator has the effect of converting what follows into an integer, so x gets the value 3. Typecasting takes precedence over arithmetic operations, so in the following example, the value of PI gets converted to an integer first, and the result is 60, not 62. verbatim int x = (int) Math.PI * 20.0; verbatim Converting to an integer always rounds down, even if the fraction part is 0.99999999. These two properties (precedence and rounding) can make typecasting awkward. Math methods Math class class!Math expression argument In mathematics, you have probably seen functions like and , and you have learned to evaluate expressions like and . First, you evaluate the expression in parentheses, which is called the argument of the function. For example, is approximately 1.571, and is 0.1 (assuming that is 10). Then you can evaluate the function itself, either by looking it up in a table or by performing various computations. The of 1.571 is 1, and the of 0.1 is -1 (assuming that indicates the logarithm base 10). This process can be applied repeatedly to evaluate more complicated expressions like . First we evaluate the argument of the innermost function, then evaluate the function, and so on. Java provides a set of built-in functions that includes most of the mathematical operations you can think of. These functions are called methods. Most math methods operate on doubles. The math methods are invoked using a syntax that is similar to the print commands we have already seen: verbatim double root = Math.sqrt (17.0); double angle = 1.5; double height = Math.sin (angle); verbatim The first example sets root to the square root of 17. The second example finds the sine of 1.5, which is the value of the variable angle. Java assumes that the values you use with sin and the other trigonometric functions (cos, tan) are in radians. To convert from degrees to radians, you can divide by 360 and multiply by . Conveniently, Java provides as a built-in value: verbatim double degrees = 90; double angle = degrees * 2 * Math.PI / 360.0; verbatim Notice that PI is in all capital letters. Java does not recognize Pi, pi, or pie. Another useful method in the Math class is round, which rounds a floating-point value off to the nearest integer and returns an int. verbatim int x = Math.round (Math.PI * 20.0); verbatim In this case the multiplication happens first, before the method is invoked. The result is 63 (rounded up from 62.8319). Composition composition composition expression Just as with mathematical functions, Java methods can be composed, meaning that you use one expression as part of another. For example, you can use any expression as an argument to a method: verbatim double x = Math.cos (angle + Math.PI/2); verbatim This statement takes the value Math.PI, divides it by two and adds the result to the value of the variable angle. The sum is then passed as an argument to the cos method. (Notice that PI is the name of a variable, not a method, so there are no arguments, not even the empty argument ()). You can also take the result of one method and pass it as an argument to another: verbatim double x = Math.exp (Math.log (10.0)); verbatim In Java, the log function always uses base , so this statement finds the log base of 10 and then raises to that power. The result gets assigned to x; I hope you know what it is. Adding new methods method!definition main method!main So far we have only been using the methods that are built into Java, but it is also possible to add new methods. Actually, we have already seen one method definition: main. The method named main is special in that it indicates where the execution of the program begins, but the syntax for main is the same as for other method definitions: verbatim public static void NAME ( LIST OF PARAMETERS ) STATEMENTS verbatim You can make up any name you want for your method, except that you can't call it main or any other Java keyword. The list of parameters specifies what information, if any, you have to provide in order to use (or invoke) the new function. body!method The single parameter for main is String[] args, which indicates that whoever invokes main has to provide an array of Strings (we'll get to arrays in Chapter arrays). The first couple of methods we are going to write have no parameters, so the syntax looks like this: verbatim public static void newLine () System.out.println (""); verbatim This method is named newLine, and the empty parentheses indicate that it takes no parameters. It contains only a single statement, which prints an empty String, indicated by "". Printing a String with no letters in it may not seem all that useful, except remember that println skips to the next line after it prints, so this statement has the effect of skipping to the next line. In main we can invoke this new method using syntax that is similar to the way we invoke the built-in Java commands: verbatim public static void main (String[] args) System.out.println ("First line."); newLine (); System.out.println ("Second line."); verbatim The output of this program is verbatim First line. Second line. verbatim Notice the extra space between the two lines. What if we wanted more space between the lines? We could invoke the same method repeatedly: verbatim public static void main (String[] args) System.out.println ("First line."); newLine (); newLine (); newLine (); System.out.println ("Second line."); verbatim Or we could write a new method, named threeLine, that prints three new lines: verbatim public static void threeLine () newLine (); newLine (); newLine (); public static void main (String[] args) System.out.println ("First line."); threeLine (); System.out.println ("Second line."); verbatim You should notice a few things about this program: itemize You can invoke the same procedure repeatedly. In fact, it is quite common and useful to do so. You can have one method invoke another method. In this case, main invokes threeLine and threeLine invokes newLine. Again, this is common and useful. In threeLine I wrote three statements all on the same line, which is syntactically legal (remember that spaces and new lines usually don't change the meaning of a program). On the other hand, it is usually a better idea to put each statement on a line by itself, to make your program easy to read. I sometimes break that rule in this book to save space. itemize So far, it may not be clear why it is worth the trouble to create all these new methods. Actually, there are a lot of reasons, but this example only demonstrates two: enumerate Creating a new method gives you an opportunity to give a name to a group of statements. Methods can simplify a program by hiding a complex computation behind a single command, and by using English words in place of arcane code. Which is clearer, newLine or System.out.println ("")? Creating a new method can make a program smaller by eliminating repetitive code. For example, how would you print nine consecutive new lines? You could just invoke threeLine three times. enumerate Classes and methods class method Pulling together all the code fragments from the previous section, the whole class definition looks like this: verbatim class NewLine public static void newLine () System.out.println (""); public static void threeLine () newLine (); newLine (); newLine (); public static void main (String[] args) System.out.println ("First line."); threeLine (); System.out.println ("Second line."); verbatim The first line indicates that this is the class definition for a new class called NewLine. A class is a collection of related methods. In this case, the class named NewLine contains three methods, named newLine, threeLine, and main. The other class we've seen is the Math class. It contains methods named sqrt, sin, and many others. When we invoke a mathematical function, we have to specify the name of the class (Math) and the name of the function. That's why the syntax is slightly different for built-in methods and the methods that we write: verbatim Math.pow (2.0, 10.0); newLine (); verbatim The first statement invokes the pow method in the Math class (which raises the first argument to the power of the second argument). The second statement invokes the newLine method, which Java assumes (correctly) is in the NewLine class, which is what we are writing. If you try to invoke a method from the wrong class, the compiler will generate an error. For example, if you type: verbatim pow (2.0, 10.0); verbatim The compiler will say something like, ``Can't find a method named pow in class NewLine.'' If you have seen this message, you might have wondered why it was looking for pow in your class definition. Now you know. Programs with multiple methods When you look at a class definition that contains several methods, it is tempting to read it from top to bottom, but that is likely to be confusing, because that is not the order of execution of the program. Execution always begins at the first statement of main, regardless of where it is in the program (in this case I deliberately put it at the bottom). Statements are executed one at a time, in order, until you reach a method invocation. Method invocations are like a detour in the flow of execution. Instead of going to the next statement, you go to the first line of the invoked method, execute all the statements there, and then come back and pick up again where you left off. That sounds simple enough, except that you have to remember that one method can invoke another. Thus, while we are in the middle of main, we might have to go off and execute the statements in threeLine. But while we are executing threeLine, we get interrupted three times to go off and execute newLine. For its part, newLine invokes the built-in method println, which causes yet another detour. Fortunately, Java is quite adept at keeping track of where it is, so when println completes, it picks up where it left off in newLine, and then gets back to threeLine, and then finally gets back to main so the program can terminate. Actually, technically, the program does not terminate at the end of main. Instead, execution picks up where it left off in the program that invoked main, which is the Java interpreter. The Java interpreter takes care of things like deleting windows and general cleanup, and then the program terminates. What's the moral of this sordid tale? When you read a program, don't read from top to bottom. Instead, follow the flow of execution. Parameters and arguments parameter argument Some of the built-in methods we have used have parameters, which are values that you provide to let the method do its job. For example, if you want to find the sine of a number, you have to indicate what the number is. Thus, sin takes a double value as a parameter. To print a string, you have to provide the string, which is why println takes a String as a parameter. Some methods take more than one parameter, like pow, which takes two doubles, the base and the exponent. Notice that in each of these cases we have to specify not only how many parameters there are, but also what type they are. So it shouldn't surprise you that when you write a class definition, the parameter list indicates the type of each parameter. For example: verbatim public static void printTwice (String phil) System.out.println (phil); System.out.println (phil); verbatim This method takes a single parameter, named phil, that has type String. Whatever that parameter is (and at this point we have no idea what it is), it gets printed twice. I chose the name phil to suggest that the name you give a parameter is up to you, but in general you want to choose something more illustrative than phil. In order to invoke this method, we have to provide a String. For example, we might have a main method like this: verbatim public static void main (String[] args) printTwice ("Don't make me say this twice!"); verbatim The string you provide is called an argument, and we say that the argument is passed to the method. In this case we are creating a string value that contains the text ``Don't make me say this twice!'' and passing that string as an argument to printTwice where, contrary to its wishes, it will get printed twice. Alternatively, if we had a String variable, we could use it as an argument instead: verbatim public static void main (String[] args) String argument = "Never say never."; printTwice (argument); verbatim Notice something very important here: the name of the variable we pass as an argument (argument) has nothing to do with the name of the parameter (phil). Let me say that again: quote The name of the variable we pass as an argument has nothing to do with the name of the parameter. quote They can be the same or they can be different, but it is important to realize that they are not the same thing, except that they happen to have the same value (in this case the string "Never say never."). The value you provide as an argument must have the same type as the parameter of the method you invoke. This rule is very important, but it often gets complicated in Java for two reasons: itemize There are some methods that can accept arguments with many different types. For example, you can send any type to print and println, and it will do the right thing no matter what. This sort of thing is an exception, though. If you violate this rule, the compiler often generates a confusing error message. Instead of saying something like, ``You are passing the wrong kind of argument to this method,'' it will probably say something to the effect that it could not find a method with that name that would accept an argument with that type. Once you have seen this error message a few times, though, you will figure out how to interpret it. itemize Stack diagrams stack stack diagram diagram!stack Parameters and other variables only exist inside their own methods. Within the confines of main, there is no such thing as phil. If you try to use it, the compiler will complain. Similarly, inside printTwice there is no such thing as argument. One way to keep track of where each variable is defined is with a stack diagram. The stack diagram for the previous example looks like this: figure=figs/stack.eps For each method there is a gray box called a frame that contains the methods parameters and local variables. The name of the method appears outside the frame. As usual, the value of each variable is drawn inside a box with the name of the variable beside it. Methods with multiple parameters time parameter!multiple method!multiple parameter class!Time The syntax for declaring and invoking methods with multiple parameters is a common source of errors. First, remember that you have to declare the type of every parameter. For example verbatim public static void printTime (int hour, int minute) System.out.print (hour); System.out.print (":"); System.out.println (minute); verbatim It might be tempting to write int hour, minute, but that format is only legal for variable declarations, not for parameters. Another common source of confusion is that you do not have to declare the types of arguments. The following is wrong! verbatim int hour = 11; int minute = 59; printTime (int hour, int minute); // WRONG! verbatim In this case, Java can tell the type of hour and minute by looking at their declarations. It is unnecessary and illegal to include the type when you pass them as arguments. The correct syntax is printTime (hour, minute). As an exercise, draw a stack frame for printTime called with the arguments 11 and 59. Methods with results fruitful method method!fruitful You might have noticed by now that some of the methods we are using, like the Math methods, yield results. Other methods, like println and newLine, perform some action but they don't return a value. That raises some questions: itemize What happens if you invoke a method and you don't do anything with the result (i.e. you don't assign it to a variable or use it as part of a larger expression)? What happens if you use a print method as part of an expression, like System.out.println ("boo!") + 7? Can we write methods that yield results, or are we stuck with things like newLine and printTwice? itemize The answer to the third question is ``yes, you can write methods that return values,'' and we'll do it in a couple of chapters. I will leave it up to you to answer the other two questions by trying them out. In fact, any time you have a question about what is legal or illegal in Java, a good way to find out is to ask the compiler. Glossary description [floating-point:] A type of variable (or value) that can contain fractions as well as integers. In Java this type is called double. [class:] A named collection of methods. So far, we have used the Math class and the System class, and we have written classes named Hello and NewLine. [method:] A named sequence of statements that performs some useful function. Methods may or may not take parameters, and may or may not produce a result. [parameter:] A piece of information you provide in order to invoke a method. Parameters are like variables in the sense that they contain values and have types. [argument:] A value that you provide when you invoke a method. This value must have the same type as the corresponding parameter. [invoke:] Cause a method to be executed. floating-point class method parameter argument description Conditionals, graphics and recursion condrecursion The modulus operator modulus operator!modulus The modulus operator works on integers (and integer expressions) and yields the remainder when the first operand is divided by the second. In Java, the modulus operator is a percent sign, . The syntax is exactly the same as for other operators: verbatim int quotient = 7 / 3; int remainder = 7 verbatim The first operator, integer division, yields 2. The second operator yields 1. Thus, 7 divided by 3 is 2 with 1 left over. The modulus operator turns out to be surprisingly useful. For example, you can check whether one number is divisible by another: if x y is zero, then x is divisible by y. Also, you can use the modulus operator to extract the rightmost digit or digits from a number. For example, x 10 yields the rightmost digit of x (in base 10). Similarly x 100 yields the last two digits. Conditional execution conditional statement!conditional In order to write useful programs, we almost always need the ability to check certain conditions and change the behavior of the program accordingly. Conditional statements give us this ability. The simplest form is the if statement: verbatim if (x > 0) System.out.println ("x is positive"); verbatim The expression in parentheses is called the condition. If it is true, then the statements in brackets get executed. If the condition is not true, nothing happens. operator!comparison operator!relational comparison!operator relational operator The condition can contain any of the comparison operators, sometimes called relational operators: verbatim x == y // x equals y x != y // x is not equal to y x > y // x is greater than y x < y // x is less than y x >= y // x is greater than or equal to y x <= y // x is less than or equal to y verbatim Although these operations are probably familiar to you, the syntax Java uses is a little different from mathematical symbols like , and . A common error is to use a single = instead of a double ==. Remember that = is the assignment operator, and == is a comparison operator. Also, there is no such thing as =< or =>. The two sides of a condition operator have to be the same type. You can only compare ints to ints and doubles to doubles. Unfortunately, at this point you can't compare Strings at all! There is a way to compare Strings, but we won't get to it for a couple of chapters. Alternative execution alternative conditional!alternative A second form of conditional execution is alternative execution, in which there are two possibilities, and the condition determines which one gets executed. The syntax looks like: verbatim if (x System.out.println ("x is even"); else System.out.println ("x is odd"); verbatim If the remainder when x is divided by 2 is zero, then we know that x is even, and this code prints a message to that effect. If the condition is false, the second print statement is executed. Since the condition must be true or false, exactly one of the alternatives will be executed. As an aside, if you think you might want to check the parity (evenness or oddness) of numbers often, you might want to ``wrap'' this code up in a method, as follows: verbatim public static void printParity (int x) if (x System.out.println ("x is even"); else System.out.println ("x is odd"); verbatim Now you have a method named printParity that will print an appropriate message for any integer you care to provide. In main you would invoke this method as follows: verbatim printParity (17); verbatim Always remember that when you invoke a method, you do not have to declare the types of the arguments you provide. Java can figure out what type they are. You should resist the temptation to write things like: verbatim int number = 17; printParity (int number); // WRONG!!! verbatim Chained conditionals conditional!chained Sometimes you want to check for a number of related conditions and choose one of several actions. One way to do this is by chaining a series of ifs and elses: verbatim if (x > 0) System.out.println ("x is positive"); else if (x < 0) System.out.println ("x is negative"); else System.out.println ("x is zero"); verbatim These chains can be as long as you want, although they can be difficult to read if they get out of hand. One way to make them easier to read is to use standard indentation, as demonstrated in these examples. If you keep all the statements and squiggly-brackets lined up, you are less likely to make syntax errors and you can find them more quickly if you do. Nested conditionals conditional!nested In addition to chaining, you can also nest one conditional within another. We could have written the previous example as: verbatim if (x == 0) System.out.println ("x is zero"); else if (x > 0) System.out.println ("x is positive"); else System.out.println ("x is negative"); verbatim There is now an outer conditional that contains two branches. The first branch contains a simple print statement, but the second branch contains another conditional statement, which has two branches of its own. Fortunately, those two branches are both print statements, although they could have been conditional statements as well. Notice again that indentation helps make the structure apparent, but nevertheless, nested conditionals get difficult to read very quickly. In general, it is a good idea to avoid them when you can. nested structure On the other hand, this kind of nested structure is common, and we will see it again, so you better get used to it. The return statement return statement!return The return statement allows you to terminate the execution of a method before you reach the end. One reason to use it is if you detect an error condition: verbatim public static void printLogarithm (double x) if (x <= 0.0) System.out.println ("Positive numbers only, please."); return; double result = Math.log (x); System.out.println ("The log of x is " + result); verbatim This defines a method named printLogarithm that takes a double named x as a parameter. The first thing it does is check whether x is less than or equal to zero, in which case it prints an error message and then uses return to exit the method. The flow of execution immediately returns to the caller and the remaining lines of the method are not executed. I used a floating-point value on the right side of the condition because there is a floating-point variable on the left. Type conversion type!conversion typecasting You might wonder how you can get away with an expression like "The log of x is " + result, since one of the operands is a String and the other is a double. Well, in this case Java is being smart on our behalf, by automatically converting the double to a String before it does the string concatenation. This kind of feature is an example of a common problem in designing a programming language, which is that there is a conflict between formalism, which is the requirement that formal languages should have simple rules with few exceptions, and convenience, which is the requirement that programming languages be easy to use in practice. More often than not, convenience wins, which is usually good for expert programmers (who are spared from rigorous but unwieldy formalism), but bad for beginning programmers, who are often baffled by the complexity of the rules and the number of exceptions. In this book I have tried to simplify things by emphasizing the rules and omitting many of the exceptions. Nevertheless, it is handy to know that whenever you try to ``add'' two expressions, if one of them is a String, then Java will convert the other to a String and then perform string concatenation. What do you think happens if you perform an operation between an integer and a floating-point value? Slates and Graphics objects graphics class!Slate class!Graphics Slate Graphics In order to draw things on the screen, you need two objects, a Slate and a Graphics object. description Slate: a Slate is a window that contains a blank rectangle you can draw on. The Slate class is not part of the standard Java library; it is something I wrote for this course. Graphics: the Graphics object is the object we will use to draw lines, circles, etc. It is part of the Java library, so the documentation for it is on the Sun web site. description The methods that pertain to Graphics objects are defined in the built-in Graphics class. The methods that pertain to Slates are defined in the Slate class, which is shown in Appendix slate. The primary method in the Slate class is makeSlate, which does pretty much what you would expect. It creates a new window and returns a Slate object you can use to refer to the window later in the program. You can create more than one Slate in a single program. verbatim Slate slate = Slate.makeSlate (500, 500); verbatim makeSlate takes two arguments, the width and height of the window. Because it belongs to a different class, we have to specify the name of the class using ``dot notation.'' The return value gets assigned to a variable named slate. There is no conflict between the name of the class (with an upper-case ``S'') and the name of the variable (with a lower-case ``s''). The next method we need is getGraphics, which takes a Slate object and creates a Graphics object that can draw on it. You can think of a Graphics object as a piece of chalk. verbatim Graphics g = Slate.getGraphics (slate); verbatim Using the name g is conventional, but we could have called it anything. Invoking methods on a Graphics object method!object method!Graphics setColor drawOval In order to draw things on the screen, you invoke methods on the graphics object. We have invoked lots of methods already, but this is the first time we have ``invoked a method on an object.'' The syntax is similar to invoking a method from another class: verbatim g.setColor (Color.black); g.drawOval (x, y, width, height); verbatim The name of the object comes before the dot; the name of the method comes after, followed by the arguments for that method. In this case, the method takes a single argument, which is a color. setColor changes the current color, in this case to black. Everything that gets drawn will be black, until we use setColor again. Color.black is a special value provided by the Color class, just as Math.PI is a special value provided by the Math class. Color, you will be happy to hear, provides a palette of other colors, including: verbatim black blue cyan darkGray gray lightGray magenta orange pink red white yellow verbatim To draw on the Slate, we can invoke draw methods on the Graphics object. For example: verbatim g.drawOval (x, y, width, height); verbatim drawOval takes four integers as arguments. These arguments specify a bounding box, which is the rectangle in which the oval will be drawn (as shown in the figure). The bounding box itself is not drawn; only the oval is. The bounding box is like a guideline. Bounding boxes are always oriented horizontally or vertically; they are never at a funny angle. bounding box figure=figs/circle.eps If you think about it, there are lots of ways to specify the location and size of a rectangle. You could give the location of the center or any of the corners, along with the height and width. Or, you could give the location of opposing corners. The choice is arbitrary, but in any case it will require the same number of parameters: four. By convention, the usual way to specify a bounding box is to give the location of the upper-left corner and the width and height. The usual way to specify a location is to use a coordinate system. Coordinates coordinate Cartesian coordinate graphics coordinate You are probably familiar with Cartesian coordinates in two dimensions, in which each location is identified by an x-coordinate (distance along the x-axis) and a y-coordinate. By convention, Cartesian coordinates increase to the right and up, as shown in the figure. figure=figs/coordinates.eps,width=5in Annoyingly, it is conventional for computer graphics systems to use a variation on Cartesian coordinates in which the origin is in the upper-left corner of the screen or window, and the direction of the positive y-axis is down. Java follows this convention. pixel The unit of measure is called a pixel; a typical screen is about 1000 pixels wide. Coordinates are always integers. If you want to use a floating-point value as a coordinate, you have to round it off to an integer (See Section rounding). A lame Mickey Mouse Mickey Mouse Let's say we want to draw a picture of Mickey Mouse. We can use the oval we just drew as the face, and then add ears. Before we do that it is a good idea to break the program up into two methods. main will create the Slate and Graphics objects and then invoke draw, which does the actual drawing. verbatim public static void main (String[] args) int width = 500; int height = 500; Slate slate = Slate.makeSlate (width, height); Graphics g = Slate.getGraphics (slate); g.setColor (Color.black); draw (g, 0, 0, width, height); public static void draw (Graphics g, int x, int y, int width, int height) g.drawOval (x, y, width, height); g.drawOval (x, y, width/2, height/2); g.drawOval (x+width/2, y, width/2, height/2); verbatim The parameters for draw are the Graphics object and a bounding box. draw invokes drawOval three times, to draw Mickey's face and two ears. The following figure shows the bounding boxes for the ears. figure=figs/mickey.eps As shown in the figure, the coordinates of the upper-left corner of the bounding box for the left ear are (x, y). The coordinates for the right ear are (x+width/2, y). In both cases, the width and height of the ears are half the width and height of the original bounding box. Notice that the coordinates of the ear boxes are all relative to the location (x and y) and size (width and height) of the original bounding box. As a result, we can use draw to draw a Mickey Mouse (albeit a lame one) anywhere on the screen in any size. As an exercise, modify the arguments passed to draw so that Mickey is one half the height and width of the screen, and centered. Other drawing commands prototype drawLine drawRect fillOval fillRect prototype interface Another drawing command with the same parameters as drawOval is verbatim drawRect (int x, int y, int width, int height) verbatim Here I am using a standard format for documenting the name and parameters of methods. This information is sometimes called the method's interface or prototype. Looking at this prototype, you can tell what types the parameters are and (based on their names) infer what they do. Here's another example: verbatim drawLine (int x1, int y1, int x2, int y2) verbatim The use of parameter names x1, x2, y1 and y2 suggests that drawLine draws a line from the point (x1, y1) to the point (x2, y2). One other command you might want to try is verbatim drawRoundRect (int x, int y, int width, int height, int arcWidth, int arcHeight) verbatim The first four parameters specify the bounding box of the rectangle; the remaining two parameters indicate how rounded the corners should be, specifying the horizontal and vertical diameter of the arcs at the corners. There are also ``fill'' versions of these commands, that not only draw the outline of a shape, but also fill it in. The interfaces are identical; only the names have been changed: verbatim fillOval (int x, int y, int width, int height) fillRect (int x, int y, int width, int height) fillRoundRect (int x, int y, int width, int height, int arcWidth, int arcHeight) verbatim There is no such thing as fillLine---it just doesn't make sense. Recursion recursion recursion I mentioned in the last chapter that it is legal for one method to call another, and we have seen several examples of that. I neglected to mention that it is also legal for a method to invoke itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do. For example, look at the following method: verbatim public static void countdown (int n) if (n == 0) System.out.println ("Blastoff!"); else System.out.println (n); countdown (n-1); verbatim The name of the method is countdown and it takes a single integer as a parameter. If the parameter is zero, it prints the word ``Blastoff.'' Otherwise, it prints the number and then invokes a method named countdown---itself---passing n-1 as an argument. What happens if we invoke this method, in main, like this: verbatim countdown (3); verbatim The execution of countdown begins with n=3, and since n is not zero, it prints the value 3, and then invokes itself... quote The execution of countdown begins with n=2, and since n is not zero, it prints the value 2, and then invokes itself... quote The execution of countdown begins with n=1, and since n is not zero, it prints the value 1, and then invokes itself... quote The execution of countdown begins with n=0, and since n is zero, it prints the word ``Blastoff!'' and then returns. quote The countdown that got n=1 returns. quote The countdown that got n=2 returns. quote The countdown that got n=3 returns. And then you're back in main (what a trip). So the total output looks like: verbatim 3 2 1 Blastoff! verbatim As a second example, let's look again at the methods newLine and threeLine. verbatim public static void newLine () System.out.println (""); public static void threeLine () newLine (); newLine (); newLine (); verbatim Although these work, they would not be much help if I wanted to print 2 newlines, or 106. A better alternative would be verbatim public static void nLines (int n) if (n > 0) System.out.println (""); nLines (n-1); verbatim This program is very similar; as long as n is greater than zero, it prints one newline, and then invokes itself to print n-1 additional newlines. Thus, the total number of newlines that get printed is 1 + (n-1), which usually comes out to roughly n. recursive newline The process of a method invoking itself is called recursion, and such methods are said to be recursive. Stack diagrams for recursive methods stack diagram!state diagram!stack In the previous chapter we used a stack diagram to represent the state of a program during a method call. The same kind of diagram can make it easier to interpret a recursive method. Remember that every time a method gets called it creates a new instance of the method that contains a new version of the method's local variables and parameters. The following figure is a stack diagram for countdown, called with n = 3: figure=figs/stack2.eps There is one instance of main and four instances of countdown, each with a different value for the parameter n. The bottom of the stack, countdown with n=0 is the base case. It does not make a recursive call, so there are no more instances of countdown. The instance of main is empty because main does not have any parameters or local variables. As an exercise, draw a stack diagram for nLines, invoked with the parameter n=4. Convention and divine law convention divine law In the last few sections, I used the phrase ``by convention'' several times to indicate design decisions that are arbitrary in the sense that there are no significant reasons to do things one way or another, but dictated by convention. In these cases, it is to your advantage to be familiar with convention and use it, since it will make your programs easier for others to understand. At the same time, it is important to distinguish between (at least) three kinds of rules: description [Divine law:] This is my phrase to indicate a rule that is true because of some underlying principle of logic or mathematics, and that is true in any programming language (or other formal system). For example, there is no way to specify the location and size of a bounding box using fewer than four pieces of information. Another example is that adding integers is commutative. That's part of the definition of addition and has nothing to do with Java. [Rules of Java:] These are the syntactic and semantic rules of Java that you cannot violate, because the resulting program will not compile or run. Some are arbitrary; for example, the fact that the + symbol represents addition and string concatenation. Others reflect underlying limitations of the compilation or execution process. For example, you have to specify the types of parameters, but not arguments. [Style and convention:] There are a lot of rules that are not enforced by the compiler, but that are essential for writing programs that are correct, that you can debug and modify, and that others can read. Examples include indentation and the placement of squiggly braces, as well as conventions for naming variables, methods and classes. description As we go along, I will try to indicate which category various things fall into, but you might want to give it some thought from time to time. While I am on the topic, you have probably figured out by now that the names of classes always begin with a capital letter, but variables and methods begin with lower case. If a name includes more than one word, you usually capitalize the first letter of each word, as in newLine and printParity. Which category are these rules in? Glossary description [modulus:] An operator that works on integers and yields the remainder when one number is divided by another. In Java it is denoted with a percent sign (). [conditional:] A block of statements that may or may not be executed depending on some condition. [chaining:] A way of joining several conditional statements in sequence. [nesting:] Putting a conditional statement inside one or both branches of another conditional statement. [coordinate:] A variable or value that specifies a location in a two-dimensional graphical window. [pixel:] The unit in which coordinates are measured. [bounding box:] A common way to specify the coordinates of a rectangular area. [typecast:] An operator that converts from one type to another. In Java it appears as a type name in parentheses, like (int). [interface:] A description of the parameters required by a method and their types. [prototype:] A way of describing the interface to a method using Java-like syntax. [recursion:] The process of invoking the same method you are currently executing. [infinite recursion:] A method that invokes itself recursively without ever reaching the base case. The usual result is a StackOverflowException. [fractal:] A kind of image that is defined recursively, so that each part of the image is a smaller version of the whole. modulus conditional conditional!chained conditional!nested coordinate bounding box typecast interface prototype recursion fractal recursion!infinite infinite recursion exception!StackOverflow description Fruitful methods Return values return statement!return method!fruitful fruitful method return value void method!void Some of the built-in methods we have used, like the Math functions, have produced results. That is, the effect of invoking the method is to generate a new value, which we usually assign to a variable or use as part of an expression. For example: verbatim double e = Math.exp (1.0); double height = radius * Math.sin (angle); verbatim But so far all the methods we have written have been void methods; that is, methods that return no value. When you invoke a void method, it is typically on a line by itself, with no assignment: verbatim nLines (3); g.drawOval (0, 0, width, height); verbatim In this chapter, we are going to write methods that return things, which I will refer to as fruitful methods, for want of a better name. The first example is area, which takes a double as a parameter, and returns the area of a circle with the given radius: verbatim public static double area (double radius) double area = Math.PI * radius * radius; return area; verbatim The first thing you should notice is that the beginning of the method definition is different. Instead of public static void, which indicates a void method, we see public static double, which indicates that the return value from this method will have type double. I still haven't explained what public static means, but be patient. static Also, notice that the last line is an alternate form of the return statement that includes a return value. This statement means, ``return immediately from this method and use the following expression as a return value.'' The expression you provide can be arbitrarily complicated, so we could have written this method more concisely: verbatim public static double area (double radius) return Math.PI * radius * radius; verbatim On the other hand, temporary variables like area often make debugging easier. In either case, the type of the expression in the return statement must match the return type of the method. In other words, when you declare that the return type is double, you are making a promise that this method will eventually produce a double. If you try to return with no expression, or an expression with the wrong type, the compiler will take you to task. temporary variable variable!temporary Sometimes it is useful to have multiple return statements, one in each branch of a conditional: verbatim public static double absoluteValue (double x) if (x < 0) return -x; else return x; verbatim Since these return statements are in an alternative conditional, only one will be executed. Although it is legal to have more than one return statement in a method, you should keep in mind that as soon as one is executed, the method terminates without executing any subsequent statements. Code that appears after a return statement, or any place else where it can never be executed, is called dead code. Some compilers warn you if part of your code is dead. dead code If you put return statements inside a conditional, then you have to guarantee that every possible path through the program hits a return statement. For example: verbatim public static double absoluteValue (double x) if (x < 0) return -x; else if (x > 0) return x; // WRONG!! verbatim This program is not legal because if x happens to be 0, then neither condition will be true and the method will end without hitting a return statement. A typical compiler message would be ``return statement required in absoluteValue,'' which is a confusing message considering that there are already two of them. Program development distance program development At this point you should be able to look at complete Java methods and tell what they do. But it may not be clear yet how to go about writing them. I am going to suggest one technique that I call incremental development. incremental development As an example, imagine you want to find the distance between two points, given by the coordinates and . By the usual definition, equation distance = (x_2 - x_1)^2 + (y_2 - y_1)^2 equation The first step is to consider what a distance method should look like in Java. In other words, what are the inputs (parameters) and what is the output (return value). In this case, the two points are the parameters, and it is natural to represent them using four doubles, although we will see later that there is a Point object in Java that we could use. The return value is the distance, which will have type double. Already we can write an outline of the method: verbatim public static double distance (double x1, double y1, double x2, double y2) return 0.0; verbatim The statement return 0.0; is a place-keeper that is necessary in order to compile the program. Obviously, at this stage the program doesn't do anything useful, but it is worthwhile to try compiling it so we can identify any syntax errors before we make it more complicated. In order to test the new method, we have to invoke it with sample values. Somewhere in main I would add: verbatim double dist = distance (1.0, 2.0, 4.0, 6.0); verbatim I chose these values so that the horizontal distance is 3 and the vertical distance is 4; that way, the result will be 5 (the hypotenuse of a 3-4-5 triangle). When you are testing a method, it is useful to know the right answer. Once we have checked the syntax of the method definition, we can start adding lines of code one at a time. After each incremental change, we recompile and run the program. That way, at any point we know exactly where the error must be---in the last line we added. The next step in the computation is to find the differences and . I will store those values in temporary variables named dx and dy. verbatim public static double distance (double x1, double y1, double x2, double y2) double dx = x2 - x1; double dy = y2 - y1; System.out.println ("dx is " + dx); System.out.println ("dy is " + dy); return 0.0; verbatim I added print statements that will let me check the intermediate values before proceeding. As I mentioned, I already know that they should be 3.0 and 4.0. scaffolding When the method is finished I will remove the print statements. Code like that is called scaffolding, because it is helpful for building the program, but it is not part of the final product. Sometimes it is a good idea to keep the scaffolding around, but comment it out, just in case you need it later. The next step in the development is to square dx and dy. We could use the Math.pow method, but it is simpler and faster to just multiply each term by itself. verbatim public static double distance (double x1, double y1, double x2, double y2) double dx = x2 - x1; double dy = y2 - y1; double dsquared = dx*dx + dy*dy; System.out.println ("dsquared is " + dsquared); return 0.0; verbatim Again, I would compile and run the program at this stage and check the intermediate value (which should be 25.0). Finally, we can use the Math.sqrt method to compute and return the result. verbatim public static double distance (double x1, double y1, double x2, double y2) double dx = x2 - x1; double dy = y2 - y1; double dsquared = dx*dx + dy*dy; double result = Math.sqrt (dsquared); return result; verbatim Then in main, we should print and check the value of the result. As you gain more experience programming, you might find yourself writing and debugging more than one line at a time. Nevertheless, this incremental development process can save you a lot of debugging time. The key aspects of the process are: itemize Start with a working program and make small, incremental changes. At any point, if there is an error, you will know exactly where it is. Use temporary variables to hold intermediate values so you can print and check them. Once the program is working, you might want to remove some of the scaffolding or consolidate multiple statements into compound expressions, but only if it does not make the program difficult to read. itemize Composition composition As you should expect by now, once you define a new method, you can use it as part of an expression, and you can build new methods using existing methods. For example, what if someone gave you two points, the center of the circle and a point on the perimeter, and asked for the area of the circle? Let's say the center point is stored in the variables xc and yc, and the perimeter point is in xp and yp. The first step is to find the radius of the circle, which is the distance between the two points. Fortunately, we have a method, distance that does that. verbatim double radius = distance (xc, yc, xp, yp); verbatim The second step is to find the area of a circle with that radius, and return it. verbatim double area = area (radius); return area; verbatim Wrapping that all up in a method, we get: verbatim public static double fred (double xc, double yc, double xp, double yp) double radius = distance (xc, yc, xp, yp); double area = area (radius); return area; verbatim The name of this method is fred, which may seem odd. I will explain why in the next section. The temporary variables radius and area are useful for development and debugging, but once the program is working we can make it more concise by composing the method invocations: verbatim public static double fred (double xc, double yc, double xp, double yp) return area (distance (xc, yc, xp, yp)); verbatim Overloading overloading overloading In the previous section you might have noticed that fred and area perform similar functions---finding the area of a circle---but take different parameters. For area, we have to provide the radius; for fred we provide two points. If two methods do the same thing, it is natural to give them the same name. In other words, it would make more sense if fred were called area. Having more than one method with the same name, which is called overloading, is legal in Java as long as each version takes different parameters. So we can go ahead and rename fred: verbatim public static double area (double x1, double y1, double x2, double y2) return area (distance (xc, yc, xp, yp)); verbatim When you invoke an overloaded method, Java knows which version you want by looking at the arguments that you provide. If you write: verbatim double x = area (3.0); verbatim Java goes looking for a method named area that takes a single double as an argument, and so it uses the first version, which interprets the argument as a radius. If you write: verbatim double x = area (1.0, 2.0, 4.0, 6.0); verbatim Java uses the second version of area. More amazing still, the second version of area actually invokes the first. Many of the built-in Java commands are overloaded, meaning that there are different versions that accept different numbers or types of parameters. For example, there are versions of print and println that accept a single parameter of any type. In the Math class, there is a version of abs that works on doubles, and there is also a version for ints. Although overloading is a useful feature, it should be used with caution. You might get yourself nicely confused if you are trying to debug one version of a method while accidently invoking a different one. Actually, that reminds me of one of the cardinal rules of debugging: make sure that the version of the program you are looking at is the version of the program that is running! Some time you may find yourself making one change after another in your program, and seeing the same thing every time you run it. This is a warning sign that for one reason or another you are not running the version of the program you think you are. To check, stick in a print statement (it doesn't matter what you print) and make sure the behavior of the program changes accordingly. Boolean expressions boolean expression!boolean Most of the operations we have seen produce results that are the same type as their operands. For example, the + operator takes two ints and produces an int, or two doubles and produces a double, etc. operator!relational relational operator The exceptions we have seen are the relational operators, which compare ints and floats and return either true or false. true and false are special values in Java, and together they make up a type called boolean. You might recall that when I defined a type, I said it was a set of values. In the case of ints, doubles and Strings, those sets are pretty big. For booleans, not so big. Boolean expressions and variables work just like other types of expressions and variables: verbatim boolean fred; fred = true; boolean testResult = false; verbatim The first example is a simple variable declaration; the second example is an assignment, and the third example is a combination of a declaration and an assignment, sometimes called an initialization. The values true and false are keywords in Java, so they may appear in a different color, depending on your development environment. initialization statement!initialization As I mentioned, the result of a conditional operator is a boolean, so you can store the result of a comparison in a variable: verbatim boolean evenFlag = (n boolean positiveFlag = (x > 0); // true if x is positive verbatim and then use it as part of a conditional statement later: verbatim if (evenFlag) System.out.println ("n was even when I checked it"); verbatim A variable used in this way is frequently called a flag, since it flags the presence or absence of some condition. Logical operators logical operator operator!logical There are three logical operators in Java: AND, OR and NOT, which are denoted by the symbols , and !. The semantics (meaning) of these operators is similar to their meaning in English. For example x > 0 x < 10 is true only if x is greater than zero AND less than 10. semantics evenFlag n3 == 0 is true if either of the conditions is true, that is, if evenFlag is true OR the number is divisible by 3. Finally, the NOT operator has the effect of negating or inverting a boolean expression, so !evenFlag is true if evenFlag is false---if the number is odd. nested structure Logical operators often provide a way to simplify nested conditional statements. For example, how would you write the following code using a single conditional? verbatim if (x > 0) if (x < 10) System.out.println ("x is a positive single digit."); verbatim Boolean methods boolean boolean method!boolean Methods can return boolean values just like any other type, which is often convenient for hiding complicated tests inside methods. For example: verbatim public static boolean isSingleDigit (int x) if (x >= 0 && x < 10) return true; else return false; verbatim The name of this method is isSingleDigit. It is common to give boolean methods names that sound like yes/no questions. The return type is boolean, which means that every return statement has to provide a boolean expression. The code itself is straightforward, although it is a bit longer than it needs to be. Remember that the expression x >= 0 x < 10 has type boolean, so there is nothing wrong with returning it directly, and avoiding the if statement altogether: verbatim public static boolean isSingleDigit (int x) return (x >= 0 && x < 10); verbatim In main you can invoke this method in the usual ways: verbatim boolean bigFlag = !isSingleDigit (17); System.out.println (isSingleDigit (2)); verbatim The first line assigns the value true to bigFlag only if 17 is not a single-digit number. The second line prints true because 2 is a single-digit number. Yes, println is overloaded to handle booleans, too. The most common use of boolean methods is inside conditional statements verbatim if (isSingleDigit (x)) System.out.println ("x is little"); else System.out.println ("x is big"); verbatim More recursion recursion language!complete Now that we have methods that return values, you might be interested to know that we have a complete programming language, by which I mean that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features we have used so far (actually, we would need a few commands to control devices like the keyboard, mouse, disks, etc., but that's all). Turing, Alan Proving this claim is a non-trivial exercise first accomplished by Alan Turing, one of the first computer scientists (well, some would argue that he was a mathematician, but a lot of the early computer scientists started as mathematicians). Accordingly, it is known as the Turing thesis. If you take a course on the Theory of Computation, you will have a chance to see the proof. To give you an idea of what you can do with the tools we have learned so far, let's look at some methods for evaluating recursively-defined mathematical functions. A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is typically not very useful: description [frabjuous:] an adjective used to describe something that is frabjuous. frabjuous description If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the mathematical function factorial, you might get something like: eqnarray* && 0! = 1 && n! = n (n-1)! eqnarray* (Factorial is usually denoted with the symbol , which is not to be confused with the Java logical operator ! which means NOT.) This definition says that the factorial of 0 is 1, and the factorial of any other value, , is multiplied by the factorial of . So is 3 times , which is 2 times , which is 1 times . Putting it all together, we get equal to 3 times 2 times 1 times 1, which is 6. If you can write a recursive definition of something, you can usually write a Java program to evaluate it. The first step is to decide what the parameters are for this function, and what the return type is. With a little thought, you should conclude that factorial takes an integer as a parameter and returns an integer: verbatim public static int factorial (int n) verbatim If the argument happens to be zero, all we have to do is return 1: verbatim public static int factorial (int n) if (n == 0) return 1; verbatim Otherwise, and this is the interesting part, we have to make a recursive call to find the factorial of , and then multiply it by . verbatim public static int factorial (int n) if (n == 0) return 1; else int recurse = factorial (n-1); int result = n * recurse; return result; verbatim If we look at the flow of execution for this program, it is similar to nLines from the previous chapter. If we invoke factorial with the value 3: Since 3 is not zero, we take the second branch and calculate the factorial of ... quote Since 2 is not zero, we take the second branch and calculate the factorial of ... quote Since 1 is not zero, we take the second branch and calculate the factorial of ... quote Since 0 is zero, we take the first branch and return the value 1 immediately without making any more recursive calls. quote The return value (1) gets multiplied by n, which is 1, and the result is returned. quote The return value (1) gets multiplied by n, which is 2, and the result is returned. quote The return value (2) gets multiplied by n, which is 3, and the result, 6, is returned to main, or whoever invoked factorial (3). stack diagram!state diagram!stack Here is what the stack diagram looks like for this sequence of function calls: figure=figs/stack3.eps The return values are shown being passed back up the stack. Notice that in the last instance of factorial, the local variables recurse and result do not exist because when n=0 the branch that creates them does not execute. Leap of faith leap of faith Following the flow of execution is one way to read programs, but as you saw in the previous section, it can quickly become labarynthine. An alternative is what I call the ``leap of faith.'' When you come to a method invocation, instead of following the flow of execution, you assume that the method works correctly and returns the appropriate value. In fact, you are already practicing this leap of faith when you use built-in methods. When you invoke Math.cos or drawOval, you don't examine the implementations of those methods. You just assume that they work, because the people who wrote the built-in classes were good programmers. Well, the same is true when you invoke one of your own methods. For example, in Section boolean we wrote a method called isSingleDigit that determines whether a number is between 0 and 9. Once we have convinced ourselves that this method is correct---by testing and examination of the code---we can use the method without ever looking at the code again. The same is true of recursive programs. When you get to the recursive invocation, instead of following the flow of execution, you should assume that the recursive invocation works (yields the correct result), and then ask yourself, ``Assuming that I can find the factorial of , can I compute the factorial of ?'' In this case, it is clear that you can, by multiplying by . Of course, it is a bit strange to assume that the method works correctly when you have not even finished writing it, but that's why it's called a leap of faith! One more example factorial In the previous example I used temporary variables to spell out the steps, and to make the code easier to debug, but I could have saved a few lines: verbatim public static int factorial (int n) if (n == 0) return 1; else return n * factorial (n-1); verbatim From now on I will tend to use the more concise version, but I recommend that you use the more explicit version while you are developing code. When you have it working, you can tighten it up, if you are feeling inspired. After factorial, the classic example of a recursively-defined mathematical function is fibonacci, which has the following definition: eqnarray* && fibonacci(0) = 1 && fibonacci(1) = 1 && fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); eqnarray* Translated into Java, this is verbatim public static int fibonacci (int n) if (n == 0 n == 1) return 1; else return fibonacci (n-1) + fibonacci (n-2); verbatim If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if we assume that the two recursive calls (yes, you can make two recursive calls) work correctly, then it is clear that we get the right result by adding them together. Glossary description [return type:] The part of a method declaration that indicates what type of value the method returns. [return value:] The value provided as the result of a method invocation. [dead code:] Part of a program that can never be executed, often because it appears after a return statement. [scaffolding:] Code that is used during program development but is not part of the final version. [void:] A special return type that indicates a void method; that is, one that does not return a value. [overloading:] Having more than one method with the same name but different parameters. When you invoke an overloaded method, Java knows which version to use by looking at the arguments you provide. [boolean:] A type of variable that can contain only the two values true and false. [flag:] A variable (usually boolean) that records a condition or status information. [conditional operator:] An operator that compares two values and produces a boolean that indicates the relationship between the operands. [logical operator:] An operator that combines boolean values and produces boolean values. [initialization:] A statement that declares a new variable and assigns a value to it at the same time. return type return value dead code scaffolding void overloading boolean operator!conditional operator!logical initialization description Iteration Multiple assignment assignment statement!assignment multiple assignment I haven't 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. verbatim int fred = 5; System.out.print (fred); fred = 7; System.out.println (fred); verbatim 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, as shown in the figure: figure=figs/assign2.eps 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. It is not! First of all, equality is commutative, and assignment is not. For example, in mathematics if then . 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 now, then will always equal . In Java, an assignment statement can make two variables equal, but they don't have to stay that way! verbatim int a = 5; int b = a; // a and b are now equal a = 3; // a and b are no longer equal verbatim 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. Iteration iteration 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 statement!while while statement Using a while statement, we can rewrite countdown: verbatim public static void countdown (int n) while (n > 0) System.out.println (n); n = n-1; System.out.println ("Blastoff!"); verbatim 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: enumerate Evaluate the condition in parentheses, yielding true or false. If the condition is false, exit the while statement and continue execution at the next statement. If the condition is true, execute each of the statements between the squiggly-brackets, and then go back to step 1. enumerate 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. loop loop!body loop!infinite body!loop infinite 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: verbatim public static void sequence (int n) while (n != 1) System.out.println (n); if (n n = n / 2; else // n is odd n = n*3 + 1; verbatim 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 . 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 table logarithm 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. division!floating-point 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: verbatim double x = 1.0; while (x < 10.0) System.out.println (x + " " + Math.log(x)); x = x + 1.0; verbatim The output of this program is verbatim 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 verbatim 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: equation _2 x = log_e x / log_e 2 equation Changing the print statement to verbatim System.out.println (x + " " + Math.log(x) / Math.log(2.0)); verbatim yields verbatim 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 verbatim 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: verbatim double x = 1.0; while (x < 100.0) System.out.println (x + " " + Math.log(x) / Math.log(2.0)); x = x * 2.0; verbatim 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: verbatim 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 verbatim 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's ). Two-dimensional tables table!two-dimensional 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. verbatim int i = 1; while (i <= 6) System.out.print (2*i + " "); i = i + 1; System.out.println (""); verbatim The first line initializes a variable named i, which is going to act as a counter, or loop variable. 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. loop variable variable!loop 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: verbatim 2 4 6 8 10 12 verbatim So far, so good. The next step is to encapsulate and generalize. Encapsulation and generalization encapsulation 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. encapsulation generalization Here's a method that encapsulates the loop from the previous section and generalizes it to print multiples of n. verbatim public static void printMultiples (int n) int i = 1; while (i <= 6) System.out.print (n*i + " "); i = i + 1; System.out.println (""); verbatim 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: verbatim 3 6 9 12 15 18 verbatim and with argument 4, the output is verbatim 4 8 12 16 20 24 verbatim 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. verbatim int i = 1; while (i <= 6) printMultiples (i); i = i + 1; verbatim 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 verbatim 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 verbatim 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'm not going to get into that here. Methods method 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: itemize 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. itemize More encapsulation encapsulation To demonstrate encapsulation again, I'll take the code from the previous section and wrap it up in a method: verbatim public static void printMultTable () int i = 1; while (i <= 6) printMultiples (i); i = i + 1; verbatim 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 don't 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. local variable variable!local 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. loop variable variable!loop More generalization 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: verbatim public static void printMultTable (int high) int i = 1; while (i <= high) printMultiples (i); i = i + 1; verbatim I replaced the value 6 with the parameter high. If I invoke printMultTable with the argument 7, I get verbatim 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 verbatim 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): verbatim public static void printMultiples (int n, int high) int i = 1; while (i <= high) System.out.print (n*i + " "); i = i + 1; newLine (); public static void printMultTable (int high) int i = 1; while (i <= high) printMultiples (i, high); i = i + 1; verbatim Notice that when I added a new parameter, I had to change the first line of the method (the interface or prototype), and I also had to change the place where the method is invoked in printMultTable. As expected, this program generates a square 7x7 table: verbatim 1 2 3 4 5 6 7 2 4 6 8 10 12 14 3 6 9 12 15 18 21 4 8 12 16 20 24 28 5 10 15 20 25 30 35 6 12 18 24 30 36 42 7 14 21 28 35 42 49 verbatim When you generalize a method appropriately, you often find that the resulting program has capabilities you did not intend. For example, you might notice that the multiplication table is symmetric, because , so all the entries in the table appear twice. You could save ink by printing only half the table. To do that, you only have to change one line of printMultTable. Change verbatim printMultiples (i, high); verbatim to verbatim printMultiples (i, i); verbatim and you get verbatim 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 verbatim I'll leave it up to you to figure out how it works. Glossary description [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. loop infinite loop loop!infinite iteration encapsulation generalization local variable variable!local program development description Strings and things strings Invoking methods on objects method!string String method method!object object method class!Graphics class!String 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 verbatim g.drawOval (0, 0, width, height); verbatim In this case drawOval is the method being invoked on the object named g. At the time I didn't provide a definition of object, and I still can't 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?'' documentation Sun 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 verbatim http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html verbatim 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 type!char charAt chars work just like the other types we have seen: verbatim char fred = 'c'; if (fred == 'c') System.out.println (fred); verbatim 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. quote double-quote value!char Here's how the charAt method is used: verbatim String fruit = "banana"; char letter = fruit.charAt(1); System.out.println (letter); verbatim 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: verbatim a verbatim 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 zereoth letter of a string, you have to pass zero as an argument: verbatim char letter = fruit.charAt(0); verbatim Length String!length length!String The second String method we'll look at is length, which returns the number of characters in the string. For example: verbatim int length = fruit.length(); verbatim 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 verbatim int length = fruit.length(); char last = fruit.charAt (length); // WRONG!! verbatim 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. verbatim int length = fruit.length(); char last = fruit.charAt (length-1); verbatim Traversal traverse 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: verbatim int index = 0; while (index < fruit.length()) char letter = fruit.charAt (index); System.out.println (letter); index = index + 1; verbatim 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. loop variable variable!loop index 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 error!run-time run-time error exception!StringIndexOutOfBounds Way back in Section run-time I talked about run-time errors, which are errors that don't appear until a program has started running. In Java run-time errors are called exceptions. So far, you probably haven't seen many run-time errors, because we haven't 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 documentation If you go to verbatim http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html verbatim and click on charAt, you get the following documentation (or something like it): verbatim 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 indexOf 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. verbatim String fruit = "banana"; int index = fruit.indexOf('a'); verbatim 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 verbatim int index = fruit.indexOf('a', 2); verbatim 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, verbatim int index = fruit.indexOf('a', 5); verbatim returns 5. Based on the documentation, it is a little tricky to figure out what happens if the starting index is out of range: quote 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. quote One way to figure out what this means is to try out a couple of cases. Here are the results of my experiments: itemize 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. itemize 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 loopcount traverse!counting loop!counting The following program counts the number of times the letter 'a' appears in a string: verbatim String fruit = "banana"; int length = fruit.length(); int count = 0; int index = 0; while (index < length) if (fruit.charAt(index) == 'a') count = count + 1; index = index + 1; System.out.println (count); verbatim 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. counter increment decrement 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. encapsulation generalization 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 operator!increment operator!decrement 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: verbatim System.out.println (i++); verbatim 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'm 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: verbatim int index = 0; while (index < length) if (fruit.charAt(index) == 'a') count++; index++; verbatim It is a common error to write something like verbatim index = index++; // WRONG!! verbatim 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 shouldn't mix them. Character arithmetic char type!char operator!char arithmetic!char 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 verbatim char letter = '3'; int x = (int) letter; System.out.println (x); verbatim 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': verbatim int x = (int)(letter - '0'); verbatim 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'm 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: verbatim int x = Character.digit (letter, 10); verbatim 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: Jack, Kack, Lack, Mack, Nack, Ouack, Pack and Quack. Here is a loop that prints these names in order: verbatim char letter = 'J'; while (letter <= 'Q') System.out.println (letter + "ack"); letter++; verbatim Notice that in addition to the arithmetic operators, we can also use the conditional operators on characters. The output of this program is: verbatim Jack Kack Lack Mack Nack Oack Pack Qack verbatim Of course, that's not quite right because I've misspelled ``Ouack'' and ``Quack.'' As an exercise, modify the program to correct this error. Typecasting for experts typecasting Here's 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 immutable class!String immutable String toUpperCase toLowerCase 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: verbatim String name = "Alan Turing"; String upperName = name.toUpperCase (); verbatim After the second line is executed, upperName contains the value "ALAN TURING", but name still contains "Alan Turing". Turing, Alan Lovelace, Ada Strings are incomparable incomparable class!String comparison!String String equals compareTo 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 can't. In order to compare Strings, we have to use the equals and compareTo methods. For example: verbatim String name1 = "Alan Turing"; String name2 = "Ada Lovelace"; if (name1.equals (name2)) System.out.println ("The names are the same."); int flag = name1.compareTo (name2); if (flag == 0) System.out.println ("The names are the same."); else if (flag < 0) System.out.println ("name1 comes before name2."); else if (flag > 0) System.out.println ("name2 comes before name1."); verbatim 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, don't do it. Glossary description [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. object index traverse counter increment decrement exception run-time error description Interesting objects objects object What's interesting? String type!String Although Strings are objects, they are not very interesting objects, because itemize They are immutable. They have no instance variables. You don't have to use the new command to create one. itemize In this chapter, we are going to use two new object types that are part of the Java language, Point and Rectangle. Right from the start, I want to make it clear that these points and rectangles are not graphical objects that appear on the screen. They are variables that contain data, just like ints and doubles. Like other variables, they are 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 package AWT Abstract Window Toolkitsee AWT import statement!import 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 haven't required an import statement. All import statements appear at the beginning of the program, outside the class definition. Point objects Point class!Point 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. new statement!new In Java, a point is represented by a Point object. To create a new point, you have to use the new command: verbatim Point blank; blank = new Point (3, 4); verbatim 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, . declaration statement!declaration reference state diagram state 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 reference to the newly-created object. There is a standard way to diagram this assignment, shown in the figure. figure=figs/reference.eps As usual, the name of the variable blank appears outside the box and its value appears inside the box. In this case, that value is a reference, which is shown graphically with a dot and an arrow. The arrow points to the object we're referring to. The big box shows the newly-created object with the two values in it. The names x and y are the names of the instance variables. 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 variable!instance instance variable 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's 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. dot notation 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.'' verbatim int x = blank.x; verbatim 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. verbatim System.out.println (blank.x + ", " + blank.y); int distance = blank.x * blank.x + blank.y * blank.y; verbatim The first line prints 3, 4; the second line calculates the value 25. Objects as parameters parameter object!as parameter You can pass objects as parameters in the usual way. For example verbatim public static void printPoint (Point p) System.out.println ("(" + p.x + ", " + p.y + ")"); verbatim 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 verbatim java.awt.Point[x=3,y=4] verbatim 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. verbatim public static double distance (Point p1, Point p2) double dx = (double)(p2.x - p1.x); double dy = (double)(p2.y - p1.y); return Math.sqrt (dx*dx + dy*dy); verbatim The typecasts are not really necessary; I just added them as a reminder that the instance variables in a Point are integers. Rectangles Rectangle class!Rectangle 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. verbatim Rectangle box = new Rectangle (0, 0, 100, 200); verbatim creates a new Rectangle object and makes box refer to it. The figure shows the effect of this assignment. figure=figs/rectangle.eps If you print box, you get verbatim java.awt.Rectangle[x=0,y=0,width=100,height=200] verbatim Again, this is the result of a built-in Java method that knows how to print Rectangle objects. Objects as return types object!as return type return statement!return 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: verbatim public static Point findCenter (Rectangle box) int x = box.x + box.width/2; int y = box.y + box.height/2; return new Point (x, y); verbatim Notice that you can use new to create a new object, and then immediately use the result as a return value. Objects are mutable object!mutable 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: verbatim box.x = box.x + 50; box.y = box.y + 100; verbatim The result is shown in the figure: figure=figs/rectangle2.eps encapsulation generalization We could take this code and encapsulate it in a method, and generalize it to move the rectangle by any amount: verbatim public static void moveRect (Rectangle box, int dx, int dy) box.x = box.x + dx; box.y = box.y + dy; verbatim 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. verbatim Rectangle box = new Rectangle (0, 0, 100, 200); moveRect (box, 50, 100); System.out.println (box); verbatim 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. verbatim box.translate (50, 100); verbatim 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: verbatim Rectangle box1 = new Rectangle (0, 0, 100, 200); Rectangle box2 = box1; verbatim generates a state diagram that looks like this: figure=figs/aliasing.eps 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's called aliasing. Same thing with objects. When two variables are aliased, any changes that affect one variable also affect the other. For example: verbatim System.out.println (box2.width); box1.grow (50, 50); System.out.println (box2.width); verbatim 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). The effect is shown in the figure: figure=figs/aliasing2.eps 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 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 verbatim Point blank = null; verbatim and is shown in the following state diagram: figure=figs/reference2.eps The value null is represented by a dot with no arrow. exception!NullPointer run-time error 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. verbatim Point blank = null; int x = blank.x; // NullPointerException blank.translate (50, 50); // NullPointerException verbatim 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 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: verbatim Point blank = new Point (3, 4); blank = null; verbatim 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). figure=figs/reference3.eps 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 don't have to do anything to make garbage collection work, and in general you will not be aware of it. Objects and primitives type!object type!primitive object type primitive type 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: itemize 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 don't 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. itemize 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 description [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. package AWT instance instance variable reference aliasing garbage collection state state diagram description Create your own objects Class definitions and object types classes type!object type!user-defined object type class definition user-defined type 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: itemize Defining a new class also creates a new object type with the same name. A class definition is like a template for objects: it determines what instance variables the objects have and what methods can operate on them. Every object belongs to some object type; hence, it is an instance of some class. When you invoke the new command to create an object, Java invokes a special method called a constructor to initialize the instance variables. You provide one or more constructors as part of the class definition. Typically all the methods that operate on a type go in the class definition for that type. itemize Here are some syntax issues about class definitions: itemize Class names (and hence object types) always begin with a capital letter, which helps distinguish them from primitive types and variable names. You usually put one class definition in each file, and the name 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. In any program, one class is designated as the startup 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. itemize With those issues out of the way, let's look at an example of a user-defined type, Time. Time class!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 variable variable!instance Instance variables are declared at the beginning of the class definition, outside of any method definition, like this: verbatim class Time int hour, minute; double second; verbatim All by itself, this code fragment is a legal class definition. The state diagram for a Time object would look like this: figure=figs/time.eps After declaring the instance variables, the next step is usually to define a constructor for the new class. Constructors constructor method!constructor static 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: itemize The name of the constructor is the same as the name of the class. Constructors have no return type and no return value. The keyword static is omitted. itemize Here is an example for the Time class: verbatim public Time () this.hour = 0; this.minute = 0; this.second = 0.0; verbatim 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. this 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 overloading 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: verbatim public Time (int hour, int minute, double second) this.hour = hour; this.minute = minute; this.second = second; verbatim 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 new statement!new 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: verbatim 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); verbatim 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 printobject print statement!print object!printing The output of this program is: verbatim Time@80cc7c0 Time@80cc807 verbatim 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: verbatim public static void printTime (Time t) System.out.println (t.hour + ":" + t.minute + ":" + t.second); verbatim 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. Date class!Date Operations on objects objectops object operator!object 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: description [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. description Pure functions pure function function method!pure function 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: verbatim 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; verbatim 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: verbatim 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; verbatim 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. verbatim Time currentTime = new Time (9, 14, 30.0); Time breadTime = new Time (3, 35, 0.0); Time doneTime = addTime (currentTime, breadTime); printTime (doneTime); verbatim 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. verbatim 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; verbatim 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. increment decrement operator!increment operator!decrement 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 modifier method!modifier 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: verbatim 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; verbatim 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: verbatim 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; verbatim This solution is correct, but not very efficient. Can you think of a solution that does not require iteration? Fill-in methods fill-in method method!fill-in 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: verbatim 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; verbatim 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? programming style 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 incremental development prototyping program development!incremental program development!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. arithmetic!floating-point 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: verbatim public static double convertToSeconds (Time t) int minutes = t.hour * 60 + t.minute; double seconds = minutes * 60 + t.second; return seconds; verbatim 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: verbatim 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; verbatim 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: verbatim public static Time addTime (Time t1, Time t2) double seconds = convertToSeconds (t1) + convertToSeconds (t2); return new Time (seconds); verbatim 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 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 algorithm algorithm 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 description [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. class instance constructor project startup class function functional programming modifier algorithm description 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= 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 and the others) don't work for object types. For Strings there is a built-in compareTo method. For Cards we have to write our own, which we will call compareCard. Later, we will use this method to sort a deck of cards. ordering complete ordering partial ordering Some sets are completely ordered, which means that you can compare any two elements and tell which is bigger. For example, the integers and the floating-point numbers are totally ordered. Some sets are unordered, which means that there is no meaningful way to say that one element is bigger than another. For example, the fruits are unordered, which is why we cannot compare apples and oranges. In Java, the boolean type is unordered; we cannot say that true is greater than false. The set of playing cards is partially ordered, which means that sometimes we can compare cards and sometimes not. For example, I know that the 3 of Clubs is higher than the 2 of Clubs, and the 3 of Diamonds is higher than the 3 of Clubs. But which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit. comparable In order to make cards comparable, we have to decide which is more important, rank or suit. To be honest, the choice is completely arbitrary. For the sake of choosing, I will say that suit is more important, because when you buy a new deck of cards, it comes sorted with all the Clubs together, followed by all the Diamonds, and so on. With that decided, we can write compareCard. It will take two Cards as parameters and return 1 if the first card wins, -1 if the second card wins, and 0 if they tie (indicating deep equality). It is sometimes confusing to keep those return values straight, but they are pretty standard for comparison methods. First we compare the suits: verbatim if (c1.suit > c2.suit) return 1; if (c1.suit < c2.suit) return -1; verbatim If neither statement is true, then the suits must be equal, and we have to compare ranks: verbatim if (c1.rank > c2.rank) return 1; if (c1.rank < c2.rank) return -1; verbatim If neither of these is true, the ranks must be equal, so we return 0. In this ordering, aces will appear lower than deuces (2s). As an exercise, fix it so that aces are ranked higher than Kings, and encapsulate this code in a method. Arrays of cards array!of object object!array of deck The reason I chose Cards as the objects for this chapter is that there is an obvious use for an array of cards---a deck. Here is some code that creates a new deck of 52 cards: verbatim Card[] deck = new Card [52]; verbatim Here is the state diagram for this object: state diagram figure=figs/cardarray.eps The important thing to see here is that the array contains only references to objects; it does not contain any Card objects. The values of the array elements are initialized to null. You can access the elements of the array in the usual way: verbatim if (deck[3] == null) System.out.println ("No cards yet!"); verbatim But if you try to access the instance variables of the non-existent Cards, you will get a NullPointerException. exception!NullPointer run-time error null verbatim deck[2].rank; // NullPointerException verbatim Nevertheless, that is the correct syntax for accessing the rank of the ``twoeth'' card in the deck (really the third---we started at zero, remember?). This is another example of composition, the combination of the syntax for accessing an element of an array and an instance variable of an object. composition loop!nested The easiest way to populate the deck with Card objects is to write a nested loop: verbatim int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) deck[index] = new Card (suit, rank); index++; verbatim The outer loop enumerates the suits, from 0 to 3. For each suit, the inner loop enumerates the ranks, from 1 to 13. Since the outer loop iterates 4 times, and the inner loop iterates 13 times, the total number of times the body is executed is 52 (13 times 4). index I used the variable index to keep track of where in the deck the next card should go. The following state diagram shows what the deck looks like after the first two cards have been allocated: figure=figs/cardarray2.eps As an exercise, encapsulate this deck-building code in a method called buildDeck that takes no parameters and that returns a fully-populated array of Cards. encapsulation The printDeck method printdeck printDeck print!array of Cards Whenever you are working with arrays, it is convenient to have a method that will print the contents of the array. We have seen the pattern for traversing an array several times, so the following method should be familiar: verbatim public static void printDeck (Card[] deck) for (int i=0; i 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim Rather than call compareCard three times, I called it once and stored the result. Although this code contains the kernel of a bisection search, it is still missing a piece. As it is currently written, if the card is not in the deck, it will recurse forever. We need a way to detect this condition and deal with it properly (by returning -1). recursion The easiest way to tell that your card is not in the deck is if there are no cards in the deck, which is the case if high is less than low. Well, there are still cards in the deck, of course, but what I mean is that there are no cards in the segment of the deck indicated by low and high. With that line added, the method works correctly: verbatim public static int findBisect (Card[] deck, Card card, int low, int high) System.out.println (low + ", " + high); if (high < low) return -1; int mid = (high + low) / 2; int comp = deck[mid].compareCard (card); if (comp == 0) return mid; else if (comp > 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim I added a print statement at the beginning so I could watch the sequence of recursive calls and convince myself that it would eventually reach the base case. I tried out the following code: verbatim Card card1 = new Card (1, 11); System.out.println (findBisect (deck, card1, 0, 51)); verbatim And got the following output: verbatim 0, 51 0, 24 13, 24 19, 24 22, 24 23 verbatim Then I made up a card that is not in the deck (the 15 of Diamonds), and tried to find it. I got the following: verbatim 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 -1 verbatim These tests don't prove that this program is correct. In fact, no amount of testing can prove that a program is correct. On the other hand, by looking at a few cases and examining the code, you might be able to convince yourself. testing correctness The number of recursive calls is fairly small, typically 6 or 7. That means we only had to invoke compareCard 6 or 7 times, compared to up to 52 times if we did a linear search. In general, bisection is much faster than a linear search, especially for large arrays. Two common errors in recusive programs are forgetting to include a base case and writing the recursive call so that the base case is never reached. Either error will cause an infinite recursion, in which case Java will (eventually) throw a StackOverflowException. recursion!infinite infinite recursion exception!StackOverflow Decks and subdecks deck subdeck Looking at the interface to findBisect verbatim public static int findBisect (Card[] deck, Card card, int low, int high) verbatim it might make sense to treat three of the parameters, deck, low and high, as a single parameter that specifies a subdeck. We took a similar view in Section graphics when we were talking about bounding boxes. In that case I referred to x, y, width and height as if they were a single parameter, a bounding box. parameter!abstract abstract parameter This kind of thing is quite common, and I sometimes think of it as an abstract parameter. What I mean by ``abstract,'' is something that is not literally part of the program text, but which describes the function of the program at a higher level. For example, when you invoke a method and pass an array and the bounds low and high, there is nothing that prevents the invoked method from accessing parts of the array that are out of bounds. So you are not literally sending a subset of the deck; you are really sending the whole deck. But as long as the recipient plays by the rules, it makes sense to think of it, abstractly, as a subdeck. There is one other example of this kind of abstraction that you might have noticed in Section objectops, when I referred to an ``empty'' data structure. The reason I put ``empty'' in quotation marks was to suggest that it is not literally accurate. All variables have values all the time. When you create them, they are given default values. So there is no such thing as an empty object. But if the program guarantees that the current value of a variable is never read before it is written, then the current value is irrelevant. Abstractly, it makes sense to think of such a variable as ``empty.'' This kind of thinking, in which a program comes to take on meaning beyond what is literally encoded, is a very important part of thinking like a computer scientist. Sometimes, the word ``abstract'' gets used so often and in so many contexts that it comes to lose its meaning. Nevertheless, abstraction is a central idea in computer science (as well as many other fields). abstraction A more general definition of ``abstraction'' is ``The process of modeling a complex system with a simplified description in order to suppress unnecessary details while capturing relevant behavior.'' Glossary description [encode:] To represent one set of values using another set of values, by constructing a mapping between them. [shallow equality:] Equality of references. Two references that point to the same object. [deep equality:] Equality of values. Two references that point to objects that have the same value. [abstract parameter:] A set of parameters that act together as a single parameter. [abstraction:] The process of interpreting a program (or anything else) at a higher level than what is literally represented by the code. encode shallow equality deep equality abstract parameter abstraction description Objects of Arrays deck deck array!of Cards In the previous chapter, we worked with an array of objects, but I also mentioned that it is possible to have an object that contains an array as an instance variable. In this chapter I am going to create a new object, called a Deck, that contains an array of Cards as an instance variable. instance variable variable!instance The class definition looks like this verbatim class Deck Card[] cards; public Deck (int n) cards = new Card[n]; verbatim The name of the instance variable is cards to help distinguish the Deck object from the array of Cards that it contains. Here is a state diagram showing what a Deck object looks like with no cards allocated: state diagram constructor figure=figs/deckobject.eps As usual, the constructor initializes the instance variable, but in this case it uses the new command to create the array of cards. It doesn't create any cards to go in it, though. For that we could write another constructor that creates a standard 52-card deck and populates it with Card objects: verbatim public Deck () cards = new Card[52]; int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) cards[index] = new Card (suit, rank); index++; verbatim Notice how similar this method is to buildDeck, except that we had to change the syntax to make it a constructor. To invoke it, we use the new command: new statement!new verbatim Deck deck = new Deck (); verbatim Now that we have a Deck class, it makes sense to put all the methods that pertain to Decks in the Deck class definition. Looking at the methods we have written so far, one obvious candidate is printDeck (Section printdeck). Here's how it looks, rewritten to work with a Deck object: printDeck verbatim public static void printDeck (Deck deck) for (int i=0; i 0) maxIndex = i; Comparable result = array[maxIndex]; // move the last item into the empty slot index--; array[maxIndex] = array[index]; return result; verbatim As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the ``largest'' is determined by compareTo. In this case the compareTo method is provided by the Integer class, and it does what we expect---larger (more positive) numbers win. A Priority Queue client client abstract class class!abstract The implementation of Priority Queue is written entirely in terms of Comparable objects, but there is no such thing as a Comparable object! Go ahead, try to create one: verbatim Comparable comp = new Comparable (); // ERROR verbatim You'll get a compile-time message that says something like ``java.lang.Comparable is an interface. It can't be instantiated.'' In Java, abstract classes are called interfaces. I have avoided this word so far because it also means several other things, but now you have to know. interface Why can't abstract classes be instantiated? Because an abstract class only specifies requirements (you must have a compareTo method); it does not provide an implementation. To create a Comparable object, you have to create one of the objects that belongs to the Comparable set, like Integer. Then you can use that object anywhere a Comparable is called for. verbatim PriorityQueue pq = new PriorityQueue (); Integer item = new Integer (17); pq.insert (item); verbatim This code creates a new, empty Priority Queue and a new Integer object. Then it inserts the Integer into the queue. insert is expecting a Comparable as a parameter, so it is perfectly happy to take an Integer. If we try to pass a Rectangle, which does not belong to Comparable, we get a compile-time message like, ``Incompatible type for method. Explicit cast needed to convert java.awt.Rectangle to java.lang.Comparable.'' That's the compiler telling us that if we want to make that conversion, we have to do it explicitly. We might try to do what it says: verbatim Rectangle rect = new Rectangle (); pq.insert ((Comparable) rect); verbatim But in that case we get a run-time error, a ClassCastException. When the Rectangle tries to pass as a Comparable, the run-time system checks whether it satisfies the requirements, and rejects it. So that's what we get for following the compiler's advise. ClassCastException exception!ClassCastException To get items out of the queue, we have to reverse the process: verbatim while (!pq.empty ()) item = (Integer) pq.remove (); System.out.println (item); verbatim This loop removes all the items from the queue and prints them. It assumes that the items in the queue are Integers. If they were not, we would get a ClassCastException. The Golfer class Golfer class!Golfer abstract class!implementing Comparable Finally, let's look at how we can make a new class that belongs to Comparable. As an example of something with an unusual definition of ``highest'' priority, we'll use golfers: verbatim public class Golfer implements Comparable String name; int score; public Golfer (String name, int score) this.name = name; this.score = score; verbatim The class definition and the constructor are pretty much the same as always; the difference is that we have to declare that Golfer implements Comparable. In this case the keyword implements means that Golfer implements the interface specified by Comparable. If we try to compile Golfer.java at this point, we get something like ``class Golfer must be declared abstract. It does not define int compareTo(java.lang.Object) from interface java.lang.Comparable.'' In other words, to be a Comparable, Golfer has to provide a method named compareTo. So let's write one: verbatim public int compareTo (Object obj) Golfer that = (Golfer) obj; int a = this.score; int b = that.score; // for golfers, low is good! if (ab) return -1; return 0; verbatim Two things here are a little surprising. First, the parameter is an Object. That's because in general the caller doesn't know what type the objects are that are being compared. For example, in PriorityQueue.java when we invoke compareTo, we pass a Comparable as a parameter. We don't have to know whether it is an Integer or a Golfer or whatever. Inside compareTo we have to convert the parameter from an Object to a Golfer. As usual, there is a risk when we do this kind of cast: if we cast to the wrong type we get an exception. Finally, we can create some golfers: verbatim Golfer tiger = new Golfer ("Tiger Woods", 61); Golfer phil = new Golfer ("Phil Mickelson", 72); Golfer hal = new Golfer ("Hal Sutton", 69); verbatim And put them in the queue: verbatim pq.insert (tiger); pq.insert (phil); pq.insert (hal); verbatim When we pull them out: verbatim while (!pq.empty ()) golfer = (Golfer) pq.remove (); System.out.println (golfer); verbatim They appear in descending order (for golfers): verbatim Tiger Woods 61 Hal Sutton 69 Phil Mickelson 72 verbatim When we switched from Integers to Golfers, we didn't have to make any changes in PriorityQueue.java at all. So we succeeded in maintaining a barrier between PriorityQueue and the classes that use it, allowing us to reuse the code without modification. Furthermore, we were able to give the client code control over the definition of compareTo, making this implementation of PriorityQueue more versatile. Glossary queue queueing discipline FIFO priority queue veneer constant time linear time performance hazard linked queue circular buffer abstract class interface description [queue:] An ordered set of objects waiting for a service of some kind. [queueing discipline:] The rules that determine which member of a queue is removed next. [FIFO:] ``first in, first out,'' a queueing discipline in which the first member to arrive is the first to be removed. [priority queue:] A queueing discipline in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed. [Priority Queue:] An ADT that defines the operations one might perform on a priority queue. [veneer:] A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client. [performance hazard:] A danger associated with a veneer that some of the methods might be implemented inefficiently in a way that is not apparent to the client. [constant time:] An operation whose run time does not depend on the size of the data structure. [linear time:] An operation whose run time is a linear function of the size of the data structure. [linked queue:] An implementation of a queue using a linked list and references to the first and last nodes. [circular buffer:] An implementation of a queue using an array and indices of the first element and the next available space. [abstract class:] A set of classes. The abstract class specification lists the requirements a class must satisfy to be included in the set. [interface:] The Java word for an abstract class. Not to be confused with the more broad meaning of the word interface. description Trees tree ADT data structure This chapter presents a new data structure called a tree, some of its uses and two ways to implement it. A possible source of confusion is the distinction between an ADT, a data structure, and an implementation of an ADT or data structure. There is no universal answer, because something that is an ADT at one level might in turn be the implementation of another ADT. diagram!implementation To help keep some of this straight, it is sometimes useful to draw a diagram showing the relationship between an ADT and its possible implementations. This figure shows that there are two implementations of a tree: figure=figs/tree_adt.eps The horizontal line in the figure represents the barrier of abstraction between the ADT and its implementations. A tree node node tree node cargo embedded reference implementation!Tree binary tree Like lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes (possibly null). The class definition looks like this: verbatim public class Tree Object cargo; Tree left, right; verbatim Like list nodes, tree nodes contain cargo: in this case a generic Object. The other instance variables are named left and right, in accordance with a standard way to represent trees graphically: figure=figs/tree1.eps The top of the tree (the node referred to by tree) is called the root. In keeping with the tree metaphor, the other nodes are called branches and the nodes at the tips with null references are called leaves. It may seem odd that we draw the picture with the root at the top and the leaves at the bottom, but that is not the strangest thing. root node leaf node parent node child node level To make things worse, computer scientists mix in yet another metaphor: the family tree. The top node is sometimes called a parent and the nodes it refers to are its children. Nodes with the same parent are called siblings, and so on. Finally, there is also a geometric vocabulary for taking about trees. I already mentioned left and right, but there is also ``up'' (toward the parent/root) and down (toward the children/leaves). Also, all the nodes that are the same distance from the root comprise a level of the tree. I don't know why we need three metaphors for talking about trees, but there it is. Building trees tree!linked implementation The process of assembling tree nodes is similar to the process of assembling lists. We have a constructor for tree nodes that initializes the instance variables. verbatim public Tree (Object cargo, Tree left, Tree right) this.cargo = cargo; this.left = left; this.right = right; verbatim We allocate the child nodes first: verbatim Tree left = new Tree (new Integer(2), null, null); Tree right = new Tree (new Integer(3), null, null); verbatim We can create the parent node and link it to the children at the same time: verbatim Tree tree = new Tree (new Integer(1), left, right); verbatim This code produces the state shown in the previous figure. Traversing trees tree!traversal traverse The most natural way to traverse a tree is recursively. For example, to add up all the integers in a tree, we could write this class method: verbatim public static int total (Tree tree) if (tree == null) return 0; Integer cargo = (Integer) tree.cargo; return cargo.intValue() + total (tree.left) + total (tree.right); verbatim This is a class method because we would like to use null to represent the empty tree, and make the empty tree the base case of the recursion. If the tree is empty, the method returns 0. Otherwise it makes two recursive calls to find the total value of its two children. Finally, it adds in its own cargo and returns the total. tree!empty Although this method works, there is some difficulty fitting it into an object-oriented design. It should not appear in the Tree class because it requires the cargo to be Integer objects. If we make that assumption in Tree.java then we lose the advantages of a generic data structure. On the other hand, this code accesses the instance variables of the Tree nodes, so it ``knows'' more than it should about the implementation of the tree. If we changed that implementation later (and we will) this code would break. Later in this chapter we will develop ways to solve this problem, allowing client code to traverse trees containing any kinds of objects without breaking the abstraction barrier between the client code and the implementation. Before we get there, let's look at an application of trees. Expression trees tree!expression expression tree postfix infix A tree is a natural way to represent the structure of an expression. Unlike other notations, it can represent the comptation unambiguously. For example, the infix expression 1 + 2 * 3 is ambiguous unless we know that the multiplication happens before the addition. The following figure represents the same computation: figure=figs/tree2.eps The nodes can be operands like 1 and 2 or operators like + and *. Operands are leaf nodes; operator nodes contain references to their operands (all of these operators are binary, meaning they have exactly two operands). Looking at this figure, there is no question what the order of operations is: the multiplication happens first in order to compute the first operand of the addition. Expression trees like this have many uses. The example we are going to look at is translation from one format (postfix) to another (infix). Similar trees are used inside compilers to parse, optimize and translate programs. Traversal tree!traversal traverse recursion preorder postorder inorder I already pointed out that recursion provides a natural way to traverse a tree. We can print the contents of an expression tree like this: verbatim public static void print (Tree tree) if (tree == null) return; System.out.print (tree + " "); print (tree.left); print (tree.right); verbatim In other words, to print a tree, first print the contents of the root, then print the entire left subtree, then print the entire right subtree. This way of traversing a tree is called a preorder, because the contents of the root appear before the contents of the children. For the example expression the output is + 1 * 2 3. This is different from both postfix and infix; it is a new notation called prefix, in which the operators appear before their operands. You might suspect that if we traverse the tree in a different order we get the expression in a different notation. For example, if we print the subtrees first, and then the root node: verbatim public static void printPostorder (Tree tree) if (tree == null) return; printPostorder (tree.left); printPostorder (tree.right); System.out.print (tree + " "); verbatim We get the expression in postfix (1 2 3 * +)! As the name of the previous method implies, this order of traversal is called postorder. Finally, to traverse a tree inorder, we print the left tree, then the root, then the right tree: verbatim public static void printInorder (Tree tree) if (tree == null) return; printInorder (tree.left); System.out.print (tree + " "); printInorder (tree.right); verbatim The result is 1 + 2 * 3, which is the expression in infix. To be fair, I have to point out that I omitted an important complication. Sometimes when we write an expression in infix we have to use parentheses to preserve the order of operations. So an inorder traversal is not quite sufficient to generate an infix expression. Nevertheless, with a few improvements, the expression tree and the three recursive traversals provide a general way to translate expressions from one format to another. Encapsulation encapsulation client provider abstract class class!abstract As I mentioned before, there is a problem with the way we have been traversing trees: it breaks down the barrier between the client code (the application that uses the tree) and the provider code (the Tree implementation). Ideally, tree code should be general; it shouldn't know anything about expression trees. And the code that generates and traverses the expression tree shouldn't know about the implementation of the trees. This design criterion is called object encapsulation to distinguish it from the encapsulation we saw in Section encapsulation, which we might call method encapsulation. In the current version, the Tree code knows too much about the client. Instead, the Tree class should provide the general capability of traversing a tree in various ways. As it traverses, it should perform operations on each node that are specified by the client. Visitable abstract class!Visitable To facilitate this separation of interests, we will create a new abstract class, called Visitable. The items stored in a tree will be required to be visitable, which means that they define a method named visit that does whatever the client wants done to each node. That way the Tree can perform the traversal and the client can perform the node operations. Here are the steps we have to perform to wedge an abstract class between a client and a provider: enumerate Define an abstract class that specifies the methods the provider code will need to invoke on its components. Write the provider code in terms of the new abstract class, as opposed to generic Objects. Define a concrete class that belongs to the abstract class and that implements the required methods as appropriate for the client. Write the client code to use the new concrete class. enumerate The next few sections demonstrate these steps. Defining an abstract class abstract class!defining interface An abstract class definition looks a lot like a concrete class definition, except that it only specifies the interface of each method and not an implementation. The definition of Visitable is verbatim public interface Visitable public void visit (); verbatim That's it! The word interface is Java's keyword for an abstract class. The definition of visit looks like any other method definition, except that it has no body. This definition specifies that any class that implements Visitable has to have a method named visit that takes no parameters and that returns void. body!method Like other class definitions, abstract class definitions go in a file with the same name as the class (in this case Visitable.java). Implementing an abstract class abstract class!implementing Token class class!Token If we are using an expression tree to generate infix, then ``visiting'' a node means printing its contents. Since the contents of an expression tree are tokens, we'll create a new concrete class called Token that implements Visitable verbatim public class Token implements Visitable String str; public Token (String str) this.str = str; public void visit () System.out.print (str + " "); verbatim When we compile this class definition (which is in a file named Token.java), the compiler checks whether the methods provided satisfy the requirements specified by the abstract class. If not, it will produce an error message. For example, if we misspell the name of the method that is supposed to be visit, we might get something like, ``class Token must be declared abstract. It does not define void visit() from interface Visitable.'' The next step is to modify the parser to put Token objects into the tree instead of Strings. Here is a small example: verbatim String expr = "1 2 3 * +"; StringTokenizer st = new StringTokenizer (expr, " +-*/", true); String token = st.nextToken(); Tree tree = new Tree (new Token (token), null, null)); verbatim This code takes the first token in the string and wraps it in a Token object, then puts the Token into a tree node. If the Tree requires the cargo to be Visitable, it will convert the Token to be a Visitable object. When we remove the Visitable from the tree, we will have to cast it back into a Token. As an exercise, write a version of printPreorder called visitPreorder that traverses the tree and invokes visit on each node in preorder. Array implementation of trees tree!array implementation implementation!Tree ADT!Tree What does it mean to ``implement'' a tree? So far we have only seen one implementation of a tree, a linked data structure similar to a linked list. But there are other structures we would like to identify as trees. Anything that can perform the basic set of tree operations should be recognized as a tree. So what are the tree operations? In other words, how do we define the Tree ADT? description [constructor:] Build an empty tree. [isEmpty:] Is this tree the empty tree? [getLeft:] Return the left child of this node. [getRight:] Return the left child of this node. [getParent:] Return the parent of this node. [getCargo:] Return the cargo object from this node. [setCargo:] Assign a cargo object to this node (and create the node, if necessary). description In the implementation we have seen, the empty tree is represented by the special value null. getLeft and getRight are performed by accessing the instance variables of the node, as are getCargo and setCargo. We have not implemented getParent yet (you might think about how to do it). There is another implementation of trees that uses arrays and indices instead of objects and references. To see how it works, we will start by looking at a hybrid implementation that uses both arrays and objects. This figure shows a tree like the ones we have been looking at, although it is laid out sideways, with the root at the left and the leaves on the right. At the bottom there is an array of references that refer to the objects in the trees. The cargo objects are represented as null references. figure=figs/tree3.eps,width=5in You might notice that array index 1 refers to the root node and array index 0 is empty. The reason for that will become clear soon. So now we have a tree where each node has a unique index. Furthermore, the indices have been assigned to the nodes according to a deliberate pattern, in order to achieve the following results: enumerate The left child of the node with index has index . The right child of the node with index has index . The parent of the node with index has index (rounded down). enumerate Using these formulas, we can implement getLeft, getRight and getParent just by doing arithmetic; we don't have to use the references at all! Since we don't use the references, we can get rid of them, which means that what used to be a tree node is now just cargo and nothing else. That means we can implement the tree as an array of cargo objects; we don't need tree nodes at all. Here's what one implementation looks like: verbatim public class Tree Object[] array; int i; public Tree () array = new Object [128]; i = 1; public Tree (Object[] array, int i) this.array = array; this.i = i; verbatim No surprises so far. The instance variables are an array of Objects and an integer that indicates where in the array the new node is found. The first constructor initializes the array with an arbitrary initial size (we can always resize it later). The second constructor assumes that the array of objects already exists. All nodes that comprise a tree will share the same array and have different values of i. We use i to access the cargo of a given node: verbatim public Object getCargo () if (i >= array.length) return null; return array[i]; public void setCargo (Object obj) if (i >= array.length) array = resize (array); array[i] = obj; verbatim Both methods have to check the length of the array. If getCargo tries to access a nonexistent element of the array, it returns null to indicate an empty tree. If getCargo goes past the length of the array, it resizes the array to make room (see Section resize for a possible implementation of resize). To check whether a node is an empty tree, we check whether the cargo is null. verbatim public boolean empty () return (getCargo() == null); verbatim The implementation of getLeft, getRight and getParent is just arithmetic: verbatim public Tree getLeft () return new Tree (array, 2*i); public Tree getRight () return new Tree (array, 2*i + 1); public Tree parent () return new Tree (array, i/2); verbatim Finally we are ready to build a tree. In another class (the client), we would write verbatim Tree tree = new Tree (); tree.setCargo ("cargo for root"); verbatim The constructor builds an empty tree. Invoking setCargo puts the string "cargo for root" into the root node. To add children to the root node: verbatim tree.getLeft().setCargo ("cargo for left"); tree.getRight().setCargo ("cargo for right"); verbatim In the tree class we could provide a method that prints the contents of the tree in preorder. verbatim public void print () if (isEmpty ()) return; System.out.println (array[i]); getLeft().print(); getRight().print(); verbatim We invoke this method from the client by passing the root as a parameter. verbatim tree.print (root); verbatim The output is verbatim cargo for root cargo for left cargo for right verbatim This implementation provides the basic operations that define a tree. As I pointed out, the linked implementation of a tree provides the same operations, but the syntax is different. As an exercise, modify the linked tree so that it implements the Tree ADT. One problem with the array implementation is that the initial size of the array is arbitrary and it might have to be resized. This last problem can be solved by replacing the array with a Vector. The Vector class vector Vector class class!Vector The Vector is a built-in Java class in the java.util package. It is an implementation of an array of Objects, with the added feature that it can resize itself automatically, so we don't have to. The Vector class provides methods named get and set that are similar to the getCargo and setCargo methods we wrote for the Tree class. You should review the other Vector operations by consulting the online documentation. Before using the Vector class, you should understand a few concepts. Every Vector has a capacity, which is the amount of space that has been allocated to store values, and a size, which is the number of values that are actually in the vector. The following figure is a simple diagram of a Vector that contains three elements, but it has a capacity of seven. figure=figs/vector.eps In general, it is the responsibility of the client code to make sure that the vector has sufficient size before invoking set or get. If you try to access an element that does not exist (in this case the elements with indices 3 through 6), you will get an ArrayIndexOutOfBounds exception. exception!ArrayIndexOutOfBounds ArrayIndexOutOfBounds The Vector methods add and insert automatically increase the size of the Vector, but set does not. The resize method adds null elements to the end of the Vector to get to the given size. Most of the time the client doesn't have to worry about capacity. Whenever the size of the Vector changes, the capacity is updated automatically. For performance reasons, some applications might want to take control of this function, which is why there are additional methods for increasing and decreasing capacity. Because the client code has no access to the implementation of a vector, it is not clear how we should traverse one. Of course, one possibility is to use a loop variable as an index into the vector: verbatim for (int i=0; i 1) return false; // check the children if (!isComplete (tree.left)) return false; return isComplete (tree.right); verbatim For this example I used the linked implementation of a tree. As an exercise, write the same method for the array implementation. Also as an exercise, write the height method. The height of a null tree is 0 and the height of a leaf node is 1. recursive definition The heap property is similarly recursive. In order for a tree to be a heap, the largest value in the tree has to be at the root, and the same has to be true for each subtree. As another exercise, write a method that checks whether a tree has the heap property. Heap remove reheapify It might seem odd that we are going to remove things from the heap before we insert any, but I think removal is easier to explain. At first glance, we might think that removing an item from the heap is a constant time operation, since the item with the highest priority is always at the root. The problem is that once we remove the root node, we are left with something that is no longer a heap. Before we can return the result, we have to restore the heap property. We call this operation reheapify. The situation is shown in the following figure: figure=figs/tree5.eps,height=2in The root node has priority r and two subtrees, A and B. The value at the root of Subtree A is a and the value at the root of Subtree B is b. We assume that before we remove r from the tree, the tree is a heap. That implies that r is the largest value in the heap and that a and b are the largest values in their respective subtrees. Once we remove r, we have to make the resulting tree a heap again. In other words we need to make sure it has the properties of completeness and heapness. The best way to ensure completeness is to remove the bottom-most, right-most node, which we'll call c and put its value at the root. In a general tree implementation, we would have to traverse the tree to find this node, but in the array implementation, we can find it in constant time because it is always the last (non-null) element of the array. Of course, the chances are that the last value is not the highest, so putting it at the root breaks the heapness property. Fortunately it is easy to restore. We know that the largest value in the heap is either a or b. Therefore we can select whichever is larger and swap it with the value at the root. Arbitrarily, let's say that b is larger. Since we know it is the highest value left in the heap, we can put it at the root and put c at the top of Subtree B. Now the situation looks like this: figure=figs/tree6.eps,height=2in Again, c is the value we copied from the last entry in the array and b is the highest value left in the heap. Since we haven't changed Subtree A at all, we know that it is still a heap. The only problem is that we don't know if Subtree B is a heap, since we just stuck a (probably low) value at its root. recursion Wouldn't it be nice if we had a method that could reheapify Subtree B? Wait... we do! Heap insert Inserting a new item in a heap is a similar operation, except that instead of trickling a value down from the top, we trickle it up from the bottom. Again, to guarantee completeness, we add the new element at the bottom-most, rightmost position in the tree, which is the next available space in the array. Then to restore the heap property, we compare the new value with its neighbors. The situation looks like this: figure=figs/tree7.eps,height=2in The new value is c. We can restore the heap property of this subtree by comparing c to a. If c is smaller, then the heap property is satisfied. If c is larger, then we swap c and a. The swap satisfies the heap property because we know that c must also be bigger than b, because c > a and a > b. Now that the subtree is reheapified, we can work our way up the tree until we reach the root. Performance of heaps Heap!analysis analysis!Heap For both insert and remove, we perform a constant time operation to do the actual insertion and removal, but then we have to reheapify the tree. In one case we start at the root and work our way down, comparing items and then recursively reheapifying one of the subtrees. In the other case we start at a leaf and work our way up, again comparing elements at each level of the tree. As usual, there are several operations we might want to count, like comparisons and swaps. Either choice would work; the real issue is the number of levels of the tree we examine and how much work we do at each level. In both cases we keep examining levels of the tree until we restore the heap property, which means we might only visit one, or in the worst case we might have to visit them all. Let's consider the worst case. At each level, we perform only constant time operations like comparisons and swaps. So the total amount of work is proportional to the number of levels in the tree, a.k.a. the height. So we might say that these operations are linear with respect to the height of the tree, but the ``problem size'' we are interested in is not height, it's the number of items in the heap. As a function of , the height of the tree is . This is not true for all trees, but it is true for complete trees. To see why, think of the number of nodes on each level of the tree. The first level contains 1, the second contains 2, the third contains 4, and so on. The th level contains nodes, and the total number in all levels up to is . In other words, , which means that . logarithmic time Thus, both insertion and removal take logarithmic time. To insert and remove items takes time proportional to . Heapsort heapsort sorting analysis!heapsort The result of the previous section suggests yet another algorithm for sorting. Given items, we insert them into a Heap and then remove them. Because of the Heap semantics, they come out in order. We have already shown that this algorithm, which is called heapsort, takes time proportional to , which is better than selection sort and the same as mergesort. As the value of gets large, we expect heapsort to be faster than selection sort, but performance analysis gives us no way to know whether it will be faster than mergesort. We would say that the two algorithms have the same order of growth because they grow with the same functional form. Another way to say the same thing is that they belong to the same complexity class. big-O notation complexity class order of growth constant time linear time quadratic time logarithmic time Complexity classes are sometimes written in ``big-O notation''. For example, , pronounced ``oh of en squared'' is the set of all functions that grow no faster than for large values of . To say that an algorithm is is the same as saying that it is quadratic. The other complexity classes we have seen, in decreasing order of performance, are: 0.2in tabularll & constant time & logarithmic & linear & ``en log en'' & quadratic & exponential tabular 0.2in So far none of the algorithms we have looked at are exponential. For large values of , these algorithms quickly become impractical. Nevertheless, the phrase ``exponential growth'' appears frequently in even non-technical language. It is frequently misused so I wanted to include its technical meaning. People often use ``exponential'' to describe any curve that is increasing and accelerating (that is, one that has positive slope and curvature). Of course, there are many other curves that fit this description, including quadratic functions (and higher-order polynomials) and even functions as undramatic as . Most of these curves do not have the (often detrimental) explosive behavior of exponentials. As an exercise, compare the behavior of and as the value of increases. Glossary selection sort mergesort heapsort complexity class order of growth overhead description [selection sort:] The simple sorting algorithm in Section sorting. [mergesort:] A better sorting algorithm from Section mergesort. [heapsort:] Yet another sorting algorithm. [complexity class:] A set of algorithms whose performance (usually run time) has the same order of growth. [order of growth:] A set of functions with the same leading-order term, and therefore the same qualitative behavior for large values of . [overhead:] Additional time or resources consumed by a programming performing operations other than the abstract operations considered in performance analysis. description Table Arrays, Vectors and Tables array Vector table Arrays are a generally useful data structure, but they suffer from two important limitations: itemize The size of the array does not depend on the number of items in it. If the array is too big, it wastes space. If it is too small it might cause an error, or we might have to write code to resize it. Although the array can contain any type of item, the indices of the array have to be integers. We cannot, for example, use a String to specify an element of an array. itemize In Section vector we saw how the built-in Vector class solves the first problem. As the user adds items it expands automatically. It is also possible to shrink a Vector so that the capacity is the same as the current size. But Vectors don't help with the second problem. The indices are still integers. That's where the Table ADT comes in. The Table is a generalization of the Vector that can use any type as an index. These generalized indices are called keys. Just as you would use an index to access a value in an array, you use a key to access a value in a Table. So each key is associated with a value, which is why Tables are sometimes called associative arrays. dictionary associative array key entry index A common example of a table is a dictionary, which is a table that associates words (the keys) with their definitions (the values). Because of this example Tables are also sometimes called Dictionaries. Also, the association of a particular key with a particular value is called an entry. The Table ADT Table ADT ADT!Table Like the other ADTs we have looked at, Tables are defined by the set of operations they support: description [constructor:] Make a new, empty table. [put:] Create an entry that associates a value with a key. [get:] For a given key, find the corresponding value. [containsKey:] Return true if there is an entry in the Table with the given Key. [keys]: Return a collection that contains all the keys in the Table. description The built-in Hashtable Hashtable class!Hashtable Java provides an implementation of the Table ADT called Hashtable. It is in the java.util package. Later in the chapter we'll see why it is called Hashtable. To demonstrate the use of the Hashtable we'll write a short program that traverses a String and counts the number of times each word appears. We'll create a new class called WordCount that will build the Table and then print its contents. Naturally, each WordCount object contains a Hashtable: verbatim public class WordCount Hashtable ht; public WordCount () ht = new Hashtable (); verbatim The only public methods for WordCount are processLine, which takes a String and adds its words to the Table, and print, which prints the results at the end. processLine breaks the String into words using a StringTokenizer and passes each word to processWord. verbatim public void processLine (String s) StringTokenizer st = new StringTokenizer (s, " ,."); while (st.hasMoreTokens()) String word = st.nextToken(); processWord (word.toLowerCase ()); verbatim The interesting work is in processWord. verbatim public void processWord (String word) if (ht.containsKey (word)) Integer i = (Integer) ht.get (word); Integer j = new Integer (i.intValue() + 1); ht.put (word, j); else ht.put (word, new Integer (1)); verbatim If the word is already in the table, we get its counter, increment it, and put the new value. Otherwise, we just put a new entry in the table with the counter set to 1. Enumeration class class!Enumeration traverse To print the entries in the table, we need to be able to traverse the keys in the table. Fortunately, the Hashtable implementation provides a method, keys, that returns an Enumeration object we can use. Enumerations are very similar to the Iterators we saw in Section iterator. Both are abstract classes in the java.util package; you should review the documentation of both. Here's how to use keys to print the contents of the Hashtable: verbatim public void print () Enumeration enum = ht.keys (); while (enum.hasMoreElements ()) String key = (String) enum.nextElement (); Integer value = (Integer) ht.get (key); System.out.println (" " + key + ", " + value + " "); verbatim Each of the elements of the Enumeration is an Object, but since we know they are keys, we typecast them to be Strings. When we get the values from the Table, they are also Objects, but we know they are counters, so we typecast them to be Integers. Finally, to count the words in a string: verbatim WordCount wc = new WordCount (); wc.processLine ("da doo ron ron ron, da doo ron ron"); wc.print (); verbatim The output is verbatim ron, 5 doo, 2 da, 2 verbatim The elements of the Enumeration are not in any particular order. The only guarantee is that all the keys in the table will appear. A Vector implementation implementation!Table table!vector implementation KeyValuePair An easy way to implement the Table ADT is to use a Vector of entries, where each entry is an object that contains a key and a value. These objects are called key-value pairs. A class definition for a KeyValuePair might look like this: verbatim class KeyValuePair Object key, value; public KeyValuePair (Object key, Object value) this.key = key; this.value = value; public String toString () return " " + key + ", " + value + " "; verbatim Then the implementation of Table looks like this: verbatim public class Table Vector v; public Table () v = new Vector (); verbatim To put a new entry in the table, we just add a new KeyValuePair to the Vector: verbatim public void put (Object key, Object value) KeyValuePair pair = new KeyValuePair (key, value); v.add (pair); verbatim Then to look up a key in the Table we have to traverse the Vector and find a KeyValuePair with a matching key: verbatim public Object get (Object key) Iterator iterator = v.iterator (); while (iterator.hasNext ()) KeyValuePair pair = (KeyValuePair) iterator.next (); if (key.equals (pair.key)) return pair.value; return null; verbatim The idiom to traverse a Vector is the one we saw in Section iterator. When we compare keys, we use deep equality (the equals method) rather than shallow equality (the == operator). This allows the key class to specify the definition of equality. In our example, the keys are Strings, so it will use the built-in equals method in the String class. traverse For most of the built-in classes, the equals method implements deep equality. For some classes, though, it is not easy to define what that means. For example, see the documentation of equals for Doubles. equals equality Because equals is an object method, this implementation of get does not work if key is null. We could handle null as a special case, or we could do what the build-in Hashtable does---simply declare that null is not a legal key. Speaking of the built-in Hashtable, it's implementation of put is a bit different from ours. If there is already an entry in the table with the given key, put updates it (give it a new value), and returns the old value (or null if there was none. Here is an implementation of their version: verbatim public Object put (Object key, Object value) Object result = get (key); if (result == null) KeyValuePair pair = new KeyValuePair (key, value); v.add (pair); else update (key, value); return result; verbatim The update method is not part of the Table ADT, so it is declared private. It traverses the vector until it finds the right KeyValuePair and then it updates the value field. Notice that we don't have to modify the Vector itself, just one of the objects it contains. verbatim private void update (Object key, Object value) Iterator iterator = v.iterator (); while (iterator.hasNext ()) KeyValuePair pair = (KeyValuePair) iterator.next (); if (key.equals (pair.key)) pair.value = value; break; verbatim The only methods we haven't implemented are containsKey and keys. The containsKey method is almost identical to get except that it returns true or false instead of an object reference or null. As an exercise, implement keys by building a Vector of keys and returning the elements of the vector. See the documentation of elements in the Vector class for more information. The List abstract class abstract class!List List abstract class The java.util package defines an abstract class called List that specifies the set of operations a class has to implement in order to be considered (very abstractly) a list. This does not mean, of course, that every class that implements List has to be a linked list. Not surprisingly, the built-in LinkedList class is a member of the List abstract class. Surprisingly, so is Vector. The methods in the List definition include add, get and iterator. In fact, all the methods from the Vector class that we used to implement Table are defined in the List abstract class. That means that instead of a Vector, we could have used any List class. In Table.java we can replace Vector with LinkedList, and the program still works! This kind of type generality can be useful for tuning the performance of a program. You can write the program in terms of an abstract class like List and then test the program with several different implementations to see which yields the best performance. Hash table implementation implementation!Table implementation!hash table hash table!implementation table!hash table implementation The reason that the built-in implementation of the Table ADT is called Hashtable is that it uses a particularly efficient implementation of a Table called a hashtable. Of course, the whole point of defining an ADT is that it allows us to use an implementation without knowing the details. So it is probably a bad thing that the people who wrote the Java library named this class according to its implementation rather than its ADT, but I suppose of all the bad things they did, this one is pretty small. Anyhoo, you might be wondering what a hashtable is, and why I say it is particularly efficient. We'll start by analyzing the performance of the List implementation we just did. Looking at the implementation of put, we see that there are two cases. If the key is not already in the table, then we only have to create a new key-value pair and add it to the List. Both of these are constant-time operations. In the other case, we have to traverse the List to find the existing key-value pair. That's a linear time operation. For the same reason, get and containsKey are also linear. Although linear operations are often good enough, we can do better. It turns out that there is a way to implement the Table ADT so that both put and get are constant time operations! The key is to realize that traversing a list takes time proportional to the length of the list. If we can put an upper bound on the length of the list, then we can put an upper bound on the traverse time, and anything with a fixed upper bound is considered constant time. analysis!hashtable But how can we limit the length of the lists without limiting the number of items in the table? By increasing the number of lists. Instead of one long list, we'll keep many short lists. As long as we know which list to search, we can put a bound on the amount of searching. Hash Functions hash function mapping And that's where hash functions come in. We need some way to look at a key and know, without searching, which list it will be in. We'll assume that the lists are in an array (or Vector) so we can refer to them by index. The solution is to come up with some mapping---almost any mapping---between the key values and the indices of the lists. For every possible key there has to be a single index, but there might be many keys that map to the same index. For example, imagine an array of 8 lists and a table made up of keys that are Integers and values that are Strings. It might be tempting to use the intValue of the Integers as indices, since they are the right type, but there are a whole lot of integers that do not fall between 0 and 7, which are the only legal indices. modulus operator!modulus The modulus operator provides a simple (in terms of code) and efficient (in terms of run time) way to map all the integers into the range . The expression verbatim key.intValue() verbatim is guaranteed to produce a value in the range from -7 to 7 (including both). If you take its absolute value (using Math.abs) you will get a legal index. For other types, we can play similar games. For example, to convert a Character to an integer, we can use the built-in method Character.getNumericValue and for Doubles there is intValue. shifted sum For Strings we could get the numeric value of each character and add them up, or instead we might use a shifted sum. To calculate a shifted sum, alternate between adding new values to the accumulator and shifting the accumulator to the left. By ``shift to the left'' I mean ``multiply by a constant.'' To see how this works, take the list of numbers and compute their shifted sum as follows. First, initialize the accumulator to 0. Then, enumerate Multiply the accumulator by 10. Add the next element of the list to the accumulator. Repeat until the list is finished. enumerate As an exercise, write a method that calculates the shifted sum of the numeric values of the characters in a String using a multiplier of 32. For each type, we can come up with a function that takes values of that type and generates a corresponding integer value. These functions are called hash functions, because they often involve making a hash of the components of the object. The integer value for each object is called its hash code. There is one other way we might generate a hash code for Java objects. Every Java object provides a method called hashCode that returns an integer that corresponds to that object. For the built-in types, the hashCode method is implemented so that if two objects contain the same data, they will have the same hash code (as in deep equality). The documentation of these methods explains what the hash function is. You should check them out. deep equality hash function hash code For user-defined types, it is up to the implementor to provide an appropriate hash function. The default hash function, provided in the Object class, often uses the location of the object to generate a hash code, so its notion of ``sameness'' is shallow equality. Most often when we are searching a hash table for a key, shallow equality is not what we want. Regardless of how the hash code is generated, the last step is to use modulus and absolute value to map the hash code into the range of legal indices. Resizing a hash table resizing hash table!resizing Let's review. A Hash table consists of an array (or Vector) of Lists, where each List contains a small number of key-value pairs. To add a new entry to a table, we calculate the hash code of the new key and add the entry to the corresponding List. To look up a key, we hash it again and search the corresponding list. If the lengths of the lists are bounded then the search time is bounded. So how do we keep the lists short? Well, one goal is to keep them as balanced as possible, so that there are no very long lists at the same time that others are empty. This is not easy to do perfectly---it depends on how well we chose the hash function---but we can usually do a pretty good job. Even with perfect balance, the average list length grows linearly with the number of entries, and we have to put a stop to that. The solution is to keep track of the average number of entries per list, which is called the load factor; if the load factor gets too high, we have to resize the table. load factor rehashing To resize, we create a new table, usually twice as big as the original, take all the entries out of the old one, hash them again, and put them in the new table. Usually we can get away with using the same hash function; we just use a different value for the modulus operator. Performance of resizing analysis!Hashtable How long does it take to resize the table? Clearly it is linear with the number of entries. That means that most of the time put takes constant time, but every once in a while ---when we resize---it takes linear time. At first that sounds bad. Doesn't that undermine my claim that we can perform put in constant time? Well, frankly, yes. But with a little wheedling, I can fix it. Since some put operations take longer than others, let's figure out the average time for a put operation. The average is going to be , the constant time for a simple put, plus an additional term of , the percentage of the time I have to resize, times , the cost of resizing. equation t(n) = c + p kn equation I don't know what and are, but we can figure out what is. Imagine that we have just resized the hash table by doubling its size. If there are entries, then we can add an addition entries before we have to resize again. So the percentage of the time we have to resize is . Plugging into the equation, we get equation t(n) = c + 1/n kn = c + k equation In other words, is constant time! Glossary table entry key value dictionary associative array hash table hash function hash code shifted sum load factor description [table:] An ADT that defines operations on a collection of entries. [entry:] An element in a table that contains a key-value pair. [key:] An index, of any type, used to look up values in a table. [value:] An element, of any type, stored in a table. [dictionary:] Another name for a table. [associative array:] Another name for a dictionary. [hash table:] A particularly efficient implementation of a table. [hash function:] A function that maps values of a certain type onto integers. [hash code:] The integer value that corresponds to a given value. [shifted sum:] A simple hash function often used for compounds objects like Strings. [load factor:] The number of entries in a hashtable divided by the number of lists in the hashtable; i.e. the average number of entries per list. description Wrapper classes For every primitive type in Java, there is a built-in object type called a wrapper class. For example, the wrapper class for int is called Integer; for double it is called Double. Wrapper classes are useful for several reasons: itemize Each wrapper class contains special values (like the minimum and maximum values for the type) and methods that are useful for converting between types. You can instantiate wrapper classes and create objects that contain primitive values. In other words, you can wrap a primitive value up in an object, which is useful if you want to invoke a method that requires an object type. itemize Creating wrapper objects The most straightforward way to create a wrapper object is to use its constructor: verbatim Integer i = new Integer (17); Double d = new Double (3.14159); Character c = new Character ('b'); verbatim Technically String is not a wrapper class, because there is no corresponding primitive type, but the syntax for creating a String object is the same: verbatim String s = new String ("fred"); verbatim On the other hand, no one ever uses the constructor for String objects, because you can get the same effect with a simple String value: verbatim String s = "fred"; verbatim In my development environment, the Boolean wrapper class has not been implemented correctly. There is supposed to be a constructor that takes a primitive boolean as an argument, but the following code verbatim Boolean b = new Boolean (true); verbatim generates an error. Creating more wrapper objects Some of the wrapper classes have a second constructor that takes a String as an argument and tries to convert to the appropriate type. For example: verbatim Integer i = new Integer ("17"); Double d = new Double ("3.14159"); verbatim There is supposed to be a Boolean constructor that takes a String argument, but it has not been implemented in my development environment. There is no such constructor for Characters. The type conversion process is not very robust. For example, if the Strings are not in the right format, they will cause a NumberFormatException. Any non-numeric character in the String, including a space, will cause the conversion to fail. verbatim Integer i = new Integer ("17.1"); // WRONG!! Double d = new Double ("3.1459 "); // WRONG!! verbatim It is usually a good idea to check the format of the String before you try to convert it. Creating even more wrapper objects Annoyingly, there is yet another way to create wrapper objects, using class methods in the wrapper classes. verbatim Integer i = Integer.valueOf ("17"); Double d = Double.valueOf ("3.14159"); verbatim These methods use the same conversion methods as the constructors (parseInt and parseDouble), so they are no more robust. When there are two ways to do the same thing, it is probably best to choose one and stick to it consistently. In this case, I think using the constructors is much better than using valueOf, because it makes it much clearer that you are creating new wrapper objects. The name valueOf is poorly chosen; given the name, it is not at all clear what it does. Getting the values out Java knows how to print wrapper objects, so the easiest way to extract a value is just to print the object: verbatim Integer i = new Integer (17); Double d = new Double (3.14159); System.out.println (i); System.out.println (d); verbatim Alternatively, you can use the toString method to convert the contents of the wrapper object to a String verbatim String istring = i.toString(); String dstring = d.toString(); verbatim Finally, if you just want to extract the primitive value from the object, there is an object method in each wrapper class that does the job: verbatim int iprim = i.intValue (); double dprim = d.doubleValue (); verbatim There are also methods for converting wrapper classes into different primitive types. Useful methods in the wrapper classes As I mentioned, the wrapper classes contain useful methods that pertain to each type. For example, Integer contains methods for interpreting and printing integers in different bases. If you have a String that contains a number in base 6, you can convert to base 10 using parseInt. verbatim String base6 = "12345"; int base10 = Integer.parseInt (base6, 6); System.out.println (base10); verbatim Since parseInt is a class method, you invoke it by naming the class and the method in dot notation. Base 6 might not be all that useful, but hexadecimal (base 16) and octal (base 8) are common for computer science related things. In the Character class, there are lots of methods for converting charaters to upper and lower case, and for checking whether a character is a number, letter, or symbol. Input and Output in Java * System objects System is the name of the built-in class that contains methods and objects used to get input from the keyboard, print text on the screen, and do file input/output (I/0). System.out is the name of the object we have used to print text. When you invoke print and println, you invoke them on the object named System.out. Interestingly, you can print System.out: verbatim System.out.println (System.out); verbatim The output is: verbatim java.io.PrintStream@80cc0e5 verbatim As usual, when Java prints an object, it prints the type of the object, which is PrintStream, the package in which that type is defined, java.io, and a unique identifier for the object. On my machine the identifier is 80cc0e5, but if you run the same code, you will probably get something different. There is also an object named System.in that has type BufferedInputStream. System.in makes it possible to get input from the keyboard. Unfortunately, it does not make it easy to get input from the keyboard. * Keyboard input First, you have to use System.in to create a new InputStreamReader. verbatim InputStreamReader in = new InputStreamReader (System.in); verbatim Then you use in to create a new BufferedReader: verbatim BufferedReader keyboard = new BufferedReader (in); verbatim The point of all this manipulation is that there is a method you can invoke on a BufferedReader, called readLine, that gets input from the keyboard and converts it into a String. For example: verbatim String s = keyboard.readLine (); System.out.println (s); verbatim reads a line from the keyboard and prints the result. There is only one problem. There are things that can go wrong when you invoke readLine, and they might cause an IOException. There is a rule in Java that if a method might cause an exception, it should say so. The syntax looks like this: verbatim public static void main (String[] args) throws IOException verbatim This indicates that main might ``throw'' an IOException. You can think of throwing an exception as similar to throwing a tantrum. * File input Reading input from a file is equally stupid. Here is an example: verbatim public static void main (String[] args) throws FileNotFoundException, IOException processFile ("/usr/dict/words"); public static void processFile (String filename) throws FileNotFoundException, IOException FileReader fileReader = new FileReader (filename); BufferedReader in = new BufferedReader (fileReader); while (true) String s = in.readLine(); if (s == null) break; System.out.println (s); verbatim This program reads each line of the named file (/use/dict/words) into a String and then prints the line. Again, the declaration throws FileNotFoundException, IOException is required by the compiler. The object types FileReader and BufferedReader are part of the insanely complicated class hierarchy Java uses to do incredibly common, simple things. Other than that, you couldn't possibly care how this program works. The Slate Class slate Slate class!Slate verbatim import java.awt.*; public class Example // demonstrate simple use of the Slate class public static void main (String[] args) int width = 500; int height = 500; Slate slate = Slate.makeSlate (width, height); Graphics g = Slate.getGraphics (slate); g.setColor (Color.blue); draw (g, 0, 0, width, height); anim (slate, 0, 0, width, height); // draw is taken from Section 4.14 of the book public static void draw (Graphics g, int x, int y, int width, int height) if (height < 3) return; g.drawOval (x, y, width, height); draw (g, x, y+height/2, width/2, height/2); draw (g, x+width/2, y+height/2, width/2, height/2); // anim demonstrates a simple animation public static void anim (Slate slate, int x, int y, int width, int height) Graphics g = slate.image.getGraphics (); g.setColor (Color.red); for (int i=-100; i<500; i+=8) g.drawOval (i, 100, 100, 100); slate.repaint (); try Thread.sleep(10); catch (InterruptedException e) class Slate extends Frame // image is a buffer: when Slate users draw things, they // draw on the buffer. When the Slate gets painted, we // copy the image onto the screen. Image image; public static Slate makeSlate (int width, int height) Slate s = new Slate (); s.setSize (width, height); s.setBackground (Color.white); s.setVisible (true); s.image = s.createImage (width, height); return s; // when a Slate user asks for a Graphics object, we give // them one from the off-screen buffer. public static Graphics getGraphics (Slate s) return s.image.getGraphics (); // normally update erases the screen and invokes paint, but // since we are overwriting the whole screen anyway, it is // slightly faster to override update and avoid clearing the // screen public void update (Graphics g) paint (g); // paint copies the off-screen buffer onto the screen public void paint (Graphics g) g.drawImage (image, 0, 0, null); verbatim GNU GENERAL PUBLIC LICENSE center Version 2, June 1991 Copyright (C) 1989, 1991 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. center Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it. For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software. Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations. Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all. The precise terms and conditions for copying, distribution and modification follow. GNU GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you". Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does. 1. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change. b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program. In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following: a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code. 4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it. 6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License. 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation. 10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally. NO WARRANTY 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Debugging debugging There are a few different kinds of errors that can occur in a program, and it is useful to distinguish between them in order to track them down more quickly. itemize Compile-time errors are produced by the compiler and usually indicate that there is something wrong with the syntax of the program. Example: omitting the semi-colon at the end of a statement. Run-time errors are produced by the run-time system if something goes wrong while the program is running. Most run-time errors are Exceptions. Example: an infinite recursion eventually causes a StackOverflowException. Semantic errors are problems with a program that compiles and runs, but doesn't do the right thing. Example: an expression may not be evaluated in the order you expect, yielding an unexpected result. itemize compile-time error run-time error semantic error error!compile-time error!run-time error!semantic exception The first step in debugging is to figure out which kind of error you are dealing with. Although the following sections are organized by error type, there are some techniques that are applicable in more than one situation. Compile-time errors *The compiler is spewing error messages. error messages compiler If the compiler reports 100 error messages, that doesn't mean there are 100 errors in your program. When the compiler encounters an error, it gets thrown off track for a while. It tries to recover and pick up again after the first error, but sometimes it fails, and it reports spurious errors. In general, only the first error message is reliable. I suggest that you only fix one error at a time, and then recompile the program. You may find that one semi-colon ``fixes'' 100 errors. Of course, if you see several legitimate error messages, you might as well fix more than one bug per compilation attempt. *I'm getting a weird compiler message and it won't go away. First of all, read the error message carefully. It is written in terse jargon, but often there is a kernel of information there that is carefully hidden. If nothing else, the message will tell you where in the program the problem occurred. Actually, it tells you where the compiler was when it noticed a problem, which is not necessarily where the error is. Use the information the compiler gives you as a guideline, but if you don't see an error where the compiler is pointing, broaden the search. Generally the error will be prior to the location of the error message, but there are cases where it will be somewhere else entirely. For example, if you get an error message at a method invocation, the actual error may be in the method definition. If you are building the program incrementally, you should have a good idea about where the error is. It will be in the last line you added. If you are copying code from a book, start by comparing your code to the book's code very carefully. Check every character. At the same time, remember that the book might be wrong, so if you see something that looks like a syntax error, it might be. If you don't find the error quickly, take a breath and look more broadly at the entire program. Now is a good time to go through the whole program and make sure it is indented properly. I won't say that good indentation makes it easy to find syntax errors, but bad indentation sure makes it harder. Now, start examining the code for the common syntax errors. syntax enumerate Check that all parentheses and brackets are balanced and properly nested. All method definitions should be nested within a class definition. All program statements should be within a method definition. Remember that upper case letters are not the same as lower case letters. Check for semi-colons at the end of statements (and no semi-colons after squiggly-braces). Make sure that any strings in the code have matching quotation marks (and that you use double-quotes, not single). For each assignment statement, make sure that the type on the left is the same as the type on the right. For each method invocation, make sure that the arguments you provide are in the right order, and have right type, and that the object you are invoking the method on is the right type. If you are invoking a fruitful method, make sure you are doing something with the result. If you are invoking a void method, make sure you are not trying to do something with the result. If you are invoking an object method, make sure you are invoking it on an object with the right type. If you are invoking a class method from outside the class where it is defined, make sure you specify the class name. Inside an object method you can refer to the instance variables without specifying an object. If you try that in a class method, you will get a confusing message like, ``Static reference to non-static variable.'' enumerate If nothing works, move on to the next section... *I can't get my program to compile no matter what I do. If the compiler says there is an error and you don't see it, that might be because you and the compiler are not looking at the same code. Check your development environment to make sure the program you are editing is the program the compiler is compiling. If you are not sure, try putting an obvious and deliberate syntax error right at the beginning of the program. Now compile again. If the compiler doesn't find the new error, there is probably something wrong with the way you set up the project. Otherwise, if you have examined the code thoroughly, it is time for desperate measures. You should start over with a program that you can compile and then gradually add your code back. itemize Make a copy of the file you are working on. If you are working on Fred.java, make a copy called Fred.java.old. Delete about half the code from Fred.java. Try compiling again. itemize If the program compiles now, then you know the error is in the other half. Bring back about half of the code you deleted and repeat. If the program still doesn't compile, the error must be in this half. Delete about half of the code and repeat. itemize Once you have found and fixed the error, start bringing back the code you deleted, a little bit at a time. itemize This process is called ``debugging by bisection.'' As an alternative, you can comment out chunks of code instead of deleting them. For really sticky syntax problems, though, I think deleting is more reliable---you don't have to worry about the syntax of the comments, and by making the program smaller you make it more readable. bisection!debugging by debugging by bisection Run-time errors *My program hangs. infinite loop infinite recursion hanging If a program stops and seems to be doing nothing, we say it is ``hanging.'' Often that means that it is caught in an infinite loop or an infinite recursion. itemize If there is a particular loop that you suspect is the problem, add a print statement immediately before the loop that says ``entering the loop'' and another immediately after that says ``exiting the loop.'' Run the program. If you get the first message and not the second, you've got an infinite loop. Go to the section titled ``Infinite loop.'' Most of the time an infinite recursion will cause the program to run for a while and then produce a StackOverflowException. If that happens, go to the section titled ``Infinite recursion.'' If you are not getting a StackOverflowException, but you suspect there is a problem with a recursive method, you can still use the techniques in the infinite recursion section. If neither of those things works, start testing other loops and other recursive methods. If none of those things works, then it is possible that you don't understand the flow of execution in your program. Go to the section titled ``Flow of execution.'' itemize *Infinite loop If you think you have an infinite loop and think you know what loop is causing the problem, add a print statement at the end of the loop that prints the values of the variables in the condition, and the value of the condition. For example, verbatim while (x > 0 && y < 0) // do something to x // do something to y System.out.println ("x: " + x); System.out.println ("y: " + y); System.out.println ("condition: " + (x > 0 && y < 0)); verbatim Now when you run the program you will see three lines of output for each time through the loop. The last time through the loop, the condition should be false. If the loops keeps going, you will be able to see the values of x and y and you might figure out why they are not being updated correctly. *Infinite recursion Most of the time an infinite recursion will cause the program to run for a while and then produce a StackOverflowException. If you suspect that method is causing an infinite recursion, start by checking to make sure that there is a base case. In other words, there should be some condition that will cause the method to return without making a recursive invocation. If not, then you need to rethink the algorithm and identify a base case. If there is a base case, but the program doesn't seem to be reaching it, add a print statement at the beginning of the method that prints the parameters. Now when you run the program you will see a few lines of output every time the method is invoked, and you will see the parameters. If the parameters are not moving toward the base case, you will get some ideas about why not. *Flow of execution flow of execution If you are not sure how the flow of execution is moving through your program, add print statements to the beginning of each method with a message like ``entering method foo,'' where foo is the name of the method. Now when you run the program it will print a trace of each method as it is invoked. It is often useful to print the parameters each method receives when it is invoked. When you run the program, check whether the parameters are reasonable, and check for one of the classic errors---providing parameters in the wrong order. *When I run the program I get an Exception. Exception If something goes wrong during run time, the Java run-time system prints a message that includes the name of the exception, the line of the program where the problem occurred, and a stack trace. The stack trace includes the method that is currently running, and then the method that invoked it, and then the method that invoked that, and so on. In other words, it traces the path of method invocations that got you to where you are. The first step is to examine the place in the program where the error occurred and see if you can figure out what happened. description [NullPointerException:] You tried to access an instance variable or invoke a method on an object that is currently null. You should figure out what variable is null and then figure out how it got to be that way. Remember that when you declare a variable with an object type, it is initially null, until you assign a value to it. For example, this code causes a NullPointerException: verbatim Point blank; System.out.println (blank.x); verbatim [ArrayIndexOutOfBoundsException:] The index you are using to access an array is either negative or greater than array.length-1. If you can find the site where the problem is, add a print statement immediately before it to print the value of the index and the length of the array. Is the array the right size? Is the index the right value? Now work your way backwards through the program and see where the array and the index come from. Find the nearest assignment statement and see if it is doing the right thing. If either one is a parameter, go to the place where the method is invoked and see where the values are coming from. [StackOverFlowException:] See ``Infinite recursion.'' description *I added so many print statements I get inundated with output. print statement statement!print One of the problems with using print statements for debugging is that you can end up buried in output. There are two ways to proceed: either simplify the output or simplify the program. To simplify the output, you can remove or comment out print statements that aren't helping, or combine them, or format the output so it is easier to understand. To simplify the program, there are several things you can do. First, scale down the problem the program is working on. For example, if you are sorting an array, sort a small array. If the program takes input from the user, give it the simplest input that causes the error. Second, clean up the program. Remove dead code and reorganize the program to make it as easy to read as possible. For example, if you suspect that the error is in a deeply-nested part of the program, try rewriting that part with simpler structure. If you suspect a large method, try splitting it into smaller methods and test them separately. Often the process of finding the minimal test case leads you to the bug. For example, if you find that a program works when the array has an even number of elements, but not when it has an odd number, that gives you a clue about what is going on. Similarly, rewriting a piece of code can help you find subtle bugs. If you make a change that you think doesn't affect the program, and it does, that can tip you off. Semantic errors *My program doesn't work. In some ways semantic errors are the hardest, because the compiler and the run-time system provide no information about what is wrong. Only you know what the program was supposed to do, and only you know that it isn't doing it. The first step is to make a connection between the program text and the behavior you are seeing. You need a hypothesis about what the program is actually doing. One of the things that makes this hard is that computers run so fast. You will often wish that you could slow the program down to human speed, but there is no straightforward way to do that, and even if there were, it is not really a good way to debug. Here are some questions to ask yourself: itemize Is there something the program was supposed to do, but doesn't seem to be happening? Find the section of the code that performs that function and make sure it is executing when you think it should. Add a print statement to the beginning of the suspect methods. Is something happening that shouldn't? Find code in your program that performs that function and see if it is executing when it shouldn't. Is a section of code producing an effect that is not what you expected? Make sure that you understand the code in question, especially if it involves invocations to built-in Java methods. Read the documentation for the methods you invoke. Try out the methods by invoking the methods directly with simple test cases, and check the results. itemize In order to program, you need to have a mental model of how programs work. If your program that doesn't do what you expect, very often the problem is not in the program; it's in your mental model. model!mental mental model The best way to correct your mental model is to break the program into its components (usually the classes and methods) and test each component independently. Once you find the discrepancy between your model and reality, you can solve the problem. Of course, you should be building and testing components as you develop the program. If you encounter a problem, there should be only a small amount of new code that is not known to be correct. Here are some common semantic errors that you might want to check for: itemize If you use the assignment operator, =, instead of the equality operator, ==, in the condition of an if, while or for statement, you might get an expression that is sytactically legal, but it doesn't do what you expect. When you apply the equality operator, ==, to an object, it checks shallow equality. If you meant to check deep equality, you should use the equals method (or define one, for user-defined objects). Some Java libraries expect user-defined objects to define methods like equals. If you don't define them yourself, you will inherit the default behavior from the parent class, which may not be what you want. In general, inheritance can cause subtle semantic errors, because you may be executing inherited code without realizing it. Again, make sure you understand the flow of execution in your program. itemize *I've got a big hairy expression and it doesn't do what I expect. expression!big and hairy Writing complex expressions is fine as long as they are readable, but they can be hard to debug. It is often a good idea to break a complex expression into a series of assignments to temporary variables. For example: verbatim rect.setLocation (rect.getLocation().translate (-rect.getWidth(), -rect.getHeight())); verbatim Can be rewritten as verbatim int dx = -rect.getWidth(); int dy = -rect.getHeight(); Point location = rect.getLocation(); Point newLocation = location.translate (dx, dy); rect.setLocation (newLocation); verbatim The explicit version is easier to read, because the variable names provide additional documentation, and easier to debug, because we can check the types of the intermediate variables and display their values. temporary variable variable!temporary order of evaluation precedence Another problem that can occur with big expressions is that the order of evaluation may not be what you expect. For example, if you are translating the expression into Java, you might write verbatim double y = x / 2 * Math.PI; verbatim That is not correct, because multiplication and division have the same precedence, and are evaluated from left to right. So this expression computes . A good way to debug expressions is to add parentheses to make the order of evaluation explicit. verbatim double y = x / (2 * Math.PI); verbatim Any time you are not sure of the order of evaluation, use parentheses. Not only will the program be correct (in the sense of doing what you intend); it will also be more readable for other people who haven't memorized the rules of precedence. *I've got a method that doesn't return what I expect. return statement statement!return If you have a return statement with a complex expression, you don't have a chance to print the return value before returning. Again, you can use a temporary variable. For example, instead of verbatim public Rectangle intersection (Rectangle a, Rectangle b) return new Rectangle ( Math.min (a.x, b.x), Math.min (a.y, b.y), Math.max (a.x+a.width, b.x+b.width)-Math.min (a.x, b.x) Math.max (a.y+a.height, b.y+b.height)-Math.min (a.y, b.y) ); verbatim You could write verbatim public Rectangle intersection (Rectangle a, Rectangle b) int x1 = Math.min (a.x, b.x); int y2 = Math.min (a.y, b.y); int x2 = Math.max (a.x+a.width, b.x+b.width); int y2 = Math.max (a.y+a.height, b.y+b.height); Rectangle rect = new Rectangle (x1, y1, x2-x1, y2-y1); return rect; verbatim Now you have the opportunity to display any of the intermediate variables before returning. *My print statement isn't doing anything print statement statement!print If your use the println method, the output gets displayed immediately, but if you use print (at least in some environments) the output gets stored without being displayed until the next newline character gets output. If the program terminates without producing a newline, you may never see the stored output. If you suspect that this is happening to you, try changing all the print statements to println. *I'm really, really stuck and I need help First of all, try getting away from the computer for a few minutes. Computers emit waves that affect the brain, causing the following symptoms: itemize Frustration and/or rage. Superstitious beliefs (``the computer hates me'') and magical thinking (``the program only works when I wear my hat backwards''). Random walk programming (the attempt to program by writing every possible program and choosing the one that does the right thing). itemize If you find yourself suffering from any of these symptoms, get up and go for a walk. When you are calm, think about the program. What is it doing? What are some possible causes of that behavior? When was the last time you had a working program, and what did you do next? Sometimes it just takes time to find a bug. I often find bugs when I am away from the computer and I let my mind wander. Some of the best places to find bugs are trains, showers, and in bed, just before you fall asleep. *No, I really need help. It happens. Even the best programmers occasionally get stuck. Sometimes you work on a program so long that you can't see the error. A fresh pair of eyes is just the thing. Before you bring someone else in, make sure you have exhausted the techniques described here. You program should be as simple as possible, and you should be working on the smallest input that causes the error. You should have print statements in the appropriate places (and the output they produce should be comprehensible). You should understand the problem well enough to describe it concisely. When you bring someone in to help, be sure to give them the information they need. itemize What kind of bug is it? Compile-time, run-time, or semantic? If the bug occurs at compile-time or run-time, what is the error message, and what part of the program does it indicate? What was the last thing you did before this error occurred? What were the last lines of code that you wrote, or what is the new test case that fails? What have you tried so far, and what have you learned? itemize When you find the bug, take a second to think about what you could have done to find it faster. Next time you see something similar, you will be able to find the bug more quickly. Remember, in this class the goal is not to make the program work. The goal is to learn how to make the program work. Program development plan If you are spending a lot of time debugging, it is probably because you do not have an effective program development plan. A typical, bad program development plan goes something like this: enumerate Write an entire method. Write several more methods. Try to compile the program. Spend an hour finding syntax errors. Spend an hour finding run time errors. Spend three hours finding semantic errors. enumerate The problem, of course, is the first two steps. If you write more than one method, or even an entire method, before you start the debugging process, you are likely to write more code than you can debug. If you find yourself in this situation, the only solution is to remove code until you have a working program again, and then gradually build the program back up. Beginning programmers are often unwilling to do this, because their carefully crafted code is precious to them. To debug effectively, you have to be ruthless! Here is a better program development plan: enumerate Start with a working program that does something visible, like printing something. Add a small number of lines of code at a time, and test the program after every change. Repeat until the program does what it is supposed to do. enumerate After every change, the program should produce some visible effect that demonstrates the new code. This approach to programming can save a lot of time. Because you only add a few lines of code at a time, it is easy to find syntax errors. Also, because each version of the program produces a visible result, you are constantly testing your mental model of how the program works. If your mental model is erroneous, you will be confronted with the conflict (and have a chance to correct it) before you have written a lot of erroneous code. One problem with this approach is that it is often difficult to figure out a path from the starting place to a complete and correct program. I will demonstrate by developing a method called isIn that takes a String and a Vector, and that returns a boolean: true if the String appears in the list and false otherwise. enumerate The first step is to write the shortest possible method that will compile, run, and do something visible: verbatim public static boolean isIn (String word, Vector v) System.out.println ("isIn"); return false; verbatim Of course, to test the method we have to invoke it. In main, or somewhere else in a working program, we need to create a simple test case. We'll start with a case where the String appears in the vector (so we expect the result to be true). verbatim public static void main (String[] args) Vector v = new Vector (); v.add ("banana"); boolean test = isIn ("banana", v); System.out.println (test); verbatim If everything goes according to plan, this code will compile, run, and print the word isIn and the value false. Of course, the answer isn't correct, but at this point we know that the method is getting invoked and returning a value. In my programming career, I have wasted way too much time debugging a method, only to discover that it was never getting invoked. If I had used this development plan, it never would have happened. The next step is to check the parameters the method receives. verbatim public static boolean isIn (String word, Vector v) System.out.println ("isIn looking for " + word); System.out.println ("in the vector " + v); return false; verbatim The first print statement allows us to confirm that isIn is looking for the right word. The second statement prints a list of the elements in the vector. To make things more interesting, we might add a few more elements to the vector: verbatim public static void main (String[] args) Vector v = new Vector (); v.add ("apple"); v.add ("banana"); v.add ("grapefruit"); boolean test = isIn ("banana", v); System.out.println (test); verbatim Now the output looks like this: verbatim isIn looking for banana in the vector [apple, banana, grapefruit] verbatim Printing the parameters might seem silly, since we know what they are supposed to be. The point is to confirm that they are what we think they are. To traverse the vector, we can take advantage of the code from Section vector. In general, it is a great idea to reuse code fragments rather than writing them from scratch. verbatim public static boolean isIn (String word, Vector v) System.out.println ("isIn looking for " + word); System.out.println ("in the vector " + v); for (int i=0; i