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 533 15.6 Stack and Queue Applications 534 Balancing Parentheses 534 Evaluating Reverse Polish Expressions 535 Evaluating Algebraic Expressions 537 Backtracking 540 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 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 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 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 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 18.5 Type Erasure 639 19 Stream Processing 645 19.1 The Stream Concept 646 19.2 Producing Streams 648 19.3 Collecting Results 649 19.4 Transforming Streams 652 19.5 Lambda Expressions 654 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 20 Graphical User Interfaces 675 20.1 Layout Management 676 Using Layout Managers 676 Achieving Complex Layouts 677 Using Inheritance to Customize Frames 678 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 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 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 22.2 Terminating Threads 22.3 Race Conditions 22.4 Synchronizing Object Access 22.5 Avoiding Deadlocks 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 23.5 URL Connections 24 Relational Databases* (Etext Only) 24.1 Organizing Database Information Database Tables Linking Tables Implementing Multi-Valued Relationships 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 25 XML* (Etext Only) 25.1 XML Tags and Documents Advantages of XML Differences Between XML and HTML The Structure of an XML Document 25.2 Parsing XML Documents 25.3 Creating XML Documents 25.4 Validating XML Documents Document Type Definitions Specifying a DTD in an XML Document Parsing and Validation 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