Big Java

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

HT 1 Describing an Algorithm with Pseudocode 18

WE 1 Writing an Algorithm for Tiling a Floor 20

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

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

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

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

4 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

5 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

6 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

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

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

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

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

9 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

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

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

11 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

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

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

13 Recursion 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

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

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

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

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

16 Basic Data Structures 545

16.1 Implementing Linked Lists 546

The Node Class 546

Adding and Removing the First Element 547

The Iterator Class 548

Advancing an Iterator 549

Removing an Element 550

Adding an Element 552

Setting an Element to a Different Value 553

Efficiency of Linked List Operations 553

ST 1 Static Classes 560

WE 1 Implementing a Doubly-Linked List 560

16.2 Implementing Array Lists 560

Getting and Setting Elements 560

Removing or Adding Elements 562

Growing the Internal Array 563

16.3 Implementing Stacks and Queues 564

Stacks as Linked Lists 565

Stacks as Arrays 566

Queues as Linked Lists 567

Queues as Circular Arrays 568

16.4 Implementing a Hash Table 570

Hash Codes 570

Hash Tables 570

Finding an Element 572

Adding and Removing Elements 572

Iterating over a Hash Table 573

ST 2 Open Addressing 578

17 Tree Structures 581

17.1 Basic Tree Concepts 582

17.2 Binary Trees 585

Binary Tree Examples 586

Balanced Trees 588

A Binary Tree Implementation 589

WE 1 Building a Huffman Tree 590

17.3 Binary Search Trees 590

The Binary Search Property 591

Insertion 592

Removal 594

Efficiency of the Operations 595

17.4 Tree Traversal 599

Inorder Traversal 599

Preorder and Postorder Traversals 601

The Visitor Pattern 602

Depth-First and Breadth-First Search 603

Tree Iterators 604

17.5 Red-Black Trees 605

Basic Properties of Red-Black Trees 605

Insertion 607

Removal 608

WE 2 Implementing a Red-Black Tree 611

17.6 Heaps 612

17.7 The Heapsort Algorithm 622

18 Generic Classes 629

18.1 Generic Classes and Type Parameters 630

18.2 Implementing Generic Types 631

18.3 Generic Methods 634

18.4 Constraining Type Parameters 636

ST 1 Wildcard Types 638

18.5 Type Erasure 639

ST 2 Reflection 642

WE 1 Making a Generic Binary Search Tree Class 643

19 Stream Processing 645

19.1 The Stream Concept 646

19.2 Producing Streams 648

19.3 Collecting Results 649

ST 1 Infinite Streams 651

19.4 Transforming Streams 652

19.5 Lambda Expressions 654

ST 2 Method and Constructor References 656

ST 3 Higher-Order Functions 657

ST 4 Higher-Order Functions and Comparators 658

19.6 The Optional Type 659

19.7 Other Terminal Operations 661

19.8 Primitive-Type Streams 663

Creating Primitive-Type Streams 663

Mapping a Primitive-Type Stream 663

Processing Primitive-Type Streams 664

19.9 Grouping Results 665

19.10 Common Algorithms Revisited 667

Filling 667

Sum, Average, Maximum, and Minimum 668

Counting Matches 668

Element Separators 668

Linear Search 669

Comparing Adjacent Values 669

HT 1 Working with Streams 670

WE 1 Word Properties 672

WE 2 A Movie Database 673

20 Graphical User Interfaces 675

20.1 Layout Management 676

Using Layout Managers 676

Achieving Complex Layouts 677

Using Inheritance to Customize Frames 678

ST 1 Adding the main Method to the Frame Class 679

20.2 Processing Text Input 680

Text Fields 680

Text Areas 682

20.3 Choices 685

Radio Buttons 685

Check Boxes 687

Combo Boxes 687

HT 1 Laying Out a User Interface 692

WE 1 Programming a Working Calculator 694

20.4 Menus 695

20.5 Exploring the Swing Documentation 702

21 Advanced Input/Output*(Etext Only)

21.1 Readers, Writers, and Input/Output Streams

21.2 Binary Input and Output

21.3 Random Access

21.4 Object Input and Output Streams

HT 1 Choosing a File Format

21.5 File and Directory Operations

Paths

Creating and Deleting Files and Directories

Useful File Operations

Visiting Directories

22 Multithreading*(Etext Only)

22.1 Running Threads

ST 1 Thread Pools

22.2 Terminating Threads

22.3 Race Conditions

22.4 Synchronizing Object Access

22.5 Avoiding Deadlocks

ST 2 Object Locks and Synchronized Methods

ST 3 The Java Memory Model

22.6 APPLICATION Algorithm Animation

23 Internet Networking*(Etext Only)

23.1 The Internet Protocol

23.2 Application Level Protocols

23.3 A Client Program

23.4 A Server Program

HT 1 Designing Client/Server Programs

23.5 URL Connections

24 Relational Databases*(Etext Only)

24.1 Organizing Database Information

Database Tables

Linking Tables

Implementing Multi-Valued Relationships

ST 1 Primary Keys and Indexes

24.2 Queries

Simple Queries

Selecting Columns

Selecting Subsets

Calculations

Joins

Updating and Deleting Data

24.3 Installing a Database

24.4 Database Programming in Java

Connecting to the Database

Executing SQL Statements

Analyzing Query Results

Result Set Metadata

24.5 APPLICATION Entering an Invoice

ST 2 Transactions

ST 3 Object-Relational Mapping

WE 1 Programming a Bank Database

25 XML* (Etext Only)

25.1 XML Tags and Documents

Advantages of XML

Differences Between XML and HTML

The Structure of an XML Document

HT 1 Designing an XML Document Format

25.2 Parsing XML Documents

25.3 Creating XML Documents

HT 2 Writing an XML Document

ST 1 Grammars, Parsers, and Compilers

25.4 Validating XML Documents

Document Type Definitions

Specifying a DTD in an XML Document

Parsing and Validation

HT 3 Writing a DTD

ST 2 Schema Languages

ST 3 Other XML Technologies

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-38

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