Transcript Chapter 9

Polymorphism
Chapter
5TH EDITION
Lewis & Loftus
java
Software Solutions
Foundations of Program Design
© 2007 Pearson Addison-Wesley. All rights reserved
9
Polymorphism
• Polymorphism is an object-oriented concept that
allows us to create versatile software designs
• Chapter 9 focuses on:




defining polymorphism and its benefits
using inheritance to create polymorphic references
using interfaces to create polymorphic references
using polymorphism to implement sorting and searching
algorithms
 additional GUI components*
Outline
Polymorphic References
Polymorphism via Inheritance
Polymorphism via Interfaces
Sorting
Searching
Event Processing Revisited
File Choosers and Color Choosers
Sliders
Binding
• Consider the following method invocation:
obj.doIt();
• At some point, this invocation is bound to the
definition of the method that it invokes
• If this binding occurred at compile time, then that
line of code would call the same method every
time
• However, Java defers method binding until run
time -- this is called dynamic binding or late
binding
• Late binding provides flexibility in program design
Polymorphism
• The term polymorphism literally means "having
many forms"
• A polymorphic reference is a variable that can
refer to different types of objects at different
points in time
• The method invoked through a polymorphic
reference can change from one invocation to the
next
• All object references in Java are potentially
polymorphic
 Why?
Polymorphism
• Suppose we create the following reference
variable:
Occupation job;
• Java allows this reference to point to an
Occupation object, or to any object of any
compatible type
• This compatibility can be established using
inheritance or using interfaces
• Careful use of polymorphic references can lead to
elegant, robust software designs
Outline
Polymorphic References
Polymorphism via Inheritance
Polymorphism via Interfaces
Sorting
Searching
Event Processing Revisited
File Choosers and Color Choosers
Sliders
References and Inheritance
• An object reference can refer to an object of its
class, or to an object of any class related to it by
inheritance
• For example, if the Holiday class is used to derive
a class called Christmas, then a Holiday reference
could be used to point to a Christmas object
Holiday
Holiday day;
day = new Christmas();
Christmas
References and Inheritance
• Assigning a child object to a parent reference is
considered to be a widening conversion, and can
be performed by simple assignment
• Assigning an parent object to a child reference can
be done also, but it is considered a narrowing
conversion and must be done with a cast
• The widening conversion is the most useful
Polymorphism via Inheritance
• It is the type of the object being referenced, not the
reference type, that determines which method is
invoked
• Suppose the Holiday class has a method called
celebrate, and the Christmas class overrides it
• Now consider the following invocation:
 Holiday day;
 day = new Christmas();
 day.celebrate();
