Brief Java

Preface v

Special Features xxvi

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

HT 1 Describing an Algorithm with Pseudocode 18

WE 1 Writing an Algorithm for Tiling a Floor 20

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

ST 1 Variable Type Inference 33

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

ST 2 Testing Classes in an Interactive Environment 45

WE 1 How Many Days Have You Been Alive? 46

WE 2 Working with Pictures 46

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

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

HT 1 Implementing a Class 78

WE 1 Making a Simple Menu 81

3.4 Unit Testing 81

3.5 PROBLEM SOLVING Tracing Objects 84

3.6 Local Variables 86

3.7 The this Reference 88

ST 1 Calling One Constructor from Another 90

3.8 Shape Classes 90

HT 2 Drawing Graphical Shapes 94

Fundamental Data Types 99

4.1 Numbers 100

Number Types 100

Constants 102

ST 1 Big Numbers 106

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

ST 2 Avoiding Negative Remainders 112

ST 3 Combining Assignment and Arithmetic 113

ST 4 Instance Methods and Static Methods 113

4.3 Input and Output 114

Reading Input 114

Formatted Output 115

HT 1 Carrying Out Computations 118

WE 1 Computing the Volume and Surface Area of a Pyramid 121

4.4 PROBLEM SOLVING First Do it By Hand 121

WE 2 Computing Travel Time 122

4.5 Strings 122

The String Type 122

Concatenation 123

String Input 124

Escape Sequences 124

Strings and Characters 124

Substrings 125

ST 5 Using Dialog Boxes for Input and Output 128

Decisions 131

5.1 The if Statement 132

ST 1 The Conditional Operator 137

5.2 Comparing Values 137

Relational Operators 138

Comparing Floating-Point Numbers 139

Comparing Strings 140

Comparing Objects 141

Testing for null 141

HT 1 Implementing an if Statement 143

WE 1 Extracting the Middle 146

5.3 Multiple Alternatives 146

ST 2 The switch Statement 148

5.4 Nested Branches 149

ST 3 Block Scope 154

ST 4 Enumeration Types 155

5.5 PROBLEM SOLVING Flowcharts 156

5.6 PROBLEM SOLVING Selecting Test Cases 159

ST 5 Logging 161

5.7 Boolean Variables and Operators 161

ST 6 Short-Circuit Evaluation of Boolean Operators 165

ST 7 De Morgan’s Law 165

5.8 APPLICATION Input Validation 166

Loops 171

6.1 The while Loop 172

6.2 PROBLEM SOLVING Hand-Tracing 179

6.3 The for Loop 183

ST 1 Variables Declared in a for Loop Header 189

6.4 The do Loop 190

6.5 APPLICATION Processing Sentinel Values 192

ST 2 Redirection of Input and Output 194

ST 3 The “Loop and a Half” Problem 194

ST 4 The break and continue Statements 195

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

HT 1 Writing a Loop 203

WE 1 Credit Card Processing 206

6.8 Nested Loops 206

WE 2 Manipulating the Pixels in an Image 209

6.9 APPLICATION Random Numbers and Simulations 209

Generating Random Numbers 210

The Monte Carlo Method 211

6.10 Using a Debugger 213

HT 2 Debugging 215

WE 3 A Sample Debugging Session 217

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

ST 1 Methods with a Variable Number of 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

ST 2 Sorting with the Java Library 240

7.4 PROBLEM SOLVING Adapting Algorithms 240

HT 1 Working with Arrays 242

WE 1 Rolling the Dice 245

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

WE 2 A World Population Table 253

ST 3 Two-Dimensional Arrays with Variable Row Lengths 254

ST 4 Multidimensional Arrays 255

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

ST 5 The Diamond Syntax 264

7.8 Regression Testing 264

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

ST 1 Call by Value and Call by Reference 278

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

ST 2 Alternative Forms of Instance and Static Variable Initialization 289

ST 3 Static Imports 290

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

ST 4 Package Access 298

HT 1 Programming with Packages 299

