Data structure programs in java pdf

JAVA Program

DATA STRUCTURES Abstraction and Design

Using Java THIRD EDITION

ELLIOT B. KOFFMAN Temple University

PAUL A. T. WOLFGANG Temple University

Koffman-ffirs.indd 1 11/3/2015 9:04:31 PM

VICE PRESIDENT & DIRECTOR Laurie Rosatone SENIOR DIRECTOR Don Fowley EXECUTIVE EDITOR Brian Gambrel DEVELOPMENT EDITOR Jennifer Lartz ASSISTANT Jessy Moor PROJECT MANAGER Gladys Soto PROJECT SPECIALIST Nichole Urban PROJECT ASSISTANT Anna Melhorn MARKETING MANAGER Dan Sayre ASSISTANT MARKETING MANAGER Puja Katarawala ASSOCIATE DIRECTOR Kevin Holm SENIOR CONTENT SPECIALIST Nicole Repasky PRODUCTION EDITOR Rajeshkumar Nallusamy PHOTO RESEARCHER Amanda Bustard COVER PHOTO CREDIT © Robert Davies/Shutterstock

This book was set in 10/12 pt SabonLTStd-Roman by SPiGlobal and printed and bound by Lightning Source Inc.

Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship.

Copyright © 2016, 2010 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permit- ted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authori- zation through payment of the appropriate per‐copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923 (Web site: www.copyright.com). Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030‐5774, (201) 748‐6011, fax (201) 748‐6008, or online at: www.wiley.com/go/permissions.

Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return shipping label are available at: www.wiley.com/go/ returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative.

ISBN: 978-1-119-23914-7 (PBK) ISBN: 978-1-119-22307-8 (EVALC)

Library of Congress Cataloging-in-Publication Data Koffman, Elliot B. [Objects, abstraction, data structures and design using Java] Data structures : abstraction and design using Java / Elliot B. Koffman, Temple University, Paul A.T. Wolfgang, Temple University. — Third edition. pages cm Original edition published under title: Objects, abstraction, data structures and design using Java. Includes index. ISBN 978-1-119-23914-7 (pbk.) 1. Data structures (Computer science) 2. Java (Computer program language) 3. Object-oriented programming (Computer science) 4. Application program interfaces (Computer software) I. Wolfgang, Paul A. T. II. Title.

QA76.9.D35K58 2016 005.7'3—dc23

2015036861

Printing identification and country of origin will either be included on this page and/or the end of the book. In addition, if the ISBN on this page and the back cover do not match, the ISBN on the back cover should be considered the correct ISBN.

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

Koffman-ffirs.indd 2 11/4/2015 3:00:52 PM

http://www.wiley.com/go/citizenship
http://www.copyright.com
http://www.wiley.com/go/permissions
http://www.wiley.com/goreturnlabel
Preface Our goal in writing this book was to combine a strong emphasis on problem solving and software design with the study of data structures. To this end, we discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (a Java class), we then cover case studies that use the data structure to solve a significant problem. Examples include maintaining an ordered list, evaluating arithmetic expressions using a stack, finding the shortest path through a maze, and Huffman coding using a binary tree and a priority queue. In the implementation of each data structure and in the solutions of the case studies, we reinforce the message “Think, then code” by performing a thorough analysis of the problem and then carefully designing a solution (using pseudo‐ code and UML class diagrams) before the implementation. We also provide a performance analysis when appropriate. Readers gain an understanding of why different data structures are needed, the applications they are suited for, and the advantages and disadvantages of their possible implementations.

Intended Audience This book was written for anyone with a curiosity or need to know about data structures, those essential elements of good programs and reliable software. We hope that the text will be useful to readers with either professional or educational interests.

It is intended as a textbook for the second programming course in a computing curriculum involving the study of data structures, especially one that emphasizes Object‐Oriented Design (OOD). The text could also be used in a more‐advanced course in algorithms and data struc- tures. Besides coverage of the basic data structures and algorithms (lists, stacks, queues, trees, recursion, sorting), there are chapters on sets and maps, balanced binary search trees, graphs, and an online appendix on event‐oriented programming. Although we expect that most read- ers will have completed a first programming course in Java, there is an extensive review chapter (included as an appendix) for those who may have taken a first programming course in a different language, or for those who need a refresher in Java.

Emphasis on the Java Collections Framework The book focuses on the interfaces and classes in the Java Collections Framework. We begin the study of a new data structure by specifying an abstract data type as an interface, which we adapt from the Java API. Readers are encouraged throughout the text to use the Java Collections Framework as a resource for their programming.

Our expectation is that readers who complete this book will be familiar with the data struc- tures available in the Java Collections Framework and will be able to use them in their future programming. However, we also expect that they will want to know how the data structures are implemented, so we provide thorough discussions of classes that implement these data structures. Each class follows the approach taken by the Java designers where appropriate. However, when their industrial‐strength solutions appear to be too complicated for beginners to understand, we have provided simpler implementations but have tried to be faithful to their approach.

Koffman-preface.indd 3 10/20/2015 3:02:35 PM

iv Preface

Think, then Code To help you “Think, then code” we discuss problem solving and introduce appropriate soft- ware design tools throughout the textbook. For example, Chapter 1 focuses on OOD and Class Hierarchies. It introduces the Uniform Modeling Language (also covered in Appendix B) to document an OOD. It introduces the use of interfaces to specify abstract data types and to facilitate contract programming and describes how to document classes using Javadoc‐style comments. There is also coverage of exceptions and exception handling. Chapter 2 intro- duces the Java Collections Framework and focuses on the List interface, and it shows how to use big‐O notation to analyze program efficiency. In Chapter 3, we cover different testing strategies in some detail including a discussion of test‐driven design and the use of the JUnit program to facilitate testing.

Features of the Third Edition We had two major goals for the third edition. The first was to bring the coverage of Java up to Java 8 by introducing new features of Java where appropriate. For example, we use the Java 7 diamond operator when creating new Collection objects. We use the Java 8 StringJoiner in place of the older StringBuilder for joining strings.

A rather significant change was to introduce Java 8 lambda expressions and functional inter- faces as a way to facilitate functional programming in Java in a new Section 6.4. Using these features significantly improved the code.

The second major goal was to provide additional emphasis on testing and debugging. To facilitate this, we moved our discussion of testing and debugging from an appendix to Chapter 3 and expanded our coverage of testing including more discussion of JUnit. We also added a new section that introduced test‐driven development.

A third goal was to ease the transition to Java for Python programmers. When introducing Java data structures (for example, arrays, lists, sets, and maps), we compared them to equiva- lent Python data structures.

Other changes to the text included reorganizing the chapter on lists and moving the discussion of algorithm analysis to the beginning of the chapter so that big‐O notation could be used to compare the efficiency of different List implementations. We also combined the chapters on stacks and queues and increased our emphasis on using Deque as an alternative to the legacy Stack class. We also added a discussion of Timsort, which is used in Java 8, to the chapter on sorting algorithms. Finally, some large case studies and an appendix were moved to online supplements.

Case Studies We illustrate OOD principles in the design and implementation of new data structures and in the solution of approximately 20 case studies. Case studies follow a five‐step process (prob- lem specification, analysis, design, implementation, and testing). As is done in industry, we sometimes perform these steps in an iterative fashion rather than in strict sequence. Several case studies have extensive discussions of testing and include methods that automate the test- ing process. Some case studies are revisited in later chapters, and solutions involving different data structures are compared. We also provide additional case studies on the Web site for the textbook (www.wiley.com/college/koffman), including one that illustrates a solution to the same problem using several different data structures.

Koffman-preface.indd 4 10/20/2015 3:02:35 PM

http://www.wiley.com/college/koffman
Preface v

Prerequisites Our expectation is that the reader will be familiar with the Java primitive data types including int, boolean, char, and double; control structures including if, case, while, for, and try‐catch; the String class; the one‐dimensional array; input/output using either JOptionPane dialog win- dows or text streams (class Scanner or BufferedReader) and console input/output. For those readers who lack some of the concepts or who need some review, we provide complete coverage of these topics in Appendix A. Although labeled an Appendix, the review chapter provides full coverage of the background topics and has all the pedagogical features (discussed below) of the other chapters. We expect most readers will have some experience with Java programming, but someone who knows another programming language should be able to undertake the book after careful study of the review chapter. We do not require prior knowledge of inheritance, wrapper classes, or ArrayLists as we cover them in the book (Chapters 1 and 2).

Pedagogy The book contains the following pedagogical features to assist inexperienced programmers in learning the material.

• Learning objectives at the beginning of each chapter tell readers what skills they should develop.

• Introductions for each chapter help set the stage for what the chapter will cover and tie the chapter contents to other material that they have learned.

• Case Studies emphasize problem solving and provide complete and detailed solutions to real‐world problems using the data structures studied in the chapter.

• Chapter Summaries review the contents of the chapter. • Boxed Features emphasize and call attention to material designed to help readers become

better programmers.

Pitfall boxes help readers identify common problems and how to avoid them.

Design Concept boxes illuminate programming design decisions and trade‐offs.

Programming Style boxes discuss program features that illustrate good programming style and provide tips for writing clear and effective code.

Syntax boxes are a quick reference for the Java structures being introduced.

• Self‐Check and Programming Exercises at the end of each section provide immediate feedback and practice for readers as they work through the chapter.

• Quick‐Check, Review Exercises, and Programming Projects at the end of each chapter review chapter concepts and give readers a variety of skill‐building activities, including longer projects that integrate chapter concepts as they exercise the use of data structures.

Theoretical Rigor In Chapter 2, we discuss algorithm efficiency and big‐O notation as a measure of algorithm efficiency. We have tried to strike a balance between pure “hand waving” and extreme rigor when determining the efficiency of algorithms. Rather than provide several paragraphs of

Koffman-preface.indd 5 10/20/2015 3:02:42 PM

vi Preface

formulas, we have provided simplified derivations of algorithm efficiency using big‐O nota- tion. We feel this will give readers an appreciation of the performance of various algorithms and methods and the process one follows to determine algorithm efficiency without bogging them down in unnecessary detail.

Overview of the book Chapter 1 introduces Object Oriented Programming, inheritance, and class hierarchies including interfaces and abstract classes. We also introduce UML class diagrams and Javadoc‐ style documentation. The Exception class hierarchy is studied as an example of a Java class hierarchy.

Chapter 2 introduces the Java Collections Framework as the foundation for the traditional data structures. These are covered in separate chapters: lists (Chapter 2), stacks, queues and deques (Chapter 4), Trees (Chapters 6 and 9), Sets and Maps (Chapter 7), and Graphs (Chapter 10). Each new data structure is introduced as an abstract data type (ADT). We pro- vide a specification of each ADT in the form of a Java interface. Next, we implement the data structure as a class that implements the interface. Finally, we study applications of the data structure by solving sample problems and case studies.

Chapter 3 covers different aspects of testing (e.g. top‐down, bottom‐up, white‐box, black‐ box). It includes a section on developing a JUnit test harness and also a section on Test‐ Driven Development. It also discuses using a debugger to help find and correct errors.

Chapter 4 discusses stacks, queues, and deques. Several applications of these data structures are provided.

Chapter 5 covers recursion so that readers are prepared for the study of trees, a recursive data structure. This chapter could be studied earlier. There is an optional section on list processing applications of recursion that may be skipped if the chapter is covered earlier.

