WIXLIB

xiiCONTENTSA Development tools233A.1Installing DrJava . . . . . . . . . . . . . . . . . . . . . . . .233A.2DrJava interactions . . . . . . . . . . . . . . . . . . . . . . .235A.3Command-line interface . . . . . . . . . . . . . . . . . . . . .236A.4Command-line testing . . . . . . . . . . . . . . . . . . . . . .237A.5Running Checkstyle . . . . . . . . . . . . . . . . . . . . . . .239A.6Tracing with a debugger . . . . . . . . . . . . . . . . . . . .240A.7Testing with JUnit . . . . . . . . . . . . . . . . . . . . . . .241A.8Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . .243B Java 2D graphics245B.1Creating graphics . . . . . . . . . . . . . . . . . . . . . . . .245B.2Graphics methods . . . . . . . . . . . . . . . . . . . . . . . .246B.3Example drawing . . . . . . . . . . . . . . . . . . . . . . . .248B.4Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . .250B.5Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .250C Debugging253C.1Compile-time errors . . . . . . . . . . . . . . . . . . . . . . .253C.2Run-time errors . . . . . . . . . . . . . . . . . . . . . . . . .257C.3Logic errors . . . . . . . . . . . . . . . . . . . . . . . . . . .261Index267

PrefaceThink Java is an introduction to computer science and programming intendedfor readers with little or no experience. We start with the most basic conceptsand are careful to define all terms when they are first used. The book presentseach new idea in a logical progression. Larger topics, like recursion and objectoriented programming, are divided into smaller examples and introduced overthe course of several chapters.This book is intentionally concise. Each chapter is 12–14 pages and covers thematerial for one week of a college course. It is not meant to be a comprehensivepresentation of Java, but rather, an initial exposure to programming constructsand techniques. We begin with small problems and basic algorithms and workup to object-oriented design. In the vocabulary of computer science pedagogy,this book uses the “objects late” approach.The philosophy behind the bookHere are the guiding principles that make the book the way it is: One concept at a time. We break down topics that give beginners troubleinto a series of small steps, so that they can exercise each new conceptin isolation before continuing. Balance of Java and concepts. The book is not primarily about Java;it uses code examples to demonstrate computer science. Most chaptersstart with language features and end with concepts.

xivPREFACE Conciseness. An important goal of the book is to be small enough sothat students can read and understand the entire text in a one-semestercollege or AP course. Emphasis on vocabulary. We try to introduce the minimum numberof terms and define them carefully when they are first used. We alsoorganize them in glossaries at the end of each chapter. Program development. There are many strategies for writing programs,including bottom-up, top-down, and others. We demonstrate multipleprogram development techniques, allowing readers to choose methodsthat work best for them. Multiple learning curves. To write a program, you have to understandthe algorithm, know the programming language, and be able to debugerrors. We discuss these and other aspects throughout the book, andinclude an appendix that summarizes our advice.Object-oriented programmingSome Java books introduce classes and objects immediately; others begin withprocedural programming and transition to object-oriented more gradually.Many of Java’s object-oriented features are motivated by problems with previous languages, and their implementations are influenced by this history. Someof these features are hard to explain when people aren’t familiar with theproblems they solve.We get to object-oriented programming as quickly as possible, limited by therequirement that we introduce concepts one at a time, as clearly as possible,in a way that allows readers to practice each idea in isolation before movingon. So it takes some time to get there.But you can’t write Java programs (even hello world) without encounteringobject-oriented features. In some cases we explain a feature briefly when itfirst appears, and then explain it more deeply later on.This book is well suited to prepare students for the AP Computer ScienceA exam, which includes object-oriented design and implementation. (AP is

PREFACExva registered trademark of the College Board.) We introduce nearly everytopic in the “AP Java subset” with a few exceptions. A mapping of ThinkJava section numbers to the current AP course description is available on ourwebsite: http://thinkjava.org.AppendixesThe chapters of this book are meant to be read in order, because each onebuilds on the previous one. We also include three appendixes with materialthat can be read at any time:Appendix 1: Development toolsThe steps for compiling, running, and debugging Java code depend onthe details of the development environment and operating system. Weavoided putting these details in the main text, because they can bedistracting. Instead, we provide this appendix with a brief introductionto DrJava – an interactive development environment (IDE) that is helpfulfor beginners – and other development tools, including Checkstyle forcode quality and JUnit for testing.Appendix 2: Java 2D graphicsJava provides libraries for working with graphics and animation, andthese topics can be engaging for students. The libraries require objectoriented features that readers will not completely understand until afterChapter 11, but they can be used much earlier.Appendix 3: DebuggingWe provide debugging suggestions throughout the book, but we also collect our debugging advice in an appendix. We recommend that readersreview this appendix several times as they work through the book.Using the code examplesMost of the code examples in this book are available from a Git repository athttps://github.com/AllenDowney/ThinkJavaCode. Git is a “version control system” that allows you to keep track of the files that make up a project.A collection of files under Git’s control is called a “repository”.

