Transcript sort

Unit 16
Template
Summary prepared by Kirk Scott
1
Design Patterns in Java
Chapter 21
Template Method
Summary prepared by Kirk Scott
2
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
• I will not cover the additional material where
the authors try to come up with examples out
of whole cloth based on the fireworks
scenario
• As a student, you are only responsible for the
first example
3
• 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
4
• 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
• The overall algorithm may be designed
generally so that it can apply to multiple kinds
of objects
5
• 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
6
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.
7
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
8
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 would rely on a method that
supported the pairwise comparison of the values
or objects to be sorted
9
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
10
• 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 have various different
implementations of the subpart, the pairwise
comparison operation that the template
depends on
11
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
12
• 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
13
• 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
14
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
15
• 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
16
• 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
17
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
18
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
19
• First of all, do not to confuse these 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
• Recall that the Array class is a concrete class
where instances of the class are arrays
• The Collection interface is at the root of the
hierarchy, which containing classes like ArrayList,
HashMap, etc.
20
The Arrays and Collections Classes
Contain Static Methods
• So what are the classes Arrays and
Collections?
• They are classes that contain methods that
can be used to work on instances of arrays or
collections
• The whole idea is that you want to sort the
contents of an array or collection based on
pairwise comparison of the elements
21
• 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.”
• All of the methods in the class appear to be
static
22
• 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.”
23
• This is a simple analogy:
• The Math class contains static methods for
performing mathematical operations
• The Arrays and Collections classes contain
static methods for performing operations on
instances of Array or Collection classes
24
The sort() Methods in the Arrays Class
• The Arrays class has 18 different sort methods
in it
• Most of these methods differ according to the
type of element in the array that is passed in
as the explicit parameter to be sorted
• For simple types, the sort order is clear
25
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
simply the numerical < operator
• For what it’s worth, this version of sort()
implements a version of quick sort
26
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
27
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.
28
• 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
29
Sorting Object References in
Collections
• 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
30
• 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
31
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.
32
• The signature of the first sort() method in the
Collections class differs from the signature of the
sort() method in the Arrays class in two ways:
• 1. An Array contains elements of one kind
• It is possible for a collection to contain references
to different kinds of objects
• For a collection, angle bracket notation is used to
specify a single object type that a collection
contains
33
• 2. In the Arrays class, the sort() method was
void and it sorted the explicit parameter
directly
• In the Collections class, the sort() method
returns a sorted version of the explicit
parameter
34
• Aside from those two differences, the sort()
methods in Arrays and Collections 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
35
Kinds of Objects in Collections
• The elements of a collection may literally be
instances of different classes
• You are saved by polymorphism and dynamic
binding
• 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
36
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 merge sort and the other for quick
sort, for example
• They both can make use of the same pairwise
comparison operation
37
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
38
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
39
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 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
40
• 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
parameter 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
41
compare()’s Return Values
• The meaning of the integer return value is the
same as for compareTo(),
• 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
42
Using Comparator/compare() in Arrays
and Collections
• The Arrays and Collections classes both
contain other sort() methods not discussed so
far
• 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
43
• Notice that this is one step deeper than plain
Comparable
• With Comparable, the element class itself
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
44
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.
45
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.
46
• Recall that in Collections there are only two
sort() methods
• The first was the one on natural order
• The second is this one
47
• 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
48
• The List will be sorted by the Comparator
• You can have as many different comparators
as you would like
49
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
50
• With careful design it is possible to write flexible
and general code for sorting
• Different sorting algorithms are possible
• Different pairwise comparisons are possible
• 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
51
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
52
53
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
54
• 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
55
•
•
•
•
•
•
•
•
•
•
•
•
•
•
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 };
56
•
•
•
•
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]);
}
}
57
• 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
58
•
•
•
•
•
Sorted by apogee:
Pocket
Sprocket
Sock-it
Mach-it
•
•
•
•
•
Sorted by name:
Mach-it
Pocket
Sock-it
sprocket
59
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
60
Solution 21.1
•
•
•
•
•
•
•
•
•
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());
}
}
61
Solution 21.1
•
•
•
•
•
•
•
•
•
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());
}
}
62
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
63
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
64
• 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
65
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>();
•
}
66
•
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);
}
}
67
•
•
•
•
public void setOwnersName(String ownersNameIn)
{
ownersName = ownersName;
}
•
•
•
•
public String getOwnersName()
{
return ownersName;
}
•
•
•
•
public int getSeedCount()
{
return seedArrayList.size();
}
68
•
•
•
•
•
•
•
•
•
•
•
•
•
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() + "]");
}
69
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
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();
}
}
}
70
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;
}
}
71
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()));
}
}
}
•
•
•
•
•
•
•
•
•
•
•
•
•
72
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);
73
•
•
•
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);
}
}
74
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
75
76
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
77
78
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 overhead
79
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
80
• 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
81
• 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
82
• 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
83
The End
84