Chapter 6 discusses binary trees, including binary search trees, heaps, priority queues, and Huffman trees. It also shows how Java 8 lambda expressions and functional interfaces sup- port functional programming.

Chapter 7 covers the Set and Map interfaces. It also discusses hashing and hash tables and shows how a hash table can be used in an implementation of these interfaces. Building an index for a file and Huffman Tree encoding and decoding are two case studies covered in this chapter.

Chapter 8 covers various sorting algorithms including mergesort, heapsort, quicksort and Timsort.

Chapter 9 covers self‐balancing search trees, focusing on algorithms for manipulating them. Included are AVL and Red‐Black trees, 2‐3 trees, 2‐3‐4 trees, B‐trees, and skip‐lists.

Chapter 10 covers graphs. We provide several well‐known algorithms for graphs, including Dijkstra’s shortest path algorithm and Prim’s minimal spanning tree algorithm. In most pro- grams, the last few chapters would be covered in a second course in algorithms and data structures.

Supplements and Companion Web Sites The following supplementary materials are available on the Instructor’s Companion Web Site for this textbook at www.wiley.com/college/koffman. Items marked for students are accessi- ble on the Student Companion Web Site at the same address.

Koffman-preface.indd 6 10/20/2015 3:02:42 PM

http://www.wiley.com/college/koffman
Preface vii

• Additional homework problems with solutions • Additional case studies, including one that illustrates a solution to the same problem

using several different data structures • Source code for all classes in the book (for students and instructors) • PowerPoint slides • Electronic test bank for instructors • Solutions to end‐of‐section odd‐numbered self‐check and programming exercises (for students) • Solutions to all exercises for instructors • Solutions to chapter‐review exercises for instructors • Sample programming project solutions for instructors • Additional homework and laboratory projects, including cases studies and solutions

Acknowledgments Many individuals helped us with the preparation of this book and improved it greatly. We are grateful to all of them. These include students at Temple University who have used notes that led to the preparation of this book in their coursework, and who class‐tested early drafts of the book. We would like to thank Rolf Lakaemper and James Korsh, colleagues at Temple University, who used earlier editions in their classes. We would also like to thank a former Temple student, Michael Mayle, who provided preliminary solutions to many of the exercises.

We would also like to acknowledge support from the National Science Foundation (grant num- ber DUE‐1225742) and Principal Investigator Peter J. Clarke, Florida International University (FIU), to attend the Fifth Workshop on Integrating Software Testing into Programming Courses (WISTPC 2014) at FIU. Some of the testing methodologies discussed at the workshop were integrated into the chapter on Testing and Debugging.

We are especially grateful to our reviewers who provided invaluable comments that helped us correct errors in each version and helped us set our revision goals for the next version. The individuals who reviewed this book are listed below.

Reviewers Sheikh Iqbal Ahamed, Marquette University Justin Beck, Oklahoma State University John Bowles, University of South Carolina Mary Elaine Califf, Illinois State University Tom Cortina, SUNY Stony Brook Adrienne Decker, SUNY Buffalo Chris Dovolis, University of Minnesota Vladimir Drobot, San Jose State University Kenny Fong, Southern Illinois University, Carbondale Ralph Grayson, Oklahoma State University Allan M. Hart, Minnesota State University, Mankato James K. Huggins, Kettering University Chris Ingram, University of Waterloo Gregory Kesden, Carnegie Mellon University Sarah Matzko, Clemson University Lester McCann, University of Arizona

Koffman-preface.indd 7 10/20/2015 3:02:42 PM

viii Preface

Ron Metoyer, Oregon State University Rich Pattis, Carnegie Mellon University Thaddeus F. Pawlicki, University of Rochester Sally Peterson, University of Wisconsin—Madison Salam N. Salloum, California State Polytechnic University, Pomona Mike Scott, University of Texas—Austin Victor Shtern, Boston University Mark Stehlik, Carnegie Mellon University Ralph Tomlinson, Iowa State University Frank Tompa, University of Waterloo Renee Turban, Arizona State University Paul Tymann, Rochester Institute of Technology Karen Ward, University of Texas—El Paso Jim Weir, Marist College Lee Wittenberg, Kean University Martin Zhao, Mercer University

Although all the reviewers provided invaluable suggestions, we do want to give special thanks to Chris Ingram who reviewed every version of the first edition of the manuscript, including the preliminary pages for the book. His care, attention to detail, and dedication helped us improve this book in many ways, and we are very grateful for his efforts.

Besides the principal reviewers, there were a number of faculty members who reviewed sample pages of the first edition online and made valuable comments and criticisms of its content. We would like to thank those individuals, listed below.

Content Connections Online Review Razvan Andonie, Central Washington University Antonia Boadi, California State University Dominguez Hills Mikhail Brikman, Salem State College Robert Burton, Brigham Young University Chakib Chraibi, Barry University Teresa Cole, Boise State University Jose Cordova, University of Louisiana Monroe Joyce Crowell, Belmont University Robert Franks, Central College Barabra Gannod, Arizona State University East Wayne Goddard, Clemson University Simon Gray, College of Wooster Wei Hu, Houghton College Edward Kovach, Franciscan University of Steubenville Saeed Monemi, California Polytechnic and State University Robert Noonan, College of William and Mary

Koffman-preface.indd 8 10/20/2015 3:02:43 PM

Preface ix

Kathleen O’Brien, Foothill College Rathika Rajaravivarma, Central Connecticut State University Sam Rhoads, Honolulu Community College Vijayakumar Shanmugasundaram, Concordia College Moorhead Gene Sheppard, Perimeter College Linda Sherrell, University of Memphis Meena Srinivasan, Mary Washington College David Weaver, Sheperd University Stephen Weiss, University of North Carolina—Chapel Hill Glenn Wiggins, Mississippi College Bruce William, California State University Pomona

Finally, we want to acknowledge the participants in focus groups for the second programming course organized by John Wiley & Sons at the Annual Meeting of the SIGCSE Symposium in March 2004. They reviewed the preface, table of contents, and sample chapters and also provided valuable input on the book and future directions of the course.

Focus Group Claude Anderson, Rose-Hulman Institute of Technology Jay M. Anderson, Franklin & Marshall University John Avitabile, College of Saint Rose Cathy Bishop‐Clark, Miami University—Middletown Debra Burhans, Canisius College Michael Clancy, University of California—Berkeley Nina Cooper, University of Nevada Las Vegas Kossi Edoh, Montclair State University Robert Franks, Central College Evan Golub, University of Maryland Graciela Gonzalez, Sam Houston State University Scott Grissom, Grand Valley State University Jim Huggins, Kettering University Lester McCann, University of Wisconsin—Parkside Briana Morrison, Southern Polytechnic State University Judy Mullins, University of Missouri—Kansas City Roy Pargas, Clemson University J.P. Pretti, University of Waterloo Reza Sanati, Utah Valley State College Barbara Smith, University of Dayton Suzanne Smith, East Tennessee State University Michael Stiber, University of Washington, Bothell Jorge Vasconcelos, University of Mexico (UNAM) Lee Wittenberg, Kean University

Koffman-preface.indd 9 10/20/2015 3:02:43 PM

x Preface

We would also like to acknowledge and thank the team at John Wiley & Sons who were responsible for the management of this edition and ably assisted us with all phases of the book development and production. They were Gladys Soto, Project Manager, Nichole Urban, Project Specialist, and Rajeshkumar Nallusamy, Production Editor.

We would like to acknowledge the help and support of our colleague Frank Friedman who also read an early draft of this textbook and offered suggestions for improvement. Frank and Elliot began writing textbooks together many years ago and Frank has had substantial influ- ence on the format and content of these books. Frank also influenced Paul to begin his teach- ing career as an adjunct faculty member and then hired him as a full‐time faculty member when he retired from industry. Paul is grateful for his continued support.

Finally, we would like to thank our wives who provided us with comfort and support through this arduous process. We very much appreciate their understanding and their sacrifices that enabled us to focus on this book, often during time we would normally be spending with them. In particular, Elliot Koffman would like to thank

Caryn Koffman

and Paul Wolfgang would like to thank

Sharon Wolfgang

Koffman-preface.indd 10 10/20/2015 3:02:43 PM

Contents xi

Contents Preface iii

Chapter 1 Object-Oriented Programming and Class Hierarchies 1

1.1 ADTs, Interfaces, and the Java API 2 Interfaces 2 The implements Clause 5 Declaring a Variable of an Interface Type 6 Exercises for Section 1.1 6

1.2 Introduction to Object‐Oriented Programming (OOP) 7 A Superclass and Subclass Example 8 Use of this. 9 Initializing Data Fields in a Subclass 10 The No‐Parameter Constructor 11 Protected Visibility for Superclass Data Fields 11 Is‐a versus Has‐a Relationships 12 Exercises for Section 1.2 12

1.3 Method Overriding, Method Overloading, and Polymorphism 13 Method Overriding 13 Method Overloading 15 Polymorphism 17 Methods with Class Parameters 17 Exercises for Section 1.3 18

1.4 Abstract Classes 19 Referencing Actual Objects 21 Initializing Data Fields in an Abstract Class 21 Abstract Class Number and the Java Wrapper Classes 21 Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22 Implementing Multiple Interfaces 23 Extending an Interface 23 Exercises for Section 1.4 23

1.5 Class Object and Casting 24 The Method toString 24 Operations Determined by Type of Reference Variable 25 Casting in a Class Hierarchy 26 Using instanceof to Guard a Casting Operation 27 The Class Class 29 Exercises for Section 1.5 29

1.6 A Java Inheritance Example—The Exception Class Hierarchy 29 Division by Zero 29 Array Index Out of Bounds 30 Null Pointer 31 The Exception Class Hierarchy 31

Koffman-ftoc.indd 11 10/20/2015 3:01:55 PM

xii Contents

The Class Throwable 31 Checked and Unchecked Exceptions 32 Handling Exceptions to Recover from Errors 34 Using try‐catch to Recover from an Error 34 Throwing an Exception When Recovery Is Not Obvious 35 Exercises for Section 1.6 36

1.7 Packages and Visibility 36 Packages 36 The No‐Package‐Declared Environment 37 Package Visibility 38 Visibility Supports Encapsulation 38 Exercises for Section 1.7 39

1.8 A Shape Class Hierarchy 39 Case Study: Processing Geometric Figures 40 Exercises for Section 1.8 45 Java Constructs Introduced in This Chapter 46 Java API Classes Introduced in This Chapter 46 User‐Defined Interfaces and Classes in This Chapter 47 Quick‐Check Exercises 47 Review Questions 47 Programming Projects 48 Answers to Quick-Check Exercises 51

Chapter 2 Lists and the Collections Framework 53

2.1 Algorithm Efficiency and Big-O 54 Big-O Notation 56 Formal Definition of Big-O 57 Summary of Notation 60 Comparing Performance 60 Algorithms with Exponential and Factorial Growth Rates 62 Exercises for Section 2.1 62

2.2 The List Interface and ArrayList Class 63 The ArrayList Class 64 Generic Collections 66 Exercises for Section 2.2 68

2.3 Applications of ArrayList 68 A Phone Directory Application 69 Exercises for Section 2.3 69

