Java Concepts, Binder Ready Version

Cay Horstmann grew up in Northern Germany and attended the Christian-Albrechts-Universität in Kiel, a harbor town at the Baltic sea. He received a M.S. in computer science from Syracuse University, and a Ph.D. in mathematics from the University of Michigan in Ann Arbor. For four years, he was VP and CTO of an Internet startup that went from 3 people in a tiny office to a public company. He now teaches computer science at San Jose State University. Cay also writes books and articles on programming languages and computer science education.

Preface v

Special Features xxvi

1 Introduction 1

1.1 Computer Programs 2

1.2 The Anatomy of a Computer 3

1.3 The Java Programming Language 6

1.4 Becoming Familiar with Your Programming Environment 7

1.5 Analyzing Your First Program 11

1.6 Errors 14

1.7 Problem Solving Algorithm Design 15

The Algorithm Concept 16

An Algorithm for Solving an Investment Problem 17

Pseudocode 18

From Algorithms to Programs 18

HT 1 Describing an Algorithm with Pseudocode 19

WE 1 Writing an Algorithm for Tiling a Floor 21

2 Using Objects 31

2.1 Objects and Classes 32

Using Objects 32

Classes 33

2.2 Variables 34

Variable Declarations 34

Types 36

Names 37

Comments 38

Assignment 38

2.3 Calling Methods 41

The Public Interface of a Class 41

Method Arguments 42

Return Values 43

Method Declarations 45

2.4 Constructing Objects 46

2.5 Accessor and Mutator Methods 48

2.6 The API Documentation 50

Browsing the API Documentation 50

Packages 52

2.7 Implementing a Test Program 53

ST 1 Testing Classes in an Interactive Environment 54

WE 1 How Many Days Have You Been Alive?

WE 2 Working with Pictures

2.8 Object References 55

2.9 Graphical Applications 59

Frame Windows 59

Drawing on a Component 60

Displaying a Component in a Frame 63

2.10 Ellipses, Lines, Text, and Color 64

Ellipses and Circles 64

Lines 65

Drawing Text 65

Colors 66

3 Implementing Classes 79

3.1 Instance Variables and Encapsulation 80

Instance Variables 80

The Methods of the Counter Class 82

Encapsulation 82

3.2 Specifying the Public Interface of a Class 84

Specifying Methods 84

Specifying Constructors 85

Using the Public Interface 87

Commenting the Public Interface 87

3.3 Providing the Class Implementation 91

Providing Instance Variables 91

Providing Constructors 92

Providing Methods 93

HT 1 Implementing a Class 96

WE 1 Making a Simple Menu

3.4 Unit Testing 100

3.5 Problem Solving Tracing Objects 103

3.6 Local Variables 105

3.7 The this Reference 107

ST 1 Calling One Constructor from Another 110

3.8 Shape Classes 110

HT 2 Drawing Graphical Shapes 114

4 Fundamental Data Types 129

4.1 Numbers 130

Number Types 130

Constants 132

ST 1 Big Numbers 136

4.2 Arithmetic 137

Arithmetic Operators 137

Increment and Decrement 138

Integer Division and Remainder 138

Powers and Roots 139

Converting Floating-Point Numbers to Integers 140

J8 1 Avoiding Negative Remainders 143

ST 2 Combining Assignment and Arithmetic 143

ST 3 Instance Methods and Static Methods 143

4.3 Input and Output 145

Reading Input 145

Formatted Output 146

HT 1 Carrying Out Computations 149

WE 1 Computing the Volume and Surface Area of a Pyramid

4.4 Problem Solving First Do it By Hand 152

WE 2 Computing Travel Time

4.5 Strings 154

The String Type 154

Concatenation 155

String Input 155

Escape Sequences 156

Strings and Characters 156

Substrings 157

ST 4 Using Dialog Boxes for Input and Output 160

5 Decisions 177

5.1 The if Statement 178

ST 1 The Conditional Operator 182

5.2 Comparing Values 183

Relational Operators 184

Comparing Floating-Point Numbers 185

Comparing Strings 186

Comparing Objects 187

Testing for null 187

HT 1 Implementing an if Statement 190

WE 1 Extracting the Middle

5.3 Multiple Alternatives 193

ST 2 The switch Statement 196

5.4 Nested Branches 196

ST 3 Block Scope 201

ST 4 Enumeration Types 203

5.5 Problem Solving Flowcharts 203

5.6 Problem Solving Selecting Test Cases 206

ST 5 Logging 208

5.7 Boolean Variables and Operators 209

ST 6 Short-Circuit Evaluation of Boolean Operators 213

ST 7 De Morgan’s Law 213

5.8 Application Input Validation 214

6 Loops 237

6.1 The while Loop 238

6.2 Problem Solving Hand-Tracing 245

