Version 2.21
Handouts:
null."Another fundamental principle of object-oriented software" — Lewis and Loftus
Polymorphism means having many forms. "A polymorphic reference is a reference variable that can refer to different types of objects" at different times; consequently, in a method invocation like a.foo(), where a is a polymorphic reference, the precise method which is invoked can vary depending on the type of object.
Binding is the decision to connect a method call with a particular method definition. Sometimes binding can be done at compile time. But if the reference is polymorphic, it cannot, and we use late binding or dynamic binding. Late binding is less efficient than compile-time binding, but the overhead is generally justified by the increased flexibility.
We can create a polymorphic reference either when a variable is declared with a class as its type, or with an interface as its type.
Assume C is a subclass of B, and B is a subclass of A.
A a = new A();
A a = new B();
A a = new C();All of the above statements are allowed, since B and C are subtypes of A.
(The textbook uses the Animal/Mammal/Horse example.)
a.foo() may refer to a different definition of foo, depending on the type of object referenced by a.
See Figure 10.1, showing some classes related to a company's personnel; it includes a hierarchy of StaffMembers. Observe how the notation shows that: Firm uses Staff; Staff has a StaffMember; StaffMember is an abstract class; Volunteer and Employee are subclasses of StaffMember; and Executive and Hourly are subclasses of Employee.
Listings 10.1-10.7:
Firm: creates a new Staff.Staff: has an array of StaffMember, the members of which are polymorphic variants of the StaffMember type, such as Volunteer and Executive.
payday method iterates through the array, and prints each employee and his/her pay.StaffMember: abstract class; each has a name, address, and phone; defines constructor and toString method; declares abstract method pay.Volunteers are paid 0.0.Employees are paid a fixed salary.Executives are paid a fixed salary plus a bonus.Hourly employees are paid at a fixed rate per hour.Assume ShowXML is an interface which the Account and Customer classes implement. Then we can create polymorphic references using the interface as a type, e.g.:
ShowXML s;
s = new Account();
s = new Customer();Just as with inheritance-based polymorphism, the statement s.showXML() calls one method or another, depending on the run-time object referenced by the variable s.
(No program-length example.)
We consider two sorting algorithms, without going much into the analysis of the algorithms.
To sort a list (array) of n elements:
for i from 0 to n - 2 (sic)
ismall = index of smallest element in list[i+1 ... n-2]
swap list[i] with list[ismall]See Figure 10.2.
The selection sort is polymorphic, accepting any array of Comparable objects. Contact implements Comparable. Review what the compareTo method is supposed to do. Note that the argument is declared Object, not Contact. If we wanted to sort primitive data, we'd need a wrapper class, such as Integer; all of the wrapper classes implement Comparable.
How is finding the smallest element done?
Go through an example in some detail, maybe the one in Fig. 10.2.
To sort a list (array) of n elements:
for i from 1 (sic) to n - 1:
insert list[i] in its proper position within list[0..i]See Figure 10.3.
Invariant: list[0..i−1] is sorted, list[i..n−1] is unsorted. At the loop's termination, i = n − 1, so list[0..n−1] is sorted, meaning the whole thing is sorted.]
Listing 10.9(b) Sorting: also contains a polymorphic implementation of insertionSort. Demonstrate by modifying PhoneList.java to use insertionSort rather than selectionSort.
How is insertion into the proper place done?
Go through an example in some detail, maybe the one in Fig. 10.3.
Both sorts have nested loops where the outer loop executes about n times and the inner loop up to n times for each outer loop iteration; so the running time is proportional to about n2. We say that the running time of the selection sort and insertion sort algorithms is "order [of] n2" (Lewis and Loftus), or O(n2). More efficient sorting algorithms exist, with running time O(n log n).
Still, there may be slight differences in running time, since selection sort makes fewer swaps than insertion sort.
The class java.util.Arrays has methods for sorting and searching.
BREAK
Searching means finding a target value in a collection, such as an array.
Linear search begins at the beginning of the array and checks each element in sequence, stopping when it finds the target element (success) or runs off the end of the array (failure).
Listings 10.11-10.12 PhoneList2/Searching: creates an array of Contacts, creates a target object
new Contact("Frank", "Phelps", "")and searches for it with linear search. Then sorts the array and searches for the target with binary search (defer).
Explain why Frank has no telephone number.
How does equals work for Contacts?
The linear search implementation returns null if the target is not found.
Binary search requires the array to be sorted before it begins. It first looks in the middle of the array, and compares the middle value with the target value. If they are equal, we are done. Otherwise, if the target is present in the array at all, it must be at an index less than the midpoint if target < midvalue, or at an index greater than midpoint if target > midvalue. We then adjust the bounds of the search space (which initially are the whole array) to the lower or upper region, and repeat. The search stops, unsuccessfully, if the search space shrinks to nothing (becomes empty).
Listing 10.12 Searching implements binarySearch, returning null in case of failure.
How does the implementation find the middle element?
How does it reduce the search space?
Discuss invariant, pre- and post-conditions, and termination.
Discuss the natural recursive solution. After examining the midpoint, we are either done or have a sub-problem of the same type as the original problem. So we can use the same method to solve it, right? Such methods (which call themselves) are said to be recursive.
Details:
public static Comparable binarySearch (Comparable [] list, Comparable target)
{
...
}
public static Comparable binarySearch (Comparable [] list, Comparable target,
int lo, int hi)
{
...
}In what way are the two searches (linear and binary) polymorphic? Is this done using inheritance or interfaces?
Comparing searches:
Use polymorphism when different kinds of objects perform the same type of behavior, but in different ways. Use inheritance when it makes sense to say each type of object "is a" special case of some super-type. Otherwise use interfaces.
An example: many different shapes, each can be drawn or filled.
Polymorphism makes it possible to define the JButton addActionListener method, using ActionListener as the argument type, so that previously undefined classes can be added to a JButton as ActionListeners. (Explain.)
The remaining material has little or no relation to polymorphism!
Constructor: JFileChooser()
Methods: int showOpenDialog()
Constants: int JFileChooser.APPROVE_OPTION
See Listing 10.13 DisplayFile
Discuss making a subclass that remembers directories.
Static method: Color JColorChooser.showDialog(...)
See Listing 10.14 DisplayColor
Sliders can be used to input numerical values restricted to a range (or to display numerical values similarly restricted.
Constructor:
JSlider(orientation, min, max, initial)where orientation = JSlider.HORIZONTAL or JSlider.VERTICAL; min, max, and initial are ints.
Tick marks (methods setMajorTickSpacing, setMinorTickSpacing, setPaintTicks).
Method setPaintLabels controls whether to display the numerical values at the major tick marks.
Method getValue returns the int value of the slider.
(There's also setValue?)
ChangeListener interface declares the stateChanged method.
Listings 10.15-10.16 SlideColor/SlideColorPanel
Exercises:
Programming Projects: