Preface iii

Special Features xxiv

1 Introduction 1

1.1 Computer Programs 2

1.2 The Anatomy of a Computer 3

1.3 The Java Programming Language 5

1.4 Becoming Familiar with Your Programming Environment 7

1.5 Analyzing Your First Program 11

1.6 Errors 13

1.7 PROBLEM SOLVING Algorithm Design 15

The Algorithm Concept 15

An Algorithm for Solving an Investment Problem 16

Pseudocode 17

From Algorithms to Programs 18

2 Using Objects 23

2.1 Objects and Classes 24

Using Objects 24

Classes 25

2.2 Variables 26

Variable Declarations 26

Types 28

Names 29

Comments 30

Assignment 30

2.3 Calling Methods 33

The Public Interface of a Class 33

Method Arguments 34

Return Values 35

Method Declarations 36

2.4 Constructing Objects 38

2.5 Accessor and Mutator Methods 40

2.6 The API Documentation 41

Browsing the API Documentation 41

Packages 43

2.7 Implementing a Test Program 44

2.8 Object References 46

2.9 Graphical Applications 49

Frame Windows 50

Drawing on a Component 51

Displaying a Component in a Frame 53

2.10 Ellipses, Lines, Text, and Color 54

Ellipses and Circles 54

Lines 55

Drawing Text 56

Colors 56

3 Implementing Classes 61

3.1 Instance Variables and Encapsulation 62

Instance Variables 62

The Methods of the Counter Class 64

Encapsulation 64

3.2 Specifying the Public Interface of a Class 66

Specifying Methods 66

Specifying Constructors 67

Using the Public Interface 69

Commenting the Public Interface 69

3.3 Providing the Class Implementation 72

Providing Instance Variables 72

Providing Constructors 73

Providing Methods 75

3.4 Unit Testing 81

3.5 PROBLEM SOLVING Tracing Objects 84

3.6 Local Variables 86

3.7 The this Reference 88

3.8 Shape Classes 90

4 Fundamental Data Types 99

4.1 Numbers 100

Number Types 100

Constants 102

4.2 Arithmetic 107

Arithmetic Operators 107

Increment and Decrement 107

Integer Division and Remainder 108

Powers and Roots 109

Converting Floating-Point Numbers to Integers 110

4.3 Input and Output 114

Reading Input 114

Formatted Output 115

4.4 PROBLEM SOLVING First Do it By Hand 121

4.5 Strings 122

The String Type 122

Concatenation 123

String Input 124

Escape Sequences 124

Strings and Characters 124

Substrings 125

5 Decisions 131

5.1 The if Statement 132

5.2 Comparing Values 137

Relational Operators 138

Comparing Floating-Point Numbers 139

Comparing Strings 140

Comparing Objects 141

Testing for null 141

5.3 Multiple Alternatives 146

5.4 Nested Branches 149

5.5 PROBLEM SOLVING Flowcharts 156

5.6 PROBLEM SOLVING Selecting Test Cases 159

5.7 Boolean Variables and Operators 161

Operators 165

5.8 APPLICATION Input Validation 166

6 Loops 171

6.1 The while Loop 172

6.2 PROBLEM SOLVING Hand-Tracing 179

6.3 The for Loop 183

Header 189

6.4 The do Loop 190

6.5 APPLICATION Processing Sentinel Values 192

6.6 PROBLEM SOLVING Storyboards 197

6.7 Common Loop Algorithms 199

Sum and Average Value 199

Counting Matches 200

Finding the First Match 200

Prompting Until a Match is Found 201

Maximum and Minimum 201

Comparing Adjacent Values 202

6.8 Nested Loops 206

6.9 APPLICATION Random Numbers and Simulations 209

Generating Random Numbers 210

The Monte Carlo Method 211

6.10 Using a Debugger 213

7 Arrays and Array Lists 221

7.1 Arrays 222

Declaring and Using Arrays 222

Array References 225

Using Arrays with Methods 226

Partially Filled Arrays 226

Arguments 229

7.2 The Enhanced for Loop 230

7.3 Common Array Algorithms 232

Filling 232

Sum and Average Value 232

Maximum and Minimum 232

Element Separators 232

Linear Search 233

Removing an Element 234

Inserting an Element 234

Swapping Elements 236

Copying Arrays 237

Reading Input 238

7.4 PROBLEM SOLVING Adapting Algorithms 240

7.5 PROBLEM SOLVING Discovering Algorithms by Manipulating Physical Objects 245

7.6 Two-Dimensional Arrays 248

Declaring Two-Dimensional Arrays 248

Accessing Elements 249

Locating Neighboring Elements 250

Accessing Rows and Columns 251