xviPREFACEGitHub is a hosting service that provides storage for Git repositories and aconvenient web interface. It provides several ways to work with the code: You can create a copy of the repository on GitHub by pressing the Forkbutton. If you don’t already have a GitHub account, you’ll need tocreate one. After forking, you’ll have your own repository on GitHubthat you can use to keep track of code you write. Then you can “clone”the repository, which downloads a copy of the files to your computer. Alternatively, you could clone the repository without forking. If youchoose this option, you don’t need a GitHub account, but you won’t beable to save your changes on GitHub. If you don’t want to use Git at all, you can download the code in a ZIParchive using the Download ZIP button on the GitHub page, or this link:http://tinyurl.com/ThinkJavaCodeZip.After you clone the repository or unzip the ZIP file, you should have a directorycalled ThinkJavaCode with a subdirectory for each chapter in the book.All examples in this book were developed and tested using Java SE Development Kit 8. If you are using a more recent version, the examples in this bookshould still work. If you are using an older version, some of them may not.Contributors over the yearsMany people have sent corrections and suggestions, and we appreciate theirvaluable feedback! Ellen Hildreth used this book to teach Data Structures at WellesleyCollege and submitted a whole stack of corrections, along with somegreat suggestions. Tania Passfield pointed out that some glossaries had leftover terms thatno longer appeared in the text. Elizabeth Wiethoff noticed that the series expansion of exp( x2 ) waswrong. She has also worked on a Ruby version of the book.

PREFACExvii Matt Crawford sent in a whole patch file full of corrections. Chi-Yu Li pointed out a typo and an error in one of the code examples. Doan Thanh Nam corrected an example. Muhammad Saied translated the book into Arabic, and found severalerrors in the process. Marius Margowski found an inconsistency in a code example. Leslie Klein discovered another error in the series expansion of exp( x2 ),identified typos in the card array figures, and gave helpful suggestionsto clarify several exercises. Micah Lindstrom reported half a dozen typos and sent corrections. James Riely ported the textbook source from LaTeX to / Peter Knaggs ported the book to C#.http://www.rigwit.co.uk/think/sharp/ Heidi Gentry-Kolen recorded several video lectures that follow the book.https://www.youtube.com/user/digipipelineWe are especially grateful to our technical reviewers: Blythe Samuels, DavidWisneski, and Stephen Rose. They found errors, made many great suggestions,and helped make the book much better.Additional contributors who found one or more typos: Stijn Debrouwere, GuyDriesen, Andai Velican, Chris Kuszmaul, Daniel Kurikesu, Josh Donath, RensFindhammer, Elisa Abedrapo, Yousef BaAfif, Bruce Hill, Matt Underwood,Isaac Sultan, Dan Rice, Robert Beard, Daniel Pierce, Michael Giftthaler, andMin Zeng.If you have additional comments or ideas about the text, please send them to:feedback@greenteapress.com.

xviiiPREFACE

Chapter 1The way of the programThe goal of this book is to teach you to think like a computer scientist. Thisway of thinking combines some of the best features of mathematics, engineering, and natural science. Like mathematicians, computer scientists use formallanguages to denote ideas, specifically computations. Like engineers, theydesign things, assembling components into systems and evaluating trade-offsamong alternatives. And like scientists, they observe the behavior of complexsystems, form hypotheses, and test predictions.The single most important skill for a computer scientist is problem solving.It involves the ability to formulate problems, think creatively about solutions,and express solutions clearly and accurately. As it turns out, the process oflearning to program is an excellent opportunity to develop problem solvingskills. That’s why this chapter is called, “The way of the program”.On one level you will be learning to program, a useful skill by itself. But onanother level you will use programming as a means to an end. As we go along,that end will become clearer.1.1What is programming?A program is a sequence of instructions that specifies how to perform acomputation. The computation might be something mathematical, like solving

2Chapter 1The way of the programa system of equations or finding the roots of a polynomial. It can also bea symbolic computation, like searching and replacing text in a document or(strangely enough) compiling a program. The details look different in differentlanguages, but a few basic instructions appear in just about every language.input: Get data from the keyboard, a file, a sensor, 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 division.decisions: Check for certain conditions and execute the appropriate code.repetition: Perform some action repeatedly, usually with some variation.Believe it or not, that’s pretty much all there is to it. Every program you’veever used, no matter how complicated, is made up of small instructions thatlook much like these. So you can think of programming as the process ofbreaking down a large, complex task into smaller and smaller subtasks. Theprocess continues until the subtasks are simple enough to be performed withthe basic instructions provided by the computer.1.2What is computer science?One of the most interesting aspects of writing programs is deciding how tosolve a particular problem, especially when there are multiple solutions. Forexample, there are numerous ways to sort a list of numbers, and each way hasits advantages. In order to determine which way is best for a given situation,we need techniques for describing and analyzing solutions formally.Computer science is the science of algorithms, including their discovery andanalysis. An algorithm is a sequence of steps that specifies how to solve aproblem. Some algorithms are faster than others, and some use less spacein computer memory. As you learn to develop algorithms for problems youhaven’t solved before, you also learn to think like a computer scientist.Designing algorithms and writing code is difficult and error-prone. For historical reasons, programming errors are called bugs, and the process of tracking