2.4 Implementation of an ArrayList Class 70 The Constructor for Class KWArrayList 71 The add(E anEntry) Method 72 The add(int index, E anEntry) Method 73 The set and get Methods 73 The remove Method 74 The reallocate Method 74 Performance of the KWArrayList Algorithms 74 Exercises for Section 2.4 75

2.5 Single‐Linked Lists 75 A List Node 77

Koffman-ftoc.indd 12 10/20/2015 3:01:55 PM

Contents xiii

Connecting Nodes 78 A Single-Linked List Class 79 Inserting a Node in a List 79 Removing a Node 80 Completing the SingleLinkedList Class 81 The get and set Methods 82 The add Methods 82 Exercises for Section 2.5 83

2.6 Double‐Linked Lists and Circular Lists 84 The Node Class 85 Inserting into a Double‐Linked List 86 Removing from a Double‐Linked List 86 A Double‐Linked List Class 86 Circular Lists 87 Exercises for Section 2.6 88

2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 89 The LinkedList Class 89 The Iterator 89 The Iterator Interface 90 The Enhanced for Loop 92 The ListIterator Interface 92 Comparison of Iterator and ListIterator 94 Conversion between a ListIterator and an Index 95 The Iterable Interface 95 Exercises for Section 2.7 95

2.8 Application of the LinkedList Class 96 Case Study: Maintaining an Ordered List 96 Testing Class OrderedList 101 Exercises for Section 2.8 103

2.9 Implementation of a Double‐Linked List Class 103 Implementing the KWLinkedList Methods 104 A Class that Implements the ListIterator Interface 104 The Constructor 105 The hasNext and next Methods 106 The hasPrevious and previous Methods 107 The add Method 107 Inner Classes: Static and Nonstatic 111 Exercises for Section 2.9 111

2.10 The Collections Framework Design 112 The Collection Interface 112 Common Features of Collections 113 The AbstractCollection, AbstractList, and AbstractSequentialList Classes 113 The List and RandomAccess Interfaces (Advanced) 114 Exercises for Section 2.10 114 Java API Interfaces and Classes Introduced in this Chapter 116 User‐Defined Interfaces and Classes in this Chapter 116 Quick‐Check Exercises 116 Review Questions 117 Programming Projects 117 Answers to Quick-Check Exercises 119

Koffman-ftoc.indd 13 10/20/2015 3:01:55 PM

xiv Contents

Chapter 3 Testing and Debugging 121

3.1 Types of Testing 122 Preparations for Testing 124 Testing Tips for Program Systems 124 Exercises for Section 3.1 125

3.2 Specifying the Tests 125 Testing Boundary Conditions 125 Exercises for Section 3.2 126

3.3 Stubs and Drivers 127 Stubs 127 Preconditions and Postconditions 127 Drivers 128 Exercises for Section 3.3 128

3.4 The JUnit Test Framework 128 Exercises for Section 3.4 132

3.5 Test‐Driven Development 132 Exercises for Section 3.5 136

3.6 Testing Interactive Programs in JUnit 137 ByteArrayInputStream 138

ByteArrayOutputStream 138

Exercises for Section 3.6 139

3.7 Debugging a Program 139 Using a Debugger 140 Exercises for Section 3.7 142 Java API Classes Introduced in This Chapter 144 User‐Defined Interfaces and Classes in This Chapter 144 Quick‐Check Exercises 144 Review Questions 144 Programming 144 Answers to Quick-Check Exercises 146

Chapter 4 Stacks and Queues 147

4.1 Stack Abstract Data Type 148 Specification of the Stack Abstract Data Type 148 Exercises for Section 4.1 150

4.2 Stack Applications 151 Case Study: Finding Palindromes 151 Exercises for Section 4.2 155

4.3 Implementing a Stack 155 Implementing a Stack with an ArrayList Component 155 Implementing a Stack as a Linked Data Structure 157 Comparison of Stack Implementations 158 Exercises for Section 4.3 159

4.4 Additional Stack Applications 159 Case Study: Evaluating Postfix Expressions 160 Case Study: Converting From Infix To Postfix 165

Koffman-ftoc.indd 14 10/20/2015 3:01:55 PM

Contents xv

Case Study: Converting Expressions with Parentheses 173 Tying the Case Studies Together 176 Exercises for Section 4.4 176

4.5 Queue Abstract Data Type 177 A Print Queue 177 The Unsuitability of a “Print Stack” 178 A Queue of Customers 178 Using a Queue for Traversing a Multi‐Branch Data Structure 178 Specification for a Queue Interface 179 Class LinkedList Implements the Queue Interface 179 Exercises for Section 4.5 180

4.6 Queue Applications 181 Case Study: Maintaining a Queue 181 Exercises for Section 4.6 186

4.7 Implementing the Queue Interface 187 Using a Double‐Linked List to Implement the Queue Interface 187 Using a Single‐Linked List to Implement the Queue Interface 187 Using a Circular Array to Implement the Queue Interface 189 Exercises for Section 4.7 196

4.8 The Deque Interface 196 Classes that Implement Deque 198 Using a Deque as a Queue 198 Using a Deque as a Stack 198 Exercises for Section 4.8 199 Java API Classes Introduced in This Chapter 200 User‐Defined Interfaces and Classes in This Chapter 200 Quick‐Check Exercises 201 Review Questions 202 Programming Projects 203 Answers to Quick-Check Exercises 207

Chapter 5 Recursion 211

5.1 Recursive Thinking 212 Steps to Design a Recursive Algorithm 214 Proving that a Recursive Method Is Correct 216 Tracing a Recursive Method 216 The Run‐Time Stack and Activation Frames 217 Exercises for Section 5.1 218

5.2 Recursive Definitions of Mathematical Formulas 219 Tail Recursion versus Iteration 222 Efficiency of Recursion 223 Exercises for Section 5.2 225

5.3 Recursive Array Search 226 Design of a Recursive Linear Search Algorithm 226 Implementation of Linear Search 227 Design of a Binary Search Algorithm 228 Efficiency of Binary Search 229 The Comparable Interface 230

Koffman-ftoc.indd 15 10/20/2015 3:01:55 PM

xvi Contents

Implementation of Binary Search 230 Testing Binary Search 232 Method Arrays.binarySearch 233 Exercises for Section 5.3 233

5.4 Recursive Data Structures 233 Recursive Definition of a Linked List 234 Class LinkedListRec 234 Removing a List Node 236 Exercises for Section 5.4 237

5.5 Problem Solving with Recursion 238 Case Study: Towers of Hanoi 238 Case Study: Counting Cells in a Blob 243 Exercises for Section 5.5 247

5.6 Backtracking 247 Case Study: Finding a Path through a Maze 248 Exercises for Section 5.6 252 User‐Defined Classes in This Chapter 253 Quick‐Check Exercises 253 Review Questions 253 Programming Projects 254 Answers to Quick-Check Exercises 255

Chapter 6 Trees 257

6.1 Tree Terminology and Applications 258 Tree Terminology 258 Binary Trees 259 Some Types of Binary Trees 260 Full, Perfect, and Complete Binary Trees 263 General Trees 263 Exercises for Section 6.1 264

6.2 Tree Traversals 265 Visualizing Tree Traversals 266 Traversals of Binary Search Trees and Expression Trees 266 Exercises for Section 6.2 267

6.3 Implementing a BinaryTree Class 268 The Node Class 268 The BinaryTree Class 269 Exercises for Section 6.3 275

6.4 Java 8 Lambda Expressions and Functional Interfaces 276 Functional Interfaces 277 Passing a Lambda Expression as an Argument 279 A General Preorder Traversal Method 280 Using preOrderTraverse 280 Exercises for Section 6.4 281

6.5 Binary Search Trees 282 Overview of a Binary Search Tree 282 Performance 283

Koffman-ftoc.indd 16 10/20/2015 3:01:55 PM

Contents xvii

Interface SearchTree 283 The BinarySearchTree Class 283 Insertion into a Binary Search Tree 285 Removal from a Binary Search Tree 288 Testing a Binary Search Tree 293 Case Study: Writing an Index for a Term Paper 294 Exercises for Section 6.5 297

6.6 Heaps and Priority Queues 297 Inserting an Item into a Heap 298 Removing an Item from a Heap 298 Implementing a Heap 299 Priority Queues 302 The PriorityQueue Class 303 Using a Heap as the Basis of a Priority Queue 303 The Other Methods 306 Using a Comparator 306 The compare Method 306 Exercises for Section 6.6 307

6.7 Huffman Trees 308 Case Study: Building a Custom Huffman Tree 310 Exercises for Section 6.6 315 Java API Interfaces and Classes Introduced in This Chapter 316 User‐Defined Interfaces and Classes in This Chapter 317 Quick‐Check Exercises 317 Review Questions 318 Programming Projects 318 Answers to Quick-Check Exercises 320

Chapter 7 Sets and Maps 323

7.1 Sets and the Set Interface 324 The Set Abstraction 324 The Set Interface and Methods 325 Comparison of Lists and Sets 327 Exercises for Section 7.1 328

7.2 Maps and the Map Interface 329 The Map Hierarchy 330 The Map Interface 330 Exercises for Section 7.2 332

7.3 Hash Tables 333 Hash Codes and Index Calculation 333 Methods for Generating Hash Codes 334 Open Addressing 335 Table Wraparound and Search Termination 335 Traversing a Hash Table 337 Deleting an Item Using Open Addressing 337 Reducing Collisions by Expanding the Table Size 338 Reducing Collisions Using Quadratic Probing 338 Problems with Quadratic Probing 339

Koffman-ftoc.indd 17 10/20/2015 3:01:55 PM

xviii Contents

Chaining 340 Performance of Hash Tables 340 Exercises for Section 7.3 342

7.4 Implementing the Hash Table 344 Interface KWHashMap 344 Class Entry 344 Class HashtableOpen 345 Class HashtableChain 350 Testing the Hash Table Implementations 353 Exercises for Section 7.4 354

7.5 Implementation Considerations for Maps and Sets 354 Methods hashCode and equals 354 Implementing HashSetOpen 355 Writing HashSetOpen as an Adapter Class 355 Implementing the Java Map and Set Interfaces 356 Interface Map.Entry and Class AbstractMap.SimpleEntry 356 Creating a Set View of a Map 357 Method entrySet and Classes EntrySet and SetIterator 357 Classes TreeMap and TreeSet 358 Exercises for Section 7.5 359

7.6 Additional Applications of Maps 359 Case Study: Implementing a Cell Phone Contact List 359 Case Study: Completing the Huffman Coding Problem 361 Encoding the Huffman Tree 365 Exercises for Section 7.6 366

7.7 Navigable Sets and Maps 366 Application of a NavigableMap 368 Exercises for Section 7.7 370 Java API Interfaces and Classes Introduced in This Chapter 372 User‐Defined Interfaces and Classes in This Chapter 372 Quick‐Check Exercises 372 Review Questions 372 Programming Projects 373 Answers to Quick-Check Exercises 374

Chapter 8 Sorting 375

8.1 Using Java Sorting Methods 376 Exercises for Section 8.1 380

8.2 Selection Sort 380 Analysis of Selection Sort 381 Code for Selection Sort 381 Exercises for Section 8.2 383

8.3 Insertion Sort 383 Analysis of Insertion Sort 384 Code for Insertion Sort 385 Exercises for Section 8.3 386

8.4 Comparison of Quadratic Sorts 386 Comparisons versus Exchanges 387 Exercises for Section 8.4 388

