Java software solutions etc w bind in access edition 8th

Chapter 1 Overview of program, p. 28 Comparison of Java IDEs, p. 41 Examples of various error types, p. 43 Developing a solution of PP 1.2, p. 55

Chapter 2 Example using strings and escape sequences, p. 63 Review of primitive date and expressions, p. 76 Example using the Scanner class, p. 91 Example using drawn shapes, p. 101 Developing a solution of PP 2.8, p. 109

Chapter 3 Creating objects, p. 115 Example using the Random and Math classes, p. 129 Example using frames and panels, p. 150 Developing a solution of PP 3.5, p. 157

Chapter 4 Dissecting the Die class, p. 164 Discussion of the Account class, p. 178 Example using an extended JPanel, p. 182 Overview of GUI development, p. 191 Developing a solution of PP 4.2, p. 202

Chapter 5 Examples using conditionals, p. 221 Examples using while loops, p. 233

Examples using check boxes and radio buttons, p. 255 Developing a solution of PP 5.4, p. 264

Chapter 6 Examples using for loops, p. 280 Developing a solution of PP 6.2, p. 296

Chapter 7 Exploring the static modifier, p. 305 Examples of method overloading, p. 344 Discussion of layout managers, p. 356 Developing a solution of PP 7.1, p. 374

Chapter 8 Overview of arrays, p. 382 Discussion of the LetterCount example, p. 388 Example using rubberbanding and arrays, p. 423 Developing a solution of PP 8.5, p. 436

Chapter 9 Overview of inheritance, p. 449 Example using a class hierarchy, p. 461 Example using the Timer class, p. 475 Developing a solution of PP 9.8, p. 483

Chapter 10 Exploring the Firm program, p. 490 Sorting Comparable objects, p. 506

Developing a solution of PP 10.1, p. 534

Chapter 11 Proper exception handling, p. 545 Exploring GUI design details, p. 561 Developing a solution of PP 11.1, p. 580

Chapter 12 Tracing the MazeSearch program, p. 594 Exploring the Towers of Hanoi, p. 597 Developing a solution of PP 12.1, p. 613

Chapter 13 Example using a linked list, p. 620 Implementing a queue, p. 628 Developing a solution of PP 13.3, p. 638

LOCATION OF VIDEONOTES IN THE TEXT

Through the power of practice and immediate personalized

feedback, MyProgrammingLab improves your performance.

Learn more at www.myprogramminglab.com

get with the programming

www.myprogramminglab.com
This page intentionally left blank

JOHN LEWIS Virginia Tech

WILLIAM LOFTUS

Accenture

FOUNDATIONS OF PROGRAM DESIGN

Addison-Wesley Boston Columbus Indianapolis New York San Francisco Upper Saddle River

Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo

SOFTWARE SOLUTIONS

Seventh Edition

TM

Editorial Director: Marcia Horton Editor-in-Chief: Michael Hirsch Editorial Assistant: Stephanie Sellinger Vice President, Marketing: Patrice Jones Marketing Manager: Yezan Alayan Marketing Coordinator: Kathryn Ferranti Vice President, Production: Vince O’Brien Managing Editor: Jeff Holcomb Production Project Manager: Heather McNally Senior Operations Supervisor: Alan Fischer Manufacturing Buyer: Lisa McDowell Art Director: Linda Knowles Cover Designer: Suzanne Harbison

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear below, or on appropriate page within text.

Photo Credits: Page 11: NASA Earth Observing System. Page 205: Susan Van Etten /PhotoEdit. Page 267: David Joel /Stone/ Getty Images. Page 377 (left and right): National Oceanic and Atmospheric Administration NOAA. Page 441: Matthew McVay/ Stone/Getty Images. Page 485: Mario Fourmy/REA/Redux Pictures.

Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other countries. Screen shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or affili- ated with the Microsoft Corporation.

Copyright © 2012, 2009, 2007, 2005, 2003 Pearson Education, Inc., publishing as Addison-Wesley, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, stor- age in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, Addison-Wesley, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data

10 9 8 7 6 5 4 3 2 1—QWT—15 14 13 12 11

Image Permission Coordinator: Rita Wenning Cover Photograph: © Creative Crop/Digital Vision/Getty Images Media Editor: Daniel Sandin Media Project Manager: Wanda Rockwell Full-Service Project Management: Rose Kernan,

Nesbitt Graphics, Inc. Composition: Glyph International Printer/Binder: Quebecor World Book

Services, Taunton Cover Printer: Coral Graphics Services,

Inc. Text Font: Sabon LT Std

ISBN 10: 0-13-214918-4

ISBN 13: 978-0-13-214918-1

This book is dedicated to our families.

Sharon, Justin, Kayla, Nathan, and Samantha Lewis

and

Veena, Isaac, and Dévi Loftus

This page intentionally left blank

vii

Welcome to the Seventh Edition of Java Software Solutions: Foundations of Program Design. We are pleased that this book has served the needs of so many students and faculty over the years. This edition has been tailored further to improve the coverage of topics key to introductory computing.

New to This Edition

■ Split Chapter 5 of the 6th edition into two for better coverage and flow.

■ Moved the coverage of the ArrayList class earlier in the book to permit more interesting projects earlier.

■ Improved the discussion of an array as a programming construct.

■ Improved the discussions of visibility modifiers, especially regarding the protected modifier.

■ Replaced and updated examples throughout the book.

■ Replaced, updated, and added exercises and programming projects.

■ Available with MyProgrammingLab (see details later in this Preface).

Feedback from both instructors and students continues to make it clear that we have hit the mark with the overall vision of the book. The emphasis remains on presenting underlying core concepts in a clear and gradual man- ner. The Graphics Track sections in each chapter still segregate the coverage of graphics and graphical user interfaces, giving extreme flexibility in how that material gets covered. The casual writing style and entertaining examples still rule the day.

