Java Structures Data Structures in Java for the Principled Programmer

Java Structures......Page 1 Copyright (c) 2005-2007 Duane A. Bailey......Page 2 Table of Contents......Page 3 Preface to First Edition......Page 11 Preface to the Second Edition......Page 13 Preface to the ``Root 7'' Edition......Page 15 0.1 Read Me......Page 17 0.2 He Can't Say That, Can He?......Page 18 1 The Object-Oriented Method......Page 21 1.1 Data Abstraction and Encapsulation......Page 22 1.2 The Object Model......Page 23 1.3 Object-Oriented Terminology......Page 24 1.4 A Special-Purpose Class: A Bank Account......Page 27 1.5 A General-Purpose Class: An Association......Page 30 1.6 Sketching an Example: A Word List......Page 34 1.7 Sketching an Example: A Rectangle Class......Page 36 1.8 Interfaces......Page 38 1.9 Who Is the User?......Page 40 1.10 Conclusions......Page 41 1.11 Laboratory: The Day of the Week Calculator......Page 45 2 Comments, Conditions, and Assertions......Page 49 2.2 Assertions......Page 50 2.3 Craftsmanship......Page 52 2.4 Conclusions......Page 53 2.5 Laboratory: Using Javadoc Commenting......Page 55 3 Vectors......Page 59 3.1 The Interface......Page 61 3.2 Example: The Word List Revisited......Page 63 3.3 Example: Word Frequency......Page 64 3.4 The Implementation......Page 66 3.5 Extensibility: A Feature......Page 69 3.6 Example: L-Systems......Page 72 3.7 Example: Vector-Based Sets......Page 73 3.8 Example: The Matrix Class......Page 76 3.9 Conclusions......Page 80 3.10 Laboratory: The Silver Dollar Game......Page 83 4 Generics......Page 85 4.1 Motivation (in case we need some)......Page 86 4.1.1 Possible Solution: Specialization......Page 87 4.2.1 Generic Associations......Page 88 4.2.2 Parameterizing the Vector Class......Page 90 4.2.3 Restricting Parameters......Page 95 4.3 Conclusions......Page 96 5.1 Asymptotic Analysis Tools......Page 97 5.1.1 Time and Space Complexity......Page 98 5.1.2 Examples......Page 101 5.1.3 The Trading of Time and Space......Page 107 5.1.4 Back-of-the-Envelope Estimations......Page 108 5.2.1 Recursion......Page 110 5.2.2 Mathematical Induction......Page 117 5.3.1 Symmetry......Page 124 5.4 Conclusions......Page 126 5.5 Laboratory: How Fast Is Java?......Page 131 6.1 Approaching the Problem......Page 135 6.2 Selection Sort......Page 138 6.3 Insertion Sort......Page 141 6.4 Mergesort......Page 143 6.5 Quicksort......Page 147 6.6 Radix Sort......Page 150 6.7 Sorting Objects......Page 154 6.8 Ordering Objects Using Comparators......Page 156 6.9 Vector-Based Sorting......Page 159 6.10 Conclusions......Page 160 6.11 Laboratory: Sorting with Comparators......Page 163 7.1 The Interface-Based Approach......Page 165 7.1.1 Design of the Interface......Page 166 7.1.2 Development of an Abstract Implementation......Page 167 7.2 Example: Development of Generators......Page 168 7.3 Example: Playing Cards......Page 171 7.4 Conclusions......Page 176 8.1 Java's Enumeration Interface......Page 177 8.2 The Iterator Interface......Page 179 8.3 Example: Vector Iterators......Page 181 8.4 Example: Rethinking Generators......Page 183 8.5 Example: Filtering Iterators......Page 186 8.6 Conclusions......Page 188 8.7 Laboratory: The Two-Towers Problem......Page 191 9 Lists......Page 195 9.1 Example: A Unique Program......Page 198 9.2 Example: Free Lists......Page 199 9.3 Partial Implementation: Abstract Lists......Page 202 9.4 Implementation: Singly Linked Lists......Page 204 9.5 Implementation: Doubly Linked Lists......Page 217 9.6 Implementation: Circularly Linked Lists......Page 222 9.8 List Iterators......Page 225 9.9 Conclusions......Page 227 9.10 Laboratory: Lists with Dummy Nodes......Page 231 10 Linear Structures......Page 235 10.1 Stacks......Page 237 10.1.1 Example: Simulating Recursion......Page 238 10.1.2 Vector-Based Stacks......Page 241 10.1.3 List-Based Stacks......Page 243 10.1.4 Comparisons......Page 244 10.2 Queues......Page 245 10.2.1 Example: Solving a Coin Puzzle......Page 247 10.2.2 List-Based Queues......Page 250 10.2.3 Vector-Based Queues......Page 251 10.2.4 Array-Based Queues......Page 254 10.3 Example: Solving Mazes......Page 258 10.4 Conclusions......Page 260 10.5 Laboratory: A Stack-Based Language......Page 263 10.6 Laboratory: The Web Crawler......Page 267 11.1 Comparable Objects Revisited......Page 269 11.1.1 Example: Comparable Ratios......Page 270 11.1.2 Example: Comparable Associations......Page 272 11.2.1 The OrderedStructure Interface......Page 274 11.2.2 The Ordered Vector and Binary Search......Page 275 11.2.3 Example: Sorting Revisited......Page 280 11.2.4 A Comparator-based Approach......Page 281 11.2.5 The Ordered List......Page 283 11.2.6 Example: The Modified Parking Lot......Page 286 11.3 Conclusions......Page 288 11.4 Laboratory: Computing the ``Best Of''......Page 291 12.1 Terminology......Page 293 12.2 Example: Pedigree Charts......Page 296 12.3 Example: Expression Trees......Page 297 12.4 Implementation......Page 298 12.4.1 The BinaryTree Implementation......Page 300 12.5 Example: An Expert System......Page 303 12.6 Traversals of Binary Trees......Page 306 12.6.1 Preorder Traversal......Page 307 12.6.2 In-order Traversal......Page 309 12.6.3 Postorder Traversal......Page 311 12.6.4 Level-order Traversal......Page 312 12.6.5 Recursion in Iterators......Page 313 12.7 Property-Based Methods......Page 315 12.8 Example: Huffman Compression......Page 319 12.9 Example Implementation: Ahnentafel......Page 323 12.10 Conclusions......Page 325 12.11 Laboratory: Playing Gardner's Hex-a-Pawn......Page 329 13.1 The Interface......Page 331 13.2 Example: Improving the Huffman Code......Page 333 13.3 A Vector-Based Implementation......Page 334 13.4 A Heap Implementation......Page 335 13.4.1 Vector-Based Heaps......Page 336 13.4.2 Example: Heapsort......Page 342 13.4.3 Skew Heaps......Page 345 13.5 Example: Circuit Simulation......Page 349 13.6 Conclusions......Page 353 13.7 Laboratory: Simulating Business......Page 357 14.1 Binary Search Trees......Page 359 14.3 Example: Associative Structures......Page 361 14.4 Implementation......Page 364 14.5 Splay Trees......Page 370 14.6 Splay Tree Implementation......Page 373 14.7 An Alternative: Red-Black Trees......Page 377 14.8 Conclusions......Page 379 14.9 Laboratory: Improving the BinarySearchTree......Page 383 15.1 Example Revisited: The Symbol Table......Page 385 15.2 The Interface......Page 386 15.3 Simple Implementation: MapList......Page 388 15.4 Constant Time Maps: Hash Tables......Page 390 15.4.1 Open Addressing......Page 391 15.4.2 External Chaining......Page 399 15.4.3 Generation of Hash Codes......Page 401 15.4.4 Hash Codes for Collection Classes......Page 407 15.5 Ordered Maps and Tables......Page 408 15.6 Example: Document Indexing......Page 411 15.7 Conclusions......Page 414 15.8 Laboratory: The Soundex Name Lookup System......Page 417 16.1 Terminology......Page 419 16.2 The Graph Interface......Page 420 16.3.1 Abstract Classes Reemphasized......Page 424 16.3.2 Adjacency Matrices......Page 426 16.3.3 Adjacency Lists......Page 432 16.4.1 Reachability......Page 438 16.4.2 Topological Sorting......Page 440 16.4.3 Transitive Closure......Page 443 16.4.4 All Pairs Minimum Distance......Page 444 16.4.5 Greedy Algorithms......Page 445 16.5 Conclusions......Page 450 16.6 Laboratory: Converting Between Units......Page 455 A.1 Solutions to Self Check Problems......Page 457 A.2 Solutions to Odd-Numbered Problems......Page 467 B.1 A First Program......Page 505 B.2.1 Primitive Types......Page 507 B.2.2 Reference Types......Page 509 B.3.1 The structure.ReadStream Class......Page 510 B.3.2 The java.util.Scanner Class......Page 511 B.3.3 The PrintStream Class......Page 512 B.3.4 Strings......Page 513 B.4.1 Conditional Statements......Page 514 B.4.2 Loops......Page 515 B.6.1 Inheritance......Page 518 B.6.2 Subtyping......Page 519 B.6.3 Interfaces and Abstract Classes......Page 520 B.7 Use of the Assert Command......Page 522 B.8 Use of the Keyword Protected......Page 523 C.2 Parallel Features......Page 527 C.3 Conversion......Page 528 D.1 Structure Package Hierarchy......Page 529 D.2 Principles......Page 531 Index......Page 533 Colophon......Page 542 Java-based data structures Java Structures 1 Copyright (c) 2005-2007 Duane A. Bailey 2 Table of Contents 3 Preface to First Edition 11 Preface to the Second Edition 13 Preface to the ``Root 7'' Edition 15 0 Introduction 17 0.1 Read Me 17 0.2 He Can't Say That, Can He? 18 1 The Object-Oriented Method 21 1.1 Data Abstraction and Encapsulation 22 1.2 The Object Model 23 1.3 Object-Oriented Terminology 24 1.4 A Special-Purpose Class: A Bank Account 27 1.5 A General-Purpose Class: An Association 30 1.6 Sketching an Example: A Word List 34 1.7 Sketching an Example: A Rectangle Class 36 1.8 Interfaces 38 1.9 Who Is the User? 40 1.10 Conclusions 41 1.11 Laboratory: The Day of the Week Calculator 45 2 Comments, Conditions, and Assertions 49 2.1 Pre- and Postconditions 50 2.2 Assertions 50 2.3 Craftsmanship 52 2.4 Conclusions 53 2.5 Laboratory: Using Javadoc Commenting 55 3 Vectors 59 3.1 The Interface 61 3.2 Example: The Word List Revisited 63 3.3 Example: Word Frequency 64 3.4 The Implementation 66 3.5 Extensibility: A Feature 69 3.6 Example: L-Systems 72 3.7 Example: Vector-Based Sets 73 3.8 Example: The Matrix Class 76 3.9 Conclusions 80 3.10 Laboratory: The Silver Dollar Game 83 4 Generics 85 4.1 Motivation (in case we need some) 86 4.1.1 Possible Solution: Specialization 87 4.2 Implementing Generic Container Classes 88 4.2.1 Generic Associations 88 4.2.2 Parameterizing the Vector Class 90 4.2.3 Restricting Parameters 95 4.3 Conclusions 96 5 Design Fundamentals 97 5.1 Asymptotic Analysis Tools 97 5.1.1 Time and Space Complexity 98 5.1.2 Examples 101 5.1.3 The Trading of Time and Space 107 5.1.4 Back-of-the-Envelope Estimations 108 5.2 Self-Reference 110 5.2.1 Recursion 110 5.2.2 Mathematical Induction 117 5.3 Properties of Design 124 5.3.1 Symmetry 124 5.3.2 Friction 126 5.4 Conclusions 126 5.5 Laboratory: How Fast Is Java? 131 6 Sorting 135 6.1 Approaching the Problem 135 6.2 Selection Sort 138 6.3 Insertion Sort 141 6.4 Mergesort 143 6.5 Quicksort 147 6.6 Radix Sort 150 6.7 Sorting Objects 154 6.8 Ordering Objects Using Comparators 156 6.9 Vector-Based Sorting 159 6.10 Conclusions 160 6.11 Laboratory: Sorting with Comparators 163 7 A Design Method 165 7.1 The Interface-Based Approach 165 7.1.1 Design of the Interface 166 7.1.2 Development of an Abstract Implementation 167 7.1.3 Implementation 168 7.2 Example: Development of Generators 168 7.3 Example: Playing Cards 171 7.4 Conclusions 176 8 Iterators 177 8.1 Java's Enumeration Interface 177 8.2 The Iterator Interface 179 8.3 Example: Vector Iterators 181 8.4 Example: Rethinking Generators 183 8.5 Example: Filtering Iterators 186 8.6 Conclusions 188 8.7 Laboratory: The Two-Towers Problem 191 9 Lists 195 9.1 Example: A Unique Program 198 9.2 Example: Free Lists 199 9.3 Partial Implementation: Abstract Lists 202 9.4 Implementation: Singly Linked Lists 204 9.5 Implementation: Doubly Linked Lists 217 9.6 Implementation: Circularly Linked Lists 222 9.7 Implementation: Vectors 225 9.8 List Iterators 225 9.9 Conclusions 227 9.10 Laboratory: Lists with Dummy Nodes 231 10 Linear Structures 235 10.1 Stacks 237 10.1.1 Example: Simulating Recursion 238 10.1.2 Vector-Based Stacks 241 10.1.3 List-Based Stacks 243 10.1.4 Comparisons 244 10.2 Queues 245 10.2.1 Example: Solving a Coin Puzzle 247 10.2.2 List-Based Queues 250 10.2.3 Vector-Based Queues 251 10.2.4 Array-Based Queues 254 10.3 Example: Solving Mazes 258 10.4 Conclusions 260 10.5 Laboratory: A Stack-Based Language 263 10.6 Laboratory: The Web Crawler 267 11 Ordered Structures 269 11.1 Comparable Objects Revisited 269 11.1.1 Example: Comparable Ratios 270 11.1.2 Example: Comparable Associations 272 11.2 Keeping Structures Ordered 274 11.2.1 The OrderedStructure Interface 274 11.2.2 The Ordered Vector and Binary Search 275 11.2.3 Example: Sorting Revisited 280 11.2.4 A Comparator-based Approach 281 11.2.5 The Ordered List 283 11.2.6 Example: The Modified Parking Lot 286 11.3 Conclusions 288 11.4 Laboratory: Computing the ``Best Of'' 291 12 Binary Trees 293 12.1 Terminology 293 12.2 Example: Pedigree Charts 296 12.3 Example: Expression Trees 297 12.4 Implementation 298 12.4.1 The BinaryTree Implementation 300 12.5 Example: An Expert System 303 12.6 Traversals of Binary Trees 306 12.6.1 Preorder Traversal 307 12.6.2 In-order Traversal 309 12.6.3 Postorder Traversal 311 12.6.4 Level-order Traversal 312 12.6.5 Recursion in Iterators 313 12.7 Property-Based Methods 315 12.8 Example: Huffman Compression 319 12.9 Example Implementation: Ahnentafel 323 12.10 Conclusions 325 12.11 Laboratory: Playing Gardner's Hex-a-Pawn 329 13 Priority Queues 331 13.1 The Interface 331 13.2 Example: Improving the Huffman Code 333 13.3 A Vector-Based Implementation 334 13.4 A Heap Implementation 335 13.4.1 Vector-Based Heaps 336 13.4.2 Example: Heapsort 342 13.4.3 Skew Heaps 345 13.5 Example: Circuit Simulation 349 13.6 Conclusions 353 13.7 Laboratory: Simulating Business 357 14 Search Trees 359 14.1 Binary Search Trees 359 14.2 Example: Tree Sort 361 14.3 Example: Associative Structures 361 14.4 Implementation 364 14.5 Splay Trees 370 14.6 Splay Tree Implementation 373 14.7 An Alternative: Red-Black Trees 377 14.8 Conclusions 379 14.9 Laboratory: Improving the BinarySearchTree 383 15 Maps 385 15.1 Example Revisited: The Symbol Table 385 15.2 The Interface 386 15.3 Simple Implementation: MapList 388 15.4 Constant Time Maps: Hash Tables 390 15.4.1 Open Addressing 391 15.4.2 External Chaining 399 15.4.3 Generation of Hash Codes 401 15.4.4 Hash Codes for Collection Classes 407 15.4.5 Performance Analysis 408 15.5 Ordered Maps and Tables 408 15.6 Example: Document Indexing 411 15.7 Conclusions 414 15.8 Laboratory: The Soundex Name Lookup System 417 16 Graphs 419 16.1 Terminology 419 16.2 The Graph Interface 420 16.3 Implementations 424 16.3.1 Abstract Classes Reemphasized 424 16.3.2 Adjacency Matrices 426 16.3.3 Adjacency Lists 432 16.4 Examples: Common Graph Algorithms 438 16.4.1 Reachability 438 16.4.2 Topological Sorting 440 16.4.3 Transitive Closure 443 16.4.4 All Pairs Minimum Distance 444 16.4.5 Greedy Algorithms 445 16.5 Conclusions 450 16.6 Laboratory: Converting Between Units 455 A Answers 457 A.1 Solutions to Self Check Problems 457 A.2 Solutions to Odd-Numbered Problems 467 B Beginning with Java 505 B.1 A First Program 505 B.2 Declarations 507 B.2.1 Primitive Types 507 B.2.2 Reference Types 509 B.3 Important Classes 510 B.3.1 The structure.ReadStream Class 510 B.3.2 The java.util.Scanner Class 511 B.3.3 The PrintStream Class 512 B.3.4 Strings 513 B.4 Control Constructs 514 B.4.1 Conditional Statements 514 B.4.2 Loops 515 B.5 Methods 518 B.6 Inheritance and Subtyping 518 B.6.1 Inheritance 518 B.6.2 Subtyping 519 B.6.3 Interfaces and Abstract Classes 520 B.7 Use of the Assert Command 522 B.8 Use of the Keyword Protected 523 C Collections 527 C.1 Collection Class Features 527 C.2 Parallel Features 527 C.3 Conversion 528 D Documentation 529 D.1 Structure Package Hierarchy 529 D.2 Principles 531 Index 533 Colophon 542