Koffman-ftoc.indd 18 10/20/2015 3:01:55 PM

Contents xix

8.5 Shell Sort: A Better Insertion Sort 388 Analysis of Shell Sort 389 Code for Shell Sort 390 Exercises for Section 8.5 391

8.6 Merge Sort 391 Analysis of Merge 392 Code for Merge 392 Algorithm for Merge Sort 394 Trace of Merge Sort Algorithm 394 Analysis of Merge Sort 394 Code for Merge Sort 395 Exercises for Section 8.6 396

8.7 Timsort 397 Merging Adjacent Sequences 400 Implementation 400

8.8 Heapsort 405 First Version of a Heapsort Algorithm 405 Revising the Heapsort Algorithm 405 Algorithm to Build a Heap 407 Analysis of Revised Heapsort Algorithm 407 Code for Heapsort 407 Exercises for Section 8.8 409

8.9 Quicksort 409 Algorithm for Quicksort 410 Analysis of Quicksort 411 Code for Quicksort 411 Algorithm for Partitioning 412 Code for partition 413 A Revised partition Algorithm 415 Code for Revised partition Method 416 Exercises for Section 8.9 417

8.10 Testing the Sort Algorithms 417 Exercises for Section 8.10 419

8.11 The Dutch National Flag Problem (Optional Topic) 419 Case Study: The Problem of the Dutch National Flag 419 Exercises for Section 8.11 422 Java Classes Introduced in This Chapter 423 User‐Defined Interfaces and Classes in This Chapter 423 Quick‐Check Exercises 424 Review Questions 424 Programming Projects 424 Answers to Quick-Check Exercises 425

Chapter 9 Self-Balancing Search Trees 427

9.1 Tree Balance and Rotation 428 Why Balance Is Important 428 Rotation 428 Algorithm for Rotation 429 Implementing Rotation 430 Exercises for Section 9.1 432

Koffman-ftoc.indd 19 10/20/2015 3:01:55 PM

xx Contents

9.2 AVL Trees 432 Balancing a Left–Left Tree 432 Balancing a Left–Right Tree 433 Four Kinds of Critically Unbalanced Trees 434 Implementing an AVL Tree 436 Inserting into an AVL Tree 438 Removal from an AVL Tree 443 Performance of the AVL Tree 444 Exercises for Section 9.2 444

9.3 Red–Black Trees 445 Insertion into a Red–Black Tree 445 Removal from a Red–Black Tree 455 Performance of a Red–Black Tree 455 The TreeMap and TreeSet Classes 455 Exercises for Section 9.3 456

9.4 2–3 Trees 456 Searching a 2–3 Tree 457 Inserting an Item into a 2–3 Tree 457 Analysis of 2–3 Trees and Comparison with Balanced Binary Trees 461 Removal from a 2–3 Tree 461 Exercises for Section 9.4 462

9.5 B‐Trees and 2–3–4 Trees 463 B‐Trees 463 Implementing the B‐Tree 464 Code for the insert Method 466 The insertIntoNode Method 467 The splitNode Method 468 Removal from a B‐Tree 470 B+ Trees 471 2–3–4 Trees 471 Relating 2–3–4 Trees to Red–Black Trees 473 Exercises for Section 9.5 474

9.6 Skip‐Lists 475 Skip‐List Structure 475 Searching a Skip‐List 476 Performance of a Skip‐List Search 477 Inserting into a Skip‐List 477 Increasing the Height of a Skip‐List 477 Implementing a Skip‐List 477 Searching a Skip‐List 478 Insertion 479 Determining the Size of the Inserted Node 480 Completing the Insertion Process 480 Performance of a Skip‐List 480 Exercises for Section 9.6 480 Java Classes Introduced in This Chapter 482 User‐Defined Interfaces and Classes in This Chapter 482 Quick‐Check Exercises 482

Koffman-ftoc.indd 20 10/20/2015 3:01:55 PM

Contents xxi

Review Questions 483 Programming Projects 484 Answers to Quick-Check Exercises 486

Chapter 10 Graphs 489

10.1 Graph Terminology 490 Visual Representation of Graphs 490 Directed and Undirected Graphs 491 Paths and Cycles 491 Relationship between Graphs and Trees 493 Graph Applications 493 Exercises for Section 10.1 494

10.2 The Graph ADT and Edge Class 494 Representing Vertices and Edges 495 Exercises for Section 10.2 496

10.3 Implementing the Graph ADT 496 Adjacency List 497 Adjacency Matrix 497 Overview of the Hierarchy 499 Class AbstractGraph 499 The ListGraph Class 501 The MatrixGraph Class 503 Comparing Implementations 504 The MapGraph Class 505 Exercises for Section 10.3 505

10.4 Traversals of Graphs 506 Breadth‐First Search 506 Algorithm for Breadth‐First Search 508 Depth‐First Search 511 Exercises for Section 10.4 517

10.5 Applications of Graph Traversals 517 Case Study: Shortest Path through a Maze 517 Case Study: Topological Sort of a Graph 521 Exercises for Section 10.5 524

10.6 Algorithms Using Weighted Graphs 524 Finding the Shortest Path from a Vertex to All Other Vertices 524 Minimum Spanning Trees 528 Exercises for Section 10.6 531 User‐Defined Classes and Interfaces in This Chapter 533 Quick‐Check Exercises 533 Review Questions 534 Programming Projects 534 Answers to Quick-Check Exercises 536

Appendix A Introduction to Java 541

A.1 The Java Environment and Classes 542 The Java Virtual Machine 543

Koffman-ftoc.indd 21 10/20/2015 3:01:55 PM

xxii Contents

The Java Compiler 543 Classes and Objects 543 The Java API 543 The import Statement 544 Method main 544 Execution of a Java Program 545 Exercises for Section A.1 545

A.2 Primitive Data Types and Reference Variables 545 Primitive Data Types 545 Primitive‐Type Variables 547 Primitive‐Type Constants 547 Operators 547 Postfix and Prefix Increment 549 Type Compatibility and Conversion 549 Referencing Objects 550 Creating Objects 550 Exercises for Section A.2 551

A.3 Java Control Statements 551 Sequence and Compound Statements 551 Selection and Repetition Control 551 Nested if Statements 553 The switch Statement 555 Exercises for Section A.3 555

A.4 Methods and Class Math 555 The Instance Methods println and print 556 Call‐by‐Value Arguments 557 The Class Math 557 Escape Sequences 558 Exercises for Section A.4 559

A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes 559 The String Class 559 Strings Are Immutable 562 The Garbage Collector 562 Comparing Objects 562 The String.format Method 564 The Formatter Class 565 The String.split Method 565 Introduction to Regular Expressions 565 Matching One of a Group of Characters 566 Qualifiers 566 Defined Character Groups 567 Unicode Character Class Support 567 The StringBuilder and StringBuffer Classes 567 Java 8 StringJoiner Class 569 Exercises for Section A.5 570

A.6 Wrapper Classes for Primitive Types 571 Exercises for Section A.6 572

A.7 Defining Your Own Classes 573 Private Data Fields, Public Methods 576

Koffman-ftoc.indd 22 10/20/2015 3:01:56 PM

Contents xxiii

Constructors 577 The No‐Parameter Constructor 577 Modifier and Accessor Methods 578 Use of this. in a Method 578 The Method toString 578 The Method equals 579 Declaring Local Variables in Class Person 580 An Application that Uses Class Person 580 Objects as Arguments 581 Classes as Components of Other Classes 582 Java Documentation Style for Classes and Methods 582 Exercises for Section A.7 585

A.8 Arrays 585 Data Field length 587 Method Arrays.copyOf 588 Method System.arrayCopy 588 Array Data Fields 589 Array Results and Arguments 590 Arrays of Arrays 590 Exercises for Section A.8 593

A.9 Enumeration Types 594 Using Enumeration Types 595 Assigning Values to Enumeration Types 596 Exercises for Section A.9 596

A.10 I/O Using Streams, Class Scanner, and Class JOptionPane 596 The Scanner 597 Using a Scanner to Read from a File 599 Exceptions 599 Tokenized Input 599 Extracting Tokens Using Scanner.findInLine 600 Using a BufferedReader to Read from an Input Stream 600 Output Streams 600 Passing Arguments to Method main 600 Closing Streams 601 Try with Resources 601 A Complete File‐Processing Application 601 Class InputStream and Character Codes (Optional) 603 The Default Character Coding (Optional) 603 UTF‐8 (Optional) 604 Specifying a Character Encoding (Optional) 605 Input/Output Using Class JOptionPane 605 Converting Numeric Strings to Numbers 606 GUI Menus Using Method showOptionDialog 607 Exercises for Section A.10 607

A.11 Catching Exceptions 608 Catching and Handling Exceptions 608 Exercises for Section A.11 614

A.12 Throwing Exceptions 614 The throws Clause 615

Koffman-ftoc.indd 23 10/20/2015 3:01:56 PM

xxiv Contents

The throw Statement 616 Exercises for Section A.12 619 Java Constructs Introduced in This Appendix 621 Java API Classes Introduced in This Appendix 622 User‐Defined Interfaces and Classes in This Appendix 622 Quick‐Check Exercises 622 Review Questions 622 Programming Projects 623 Answer to Quick‐Check Exercises 624

Appendix B Overview of UML 625

B.1 The Class Diagram 626 Representing Classes and Interfaces 626 Generalization 629 Inner or Nested Classes 629 Association 629 Aggregation and Composition 630 Generic Classes 631

B.2 Sequence Diagrams 631 Time Axis 632 Objects 633 Life Lines 633 Activation Bars 633 Messages 633 Use of Notes 633

Glossary 635 Index 643

Koffman-ftoc.indd 24 10/20/2015 3:01:56 PM

C h a p t e r

1

This chapter describes important features of Java that support Object‐Oriented Programming (OOP). Object‐oriented languages allow you to build and exploit hierarchies of classes in order to write code that may be more easily reused in new applications. You will learn how to extend an existing Java class to define a new class that inherits all the attributes of the original, as well as having additional attributes of its own. Because there may be many versions of the same method in a class hierarchy, we show how polymorphism enables Java to determine which version to execute at any given time.

We introduce interfaces and abstract classes and describe their relationship with each other and with actual classes. We introduce the abstract class Number. We also discuss class Object, which all classes extend, and we describe several of its methods that may be used in classes you create.

As an example of a class hierarchy and OOP, we describe the Exception class hierarchy and explain that the Java Virtual Machine (JVM) creates an Exception object whenever an error occurs during program execution. Finally, you will learn how to create packages in Java and about the different kinds of visibility for instance variables (data fields) and methods.

Object‐Oriented Programming and Class Hierarchies

1C h a p t e r

C h a p t e r O b j e c t i v e s

◆ To learn about interfaces and their role in Java ◆ To understand inheritance and how it facilitates code reuse ◆ To understand how Java determines which method to execute when there are multiple methods with the same name in a class hierarchy

◆ To become familiar with the Exception hierarchy and the difference between checked and unchecked exceptions

◆ To learn how to define and use abstract classes as base classes in a hierarchy ◆ To learn the role of abstract data types and how to specify them using interfaces ◆ To study class Object and its methods and to learn how to override them ◆ To become familiar with a class hierarchy for shapes ◆ To understand how to create packages and to learn more about visibility

