bj4_fm.fm Page iv Saturday, November 7, 2009 12:01 PM • Students achieve concept mastery in a rich, structured environment that’s available 24/7 From multiple study paths, to self-assessment, to a wealth of interactive visual and audio resources, WileyPLUS gives you everything you need to personalize the teaching and learning experience. With WileyPLUS: »Find out how to Make It YourS » This online teaching and learning environment integrates the entire digital textbook with the most effective instructor and student resources to fit every learning style. • Instructors personalize and manage their course more effectively with assessment, assignments, grade tracking, and more • manage time better • study smarter • save money www.wileyplus.com WP5_FM_8x10.indd 1 8/7/09 11:36 AM Make It YourS! aLL The heLP, reSoUrceS, and PerSonaL SUPPorT yoU and yoUr STUdenTS need! technical Support 24/7 FaQs, online chat, and phone support www.wileyplus.com/support Student support from an experienced student user ask your local representative for details! Your WileyPLUS account Manager training and implementation support www.wileyplus.com/accountmanager Collaborate with your colleagues, find a mentor, attend virtual and live events, and view resources www.WhereFacultyconnect.com Pre-loaded, ready-to-use assignments and presentations www.wiley.com/college/quickstart 2-Minute tutorials and all of the resources you & your students need to get started www.wileyplus.com/firstday WP5_FM_8x10.indd 2 8/7/09 11:36 AM th edition 4 Big Java bj4_fm.fm Page iii Saturday, November 7, 2009 12:01 PM bj4_fm.fm Page iv Saturday, November 7, 2009 12:01 PM th edition 4 Big Java Cay Horstmann SAN JOSE STATE UNIVERSITY JOHN WILEY & SONS, INC. bj4_fm.fm Page v Saturday, November 7, 2009 12:01 PM VICE PRESIDENT AND EXECUTIVE PUBLISHER Donald Fowley EXECUTIVE EDITOR Beth Lang Golub EDITORIAL ASSISTANT Michael Berlin PRODUCTION SERVICES MANAGER Dorothy Sinclair PRODUCTION EDITOR Janet Foxman EXECUTIVE MARKETING MANAGER Christopher Ruel CREATIVE DIRECTOR Harry Nolan SENIOR DESIGNER Madelyn Lesure PHOTO EDITOR Lisa Gee MEDIA EDITOR Lauren Sapira PRODUCTION SERVICES Cindy Johnson COVER DESIGNER Howard Grossman COVER ILLUSTRATION Susan Cyr This book was set in Stempel Garamond by Publishing Services, and printed and bound by RRD Jefferson City. The cover was printed by RRD Jefferson City. This book is printed on acid-free paper. ∞ Copyright © 2010, 2008, 2006, 2002 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for per- mission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax (201) 748-6008, website www.wiley.com/go/permissions. Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return shipping label are available at www.wiley.com/go/returnlabel. Outside of the United States, please contact your local representative. Library of Congress Cataloging-in-Publication Data: Horstmann, Cay S., 1959– Big Java : compatible with Java 5, 6 and 7 / Cay Horstmann. -- 4th ed. p. cm. Includes index. ISBN 978-0-470-50948-7 (pbk. : alk. paper) 1. Java (Computer program language) I. Title. QA76.73.J38H674 2010 005.13'3--dc22 2009042604 ISBN 978-0-470-50948-7 Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 bj4_fm.fm Page vi Saturday, November 7, 2009 12:01 PM PREFACE vii This book is an introductory text in computer science, focusing on the principles of programming and software engineering. Here are its key features: • Teach objects gradually. In Chapter 2, students learn how to use objects and classes from the standard library. Chapter 3 shows the mechanics of implementing classes from a given specification . Students then use simple objects as they master branches, loops, and arrays. Object-oriented design starts in Chapter 8. This gradual approach allows students to use objects throughout their study of the core algorithmic topics, without teaching bad habits that must be un-learned later. • Reinforce sound engineering practices. A focus on test-driven development encourages students to test their programs systematically. A multitude of useful tips on software quality and common errors encourage the development of good programming habits. • Help students with guidance and worked examples. Beginning programmers often ask “How do I start? Now what do I do?” Of course, an activity as complex as programming cannot be reduced to cookbook- style instructions. However, step-by-step guidance is immensely helpful for building confidence and providing an outline for the task at hand. The book con- tains a large number of “How To” guides for common tasks, with pointers to additional worked examples on the Web. • Focus on the essentials while being technically accurate. An encyclopedic coverage is not helpful for a beginning programmer, but neither is the opposite—reducing the material to a list of simplistic bullet points that give an illusion of knowledge. In this book, the essentials of each subject are presented in digestible chunks, with separate notes that go deeper into good practices or lan- guage features when the reader is ready for the additional information. • Use standard Java. The book teaches the standard Java language—not a specialized “training wheels” environment. The Java language, library, and tools are presented at a depth that is sufficient to solve real-world programming problems. The final chapters of the book cover advanced techniques such as multithreading, database storage, XML, and web programming. • Provide an optional graphics track. Graphical shapes are splendid examples of objects. Many students enjoy writing programs that create drawings or use graphical user interfaces. If desired, these topics can be integrated into the course by using the materials at the end of Chapters 2, 3, 9, and 10. bj4_fm.fm Page vii Saturday, November 7, 2009 12:01 PM viii Preface This is the fourth edition of Big Java, and the book has once again been carefully revised and updated. The new and improved features include: • The How To sections have been updated and expanded, and four new ones have been added. Fifteen new Worked Examples (on the companion web site and in WileyPLUS) walk students through the steps required for solving complex and interesting problems. • The treatment of algorithm design, planning, and the use of pseudocode has been enhanced. Students learn to use pseudocode to define the solution algorithm in Chapter 1. • Chapters have been revised to focus each section on a specific learning objective. These learning objectives also organize the chapter summary to help students assess their progress. • Syntax diagrams now call out features of typical example code to draw student attention to the key elements of the syntax. Additional annotations point out special cases, common errors, and good practice associated with the syntax. • New example tables clearly present a variety of typical and special cases in a compact format. Each example is accompanied by a brief note explaining the usage shown and the values that result from it. • The gradual introduction of objects has been further improved by providing additional examples and insights in the early chapters. • Features introduced in Java 7 are covered as Special Topics so that students can prepare for them. In this edition, we use Java 5 or 6 for the main discussion. • The test bank has been greatly expanded and improved. (See page xi.) • A new set of lab assignments enables students to practice solving complex problems one step at a time. • The LabRat code evaluation feature, enhanced for this edition, gives students instant feedback on their programming assignments. (See page xvi.) New in This Edition More Help for Beginning Programmers Annotated Examples Updated for Java 7 More Opportunities for Practice bj4_fm.fm Page viii Saturday, November 7, 2009 12:01 PM Preface ix The book can be naturally grouped into four parts, as illustrated by Figure 1. The organization of chapters offers the same flexibility as the previous edition; depen- dencies among the chapters are also shown in the figure. Part A: Fundamentals (Chapters 1–7) Chapter 1 contains a brief introduction to computer science and Java programming. Chapter 2 shows how to manipulate objects of predefined classes. In Chapter 3, you will build your own simple classes from given specifications. Fundamental data types, branches, loops, and arrays are covered in Chapters 4–7. Part B: Object-Oriented Design (Chapters 8–12) Chapter 8 takes up the subject of class design in a systematic fashion, and it intro- duces a very simple subset of the UML notation. The discussion of polymorphism and inheritance is split into two chapters. Chap- ter 9 covers interfaces and polymorphism, whereas Chapter 10 covers inheritance. Introducing interfaces before inheritance pays off in an important way: Students immediately see polymorphism before getting bogged down with technical details such as superclass construction. Exception handling and basic file input/output are covered in Chapter 11. The exception hierarchy gives a useful example for inheritance. Chapter 12 contains an introduction to object-oriented design, including two significant case studies. Part C: Data Structures and Algorithms (Chapters 13–17) Chapters 13 through 17 contain an introduction to algorithms and data structures, covering recursion, sorting and searching, linked lists, binary trees, and hash tables. These topics may be outside the scope of a one-semester course, but can be covered as desired after Chapter 7 (see Figure 1). Recursion is introduced from an object-oriented point of view: An object that solves a problem recursively constructs another object of the same class that solves a simpler problem. The idea of having the other object do the simpler job is more intuitive than having a function call itself. Each data structure is presented in the context of the standard Java collections library. You will learn the essential abstractions of the standard library (such as iterators, sets, and maps) as well as the performance characteristics of the various collections. However, a detailed discussion of the implementation of advanced data structures is beyond the scope of this book. Chapter 17 introduces Java generics. This chapter is suitable for advanced stu- dents who want to implement their own generic classes and methods. Part D: Advanced Topics (Chapters 18–24) Chapters 18 through 24 cover advanced Java programming techniques that defi- nitely go beyond a first course in Java. Although, as already mentioned, a compre- hensive coverage of the Java library would span many volumes, many instructors prefer that a textbook should give students additional reference material valuable beyond their first course. Some institutions also teach a second-semester course that A Tour of the Book bj4_fm.fm Page ix Saturday, November 7, 2009 12:01 PM x Preface Figure 1 Chapter Dependencies 4. Fundamental Data Types 5. Decisions 9. Interfaces and Polymorphism 10. Inheritance 11. Input/Output and Exception Handling 19. Streams and Binary I/O 20. Multithreading 12. Object- Oriented Design 22. Relational Databases 13. Recursion 14. Sorting and Searching 15. Intro to Data Structures 16. Advanced Data Structures 21. Internet Networking 23. XML 24. Web Applications 7. Arrrays and Array Lists 6. Iteration 8. Designing Classes 17. Generic Programming 3. Implementing Classes 1. Introduction 2. Using Objects Fundamentals Object-Oriented Design Data Structures & Algorithms Advanced Topics 18. Graphical User Interfaces bj4_fm.fm Page x Saturday, November 7, 2009 12:01 PM Preface xi covers more practical programming aspects such as database and network program- ming, rather than the more traditional in-depth material on data structures and algo- rithms. This book can be used in a two-semester course to give students an introduction to programming fundamentals and broad coverage of applications. Alternatively, the material in the final chapters can be useful for student projects. The advanced topics include graphical user-interface design, advanced file han- dling, multithreading, and those technologies that are of particular interest to server-side programming: networking, databases, XML, and web applications. The Internet has made it possible to deploy many useful applications on servers, often accessed by nothing more than a browser. This server-centric approach to applica- tion development was in part made possible by the Java language and libraries, and today, much of the industrial use of Java is in server-side programming. Appendices Appendix A lists character escape sequences and the Basic Latin and Latin-1 subsets of Unicode. Appendices B and C summarize Java reserved words and operators. Appendix D documents all of the library methods and classes used in this book. Additional appendices contain quick references on Java syntax, HTML, Java tools, binary numbers, and UML. Appendix L contains a style guide for use with this book. Many instructors find it highly beneficial to require a consistent style for all assignments. If this style guide conflicts with instructor sentiment or local customs, however, it is available in electronic form so that it can be modified. Web Resources This book is complemented by a complete suite of online resources and a robust WileyPLUS course. Go to www.wiley.com/college/horstmann to visit the online companion site, which includes • Source code for all examples in the book. • Worked Examples that apply the problem-solving steps in the book to other realistic examples. • Laboratory exercises (and solutions for instructors only). • Lecture presentation slides (in HTML and PowerPoint formats). • Solutions to all review and programming exercises (for instructors only). • A test bank that focuses on skills, not just terminology (for instructors only). WileyPLUS is an online teaching and learning environment that integrates the digital textbook with instructor and student resources. See page xvi for details. • Worked Example How Many Days Have You Been Alive? • Worked Example Working with Pictures • Lab Exercises Animation Variable Initialization and Assignment Animation Parameter Passing Animation Object References Practice Quiz Code Completion Exercises Media Resources www.wiley.com/ college/ horstmann Web resources are summarized at chapter end for easy reference. bj4_fm.fm Page xi Saturday, November 7, 2009 12:01 PM xii Walkthrough The pedagogical elements in this book work together to make the book accessible to beginners as well as those learning Java as a second language. A Walkthrough of the Learning Aids 2.3 The Assignment Operator 39 You can change the value of a variable with the assignment operator (=). For exam- ple, consider the variable declaration int width = 10; If you want to change the value of the variable, simply assign the new value: width = 20; The assignment replaces the original value of the variable (see Figure 1). It is an error to use a variable that has never had a value assigned to it. For exam- ple, the following assignment statement has an error: int height; width = height; // ERROR—uninitialized variable height The compiler will complain about an “uninitialized variable” when you use a vari- able that has never been assigned a value. (See Figure 2.) 2.3 The Assignment Operator Use the assignment operator (=) to change the value of a variable. 1 2 Figure 1 Assigning a New Value to a Variable width = 10 width = 20 1 2 Figure 2 An Uninitialized Variable Syntax 2.2 Assignment height = No value has been assigned. variableName = value; Syntax Example double width = 20; . . width = 30; . . . width = width + 10; The value of this variable is changed. The same name can occur on both sides. See Figure 3. The new value of the variable This is a variable declaration. This is an assignment statement. Annotations explain required components and point to more information on common errors or best practices associated with the syntax. Throughout each chapter, margin notes show where new concepts are introduced and provide an outline of key ideas. Annotated syntax boxes provide a quick, visual overview of new language constructs. Explain the flow of execution in a loop. • A while statement executes a block of code repeatedly. A condition controls for how long the loop is executed. • An off-by-one error is a common error when programming loops. Think through simple test cases to avoid this type of error. Use for loops to implement counting loops. • You use a for loop when a variable runs from a starting to an ending value with a constant increment or decrement. • Make a choice between symmetric and asymmetric loop bounds. • Count the number of iterations to check that your for loop is correct. Implement loops that process a data set until a sentinel value is encountered. • Sometimes, the termination condition of a loop can only be evaluated in the middle of a loop. You can introduce a Boolean variable to control such a loop. Use nested loops to implement multiple levels of iterations. • When the body of a loop contains another loop, the loops are nested. A typical use of nested loops is printing a table with rows and columns. Summary of Learning Objectives Each section corresponds to a learning objective, summarized at chapter end, giving students a roadmap for assessing what they know and what they need to review. bj4_fm.fm Page xii Saturday, November 7, 2009 12:01 PM Walkthrough xiii 180 Decisions Table 1 Relational Operator Examples t n e m m o C e u l a V n o is s e r p x E e u r t 4 = < 3 3 is less than 4; <= tests for “less than or equal”. 3 =< 4 Error The “less than or equal” operator is <=, not =<, with the “less than” symbol first. e s l a f 4 > 3 > is the opposite of <=. e s l a f 4 < 4 The left-hand side must be strictly smaller than the right-hand side. e u r t 4 = < 4 Both sides are equal; <= tests for “less than or equal”. e u r t 2 - 5 = = 3 == tests for equality. e u r t 1 - 5 = ! 3 != tests for inequality. It is true that 3 is not 5 – 1. 3 = 6 / 2 Error Use == to test for equality. 1.0 / 3.0 == 0.333333333 false Although the values are very close to one another, they are not exactly equal. See Common Error 4.3. "10" > 5 Error You cannot compare a string to a number. "Tomato".substring(0, 3).equals("Tom") true Always use the equals method to check whether two strings have the same contents. "Tomato".substring(0, 3) == ("Tom") false Never use == to compare strings; it only checks whether the strings are stored in the same location. See Common Error 5.2 on page 180. "Tom".equalsIgnoreCase("TOM") true Use the equalsIgnoreCase method if you don’t want to distinguish between uppercase and lowercase letters. We simply want to know which car is the better buy. That is the desired output. Step 2 Break down the problem into smaller tasks. For each car, we need to know the total cost of driving it. Let’s do this computation sepa- rately for each car. Once we have the total cost for each car, we can decide which car is the better deal. The total cost for each car is purchase price + operating cost. We assume a constant usage and gas price for ten years, so the operating cost depends on the cost of driving the car for one year. The operating cost is 10 x annual fuel cost. The annual fuel cost is price per gallon x annual fuel consumed. The annual fuel consumed is annual miles driven / fuel efficiency. For example, if you drive the car for 15,000 miles and the fuel efficiency is 15 miles/gallon, the car consumes 1,000 gallons. Step 3 Describe each subtask in pseudocode. In your description, arrange the steps so that any intermediate values are computed before they are needed in other computations. For example, list the step total cost = purchase price + operating cost after you have computed operating cost. Here is the algorithm for deciding which car to buy. For each car, compute the total cost as follows: annual fuel consumed = annual miles driven / fuel efficiency annual fuel cost = price per gallon x annual fuel consumed operating cost = 10 x annual fuel cost total cost = purchase price + operating cost If total cost1 < total cost2 Choose car1. Else Choose car2. HOW TO 1.1 Developing and Describing an Algorithm This is the first of many “How To” sections in this book that give you step-by-step proce- dures for carrying out important tasks in developing computer programs. Before you are ready to write a program in Java, you need to develop an algorithm—a method for arriving at a solution for a particular problem. Describe the algorithm in pseudocode: a sequence of precise steps formulated in English. For example, consider this problem: You have the choice of buying two cars. One is more fuel efficient than the other, but also more expensive. You know the price and fuel efficiency (in miles per gallon, mpg) of both cars. You plan to keep the car for ten years. Assume a price of $4 per gallon of gas and usage of 15,000 miles per year. You will pay cash for the car and not worry about financing costs. Which car is the better deal? Step 1 Determine the inputs and outputs. In our sample problem, we have these inputs: • purchase price1 and fuel efficiency1, the price and fuel efficiency (in mpg) of the first car. • purchase price2 and fuel efficiency2, the price and fuel efficiency of the second car. How To guides give step-by-step guidance for common programming tasks, emphasizing planning and testing. They answer the beginner’s question, “Now what do I do?” and integrate key concepts into a problem-solving sequence. Example tables support beginners with multiple, concrete examples. These tables point out common errors and present another quick reference to the section’s topic. Worked Examples apply the steps in the How To to a different example, illustrating how they can be used to plan, implement, and test a solution to another programming problem. Credit Card Processing This Worked Example uses a loop to remove spaces from a credit card number. Worked Example 6.1 Writing an Algorithm for Tiling a Floor This Worked Example shows how to develop an algorithm for laying tile in an alternating pattern of colors. Worked Example 1.1 bj4_fm.fm Page xiii Saturday, November 7, 2009 12:01 PM