The enhancements in this edition are designed to allow the instructor more flexibility in topic coverage. In an attempt to cover all issues related to condi- tionals and loops, Chapter 5 in the previous edition had become very large and a bit too encyclopedic. In this edition that chapter has been carefully redesigned into two, giving the coverage of those topics a better flow. The new organization allows more interesting examples to be explored earlier.

One effect of this reorganization is that it allowed us to bring the coverage of the ArrayList class earlier in the book. Although arrays are used internally to

Preface

viii PREFACE

implement the ArrayList class, there is no reason to wait for arrays to be covered to introduce the ArrayList class. Like many other classes in the Java API, the ArrayList class can be used without needing to know how it works internally. An ArrayList object can be used for its (very valuable) functionality as soon as loops are available. The new organization in this edition does exactly that. If the instruc- tor chooses, coverage of ArrayList can still be deferred as it has been before, but now the option is there to introduce them earlier.

In addition to these changes, various discussions throughout the book have been revamped and improved. For example, the explanation of the effects of the protected visibility modifier has enhanced to clarify its use. Furthermore, throughout the book older examples have been rejuvenated, and end-of-chapter exercises and programming projects have been augmented.

Cornerstones of the Text This text is based on the following basic ideas that we believe make for a sound introductory text:

■ True object-orientation. A text that really teaches a solid object-oriented approach must use what we call object-speak. That is, all processing should be discussed in object-oriented terms. That does not mean, however, that the first program a student sees must discuss the writing of multiple classes and methods. A student should learn to use objects before learning to write them. This text uses a natural progression that culminates in the ability to design real object-oriented solutions.

■ Sound programming practices. Students should not be taught how to program; they should be taught how to write good software. There’s a difference. Writing software is not a set of cookbook actions, and a good program is more than a collection of statements. This text integrates practices that serve as the foundation of good programming skills. These practices are used in all examples and are reinforced in the discussions. Students learn how to solve problems as well as how to implement solu- tions. We introduce and integrate basic software engineering techniques throughout the text. The Software Failure vignettes reiterate these lessons by demonstrating the perils of not following these sound practices.

■ Examples. Students learn by example. This text is filled with fully imple- mented examples that demonstrate specific concepts. We have intertwined small, readily understandable examples with larger, more realistic ones. There is a balance between graphics and nongraphics programs. The VideoNotes provide additional examples in a live presentation format.

PREFACE ix

■ Graphics and GUIs. Graphics can be a great motivator for students, and their use can serve as excellent examples of object-orientation. As such, we use them throughout the text in a well-defined set of sections that we call the Graphics Track. This coverage includes the use of event processing and GUIs. Students learn to build GUIs in the appropriate way by using a natural progression of topics. The Graphics Track can be avoided entirely for those who do not choose to use graphics.

Chapter Breakdown Chapter 1 (Introduction) introduces computer systems in general, including basic architecture and hardware, networking, programming, and language translation. Java is introduced in this chapter, and the basics of general program development, as well as object-oriented programming, are discussed. This chapter contains broad introductory material that can be covered while students become familiar with their development environment.

Chapter 2 (Data and Expressions) explores some of the basic types of data used in a Java program and the use of expressions to perform calculations. It discusses the conversion of data from one type to another and how to read input interac- tively from the user with the help of the standard Scanner class.

Chapter 3 (Using Classes and Objects) explores the use of predefined classes and the objects that can be created from them. Classes and objects are used to manipulate character strings, produce random numbers, perform complex calcu- lations, and format output. Enumerated types are also discussed.

Chapter 4 (Writing Classes) explores the basic issues related to writing classes and methods. Topics include instance data, visibility, scope, method parameters, and return types. Encapsulation and constructors are covered as well. Some of the more involved topics are deferred to or revisited in Chapter 6.

Chapter 5 (Conditionals and Loops) covers the use of boolean expressions to make decisions. Then the if statement and while loop are explored in detail. Once loops are established, the concept of an iterator is introduced and the Scanner class is revisited for additional input parsing and the reading of text files. Finally, the ArrayList class introduced, which provides the option for managing a large number of objects.

Chapter 6 (More Conditionals and Loops) examines the rest of Java’s condi- tional (switch) and loop (do, for) statements. All related statements for condi- tionals and loops are discussed, including the enhanced version of the for loop. The for-each loop is also used to process iterators and ArrayList objects.

x PREFACE

Chapter 7 (Object-Oriented Design) reinforces and extends the coverage of issues related to the design of classes. Techniques for identifying the classes and objects needed for a problem and the relationships among them are discussed. This chapter also covers static class members, interfaces, and the design of enu- merated type classes. Method design issues and method overloading are also discussed.

Chapter 8 (Arrays) contains extensive coverage of arrays and array processing. The nature of an array as a low-level programming structure is contrasted to the higher-level object management approach. Additional topics include command- line arguments, variable length parameter lists, and multidimensional arrays.

Chapter 9 (Inheritance) covers class derivations and associated concepts such as class hierarchies, overriding, and visibility. Strong emphasis is put on the proper use of inheritance and its role in software design.

Chapter 10 (Polymorphism) explores the concept of binding and how it relates to polymorphism. Then we examine how polymorphic references can be accom- plished using either inheritance or interfaces. Sorting is used as an example of polymorphism. Design issues related to polymorphism are examined as well.

Chapter 11 (Exceptions) explores the class hierarchy from the Java standard library used to define exceptions, as well as the ability to define our own excep- tion objects. We also discuss the use of exceptions when dealing with input and output and examine an example that writes a text file.