• If day refers to a Holiday object, it invokes the
Holiday version of celebrate; if it refers to a
Christmas object, it invokes the Christmas
version
Polymorphism via Inheritance
• Consider the following class hierarchy:
StaffMember
Volunteer
Employee
Executive
Hourly
Polymorphism via Inheritance
• Now let's look at an example that pays a set of
diverse employees using a polymorphic method
•
•
•
•
•
•
•
See Firm.java (page 488)
See Staff.java (page 489)
See StaffMember.java (page 491)
See Volunteer.java (page 493)
See Employee.java (page 494)
See Executive.java (page 495)
See Hourly.java (page 496)
public class Staff
{
private StaffMember[] staffList;
public Staff ()
{
staffList = new StaffMember[6];
staffList[0] = new Executive ("Sam", "123 Main Line",
"555-0469", "123-45-6789", 2423.07);
staffList[1] = new Employee ("Carla", "456 Off Line",
"555-0101", "987-65-4321", 1246.15);
staffList[2] = new Employee ("Woody", "789 Off Rocker",
"555-0000", "010-20-3040", 1169.23);
staffList[3] = new Hourly ("Diane", "678 Fifth Ave.",
"555-0690", "958-47-3625", 10.55);
staffList[4] = new Volunteer ("Norm", "987 Suds Blvd.",
"555-8374");
staffList[5] = new Volunteer ("Cliff", "321 Duds Lane",
"555-7282");
((Executive)staffList[0]).awardBonus (500.00); // narrowing conversion by casting
((Hourly)staffList[3]).addHours (40);
}
Staff continued…
public void payday ()
{
double amount;
for (int count=0; count < staffList.length; count++)
{
System.out.println (staffList[count]);
amount = staffList[count].pay(); // polymorphic, no casting is needed here (WHY?)
if (amount == 0.0)
System.out.println ("Thanks!");
else
System.out.println ("Paid: " + amount);
System.out.println ("-----------------------------------");
}
}
}
abstract public class StaffMember
{
protected String name;
protected String address;
protected String phone;
public StaffMember (String eName, String eAddress, String ePhone)
{
name = eName;
address = eAddress;
phone = ePhone;
}
…
public abstract double pay();
}
public class Volunteer extends StaffMember
{
//----------------------------------------------------------------// Constructor: Sets up this volunteer using the specified
// information.
//----------------------------------------------------------------public Volunteer (String eName, String eAddress, String ePhone)
{
super (eName, eAddress, ePhone);
}
//----------------------------------------------------------------// Returns a zero pay value for this volunteer.
//----------------------------------------------------------------public double pay()
{
return 0.0;
}
}
public class Employee extends StaffMember
{
protected String socialSecurityNumber;
protected double payRate;
public Employee (String eName, String eAddress, String ePhone, String socSecNumber,
double rate)
{
super (eName, eAddress, ePhone);
socialSecurityNumber = socSecNumber;
payRate = rate;
}
…
public double pay()
{
return payRate;
}
}
public class Executive extends Employee
{
private double bonus;
public Executive (String eName, String eAddress, String ePhone,
String socSecNumber, double rate)
{
super (eName, eAddress, ePhone, socSecNumber, rate);
bonus = 0; // bonus has yet to be awarded
}
public void awardBonus (double execBonus)
{
bonus = execBonus;
}
public double pay()
{
double payment = super.pay() + bonus;
bonus = 0;
return payment;
}
}
Outline
Polymorphic References
Polymorphism via Inheritance
Polymorphism via Interfaces
Sorting
Searching
Event Processing Revisited
File Choosers and Color Choosers
Sliders
Polymorphism via Interfaces
• An interface name can be used as the type of an
object reference variable
Speaker current;
• The current reference can be used to point to any
object of any class that implements the Speaker
interface
• The version of speak that the following line
invokes depends on the type of object that
current is referencing
current.speak();
Polymorphism via Interfaces
• Suppose two classes, Philosopher and Dog, both
implement the Speaker interface, providing
distinct versions of the speak method
• In the following code, the first call to speak
invokes one version and the second invokes
another:
Speaker guest = new Philospher();
// Cannot new an interface!!
guest.speak();
guest = new Dog();
guest.speak();
Outline
Polymorphic References
Polymorphism via Inheritance
Polymorphism via Interfaces
Sorting
Searching
Event Processing Revisited
File Choosers and Color Choosers
Sliders
Sorting
• Sorting is the process of arranging a list of items
in a particular order
• The sorting process is based on specific value(s)
 sorting a list of test scores in ascending numeric order
 sorting a list of people alphabetically by last name
• There are many algorithms, which vary in
efficiency, for sorting a list of items
• We will examine the Selection sort algorithms:
 The book also discusses Insertion Sort, but you are not
responsible for that
Selection Sort
• The approach of Selection Sort:
 select a value and put it in its final place into the list
 repeat for all other values
• In more detail:
 find the smallest value in the list
 switch it with the value in the first position
 find the next smallest value in the list
 switch it with the value in the second position
 repeat until all values are in their proper places