6.3 The for Loop 250

ST 1 Variables Declared in a for Loop Header 257

6.4 The do Loop 258

6.5 Processing Sentinel Values 259

ST 2 Redirection of Input and Output 262

ST 3 The “Loop and a Half” Problem 262

ST 4 The break and continue Statements 263

6.6 Problem Solving Storyboards 265

6.7 Common Loop Algorithms 268

Sum and Average Value 268

Counting Matches 268

Finding the First Match 269

Prompting Until a Match is Found 270

Maximum and Minimum 270

Comparing Adjacent Values 271

HT 1 Writing a Loop 272

WE 1 Credit Card Processing

6.8 Nested Loops 275

WE 2 Manipulating the Pixels in an Image

6.9 Application Random Numbers and Simulations 279

Generating Random Numbers 279

The Monte Carlo Method 281

6.10 Using a Debugger 282

HT 2 Debugging 285

WE 3 A Sample Debugging Session

7 Arrays and Array Lists 307

7.1 Arrays 308

Declaring and Using Arrays 308

Array References 311

Using Arrays with Methods 312

Partially Filled Arrays 312

ST 1 Methods with a Variable Number of Arguments 315

7.2 The Enhanced for Loop 317

7.3 Common Array Algorithms 318

Filling 318

Sum and Average Value 319

Maximum and Minimum 319

Element Separators 319

Linear Search 320

Removing an Element 320

Inserting an Element 321

Swapping Elements 322

Copying Arrays 323

Reading Input 324

ST 2 Sorting with the Java Library 327

7.4 Problem Solving Adapting Algorithms 327

HT 1 Working with Arrays 330

WE 1 Rolling the Dice

7.5 Problem Solving Discovering Algorithms by Manipulating Physical Objects 332

7.6 Two-Dimensional Arrays 336

Declaring Two-Dimensional Arrays 336

Accessing Elements 337

Locating Neighboring Elements 338

Accessing Rows and Columns 338

WE 2 A World Population Table

ST 3 Two-Dimensional Arrays Row Lengths 341

ST 4 Multidimensional Arrays 343

7.7 Array Lists 343

Declaring and Using Array Lists 344

Using the Enhanced for Loop with Array Lists 345

Copying Array Lists 346

Wrappers and Auto-boxing 347

Using Array Algorithms with Array Lists 348

Storing Input Values in an Array List 348

Removing Matches 348

Choosing Between Array Lists and Arrays 349

ST 5 The Diamond Syntax 352

7.8 Regression Testing 352

8 Designing Classes 375

8.1 Discovering Classes 376

8.2 Designing Good Methods 377

Providing a Cohesive Public Interface 377

Minimizing Dependencies 378

Separating Accessors and Mutators 379

Minimizing Side Effects 380

ST 1 Call by Value and Call by Reference 382

8.3 Problem Solving Patterns for Object Data 386

Keeping a Total 386

Counting Events 387

Collecting Values 387

Managing Properties of an Object 388

Modeling Objects with Distinct States 388

Describing the Position of an Object 389

8.4 Static Variables and Methods 391

ST 2 Alternative Forms of Instance and Static Variable Initialization 394

ST 3 Static Imports 395

8.5 Problem Solving Solve a Simpler Problem First 395

8.6 Packages 400

Organizing Related Classes into Packages 400

Importing Packages 401

Package Names 401

Packages and Source Files 402

ST 4 Package Access 403

HT 1 Programming with Packages 404

8.7 Unit Test Frameworks 405

9 Inheritance 423

9.1 Inheritance Hierarchies 424

9.2 Implementing Subclasses 428

9.3 Overriding Methods 433

ST 1 Calling the Superclass Constructor 438

9.4 Polymorphism 439

ST 2 Dynamic Method Lookup and the Implicit Parameter 442

ST 3 Abstract Classes 443

ST 4 Final Methods and Classes 444

ST 5 Protected Access 444

HT 1 Developing an Inheritance Hierarchy 445

WE 1 Implementing an Employee Hierarchy for Payroll Processing

9.5 Object: The Cosmic Superclass 450

Overriding the toString Method 450

The equals Method 452

The instanceof Operator 453

ST 6 Inheritance and the toString Method 455

ST 7 Inheritance and the equals Method 456

10 Interfaces 465

10.1 Using Interfaces for Algorithm Reuse 466

Discovering an Interface Type 466

Declaring an Interface Type 467

Implementing an Interface Type 469

Comparing Interfaces and Inheritance 471

ST 1 Constants in Interfaces 473

J8 1 Static Methods in Interfaces 473

J8 2 Default Methods 473

J8 3 Conflicting Default Methods 474

10.2 Working with Interface Variables 475

Converting from Classes to Interfaces 475

Invoking Methods on Interface Variables 476