Chapter 12 (Recursion) covers the concept, implementation, and proper use of recursion. Several examples from various domains are used to demonstrate how recursive techniques make certain types of processing elegant.

Chapter 13 (Collections) introduces the idea of a collection and its underlying data structure. Abstraction is revisited in this context and the classic data struc- tures are explored. Generic types are introduced as well. This chapter serves as an introduction to a CS2 course.

Supplements

Student Online Resources These student resources can be accessed at the book’s Companion Website, www.pearsonhighered.com/lewis:

■ Source Code for all the programs in the text

■ Links to Java development environments

■ VideoNotes: short step-by-step videos demonstrating how to solve prob- lems from design through coding. VideoNotes allow for self-paced

www.pearsonhighered.com/lewis
PREFACE xi

instruction with easy navigation including the ability to select, play, re- wind, fast-forward, and stop within each VideoNote exercise. Margin icons in your textbook let you know when a VideoNote video is available for a particular concept or homework problem.

Online Practice and Assessment MyProgrammingLab helps students fully grasp the logic, semantics, and syntax of programming. Through practice exercises and immediate, personalized feed- back, MyProgrammingLab improves the programming competence of beginning students who often struggle with the basic concepts and paradigms of popular high-level programming languages.

A self-study and homework tool, MyProgrammingLab consists of hundreds of small practice problems organized around the structure of this textbook. For students, the system automatically detects errors in the logic and syntax of their code submissions and offers targeted hints that enable students to figure out what went wrong—and why. For instructors, a comprehensive gradebook tracks cor- rect and incorrect answers and stores the code submitted by students for review.

MyProgrammingLab is offered to users of this book in partnership with Turing’s Craft, the makers of the CodeLab interactive programming exer- cise system. For a full demonstration, to see feedback from instructors and students, or to get started using MyProgrammingLab in your course, visit www.myprogramminglab.com.

Instructor Resources The following supplements are available to qualified instructors only. Visit the Pearson Education Instructor Resource Center (www.pearsonhighered.com/irc) or send an e-mail to computing@pearson.com for information on how to access them:

■ Presentation Slides—in PowerPoint.

■ Solutions—includes solutions to exercises and programming projects.

■ Test Bank with powerful test generator software—includes a wealth of free response, multiple-choice, and true/false type questions.

■ Lab Manual—lab exercises are designed to accompany the topic progression in the text.

www.myprogramminglab.com
www.pearsonhighered.com/irc
xii PREFACE

Java Integrated Development Environment (IDE) Resource Kits Instructors can order this text with a kit that includes a disk containing 7 popu- lar Java IDEs (the most recent JDK from Oracle, Eclipse, NetBeans, jGRASP, DrJava, BlueJ, and TextPad) and access to a website containing written and video tutorials for getting started in each IDE. For Instructors, ordering information can be found at www.pearsonhighered.com/cs, or from your campus Pearson Education sales representative. For Students, if your instructor didn’t request the Java IDE Resource Kit, links for downloading the IDEs can be found at the book’s Companion Website.

Features Key Concepts. Throughout the text, the Key Concept boxes highlight funda- mental ideas and important guidelines. These concepts are summarized at the end of each chapter.

Listings. All programming examples are presented in clearly labeled listings, fol- lowed by the program output, a sample run, or screen shot display as appropri- ate. The code is colored to visually distinguish comments and reserved words.

Syntax Diagrams. At appropriate points in the text, syntactic elements of the Java language are discussed in special highlighted sections with diagrams that clearly identify the valid forms for a statement or construct. Syntax diagrams for the entire Java language are presented in Appendix L.

Graphics Track. All processing that involves graphics and graphical user inter- faces is discussed in one or two sections at the end of each chapter that we col- lectively refer to as the Graphics Track. This material can be skipped without loss of continuity, or focused on specifically as desired. The material in any Graphics Track section relates to the main topics of the chapter in which it is found. Graphics Track sections are indicated by a brown border on the edge of the page.

Summary of Key Concepts. The Key Concepts presented throughout a chap- ter are summarized at the end of the chapter.

Self-Review Questions and Answers. These short-answer questions review the fundamental ideas and terms established in the preceding section. They are designed to allow students to assess their own basic grasp of the material. The answers to these questions can be found at the end of the book in Appendix N.

Exercises. These intermediate problems require computations, the analysis or writ- ing of code fragments, and a thorough grasp of the chapter content. While the exer- cises may deal with code, they generally do not require any online activity.

www.pearsonhighered.com/cs
PREFACE xiii

Programming Projects. These problems require the design and implementation of Java programs. They vary widely in level of difficulty.

MyProgrammingLab. Many of the problems in the book can be done online in MyProgrammingLab. Through practice exercises and immediate, personal- ized feedback, MyProgrammingLab improves the programming competence of beginning students who often struggle with the basic concepts and paradigms of popular high-level programming languages.

VideoNotes. Presented by the author, VideoNotes explain topics visually through informal videos in an easy-to-follow format, giving students the extra help they need to grasp important concepts. Look for this VideoNote icon to see which in-chapter topics and end-of-chapter Programming Projects are available as VideoNotes.

Software Failures. These between-chapter vignettes discuss real-world flaws in software design, encouraging students to adopt sound design practices from the beginning.

Acknowledgments I am most grateful to the faculty and students from around the world who have provided their feedback on previous editions of this book. I am pleased to see the depth of the faculty’s concern for their students and the students’ thirst for knowledge. Your comments and questions are always welcome.

I am particularly thankful for the assistance, insight, and attention to detail of Robert Burton from Brigham Young University. For years, Robert has con- sistently provided valuable feedback that helps shape and evolve this textbook. Recently he also performed a revision of the material in Chapter 1 about personal computing systems that brought it back to a state-of-the-art discussion.