8.7 Unit Test Frameworks 300

Inheritance 305

9.1 Inheritance Hierarchies 306

9.2 Implementing Subclasses 310

9.3 Overriding Methods 314

ST 1 Calling the Superclass Constructor 318

9.4 Polymorphism 319

ST 2 Dynamic Method Lookup and the Implicit Parameter 322

ST 3 Abstract Classes 323

ST 4 Final Methods and Classes 324

ST 5 Protected Access 324

HT 1 Developing an Inheritance Hierarchy 325

WE 1 Implementing an Employee Hierarchy for Payroll Processing 330

9.5 Object: The Cosmic Superclass 330

Overriding the toString Method 330

The equals Method 332

The instanceof Operator 333

ST 6 Inheritance and the toString Method 335

ST 7 Inheritance and the equals Method 336

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

ST 1 Constants in Interfaces 346

ST 2 Nonabstract Interface Methods 347

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

WE 1 Investigating Number Sequences 350

10.3 The Comparable Interface 350

ST 3 The clone Method and the Cloneable Interface 352

10.4 Using Interfaces for Callbacks 355

ST 4 Lambda Expressions 358

ST 5 Generic Interface Types 360

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

ST 6 Keyboard Events 377

ST 7 Event Adapters 378

Input/Output and Exception Handling 383

11.1 Reading and Writing Text Files 384

ST 1 Reading Web Pages 387

ST 2 File Dialog Boxes 387

ST 3 Character Encodings 388

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

ST 4 Regular Expressions 395

ST 5 Reading an Entire File 396

11.3 Command Line Arguments 396

HT 1 Processing Text Files 399

WE 1 Analyzing Baby Names 403

11.4 Exception Handling 403

Throwing Exceptions 403

Catching Exceptions 405

Checked Exceptions 407

Closing Resources 409

Designing Your Own Exception Types 410

ST 6 Assertions 411

ST 7 The try/finally Statement 412

11.5 APPLICATION Handling Input Errors 412

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

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

ST 1 Attributes and Methods in UML Diagrams 426

ST 2 Multiplicities 427

ST 3 Aggregation, Association, and Composition 427

12.3 APPLICATION Printing an Invoice 428

Requirements 429

CRC Cards 429

UML Diagrams 432

Method Documentation 432

Implementation 434

WE 1 Simulating an Automatic Teller Machine 439

RECURSION*(ETEXT ONLY) 443

13.1 Triangle Numbers 444

HT 1 Thinking Recursively 448

WE 1 Finding Files 452

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

WE 2 Towers of Hanoi 475

SORTING AND SEARCHING*(ETEXT ONLY) 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

ST 1 Oh, Omega, and Theta 486

ST 2 Insertion Sort 487

14.4 Merge Sort 488

14.5 Analyzing the Merge Sort Algorithm 491

ST 3 The Quicksort Algorithm 493

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

ST 4 The Comparator Interface 506

ST 5 Comparators with Lambda Expressions 507

WE 1 Enhancing the Insertion Sort Algorithm 507

The Java Collections Framework*(ETEXT ONLY) 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

ST 1 Updating Map Entries 527

HT 1 Choosing a Collection 527

WE 1 Word Frequency 528

ST 2 Hash Functions 529

15.5 Stacks, Queues, and Priority Queues 531

Stacks 531

Queues 532

Priority Queues 533

15.6 Stack and Queue Applications 534

Balancing Parentheses 534

Evaluating Reverse Polish Expressions 535

Evaluating Algebraic Expressions 537

Backtracking 540

ST 3 Reverse Polish Notation 542

WE 2 Simulating a Queue of Waiting Customers 543

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 (ETEXT ONLY)

Appendix G Number Systems (ETEXT ONLY)

Appendix H UML Summary (ETEXT ONLY)

Appendix I Java Syntax Summary (ETEXT ONLY)

Appendix J Html Summary (ETEXT ONLY)

Glossary G-1

Index I-1

Credits C-1

Quick Reference C-3