Transcript unit17cs304ch21x

Unit 17
Template
Summary prepared by Kirk Scott
1
One half of a bronze mold for casting a socketed spear head
dated to the period 1400-1000 BC. There are no known parallels
for this mold.
2
Stone mold of the Bronze Age used to
produce spear tips
3
Design Patterns in Java
Chapter 21
Template Method
Summary prepared by Kirk Scott
4
The Introduction Before the
Introduction
• In this unit I will only cover the first example
given by the book, sorting, taken from the
Java API
• The book ends that discussion with an
example with rockets, which will be covered
5
• Next, the book develops some examples using
rockets which apply the template pattern to
an operation other than sorting
• Those examples will not be covered
• You will only be responsible for the template
design pattern as illustrated by sorting
6
• The Template design pattern, at heart, is not
very complicated
• The idea can be summarized as follows:
• You write the code for the outline of an
algorithm, leaving certain steps of the
algorithm as calls to other methods
7
• If the overall algorithm is complex, this is a
divide and conquer approach to code writing
• Whether the algorithm is complex or not, the
pattern has another potential benefit which is
actually more important
• The overall algorithm may be designed
generally so that it can apply to multiple kinds
of objects
8
• The changes needed for specific kinds of
objects can be implemented in the subparts
• The subparts could also be altered so that
they accomplish something different, or in a
different way, without changing the overall
outline of the algorithm
9
Book Definition of Pattern
• Book definition:
• The intent of the Template Method is to
implement an algorithm in a method,
deferring the definition of some steps of the
algorithm so that other classes can redefine
them.
10
A Classic Example: Sorting
• Sorting provides a good example where the
template method can be applied
• There are many different sorting algorithms
• These would be templates
• Each algorithm depends on the ability to do
pairwise comparisons
• How the pairwise comparison is done is the
subpart of the implementation of the
algorithm overall
11
Multiple Templates
• Here is one perspective on the design pattern
• You might have multiple templates
• You could implement a template for quick sort,
for example
• You could also implement a template for merge
sort
• Each template could rely on the same method
that supported the pairwise comparison of the
values or objects to be sorted
12
Multiple Subparts
• Here is another perspective on the design
pattern
• Given one template, you might also be
interested in varying implementations of the
subpart
• For example, assume for a moment that you
are just interested in merge sort
13
• You might be interested in applying the
sorting template to different kinds of objects
• Or you might be interested in applying it to
the same kinds of objects, but sorting them on
different attributes at different times
• This means having various different
implementations of the subpart, the pairwise
comparison operation that the template
depends on
14
Sorting in the Java API
• The book doesn’t actually explain sorting in
the Java API in great detail
• It shows an example and moves on
• I will try and explain it in detail
• It is this information that you are responsible
for
15
• There are two parallel tracks to sorting in Java
• The first of the two tracks is based on what
the API refers to as “natural order”
• In essence the second track is an extension
that makes it possible to compare objects on
some order other than the so-called natural
order
16
• For each of the two tracks, pairwise
comparison of objects will be addressed first
• Then using the comparison in a template
method will be addressed
17
Natural Order
• The phrase “natural order” sounds god-given
• This is not the case
• Natural order means the order that is defined
by a class that implements the Comparable
interface
• The Comparable interface contains a
compareTo() method
• This is known as the natural comparison
method
18
• The compareTo() method has this signature
• compareTo(obj:Object):int
• Given an implicit and an explicit parameter
that are objects, it will compare the two
• It will return an integer value as the result of
the comparison
19
• In a class that implements the Comparable
interface, the compareTo() method contains
the logic for comparison
• In general, the comparison is based on the
value of the most important instance variable
of the class
20
compareTo()’s Return Values
• If the return value is -1, the implicit parameter
is less than the explicit parameter
• If the return value is 0, the implicit parameter
is equal to the explicit parameter
• If the return value is 1, the implicit parameter
is greater than the explicit parameter
21
The Arrays and Collections Classes
• The Java API contains classes named Arrays
and Collections
• These classes contain sorting methods that
make use of calls to compareTo()
• A little bit of background on the classes will be
presented before getting to sorting
22
• Do not to confuse the Arrays and Collections
classes with the class Array or the interface
Collection
• It is a little inconvenient that there classes
Array, Arrays, and Collections, and an interface
Collection
23
•
•
•
•
Recall that the Array class is a concrete class
Instances of that class are arrays
Collection is an interface
This interface is at the root of the a hierarchy
of classes that implement it, like ArrayList,
HashMap, etc.
24
The Arrays and Collections Classes
Contain Static Methods
• So what are the classes Arrays and
Collections?
• They are classes that contain many static
methods that can be used to work on
instances of arrays or collections
• We will be interested in just those methods
that sort the contents of an array or collection
based on pairwise comparison of the
elements
25
• This is the first paragraph of the Java API for
the Arrays class:
• “This class contains various methods for
manipulating arrays (such as sorting and
searching).
• This class also contains a static factory that
allows arrays to be viewed as lists.”
• (I only see static methods in the class.)
26
• This is the first paragraph of the Java API for
the Collections class:
• “This class consists exclusively of static
methods that operate on or return collections.
• It contains polymorphic algorithms that
operate on collections, "wrappers", which
return a new collection backed by a specified
collection, and a few other odds and ends.”
27
• This is a simple analogy:
• The Math class contains static methods for
performing mathematical operations on
simple types
• The Arrays and Collections classes contain
static methods for performing operations on
instances of Array or Collection classes
28
The sort() Methods in the Arrays Class
• The Arrays class has 18 different sort methods
in it
• The methods sort an array that is passed in as
a parameter
• Most of these methods differ according to the
type of element in the array that is sorted
• For simple types, the sort order is simply
based on numeric comparison
29
Arrays with Numeric Elements
• There is a version of sort() which takes an
array of integers as the explicit parameter
• The pairwise comparison that it’s based on is
the numerical < operator
• For what it’s worth, this version of sort()
implements a version of quick sort
30
Sorting Arrays with Elements that are
References
• How will an array be sorted if it contains
references to objects?
• Remember that you typically declare the type
of the object in the array
• You can count on each of an array’s elements
being an instance of the same class
• The sort() method in Arrays will sort the
elements in “natural” order
31
Natural Order Sorting is Based on
Implementing the Comparable Interface
• Here is part of the Java API documentation for
the sort() method for objects in the Arrays
class:
• “public static void sort(Object[] a)
• Sorts the specified array of objects into
ascending order, according to the natural
ordering of its elements.
• All elements in the array must implement the
Comparable interface.”
32
• The sort() method will successfully work on an
array if the elements of the array are of a class
that implements the Comparable interface
• The results of the sort will depend on the
pairwise comparison of the array’s elements
using the compareTo() method specified by
Comparable and implemented in the class
• For what it’s worth, this version of sort()
implements a version of merge sort
33
Flexibility of the Template Pattern—
Re-using the Comparison Operation
• Notice how sorting in Java illustrates one
aspect of the template pattern
• You can have more than one sorting template,
one for quick sort and the other for merge
sort, for example
• They both can make use of the same pairwise
comparison operation
34
The sort() Methods in the Collections
Class
• Sorting with the Collections class is similar to
the Arrays class, but simpler
• Collections does not contain a large number of
sort() methods because a collection can only
contain object references, not simple types
35
• The Collections class has two sort() methods
• The first sort() method is analogous to the
sort() method for the Arrays class
• It will be discussed next
• The second sort() method is based on
something call a Comparator
• That will be discussed after finishing with the
first sort() method
36
Natural Order Sorting in the Collections
Class
• Here is part of the Java API documentation for
the first sort() method in the Collections class:
• “public static <T extends Comparable<? super
T>> void sort(List<T> list)”
• Sorts the specified list into ascending order,
according to the natural ordering of its
elements.
• All elements in the list must implement the
Comparable interface.”
37
Differences between Sorting in Arrays
and Collections
• The signature of the first sort() method in the
Collections class differs from the signature of
the sort() method in the Arrays class
• An Array contains elements of one kind
• It is possible for a collection to contain
references to different kinds of objects
38
• For a collection, angle bracket notation is used to
specify a single object type that a collection
contains
• The angle bracket notation shown is more
complex than any we’ve seen before
• You don’t have to master this syntax in order to
make use of the method
• All it apparently means is that the elements of
the collection either have to be comparable
themselves or be subclasses of classes that are
comparable
39
Similarities between Sorting in Arrays
and Collections
• Aside from those two differences, the sort()
methods in Arrays and Collections discussed
so far are similar
• They both rely on the natural order defined on
the objects by their implementation of the
Comparable interface
• The sort order results from the pairwise
application of compareTo() to the elements of
the collection
40
Kinds of Objects in Collections
• The elements of a collection may literally be
instances of different classes
• Things will work if the objects are instances of
subclasses of the type declared for the collection
and that type implements Comparable
• The collection will contain superclass references
to subclass objects
• Polymorphism and dynamic binding mean that
comparison will be done on the basis of the
comparability of the common superclass
41
Flexibility of the Template Pattern—
Changing the Comparison Operation
• The discussion of Java sorting so far has been
based on natural order as defined by
implementing the Comparable interface
• The other aspect of the template pattern is
the ability to change the pairwise comparison
to sort different kinds of objects or in a
different order
• How that is accomplished in Java sorting will
be addressed next
42
Sorting in a Different Order with a
Different Comparison Operation
• Suppose you want to sort objects which are of
the same kind, but you want to define a new
sort order
• The Comparator interface in the Java API is the
basis for this
• There are sort() methods in the Arrays and
Collections classes which are defined to work
on parameters which implement this interface
43
The Comparator Interface for “NonNatural Order” Sorting
• Let a class implement the Comparator
interface
• This means that it implements a method
named compare() with this signature
• compare(o1:Object, o2:Object):int
• Given two explicit parameters that are
objects, it will compare the two
• It will return an integer value as the result of
the comparison
44
• compare() isn’t declared static in the interface
definition, but in a practical sense it is
• It takes two instances of a class as explicit
parameters and compares them with each
other
• Just like with compareTo(), we don’t call the
method ourselves
• A sorting method that uses Comparator will
call the compare() method
45
compare()’s Return Values
• The meaning of the integer return value of
compare() is like that of compareTo(),
• If the return value is -1, the first explicit
parameter is less than the second explicit
parameter
• If the return value is 0, the first explicit parameter
is equal to the second explicit parameter
• If the return value is 1, the first explicit parameter
is greater than the second explicit parameter
46
Using Comparator/compare() in Arrays
and Collections
• The Arrays and Collections classes both
contain sort() methods based on Comparator
• The methods take two parameters:
• An array or collection of elements to be sorted
• An instance of a class that implements the
Comparator interface for the elements of the
array or collection
47
• Notice that this is one step deeper than plain
Comparable
• With Comparable, the element class itself
implemented the interface and contained
compareTo(), which defined its natural order
• A Comparator is external to the element class
• In theory, you could have many different
comparators for the same element class
48
The sort() Method with a Comparator
Parameter in the Arrays Class
• Here is part of the Java API documentation for
the sort() method with a Comparator
parameter in the Arrays class:
• public static <T> void sort(T[] a, Comparator<?
super T> c)
• Sorts the specified array of objects according
to the order induced by the specified
comparator.
49
The sort() Method with a Comparator
Parameter in the Collections Class
• Here is part of the Java API documentation for
the sort() method with a Comparator
parameter in the Collections class:
• public static <T> void sort(List<T> list,
Comparator<? super T> c)
• Sorts the specified list according to the order
induced by the specified comparator.
50
• Recall that in Collections there are only two
sort() methods
• The first was the one on natural order
• The second is this one
51
• This one uses some advanced syntactical
notation
• Luckily, we don’t have to understand the
notation in detail in order to use the method
• Pass in a parameter of type List containing
elements of type T
• Pass in another parameter of type Comparator
on elements of type T
52
• The List will be sorted by the Comparator
• You can have as many different comparators
as you would like
53
Review of the Overall Idea
• Stated in very general terms, the idea is this:
• What sorting is doesn’t change
• What sort order you get depends on the
objects you’re sorting and their
implementation of Comparable and
Comparator
54
• With careful design it is possible to write
flexible and general code for sorting
• Different sorting algorithms are possible
• Different pairwise comparisons are possible
55
• Flexibility and generality are what the
template pattern is about
• The pattern doesn’t just apply to sorting
• It can bring the same benefits if applied in
other domains
56
UML for the Pattern
• The book provides the UML diagram shown on
the following overhead to summarize the
Comparable and Comparator interfaces along
with the Collections class
• The diagram only shows the sort() method
that depends on Comparator
• The diagram would be more complete if it
included the sort() method that depends on
Comparable
57
58
The Book’s Concrete Example of
Sorting
• The book illustrates sorting based on objects
in the fireworks set of classes
• The code constructs an array of rockets
• It then uses the sort() method of the Arrays
class and a comparator named
ApogeeComparator to sort the rockets
• It prints out the sorted array
59
• Then it sorts the array again using a
NameComparator object as the comparator
parameter to the sort method
• It prints out the re-sorted array
• The code is shown on the following overheads
60
•
•
•
•
•
•
•
•
•
•
•
•
•
•
public class ShowComparator
{
public static void main(String args[])
{
Rocket r1 = new
Rocket("Sock-it", 0.8, new Dollars(11.95), 320, 25);
Rocket r2 = new
Rocket("Sprocket", 1.5, new Dollars(22.95), 270, 40);
Rocket r3 = new
Rocket("Mach-it", 1.1, new Dollars(22.95), 1000, 70);
Rocket r4 = new
Rocket("Pocket", 0.3, new Dollars(4.95), 150, 20);
Rocket[] rockets = new Rocket[] { r1, r2, r3, r4 };
61
•
•
•
•
System.out.println("Sorted by apogee: ");
Arrays.sort(rockets, new ApogeeComparator());
for (int i = 0; i < rockets.length; i++)
System.out.println(rockets[i]);
•
•
•
•
•
•
•
System.out.println();
System.out.println("Sorted by name: ");
Arrays.sort(rockets, new NameComparator());
for (int i = 0; i < rockets.length; i++)
System.out.println(rockets[i]);
}
}
62
• The book gives the output shown on the
following overhead for the program
• It’s clear that the toString() method for the
Rocket class isn’t very complete
• It would be helpful if it showed the apogee
values so that that sort could be verified
63
•
•
•
•
•
Sorted by apogee:
Pocket
Sprocket
Sock-it
Mach-it
•
•
•
•
•
Sorted by name:
Mach-it
Pocket
Sock-it
sprocket
64
The Comparator Classes for the
Example
• Clearly, how the code sorts is based on the
template pattern
• In other words, everything depends on how
the ApogeeComparator and NameComparator
are implemented
• The book does the code as a challenge
• As usual, the solutions are simply shown
65
Solution 21.1
• Notice how the implementation relies on the compare()
method for the Double class.
•
•
•
•
•
•
•
•
•
public class ApogeeComparator implements Comparator
{
public int compare(Object o1, Object o2)
{
Rocket r1 = (Rocket) o1;
Rocket r2 = (Rocket) o2;
return Double.compare(r1.getApogee(), r2.getApogee());
}
}
66
Solution 21.1
• Notice how the implementation relies on the compareTo()
method for the String class.
•
•
•
•
•
•
•
•
•
public class NameComparator implements Comparator
{
public int compare(Object o1, Object o2)
{
Rocket r1 = (Rocket) o1;
Rocket r2 = (Rocket) o2;
return r1.toString().compareTo(r2.toString());
}
}
67
How the Example Illustrates the
Pattern
• The book reiterates the idea behind the Template
pattern with this observation:
• Sorting, per se, doesn’t have anything to do with
rocket apogees
• Rocket apogees are a problem domain specific
concept
• It is extremely convenient to be able to
implement sorting with a general algorithm that
would apply to many things
• Then for each different type of thing, all you have
to do is provide the comparison step
68
Another Example
• This is another example based on a Cup class
and a Seed class
• The template design pattern can be used to
sort an ArrayList of Cups
• The Cup class has two attributes, an owner's
name and an ArrayList of seeds
69
• An ArrayList of cups can be sorted on either of
these attributes
• Sorting on seed count is the natural order and is
implemented with compareTo() in the Cup class
• Sorting by name is accomplished with a
comparator which implements compare()
• The sort() methods in the API can then be used
on the ArrayList of cups
• Code is given on the following overheads
70
The Cup Class
• import java.util.ArrayList;
• import java.awt.Color;
• public class Cup implements Comparable
• {
•
private String ownersName;
•
private ArrayList<Seed> seedArrayList;
•
•
•
public Cup()
{
seedArrayList = new
ArrayList<Seed>();
•
}
71
•
public Cup(String ownersNameIn, int
seedCountIn)
•
{
•
Seed newSeed;
•
•
•
•
•
•
•
•
ownersName = ownersNameIn;
seedArrayList = new ArrayList<Seed>();
for(int i = 0; i < seedCountIn; i++)
{
newSeed = new Seed(Color.BLUE);
seedArrayList.add(newSeed);
}
}
72
•
•
•
•
public void setOwnersName(String ownersNameIn)
{
ownersName = ownersName;
}
•
•
•
•
public String getOwnersName()
{
return ownersName;
}
•
•
•
•
public int getSeedCount()
{
return seedArrayList.size();
}
73
•
•
•
•
•
•
•
•
•
•
•
•
•
public void addSeed(Seed aSeed)
{
seedArrayList.add(aSeed);
}
public Seed removeSeed()
{
return (Seed)
seedArrayList.remove(seedArrayList.size() - 1);
}
public String toString()
{
return ("Cup[ownersName=" + ownersName
+ ", seedCount=" +
seedArrayList.size() + "]");
}
74
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
public int compareTo(Object objIn) throws ClassCastException
{
if(objIn instanceof Cup)
{
Cup that = (Cup) objIn;
if(this.seedArrayList.size() <
that.seedArrayList.size())
{
return -1;
}
else if(this.seedArrayList.size() >
that.seedArrayList.size())
{
return 1;
}
else
{
return 0;
}
}
else
{
throw new ClassCastException();
}
}
}
75
The Seed Class
•
import java.awt.Color;
•
•
•
public class Seed
{
private Color seedColor;
•
•
•
public Seed()
{
}
•
•
•
•
public Seed(Color aColor)
{
seedColor = aColor;
}
•
•
•
•
•
public Color getColor()
{
return seedColor;
}
}
76
The CupNameComparator Class
•
import java.util.Comparator;
•
•
•
public class CupNameComparator implements Comparator
{
public int compare(Object obj1In, Object obj2In) throws
ClassCastException
{
if(!((obj1In instanceof Cup) && (obj2In instanceof Cup)))
{
throw new ClassCastException();
}
else
{
Cup cupOne = (Cup) obj1In;
Cup cupTwo = (Cup) obj2In;
return
(cupOne.getOwnersName().compareTo(cupTwo.getOwnersName()));
}
}
}
•
•
•
•
•
•
•
•
•
•
•
•
•
77
The Test Program
•
•
import java.util.ArrayList;
import java.util.Collections;
•
•
•
•
•
public class TestCupAndSeed
{
public static void main(String[] args)
{
MyTerminalIO myterminal = new MyTerminalIO();
•
ArrayList<Cup> cupArrayList = new
ArrayList<Cup>();
•
•
•
Cup cup1 = new Cup("Bob", 2);
Cup cup2 = new Cup("Sue", 4);
Cup cup3 = new Cup("Al", 3);
78
•
•
•
cupArrayList.add(cup1);
cupArrayList.add(cup2);
cupArrayList.add(cup3);
•
myterminal.println(cupArrayList);
•
Collections.sort(cupArrayList);
•
myterminal.println(cupArrayList);
•
CupNameComparator myComparator = new
CupNameComparator();
•
Collections.sort(cupArrayList, myComparator);
•
•
•
myterminal.println(cupArrayList);
}
}
79
Lasater’s UML for the Pattern
• Lasater’s UML for the pattern is given on the
following overhead
• Keep in mind that this is general, not specific
to sorting
• The idea is that an operation may implement
a general algorithm
• What the algorithm accomplishes depends on
the specific operations implemented in the
concrete subclass
80
81
UML for the Pattern
• On the following overhead I give a UML
diagram where I attempt to summarize my
understanding of the pattern.
• The Template class contains a method with a
general implementation of an algorithm
• That implementation relies on calls to the
specific “other” methods defined in the other
classes
82
83
Conclusion
• As pointed out at the beginning, the overhead
presentation ends with the example taken
from sorting
• The rest of the chapter will not be covered
and you will not be responsible for it
• A subset of the book’s summary is given on
the following overheads
84
Summary
• The intent of the Template Method design
pattern is to define an algorithm in a method
• Some of the steps are left abstract, stubbed
out, or defined in an interface
• Other classes then fill in the functionality for
those missing steps
85
• The Template Method design pattern can be
useful in a large scale development
environment
• One developer is responsible for setting up
the outline of an algorithm (like sorting for
example)
• Then other developers only need to fill in the
missing steps in order to use the general
outline
86
• The book also notes that the development of
the Template Method pattern may go in the
opposite direction
• You may find that you are repeating similar
code in different places, where the only
difference seems to be in certain small steps
• It would then be possible to refactor and
generalize, taking the commonality out into a
template
87
• Elsewhere in the chapter the authors observe
that there is some similarity between a template
and an adapter
• In the end, all of the patterns start looking alike
• The idea here is that with a few well-designed
interfaces it is possible for one piece of code
(sorting for example) to make use of another
(comparable objects) in order to achieve its
overall goal
88
The End
89