Brian Fraser of Simon Fraser University also has recently provided some excel- lent feedback that helped clarify some issues in this edition. Such interaction with computing educators is incredibly valuable.

I also want to thank Dan Joyce from Villanova University, who developed the Self-Review questions, ensuring that each relevant topic had enough review mate- rial, as well as developing the answers to each.

I continue to be amazed at the talent and effort demonstrated by the team at Pearson Addison-Wesley. Michael Hirsch, our editor, has amazing insight and commitment. His assistant, Stephanie Sellinger, is a source of consistent and helpful support. Marketing Manager Yez Alayan makes sure that instructors understand the pedagogical advantages of the text. The cover was designed by the skilled talents of Suzanne Harbison. Jeff Holcomb and Heather McNally led the production effort.

xiv PREFACE

The Addison-Wesley folks were supported by a phenomenal team at Nesbitt Graphics, including Jerilyn Bockorick for the interior design, Rose Kernan for project management, Diane Paluba for production coordination. We thank all of these people for ensuring that this book meets the highest quality standards.

Special thanks go to the following people who provided valuable advice to us about this book via their participation in focus groups, interviews, and reviews. They, as well as many other instructors and friends, have provided valuable feed- back. They include:

Elizabeth Adams James Madison University David Atkins University of Oregon Lewis Barnett University of Richmond Thomas W. Bennet Mississippi College Gian Mario Besana DePaul University Hans-Peter Bischof Rochester Institute of Technology Robert Burton Brigham Young University John Chandler Oklahoma State University Robert Cohen University of Massachusetts, Boston Dodi Coreson Linn Benton Community College James H. Cross II Auburn University Eman El-Sheikh University of West Florida Christopher Eliot University of Massachusetts, Amherst Wanda M. Eanes Macon State College Stephanie Elzer Millersville University Matt Evett Eastern Michigan University Marj Feroe Delaware County Community College,

Pennsylvania John Gauch University of Kansas Chris Haynes Indiana University James Heliotis Rochester Institute of Technology Laurie Hendren McGill University Mike Higgs Austin College Stephen Hughes Roanoke College Saroja Kanchi Kettering University Karen Kluge Dartmouth College Jason Levy University of Hawaii Peter MacKenzie McGill University Blayne Mayfield Oklahoma State University Gheorghe Muresan Rutgers University Laurie Murphy Pacific Lutheran University Dave Musicant Carleton College Faye Navabi-Tadayon Arizona State University

PREFACE xv

Lawrence Osborne Lamar University Barry Pollack City College of San Francisco B. Ravikumar University of Rhode Island David Riley University of Wisconsin (La Crosse) Jerry Ross Lane Community College Patricia Roth Southeastern Polytechnic State University Carolyn Schauble Colorado State University Arjit Sengupta Georgia State University Bennet Setzer Kennesaw State University Vijay Srinivasan JavaSoft, Sun Microsystems, Inc. Stuart Steiner Eastern Washington University Katherine St. John Lehman College, CUNY Alexander Stoytchev Iowa State University Ed Timmerman University of Maryland, University College Shengru Tu University of New Orleans Paul Tymann Rochester Institute of Technology John J. Wegis JavaSoft, Sun Microsystems, Inc. Linda Wilson Dartmouth College David Wittenberg Brandeis University Wang-Chan Wong California State University (Dominguez Hills)

Thanks also go to my friends and former colleagues at Villanova University who have provided so much wonderful feedback. They include Bob Beck, Cathy Helwig, Anany Levitin, Najib Nadi, Beth Taddei, and Barbara Zimmerman.

Special thanks go to Pete DePasquale of The College of New Jersey for the design and evolution of the PaintBox project, as well as the original Java Class Library appendix.

Many other people have helped in various ways. They include Ken Arnold, Mike Czepiel, John Loftus, Sebastian Niezgoda, and Saverio Perugini. Our apolo- gies to anyone we may have omitted.

The ACM Special Interest Group on Computer Science Education (SIGCSE) is a tremendous resource. Their conferences provide an opportunity for educators from all levels and all types of schools to share ideas and materials. If you are an educator in any area of computing and are not involved with SIGCSE, you’re missing out.

This page intentionally left blank

Contents

Preface vii

Chapter 1 Introduction 1

1.1 Computer Processing 2 Software Categories 3 Digital Computers 4 Binary Numbers 7

1.2 Hardware Components 10 Computer Architecture 11 Input/Output Devices 12 Main Memory and Secondary Memory 13 The Central Processing Unit 17

1.3 Networks 20 Network Connections 20 Local-Area Networks and

Wide-Area Networks 22 The Internet 23 The World Wide Web 24 Uniform Resource Locators 25

1.4 The Java Programming Language 26 A Java Program 27 Comments 29 Identifiers and Reserved Words 31 White Space 33

1.5 Program Development 36 Programming Language Levels 36 Editors, Compilers, and Interpreters 38 Development Environments 40 Syntax and Semantics 41 Errors 42

xvii

xviii CONTENTS

1.6 Object-Oriented Programming 44 Problem Solving 45 Object-Oriented Software Principles 46

Chapter 2 Data and Expressions 57

2.1 Character Strings 58 The print and println Methods 58 String Concatenation 60 Escape Sequences 63

2.2 Variables and Assignment 65 Variables 65 The Assignment Statement 67 Constants 69

2.3 Primitive Data Types 71 Integers and Floating Points 71 Characters 73 Booleans 74

2.4 Expressions 75 Arithmetic Operators 75 Operator Precedence 76 Increment and Decrement Operators 80 Assignment Operators 81

2.5 Data Conversion 83 Conversion Techniques 85

2.6 Interactive Programs 87 The Scanner Class 87