Selection Sort
• An example:
original:
smallest is
smallest is
smallest is
smallest is
1:
2:
3:
6:
3
1
1
1
1
9
9
2
2
2
6
6
6
3
3
1
3
3
6
6
2
2
9
9
9
• Each time, the smallest remaining value is found
and exchanged with the element in the "next"
position to be filled
Swapping
• The processing of the selection sort algorithm
includes the swapping of two values
• Swapping requires three assignment statements
and a temporary storage location:
temp = first;
first = second;
second = temp;
Polymorphism in Sorting
• Recall that an class that implements the
Comparable interface defines a compareTo
method to determine the relative order of its
objects
• We can use polymorphism to develop a generic
sort for any set of Comparable objects
• The sorting method accepts as a parameter an
array of Comparable objects
• That way, one method can be used to sort a group
of People, or Books, or whatever
Selection Sort
• The sorting method doesn't "care" what it is
sorting, it just needs to be able to call the
compareTo method
• That is guaranteed by using Comparable as the
parameter type
• Also, this way each class decides for itself what it
means for one object to be less than another
• See PhoneList.java (page 502) // driver class
• See Sorting.java (page 503), specifically the
selectionSort method
• See Contact.java (page 505)
public class PhoneList
{ //----------------------------------------------------------------// Creates an array of Contact objects, sorts them, then prints
// them.
//----------------------------------------------------------------public static void main (String[] args)
{
Contact[] friends = new Contact[8];
friends[0] = new Contact ("John", "Smith", "610-555-7384");
friends[1] = new Contact ("Sarah", "Barnes", "215-555-3827");
friends[2] = new Contact ("Mark", "Riley", "733-555-2969");
friends[3] = new Contact ("Laura", "Getz", "663-555-3984");
friends[4] = new Contact ("Larry", "Smith", "464-555-3489");
friends[5] = new Contact ("Frank", "Phelps", "322-555-2284");
friends[6] = new Contact ("Mario", "Guzman", "804-555-9066");
friends[7] = new Contact ("Marsha", "Grant", "243-555-2837");
Sorting.selectionSort(friends); // This will change the order of contact objects in friends
for (Contact friend : friends)
System.out.println (friend);
}
}
public class Sorting
{
//----------------------------------------------------------------// Sorts the specified array of objects using the selection
// sort algorithm.
//----------------------------------------------------------------public static void selectionSort (Comparable[] list) // Static method
{
int min;
Comparable temp;
for (int index = 0; index < list.length-1; index++) // Why -1?
{
min = index;
for (int scan = index+1; scan < list.length; scan++)
if (list[scan].compareTo(list[min]) < 0)
min = scan;
// Swap the values
temp = list[min];
list[min] = list[index];
list[index] = temp;
}
}
public class Contact implements Comparable
{
private String firstName, lastName, phone;
public Contact (String first, String last, String telephone)
{ firstName = first;
lastName = last;
phone = telephone;
}
public boolean equals (Object other) // overriding equals() inherited from Object class
{ return (lastName.equals(((Contact)other).getLastName()) &&
firstName.equals(((Contact)other).getFirstName()));
}
public int compareTo (Object other) // implement the interface method
{
int result;
String otherFirst = ((Contact)other).getFirstName();
String otherLast = ((Contact)other).getLastName();
if (lastName.equals(otherLast))
result = firstName.compareTo(otherFirst); // the compareTo method of String
else
result = lastName.compareTo(otherLast); // the compareTo method of String
return result;
Outline
Polymorphic References
Polymorphism via Inheritance
Polymorphism via Interfaces
Sorting
Searching
Event Processing Revisited
File Choosers and Color Choosers
Sliders
Searching
• Searching is the process of finding a target
element within a group of items called the search
pool
• The target may or may not be in the search pool
• We want to perform the search efficiently,
minimizing the number of comparisons
• Let's look at two classic searching approaches:
linear search and binary search
• As we did with sorting, we'll implement the
searches with polymorphic Comparable
parameters
Linear Search
• A linear search begins at one end of a list and
examines each element in turn
• Eventually, either the item is found or the end of
the list is encountered
• See PhoneList2.java (page 510)
• See Searching.java (page 511), specifically the
linearSearch method
Binary Search
• A binary search assumes the list of items in the
search pool is sorted
• It eliminates a large part of the search pool with a
single comparison
• A binary search first examines the middle element
of the list -- if it matches the target, the search is
over
• If it doesn't, only one half of the remaining
elements need be searched
• Since they are sorted, the target can only be in one
half of the other
Binary Search
• The process continues by comparing the middle
element of the remaining viable candidates
• Each comparison eliminates approximately half of
the remaining data
• Eventually, the target is found or the data is
exhausted
• See PhoneList2.java (page 510)
• See Searching.java (page 511), specifically the
binarySearch method
Summary
• Chapter 9 has focused on:




defining polymorphism and its benefits
using inheritance to create polymorphic references
using interfaces to create polymorphic references
using polymorphism to implement sorting and searching
algorithms
 additional GUI components
Recommendation
• We did not get to cover the material in chapter 10.
If you are a CS major, you should read this chapter
some time at your leisure after the course is over.
Please feel free to ask me questions about that
chapter.
Redo from Chapter 6
• Comments on Parameter passing
 Pages 331-333
Objects as Parameters
• Parameters in a Java method are passed by value
• A copy of the actual parameter (the value passed
in) is stored into the formal parameter (in the
method header)
• Therefore passing parameters is similar to an
assignment statement
• When an object is passed to a method, the actual
parameter and the formal parameter become
aliases of each other
Passing Objects as Parameters
When an object is passed to a method, the actual
parameter and the formal parameter become aliases
of each other
objA.doThis( objActualParam );
doThis( Object objFormalParam )
{
memory …
address };
The object.
is what
is passed
example 
r3 = r1.add(r2);
r2 object of type
Rational
Passing Objects to Methods
• What a method does with a parameter may or may
not have a permanent effect (outside the method)
• See ParameterTester.java (page 331)
• See ParameterModifier.java (page 333)
• See Num.java (page 334)
• Note the difference between changing the internal
state of an object versus changing which object a
reference points to
public class ParameterTester
{
public static void main (String[] args)
{
ParameterModifier modifier = new ParameterModifier();
int a1 = 111;
Num a2 = new Num (222);
Num a3 = new Num (333);
System.out.println ("Before calling changeValues:");
System.out.println ("a1\ta2\ta3");
System.out.println (a1 + "\t" + a2 + "\t" + a3 + "\n");
modifier.changeValues (a1, a2, a3);
System.out.println ("After calling changeValues:");
System.out.println ("a1\ta2\ta3");
System.out.println (a1 + "\t" + a2 + "\t" + a3 + "\n");
}
}
public class Num
{
private int value;
//----------------------------------------------------------------// Sets up the new Num object, storing an initial value.
//----------------------------------------------------------------public Num (int update)
{
value = update;
}
//----------------------------------------------------------------// Sets the stored value to the newly specified value.
//----------------------------------------------------------------public void setValue (int update)
{
value = update;
}
//----------------------------------------------------------------// Returns the stored integer value as a string.
//----------------------------------------------------------------public String toString ()
{
return value + "";
}
}
public class ParameterModifier
{
//----------------------------------------------------------------// Modifies the parameters, printing their values before and
// after making the changes.
//----------------------------------------------------------------public void changeValues (int f1, Num f2, Num f3)
{
System.out.println ("Before changing the values:");
System.out.println ("f1\tf2\tf3");
System.out.println (f1 + "\t" + f2 + "\t" + f3 + "\n");
f1 = 999;
f2.setValue(888); // change the object’s internal state
f3 = new Num (777); // change the object the reference points to
System.out.println ("After changing the values:");
System.out.println ("f1\tf2\tf3");
System.out.println (f1 + "\t" + f2 + "\t" + f3 + "\n");
}
}
Parameter tracing
Step 1
Before invoking changeValues
a1
a2
111
f1
a3
333
222
f2
f3
Step 2
tester.changeValues (a1, a2, a3);
a1
a2
111
= undefined
f1
111
a3
333
222
f2
f3
Parameter tracing
Step 3
f1 = 999;
a1
a2
111
f1
a3
333
222
f2
f3
999
Step 4
f2.setValue (888);
a1
a2
111
f1
999
a3
333
888
f2
f3
Parameter tracing
Step 5
f3 = new Num (777) ;
a1
a2
111
f1
999
a3
333
888
f2
f3
777
Step 6
After returning from changeValues
a1
a2
111
f1
a3
333
888
f2
f3
pass by value - pass by reference
pass by value
data
variable
pass by reference
objects
Step 2
tester.changeValues (a1, a2, a3);
pass
by value
a1
pass by reference
a2
a3
111
f1
111
333
222
f2
f3
Arrays as Parameters
• An entire array can be passed as a parameter to a
method
• Like any other object, the reference to the array is
passed, making the formal and actual parameters
aliases of each other
• Therefore, changing an array element within the
method changes the original (see selectionSort())
• An individual array element can be passed to a
method as well, in which case the type of the
formal parameter is the same as the element type
Final Exam (Aug. 3rd)
•
•
•
•
Comprehensive (Chapters 1-9)
True/False questions
Programming questions
1~2 Essay questions and 2 bonus questions
 You can select only one from the two bonus questions.
 One of the bonus questions requires the knowledge in
Exception handling (Chapter 10)…
• The three kinds of errors we will typically
encounter during program development
• Operator precedence in Java
• Data conversion (narrowing and widening, casting
(int))
• Overloading of ‘/’ and ‘+’
Final Exam (Aug. 3rd)
• Conditional statements (if-else, if-elseif, switch)
• Loops (while, do-while, for)
 Dead lock
• Array operations (1-dimension, two-dimension…)
• String methods (charAt, subString, compareTo,
indexOf…)
• Visibility modifiers (public, private, protected)
• Class definition and manipulation





Constructors
Static members
Method overloading
Method overriding
Interface
• Three kinds of relationship between classes
Final Exam (Aug. 3rd)
• Inheritance








super, this
A parent’s constructor cannot be inherited.
Method overriding
Object class (toString, equals)
Inheritance hierarchy
Comparable interface (compareTo)
Implement an interface
Abstract class
Final Exam (Aug. 3rd)
• Polymorphism
 Dynamic binding
 A reference variable can refer to any object created from
any class related to it by inheritance
 The type of the object, not the type of the object
reference, is used to determine which version of a
method to invoke
 Selection sort
• Assume that q, x, y, and z are int variables with x =
1, y = 10, z = -3. Which of the following is true after
the following statement is executed? q = (x++ * y-) + ++z;
A.
B.
C.
D.
E.
q=7
q = 16
q = 22
q=8
q = 17
• Assume that Student, Employee and Retired are all extended
classes of Person, and all four classes have different
implementations of the method getMoney. Consider the
following code where … are the required parameters for the
constructors:
Person p = new Person(…);
int m1 = p.getMoney( );
p = new Student(…);
int m2 = p.getMoney( );
if (m2 < 100000) p = new Employee(…);
else if (m1 > 50000) p = new Retired(…);
int m3 = p.getMoney( );
public class Inherit
{
abstract class Figure
{
void display( )
{
System.out.println("Figure");
}
}
abstract class Rectangle extends Figure
{
}
class Box extends Rectangle
{
void display( )
{
System.out.println("Rectangle");
}
}
Inherit( )
{
Inherit( ) // constructor
{
Figure f = (Figure) new Box( );
f.display( );
Rectangle r = (Rectangle) f;// will succeed because there
r.display( );
}
public static void main(String[ ] args)
{
new Inherit( );
}
}