Detailed Contents

preface

chapter 1 Introduction

	1.1	What Is computer science? 1
			Foundations
			Systems
			Applications
			Methods
	1.2	What Is a software system? 5
		1.2.1	Dealing with complexity: composition and abstraction
			Composition
			Abstraction
		1.2.2	Two aspects of a system: data and functionality
	1.3	Object-oriented systems 11
	1.4	A model of a computer system 13
			Input/output
			Processor
			Memory
			File system
			Network
	1.5	Software tools 17
			Operating systems
			Programming languages
			Editors
			Translators
	1.6	Errors in the programming process 20
	1.7	Summary 22
		Exercises 23
		Glossary 24

chapter 2 Data abstraction: introductory concepts

	2.1	Values and types 27
	2.2	Primitive types in Java 28
	2.3	Objects 30
		2.3.1	Queries and properties
		2.3.2	Commands and state
		2.3.3	Designing with objects
		2.3.4	Some additional examples
		2.3.5	Objects denoting composite values: immutable objects
		2.3.6	Some cautions
	2.4	Classes 39
	2.5	Objects as properties of objects 40
	2.6	Summary 43
		Exercises 44
		Glossary 46

chapter 3 Basic Java structural components

	3.1	Syntactic structure of a system definition in Java 49
			Packages
			Compilation units
	3.2	Identifiers 52
			Class, package, and compilation unit names
			Guidelines in choosing identifiers
	3.3	Literals 55
	3.4	Lexical structure 57
			Comments
	3.5	Summary 59
		Exercises 59
		Glossary 60

chapter 4 Specification of a simple class

	4.1	Object specification: clients and servers 62
		4.1.1	Client and server
		4.1.2	Specification and implementation
	4.2	Specifying a class 64
		4.2.1	A simple counter
			Specifying a method for a query
			Specifying methods for commands
			Constructors
		4.2.2	Specification documentation
		4.2.3	Invoking a method
		4.2.4	Interaction diagrams
	4.3	A maze game example 72
		4.3.1	Specifying the class
			Queries for class Explorer
			Commands for class Explorer
			A constructor for the class Explorer
		4.3.2	Specifying the class Explorer in Java
		4.3.3	Invoking methods with parameters
		4.3.4	The classDenizen
	4.4	Another example: class Student 85
	4.5	Summary 89
		Exercises 90
		Glossary 91

chapter 5 Implementing a simple class

	5.1	Implementing data descriptions 93
		5.1.1	Instance variables
		5.1.2	Naming values: named constants
	5.2	Implementing functionality 100
		5.2.1	Method implementation: simple queries
		5.2.2	Arithmetic expressions
			Simple expressions
			Operators
			Operator precedence
			Associativity
			Casting
			Concatenation
		5.2.3	Method implementation: simple commands
			Implementing the constructor
		5.2.4	Using parameters
			Implementing the constructor
		5.2.5	Invoking a method: acting as client
		5.2.6	Local variables: another kind of automatic variable
			Local Variable
			Instance Variable
	5.3	Testing an implementation 124
		5.3.1	Getting it started: invoking constructors
	5.3	Summary 128
		Exercises 129
		Glossary 132

chapter 6 Conditions

	6.1	Conditional statements 135
			Postconditions and invariants
		6.1.1	The if-then statement
		6.1.2	The if-then-else statement
		6.1.3	Compound statements
	6.2	Boolean expressions 145
		6.2.1	Relational expressions
			String equality
		6.2.2	Boolean variables and assignment
		6.2.3	Boolean operators
			"and-then" and "or-else" are lazy
			DeMorgan's laws
	6.3	Handling multiple cases 151
		6.3.1	Dangling else
	6.4	Example: a combination lock 156
			A digit by digit lock
	6.5	Summary 169
		Exercises 170
		Glossary 173

chapter 7 Programming by contract

	7.1	Programming by contract 176
		7.1.1	Using preconditions and postconditions
			Preconditions
			Query postconditions
			Command postconditions
			Constructor postconditions
			Preconditions and postconditions are part of the specification
			Named constants
	7.2	Summary 186
		Exercises 186
		Glossary 188

chapter 8 Testing a class

	8.1	Testing 191
	8.2	Testing a class implementation 193
	8.3	Building a test system 195
		8.3.1	Basic input/output classes
		8.3.2	Implementing the test driver
			Specifying the user interface
			Implementing the user interface
			Repeating the actions
			Getting the system started
		8.3.3	Creating a test plan
	8.4	Summary 205
		Exercises 206
		Glossary 206

chapter 9 Relations

	9.1	Relations between objects 209
	9.2	Responsibilities and relations 213
			"Knowing" responsibilities
			"Doing" responsibilities and the uses relation
			Creation responsibilities
	9.3	Implementing relations: object composition and arguments 213
			Object composition
			One-to-many and many-to-many relations
			Establishing the relation
			Uses implemented with an argument
	9.4	Aggregation 220
	9.5	Hierarchical abstraction 223
	9.6	Summary 225
		Exercises 226
		Glossary 227