2.7 Graphics 92 Coordinate Systems 92 Representing Color 94

2.8 Applets 95 Executing Applets Using the Web 98

2.9 Drawing Shapes 99 The Graphics Class 99

Software Failure: NASA Mars Climate Orbiter

and Polar Lander 111

CONTENTS xix

Chapter 3 Using Classes and Objects 113

3.1 Creating Objects 114 Aliases 116

3.2 The String Class 118

3.3 Packages 122 The import Declaration 124

3.4 The Random Class 126

3.5 The Math Class 129

3.6 Formatting Output 132 The NumberFormat Class 132 The DecimalFormat Class 134 The printf Method 135

3.7 Enumerated Types 138

3.8 Wrapper Classes 141 Autoboxing 143

3.9 Components and Containers 143 Frames and Panels 144

3.10 Nested Panels 148

3.11 Images 151

Chapter 4 Writing Classes 159

4.1 Classes and Objects Revisited 160

4.2 Anatomy of a Class 162 Instance Data 167 UML Class Diagrams 167

4.3 Encapsulation 169 Visibility Modifiers 170 Accessors and Mutators 171

4.4 Anatomy of a Method 172 The return Statement 174 Parameters 175

xx CONTENTS

Local Data 175 Bank Account Example 176

4.5 Constructors Revisited 181

4.6 Graphical Objects 182

4.7 Graphical User Interfaces 191

4.8 Buttons 192

4.9 Text Fields 196

Software Failure: Denver Airport Baggage

Handling System 205

Chapter 5 Conditionals and Loops 207

5.1 Boolean Expressions 208 Equality and Relational Operators 209 Logical Operators 210

5.2 The if Statement 213 The if-else Statement 216 Using Block Statements 219 Nested if Statements 223

5.3 Comparing Data 226 Comparing Floats 226 Comparing Characters 227 Comparing Objects 228

5.4 The while Statement 230 Infinite Loops 234 Nested Loops 236 The break and continue Statements 239

5.5 Iterators 241 Reading Text Files 242

5.6 The ArrayList Class 245

5.7 Determining Event Sources 248

CONTENTS xxi

5.8 Check Boxes and Radio Buttons 251 Check Boxes 251 Radio Buttons 255

Software Failure: Therac-25 267

Chapter 6 More Conditionals and Loops 269

6.1 The switch Statement 270

6.2 The Conditional Operator 274

6.3 The do Statement 275

6.4 The for Statement 279 The for-each Loop 282 Comparing Loops 284

6.5 Drawing with Loops and Conditionals 285

6.6 Dialog Boxes 291

Chapter 7 Object-Oriented Design 301

7.1 Software Development Activities 302

7.2 Identifying Classes and Objects 303 Assigning Responsibilities 305

7.3 Static Class Members 305 Static Variables 306 Static Methods 306

7.4 Class Relationships 310 Dependency 310 Dependencies Among Objects

of the Same Class 310 Aggregation 316 The this Reference 320

7.5 Interfaces 322 The Comparable Interface 327 The Iterator Interface 328

xxii CONTENTS

7.6 Enumerated Types Revisited 329

7.7 Method Design 332 Method Decomposition 333 Method Parameters Revisited 338

7.8 Method Overloading 343

7.9 Testing 345 Reviews 346 Defect Testing 346

7.10 GUI Design 349

7.11 Layout Managers 350 Flow Layout 352 Border Layout 356 Grid Layout 359 Box Layout 361

7.12 Borders 365

7.13 Containment Hierarchies 369

Software Failure: 2003 Northeast Blackout 377

Chapter 8 Arrays 379

8.1 Array Elements 380

8.2 Declaring and Using Arrays 381 Bounds Checking 384 Alternate Array Syntax 389 Initializer Lists 389 Arrays as Parameters 390

8.3 Arrays of Objects 392

8.4 Command-Line Arguments 402

8.5 Variable Length Parameter Lists 404

8.6 Two-Dimensional Arrays 408 Multidimensional Arrays 412

CONTENTS xxiii

8.7 Polygons and Polylines 413 The Polygon Class 416

8.8 Mouse Events 418

8.9 Key Events 427

Software Failure: LA Air Traffic Control 441

Chapter 9 Inheritance 443

9.1 Creating Subclasses 444 The protected Modifier 447 The super Reference 450 Multiple Inheritance 453

9.2 Overriding Methods 455 Shadowing Variables 457

9.3 Class Hierarchies 458 The Object Class 460 Abstract Classes 461 Interface Hierarchies 463

9.4 Visibility 463

9.5 Designing for Inheritance 466 Restricting Inheritance 467

9.6 The Component Class Hierarchy 468

9.7 Extending Adapter Classes 471

9.8 The Timer Class 475

Software Failure: Ariane 5 Flight 501 485

Chapter 10 Polymorphism 487

10.1 Late Binding 488

10.2 Polymorphism via Inheritance 489

xxiv CONTENTS

10.3 Polymorphism via Interfaces 502

10.4 Sorting 504 Selection Sort 505 Insertion Sort 511 Comparing Sorts 512

10.5 Searching 513 Linear Search 513 Binary Search 515 Comparing Searches 519

10.6 Designing for Polymorphism 519

10.7 Event Processing 521

10.8 File Choosers 522

10.9 Color Choosers 525

10.10 Sliders 527

Chapter 11 Exceptions 537

11.1 Exception Handling 538

11.2 Uncaught Exceptions 539

11.3 The try-catch Statement 540 The finally Clause 544

11.4 Exception Propagation 545

11.5 The Exception Class Hierarchy 549 Checked and Unchecked Exceptions 552

11.6 I/O Exceptions 553

11.7 Tool Tips and Mnemonics 557