Casting from Interfaces to Classes 476

WE 1 Investigating Number Sequences

10.3 The Comparable Interface 477

ST 2 The clone Method and the Cloneable Interface 479

10.4 Using Interfaces for Callbacks 482

J8 4 Lambda Expressions 485

ST 3 Generic Interface Types 486

10.5 Inner Classes 487

ST 4 Anonymous Classes 488

10.6 Mock Objects 489

10.7 Event Handling 490

Listening to Events 491

Using Inner Classes for Listeners 493

J8 5 Lambda Expressions for Event Handling 496

10.8 Building Applications with Buttons 496

10.9 Processing Timer Events 499

10.10 Mouse Events 502

ST 5 Keyboard Events 506

ST 6 Event Adapters 506

11 Input/Output and Exception Handling 519

11.1 Reading and Writing Text Files 520

ST 1 Reading Web Pages 523

ST 2 File Dialog Boxes 523

ST 3 Character Encodings 524

11.2 Text Input and Output 525

Reading Words 525

Reading Characters 526

Classifying Characters 526

Reading Lines 527

Scanning a String 528

Converting Strings to Numbers 528

Avoiding Errors When Reading Numbers 529

Mixing Number, Word, and Line Input 529

Formatting Output 530

ST 4 Regular Expressions 532

ST 5 Reading an Entire File 533

11.3 Command Line Arguments 533

HT 1 Processing Text Files 536

WE 1 Analyzing Baby Names

11.4 Exception Handling 540

Throwing Exceptions 540

Catching Exceptions 542

Checked Exceptions 543

Closing Resources 545

Designing Your Own Exception Types 546

ST 6 Assertions 549

ST 7 The try/finally Statement 549

11.5 Application Handling Input Errors 549

12 Object-Oriented Design 565

12.1 Classes and Their Responsibilities 566

Discovering Classes 566

The CRC Card Method 567

12.2 Relationships Between Classes 569

Dependency 569

Aggregation 570

Inheritance 571

HT 1 Using CRC Cards and UML Diagrams in Program Design 572

ST 1 Attributes and Methods in UML Diagrams 573

ST 2 Multiplicities 574

ST 3 Aggregation, Association, and Composition 574

12.3 Application Printing an Invoice 575

Requirements 575

CRC Cards 576

UML Diagrams 578

Method Documentation 579

Implementation 581

WE 1 Simulating an Automatic Teller Machine

13 Recursion (Web Only)

13.1 Triangle Numbers

HT 1 Thinking Recursively

WE 1 Finding Files

13.2 Recursive Helper Methods

13.3 The Efficiency of Recursion

13.4 Permutations

13.5 Mutual Recursion

13.6 Backtracking

WE 2 Towers of Hanoi

14 Sorting and Searching (Web Only)

14.1 Selection Sort

14.2 Profiling the Selection Sort Algorithm

14.3 Analyzing the Performance of the Selection Sort Algorithm

ST 1 Oh, Omega, and Theta

ST 2 Insertion Sort

14.4 Merge Sort

14.5 Analyzing the Merge Sort Algorithm

ST 3 The Quicksort Algorithm

14.6 Searching

Linear Search

Binary Search

14.7 Problem Solving Estimating the Running Time of an Algorithm

Linear Time

Quadratic Time

The Triangle Pattern

Logarithmic Time

14.8 Sorting and Searching in the Java Library

Sorting

Binary Search

Comparing Objects

ST 4 The Comparator Interface

J8 1 Comparators with Lambda Expressions

WE 1 Enhancing the Insertion Sort Algorithm

15 The Java Collections Framework (Web Only)

15.1 An Overview of the Collections Framework

15.2 Linked Lists

The Structure of Linked Lists

The LinkedList Class of the Java Collections

Framework

List Iterators

15.3 Sets

Choosing a Set Implementation Working with Sets

15.4 Maps

J8 1 Updating Map Entries

HT 1 Choosing a Collection

WE 1 Word Frequency

ST 1 Hash Functions

15.5 Stacks, Queues, and Priority Queues

Stacks

Queues

Priority Queues

15.6 Stack and Queue Applications

Balancing Parentheses

Evaluating Reverse Polish Expressions

Evaluating Algebraic Expressions

Backtracking WE 2 Simulating a Queue of Waiting Customers

ST 2 Reverse Polish Notation

Appendix A The Basic Latin and Latin-1 Subsets Of Unicode A-1

Appendix B Java Operator Summary A-5

Appendix C Java Reserved Word Summary A-7

Appendix D The Java Library A-9

Appendix E Java Language Coding Guidelines A-29

Appendix F Tool Summary

Appendix G Number Systems

Appendix H UML Summary

Appendix I Java Syntax Summary

Appendix J HTML Summary

Glossary G-1

Index I-1

Credits C-1