1.3Programming languages3them down and correcting them is called debugging. As you learn to debugyour programs, you will develop new problem solving skills. You will need tothink creatively when unexpected errors happen.Although it can be frustrating, debugging is an intellectually rich, challenging,and interesting part of computer programming. In some ways, debugging islike detective work. You are confronted with clues, and you have to infer theprocesses and events that led to the results you see. Thinking about how tocorrect programs and improve their performance sometimes even leads to thediscovery of new algorithms.1.3Programming languagesThe programming language you will learn is Java, which is a high-level language. Other high-level languages you may have heard of include Python, Cand C , Ruby, and JavaScript.Before they can run, programs in high-level languages have to be translatedinto a low-level language, also called “machine language”. This translationtakes some time, which is a small disadvantage of high-level languages. Buthigh-level languages have two advantages: It is much easier to program in a high-level language. Programs takeless time to write, they are shorter and easier to read, and they are morelikely to be correct. High-level languages are portable, meaning they can run on differentkinds of computers with few or no modifications. Low-level programscan only run on one kind of computer, and have to be rewritten to runon another.Two kinds of programs translate high-level languages into low-level languages:interpreters and compilers. An interpreter reads a high-level program andexecutes it, meaning that it does what the program says. It processes the program a little at a time, alternately reading lines and performing computations.Figure 1.1 shows the structure of an interpreter.In contrast, a compiler reads the entire program and translates it completelybefore the program starts running. In this context, the high-level program

4Chapter 1The way of the programFigure 1.1: How interpreted languages are executed.is called the source code, and the translated program is called the objectcode or the executable. Once a program is compiled, you can execute itrepeatedly without further translation. As a result, compiled programs oftenrun faster than interpreted programs.Java is both compiled and interpreted. Instead of translating programs directlyinto machine language, the Java compiler generates byte code. Similar tomachine language, byte code is easy and fast to interpret. But it is alsoportable, so it is possible to compile a Java program on one machine, transferthe byte code to another machine, and run the byte code on the other machine.The interpreter that runs byte code is called a “Java Virtual Machine” (JVM).Figure 1.2: The process of compiling and running a Java program.Figure 1.2 shows the steps of this process. Although it might seem complicated,these steps are automated for you in most program development environments.Usually you only have to press a button or type a single command to compileand run your program. On the other hand, it is important to know what stepsare happening in the background, so if something goes wrong you can figureout what it is.1.4The hello world programTraditionally, the first program you write when learning a new programminglanguage is called the hello world program. All it does is display the words“Hello, World!” on the screen. In Java, it looks like this:

1.4The hello world program5public class Hello {public static void main(String[] args) {// generate some simple outputSystem.out.println("Hello, World!");}}When this program runs it displays:Hello, World!Notice that the output does not include the quotation marks.Java programs are made up of class and method definitions, and methods aremade up of statements. A statement is a line of code that performs a basicoperation. In the hello world program, this line is a print statement thatdisplays a message on the screen:System.out.println("Hello, World!");System.out.println displays results on the screen; the name println standsfor “print line”. Confusingly, print can mean both “display on the screen” and“send to the printer”. In this book, we’ll try to say “display” when we meanoutput to the screen. Like most statements, the print statement ends with asemicolon (;).Java is “case-sensitive”, which means that uppercase and lowercase are not thesame. In this example, System has to begin with an uppercase letter; systemand SYSTEM won’t work.A method is a named sequence of statements. This program defines onemethod named main:public static void main(String[] args)The name and format of main is special: when the program runs, it starts atthe first statement in main and ends when it finishes the last statement. Later,we will see programs that define more than one method.A class is a collection of methods. This program defines a class named Hello.You can give a class any name you like, but it is conventional to start with a

6Chapter 1The way of the programcapital letter. The name of the class has to match the name of the file it is in,so this class has to be in a file named Hello.java.Java uses squiggly braces ({ and }) to group th

Think Java is an introduction to computer science and programming intended for readers with little or no experience. We start with the most basic concepts and are careful to de ne all terms when they are rst used. The book presents each new idea in a logical progression. Larger topics, like recursion and object-