Two-Dimensional Array Parameters 252

7.7 Array Lists 255

Declaring and Using Array Lists 255

Using the Enhanced for Loop with Array Lists 258

Copying Array Lists 259

Wrappers and Auto-boxing 259

Using Array Algorithms with Array Lists 260

Storing Input Values in an Array List 261

Removing Matches 261

Choosing Between Array Lists and Arrays 262

7.8 Regression Testing 264

8 Designing Classes 271

8.1 Discovering Classes 272

8.2 Designing Good Methods 273

Providing a Cohesive Public Interface 273

Minimizing Dependencies 274

Separating Accessors and Mutators 275

Minimizing Side Effects 276

8.3 PROBLEM SOLVING Patterns for Object Data 282

Keeping a Total 282

Counting Events 283

Collecting Values 283

Managing Properties of an Object 284

Modeling Objects with Distinct States 284

Describing the Position of an Object 285

8.4 Static Variables and Methods 286

8.5 PROBLEM SOLVING Solve a Simpler Problem First 291

8.6 Packages 295

Organizing Related Classes into Packages 295

Importing Packages 296

Package Names 297

Packages and Source Files 297

8.7 Unit Test Frameworks 300

9 Inheritance 305

9.1 Inheritance Hierarchies 306

9.2 Implementing Subclasses 310

9.3 Overriding Methods 314

9.4 Polymorphism 319

9.5 Object: The Cosmic Superclass 330

Overriding the toString Method 330

The equals Method 332

The instanceof Operator 333

10 Interfaces 339

10.1 Using Interfaces for Algorithm Reuse 340

Discovering an Interface Type 340

Declaring an Interface Type 341

Implementing an Interface Type 343

Comparing Interfaces and Inheritance 345

10.2 Working with Interface Variables 348

Converting from Classes to Interfaces 348

Invoking Methods on Interface Variables 349

Casting from Interfaces to Classes 349

10.3 The Comparable Interface 350

Interface 352

10.4 Using Interfaces for Callbacks 355

10.5 Inner Classes 360

10.6 Mock Objects 361

10.7 Event Handling 363

Listening to Events 363

Using Inner Classes for Listeners 365

10.8 Building Applications with Buttons 368

10.9 Processing Timer Events 371

10.10 Mouse Events 374

11 Input/Output and Exception Handling 383

11.1 Reading and Writing Text Files 384

11.2 Text Input and Output 389

Reading Words 389

Reading Characters 390

Classifying Characters 390

Reading Lines 390

Scanning a String 392

Converting Strings to Numbers 392

Avoiding Errors When Reading Numbers 392

Mixing Number, Word, and Line Input 393

Formatting Output 394

11.3 Command Line Arguments 396

11.4 Exception Handling 403

Throwing Exceptions 403

Catching Exceptions 405

Checked Exceptions 407

Closing Resources 409

Designing Your Own Exception Types 410

11.5 APPLICATION Handling Input Errors 412

12 Object-Oriented Design 419

12.1 Classes and Their Responsibilities 420

Discovering Classes 420

The CRC Card Method 421

12.2 Relationships Between Classes 423

Dependency 423

Aggregation 424

Inheritance 425

12.3 APPLICATION Printing an Invoice 428

Requirements 429

CRC Cards 429

UML Diagrams 432

Method Documentation 432

Implementation 434

13 Recursion 443

13.1 Triangle Numbers 444

13.2 Recursive Helper Methods 452

13.3 The Efficiency of Recursion 453

13.4 Permutations 459

13.5 Mutual Recursion 463

13.6 Backtracking 469

14 Sorting and Searching 477

14.1 Selection Sort 478

14.2 Profiling the Selection Sort Algorithm 481

14.3 Analyzing the Performance of the Selection Sort Algorithm 484

14.4 Merge Sort 488

14.5 Analyzing the Merge Sort Algorithm 491

14.6 Searching 495

Linear Search 495

Binary Search 497

14.7 PROBLEM SOLVING Estimating the Running Time of an Algorithm 500

Linear Time 500

Quadratic Time 501

The Triangle Pattern 502

Logarithmic Time 503

14.8 Sorting and Searching in the Java Library 504

Sorting 504

Binary Search 505

Comparing Objects 505

15 The Java Collections Framework 511

15.1 An Overview of the Collections Framework 512

15.2 Linked Lists 514

The Structure of Linked Lists 515

The LinkedList Class of the Java Collections Framework 516

List Iterators 516

15.3 Sets 520

Choosing a Set Implementation 520

Working with Sets 522

15.4 Maps 525

15.5 Stacks, Queues, and Priority Queues 531

Stacks 531

Queues 532

Priority Queues...