11.8 Combo Boxes 564

11.9 Scroll Panes 569

11.10 Split Panes 572

CONTENTS xxv

Chapter 12 Recursion 583

12.1 Recursive Thinking 584 Infinite Recursion 584 Recursion in Math 585

12.2 Recursive Programming 586 Recursion vs. Iteration 589 Direct vs. Indirect Recursion 589

12.3 Using Recursion 590 Traversing a Maze 591 The Towers of Hanoi 596

12.4 Recursion in Graphics 601 Tiled Pictures 601 Fractals 604

Chapter 13 Collections 617

13.1 Collections and Data Structures 618 Separating Interface from Implementation 618

13.2 Dynamic Representations 619 Dynamic Structures 619 A Dynamically Linked List 620 Other Dynamic List Representations 625

13.3 Linear Data Structures 627 Queues 627 Stacks 628

13.4 Non-Linear Data Structures 631 Trees 631 Graphs 632

13.5 The Java Collections API 634 Generics 634

xxvi CONTENTS

Appendix A Glossary 641

Appendix B Number Systems 665

Appendix C The Unicode Character Set 673

Appendix D Java Operators 677

Appendix E Java Modifiers 683

Appendix F Java Coding Guidelines 687

Appendix G Java Applets 693

Appendix H Regular Expressions 695

Appendix I Javadoc Documentation Generator 697

Appendix J The PaintBox Project 703

Appendix K GUI Events 715

Appendix L Java Syntax 719

Appendix M The Java Class Library 733

Appendix N Answers to Self-Review Questions 735

Index 789

1

C H A P T E R O B J E C T I V E S ● Describe the relationship between hardware and software.

● Define various types of software and how they are used.

● Identify the core hardware components of a computer and explain their roles.

● Explain how the hardware components interact to execute programs and manage data.

● Describe how computers are connected into networks to share information.

● Introduce the Java programming language.

● Describe the steps involved in program compilation and execution.

● Present an overview of object-oriented principles.

This book is about writing well-designed software. To understand software, we must first have a fundamental understanding of its role

in a computer system. Hardware and software cooperate in a com-

puter system to accomplish complex tasks. The purpose of various

hardware components, and the way those components are connected

into networks, are important prerequisites to the study of software

development. This chapter first discusses basic computer processing

and then begins our exploration of software development by intro-

ducing the Java programming language and the principles of object-

oriented programming.

Introduction 1

1.1 Computer Processing We begin our exploration of computer systems with an overview of computer processing, defining some fundamental terminology and showing how the key pieces of a computer system interact.

A computer system is made up of hardware and software. The hardware com- ponents of a computer system are the physical, tangible pieces that support the computing effort. They include chips, boxes, wires, keyboards, speakers, disks, memory cards, USB flash drives (also called jump drives), cables, plugs, printers, mice, monitors, routers, and so on. If you can physically touch it and it can be considered part of a computer system, then it is computer hardware.

The hardware components of a computer are essentially useless without instructions to tell them what to do. A program is a series of instructions that the hardware executes one after another. Software consists of programs and the data those programs use. Software is the intangible counterpart to the physical hardware components.

Together they form a tool that we can use to help solve problems.

The key hardware components in a computer system are

■ central processing unit (CPU)

■ input/output (I/O) devices

■ main memory

■ secondary memory devices

Each of these hardware components is described in detail in the next section. For now, let’s simply examine their basic roles. The central processing unit (CPU) is the device that executes the individual commands of a program. Input/output (I/O) devices , such as the keyboard, mouse, and monitor, allow a human being to interact with the computer.

Programs and data are held in storage devices called memory, which fall into two categories: main memory and secondary memory. Main memory is the storage device that holds the software while it is being processed by the CPU. Secondary memory devices store software in a relatively permanent manner. The most impor- tant secondary memory device of a typical computer system is the hard disk that resides inside the main computer box. A USB flash drive is also an important sec- ondary memory device. A typical USB flash drive cannot store nearly as much infor- mation as a hard disk. USB flash drives have the advantage of portability; they can be removed temporarily or moved from computer to computer as needed. Another portable secondary memory device is the compact disc (CD).

Figure 1.1 shows how information moves among the basic hardware compo- nents of a computer. Suppose you have an executable program you wish to run.

2 CHAPTER 1 Introduction

KEY CONCEPT A computer system consists of hardware and software that work in concert to help us solve problems.

The program is stored on some secondary memory device, such as a hard disk. When you instruct the computer to execute your program, a copy of the program is brought in from secondary memory and stored in main memory. The CPU reads the individual program instructions from main memory. The CPU then executes the instructions one at a time until the program ends. The data that the instructions use, such as two numbers that will be added together, also are stored in main memory. They are either brought in from secondary memory or read from an input device such as the keyboard. During execution, the program may display information to an output device such as a monitor.

The process of executing a program is fundamental to the operation of a com- puter. All computer systems basically work in the same way.

Software Categories Software can be classified into many categories using various criteria. At this point we will simply differentiate between system programs and application programs.

The operating system is the core software of a computer. It performs two important functions. First, it provides a user interface that allows the user to inter- act with the machine. Second, the operating system manages computer resources such as the CPU and main memory. It determines when programs are allowed to run, where they are loaded into memory, and how hardware devices commu- nicate. It is the operating system’s job to make the computer easy to use and to ensure that it runs efficiently.

Several popular operating systems are in use today. The Windows operating system was developed for personal computers by Microsoft, which has captured an operating system market share of almost 90%. Various versions of the Unix operating system are also quite

1.1 Computer Processing 3

FIGURE 1.1 A simplified view of a computer system

KEY CONCEPT The CPU reads the program instructions from main memory, executing them one at a time until the program ends.