Koffman-c01.indd 1 10/30/2015 7:39:45 PM

2 Chapter 1 Object‐Oriented Programming and Class Hierarchies

1.1 ADTs, Interfaces, and the Java API

In earlier programming courses, you learned how to write individual classes consisting of attributes and methods (operations). You also learned how to use existing classes (e.g., String and Scanner) to facilitate your programming. These classes are part of the Java Application Programming Interface (API).

One of our goals is to write code that can be reused in many different applications. One way to make code reusable is to encapsulate the data elements together with the methods that operate on that data. A new program can then use the methods to manipulate an object’s data without being concerned about details of the data representation or the method implementa- tions. The encapsulated data together with its methods is called an abstract data type (ADT).

Figure 1.1 shows a diagram of an ADT. The data values stored in the ADT are hidden inside the circular wall. The bricks around this wall are used to indicate that these data values can- not be accessed except by going through the ADT’s methods.

A class provides one way to implement an ADT in Java. If the data fields are private, they can be accessed only through public methods. Therefore, the methods control access to the data and determine the manner in which the data is manipulated.

Another goal of this text is to show you how to write and use ADTs in programming. As you progress through this book, you will create a large collection of ADT implementations (classes) in your own program library. You will also learn about ADTs that are available for you to use through the Java API.

Our principal focus will be on ADTs that are used for structuring data to enable you to more easily and efficiently store, organize, and process information. These ADTs are often called data structures. We introduce the Java Collections Framework (part of the Java API), which provides implementation of these common data structures, in Chapter 2 and study it through- out the text. Using the classes that are in the Java Collections Framework will make it much easier for you to design and implement new application programs.

Interfaces A Java interface is a way to specify or describe an ADT to an applications programmer. An interface is like a contract that tells the applications programmer precisely what methods are available and describes the operations they perform. It also tells the applications programmer

I n h e r i t a n c e a n d C l a s s H i e r a r c h i e s

1.1 ADTs, Interfaces, and the Java API 1.2 Introduction to Object‐Oriented Programming 1.3 Method Overriding, Method Overloading, and Polymorphism 1.4 Abstract Classes 1.5 Class Object and Casting 1.6 A Java Inheritance Example—The Exception Class Hierarchy 1.7 Packages and Visibility 1.8 A Shape Class Hierarchy

Case Study: Processing Geometric Figures

ADT operations

ADT data

F I G U R E 1 . 1 Diagram of an ADT

Koffman-c01.indd 2 10/30/2015 7:39:47 PM

1.1 ADTs, Interfaces, and the Java API 3

what arguments, if any, must be passed to each method and what result the method will return. Of course, in order to make use of these methods, someone else must have written a class that implements the interface by providing the code for these methods.

The interface tells the coder precisely what methods must be written, but it does not provide a detailed algorithm or prescription for how to write them. The coder must “program to the interface,” which means he or she must develop the methods described in the interface with- out variation. If each coder does this job well, that ensures that other programmers can use the completed class exactly as it is written, without needing to know the details of how it was coded.

There may be more than one way to implement the methods; hence, several classes may implement the interface, but each must satisfy the contract. One class may be more efficient than the others at performing certain kinds of operations (e.g., retrieving information from a database), so that class will be used if retrieval operations are more likely in a particular application. The important point is that the particular implementation that is used will not affect other classes that interact with it because every implementation satisfies the contract.

Besides providing the complete definition (implementation) of all methods declared in the interface, each implementer of an interface may declare data fields and define other methods not in the interface, including constructors. An interface cannot contain constructors because it cannot be instantiated—that is, one cannot create objects, or instances, of it. However, it can be represented by instances of classes that implement it.

EXAMPLE 1.1 An automated teller machine (ATM) enables a user to perform certain banking operations from a remote location. It must support the following operations.

1. Verify a user’s Personal Identification Number (PIN). 2. Allow the user to choose a particular account. 3. Withdraw a specified amount of money. 4. Display the result of an operation. 5. Display an account balance.

A class that implements an ATM must provide a method for each operation. We can write this requirement as the interface ATM and save it in file ATM.java, shown in Listing 1.1. The keyword interface on the header line indicates that an interface is being declared. If you are unfamiliar with the documentation style shown in this listing, read about Java documenta- tion at the end of Section A.7 in Appendix A.

L I S T I N G 1 . 1 Interface ATM.java

/** The interface for an ATM. */ public interface ATM {

/** Verifies a user's PIN. @param pin The user's PIN @return Whether or not the User's PIN is verified */ boolean verifyPIN(String pin);

/** Allows the user to select an account. @return a String representing the account selected */

Koffman-c01.indd 3 10/30/2015 7:39:47 PM

4 Chapter 1 Object‐Oriented Programming and Class Hierarchies

SYNTAX Interface Definition FORM: public interface interfaceName { abstract method declarations constant declarations }

EXAMPLE: public interface Payable { public abstract double calcSalary(); public abstract boolean salaried(); public static final double DEDUCTIONS = 25.5; }

MEANING: Interface interfaceName is defined. The interface body provides headings for abstract methods and constant declarations. Each abstract method must be defined in a class

String selectAccount();

/** Withdraws a specified amount of money @param account The account from which the money comes @param amount The amount of money withdrawn @return Whether or not the operation is successful */ boolean withdraw(String account, double amount);

/** Displays the result of an operation @param account The account for the operation @param amount The amount of money @param success Whether or not the operation was successful */ void display(String account, double amount, boolean success);

/** Displays the result of a PIN verification @param pin The user's pin @param success Whether or not the PIN was valid */ void display(String pin, boolean success);

/** Displays an account balance @param account The account selected */ void showBalance(String account); }

The interface definition shows the heading only for several methods. Because only the head- ings are shown, they are considered abstract methods. Each actual method with its body must be defined in a class that implements the interface. Therefore, a class that implements this interface must provide a void method called verifyPIN with an argument of type String. There are also two display methods with different signatures. The first is used to display the result of a withdrawal, and the second is used to display the result of a PIN verification. The keywords public abstract are optional (and usually omitted) in an interface because all interface methods are public abstract by default.

Koffman-c01.indd 4 10/30/2015 7:39:47 PM

1.1 ADTs, Interfaces, and the Java API 5

The implements Clause The class headings for two classes that implement interface ATM are

public class ATMbankAmerica implements ATM public class ATMforAllBanks implements ATM

Each class heading ends with the clause implements ATM. When compiling these classes, the Java compiler will verify that they define the required methods in the way specified by the interface. If a class implements more than one interface, list them all after implements, with commas as separators.

Figure 1.2 is a UML (Unified Modeling Language) diagram that shows the ATM interface and these two implementing classes. Note that a dashed line from the class to the interface is used to indicate that the class implements the interface. We will use UML diagrams through- out this text to show relationships between classes and interfaces. Appendix B provides detailed coverage of UML diagrams.

that implements the interface. Constants defined in the interface (e.g., DEDUCTIONS) are accessible in classes that implement the interface or in the same way as static fields and methods in classes (see Section A.4).

NOTES: The keywords public and abstract are implicit in each abstract method declaration, and the keywords public static final are implicit in each constant declaration. We show them in the example here, but we will omit them from now on. Java 8 also allows for static and default methods in interfaces. They are used to add features to existing classes and interfaces while minimizing the impact on existing programs. We will discuss default and static methods when describing where they are used in the API.

ATMbankAmerica

boolean verifyPIN(String pin) String selectAccount() boolean withdraw(String account, double amount) void display(String account, double amount, boolean success) void display(String pin, boolean success) void showBalance(String account)

ATMforAllBanks

boolean verifyPIN(String pin) String selectAccount() boolean withdraw(String account, double amount) void display(String account, double amount, boolean success) void display(String pin, boolean success) void showBalance(String account)

‹‹interface›› ATM

boolean verifyPIN(String pin) String selectAccount() boolean withdraw(String account, double amount) void display(String account, double amount, boolean success) void display(String pin, boolean success) void showBalance(String account)

F I G U R E 1 . 2 UML Diagram Showing the ATM Interface and Its Implementing Classes

Koffman-c01.indd 5 10/30/2015 7:39:48 PM

6 Chapter 1 Object‐Oriented Programming and Class Hierarchies

Declaring a Variable of an Interface Type In the previous programming pitfall, we mentioned that you cannot instantiate an interface. However, you may want to declare a variable that has an interface type and use it to reference an actual object. This is permitted if the variable references an object of a class type that implements the interface. After the following statements execute, variable ATM1 references an ATMbankAmerica object, and variable ATM2 references an ATMforAllBanks object, but both ATM1 and ATM2 are type ATM.

ATM ATM1 = new ATMbankAmerica(); // valid statement ATM ATM2 = new ATMforAllBanks(); // valid statement

E X E R C I S E S F O R S E C T I O N 1 . 1

S E L F ‐ C H E C K

1. What are the two parts of an ADT? Which part is accessible to a user and which is not? Explain the relationships between an ADT and a class, between an ADT and an interface, and between an interface and classes that implement the interface.

2. Correct each of the following statements that is incorrect, assuming that class PDGUI and class PDConsoleUI implement interface PDUserInterface. a. PDGUI p1 = new PDConsoleUI(); b. PDGUI p2 = new PDUserInterface();

P I T F A L L

Not Properly Defining a Method to Be Implemented If you neglect to define method verifyPIN in class ATMforAllBanks or if you use a different method signature, you will get the following syntax error: class ATMforAllBanks should be declared abstract; it does not define method verifyPIN(String) in interface ATM.

The above error indicates that the method verifyPin was not properly defined. Because it contains an abstract method that is not defined, Java incorrectly believes that ATM should be declared to be an abstract class. If you use a result type other than boolean, you will also get a syntax error.

P I T F A L L

Instantiating an Interface An interface is not a class, so you cannot instantiate an interface. The statement ATM anATM = new ATM(); // invalid statement

will cause the following syntax error: interface ATM is abstract; cannot be instantiated.

Koffman-c01.indd 6 10/30/2015 7:39:48 PM

1.2 Introduction to Object‐Oriented Programming (OOP) 7

1.2 Introduction to Object‐Oriented Programming (OOP)

In this course, you will learn to use features of Java that facilitate the practice of OOP. A major reason for the popularity of OOP is that it enables programmers to reuse previously written code saved as classes, reducing the time required to code new applications. Because previously written code has already been tested and debugged, the new applications should also be more reliable and therefore easier to test and debug.

However, OOP provides additional capabilities beyond the reuse of existing classes. If an appli- cation needs a new class that is similar to an existing class but not exactly the same, the pro- grammer can create it by extending, or inheriting from, the existing class. The new class (called the subclass) can have additional data fields and methods for increased functionality. Its objects also inherit the data fields and methods of the original class (called the superclass).

Inheritance in OOP is analogous to inheritance in humans. We all inherit genetic traits from our parents. If we are fortunate, we may even have some earlier ancestors who have left us

c. PDUserInterface p3 = new PDUserInterface(); d. PDUserInterface p4 = new PDConsoleUI(); e. PDGUI p5 = new PDUserInterface(); PDUserInterface p6 = p5; f. PDUserInterface p7; p7 = new PDConsoleUI();

3. Explain how an interface is like a contract.

4. What are two different uses of the term interface in programming?

P R O G R A M M I N G

1. Define an interface named Resizable with just one abstract method, resize, that is a void method with no parameter.

