Software Construction and Design 2
SOFT3202 / COMP9202 Composite, Visitor, Template Method Design Pattern
Prof Bernhard Scholz School of Computer Science
The University of Sydney
Page 1
Agenda
– GoF Design Patterns
– Composite Design Pattern – Visitor
– Template Method
The University of Sydney
Page 2
Composite Design Pattern
GoF
The University of Sydney Page 3
Composite Design Pattern
– Purpose/Intent:
– Composeobjectsintotreestructurestorepresentpart-wholehierarchies – Objectsandcompositionsofobjectsaretreateduniformlybyclient
– Applicability:
– part-wholehierarchiesofobjects
– clientcodetotreatobjectsuniformly
– Benefits:
– Arbitrarilylargecompositionhierarchywithshortinheritance – Clientcanbeverysimple
– Limitations:
– Interfacesforobjectsandcompositionsmustbeuniform
The University of Sydney
Page 4
y n
e s
ex o
.t
ve t i
d
the composite object
d by the tree on the et the other root?
b 4
Multiply
Suppose you’re writing a calculation machine. You need to form arbitrary
expressions like
b pb2 4ac
Composite Example
r1,r2=° ± 2a°
In this example the expression tree for r1
Each expression needs to be
evaluable somehow, and the
complete expression can be
would be
– Write an arbitrary calculation evaluated only when all of its
Divide
engine for expressions, e.g.
ou’re writing a calculation machine. You need to form arbitrary
s like
ssion needs to be omehow, and the
components have been
place you ite design.
Add
Multiply
evaluated. p
This is°abv±erybco°m4maocn
Negate
b
Square Root Subtract
2
a
The oInthtehrisisexinamthple dtheseigenxporefssion tree for r1
GUIsw. ould be
pression can be Divide
Square
b
Multiply Multiply
– RepreHseowntweoxulpdryeoussmioinimasllyan nly when all of its transform the composite object
expression tree
4
s have been
represented by the tree on the
– Have uniform evaluation scheme right to get the other root?
Add
Multiply
ry common place you
Negate Square Root
he composite design. s in the design of
INFO3220: Object Oriented Design
Multiply
2018 S1
23 / 66
Page 5
© Drinkwater, Charleston, Scholz (USyd.SIT)
you minimally
r1,r2 =
2
b
Subtract
The University of Sydney
Square
would use the compos 2a
a
c
2
a
a
c
e
o
r
n
e r
l m
e g
2018 S1 2018 S1
tructure
Composite – Structure
Component
Operation() Add(Component) Remove(Component) GetChild(int)
Client
children
Leaf
Operation()
Composite
Operation() Add(Component) Remove(Component) GetChild(int)
for all g in children g.Operation()
The University of Sydney Page 6
S
2018 S1
Composite – Participants
– Component
– declares the interface for objects in the composition
– implements common behaviour
– declares an interface for managing its children
– Leaf
– has no children
– defines behaviour for primitive objects – Composite
– defines behaviour for components having children
– stores those children
– implements the operations defined in Component
– Client
– manages the objects in the composition only through the Component interface.
The University of Sydney
Page 7
Composite – Participants
– Component
– declares the interface for objects in the composition
– implements common behaviour
– declares an interface for managing its children
– Leaf
– has no children
– defines behaviour for primitive objects – Composite
– defines behaviour for components having children
– stores those children
– implements the operations defined in Component
– Client
– manages the objects in the composition only through the Component interface.
The University of Sydney
Page 8
Composite Participant
– Collaborations
– Clients use the component class interface to interact with objects in the
composite structure
– If the recipient is a Leaf, then the request is handled directly
– If the recipient is a Composite, then it usually forwards requests to its child components, possibly performing additional operations before and/or after forwarding
The University of Sydney
Page 9
Composite – Consequences
– Allows recursive composition
– Clients code can expect a primitive object as well as a composite one
– Simplifies the client code
– Clients do not need to write case-statement-style functions over the
classes that define the composition
– Allow adding new kind of components
– Clients do not have to change for new component classes – Makes it harder to restrict composite’s components
– Type system cannot enforce certain components types, use run-time checks instead
The University of Sydney
Page 10
Implementation Details
– Parent Reference
– Keep a reference to parent for navigation – Invariant in component
– Sharing Components (cf. Flyweight)
– Sometimes it is useful sharing components to avoid replication
– Maximizing component interface
– Component interface union of Leaf and Composite
– Not great for SOLID principles – Ordering
– Might be of relevance in some applications (see expression tree) The University of Sydney
Page 11
Java Example
interface ExpressionNode { int execute(); // omitted children interface }
class Add implements ExpressionNode {
private ExpressionNode lhs, rhs;
public Add(ExpressionNode lhs, ExpressionNode rhs) { this.lhs = lhs;
this.rhs = rhs;
}
public int execute() {
return lhs->execute() + rhs->execute(); }
}
class Const implements ExpressionNode { private int const;
public Const(int const) { this.const = const} public int execute() {
return const;
} }
The University of Sydney
Page 12
Composite – Related Patterns
– Decorator is often used with Composite
– They have common parent class
– Decorators will have to support the Component interface with operations like Add, Remove and GetChild
– Also relate to Chain of Responsibility, Iterator, Flyweight, Visitor
The University of Sydney Page 13
Visitor Design Pattern (GoF)
Object Behavioural
The University of Sydney Page 14
Visitor Pattern (GoF Pattern)
– Separating algorithm from an object
– Add new operations to an object structure without modifying
the structure
– Enforces the open/closed principle – Object structure stays the same (closed) – Operations can be added
– Adding new virtual to a family of classes without modifying the classes
– Technical solution requiring a double-dispatch
The University of Sydney Page 15
Visitor Pattern (cont’d)
– Problem:
– Define a new operation for a family of classes of an object structure
without changing the classes
– Solution:
– Define a separate visitor object that performs the operation
– Clients traverse the object structure by dispatching operation accept() with visitor as an argument
– Uses:
– Many unrelated operations on an object structure
– Classes of object structure not expected to change – New operations added frequently
The University of Sydney
Page 16
Motivation – A Compiler
– A compiler represents programs as abstract syntax trees
– Operations like type-checking, variable assignment and code generation
– Different classes (nodes) for different statements (e.g., assignment statement, arithmetic expressions
The University of Sydney
Page 17
Motivation – A Compiler
– Problems:
– Node structure will be populated with a lot of virtual methods that are not very cohesive.
– Node structure will not change
– Operations are distributed across various node classes
• Difficulttounderstand,maintainand change design
The University of Sydney
Page 18
A Compiler Application – Improved Design
Node Visitor Hierarchy The University of Sydney
Node Hierarchy
Page 19
Visitor Pattern – Class Hierarchies
– NodeHierarchy
– For the elements being operated on
– NodeVisitorHierarchy
– For the visitors that define operations on the elements
– Tocreateanewoperation,addanewsubclasstothevisitor hierarchy
The University of Sydney
Page 20
Visitor Pattern – How it Works
– Group set of related operations from each class in a separate object (visitor)
– Pass this object to elements of the syntax tree as it is traversed
– An element accepts the visitor to be able to send request to (element passed
as an argument)
– The visitor will run the operation for that element
The University of Sydney Page 21
Visitor Pattern
– Object behavioral
– Intent:
– Modifyanewoperationwithoutchangingtheclassesoftheelementsonwhichit
operates
– Applicability:
– Youwanttoperformoperationsonobjectsthatdependontheirconcreteclasses
– You want to avoid mixing many distinct unrelated objects’ operations in an object
structure with their classes
– Theclassesthatdefinetheobjectstructurerarelychange,butoftenitisneededto
define new operations over the structure
The University of Sydney Page 22
Visitor Pattern – Structure
–
By Translated German file to English, CC BY 3.0, https://en.wikipedia.org/w/index.php?curid=52845911
The University of Sydney Page 23
Visitor Pattern – Participants
– Visitor (NodeNisitor)
– DeclaresaVisitoperationforeachclassofConcreteElementintheobjectstructure
– Classesidentifiedbytheoperation’snameandsignature
– ConcreteVisitor(TypeCheckVistor)
– Implement each operation declared by Visitor
– Eachoperationimplementsafragmentofthealgorithmdefinedforthe
corresponding class of object in the structure – Element(Node)
– Definesan“Accept”operationthattakesavisitorasanargument The University of Sydney
Page 24
Visitor Pattern – Participants
– ConcereteElement (AssignmentNode,VariableRefNode) – Implements Accept operation (visitor as argument)
– ObjectStructure(Program)
– Can enumerate its elements
– May either be composite or a collection
– Mayprovideaninterfacetoallowthevisitortovisititselements
The University of Sydney
Page 25
Visitor Pattern – Collaboration
The University of Sydney Page 26
Visitor Pattern – Benefits
– Easywaytoaddnewoperations – Add a new Visitor
– Gatherrelatedbehaviors(algorithmsdefinedintheVisitors) – Specificdatastructurecanbehiddeninthevisitor
– Visiting across class hierarchies
– Itcanvisitobjectstructureswithdifferenttypesofelements(unlikeiterator)
– State accumulation in the object structure
– Otherwise, pass the state as an argument to the operations or declare it as global
variables
The University of Sydney Page 27
Visitor Pattern – Drawbacks
– Violatingencapsulation
– Itmayenforceusingpublicoperationsthataccessanelement’sinternalstate
– Difficulttoaddnewconcreteelementclasses
– Adding new Concrete Element requires adding new abstract operation on Visitor
and a corresponding implementation in every Concrete Visitor
• Exception: default implementation to be provided or inherited by most Concrete Visitors
– Consider the likelihood to change the algorithm applied over an object structure or classes of objects that make up the structure
The University of Sydney Page 28
Visitor Example – Element Implementation
The University of Sydney Page 29
Visitor Example – Visitor Implementation
The University of Sydney Page 30
Visitor Example – Client Implementation
– Whatistheoutputofthiscode?
The University of Sydney Page 31
Visitor – Implementation (1)
– Each object structure will be associated with a Visitor (abstract class)
– DeclaresVisitConcreteElementforeachclassofConcreteElementsdefiningtheobject structure
– Visit operation declares a particular ConcreteElement as its argument to allow the visitor to access the interface of ConcreteElement directly
– ConcreteVistorclassesoverrideeachvisitoperationtoimplementvisitor-specific behavior
– ConcreteElement classes implement their Accept operation that calls the matching Visit operation on the Visitor for that ConcreteElement
The University of Sydney Page 32
Visitor – Implementation (2)
– Double dispatch
– Theexecutionofanoperationdependsonthekindofrequestandthetypesoftwo
receivers
– Visitor pattern allows adding operations to classes without changing them through the Accept method which is double dispatch
– Accept method depends on Visitor and Element types which let visitors request different operations on each class of element
The University of Sydney
Page 33
Visitor – Implementation (3)
– Traversing the object structure; a visitor must visit each element of the object structure – How?
– Can be a responsibility of
– Object structure: a collection iterates over its elements calling the Accept operation
on each (use Composite)
– Separate iteration object: using an Iterator to visit the elements
• Internaloperatorwillcallanoperationsonthevisitorwithanelementasan
argument (not using double dispatching)
– Visitor: implement the traversal logic in the Visitor
• Allowstoimplementparticularlycomplextraversal • Codeduplication
The University of Sydney Page 34
Visitor – Related Patterns
– Composite
– The composite pattern can be used to define an object structure over which
a Visitor can iterate to apply an operation – Interpreter
– Visit or may be applied to do the interpretation
The University of Sydney Page 35
Template Method Pattern (GoF)
Class behavioural
The University of Sydney Page 36
Template Method (GoF)
– Intent:
– Base class has method ‘placeholders’.
– Derived classes implement the placeholders.
– Designer decides which operations are invariant and are placed in the base class
– Examples
– Template Method is used prominently in frameworks/systems. – Device driver / file system
The University of Sydney
Page 37
Motivating Scenario
– Application framework
– Application opens existing documents stored in external format
– Document represents the document’s info once it is read
– Sub-classing:
– SpreadsheetDocument and SpreadsheetApplication are Spreadsheet Application
– OpenDocument() to define the algorithm for opening and reading a document (Template Method)
The University of Sydney
Page 38
Motivating Scenario – Template Method
– A template method defines abstract operations (algorithm) to be concretely implemented by subclasses
– Application sub-classes
– Some steps of the algorithm (e.g., for CanOpenDocument() and DoCreateDocument())
– Document sub-classes
– Steps to carry on the operation (e.g., DoRead() to read the document)
The University of Sydney
Page 39
Template Method Pattern
– Class behavioral – Intent
– Let subclasses redefine certain steps of an algorithm without changing the algorithm’s structure
– Applicability
– Implement invariant parts of an algorithm once and let subclasses implement the varying
behavior
– Commonbehavioramongsubclassestoreducecodeduplication(“refactoringtogeneralize”)
– Control subclasses extensions
• Template method calls hook operations at specific points
The University of Sydney Page 40
Template Method Pattern – Structure
The University of Sydney Page 41
Template Method – Participants and Collaboration
– AbstractClass (Application)
– Definesabstractprimitiveoperations
– Implementatemplatemethoddefininganalgorithm’sskeleton
– The template method calls primitive operations and AbstractClass’ operations
– ConcreteClass (MyApplication)
– Implementstheprimitiveoperationstoperformsub-classspecificstepsofthe
algorithm
– Relies on Abstract class to implement invariant algorithm’s steps
The University of Sydney
Page 42
Template Method – Consequences
– Code reuse (e.g., class libraries)
– Inverted control structure (“the Hollywood principle” – “Don’t call us, we’ll call you”
– Template methods can call:
– Concrete operations (ConcreteClass or client classes)
– Concrete AbstractClass operations
– Primitive (abstract) operations (must be overridden)
– Factory methods
– Hook operations
• Provides default behavior that subclass can extend if needed
• Often does nothing by default, subclass override it to extend its behavior
– Subclassesmustknowwhichoperationsaredesignedforoverriding(hookor
abstract/primitive) The University of Sydney
Page 43
Template Method Pattern – Implementation
– Minimizeprimitiveoperationsasubclassmustoverride – More primitive operations can increase client’s tasks
– Namingconventionstoidentifyoperationsthatshouldbeoverridden
– E.g.,MacAppframework(Macintoshapplications)prefixestemplatemethodnames
with “Do” (DoRead, DoCreateDocument)
The University of Sydney Page 44
Example: Template Method
– Abstract Class Game as template method
– Cricket / Football are concrete classes overwriting Game’s methods init/start/end.
– Method play is not abstract.
The University of Sydney
Page 45
Example: Template Method Class
public abstract class Game { abstract void initialize(); abstract void startPlay(); abstract void endPlay(); //template method
public final void play(){ //initialize the game initialize();
//start game startPlay();
//end game
endPlay(); }
}
The University of Sydney
Page 46
Example: Concrete Class Cricket
public class Cricket extends Game { @Override void endPlay() {
} System.out.println(“Cricket Game Finished!”); @Override void initialize() {
} System.out.println(“Cricket Game Initialized! Start playing.”);
@Override void startPlay() {
System.out.println(“Cricket Game Started. Enjoy the game!”); }
}
The University of Sydney
Page 47
Example: Concrete Class Football
public class Football extends Game { @Override void endPlay() {
} System.out.println(“Football Game Finished!”); @Override void initialize() {
} System.out.println(“Football Game Initialized! Start playing.”);
@Override void startPlay() {
System.out.println(“Football Game Started. Enjoy the game!”); }
}
The University of Sydney
Page 48
Template Method Pattern – Related Patterns
– Factory
– Factory Method is a specialization of Template Method.
– Strategy
– Strategy is like Template Method except in its granularity.
– Template Method uses inheritance to vary part of an algorithm. – Strategy uses delegation to vary the entire algorithm.
The University of Sydney
Page 49
References
– Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.
1995. Design Patterns: Elements of Reusable Object-Oriented Software. Pearson.
– Martin Fowler (With contributions from David Rice, Matthew Foemmel, Edward Hieatt, Robert Mee, and Randy Stafford). 2003. Patterns of Enterprise Applications Architecture. Pearson.
– https://www.tutorialspoint.com/design_pattern/template_pattern.htm
The University of Sydney
Page 50