KEY CONCEPT The operating system provides a user interface and manages computer resources.

4 CHAPTER 1 Introduction

popular, especially in larger computer systems. A version of Unix called Linux was developed as an open source project, which means that many people contrib- uted to its development and its code is freely available. Because of that, Linux has become a particular favorite among some users. Mac OS X is an operating system used for computing systems developed by Apple Computers.

An application is a generic term for just about any software other than the operating system. Word processors, missile control systems, database managers, Web browsers, and games all can be considered application programs. Each appli- cation program has its own user interface that allows the user to interact with that particular program.

The user interface for most modern operating systems and applications is a graphical user interface (GUI, pronounced “gooey”), which, as the name implies, make use of graphical screen elements. Among many others, these elements include

■ windows , which are used to separate the screen into distinct work areas

■ icons , which are small images that represent computer resources, such as a file

■ menus, checkboxes, and radio buttons , which provide the user with select- able options

■ sliders , which allow the user to select from a range of values

■ buttons , which can be “pushed” with a mouse click to indicate a user selection

The mouse is the primary input device used with GUIs; thus, GUIs are some- times called point-and-click interfaces . The screen shot in Figure 1.2 shows an example of a GUI.

The interface to an application or operating system is an impor- tant part of the software because it is the only part of the program with which the user interacts directly. To the user, the interface is the program. Throughout this book we discuss the design and imple-

mentation of graphical user interfaces.

The focus of this book is the development of high-quality application pro- grams. We explore how to design and write software that will perform calcula- tions, make decisions, and present results textually or graphically. We use the Java programming language throughout the text to demonstrate various comput- ing concepts.

Digital Computers Two fundamental techniques are used to store and manage information: analog and digital. Analog information is continuous, in direct proportion to the source of the information. For example, an alcohol thermometer is an analog device

KEY CONCEPT As far as the user is concerned, the interface is the program.

1.1 Computer Processing 5

for measuring temperature. The alcohol rises in a tube in direct proportion to the temperature outside the tube. Another example of analog information is an electronic signal used to represent the vibrations of a sound wave. The signal’s voltage varies in direct proportion to the original sound wave. A stereo amplifier sends this kind of electronic signal to its speakers, which vibrate to reproduce the sound. We use the term analog because the signal is directly analogous to the information it represents. Figure 1.3 graphically depicts a sound wave captured by a microphone and represented as an electronic signal.

Digital technology breaks information into discrete pieces and represents those pieces as numbers. The music on a compact disc is stored digitally, as a series of numbers. Each number represents the voltage level of one specific instance of the recording. Many of these measurements are taken in a short period of time, perhaps 44,000 measurements every second. The number of measurements per second is called the sampling rate . If samples are taken often enough, the discrete voltage measurements

FIGURE 1.2 An example of a graphical user interface (GUI)

KEY CONCEPT Digital computers store information by breaking it into pieces and repre- senting each piece as a number.

6 CHAPTER 1 Introduction

can be used to generate a continuous analog signal that is “close enough” to the original. In most cases, the goal is to create a reproduction of the original signal that is good enough to satisfy the human senses.

Figure 1.4 shows the sampling of an analog signal. When analog information is converted to a digital format by breaking it into pieces, we say it has been digitized. Because the changes that occur in a signal between samples are lost, the sampling rate must be sufficiently fast.

Sound wave Analog signal of the sound wave

FIGURE 1.3 A sound wave and an electronic analog signal that represents the wave

Information can be lost between samples

Analog signal

Sampling process

Sampled values 12 11 39 40 7 14 47

FIGURE 1.4 Digitizing an analog signal by sampling

1.1 Computer Processing 7

Sampling is only one way to digitize information. For example, a sentence of text is stored on a computer as a series of numbers, where each number represents a single character in the sentence. Every letter, digit, and punctuation symbol has been assigned a number. Even the space character is assigned a number. Consider the following sentence:

Hi, Heather.

The characters of the sentence are represented as a series of 12 numbers, as shown in Figure 1.5 . When a character is repeated, such as the uppercase 'H' , the same representation number is used. Note that the uppercase version of a letter is stored as a different number from the lowercase version, such as the 'H' and 'h' in the word Heather. They are considered separate and distinct characters.

Modern electronic computers are digital. Every kind of information, including text, images, numbers, audio, video, and even program instructions is broken into pieces. Each piece is represented as a number. The information is stored by storing those numbers.

Binary Numbers A digital computer stores information as numbers, but those numbers are not stored as decimal values. All information in a computer is stored and managed as binary values. Unlike the decimal system, which has 10 digits (0 through 9), the binary number system has only two digits (0 and 1). A single b inary dig it is called a bit .

All number systems work according to the same rules. The base value of a number system dictates how many digits we have to work with and indicates the place value of each digit in a number. The decimal number system is base 10, whereas the binary number system is base 2. Appendix B contains a detailed discussion of number systems.

Modern computers use binary numbers because the devices that store and move information are less expensive and more reliable if they have to represent only one of two possible values. Other than this characteristic, there is nothing special about the binary number

72 105 44 32 72 101 97 104 114116 101 46

H i , H e a t h e r .

FIGURE 1.5 Text is stored by mapping each character to a number

KEY CONCEPT Binary is used to store and move information in a computer because the devices that store and manipu- late binary data are inexpensive and reliable.

8 CHAPTER 1 Introduction

system. Computers have been created that use other number systems to store and move information, but they aren’t as convenient.

Some computer memory devices, such as hard drives, are magnetic in nature. Magnetic material can be polarized easily to one extreme or the other, but intermedi- ate levels are difficult to distinguish. Therefore, magnetic devices can be used to rep- resent binary values quite effectively—a magnetized area represents a binary 1 and a demagnetized area represents a binary 0. Other computer memory devices are made up of tiny electrical circuits. These devices are easier to create and are less likely to fail if they have to switch between only two states. We’re better off reproducing millions of these simple devices than creating fewer, more complicated ones.