chapter 10 Putting together a complete system

	10.1	Software life cycle 229
	10.2	Fundamental subsystems 231
			External interface
			Data management
			Model
	10.3	Design of a system 233
		10.3.1	System functionality
		10.3.2	Preliminary design
			Basic subsystems
			Identifying objects
			Determining responsibilities
		10.3.3	Relations between objects
		10.3.4	Integrating the user interface and the model
		10.3.5	Object specification
			Pile specifications
			Player specification
			GameManager specification
			UserInterface specification
	10.4	Implementation of the system 250
		10.4.1	The top level
		10.4.2	The model
			Pile implementation
			Player implementation
			GameManager implementation
		10.4.3	User interface implementation
	10.5	Summary 261
		Exercises 265
		Glossary 266

chapter 11 Software quality

	11.1	External qualities 269
	11.2	Complexity 272
	11.3	Modularity 272
	11.4	Three principles 274
	11.5	What is a software system, revisited
		11.5.1	Software = a temporary solution to an evolving problem
		11.5.2	Software = data + algorithms
		11.5.3	Software = English document and a mathematical document
	11.6	Summary 278
		Exercises 279
		Glossary 280

chapter 12 Lists and iteration

	12.1	Lists 283
	12.2	List specification 284
	12.3	Iteration 288
		12.3.1 while statement
		12.3.2 while loops and lists
	12.4	Examples 291
		12.4.1	Summing items on a list.
		12.4.2	Summing selected elements of a list.
		12.4.3	Finding the minimum
		12.4.4	Determining if an object is on a List: searching the List
	12.5	What does "equal" mean? 298
			Identity or referential equality
			State equality
		12.5.1	Removing duplicates.
	12.6	Loop structure: a summary 304
	12.7	for statement 305
	12.8	Summary 306
		Exercises 307
		Glossary 311

chapter 13 Sorting and searching

	13.1	Ordering lists 314
	13.2	Simple sorts 315
		13.2.1	Selection sort
		13.2.2	Analysis.
		13.2.3	Bubble sort
	13.3	Binary search 327
		13.3.1	Completing the search
		13.3.2	Sequential search and binary search
	13.4	Verifying correctness: using a loop invariant 332
			Preliminaries
			The key invariant
			Partial correctness
			Loop termination
	13.5	Summary 338
		Exercises 338
		Glossary 340

chapter 14 Abstraction and inheritance

	14.1	Abstraction 343
	14.2	Extension and inheritance 345
		14.2.1	Generalization and subtyping
		14.2.2	Abstract classes and abstract methods
		14.2.3	Constructors and subclasses
	14.3	Overriding and polymorphism 354
			Method overloading
	14.4	Subclasses and contracts 359
	14.5	Using inheritance 361
			Identifying common functionality among a collection of classes
			Providing an alternative implementation for a method
			Refining the implementation of a method
			Extending functionality of an existing class
	14.6	Feature accessibility 365
			Accessibility is a static issue
			Feature accessibility is limited by class accessibility
		14.6.1	Protected features
		14.6.2	Restricted features
	14.7	Java scoping rules 373
	14.8	Summary 377
		Exercises 378
		Glossary 383

chapter 15 Modeling with abstraction

	15.1	Abstract classes and interfaces 385
		15.1.1	Abstract classes
		15.1.2	Interfaces
			Interface definition
			Interface implementation
			Extending interfaces
			Multiple inheritance
			Reference-to-interface types
		15.1.3	Interfaces vs. abstract classes
			Interfaces, abstract classes, and modification
			Interfaces and the software life-cycle
		15.1.4	An example
	15.2	Extension and composition 394
			Inheritance, composition, and reuse
			Inheritance, composition, and modifying functionality
	15.3	Extension and state 400
			State as an object
	15.4	Summary 403
		Exercises 403
		Glossary 406

chapter 16 Organizing Lists

	16.1	Using abstraction to organize lists 407
		16.1.1	Generalizing sort
			Anonymous classes
			Interface Sorter
	16.2	Ordered lists 417
			Qualified invariant
	16.3	Summary 419
		Exercises 420
		Glossary 420

chapter 17 Recursion

	17.1	Recursion and iteration 421
		17.1.1	Iteration
			Essential design of a recursive algorithm
		17.1.2	Recursion
	17.2	Example: the towers puzzle 431
	17.3	Quick sort 438
	17.4	An inefficient algorithm 446
	17.5	Indirect recursion 447
	17.6	Object recursion 450
	17.7	Summary 457
		Exercises 457
		Glossary 458

chapter 18 Failures and exceptions

	18.1	Failures 459
	18.2	The Java exception mechanism 460
		18.2.1	Exceptions as objects
		18.2.2	Catching exceptions
		18.2.3	Propagated exceptions.
		18.2.4	Checked and unchecked exceptions.
	18.3	Dealing with failure: using exceptions 467
		18.3.1	Dealing with exceptions
		18.3.2	Application defined exceptions.
		18.3.3	Dealing with logical errors.
	18.4	Summary 476
		Exercises 477
		Glossary477