2. Write a Javadoc comment for the following method of a class Person. Assume that class Person has two String data fields familyName and givenName with the obvious meanings. Provide preconditions and postconditions if needed. public int compareTo(Person per) { if (familyName.compareTo(per.familyName) == 0) return givenName.compareTo(per.givenName); else return familyName.compareTo(per.familyName); }

3. Write a Javadoc comment for the following method of class Person. Provide preconditions and postconditions if needed. public void changeFamilyName(boolean justMarried, String newFamily) { if (justMarried) familyName = newFamily; }

4. Write method verifyPIN for class ATMbankAmerica assuming this class has a data field pin (type String).

Koffman-c01.indd 7 10/30/2015 7:39:48 PM

8 Chapter 1 Object‐Oriented Programming and Class Hierarchies

an inheritance of monetary value. As we grow up, we benefit from our ancestors’ resources, knowledge, and experiences, but our experiences will not affect how our parents or ancestors developed. Although we have two parents to inherit from, Java classes can have only one parent.

Inheritance and hierarchical organization allow you to capture the idea that one thing may be a refinement or an extension of another. For example, an object that is a Human is a Mammal (the superclass of Human). This means that an object of type Human has all the data fields and meth- ods defined by class Mammal (e.g., method drinkMothersMilk), but it may also have more data fields and methods that are not contained in class Mammal (e.g., method thinkCreatively). Figure 1.3 shows this simple hierarchy. The solid line in the UML class diagram shows that Human is a subclass of Mammal, and, therefore, Human objects can use methods drinkMothersMilk and thinkCreatively. Objects farther down the hierarchy are more complex and less general than those farther up. For this reason an object that is a Human is a Mammal, but the converse is not true because every Mammal object does not necessarily have the additional properties of a Human. Although this seems counterintuitive, the subclass Human is actually more powerful than the superclass Mammal because it may have additional attributes that are not present in the superclass.

A Superclass and Subclass Example To illustrate the concepts of inheritance and class hierarchies, let’s consider a simple case of two classes: Computer and Notebook. A Computer object has a manufacturer, processor, RAM, and disk. A notebook computer is a kind of computer, so it has all the properties of a com- puter plus some additional features (screen size and weight). There may be other subclasses, such as tablet computer or game computer, but we will ignore them for now. We can define class Notebook as a subclass of class Computer. Figure 1.4 shows the class hierarchy.

Class Computer Listing 1.2 shows class Computer.Java. It is defined like any other class. It contains a construc- tor, several accessors, a toString method, and a method computePower, which returns the product of its RAM size and processor speed as a simple measure of its power.

Mammal

drinkMothersMilk()

Human

thinkCreatively()

F I G U R E 1 . 3 Classes Mammal and Human

Computer

String manufacturer String processor int ramSize int diskSize double processorSpeed

int getRamSize() int getDiskSize() double getProcessorSpeed() double computePower() String toString()

Notebook

double screenSize double weight

F I G U R E 1 . 4 Classes NoteBook and Computer

L I S T I N G 1 . 2 Class Computer.java

/** Class that represents a computer. */ public class Computer { // Data Fields private String manufacturer; private String processor; private double ramSize; private int diskSize; private double processorSpeed;

// Methods /** Initializes a Computer object with all properties specified. @param man The computer manufacturer @param processor The processor type @param ram The RAM size @param disk The disk size @param procSpeed The processor speed */ public Computer(String man, String processor, double ram, int disk, double procSpeed) {

Koffman-c01.indd 8 10/30/2015 7:39:49 PM

1.2 Introduction to Object‐Oriented Programming (OOP) 9

Use of this. In the constructor for the Computer class, the statement

this.processor = processor;

sets data field processor in the object under construction to reference the same string as parameter processor. The prefix this. makes data field processor visible in the constructor. This is necessary because the declaration of processor as a parameter hides the data field declaration.

manufacturer = man; this.processor = processor; ramSize = ram; diskSize = disk; processorSpeed = procSpeed; }

public double computePower() { return ramSize * processorSpeed; } public double getRamSize() { return ramSize; } public double getProcessorSpeed() { return processorSpeed; } public int getDiskSize() { return diskSize; } // Insert other accessor and modifier methods here.

public String toString() { String result = "Manufacturer: " + manufacturer + "\nCPU: " + processor + "\nRAM: " + ramSize + " gigabytes" + "\nDisk: " + diskSize + " gigabytes" + "\nProcessor speed: " + processorSpeed + " gigahertz"; return result; } }

Class Notebook In the Notebook class diagram in Figure 1.4, we show just the data fields declared in class Notebook; however, Notebook objects also have the data fields that are inherited from class Computer (processor, ramSize, and so forth). The first line in class Notebook (Listing 1.3),