Binary values and digital electronic signals go hand in hand. They improve our ability to transmit information reliably along a wire. As we’ve seen, an analog signal has continuously varying voltage with infinitely many states, but a digital signal is discrete, which means the voltage changes dramatically between one extreme (such as +5 volts) and the other (such as –5 volts). At any point, the voltage of a digital signal is considered to be either “high,” which represents a binary 1, or “low,” which represents a binary 0. Figure 1.6 compares these two types of signals.

As a signal moves down a wire, it gets weaker and degrades due to environ- mental conditions. That is, the voltage levels of the original signal change slightly. The trouble with an analog signal is that as it fluctuates, it loses its original infor- mation. Since the information is directly analogous to the signal, any change in the signal changes the information. The changes in an analog signal cannot be recovered because the degraded signal is just as valid as the original. A digital signal degrades just as an analog signal does, but because the digital signal is originally at one of two extremes, it can be reinforced before any information is lost. The voltage may change slightly from its original value, but it still can be interpreted correctly as either high or low.

The number of bits we use in any given situation determines the number of unique items we can represent. A single bit has two possible values, 0 and 1, and

Analog signal Digital signal

FIGURE 1.6 An analog signal vs. a digital signal

1.1 Computer Processing 9

therefore can represent two possible items or situations. If we want to represent the state of a light bulb (off or on), one bit will suffice, because we can interpret 0 as the light bulb being off and 1 as the light bulb being on. If we want to represent more than two things, we need more than one bit.

Two bits, taken together, can represent four possible items because there are exactly four permutations of two bits: 00, 01, 10, and 11. Suppose we want to represent the gear that a car is in (park, drive, reverse, or neutral). We would need only two bits, and could set up a mapping between the bit permutations and the gears. For instance, we could say that 00 represents park, 01 represents drive, 10 represents reverse, and 11 represents neutral. In this case, it wouldn’t matter if we switched that mapping around, though in some cases the relationships between the bit permutations and what they represent are important.

Three bits can represent eight unique items, because there are eight permutations of three bits. Similarly, four bits can represent 16 items, five bits can represent 32 items, and so on. Figure 1.7 shows the relationship between the number of bits used and the number of items they can represent. In general, N bits can represent 2 N unique items. For every bit added, the number of items that can be represented doubles.

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

00000

00001

00010

00011

00100

00101

00110

00111

01000

01001

01010

01011

01100

01101

01110

01111

10000

10001

10010

10011

10100

10101

10110

10111

11000

11001

11010

11011

11100

11101

11110

11111

1 bit 2 bits 3 bits 4 bits 2 items 4 items 8 items 16 items

5 bits 32 items

000

001

010

011

100

101

110

111

00

01

10

11

0

1

FIGURE 1.7 The number of bits used determines the number of items that can be represented

KEY CONCEPT There are exactly 2 N permutations of N bits. Therefore, N bits can repre- sent up to 2 N unique items.

10 CHAPTER 1 Introduction

We’ve seen how a sentence of text is stored on a computer by mapping char- acters to numeric values. Those numeric values are stored as binary numbers. Suppose we want to represent character strings in a language that contains 256 characters and symbols. We would need to use eight bits to store each character because there are 256 unique permutations of eight bits (28 equals 256). Each bit permutation, or binary value, is mapped to a specific character.

How many bits would be needed to represent 195 countries of the world? Seven wouldn’t be enough, because 27 equals 128. Eight bits would be enough, but some of the 256 permutations would not be mapped to a country.

Ultimately, representing information on a computer boils down to the number of items there are to represent and determining the way those items are mapped to binary values.

SELF-REVIEW QUESTIONS (see answers in Appendix N)

SR 1.1 What is hardware? What is software?

SR 1.2 What are the two primary functions of an operating system?

SR 1.3 The music on a CD is created using a sampling rate of 44,000 mea- surements per second. Each measurement is stored as a number that represents a specific voltage level. How many such numbers are used to store a three-minute long song? How many such numbers does it take to represent one hour of music?

SR 1.4 What happens to information when it is stored digitally?

SR 1.5 How many unique items can be represented with the following?

a. 2 bits b. 4 bits c. 5 bits d. 7 bits

SR 1.6 Suppose you want to represent each of the 50 states of the United States using a unique permutation of bits. How many bits would be needed to store each state representation? Why?

1.2 Hardware Components Let’s examine the hardware components of a computer system in more detail. Consider the computer described in Figure 1.8. What does it all mean? Is the sys- tem capable of running the software you want it to? How does it compare with other systems? These terms are explained throughout this section.

1.2 Hardware Components 11

Computer Architecture The architecture of a house defines its structure. Similarly, we use the term com- puter architecture to describe how the hardware components of a computer are put together. Figure 1.9 illustrates the basic architecture of a generic computer system. Information travels between components across a group of wires called a bus.

FIGURE 1.8 The hardware specification of a particular computer

FIGURE 1.9 Basic computer architecture

12 CHAPTER 1 Introduction

The CPU and the main memory make up the core of a computer. As we mentioned earlier, main memory stores programs and data that are in active use, and the CPU methodically executes program instructions one at a time.

Suppose we have a program that computes the average of a list of numbers. The program and the numbers must reside in main memory while the program runs. The CPU reads one program instruction from

main memory and executes it. If an instruction needs data, such as a number in the list, to perform its task, the CPU reads that information as well. This process repeats until the program ends. The average, when computed, is stored in main memory to await further processing or long-term storage in secondary memory.