chapter 19 Building the user interface

	19.1	The system interface 480
		19.1.1	Algorithm-driven interfaces
		19.1.2	Event-driven interfaces
	19.2	An introduction to Swing 484
		19.2.1	Components:
			Some component attributes
		19.2.2	Containers
			Top-level containers
			Heavyweight components and component peers
	19.3	Creating components 492
		19.3.1	The top-level frame
		19.3.2	Adding components: layout
			Container validity
	19.4	Events: programming the user interface 499
		19.4.1	An example:
			Adding an ActionListener
			Adding a WindowListener
	19.5	Some class features 509
		19.5.1	Component
		19.5.2	Container
		19.5.3	Window
		19.5.4	Frame
		19.5.5	JComponent
		19.5.6	JFrame
	19.6	Summary 516
		Exercises 517
		Glossary 520

chapter 20 Designing the GUI front-end: the Model-View-Controller pattern

	20.1	Model-View-Controller 523
	20.2	Implementing MVC in Java 525
		20.2.1	The model.
		20.2.2	The class Observable and interface Observer
		20.2.3	An Observer
		20.2.4	A simple view and controller
			The View
			The Controller
			View layout
		20.2.5	A graphic view.
		20.2.6	A logger as a view
	20.3	The MVC pattern and Swing components 544
			The model
			The UI delegate
	20.4	Summary 550
		Exercises 551
		Glossary 552

chapter 21 Computational complexity

	21.1	Measuring program efficiency 553
	21.2	Time complexity for a method 554
	21.3	Comparing method costs 555
	21.4	Complexity classes. 557
		21.4.1	Complexity of a problem.
		21.4.2	Determining the complexity of a method.
			An example containing a loop
			An example containing nested loops
	21.5	An example: three methods 563
		21.5.1	A naive method.
		21.5.2	A recursive method
		21.5.3	An iterative method
	21.6	Summary 572
		Exercises 573
		Glossary 573

chapter 22 Implementing lists: array implementations

	22.1	Arrays 575
			Defining arrays
			Accessing array components
	22.2	An array-based list implementation 580
		22.2.1	The method copy
			Java interface Cloneable
			Abstract constructor
		22.2.2	Advantages and limitations of an array implementation
	22.3	Dynamic arrays 591
	22.4	Summary 594
		Exercises 597
		Glossary 599

chapter 23 Implementing lists: linked implementations

	23.1	A linked List implementation 601
		23.1.1	Implementing LinkedList methods
	23.2	Linked list variations 610
			Header nodes
			Circular lists
	23.3	Doubly-linked lists 613
	23.4	Limitations of linked structures 616
	23.5	Dynamic storage allocation 617
	23.6	Summary 618
		Exercises 619
		Glossary 621

chapter 24 Organizing list implementations

	24.1	A library structure 623
			Specifying the implementation
	24.2	Iterators 626
		24.2.1	Iterator classes
		24.2.2	Creating an iterator
	24.3	List methods with iterators as arguments 637
		24.3.1	Improving LinkedListIterator
		24.3.2	Iterator extensions
		24.3.3	Iterators and list modification
		24.3.4	Internal or passive iterators
	24.4	Comparing implementations 645
	24.5	The java.util Collection hierarchy 646
			Iterators
	24.6	Summary 649
		Exercises 650
		Glossary 651

chapter 25 Dispensers and dictionaries

	25.1	Dispensers 653
	25.2	Stacks 655
		25.2.1	Stack implementations
	25.3	Queues 660
		25.3.1	Queue implementations
			Linked implementations
			Circular arrays
	25.4	Priority queues 664
		25.4.1	PriorityQueue implementations
	25.5	Dictionaries 668
	25.6	Summary 671
		Exercises 673
		Glossary 674

appendix a Stream i/o

	a.1	OOJ library classes 676
			BasicFileReader
			BasicFileWriter
	a.2	The java.io library 679
		a.2.1	Input byte streams
			Abstract class InputStream
			Class FileInputStream
			Class FilterInputStream
		a.2.2	Input character streams
			Abstract class Reader
			Class BufferedReader
			Class InputStreamReader
			Class FileReader
			Class StreamTokenizer
		a.2.3	Output byte streams
		a.2.4	Output character streams
			Class PrintWriter
			System constants

appendix b Applets

	b.1	Applets 691
		b.1.1	The class JApplet
		b.1.2	Applets as applications
		b.1.3	An example: a simple clock
		b.1.4	An example: an animated box

appendix c Java syntactic summary

	c.1	Lexical structures 705
	c.2	Names 708
	c.3	Types 708
	c.4	Packages 709
	c.5	Classes 710
	c.6	Interfaces 717
	c.7	Methods 718
	c.8	Constructors 719
	c.9	Variables 720
	c.10	Statements 722
	c.11	Expressions 734

references

index