public class Notebook extends Computer {

P I T F A L L

Not Using this. to Access a Hidden Data Field If you write the preceding statement as processor = processor; // Copy parameter processor to itself.

you will not get an error, but the data field processor in the Computer object under construction will not be initialized and will retain its default value (null). If you later attempt to use data field processor, you may get an error or just an unexpected result. Some IDEs will provide a warning if this. is omitted.

Koffman-c01.indd 9 10/30/2015 7:39:49 PM

10 Chapter 1 Object‐Oriented Programming and Class Hierarchies

indicates that class Notebook extends class Computer and inherits its data and methods. Next, we define any additional data fields

// Data Fields private double screenSize; private double weight;

Initializing Data Fields in a Subclass The constructor for class Notebook must begin by initializing the four data fields inherited from class Computer. Because those data fields are private to the superclass, Java requires that they be initialized by a superclass constructor. Therefore, a superclass constructor must be invoked as the first statement in the constructor body using a statement such as

super(man, proc, ram, disk, procSpeed);

This statement invokes the superclass constructor with the signature Computer(String, String, double, int, double), passing the four arguments listed to the constructor. (A method signature consists of the method’s name followed by its parameter types.) The following con- structor for Notebook also initializes the data fields that are not inherited. Listing 1.3 shows class Notebook.

public Notebook(String man, String proc, double ram, int disk, double procSpeed, double screen, double wei) { super(man, proc, ram, disk, procSpeed); screenSize = screen; weight = wei; }

L I S T I N G 1 . 3 Class Notebook

/** Class that represents a notebook computer. */ public class Notebook extends Computer { // Data Fields private double screenSize; private double weight;

// Methods /** Initializes a Notebook object with all properties specified. @param man The computer manufacturer @param proc The processor type @param ram The RAM size

SYNTAX super( . . . ); FORM: super(); super(argumentList);

EXAMPLE: super(man, proc, ram, disk, procSpeed);

MEANING: The super() call in a class constructor invokes the superclass’s constructor that has the corresponding argumentList. The superclass constructor initializes the inherited data fields as specified by its argumentList. The super() call must be the first statement in a constructor.

Koffman-c01.indd 10 10/30/2015 7:39:49 PM

1.2 Introduction to Object‐Oriented Programming (OOP) 11

The No‐Parameter Constructor If the execution of any constructor in a subclass does not invoke a superclass constructor, Java automatically invokes the no‐parameter constructor for the superclass. Java does this to initialize that part of the object inherited from the superclass before the subclass starts to initialize its part of the object. Otherwise, the part of the object that is inherited would remain uninitialized.

@param disk The disk size @param procSpeed The processor speed @param screen The screen size @param wei The weight

*/ public Notebook(String man, String proc, double ram, int disk, double procSpeed, double screen, double wei) { super(man, proc, ram, disk, procSpeed); screenSize = screen; weight = wei;

} }

Protected Visibility for Superclass Data Fields The data fields inherited from class Computer have private visibility. Therefore, they can be accessed only within class Computer. Because it is fairly common for a subclass method to reference data fields declared in its superclass, Java provides a less restrictive form of visibil- ity called protected visibility. A data field (or method) with protected visibility can be accessed in the class defining it, in any subclass of that class, or in any class in the same package. Therefore, if we had used the declaration

protected String manufacturer;

in class Computer, the following assignment statement would be valid in class Notebook: manufacturer = man;

P I T F A L L

Not Defining the No‐Parameter Constructor If no constructors are defined for a class, the no‐parameter constructor for that class will be provided by default. However, if any constructors are defined, the no‐parameter constructor must also be defined explicitly if it needs to be invoked. Java does not provide it automatically because it may make no sense to create a new object of that type without providing initial data field values. (It was not defined in class Notebook or Computer because we want the client to specify some information about a Computer object when that object is created.) If the no‐parameter constructor is defined in a subclass but is not defined in the superclass, you will get a syntax error constructor not defined. You can also get this error if a subclass constructor does not explicitly call a superclass constructor. There will be an implicit call to the no‐parameter superclass constructor, so it must be defined.

Koffman-c01.indd 11 10/30/2015 7:39:49 PM

12 Chapter 1 Object‐Oriented Programming and Class Hierarchies

We will use protected visibility on occasion when we are writing a class that we intend to extend. However, in general, it is better to use private visibility because subclasses may be written by different programmers, and it is always a good practice to restrict and control access to the superclass data fields. We discuss visibility further in Section 1.7.

Is‐a versus Has‐a Relationships One misuse of inheritance is confusing: the has‐a relationship with the is‐a relationship. The is‐a relationship between classes means that one class is a subclass of the other class. For example, a game computer is a computer with specific attributes that make it suitable for gaming applications (enhanced graphics, fast processor) and is a subclass of the Computer class. The is‐a relationship is achieved by extending a class.

The has‐a relationship between classes means that one class has the second class as an attrib- ute. For example, a game box is not really a computer (it is a kind of entertainment device), but it has a computer as a component. The has‐a relationship is achieved by declaring a Computer data field in the game box class.

Another issue that sometimes arises is determining whether to define a new class in a hierarchy or whether a new object is a member of an existing class. For example, netbook computers have recently become very popular. They are smaller portable computers that can be used for general‐ purpose computing but are also used extensively for Web browsing. Should we define a separate class NetBook, or is a netbook computer a Notebook object with a small screen and low weight?

E X E R C I S E S F O R S E C T I O N 1 . 2

S E L F ‐ C H E C K

1. Explain the effect of each valid statement in the following fragment. Indicate any invalid statements. Computer c1 = new Computer(); Computer c2 = new Computer("Ace", "AMD", 8.0, 500, 3.5); Notebook c3 = new Notebook("Ace", "AMD", 4.0, 500, 3.0); Notebook c4 = new Notebook("Bravo", "Intel", 4.0, 750, 3.0, 15.5, 5.5); System.out.println(c2.manufacturer + ", " + c4.processor); System.out.println(c2.getDiskSize() + ", " + c4.getRamSize()); System.out.println(c2.toString() + "\n" + c4.toString());

2. Indicate where in the hierarchy you might want to add data fields for the following and the kind of data field you would add.

Cost The battery identification Time before battery discharges Number of expansion slots Wireless Internet available

3. Can you add the following constructor to class Notebook? If so, what would you need to do to class Computer? public Notebook() {}

P R O G R A M M I N G

1. Write accessor and modifier methods for class Computer.

2. Write accessor and modifier methods for class Notebook.

Koffman-c01.indd 12 10/30/2015 7:39:49 PM

1.3 Method Overriding, Method Overloading, and Polymorphism 13

1.3 Method Overriding, Method Overloading, and Polymorphism

In the preceding section, we discussed inherited data fields. We found that we could not access an inherited data field in a subclass object if its visibility was private. Next, we consider inher- ited methods. Methods generally have public visibility, so we should be able to access a method that is inherited. However, what if there are multiple methods with the same name in a class hierarchy? How does Java determine which one to invoke? We answer this question next.

Method Overriding Let’s use the following main method to test our class hierarchy.

/** Tests classes Computer and Notebook. Creates an object of each and displays them. @param args[] No control parameters */ public static void main(String[] args) { Computer myComputer = new Computer("Acme", "Intel", 4, 750, 3.5); Notebook yourComputer = new Notebook("DellGate", "AMD", 4, 500, 2.4, 15.0, 7.5); System.out.println("My computer is:\n" + myComputer.toString()); System.out.println("\nYour computer is:\n" + yourComputer.toString()); }

In the second call to println, the method call yourComputer.toString()

applies method toString to object yourComputer (type Notebook). Because class Notebook doesn’t define its own toString method, class Notebook inherits the toString method defined in class Computer. Executing this method displays the following output lines:

My computer is: Manufacturer: Acme CPU: Intel RAM: 4.0 gigabytes Disk: 750 gigabytes Speed: 3.5 gigahertz

Your computer is: Manufacturer: DellGate CPU: AMD RAM: 4.0 gigabytes Disk: 500 gigabytes Speed: 2.4 gigahertz

Unfortunately, this output doesn’t show the complete state of object yourComputer. To show the complete state of a notebook computer, we need to define a toString method for class Notebook. If class Notebook has its own toString method, it will override the inherited method and will be invoked by the method call yourComputer.toString(). We define method toString for class Notebook next.

public String toString() { String result = super.toString() + "\nScreen size: " + screenSize + " inches" + "\nWeight: " + weight + " pounds"; return result; }

Koffman-c01.indd 13 10/30/2015 7:39:49 PM

14 Chapter 1 Object‐Oriented Programming and Class Hierarchies

This method Notebook.toString returns a string representation of the state of a Notebook object. The first line

String result = super.toString()

uses method call super.toString() to invoke the toString method of the superclass (method Computer.toString) to get the string representation of the four data fields that are inherited from the superclass. The next two lines append the data fields defined in class Notebook to this string.

SYNTAX super. FORM: super.methodName() super.methodName(argumentList)

EXAMPLE: super.toString()

MEANING: Using the prefix super. in a call to method methodName calls the method with that name defined in the superclass of the current class.

P I T F A L L

Overridden Methods Must Have Compatible Return Types If you write a method in a subclass that has the same signature as one in the superclass but a different return type, you may get the following error message: in subclass‐name cannot override method‐name in superclass‐name; attempting to use incompatible return type. The subclass method return type must be the same as or a subclass of the superclass method’s return type.

P R O G R A M S T Y L E

Calling Method toString() Is Optional In the println statement shown earlier, System.out.println("My computer is:\n" + myComputer.toString());

the explicit call to method toString is not required. The statement could be written as System.out.println("My computer is:\n" + myComputer);

Java automatically applies the toString method to an object referenced in a String expression. Normally, we will not explicitly call toString.

Koffman-c01.indd 14 10/30/2015 7:39:50 PM

1.3 Method Overriding, Method Overloading, and Polymorphism 15

Method Overloading Let’s assume we have decided to standardize and purchase our notebook computers from only one manufacturer. We could then introduce a new constructor with one less parameter for class Notebook.

public Notebook(String proc, int ram, int disk, double procSpeed, double screen, double wei) { this(DEFAULT_NB_MAN, proc, ram, disk, procSpeed, screen, wei); }

The method call this(DEFAULT_NB_MAN, proc, ram, disk, procSpeed, screen, wei);

invokes the six‐parameter constructor (see Listing 1.3), passing on the five arguments it receives and the constant string DEFAULT_NB_MAN (defined in class Notebook). The six‐ parameter constructor begins by calling the superclass constructor, satisfying the requirement that it be called first. We now have two constructors with different signatures in class Notebook. Having multiple methods with the same name but different signatures in a class is called method overloading.

Now we have two ways to create new Notebook objects. Both of the following statements are valid:

Notebook lTP1 = new Notebook("Intel", 4, 500, 1.8, 14, 6.5); Notebook lTP2 = new Notebook("MicroSys", "AMD", 4, 750, 3.0, 15, 7.5);

The manufacturer of lTP1 is DEFAULT_NB_MAN.

Listing 1.4 shows the complete class Notebook. Figure 1.5 shows the UML diagram, revised to show that Notebook has a toString method and a constant data field. The next Pitfall dis- cusses the reason for the @Override annotation preceding method toString.

L I S T I N G 1 . 4 Complete Class Notebook with Method toString

/** Class that represents a notebook computer. */ public class Notebook extends Computer { // Data Fields private static final String DEFAULT_NB_MAN = "MyBrand"; private double screenSize; private double weight;

SYNTAX this( . . . ); FORM: this(argumentList);

EXAMPLE: this(DEFAULT_NB_MAN, proc, ram, disk, procSpeed);

MEANING: The call to this() invokes the constructor for the current class whose parameter list matches the argument list. The constructor initializes the new object as specified by its arguments. The invocation of another constructor (through either this() or super()) must be the first statement in a constructor.

Koffman-c01.indd 15 10/30/2015 7:39:50 PM

16 Chapter 1 Object‐Oriented Programming and Class Hierarchies

Computer

String manufacturer String processor int ramSize int diskSize double processorSpeed

int getRamSize() int getDiskSize() double getProcessorSpeed() double computePower() String toString()

String toString()

Notebook

String DEFAULT_NB_MAN double screenSize double weight

F I G U R E 1 . 5 Revised UML Diagram for Computer Class Hierarchy

/** Initializes a Notebook object with all properties specified. @param man The computer manufacturer @param proc The processor type @param ram The RAM size @param disk The disk size @param screen The screen size @param wei The weight */ public Notebook(String man, String proc, int ram, int disk, double procSpeed, double screen, double wei) { super(man, proc, ram, disk, procSpeed); screenSize = screen; weight = wei; }

/** Initializes a Notebook object with 6 properties specified. */ public Notebook(String proc, int ram, int disk, double procSpeed, double screen, double wei) { this(DEFAULT_NB_MAN, proc, ram, disk, procSpeed, screen, wei); }

@Override public String toString() { String result = super.toString() + "\nScreen size: " + screenSize + " inches" + "\nWeight: " + weight + " pounds"; return result; } }

P I T F A L L

Overloading a Method When Intending to Override It To override a method, you must use the same name and the same number and types of the parameters as the superclass method that is being overridden. If the name is the same but the number or types of the parameters are different, then the method is overloaded instead. Normally, the compiler will not detect this as an error. However, it is a sufficiently common error that a feature was added to the Java compiler so that programmers can indicate that they intend to override a method. If you precede the declaration of the method with the annotation @Override, the compiler will issue an error message if the method is overloaded instead of overridden.

P R O G R A M S T Y L E

Precede an Overridden Method with the Annotation @Override Whenever a method is overridden, we recommend preceding it with the annotation @Override. Some Java integrated development environments such as Netbeans and Eclipse will either issue a warning or add this annotation automatically.

Koffman-c01.indd 16 10/30/2015 7:39:50 PM

1.3 Method Overriding, Method Overloading, and Polymorphism 17

Polymorphism An important advantage of OOP is that it supports a feature called polymorphism, which means many forms or many shapes. Polymorphism enables the JVM to determine at run time which of the classes in a hierarchy is referenced by a superclass variable or parameter. Next we will see how this simplifies the programming process.

Suppose you are not sure whether a computer referenced in a program will be a notebook or a regular computer. If you declare the reference variable

Computer theComputer;

you can use it to reference an object of either type because a type Notebook object can be referenced by a type Computer variable. In Java, a variable of a superclass type (general) can reference an object of a subclass type (specific). Notebook objects are Computer objects with more features. When the following statements are executed,

theComputer = new Computer("Acme", "Intel", 2, 160, 2.6); System.out.println(theComputer.toString());

you would see four output lines, representing the state of the object referenced by theComputer.

Now suppose you have purchased a notebook computer instead. What happens when the following statements are executed?

theComputer = new Notebook("Bravo", "Intel", 4, 240, 2.4. 15.0, 7.5); System.out.println(theComputer.toString());

Recall that theComputer is type Computer. Will the theComputer.toString() method call return a string with all seven data fields or just the five data fields defined for a Computer object? The answer is a string with all seven data fields. The reason is that the type of the object receiving the toString message determines which toString method is called. Even though variable theComputer is type Computer, it references a type Notebook object, and the Notebook object receives the toString message. Therefore, the method toString for class Notebook is the one called.

This is an example of polymorphism. Variable theComputer references a Computer object at one time and a Notebook object another time. At compile time, the Java compiler can’t determine what type of object theComputer will reference, but at run time, the JVM knows the type of the object that receives the toString message and can call the appropriate toString method.

EXAMPLE 1.2 If we declare the array labComputers as follows: Computer[] labComputers = new Computer[10];

each subscripted variable labComputers[i] can reference either a Computer object or a Notebook object because Notebook is a subclass of Computer. For the method call labComputers[i]. toString(), polymorphism ensures that the correct toString method is called. For each value of subscript i, the actual type of the object referenced by labComputers[i] determines which toString method will execute (Computer.toString or Notebook.toString).

Methods with Class Parameters Polymorphism also simplifies programming when we write methods that have class param- eters. For example, if we want to compare the power of two computers without polymor- phism, we will need to write overloaded comparePower methods in class Computer, one for each subclass parameter and one with a class Computer parameter. However, polymorphism enables us to write just one method with a Computer parameter.

Koffman-c01.indd 17 10/30/2015 7:39:50 PM

18 Chapter 1 Object‐Oriented Programming and Class Hierarchies

E X E R C I S E S F O R S E C T I O N 1 . 3

S E L F ‐ C H E C K

1. Explain the effect of each of the following statements. Which one(s) would you find in class Computer? Which one(s) would you find in class Notebook? super(man, proc, ram, disk, procSpeed); this(man, proc, ram, disk, procSpeed);

2. Indicate whether methods with each of the following signatures and return types (if any) would be allowed and in what classes they would be allowed. Explain your answers.

Computer() Notebook() int toString() double getRamSize() String getRamSize() String getRamSize(String) String getProcessor() double getScreenSize()

3. For the loop body in the following fragment, indicate which method is invoked for each value of i. What is printed?

Computer comp[] = new Computer[3]; comp[0] = new Computer("Ace", "AMD", 8, 750, 3.5); comp[1] = new Notebook("Dell", "Intel", 4, 500, 2.2, 15.5, 7.5); comp[2] = comp[1]; for (int i = 0; i < comp.length; i++) { System.out.println(comp[i].getRamSize() + "\n" + comp[i].toString()); }

4. When does Java determine which toString method to execute for each value of i in the for statement in the preceding question: at compile time or at run time? Explain your answer.

EXAMPLE 1.3 Method Computer.comparePowers compares the power of the Computer object it is applied to with the Computer object passed as its argument. It returns −1, 0, or +1 depending on which computer has more power. It does not matter whether this or aComputer references a Computer or a Notebook object.

/** Compares power of this computer and its argument computer @param aComputer The computer being compared to this computer @return ‐1 if this computer has less power, 0 if the same, and +1 if this computer has more power. */ public int comparePower(Computer aComputer) { if (this.computePower() < aComputer.computePower()) return ‐1; else if (this.computePower() == aComputer.computePower()) return 0; else return 1; }

Koffman-c01.indd 18 10/30/2015 7:39:51 PM

1.4 Abstract Classes 19

1.4 Abstract Classes

In this section, we introduce another kind of class called an abstract class. An abstract class is denoted by the use of the word abstract in its heading:

visibility abstract class className An abstract class differs from an actual class (sometimes called a concrete class) in two respects:

An abstract class cannot be instantiated. An abstract class may declare abstract methods.

Just as in an interface, an abstract method is declared through a method heading in the abstract class definition. This heading indicates the result type, method name, and parame- ters, thereby specifying the form that any actual method declaration must take:

visibility abstract resultType methodName(parameterList); However, the complete method definition, including the method body (implementation), does not appear in the abstract class definition.

In order to compile without error, an actual class that is a subclass of an abstract class must provide an implementation for each abstract method of its abstract superclass. The heading for each actual method must match the heading for the corresponding abstract method.

We introduce an abstract class in a class hierarchy when we need a base class for two or more actual classes that share some attributes. We may want to declare some of the attributes and define some of the methods that are common to these base classes. If, in addition, we want to require that the actual subclasses implement certain methods, we can accomplish this by making the base class an abstract class and declaring these methods abstract.

P R O G R A M M I N G

1. Write constructors for both classes that allow you to specify only the processor, RAM size, and disk size.

2. Complete the accessor and modifier methods for class Computer.

3. Complete the accessor and modifier methods for class Notebook.

EXAMPLE 1.4 The Food Guide Pyramid provides a recommendation of what to eat each day based on established dietary guidelines. There are six categories of foods in the pyramid: fats, oils, and sweets; meats, poultry, fish, and nuts; milk, yogurt, and cheese; vegetables; fruits; and bread, cereal, and pasta. If we wanted to model the Food Guide Pyramid, we might have each of these as actual subclasses of an abstract class called Food:

/** Abstract class that models a kind of food. */ public abstract class Food { // Data Field private double calories;

// Abstract Methods /** Calculates the percent of protein in a Food object. */

Koffman-c01.indd 19 10/30/2015 7:39:51 PM

20 Chapter 1 Object‐Oriented Programming and Class Hierarchies

public abstract double percentProtein(); /** Calculates the percent of fat in a Food object. */ public abstract double percentFat(); /** Calculates the percent of carbohydrates in a Food object. */ public abstract double percentCarbohydrates();

// Actual Methods public double getCalories() { return calories; } public void setCalories(double cal) { calories = cal; } }

The three abstract method declarations public abstract double percentProtein(); public abstract double percentFat(); public abstract double percentCarbohydrates();

impose the requirement that all actual subclasses implement these three methods. We would expect a different method definition for each kind of food. The keyword abstract must appear in all abstract method declarations in an abstract class. Recall that this is not required for abstract method declarations in interfaces.

SYNTAX Abstract Class Definition FORM: public abstract class className { data field declarations abstract method declarations actual method definitions }

EXAMPLE: public abstract class Food { // Data Field private double calories;

// Abstract Methods public abstract double percentProtein(); public abstract double percentFat(); public abstract double percentCarbohydrates();

// Actual Methods public double getCalories() { return calories; } public void setCalories(double cal) { calories = cal; }

}

INTERPRETATION: Abstract class className is defined. The class body may have declarations for data fields and abstract methods as well as actual method definitions. Each abstract method declaration consists of a method heading containing the keyword abstract. All of the declaration kinds shown above are optional.

Koffman-c01.indd 20 10/30/2015 7:39:51 PM

1.4 Abstract Classes 21

Referencing Actual Objects Because class Food is abstract, you can’t create type Food objects. However, you can use a type Food variable to reference an actual object that belongs to a subclass of type Food. For exam- ple, an object of type Vegetable can be referenced by a Vegetable or Food variable because Vegetable is a subclass of Food (i.e., a Vegetable object is also a Food object).

EXAMPLE 1.5 The following statement creates a Vegetable object that is referenced by variable mySnack (type Food).

Food mySnack = new Vegetable("carrot sticks");

Initializing Data Fields in an Abstract Class An abstract class can’t be instantiated. However, an abstract class can have constructors that initialize its data fields when a new subclass object is created. The subclass constructor will use super(...) to call such a constructor.

Abstract Class Number and the Java Wrapper Classes The abstract class Number is predefined in the Java class hierarchy. It has as its subclasses all the wrapper classes for primitive numeric types (e.g., Byte, Double, Integer, and Short). A wrapper class is used to store a primitive‐type value in an object type. Each wrapper class contains constructors to create an object that stores a particular primitive‐type value. For example, Integer(35) or Integer("35") creates a type Integer object that stores the int 35. A wrapper class also has methods for converting the value stored to a different numeric type.

Figure 1.6 shows a portion of the class hierarchy with base class Number. Italicizing the class name Number in its class box indicates that Number is an abstract class and, therefore, cannot be instantiated. Listing 1.5 shows part of the definition for class Number. Two abstract meth- ods are declared (intValue and doubleValue), and one actual method (byteValue) is defined.

Number

Byte Double Integer Short

F I G U R E 1 . 6 The Abstract Class Number and Selected Subclasses

P I T F A L L

Omitting the Definition of an Abstract Method in a Subclass If you write class Vegetable and forget to define method percentProtein, you will get the syntax error class Vegetable should be declared abstract, it does not define method percentProtein in class Food. Although this error message is misleading (you did not intend Vegetable to be abstract), any class with undefined methods is abstract by definition. The compiler’s rationale is that the undefined method is intentional, so Vegetable must be an abstract class, with a subclass that defines percentProtein.

Koffman-c01.indd 21 10/30/2015 7:39:51 PM

22 Chapter 1 Object‐Oriented Programming and Class Hierarchies

In the actual implementation of Number, the body of byteValue would be provided, but we just indicate its presence in Listing 1.5.

L I S T I N G 1 . 5 Part of Abstract Class java.lang.Number

public abstract class Number { // Abstract Methods /** Returns the value of the specified number as an int. @return The numeric value represented by this object after conversion to type int */ public abstract int intValue(); /** Returns the value of the specified number as a double. @return The numeric value represented by this object after conversion to type double */ public abstract double doubleValue();

...

// Actual Methods /** Returns the value of the specified number as a byte. @return The numeric value represented by this object after conversion to type byte */ public byte byteValue() { // Implementation not shown. ... } }

Summary of Features of Actual Classes, Abstract Classes, and Interfaces It is easy to confuse abstract classes, interfaces, and actual classes (concrete classes). Table 1.1 summarizes some important points about these constructs.

A class (abstract or actual) can extend only one other class; however, there is no restriction on the number of interfaces a class can implement. An interface cannot extend a class.

TA B L E 1 . 1 Comparison of Actual Classes, Abstract Classes, and Interfaces

Property Actual Class Abstract Class Interface

Instances (objects) of this can be created Yes No No

This can define instance variables Yes Yes No

This can define methods Yes Yes Yes

This can define constants Yes Yes Yes

The number of these a class can extend 0 or 1 0 or 1 0

The number of these a class can implement 0 0 Any number

This can extend another class Yes Yes No

This can declare abstract methods No Yes Yes

Variables of this type can be declared Yes Yes Yes

Koffman-c01.indd 22 10/30/2015 7:39:51 PM

1.4 Abstract Classes 23

An abstract class may implement an interface just as an actual class does, but unlike an actual class, it doesn’t have to define all of the methods declared in the interface. It can leave the implementation of some of the abstract methods to its subclasses.

Both abstract classes and interfaces declare abstract methods. However, unlike an interface, an abstract class can also have data fields and methods that are not abstract. You can think of an abstract class as combining the properties of an actual class, by providing inherited data fields and methods to its subclasses, and of an interface, by specifying requirements on its subclasses through its abstract method declarations.

Implementing Multiple Interfaces A class can extend only one other class, but it may extend more than one interface. For exam- ple, assume interface StudentInt specifies methods required for student‐like classes and inter- face EmployeeInt specifies methods required for employee‐like classes. The following header for class StudentWorker

public class StudentWorker implements StudentInt, EmployeeInt

means that class StudentWorker must define (provide code for) all of the abstract methods declared in both interfaces. Therefore, class StudentWorker supports operations required for both interfaces.

Extending an Interface Interfaces can also extend other interfaces. In Chapter 2 we will introduce the Java Collection Framework. This class hierarchy contains several interfaces and classes that manage the col- lection of objects. At the top of this hierarchy is the interface Iterable, which declares the method iterator. At the next lower level is interface Collection, which extends Iterable. This means that all classes that implement Collection must also implement Iterable and therefore must define the method iterator.

An interface can extend more than one other interface. In this case, the resulting interface includes the union of the methods defined in the superinterfaces. For example, we can define the interface ComparableCollection, which extends both Comparable and Collection, as follows:

public interface ComparableCollection extends Comparable, Collection { }

Note that this interface does not define any methods itself but does require any implementing class to implement all of the methods required by Comparable and by Collection.

E X E R C I S E S F O R S E C T I O N 1 . 4

S E L F ‐ C H E C K

1. What are two important differences between an abstract class and an actual class? What are the similarities?

2. What do abstract methods and interfaces have in common? How do they differ?

3. Explain the effect of each statement in the following fragment and trace the loop execu- tion for each value of i, indicating which doubleValue method executes, if any. What is the final value of x? Number[] nums = new Number[5]; nums[0] = new Integer(35); nums[1] = new Double(3.45); nums[4] = new Double("2.45e6"); double x = 0;

Koffman-c01.indd 23 10/30/2015 7:39:51 PM

24 Chapter 1 Object‐Oriented Programming and Class Hierarchies

1.5 Class Object and Casting

The class Object is a special class in Java because it is the root of the class hierarchy, and every class has Object as a superclass. All classes inherit the methods defined in class Object; however, these methods may be overridden in the current class or in a superclass (if any). Table 1.2 shows a few of the methods of class Object. We discuss method toString next and the other Object methods shortly thereafter.

The Method toString You should always override the toString method if you want to represent an object’s state (information stored). If you don’t override it, the toString method for class Object will exe- cute and return a string, but not what you are expecting.

for (int i = 0; i < nums.length; i++) { if (nums[i] != null) x += nums[i].doubleValue(); }

4. What is the purpose of the if statement in the loop in Question 3? What would happen if it were omitted?

P R O G R A M M I N G

1. Write class Vegetable. Assume that a vegetable has three double constants: VEG_FAT_CAL, VEG_PROTEIN_CAL, and VEG_CARBO_CAL. Compute the fat percentage as VEG_FAT_CAL div ided by the sum of all the constants.

2. Earlier we discussed a Computer class with a Notebook class as its only subclass. However, there are many different kinds of computers. An organization may have servers, main- frames, desktop PCs, and notebooks. There are also personal data assistants and game computers. So it may be more appropriate to declare class Computer as an abstract class that has an actual subclass for each category of computer. Write an abstract class Computer that defines all the methods shown earlier and declares an abstract method with the signa- ture costBenefit(double) that returns the cost–benefit (type double) for each category of computer.