Overview of Design

Patterns in Java (Day 1)

Douglas C. Schmidt
[Link]@[Link]
[Link]/~schmidt

Professor of Computer Science

Institute for Software
Integrated Systems

Vanderbilt University
Nashville, Tennessee, USA
 Learning Objectives in this Lesson
• Know what topics we’ll cover

2
 Learning Objectives in this Lesson
• Know what topics we’ll cover
• Learn where to find Java
JDK/JRE & IDE platforms

3
 Learning Objectives in this Lesson
• Know what topics we’ll cover
• Learn where to find Java
JDK/JRE & IDE platforms
• Be aware of other digital
learning resources

4
 Learning Objectives in this Lesson
• Know what topics we’ll cover
• Learn where to find Java
JDK/JRE & IDE platforms
• Be aware of other digital
learning resources
• Be able to locate examples
of Java programs

We’ll just focus on the

ExpressionTree example,
but feel free to clone or
download the entire repo!

See [Link]/douglascraigschmidt/LiveLessons
5
Overview of this Course
 Overview of this Course
• We focus on programming “Gang-of-Four” (GoF) design patterns in Java, e.g.

7
 Overview of this Course
• We apply many GoF patterns in the context of a case study app
Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability Bridge
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Scattered operation implementations Command
Inflexible creation of variabilities Factory Method
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template Method
Inflexible expression input processing Interpreter
Inflexible interpreter output Builder
Minimizing global variable liabilities Singleton

See [Link]/douglascraigschmidt/LiveLessons/tree/master/ExpressionTree
8
 Overview of this Course
• We apply many GoF patterns in the context of a case study app (Day 1)
Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability Bridge
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Scattered operation implementations Command
Inflexible creation of variabilities Factory Method
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template Method
Inflexible expression input processing Interpreter
Inflexible interpreter output Builder
Minimizing global variable liabilities Singleton

9
 Overview of this Course
• We apply many GoF patterns in the context of a case study app (Day 2)
Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability Bridge
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Scattered operation implementations Command
Inflexible creation of variabilities Factory Method
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template Method
Inflexible expression input processing Interpreter
Inflexible interpreter output Builder
Minimizing global variable liabilities Singleton

10
 Overview of this Course
• This course focuses on both pattern-oriented design & implementation topics
ExpressionTree
exprTree = ...;
Visitor printVisitor
= ...;

for (ExpressionTree node

: exprTree)
node
.accept(printVisitor);

11
 Overview of this Course
• The Java expression tree processing app we cover is available on github

See [Link]/douglascraigschmidt/LiveLessons/tree/master/ExpressionTree
12
 Accessing Java
Features & Functionality
 Accessing Java Features & Functionality
• The Java runtime environment (JRE) supports Java features

See [Link]/javase/8/docs/technotes/guides/install/install_overview.html
14
 Accessing Java Features & Functionality
• The Java runtime environment (JRE) supports Java features
• Intellij & Eclipse are popular
Java IDE platforms

See [Link]/downloads &[Link]/idea/download

 Accessing Java Features & Functionality
• The Java runtime environment (JRE) supports Java features
• Intellij & Eclipse are popular
Java IDE platforms
• Most Java features are
supported by Android API
level 24 (& beyond)

See [Link]/2017/03/[Link]
16
 Accessing Java Features & Functionality
• The Java runtime environment (JRE) supports Java features
• Intellij & Eclipse are popular
Java IDE platforms
• Most Java features are
supported by Android API
level 24 (& beyond)
• Make sure to get Android
Studio 3.x or later if you
use Java 8!

See [Link]/studio/preview/features/[Link]
17
 Accessing Java Features & Functionality
• Java source code is available online
• For downloading
[Link]/[Link]

18
 Other Digital
Learning Resources
 Other Digital Learning Resources
• Addition pattern topics not covered here appear in my LiveLessons course

See [Link]/~schmidt/LiveLessons/DPiJava
20
 Other Digital Learning Resources
• There’s a Facebook group dedicated to discussing Java design pattern topics

See [Link]/groups/623398741056491
21
 Other Digital Learning Resources
• Several related Live Training courses on Java are coming soon

October 16th, 2018

9:00am – 12:00pm CST

August 20th, 2018

10:00am – 2:00pm CST

October 4th, 2018

9:00am – 1:00pm CST

See [Link]/~schmidt/DigitalLearning
22
 Other Digital Learning Resources
• See my website for many more videos
& screencasts related to programming
with patterns, frameworks, Java, etc.

See [Link]/~schmidt/DigitalLearning
23
 Other Digital Learning Resources
• See my website for many more videos
& screencasts related to programming
with patterns, frameworks, Java, etc.
• Videos from my MOOC “Pattern-
Oriented Software Architecture”
are relevant!

See [Link]/playlist?list=PLZ9NgFYEMxp6CHE-QQ040tlDILNcBqJnc
24
 Other Digital Learning Resources
• See my website for many more videos
& screencasts related to programming
with patterns, frameworks, Java, etc.
• Videos from my MOOC “Pattern-
Oriented Software Architecture”
are relevant!

We’ll cover some of these topics

25 in this course as time permits
 Other Digital Learning Resources
• The book Design Patterns: Elements of
Reusable Object-Oriented Software describes
all the Gang-of-Four (GoF) patterns in detail

26
See [Link]/wiki/Design_Patterns
 Other Digital Learning Resources
• The “POSA” books contain good sources
of material on other types of patterns &
pattern relationships

27
See [Link]/~schmidt/POSA
End of Course Overview
Overview of the Expression
Tree Processing App Case
Study (Part 1)

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand the goals of the object-oriented (OO) expression tree case study.

−5*(3+4)

−35
 Learning Objectives in This Lesson
• Understand the goals of the object-oriented (OO) expression tree case study.
• Recognize the key behavioral & structural
properties in the expression tree domain.

−5*(3+4)

−35
Douglas C. Schmidt
Lesson Introduction
 Lesson Introduction
• While patterns can be discussed abstractly,
effective design & programming practices
are not learned best by generalities.

“Sitting & thinking” is not sufficient…

 Lesson Introduction
• While patterns can be discussed abstractly,
effective design & programming practices
are not learned best by generalities.
• Instead, it’s usually better to see how
patterns can help improve nontrivial
programs
 Lesson Introduction
• While patterns can be discussed abstractly,
effective design & programming practices
are not learned best by generalities.
• Instead, it’s usually better to see how
patterns can help improve nontrivial
programs, e.g.,
• Easier to write & read;
• Easier to maintain & modify;
• More efficient & robust.
 Lesson Introduction
• While patterns can be discussed abstractly,
effective design & programming practices
are not learned best by generalities.
• Instead, it’s usually better to see how
patterns can help improve nontrivial −5*(3+4)

programs.
• This lesson describes a realistic—yet tractable
—expression tree processing app we’ll use as
−35
a case study throughout the course.
 Lesson Introduction
• While patterns can be discussed abstractly,
effective design & programming practices
are not learned best by generalities.
• Instead, it’s usually better to see how
patterns can help improve nontrivial
programs.
• This lesson describes a realistic—yet tractable
—expression tree processing app we’ll use as
a case study throughout the course.
• This case study applies many “Gang of
Four” (GoF) patterns.

See [Link]/wiki/Design_Patterns
Douglas C. Schmidt
Expression Tree Processing App
Case Study Goals
Expression Tree Processing App Case Study Goals
• Develop an OO expression Design Problem Pattern
tree processing app using
Non-extensible & error-prone designs Composite
patterns & frameworks.
Minimizing impact of variability Bridge
Inflexible expression input processing Interpreter
Inflexible interpreter output Builder
−5*(3+4)

Scattered request implementations Command

−35 Inflexible creation of variabilities Factory
Method
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template
Method
Minimizing global variable liabilities Singleton

Naturally, these patterns apply to more than expression tree processing apps!
Expression Tree Processing App Case Study Goals
• This app uses expression trees to remove Binary
ambiguity in algebraic expressions. Nodes
×
− +
−5*(3+4)

−35 Unary
Node
5 3 4

Leaf
Nodes

Each node of a binary expression

tree has zero, one, or two children.

See [Link]/wiki/Binary_expression_tree
Expression Tree Processing App Case Study Goals
• Compare/contrast algorithmic decomposition
& object-oriented (OO) approaches. ExpressionTree

Despite decades of
OO focus, algorithmic ComponentNode

decomposition is still
surprisingly common.
Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
1 AddNode SubtractNode
Tree
Composite Composite
Node MultiplyNode DivideNode
0|1|2
Pattern- & Object-Oriented
Algorithmic Decomposition
Decomposition
See [Link]/windows/software-complexity-bringing-order-to-ch/199901062
Expression Tree Processing App Case Study Goals
• Demonstrate scope, commonality, & Product Product Product Product

variability (SCV) analysis as a means Variant 1 Variant 2 Variant 3 Variant 4

to achieve systematic software

reuse.

Bundled & Third-Party Apps

Application Frameworks

Virtual Machine
System Libraries
Runtime

Operating System Kernel

• Identify common elements of a

domain & define stable interfaces.
• Identify variable elements of a
domain & define stable interfaces.

See [Link]/~schmidt/PDF/Commonality_Variability.pdf
Expression Tree Processing App Case Study Goals
• Demonstrate scope, commonality, &
variability (SCV) analysis as a means
to achieve systematic software
reuse.
−5*(3+4)
• Apply SCV in the context of the
expression tree processing app.
−35
Expression Tree Processing App Case Study Goals
• Show how to implement pattern- ExpressionTree exprTree = ...;
oriented OO frameworks & Visitor printVisitor = ...;
functional programs in Java.
for (Iterator<ExpressionTree> iter
= [Link]();
[Link]();
)
[Link]().accept
(printVisitor);

for (ExpressionTree node : exprTree)

[Link](printVisitor);

exprTree
.forEach
(node ->
[Link](printVisitor));
Expression Tree Processing App Case Study Goals
• Show how to implement pattern- ExpressionTree exprTree = ...;
oriented OO frameworks & Visitor printVisitor = ...;
functional programs in Java.
for (Iterator<ExpressionTree> iter
= [Link]();
[Link]();
)
[Link]().accept
(printVisitor);
Java-style GoF Iterator pattern

for (ExpressionTree node : exprTree)

[Link](printVisitor);

exprTree
.forEach
(node ->
[Link](printVisitor));

See [Link]/wiki/Iterator_pattern
Expression Tree Processing App Case Study Goals
• Show how to implement pattern- ExpressionTree exprTree = ...;
oriented OO frameworks & Visitor printVisitor = ...;
functional programs in Java.
for (Iterator<ExpressionTree> iter
= [Link]();
[Link]();
)
[Link]().accept
(printVisitor);

for (ExpressionTree node : exprTree)

Java for-each loop (assumes [Link](printVisitor);
ExpressionTree implements
Iterable)
exprTree
.forEach
(node ->
[Link](printVisitor));
Expression Tree Processing App Case Study Goals
• Show how to implement pattern- ExpressionTree exprTree = ...;
oriented OO frameworks & Visitor printVisitor = ...;
functional programs in Java.
for (Iterator<ExpressionTree> iter
= [Link]();
[Link]();
)
[Link]().accept
(printVisitor);

for (ExpressionTree node : exprTree)

[Link](printVisitor);

exprTree
.forEach
Java forEach() method (also (node ->
assumes ExpressionTree [Link](printVisitor));
implements Iterable)
Douglas C. Schmidt
Overview of the Expression Tree
Processing Domain
 Overview of Expression Tree Processing Domain
• Expression trees consist of nodes containing
operators & operands.
×
− +

5 3 4

See [Link]/wiki/Binary_expression_tree for expression tree information.

 Overview of Expression Tree Processing Domain
• Expression trees consist of nodes containing Binary
operators & operands. Nodes
• Operators are interior nodes ×
in the tree, i.e.,
• Binary & unary nodes
− +
Unary
Node
5 3 4
 Overview of Expression Tree Processing Domain
• Expression trees consist of nodes containing
operators & operands.
• Operators are interior nodes ×
in the tree
• Operands are exterior nodes
in the tree, i.e., − +
• Leaf nodes

5 3 4

Leaf
Nodes
 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities Nodes
×
− +
Unary
Node
5 3 4

See [Link]/wiki/Operator_associativity & [Link]/wiki/Arity

 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities, e.g., Nodes
• Precedence defines which operator ×
to perform first to evaluate a
mathematical expression.
• Multiplication takes − +
precedence over addition
Unary
Node
5 3 4

See [Link]/wiki/Order_of_operations
 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities, e.g., Nodes
• Precedence defines which operator ×
to perform first to evaluate a
mathematical expression.
• Multiplication takes − +
precedence over addition
• Operator locations in a Unary
tree unambiguously
designate precedence
Node
5 3 4

e.g., 3 + 4 is performed before –5 * 7.

 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities, e.g., Nodes
• Precedence defines which operator ×
to perform first to evaluate a
mathematical expression.
• Associativity determines how − +
operators of the same level of
precedence are grouped in
the absence of parentheses. Unary
• 5 + 3 – 4 == (5 + 3) – 4
Node
5 3 4

See [Link]/wiki/Operator_associativity
 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities, e.g., Nodes
• Precedence defines which operator ×
to perform first to evaluate a
mathematical expression.
• Associativity determines how − +
operators of the same level of
precedence are grouped in
the absence of parentheses. Unary
• Arity defines the number of
Node
5 3 4
operands an operator takes.
• Multiplication & addition operators
have two arguments (arity == 2)

See [Link]/wiki/Arity
 Overview of Expression Tree Processing Domain
• Operators have different precedence levels, Binary
different associativities, & different arities, e.g., Nodes
• Precedence defines which operator ×
to perform first to evaluate a
mathematical expression.
• Associativity determines how − +
operators of the same level of
precedence are grouped in
the absence of parentheses. Unary
• Arity defines the number of
Node
5 3 4
operands an operator takes.
• Multiplication & addition operators
have two arguments (arity == 2)
• The unary minus operator has one
argument (arity == 1)
 Overview of Expression Tree Processing Domain
• Operands can be integers, doubles, variables, etc. Binary
• We'll just handle integers in this case study. Nodes
×
− +
Unary
Node
5 3 4

Leaf
Nodes
(Integers)
 Overview of Expression Tree Processing Domain
• Operands can be integers, doubles, variables, etc. Binary
• We'll just handle integers in this case study. Nodes
• It’s easy to extend the app ×
to handle other types.

− +
Unary
Node
5.2 3.4 4.1

Leaf
Nodes
(Doubles)
 Overview of Expression Tree Processing Domain
• Trees may be “evaluated” via different traversal
orders, e.g.,
• “In-order traversal” = -5×(3+4) ×
• “Pre-order traversal” = ×-5+34
• “Post-order traversal” = 5-34+×
• “Level-order traversal” = ×-+534
− +

5 3 4

See [Link]/wiki/Binary_expression_tree#Traversal for more information.

Overview of the Expression
Tree Processing App Case
Study (Part 2)

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand the goals of the object-oriented (OO) expression tree case study.
• Recognize the key behavioral & structural
properties in the expression tree domain.
• Evaluate the functional & non- Functional
requirements
functional requirements of the
case study. Non-runtime Business
qualities constraints

Expre
ssion
Runtime −5*(3+4)
tree Technology
qualities proce constraints
−35 ssing
app

Patterns are best applied to address requirements, rather than applied blindly!
 Learning Objectives in This Lesson
• Understand the goals of the object-oriented (OO) expression tree case study.
• Recognize the key behavioral & structural
properties in the expression tree domain.
• Evaluate the functional & non-
functional requirements of the
case study.
• Put all the pieces together.
Douglas C. Schmidt
Functional &
Non-Functional Requirements
of the Case Study
 Functional & Non-Functional Requirements
• A functional requirement defines what a system should be able to do, i.e.,
the behavior it should perform.

[Link]/wiki/Functional_requirements has more information.

 Functional & Non-Functional Requirements
• A non-functional requirement defines specific criteria that can be
used to judge the operation of a system, rather than its specific behaviors.

• Non-Functional requirements are also called ”quality attributes” of a

system.

[Link]/wiki/Non-functional_requirement has more information.

 Case Study: Functional Requirements
• “Succinct mode”—the calculator
expr ::= factor expr-tail
interface evaluates arithmetic
expressions input by a user that must expr-tail ::= add_sub expr
conform to a grammar | /* empty */;

factor ::= term factor-tail

factor-tail ::= mul_div factor

| /* empty */;

mul_div ::= '×' | '/'

add_sub ::= '+' | '-‘

term :: NUMBER | '(' expr ')'

 Case Study: Functional Requirements
• The succinct mode can be command-line
or GUI interface.
• In the GUI version, a user presses Android
buttons to enter expressions. −5*(3+4)

−35
 Case Study: Functional Requirements
• The succinct mode can be command-line
or GUI interface.
• In the GUI version, a user presses Android
buttons to enter expressions. −5*(3+4)

• In the command-line version a user

designates input expressions via various −35
notations.
• e.g., in-fix, post-fix, etc.

In-fix expressions can contain parenthesized sub-expressions.

 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• “Verbose mode”—prompts the user to enter command requests that control
app behavior
• The order of these command requests must follow a specific protocol.
Command Behavior
format Allows the user to select the input format (e.g., in-fix, post-
fix, etc.)
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Prints the current input expression using the designated
traversal order (e.g., in-order, post-order, pre-order, etc.)
eval Evaluates the value of the current input expression
quit Exits the program
 Case Study: Functional Requirements
• The verbose mode can be accessed via:
• A GUI interface
 Case Study: Functional Requirements
• The verbose mode can be accessed via:
• A GUI interface
• A command-line interface
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability
Visitor
Bridge
ExpressionTree ComponentNode
Visitor
<< accept >>
<< create >>
Composite LeafNode
UnaryNode

Java Iterator EvaluationVisitor PrintVisitor

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability, e.g.,
• Add new operations on the expression tree nodes
without modifying the tree structure or
implementation
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability, e.g.,
• Add new operations on the expression tree nodes
without modifying the tree structure or
implementation, e.g.,
• Print the contents of the expression
tree in various traversal orders

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability, e.g.,
• Add new operations on the expression tree nodes
without modifying the tree structure or
implementation, e.g.,
• Print the contents of the expression
tree in various traversal orders
• Compute the “value" of the
expression tree
• e.g., via a post-order traversal
& stack-based
evaluator
1. S = [5] push([Link]())
2. S = [-5] push(-pop())
3. S = [-5, 3] push([Link]())
4. S = [-5, 3, 4] push([Link]())
5. S = [-5, 7] push(pop()+pop())
6. S = [-35] push(pop()*pop())
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability, e.g.,
• Add new operations on the expression tree nodes
without modifying the tree structure or
implementation, e.g.,
• Print the contents of the expression
tree in various traversal orders
• Compute the “value" of the
expression tree
• Perform semantic analysis &
optimization, generate code,
etc. 0: bipush -5 7: iload_1
2: istore_1 8: iload_2
3: iconst_3 9: iload_3
4: istore_2 10: iadd
5: iconst_4 11: imul
6: istore_3 12: istore 4
 Case Study: Non-Functional Requirements
• Apply a pattern-oriented OO design to simplify extensibility & portability, e.g.,
• Add new operations on the expression tree nodes
without modifying the tree structure or
implementation
• Systematically reuse the expression tree
−5*(3+4)
processing app code in diverse runtime
platforms, e.g.,
• The app code is reused in both
−35
Android GUI & command-line platforms
Douglas C. Schmidt
Putting All the
Pieces Together
 Putting All the Pieces Together
• The expression tree processing app provides a realistic case study of how to
apply GoF patterns. Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability Bridge
Inflexible expression input processing Interpreter
−5*(3+4)
Inflexible interpreter output Builder

−35 Scattered request implementations

Inflexible creation of variabilities
Command
Factory
Method
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template
Method
Minimizing global variable liabilities Singleton
 Putting All the Pieces Together
• The expression tree processing app provides a realistic case study of how to
apply GoF patterns.
• All the case study code is written in Java (~4K LOC & 57 classes).

See [Link]/douglascraigschmidt/LiveLessons/tree/master/ExpressionTree
 Putting All the Pieces Together
• The expression tree processing app provides a realistic case study of how to
apply GoF patterns.
• All the case study code is written in Java.
• There are command-line & Android GUI-
based versions. −5*(3+4)

−35

See [Link]/douglascraigschmidt/LiveLessons/tree/master/ExpressionTree
The Object-Oriented Design
of the Expression Tree
Processing App

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand the OO design of the expression tree processing app.

ExpressionTree

ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

[Link]/wiki/Unified_Modeling_Language has more on OOD notations.

Douglas C. Schmidt
Lesson Introduction
 Lesson Introduction
• Object-oriented design (OOD) is a method of planning a system of interacting
objects to solve software problem(s).

Polymorphism

Object-
Extensibility Oriented Abstraction
Design

Encapsulation

[Link]/wiki/Object-oriented_design has more information on OO design.

 Lesson Introduction
• Object-oriented design (OOD) is a method of planning a system of interacting
objects to solve software problem(s).
• OOD employs “hierarchical data Java Iterator
abstraction.”
• Components are designed based
on stable class & object roles
& relationships
LevelOrder
• Rather than functions Iterator
corresponding to actions
InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator

[Link]/wiki/Liskov_substitution_principle has more information.

 Lesson Introduction
• Object-oriented design (OOD) is a method of planning a system of interacting
objects to solve software problem(s).
• OOD employs “hierarchical data InputHandler
abstraction.” handleInput()
• It also associates actions with promptUser()
receiveInput()
specific objects and/or classes makeCommand()
of objects. executeCommand()

• Emphasize high cohesion

& low coupling
VerboseMode Succinct_Mode
InputHandler InputHandler
promptUser() promptUser()
makeCommand() makeCommand()

[Link]/wiki/Low-Coupling_/_High-Cohesion_pattern has more information.

 Lesson Introduction
• Object-oriented design (OOD) is a method of planning a system of interacting
objects to solve software problem(s).
• OOD employs “hierarchical data
abstraction.”

Bridge
ExpressionTree ComponentNode

• It also associates actions with << create >>

specific objects and/or classes

Composite LeafNode
UnaryNode
of objects. Java Iterator

• Well-designed OO programs Iterator

Composite
BinaryNode …
group classes & objects via
Composite
patterns & combine them to LevelOrder
form frameworks. Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator

[Link]/~schmidt/[Link] has more information.

Douglas C. Schmidt
OO Design of Expression Tree
Processing App
 OO Design of Expression Tree Processing App
• Create an OO design based on modeling classes & objects in “expression
tree” domain.

×
− +

5 3 4
 OO Design of Expression Tree Processing App
• Conduct scope, commonality, & variability analysis to determine stable APIs
& variable extension points.

×
− +

5 3 4

See [Link]/~schmidt/PDF/Commonality_Variability.pdf
 OO Design of Expression Tree Processing App
• Conduct scope, commonality, & variability analysis to determine stable APIs
& variable extension points.
• Model a tree as a collection of nodes. Binary
Nodes
×
− +
Unary
Node
5 3 4

Leaf
Nodes
(Integers)
 OO Design of Expression Tree Processing App
• Conduct scope, commonality, & variability analysis to determine stable APIs
& variable extension points.
• Model a tree as a collection of nodes. Binary
Nodes
×
− +
Note the different types
of nodes in a tree.
Unary
Node
5 3 4

Leaf
Nodes
(Integers)
 OO Design of Expression Tree Processing App
• Conduct scope, commonality, & variability analysis to determine stable APIs
& variable extension points.
ExpressionTree
• Model a tree as a collection of nodes.
• Represent nodes as class hierarchy,
capturing properties of each node. ComponentNode
• e.g., the “arities” (binary & unary
nodes)
Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

See [Link]/wiki/Arity
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
Visitor
Bridge
ExpressionTree ComponentNode
Visitor
<< accept >>
<< create >>
Composite LeafNode
UnaryNode

Java Iterator EvaluationVisitor PrintVisitor

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator

[Link]/wiki/Design_Patterns has information on the “Gang of Four” (GoF) book.

 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.

See [Link]/~schmidt/[Link]
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality

[Link]/~schmidt/[Link] has info on systematic reuse.

 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)

See [Link]/wiki/Inversion_of_control
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
• The framework controls the
main execution thread
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
• The framework controls the
main execution thread
• Decides how/when to run
app code via callbacks

See [Link]/wiki/Callback_(computer_programming)
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
• The framework controls the
main execution thread
• Decides how/when to run
app code via callbacks
• e.g., an Android looper
dispatches a handler,
which then dispatches
a runnable

See [Link]/android-core-looper-handler-and-handlerthread-bd54d69fe91a
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
• The framework controls the
main execution thread
• Decides how/when to run
app code via callbacks
• IoC is often called “The
Hollywood Principle”

See [Link]/~schmidt/Coursera/articles/[Link]
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality

Stock Mobile
Trading Social Apps
Media

Networking
Databases

GUIs

See [Link]/wiki/Domain-driven_design
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality
• e.g., capabilities that can
be reused in 1+ domain(s) Stock Mobile
Trading Social Apps
Media
Application
domains
Networking
Databases

Infrastructure GUIs
domains
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality
• e.g., capabilities that can
be reused in 1+ domain(s) Stock Mobile
Trading Social Apps
Media

Networking
Databases

GUIs

Application-specific functionality can systematically reuse framework components.

 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality
3. Semi-complete applications
Stock Mobile
Trading Social Apps
Media

Networking
Databases

GUIs
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality
3. Semi-complete applications
Mobile
• Hook methods plug app Stock
Social Apps
Trading
logic into the framework Media

Networking
Databases

GUIs

See [Link]/davelaribee/2008/06/16/hook-methods
 OO Design of Expression Tree Processing App
• Apply “Gang of Four” (GoF) patterns to guide the development of a
framework of extensible classes.
• A framework is an integrated set of software components that collaborate
to provide a reusable architecture for a family of related applications.
• Frameworks exhibit three characteristics that differentiate them from other
forms of systematic reuse. Application-Specific Functionality
1. Inversion of control (IoC)
2. Domain-specific structure
& functionality
3. Semi-complete applications
Mobile
• Hook methods plug app Stock
Social Apps
Trading
logic into the framework Media

• Mediate interactions among

common abstract & variant Networking
Databases
concrete classes/interfaces
GUIs

e.g., Java Runnable is an abstract interface providing basis for concrete variants.
 OO Design of Expression Tree Processing App
• Integrate pattern-oriented language & library features with frameworks.
• Both an app-specific framework…
ExpressionTree tree = ...;
Visitor printVisitor = ...;

for(Iterator<ExpressionTree> iter =
[Link](traversalOrder);
[Link]();)
[Link]().accept(printVisitor);

Factory Method, Bridge, Composite, Iterator, Strategy, & Visitor patterns

This app-specific framework exhibits high pattern density!

 OO Design of Expression Tree Processing App
• Integrate pattern-oriented language & library features with frameworks.
• Both an app-specific framework… & off-the-shelf frameworks…

See [Link] & [Link]/wiki/Java_Class_Library.

 OO Design of Expression Tree Processing App
• Complexity resides in (stable) structure & APIs, rather than (variable)
algorithms.
Visitor
Bridge
ExpressionTree ComponentNode
Visitor
<< accept >>
<< create >>
Composite LeafNode
UnaryNode

Java Iterator EvaluationVisitor PrintVisitor

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator

See [Link]/windows/software-complexity-bringing-order-to-ch/199901062
Overview of the Patterns Used
in the Expression Tree
Processing App

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize which GoF patterns the expression tree processing app uses.

Creational Structural Behavioral

Class Factory Adapter √ Interpreter √
Method √ (class) Template Method √
Object Abstract Adapter √ Chain of Responsibility
Factory √ (object) Command √
Builder √ Bridge √ Iterator √
Prototype Composite √ Mediator
Singleton √ Decorator √ Memento
Flyweight Observer √
Façade State √
Proxy Strategy √
Visitor √
Douglas C. Schmidt
Lesson Introduction
 Lesson Introduction
• The book Design Patterns: Elements of Reusable Object-Oriented Software
(the so-called "Gang of Four" or "GoF" book) presents recurring solutions to
common problems in software design in the form of 23 patterns.

Creational Structural Behavioral

Class Factory Adapter Interpreter
Method (class) Template Method
Object Abstract Adapter Chain of Responsibility
Factory (object) Command
Builder Bridge Iterator
Prototype Composite Mediator
Singleton Decorator Memento
Flyweight Observer
Façade State
Proxy Strategy
Visitor
Douglas C. Schmidt
Design Problems &
GoF Pattern Solutions
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability −5*(3+4)
Bridge
Inflexible expression input processing −35 Interpreter
Inflexible interpreter output Builder
Scattered request implementations Command
Inflexible creation of variabilities Factory Method
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template Method
Minimizing global variable liabilities Singleton
These patterns constitute a “pattern sequence” for the case study app.
See [Link]/~schmidt/[Link]
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Non-extensible & error-prone designs Composite
Composite intent
• Treat individual objects & multiple, recursively-composed objects uniformly

See [Link]/wiki/Composite_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Minimizing impact of variability Bridge
Bridge intent
• Separate an abstraction from its implementation(s) so the two can vary independently

See [Link]/wiki/Bridge_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Scattered & fixed request implementations Command
Command intent
• Encapsulate the request for a service as an object

ConcreteCommand

See [Link]/wiki/Command_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Inflexible creation of variabilities Factory Method
Factory Method intent
• Provide an interface for creating an object, but leave the choice of the object’s
concrete type to a subclass

See [Link]/wiki/Factory_method_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Inflexible expression tree traversal Iterator
Iterator intent
• Access elements of an aggregate without exposing its representation

See [Link]/wiki/Iterator_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Obtrusive behavior changes Strategy
Strategy intent
• Define a family of algorithms, encapsulate each one, & make them interchangeable to
let clients & algorithms vary independently

See [Link]/wiki/Strategy_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Non-extensible tree operations Visitor
Visitor intent
• Centralize operations on an object structure so that they can vary independently, but
still behave polymorphically

See [Link]/wiki/Visitor_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Incorrect user request ordering State
State intent
• Allow an object to alter its behavior when its internal state changes—the object will
appear to change its class

See [Link]/wiki/State_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Non-extensible operating modes Template Method
Template Method intent
• Provide a skeleton of an algorithm in a method, deferring some steps to subclasses

See [Link]/wiki/Template_method_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Inflexible expression input processing Interpreter
Interpreter intent
• Given a language, define a representation for its grammar, along with an interpreter
that uses the representation to interpret sentences in the language

See [Link]/wiki/Interpreter_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Inflexible interpreter output Builder
Builder intent
• Separate the construction of a complex object from its representation

See [Link]/wiki/Builder_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Minimizing global variable liabilities Singleton
Singleton intent
• Ensure a class only has one instance & provide a global point of access

See [Link]/wiki/Singleton_pattern
 Design Problems & GoF Pattern Solutions
Design Problem Pattern
Non-extensible & error-prone designs Composite
Minimizing impact of variability Bridge
Inflexible expression input processing Interpreter
Inflexible interpreter output Builder
Scattered request implementations Command
Inflexible creation of variabilities Factory Method
Inflexible expression tree traversal Iterator
Obtrusive behavior changes Strategy
Non-extensible tree operations Visitor
Incorrect user request ordering State
Non-extensible operating modes Template Method
Minimizing global variable liabilities Singleton

Naturally, these patterns apply to more than expression tree processing apps!
The Composite Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Composite pattern ComponentNode
can be applied to make the expression
tree object structure more uniform &
extensible. Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
Douglas C. Schmidt
Motivating the Need for
the Composite Pattern in
the Expression Tree App
A Pattern for Structuring the Expression Tree
Purpose: Define the key internal data structure for the expression tree.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode

Composite

Composite simplifies adding new types of nodes (& new node operations).
 Context: OO Expression Tree Processing App
• The design of an expression tree should reflect its “physical” structure.

×
− +

5 3 4
 Context: OO Expression Tree Processing App
• The design of an expression tree should reflect its “physical” structure.
• e.g., the tree structure should contain
binary/unary operators & operands. Binary
Nodes
×
− +
Unary
Node 5 3 4

Leaf
Nodes
 Context: OO Expression Tree Processing App
• Adding new operations on tree nodes should require little/no modifications to
the tree’s structure & implementation.
Operation 2: Evaluate
Operation 1: Print all “yield” of nodes in tree
values of nodes in tree ×
− +

5 3 4

See upcoming lesson on “The Visitor Pattern.”

 Problem: Non-Extensible & Error-Prone Designs
• Tightly coupling expression tree typedef struct TreeNode {
data structures & functionality enum { NUM, UNARY, BINARY } tag_;
impedes extensibility. short use_;
union {
char op_[3]; int num_;
1 } o_;
Tree #define num_ o_.num_
Node #define op_ o_.op_
0|1|2 union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;

See lesson on “Evaluating the Algorithmic Decomposition of the Expression Tree Processing App”
 Problem: Non-Extensible & Error-Prone Designs
• Tightly coupling expression tree typedef struct TreeNode {
data structures & functionality enum { NUM, UNARY, BINARY } tag_;
impedes extensibility. short use_;
union {
char op_[3]; int num_;
1 } o_;
Tree #define num_ o_.num_
Node #define op_ o_.op_
0|1|2 union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;

Lack of extensibility was a major limitation with algorithmic decomposition.

 Problem: Non-Extensible & Error-Prone Designs
• Tightly coupling expression tree typedef struct TreeNode {
data structures & functionality enum { NUM, UNARY, BINARY,
impedes extensibility. TERNARY } tag_;
union {
• e.g., adding new types of nodes char op_[4];
or new node operations affects int num_;
many parts of the program. } o_;
...
union {
...
struct {
Tree_Node *l_,
*m_,
*r_;
} ternary_;
} c_;
#define ternary_ c_.ternary_
} TreeNode;

See lesson on “Evaluating the Algorithmic Decomposition of the Expression Tree Processing App”
 Problem: Non-Extensible & Error-Prone Designs
• Differentiating operators & operands via type tags & switch statements is
tedious & error-prone to program & maintain.

See [Link]/?SwitchStatementsSmell
 Solution: Recursive Object Structure
• Model an expression tree as a recursive collection of nodes

×
− +

5 3 4
 Solution: Recursive Object Structure
• Model an expression tree as a recursive collection of nodes, e.g.,
• Structure nodes into a hierarchy that
captures the properties of each node ×
− +

5 3 4
 Solution: Recursive Object Structure
• Model an expression tree as a recursive collection of nodes, e.g.,
• Structure nodes into a hierarchy that
captures the properties of each node, e.g.,
• Leaf nodes contain no children
×
− +

5 3 4

Leaf
Nodes
 Solution: Recursive Object Structure
• Model an expression tree as a recursive collection of nodes, e.g.,
• Structure nodes into a hierarchy that
captures the properties of each node, e.g.,
• Leaf nodes contain no children
×
• Unary nodes recursively contain
one child node − +
Unary
Node
5 3 4
 Solution: Recursive Object Structure
• Model an expression tree as a recursive collection of nodes, e.g.,
• Structure nodes into a hierarchy that Binary
captures the properties of each node, e.g., × Nodes
• Leaf nodes contain no children
• Unary nodes recursively contain
one child node − +
• Binary nodes recursively contain
two child nodes

5 3 4
 Solution: Recursive Object Structure
• Treat operators & operands uniformly
• e.g., minimize the distinction between Binary
“one vs. many” to avoid special cases. × Nodes

− +
Unary
Node
5 3 4

Leaf
Nodes
 ComponentNode Interface Overview
• Interface for composable expression tree node objects

Interface methods
int getItem()
ComponentNode getLeftChild()
ComponentNode getRightChild()
void accept(Visitor visitor)
 ComponentNode Interface Overview
• Interface for composable expression tree node objects
These methods access relevant fields (may
Interface methods be no-ops for some implementations).
int getItem()
ComponentNode getLeftChild()
ComponentNode getRightChild()
void accept(Visitor visitor)
 ComponentNode Interface Overview
• Interface for composable expression tree node objects

Interface methods
int getItem()
ComponentNode getLeftChild()
ComponentNode getRightChild()
void accept(Visitor visitor)

This hook method plays an essential

role in Iterator & Visitor patterns.

See upcoming lessons on “The Iterator Pattern” & “The Visitor Pattern.”
 ComponentNode Interface Overview
• Interface for composable expression tree node objects

Interface methods
int getItem()
ComponentNode getLeftChild()
ComponentNode getRightChild()
void accept(Visitor visitor)

• Commonality: the interface used by all nodes in an expression tree

• Variability: each implementation defines the state & methods that can
be customized for specific types of expression tree nodes
 ComponentNode Class Hierarchy Overview
• Note the inherent recursion LeafNode is a
in this hierarchy. ComponentNode
ComponentNode.

Composite
LeafNode
UnaryNode
CompositeUnaryNode is a
ComponentNode & also has
a ComponentNode. CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

CompositeBinaryNode is a Composite Composite

CompositeUnaryNode & MultiplyNode DivideNode
also has a ComponentNode.
 ComponentNode Class Hierarchy Overview
• Note the inherent recursion
in this hierarchy. ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
2 Node Node
This is another way to
design this type of
inheritance hierarchy. Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
The Composite Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Composite pattern can be applied to make the expression
tree more uniform & extensible.
• Understand the structure & functionality of the Composite pattern.
Douglas C. Schmidt
Structure & Functionality
of the Composite Pattern
 Composite GoF Object Structural
Intent
ComponentNode
• Treat individual objects & multiple,
recursively-composed objects
uniformly
Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

See [Link]/wiki/Composite_pattern
 Composite GoF Object Structural
Applicability
ComponentNode
• Objects must be composed
recursively
Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
e.g., CompositeBinaryNode MultiplyNode DivideNode

contains other types of nodes.

 Composite GoF Object Structural
Applicability
ComponentNode
• Objects must be composed
recursively
• And no distinction between Composite
LeafNode
individual & composed UnaryNode
elements
CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
e.g., LeafNodes & Composite
*Nodes all share the same API.
 Composite GoF Object Structural
Applicability
ComponentNode
• Objects must be composed
recursively
• And no distinction between Composite
LeafNode
individual & composed UnaryNode
elements
• And objects in structure can CompositeBinary CompositeNegate
be treated uniformly Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
e.g., LeafNodes & Composite
*Nodes are (largely) treated the
same by operations on a tree.

See upcoming lessons on “The Iterator Pattern” & “The Visitor Pattern.”
 Composite GoF Object Structural
Structure & participants
 Composite GoF Object Structural
Structure & participants

Some program (also

Bridge “abstraction”)

See upcoming lessons on the Bridge pattern.

 Composite GoF Object Structural
Structure & participants ComponentNode
 Composite GoF Object Structural
Structure & participants

CompositeUnaryNode,
CompositeBinaryNode,
CompositeAddNode, etc.
 Composite GoF Object Structural
Structure & participants

LeafNode
The Composite Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Composite pattern can be applied to make the expression
tree more uniform & extensible.
• Understand the structure & functionality of the Composite pattern.
• Know how to implement the Composite pattern in Java.
Douglas C. Schmidt
Implementing the Composite
Pattern in Java
 Composite GoF Object Structural
Composite example in Java
• Build an expression tree based on recursively composed objects.
ComponentNode l1 =
new LeafNode(5);
ComponentNode l2 =
new LeafNode(3);
ComponentNode l3 =
new LeafNode(4);

l1 l2 l3
 Composite GoF Object Structural
Composite example in Java
• Build an expression tree based on recursively composed objects.
ComponentNode l1 =
new LeafNode(5);
ComponentNode l2 =
new LeafNode(3); u1 b1
ComponentNode l3 =
new LeafNode(4);
ComponentNode u1 =
new CompositeNegateNode(l1);
ComponentNode b1 = l1 l2 l3
new CompositeAddNode(l2, l3);
 Composite GoF Object Structural
Composite example in Java
• Build an expression tree based on recursively composed objects.
ComponentNode l1 =
new LeafNode(5); b2
ComponentNode l2 =
new LeafNode(3); u1 b1
ComponentNode l3 =
new LeafNode(4);
ComponentNode u1 =
new CompositeNegateNode(l1);
ComponentNode b1 = l1 l2 l3
new CompositeAddNode(l2, l3);
ComponentNode b2 =
new CompositeMultiplyNode(u1, b1);
 Composite GoF Object Structural
Composite example in Java
• Build an expression tree based on recursively composed objects.
ComponentNode l1 =
new LeafNode(5); b2
ComponentNode l2 =
new LeafNode(3); u1 b1
ComponentNode l3 =
new LeafNode(4);
ComponentNode u1 =
new CompositeNegateNode(l1);
ComponentNode b1 = l1 l2 l3
new CompositeAddNode(l2, l3);
ComponentNode b2 =
new CompositeMultiplyNode(u1, b1);

Java’s garbage collector deletes dynamically allocated

memory automatically when it’s no longer needed.

See [Link]/webfolder/technetwork/tutorials/obe/java/gc01/[Link]
 Composite GoF Object Structural
Composite example in Java
• Build an expression tree based on recursively composed objects.
ComponentNode exprTree =
makeExpressionTree
("-5 * (3 + 4)");

A better way to build an expression tree is

to apply a Creational pattern that shields
client programs from the details of how the
composite expression tree is implemented

See upcoming lessons on the Builder (& Interpreter) patterns.

The Composite Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Composite pattern can be applied to make the expression
tree more uniform & extensible.
• Understand the structure & functionality of the Composite pattern.
• Know how to implement the Composite pattern in Java.
• Be aware of other considerations when applying the Composite pattern.
Douglas C. Schmidt
Other Considerations of
the Composite Pattern
 Composite GoF Object Structural
Consequences ExpressionTree exprTree = ...;
+ Uniformity Visitor visitor = ...;
• Treat components the
same regardless of for (Iterator<ExpressionTree> iter =
complexity & behavior [Link]
(traversalOrder);
[Link]();)
[Link]().accept(visitor);

No syntactic distinction between leaf nodes

or composite nodes (iterator variant)

Eliminate type tags & switch statements when combined with other patterns.
 Composite GoF Object Structural
Consequences ExpressionTree exprTree = ...;
+ Uniformity Visitor visitor = ...;
• Treat components the
same regardless of for (Iterator<ExpressionTree> iter =
complexity & behavior [Link]
(traversalOrder);
[Link]();)
[Link]().accept(visitor);

StreamUtils
.iteratorToStream(iter, false)
.forEach(exprTree ->
[Link](visitor));

Converts an iterator to a Java stream

See ExpressionTree/CommandLine/src/expressiontree/utils/[Link]
 Composite GoF Object Structural
Consequences ExpressionTree exprTree = ...;
+ Uniformity Visitor visitor = ...;
• Treat components the
same regardless of for (Iterator<ExpressionTree> iter =
complexity & behavior [Link]
(traversalOrder);
[Link]();)
[Link]().accept(visitor);

StreamUtils
.iteratorToStream(iter, false)
.forEach(exprTree ->
[Link](visitor));

No syntactic distinction between leaf nodes

or composite nodes (Java stream’s variant)

See [Link]/javase/8/docs/api/java/util/stream/[Link]#forEach
 Composite GoF Object Structural
Consequences
+ Uniformity ComponentNode

+ Extensibility
• New component subclasses work Composite
UnaryNode
LeafNode

wherever existing ones do

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite Composite

ModNode MultiplyNode DivideNode
 Composite GoF Object Structural
Consequences
public interface ComponentNode {
+ Uniformity
+ Extensibility
+ Parsimony
default int getItem() {
• Classes & interfaces throw new
only include fields & UnsupportedOperationException
methods that they need ("method not implemented");
}

default ComponentNode getRightChild(){

return null;
}

default ComponentNode getLeftChild() {

return null;
}
...
}

See ExpressionTree/CommandLine/src/expressiontree/nodes
 Composite GoF Object Structural
Consequences
public interface ComponentNode {
+ Uniformity
+ Extensibility Only static fields & default “no-op” methods
+ Parsimony
default int getItem() {
• Classes & interfaces throw new
only include fields & UnsupportedOperationException
methods that they need ("method not implemented");
}

default ComponentNode getRightChild(){

return null;
}

default ComponentNode getLeftChild() {

return null;
}
...
}

See [Link]/javase/tutorial/java/IandI/[Link]
 Composite GoF Object Structural
Consequences
public class LeafNode
+ Uniformity implements ComponentNode {
+ Extensibility ...
private int mItem;
+ Parsimony
• Classes & interfaces int getItem()
Stores the Leaf
only include fields & { return mItem; }
Node’s value
methods that they need }

public class CompositeUnaryNode

implements ComponentNode {
...
ComponentNode mRight;

ComponentNode getRightChild()
{ return mRight; }
}

See ExpressionTree/CommandLine/src/expressiontree/nodes
 Composite GoF Object Structural
Consequences
public class LeafNode
+ Uniformity implements ComponentNode {
+ Extensibility ...
private int mItem;
+ Parsimony
• Classes & interfaces int getItem()
only include fields & { return mItem; }
methods that they need }

public class CompositeUnaryNode

implements ComponentNode {
...
ComponentNode mRight;

ComponentNode getRightChild()
Reference to { return mRight; }
the right child. }

See ExpressionTree/CommandLine/src/expressiontree/nodes
 Composite GoF Object Structural
Consequences
– Perceived complexity ComponentNode

• May need what seems like a

prohibitively large number of
classes and/or objects Composite
UnaryNode
LeafNode

1
Tree CompositeBinary CompositeNegate
Node vs. Node Node

0|1|2
Algorithmic Decomposition Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

Pattern- & OO-Decomposition

 Composite GoF Object Structural
Consequences
– Perceived complexity ComponentNode

• May need what seems like a

prohibitively large number of
classes and/or objects Composite
UnaryNode
LeafNode

1
Tree CompositeBinary CompositeNegate
Node vs. Node Node

0|1|2
Algorithmic Decomposition Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

Pattern- & OO-Decomposition

Knowledge of patterns is essential to alleviate perceived complexity.

 Composite GoF Object Structural
Consequences
– Awkward designs getItem() is unused
• May yield “bloated” interfaces in composite nodes.
for composites & leaves
getLeftChild() &
getRightChild() are
unused in leaf nodes.

int getItem()
ComponentNode getLeftChild()
ComponentNode getRightChild()
void accept(Visitor visitor)

See [Link]/wiki/Interface_bloat
 Composite GoF Object Structural
Implementation considerations
• Do components know their parents?
• e.g., is there an explicit “parent”
pointer/reference?
 Composite GoF Object Structural
Implementation considerations
• Uniform interface for both leaves &
composites?
• Trade-off between uniformity
& parsimony

Leaf inherits methods

that it doesn’t need.
 Composite GoF Object Structural
Implementation considerations tag_
• Don’t allocate child storage in
use_
component super class.
typedef struct TreeNode { op_
enum { NUM, UNARY, BINARY } tag_;
short use_; num_
union {
char op_[3]; int num_;
} o_; unary_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_; binary_
} c_; Memory
} TreeNode; Layout

This was a big problem with

the algorithmic decomposition.
 Composite GoF Object Structural
Implementation considerations
• Who is responsible for deleting
children?
• e.g., the parent or the
child itself?

See rmdir vs. /bin/rm -rf at [Link]/[Link]

 Composite GoF Object Structural
Known uses
• ET++ Vobjects
• InterViews Glyphs,
Styles
• Unidraw Components,
MacroCommands
• Internal representations
of MIME types
• Directory structures on
UNIX & Windows
• [Link] Leaf Node
#add(Component)
• Naming Contexts in
CORBA Composite Node
 Summary of the Composite Pattern
• The expression tree processing app uses the Composite pattern to enhance
the uniformity & extensibility of its key internal data structure.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode

Composite

Adding new types of nodes (& new operations on nodes) is greatly simplified.
The Bridge Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Bridge pattern can be applied to make the expression
tree structure easier to access & evolve transparently.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode
Instrumented Synchronized
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode
Douglas C. Schmidt
Motivating the Need for
the Bridge Pattern in
the Expression Tree App
 A Pattern for Binding One of Many Variations
Purpose: Decouple the expression tree programming API from its
behavior & implementation to enable transparent extensibility.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode
Instrumented Synchronized
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode

Bridge Composite

Bridge minimizes coupling between clients, abstractions, & implementations.

 Context: OO Expression Tree Processing App
• The app needs to run in a range of design-time & runtime environments
 Context: OO Expression Tree Processing App
• The app needs to run in a range of design-time & runtime environments, e.g.,
• Mobile devices with limited memory &
processing power
 Context: OO Expression Tree Processing App
• The app needs to run in a range of design-time & runtime environments, e.g.,
• Mobile devices with limited memory &
processing power
• Laptops & desktops with more
abundant resources
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
ComponentNode
ComponentNode node =
new CompositeAddNode Composite
LeafNode
UnaryNode
(new LeafNode(3),
new LeafNode(4)); CompositeBinary
Node
CompositeNegate
Node

Composite Composite
AddNode MultiplyNode …
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
ComponentNode
ComponentNode node =
new CompositeAddNode Composite
LeafNode
UnaryNode
(new LeafNode(3),
new LeafNode(4)); CompositeBinary
Node
CompositeNegate
Node

vs. Composite
AddNode
Composite
MultiplyNode …

ComponentNode node =
new TreeNode ComponentNode
(′+′,
new TreeNode(3),
new TreeNode(4));
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
ComponentNode
ComponentNode node =
new CompositeAddNode Composite
LeafNode
UnaryNode
(new LeafNode(3),
new LeafNode(4)); CompositeBinary
Node
CompositeNegate
Node

Different implementations have

different time/space trade-offs Composite
AddNode
Composite
MultiplyNode …

ComponentNode node =
new TreeNode ComponentNode
(′+′,
new TreeNode(3),
new TreeNode(4));

We should be able to change implementations without breaking client code.

 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
• Hard to change services
transparently
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
• Hard to change services
transparently, e.g.,
• Want to transparently
add instrumentation to
expression tree operations
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
• Hard to change services
transparently, e.g.,
• Want to transparently
add instrumentation to
expression tree operations
• Want to transparently add
synchronization to expression
tree methods
 Problem: Minimizing Impact of Variability
• Tightly coupling app components to a particular environment has drawbacks.
• Suboptimal implementations
for a given context
• Hard to change services
transparently, e.g.,
• Want to transparently
add instrumentation to
expression tree operations
• Want to transparently add
synchronization to expression
tree methods
• ...

We should be able to enhance the service without breaking its implementation.

 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction

ExpressionTree
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode
Synchronized Instrumented
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.
Variations in
expression tree
ExpressionTree
ComponentNode
implementations

Composite
LeafNode
UnaryNode
Synchronized Instrumented
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode
Synchronized Instrumented
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Variations in
what service is Composite Composite Composite Composite
provided by an AddNode MultiplyNode SubtractNode DivideNode
expression tree
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.
• Client calls to the abstraction are forwarded to the corresponding
implementor subclass.

mRoot ComponentNode
ExpressionTree
accept(Visitor v) accept(Visitor v)
[Link](v);
…

LeafNode …
accept(Visitor v) accept(Visitor v)
… …
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.
• Client calls to the abstraction are forwarded to the corresponding
implementor subclass.
• Subclass the abstraction class to enable different services without affecting
the implementor hierarchy.

mRoot ComponentNode
ExpressionTree
accept(Visitor v) accept(Visitor v)
…

Synchronized LeafNode …
synchronized(this)
ExpressionTree accept(Visitor v) accept(Visitor v)
{ [Link](v); }
accept(Visitor v) … …
 Solution: Separate Abstraction & Implementation
• Encapsulate variability behind a stable API that creates separate class
hierarchies for an abstraction & its implementations.
• Client calls to the abstraction are forwarded to the corresponding
implementor subclass.
• Subclass the abstraction class to enable different services without affecting
the implementor hierarchy.

mRoot ComponentNode
ExpressionTree
accept(Visitor v) accept(Visitor v)
…

Instrumented log(“begin call”); LeafNode …

ExpressionTree [Link](v);
accept(Visitor v) accept(Visitor v)
log(“end call”);
accept(Visitor v) … …
 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods

ExpressionTree(ComponentNode root)
boolean isNull()
int getItem()
ExpressionTree getLeftChild()
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)

See upcoming lessons on Factory Method, Iterator, & Visitor patterns.

 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods
Pass in the root of the
implementor hierarchy

ExpressionTree(ComponentNode root)
boolean isNull()
int getItem()
ExpressionTree getLeftChild()
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)
 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods
Forward to
implementor
hierarchy ExpressionTree(ComponentNode root)
boolean isNull()
int getItem()
ExpressionTree getLeftChild()
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)
 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods

ExpressionTree(ComponentNode root)
boolean isNull()
int getItem() Plays essential role in the
ExpressionTree getLeftChild() Iterator & Visitor patterns.
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)

See upcoming lessons on “The Iterator Pattern” & “The Visitor Pattern.”
 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods

ExpressionTree(ComponentNode root)
boolean isNull()
int getItem()
ExpressionTree getLeftChild()
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)

Factory method creates iterator

See upcoming lessons on Factory Method, Iterator, & Strategy patterns.

 ExpressionTree Class Overview
• Defines an abstraction that shields clients from implementation details of
expression tree that may change at design-time or runtime
Class methods

ExpressionTree(ComponentNode root)
boolean isNull()
int getItem()
ExpressionTree getLeftChild()
ExpressionTree getRightChild()
void accept(Visitor visitor)
Iterator
<ExpressionTree> iterator(String traversalOrder)

• Commonality: provides a common interface for expression tree

operations
• Variability: component nodes will vary depending on user input
expressions; iterator behavior can vary; & expression tree itself can vary
The Bridge Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Bridge pattern can be applied to make the expression
tree structure easier to access & evolve transparently.
• Understand the structure & functionality of the Bridge pattern.
Douglas C. Schmidt
Structure & Functionality
of the Bridge Pattern
 Bridge GoF Object Structural
Intent
ExpressionTree
• Separate an abstraction from its
implementation(s) so the two
can vary independently
ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

See [Link]/wiki/Bridge_pattern
 Bridge GoF Object Structural
Applicability
ExpressionTree
• When the abstraction & extensible
implementation(s) can vary
independently
ComponentNode

e.g., the ExpressionTree service

can be refined without affecting clients Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Bridge GoF Object Structural
Applicability
ExpressionTree
• When the abstraction & extensible
implementation(s) can vary
independently
ComponentNode
• When there’s a need to change
implementor hierarchies at design-
time or runtime without breaking Composite
LeafNode
client code
UnaryNode

CompositeBinary CompositeNegate
Node Node

e.g., the ComponentNode

implementor hierarchy can Composite Composite

change without affecting clients. AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Bridge GoF Object Structural
Applicability
ExpressionTree
• When the abstraction & extensible
implementation(s) can vary
independently
ComponentNode
• When there’s a need to change
implementor hierarchies at design-
time or runtime without breaking Composite
LeafNode
client code
UnaryNode

CompositeBinary CompositeNegate
Node Node

e.g., the ComponentNode

implementor hierarchy can Composite Composite

change without affecting clients. AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Bridge GoF Object Structural
Structure & participants

operation() operationImp()

[Link]();

operationImp() operationImp()
 Bridge GoF Object Structural
Structure & participants

ExpressionTree

operation() operationImp()

[Link]();

operationImp() operationImp()
 Bridge GoF Object Structural
Structure & participants

ComponentNode

operation() operationImp()

[Link]();

operationImp() operationImp()
 Bridge GoF Object Structural
Structure & participants

operation() operationImp()

[Link]();

operationImp() operationImp()
 Bridge GoF Object Structural
Structure & participants

operation() operationImp()

[Link]();

operationImp() operationImp()

LeafNode, CompositeAddNode,
CompositeSubtractNode, etc.
 Bridge GoF Object Structural
Structure & participants

operation() operationImp()

[Link]();

operationImp() operationImp()

SynchronizedExpressionTree,
InstrumentedExpressionTree, etc.
The Bridge Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Bridge pattern can be applied to make the expression
tree structure easier to access & evolve transparently.
• Understand the structure & functionality of the Bridge pattern.
• Know how to implement the Bridge pattern in Java.
Douglas C. Schmidt
Implementing the Bridge
Pattern in Java
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class ExpressionTree {
private ComponentNode mRoot;

public ExpressionTree(ComponentNode root) {

mRoot = root;

...
public void accept(Visitor v) { [Link](v); }

See ExpressionTree/CommandLine/src/expressiontree/tree
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class ExpressionTree {
Stores root of composite
private ComponentNode mRoot; implementor hierarchy

public ExpressionTree(ComponentNode root) {

mRoot = root;

...
public void accept(Visitor v) { [Link](v); }

}
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class ExpressionTree {
private ComponentNode mRoot;

public ExpressionTree(ComponentNode root) {

mRoot = root; Pass in root of composite
implementor hierarchy

...
public void accept(Visitor v) { [Link](v); }

}
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class ExpressionTree {
private ComponentNode mRoot;

public ExpressionTree(ComponentNode root) {

mRoot = root;

...
public void accept(Visitor v) { [Link](v); }
Abstraction forwards to
}
implementor via mRoot

See upcoming lessons on Iterator & Visitor patterns.

 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class InstrumentedExpressionTree extends ExpressionTree {
public void accept(Visitor v) {
[Link]("starting accept() call" + ...);
[Link](v);
[Link]("finished accept() call" + ...);
}
...
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class InstrumentedExpressionTree extends ExpressionTree {
public void accept(Visitor v) {
[Link]("starting accept() call" + ...);
[Link](v);
[Link]("finished accept() call" + ...);
}
... Print logging messages both
before & after call to accept()

See [Link]/2015/10/[Link]
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class InstrumentedExpressionTree extends ExpressionTree {
public void accept(Visitor v) {
[Link]("starting accept() call" + ...);
[Link](v);
[Link]("finished accept() call" + ...);
}
...

class SynchronizedExpressionTree extends ExpressionTree {

public void accept(Visitor v) {
synchronized(this) {
[Link](v);
}
...
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.
class InstrumentedExpressionTree extends ExpressionTree {
public void accept(Visitor v) {
[Link]("starting accept() call" + ...);
[Link](v);
[Link]("finished accept() call" + ...);
}
...

class SynchronizedExpressionTree extends ExpressionTree {

public void accept(Visitor v) {
synchronized(this) {
[Link](v);
}
... Synchronize the call to accept()
 Bridge GoF Object Structural
Bridge example in Java
• Separate expression tree abstraction from composite implementor hierarchy.

mRoot ComponentNode
ExpressionTree
accept(Visitor v) accept(Visitor v)
…

LeafNode …
Synchronized
ExpressionTree accept(Visitor v) accept(Visitor v)
… …
accept(Visitor v)

Instrumented
ExpressionTree
accept(Visitor v)

Changes in service behavior don’t affect implementor hierarchy & vice versa.
 Bridge GoF Object Structural
Bridge example in Java
• Encapsulate sources of variability in expression tree construction & use.

ExpressionTree exprTree
(new CompositeAddNode
(new LeafNode(3),
new LeafNode(4)));
Hide use of complex recursive
Composite internal structure
behind a stable Bridge API
 Bridge GoF Object Structural
Bridge example in Java
• Encapsulate sources of variability in expression tree construction & use.

ExpressionTree exprTree
(new CompositeAddNode
(new LeafNode(3),
new LeafNode(4)));

Replace Composite implementation

with TreeNode implementation

ExpressionTree exprTree
(new TreeNode
(′+′,
new TreeNode(3),
new TreeNode(4)));
 Bridge GoF Object Structural
Bridge example in Java
• Encapsulate sources of variability in expression tree construction & use.

ExpressionTree exprTree
(makeExpressionTree("3+4"));
We can apply a creational pattern
to reduce client dependencies on
implementation variability.

See upcoming lessons on the Interpreter & Builder patterns.

 Bridge GoF Object Structural
Bridge example in Java
• Encapsulate sources of variability in expression tree construction & use.

Regardless of which implementation or

abstraction was used, however, we can
iterate through all tree elements without
concern for how the tree is structured
internally.
for (Iterator<ExpressionTree> it =
[Link]();
[Link]();)
doSomethingWithEachNode([Link]());

Factory Method, Composite, Iterator, Strategy, & Visitor are also relevant here.
The Bridge Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Bridge pattern can be applied to make the expression
tree structure easier to access & evolve transparently.
• Understand the structure & functionality of the Bridge pattern.
• Know how to implement the Bridge pattern in Java.
• Be aware of other considerations when applying the Bridge pattern.
Douglas C. Schmidt
Other Considerations of
the Bridge Pattern
 Bridge GoF Object Structural
Consequences
+ Abstraction & implementor Enable software to be open for extension
hierarchy are decoupled (via implementor hierarchy), but closed for
• Can evolve separately by modification (via stable abstraction API)
applying Open/Closed Principle

[Link]/wiki/Open/closed_principle has info on Open/Closed Principle.

 Bridge GoF Object Structural
Consequences
+ Abstraction & implementor
hierarchy are decoupled
• Can evolve separately by
Extend software behavior by adding
applying Open/Closed Principle
new code via subclassing, not by
changing/breaking existing client code.

[Link]/wiki/Open/closed_principle has info on Open/Closed Principle.

 Bridge GoF Object Structural
Consequences
+ Implementors can vary at
design-time or runtime ExpressionTree exprTree
(new CompositeAddNode
(new LeafNode(3),
new LeafNode(4)));

versus

ExpressionTree exprTree
(new TreeNode
(′+′,
new TreeNode(3),
new TreeNode(4)));
 Bridge GoF Object Structural
Consequences
– “One-size-fits-all” abstraction
& implementor interfaces

See [Link]/wiki/Procrustes#Cultural_references
 Bridge GoF Object Structural
Consequences
– “One-size-fits-all” abstraction
& implementor interfaces
• Can be alleviated via other patterns, e.g.,
• Adapter—makes existing classes work with others
without modifying code

request() specificRequest()

request() [Link]()

[Link]/wiki/Adapter_pattern has more on Adapter.

 Bridge GoF Object Structural
Consequences
– “One-size-fits-all” abstraction
& implementor interfaces
• Can be alleviated via other patterns, e.g.,
• Adapter—makes existing classes work with others
without modifying code
• Strategy—lets the algorithm vary independently from clients that use it

[Link]/wiki/Strategy_pattern has more on Strategy.

 Bridge GoF Object Structural
Consequences
– “One-size-fits-all” abstraction
& implementor interfaces
• Can be alleviated via other patterns, e.g.,
• Adapter—makes existing classes work with others
without modifying code
• Strategy—lets the algorithm vary independently from clients that use it
• Extension Interface—allows multiple interfaces to be exported by a
component, to prevent bloating of interfaces & breaking of client code
when developers extend or modify the functionality of the component

See [Link]/pub/sag/[Link]
 Bridge GoF Object Structural
Implementation considerations
• Creating the right abstraction or implementor
• Often addressed by using Creational patterns
• e.g., Factory Method or Builder

class Multiply extends Operator {

...
ComponentNode build() {
return new CompositeMultiplyNode([Link](), [Link]());
}
class Number extends Expr {
...
Build corresponding ComponentNode build()
component nodes { return new LeafNode(item); }

We’ll cover Builder later & show how it creates composite expression trees.
 Bridge GoF Object Structural
Implementation considerations
• Sharing implementors & reference counting
• e.g., C++11/Boost shared_ptr

ExpressionTree instances

+ +
Shared CompositeAddNode Reference Reference Reference
Count: 2 Count: 1 Count: 0

See [Link]/wiki/Smart_pointer#shared_ptr_and_weak_ptr
 Bridge GoF Object Structural
Implementation considerations
• Dynamic uses of Bridge should be implemented via Decorator.

operation()

operation() operation() [Link]()

[Link]();
operation() operation()
addedBehavior();
addedBehavior()

[Link]/wiki/Decorator_pattern has more on Decorator.

 Bridge GoF Object Structural
Implementation considerations
• Dynamic uses of Bridge should be implemented via Decorator.

operation()

operation() operation() [Link]()

[Link]();
operation() operation()
addedBehavior();
addedBehavior()

• Decorator enables client-specified embellishment of a core object by

recursively wrapping it (possibly more than once) dynamically at runtime.

See [Link]/design_patterns/decorator
 Bridge GoF Object Structural
Implementation considerations
• Dynamic uses of Bridge should be implemented via Decorator.

• Decorator enables client-specified embellishment of a core object by

recursively wrapping it (possibly more than once) dynamically at runtime.
• Java I/O is a famous example of the Decorator pattern.

See [Link]/2016/11/27/Decorator-Pattern
 Bridge GoF Object Structural
Known uses
• ET++ Window/WindowPort
• libg++ Set/{LinkedList, HashTable}
• ACE Reactor framework

Bridge is used more in C++ than in Java (which uses interfaces & factories).
 Bridge GoF Object Structural
Known uses
• ET++ Window/WindowPort
• libg++ Set/{LinkedList, HashTable}
• ACE Reactor framework
• AWT Component/ComponentPeer

See [Link]/tik-76.278/group6/[Link]
 Bridge GoF Object Structural
Known uses
• ET++ Window/WindowPort
• libg++ Set/{LinkedList, HashTable}
• ACE Reactor framework
• AWT Component/ComponentPeer
• Java Socket/SocketImpl Variations in how Socket is implemented

Socket SocketImpl

SSLSocket CompressionSocket WindowsSocketImpl UNIXSocketImpl

operation() operation()

Variations in what service Socket provides

See [Link]/javase/tutorial/networking/sockets
 Bridge GoF Object Structural
Known uses
• ET++ Window/WindowPort
• libg++ Set/{LinkedList, HashTable}
• ACE Reactor framework Decouples synchronizer interface from
• AWT Component/ComponentPeer its implementation so fair & non-fair
semantics can be supported uniformly
• Java Socket/SocketImpl
• Java synchronizers

ReentrantLock Sync

FairSync NonFairSync

See [Link]/java-concurrent-locks
 Summary of the Bridge Pattern
Bridge decouples the expression tree programming API from its
behavior & implementation to enable transparent extensibility.

ExpressionTree
ComponentNode

Composite
LeafNode
UnaryNode
Instrumented Synchronized
Expression Expression
Tree Tree
CompositeBinary CompositeNegate
Node Node

Composite Composite Composite Composite

AddNode MultiplyNode SubtractNode DivideNode

Bridge Composite

Bridge Composite is an example of a “pattern compound.”

See [Link]/~schmidt/[Link]
Overview of
Pattern Collections

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand the need for pattern
relationships above & beyond
pattern collections.
Douglas C. Schmidt
Overview of
Pattern Collections
 Overview of Pattern Collections
• Stand-alone patterns provide “point solutions” to relatively bounded problems
that arise within specific contexts.
Composite
pattern

Bridge
pattern

See earlier lessons on “The Composite Pattern” & “The Bridge Pattern.”
 Overview of Pattern Collections
• A common way to group multiple
stand-alone patterns together is
the form of a “pattern collection.”

A pattern collection is an
intentionally organized
grouping of patterns

See [Link]/wiki/Design_Patterns.
 Overview of Pattern Collections
• A common way to group multiple
stand-alone patterns together is
the form of a “pattern collection.”
• A collection may be ad hoc or
it may address a given domain,
problem, or level of abstraction.
 Overview of Pattern Collections
• A common way to group multiple
stand-alone patterns together is
the form of a “pattern collection.”
• A collection may be ad hoc or
it may address a given domain,
problem, or level of abstraction.
• A collection’s organization may
be unstructured or structured.
 Overview of Pattern Collections
• The Gang-of-Four, POSA1, & Pattern Languages of Program
Design (PLoPD) books are examples of pattern collections.

The pattern collections in the GoF & POSA1 books are well structured,
where as the pattern collections in the PLoPD books are less structured.

See [Link]/patterns/books
 Overview of Pattern Collections
• In practice, however, stand-alone
“pattern islands” are unusual.
 Overview of Pattern Collections
• In practice, however, stand-alone Extension Publisher-
“pattern islands” are unusual. Interface Domain
Subscriber
Object
• Any substantial software Bridge Active
design inevitably includes Object
Layers
many patterns. Remote
Operation Evictor
Component
Configurator
Thread-
Specific Interceptor
Storage
Adapter
Factory Interpreter
Interpreter Proxy
Method
Adapter
Facade Activator

Monitor Forwarder/ Strategy Leader/Followers

Object Acceptor- Receiver
Connector Reactor
Abstract
Wrapper Facade Component Factory Wrapper Facade
Configurator
Half/Sync-
Broker Half/Async
 Overview of Pattern Collections
• In practice, however, stand-alone Extension Publisher-
“pattern islands” are unusual. Interface Domain
Subscriber
Object
• Any substantial software Bridge Active
design inevitably includes Object
Layers
many patterns. Remote
Operation Evictor
Component
Configurator
Thread-
Specific Interceptor
Storage
Adapter
Factory Interpreter
Interpreter Proxy
Method
Adapter
Facade Activator

Monitor Forwarder/ Strategy Leader/Followers

Object Acceptor- Receiver
Connector Reactor
Abstract
Wrapper Facade Component Factory Wrapper Facade
Configurator
Half/Sync-
Broker Half/Async

Key question: How to best organize all these patterns?

Overview of
Pattern Relationships

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize the common types of
pattern relationships.
 Overview of Pattern Relationships
• Collections of stand-alone patterns have certainly been used with success.
Design problems
• Document structure
• Formatting
• Embellishment
• Multiple look & feels
• Multiple window systems
• User operations
• Spelling checking
& hyphenation
• Etc.

See [Link]/wiki/Design_Patterns
 Overview of Pattern Relationships
• Patterns are social, however, & like to work together.
 Overview of Pattern Relationships
• Patterns commonly form various types of relationships

We’ll briefly summarize these types of relationships here & explore them later
 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements, where:
• One pattern provides the missing
ingredient needed by another

e.g., the Singleton & Double-checked Locking patterns

 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements, where:
• One pattern provides the missing
ingredient needed by another
• One pattern contrasts with
another to provide an
alternative solution to a
related design problem

e.g., the Strategy vs. Template Method patterns

 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements
2. Pattern compounds capture
recurring subcommunities of
patterns that can be treated as
a single distinct pattern that
addresses a design problem

e.g., the Bridge & Composite patterns

 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements
2. Pattern compounds
3. Pattern sequences are an ordered
grouping of patterns applied to create
a particular architecture or design in
response to a specific situation
• Predecessor patterns are joined
with successor patterns to form
part of their context
 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements
2. Pattern compounds
3. Pattern sequences
4. Pattern languages are
networks of interrelated
patterns that define a process
for systematically resolving
development problems in a
particular domain.
 Overview of Pattern Relationships
• Patterns commonly form various types of relationships, e.g.
1. Pattern complements
2. Pattern compounds
3. Pattern sequences
4. Pattern languages are
networks of interrelated
patterns that define a process
for systematically resolving
development problems in a
particular domain.

A pattern sequence represents a particular path through a pattern language.

Douglas C. Schmidt
Summary
 Summary
• Much existing literature on patterns
is organized as pattern collections.
• This provides a good foundation,
but more is needed.
 Summary
• Substantial software designs include Publisher-
Extension
many patterns, which are related Interface Domain
Subscriber

to each other in various ways. Object

Bridge Active
Object
Layers
Remote Component
Operation Evictor Configurator
Thread-
Specific Interceptor
Storage
Adapter
Factory Interpreter
Interpreter Proxy
Method
Adapter
Facade Activator

Monitor Forwarder/ Strategy Leader/Followers

Object Acceptor- Receiver
Connector Reactor
Abstract
Wrapper Facade Component Factory Wrapper Facade
Configurator
Half/Sync-
Broker Half/Async

See [Link]/~schmidt/PDF/[Link].
 Summary
• A key challenge is to organize Publisher-
Extension
these patterns effectively. Interface Domain
Subscriber
Object
Bridge Active
Object
Layers
Remote Component
Operation Evictor Configurator
Thread-
Specific Interceptor
Storage
Adapter
Factory Interpreter
Interpreter Proxy
Method
Adapter
Facade Activator

Monitor Forwarder/ Strategy Leader/Followers

Object Acceptor- Receiver
Connector Reactor
Abstract
Wrapper Facade Component Factory Wrapper Facade
Configurator
Half/Sync-
Broker Half/Async

See [Link]/~schmidt/POSA/POSA4 & [Link]/~schmidt/POSA/POSA5

Overview of Pattern
Complements and
Pattern Compounds

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Know the common types of
pattern relationships:
• Pattern complements
• Pattern compounds

We’ll also summarize various relevant GoF & POSA patterns.

Douglas C. Schmidt
Overview of
Pattern Complements
 Overview of Pattern Complements
• One pattern provides the missing ingredient needed
by another to make a design more complete
& balanced
 Overview of Pattern Complements
• One pattern provides the missing ingredient needed
by another to make a design more complete
& balanced, e.g.,
Disposal
• Disposal Method complements Method
Factory Method by addressing Factory
object destruction & creation. Method

Factory
Method
Disposal
Method
delete object

See [Link]/APF/files/[Link] for more information.

 Overview of Pattern Complements
• One pattern provides the missing ingredient needed
by another to make a design more complete
& balanced, e.g.,
Disposal
• Disposal Method complements Method
Factory Method by addressing Factory
object destruction & creation. Method

Factory
Method
Disposal
Method
delete object

Provide an interface for creating

families of related objects without
specifying their concrete classes

See [Link]/APF/files/[Link] for more information.

 Overview of Pattern Complements
• One pattern provides the missing ingredient needed
by another to make a design more complete
& balanced, e.g.,
Disposal
• Disposal Method complements Method
Factory Method by addressing Factory
object destruction & creation. Method

Factory
Method
Disposal
Method
delete object

Encapsulate concrete details of

object disposal by providing an
explicit method to clean up

See [Link]/APF/files/[Link] for more information.

 Overview of Pattern Complements
• Or, one pattern competes with another
by providing an alternative solution
to a related problem
 Overview of Pattern Complements
• Or, one pattern competes with another
by providing an alternative solution
to a related problem, e.g., Batch
Method
• Batch Method competes with
Iterator by accessing elements Iterator
of aggregates in bulk, thereby
reducing communication costs.

Access elements of an aggregate

without exposing its representation

create_iterator

Iterator

See [Link]/articles/2001/09/24/[Link] for more.

 Overview of Pattern Complements
• Or, one pattern competes with another
by providing an alternative solution
to a related problem, e.g., Batch
Method
• Batch Method competes with
Iterator by accessing elements Iterator
of aggregates in bulk, thereby
reducing communication costs.

Group multiple collection accesses together to reduce cost of

multiple individual accesses in a latency-sensitive context

Batch Method

See [Link]/articles/2001/09/24/[Link] for more.

Douglas C. Schmidt
Overview of
Pattern Compounds
 Overview of Pattern Compounds
• Pattern compounds capture recurring
subcommunities of patterns that can
be treated as a single distinct pattern
to address a design problem

Pattern compounds are common &

identifiable enough to treat them as a single
decision in response to a recurring problem.
 Overview of Pattern Compounds
• Pattern compounds capture recurring
subcommunities of patterns that can
be treated as a single distinct pattern
to address a design problem, e.g., Composite Command
• Composite Command encapsulates
requests as an object.
• Hides differences between a single
request & multiple requests behind a
common interface.
Collection Request …
of Request ORB
Client Parameters
send_multiple_requests_oneway

ORBs often support send_multiple_requests_oneway() operations that initiate many

requests in parallel & don’t wait for requests to finish before returning to the caller.
 Overview of Pattern Compounds
• Pattern compounds capture recurring
subcommunities of patterns that can
be treated as a single distinct pattern
to address a design problem, e.g., Batch
Iterator
(Method)
• Composite Command encapsulates
requests as an object.
• Batch Iterator combines competing
pattern complements to remotely
access elements of aggregates
containing many elements.

list

next_n
next_n
bind
next_one
unbind
destroy
Naming
BindingIterator Context

Naming Services often provide a Batch Iterator (e.g., a BindingIterator) that

enables bulk access of many—but not all—elements in a Naming Context.
Summary of
Pattern Relationships

Douglas C. Schmidt
 Summary
• Pattern complements & pattern compounds are initial steps towards moving
away from patterns as distinct islands of design to parts of an interwoven
whole.
 Summary
• Pattern complements & pattern compounds are initial steps towards moving
away from patterns as distinct islands of design to parts of an interwoven
whole.
• A pattern complement completes the design of another pattern.

Factory
Method
 Summary
• Pattern complements & pattern compounds are initial steps towards moving
away from patterns as distinct islands of design to parts of an interwoven
whole.
• A pattern complement completes the design of another pattern.
• A pattern compound names a commonly recurring, cohesive combination
of other patterns.
 Summary
• Pattern complements & pattern compounds are initial steps towards moving
away from patterns as distinct islands of design to parts of an interwoven
whole.
• A pattern complement completes the design of another pattern.
• A pattern compound names a commonly recurring, cohesive combination
of other patterns.
• The POSA5 book provides in-depth discussion
of the key concepts that underlie pattern
complements & pattern compounds.

See [Link]/~schmidt/POSA/POSA5
The Command Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Command pattern can be
applied to perform user-requested commands
ET_Command
UserCommand
ET_Command
consistently & extensibly in the expression
_Factory execute()
tree processing app.
ET_Command ET_CommandImpl
_FactoryImpl Expr
Format Command
Command Expr_
Format_ Command
Command Eval
Macro Command
Command Eval_
Macro_ Command
Command
Quit
Print Command
Quit_
Command
Print_ Command
Command
Douglas C. Schmidt
Motivating the Need for
the Command Pattern in
the Expression Tree App
 A Pattern for Objectifying User Requests
Purpose: Define objectified actions that enable users to perform command
requests consistently & extensibly in the expression tree processing app.
InputHandler

<< creates >>

*
UserCommand
Command

Format Expr
Command Command

Print Eval
Command Command

Macro Quit
Command Command

Command provides a uniform means to process all user-requested commands.

 Context: OO Expression Tree Processing App
• Verbose mode supports
user command execution

Verbose mode
 Context: OO Expression Tree Processing App
• Succinct mode supports
macro commands

Succinct mode
Problem: Scattered/Fixed User Request Implementations
• It’s hard to maintain implementations of user-requested commands that are
scattered throughout the source code.
Problem: Scattered/Fixed User Request Implementations
• Hard-coding the program to handle only a fixed set of user commands
impedes the evolution that’s needed to support new requirements.

Operation
format
expr
set
print
eval
quit
 Solution: Encapsulate User Requests as Commands
• Create a hierarchy of UserCommand
UserCommand
subclasses
execute()

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Solution: Encapsulate User Requests as Commands
• Create a hierarchy of UserCommand
UserCommand
subclasses, each containing:
execute()
• A command method (execute())

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Solution: Encapsulate User Requests as Commands
• Create a hierarchy of UserCommand
UserCommand
subclasses, each containing:
execute()
• A command method (execute())
• The state needed by the command
Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Solution: Encapsulate User Requests as Commands
• A Command object may:
• Implement the command
Command
itself
performAction()
 Solution: Encapsulate User Requests as Commands
• A Command object may:
• Implement the operation
Command
itself
• Or forward the command’s performAction()
implementation to other
object(s)

Command

[Link]()

The expression tree processing app applies this variant of the Command pattern
 UserCommand Class Overview
• Defines an abstract super class that performs a user-requested command
on an expression tree when it’s executed

Class methods

void execute()
void printValidCommands()
 UserCommand Class Overview
• Defines an abstract super class that performs a user-requested command
on an expression tree when it’s executed

Class methods These methods are

defined by subclasses
void execute()
void printValidCommands()
 UserCommand Class Overview
• Defines an abstract super class that performs a user-requested command
on an expression tree when it’s executed

Class methods

void execute()
void printValidCommands()

• Commonality: provides a common API for expression tree commands

• Variability: subclasses of UserCommand can vary depending on the
commands requested by user input
The Command Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Command pattern can be applied to perform user-
requested commands consistently & extensibly in the expression tree
processing app.
• Understand the structure & functionality of the Command pattern.
Douglas C. Schmidt
Structure & Functionality
of the Command Pattern
 Command GoF Object Behavioral
Intent
• Encapsulate the request for a service UserCommand
as an object execute()

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command

See [Link]/wiki/Command_pattern
 Command GoF Object Behavioral
Applicability
• Want to parameterize objects with an UserCommand
action to perform execute()

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Command GoF Object Behavioral
Applicability
• Want to parameterize objects with an UserCommand
action to perform execute()
• Want to specify, queue, & execute
requests at different times
Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Command GoF Object Behavioral
Applicability
• Want to parameterize objects with an UserCommand
action to perform execute()
• Want to specify, queue, & execute
requests at different times
We need to add Expr
• Want to support multilevel an unexecute() Command
Format
undo/redo method here.
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Command GoF Object Behavioral
Structure & participants

ConcreteCommand
 Command GoF Object Behavioral
Structure & participants
InputHandler

ConcreteCommand

See upcoming lesson on the Template Method pattern

 Command GoF Object Behavioral
Structure & participants
UserCommand

ConcreteCommand
 Command GoF Object Behavioral
Structure & participants

FormatCommand,
ExprCommand,
PrintCommand,
EvalCommand,
MacroCommand,
QuitCommand, etc.

ConcreteCommand
 Command GoF Object Behavioral
Structure & participants

TreeContext

ConcreteCommand

See upcoming lesson on the State pattern

 Command GoF Object Behavioral
Structure & participants

The UI

ConcreteCommand
 Command GoF Object Behavioral
Structure & participants

ConcreteCommand

The Client & Invoker objects may be the same or different.

The Command Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Command pattern can be applied to perform user-
requested commands consistently & extensibly in the expression tree
processing app.
• Understand the structure & functionality of the Command pattern.
• Know how to implement the Command pattern in Java.
Douglas C. Schmidt
Implementing the Command
Pattern in Java
 Command GoF Object Behavioral
Command example in Java public abstract class UserCommand {
protected TreeContext mTreeContext;
• Plays role of “Command” in
the Command pattern
• Defines an API for “Concrete
Command” implementations UserCommand(TreeContext
that perform an operation treeContext) {
on the expression tree when mTreeContext = treeContext;
it's executed }

public abstract void execute();

See ExpressionTree/CommandLine/src/expressiontree/commands
 Command GoF Object Behavioral
Command example in Java public abstract class UserCommand {
protected TreeContext mTreeContext;
• Plays role of “Command” in
the Command pattern Holds the expression tree
• Defines an API for “Concrete that’s the target of commands
Command” implementations UserCommand(TreeContext
that perform an operation treeContext) {
on the expression tree when mTreeContext = treeContext;
it's executed }

public abstract void execute();

See upcoming lesson on the State pattern

 Command GoF Object Behavioral
Command example in Java public abstract class UserCommand {
protected TreeContext mTreeContext;
• Plays role of “Command” in
the Command pattern
• Defines an API for “Concrete Constructor sets the field
Command” implementations UserCommand(TreeContext
that perform an operation treeContext) {
on the expression tree when mTreeContext = treeContext;
it's executed }

public abstract void execute();

 Command GoF Object Behavioral
Command example in Java public abstract class UserCommand {
protected TreeContext mTreeContext;
• Plays role of “Command” in
the Command pattern
• Defines an API for “Concrete
Command” implementations UserCommand(TreeContext
that perform an operation treeContext) {
on the expression tree when mTreeContext = treeContext;
it's executed }

public abstract void execute();

Concrete implementations run

the command via this method
 Command GoF Object Behavioral
Command example in Java public class ExprCommand
extends UserCommand {
• Encapsulate the execution of a
private String mExpr;
command object that sets
the desired input expression.
• e.g., “−5×(3+4)”
ExprCommand(TreeContext context,
String newexpr) {
super(context);
mExpr = newexpr;
}

public void execute() {

[Link](mExpr);
}
 Command GoF Object Behavioral
Command example in Java public class ExprCommand
extends UserCommand {
• Encapsulate the execution of a
private String mExpr;
command object that sets
the desired input expression. Store the requested
• e.g., “−5×(3+4)” expression

ExprCommand(TreeContext context,
String newexpr) {
super(context);
mExpr = newexpr;
}

public void execute() {

[Link](mExpr);
}
 Command GoF Object Behavioral
Command example in Java public class ExprCommand
extends UserCommand {
• Encapsulate the execution of a
private String mExpr;
command object that sets
the desired input expression.
• e.g., “−5×(3+4)”
ExprCommand(TreeContext context,
String newexpr) {
super(context);
mExpr = newexpr;
}
Provide appropriate TreeContext
& requested expression

public void execute() {

[Link](mExpr);
}
 Command GoF Object Behavioral
Command example in Java public class ExprCommand
extends UserCommand {
• Encapsulate the execution of a
private String mExpr;
command object that sets
the desired input expression.
• e.g., “−5×(3+4)”
ExprCommand(TreeContext context,
String newexpr) {
super(context);
mExpr = newexpr;
}

public void execute() {

[Link](mExpr);
}
Forward to TreeContext to create
the desired expression tree

See upcoming lesson on the State pattern

 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”
• e.g., “−5×(3+4)”
UserCommand

execute()

execute()

formatCommand().execute(); for all c in commands

[Link]()
exprCommand().execute();
evalCommand().execute();

See ExpressionTree/CommandLine/src/expressiontree/commands
 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”

public class MacroCommand extends UserCommand {

...
private List<UserCommand> mMacroCommand;

MacroCommand(TreeContext context,
List<UserCommand> macroCommand) {
super(context); mMacroCommand = macroCommand;
}

public void execute() throws Exception {

for (UserCommand command : mMacroCommand)
[Link]();
}
...
 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”

public class MacroCommand extends UserCommand {

...
private List<UserCommand> mMacroCommand;

List of commands to execute as a macro

MacroCommand(TreeContext context,
List<UserCommand> macroCommand) {
super(context); mMacroCommand = macroCommand;
}

public void execute() throws Exception {

for (UserCommand command : mMacroCommand)
[Link]();
}
...
 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”

public class MacroCommand extends UserCommand {

...
private List<UserCommand> mMacroCommand;

Constructor initializes the field

MacroCommand(TreeContext context,
List<UserCommand> macroCommand) {
super(context); mMacroCommand = macroCommand;
}

public void execute() throws Exception {

for (UserCommand command : mMacroCommand)
[Link]();
}
...
 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”

public class MacroCommand extends UserCommand {

...
private List<UserCommand> mMacroCommand;

MacroCommand(TreeContext context,
List<UserCommand> macroCommand) {
super(context); mMacroCommand = macroCommand;
}

public void execute() throws Exception {

for (UserCommand command : mMacroCommand)
[Link]();
} Java for-each loop runs a sequence of
... commands to implement the “succinct
mode”
 Command GoF Object Behavioral
Command example in Java
• Encapsulate the execution of a sequence of commands as an object, which is
used to implement the “succinct mode.”

public class MacroCommand extends UserCommand {

...
private List<UserCommand> mMacroCommand;

MacroCommand(TreeContext context,
List<UserCommand> macroCommand) {
super(context); mMacroCommand = macroCommand;
}

public void execute() throws Exception {

[Link](UserCommand::execute);
}
... The functional way of executing a sequence of
commands to implement the “succinct mode”

See [Link]/Command-Pattern-Using-Java-8-Lambda
The Command Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Command pattern can be applied to perform user-
requested commands consistently & extensibly in the expression tree
processing app.
• Understand the structure & functionality of the Command pattern.
• Know how to implement the Command pattern in Java.
• Be aware of other considerations when applying the Command pattern.
Douglas C. Schmidt
Other Considerations of
the Command Pattern
 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a
service
• Makes programs more
modular & flexible
 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a
service
ConcreteCommand
• Makes programs more
modular & flexible, e.g.,
performAction()
• Can bundle state &
behavior into an object
 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a
service
ConcreteCommand
• Makes programs more
modular & flexible, e.g.,
performAction()
• Can bundle state &
behavior into an object
• Can forward behavior
to other objects ConcreteCommand

[Link]()

See upcoming lesson on the State pattern for an example of forwarding.

 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a UserCommand
service execute()

• Makes programs more

modular & flexible, e.g.,
Expr
• Can bundle state & Format Command
behavior into an object Command

• Can forward behavior Eval

Macro
to other objects Command
Command

• Can extend behavior

via subclassing Quit
Print Command
Command
 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a void handleInput() {
service ...
UserCommand command =
• Makes programs more makeUserCommand(input);
modular & flexible, e.g.,
• Can bundle state &
behavior into an object
• Can forward behavior executeCommand(command);
to other objects
• Can extend behavior
via subclassing
• Can pass a command
object as a parameter

The handleInput() method in InputHandler plays the role of “invoker.”

 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a void handleInput() {
service ...
UserCommand command =
• Makes programs more makeUserCommand(input);
modular & flexible, e.g.,
Call a hook (factory) method to
• Can bundle state & make a command based on user
behavior into an object input

• Can forward behavior executeCommand(command);

to other objects
• Can extend behavior
via subclassing
• Can pass a command
object as a parameter

See the next lesson on “The Factory Method Pattern” for UserCommandFactory.
 Command GoF Object Behavioral
Consequences
+ Abstracts the executor of a void handleInput() {
service ...
UserCommand command =
• Makes programs more makeUserCommand(input);
modular & flexible, e.g.,
• Can bundle state &
behavior into an object
• Can forward behavior executeCommand(command);
to other objects
• Can extend behavior Call a hook method & pass
a command to execute
via subclassing
• Can pass a command
object as a parameter

See upcoming lesson on “The Template Method Pattern”

 Command GoF Object Behavioral
Consequences
+ Composition yields
macro commands
UserCommand

execute()

execute()

for all c in commands

[Link]()
 Command GoF Object Behavioral
Consequences
+ Supports arbitrary-level
undo-redo Undo: Redo:
unexecute() execute()

Case study doesn’t use unexecute(), but it’s a common Command feature.
 Command GoF Object Behavioral
Consequences
UserCommand
– Might result in lots of trivial
execute()
command subclasses

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command

Java lambda expressions

can minimize subclassing!

See [Link]/2014/12/[Link]
 Command GoF Object Behavioral
Consequences
– Excessive memory may
be needed to support Undo: Redo:
undo/redo operations unexecute() execute()
 Command GoF Object Behavioral
Implementation considerations
• Copying a command before
putting it on a history list Undo: Redo:
unexecute() execute()
 Command GoF Object Behavioral
Implementation considerations
• Avoiding error accumulation
during undo/redo Undo: Redo:
unexecute() execute()
 Command GoF Object Behavioral
Implementation considerations
• Supporting transactions
Undo: Redo:
unexecute() execute()
 Command GoF Object Behavioral
Known uses
• InterViews Actions
• MacApp, Unidraw
Commands
• JDK’s UndoableEdit,
AccessibleAction
• GNU Emacs
• Microsoft Office tools
• Java Runnable interface

See [Link]/javase/8/docs/api/java/lang/[Link]
 Command GoF Object Behavioral
Known uses
• InterViews Actions
• MacApp, Unidraw
Commands
• JDK’s UndoableEdit,
AccessibleAction
• GNU Emacs
• Microsoft Office tools
• Java Runnable interface
• Runnable can also be used to implement the Command Processor pattern

Packages a piece of application functionality—as well as its

parameterization in an object—to make it usable in another context

See [Link]/~schmidt/[Link]
 Summary of the Command Pattern
• Command ensures users interact with the expression tree processing app in a
consistent & extensible manner.

InputHandler

<< creates >>

*
UserCommand
Command

Format Expr
Command Command

Print Eval
Command Command

Macro Quit
Command Command

Command provides a uniform means to process all user-requested operations.

The Factory Method Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Factory Method pattern can
be applied to extensibly create variabilities in UserCommandFactory

the expression tree processing app. makeUserCommand()

<<creates>>
UserCommand
execute()

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
Douglas C. Schmidt
Motivating the Need for
the Factory Method Pattern in the
Expression Tree App
 A Pattern for Abstracting Object Creation
Purpose: Enable the extensible creation of variabilities,
such as commands, iterators, & visitors.
Factory Method

InputHandler UserCommandFactory TreeContext

<<creates>>

* UserCommand
Command

1
MacroCommand PrintCommand SetCommand QuitCommand NullCommand

FormatCommand ExprCommand EvalCommand

Factory Method decouples the creation of objects from their subsequent use.
 Context: OO Expression Tree Processing App
• There are many points of variability in Visitor
the expression tree processing app.
• e.g., user commands, traversal
strategies, & visitor operations EvaluationVisitor PrintVisitor

applied on an expression tree

Java Iterator
*
UserCommand

LevelOrder
Iterator
Format Expr
Command Command InOrder
Iterator

Print Eval PostOrder

Command Command Iterator

PreOrder
Macro Quit Iterator
Command Command
 Context: OO Expression Tree Processing App
• There are many points of variability in Visitor
the expression tree processing app.
• e.g., user commands, traversal
strategies, & visitor operations EvaluationVisitor PrintVisitor ...
applied on an expression tree

Java Iterator
*
UserCommand

LevelOrder
Iterator
Format Expr
Command Command InOrder
Iterator

Print Eval PostOrder

Command Command Iterator
...
PreOrder
Macro Quit Iterator
Command Command ...d

Adding new variants should

not affect existing client code.
 Problem: Inflexible Creation of Variabilities
• Tightly coupling the creation of variabilities with client code is problematic.
• e.g., hard-coding lexical dependencies on specific
subclasses can complicate maintenance
& impede extensibility

UserCommand command =
new PrintCommand();

Visitor visitor =
new EvaluationVisitor();

Iterator<ExpressionTree> it =
new PreOrderIterator();
 Solution: Abstract Creation of Objects
• Define a UserCommandFactory class whose makeUserCommand()
factory method creates a UserCommand object.

UserCommandFactory
<<creates>>
User
makeUserCommand()
Command
 Solution: Abstract Creation of Objects
• Have the makeUserCommand() factory method implement the appropriate
subclass of UserCommand

UserCommandFactory
<<creates>>
User
makeUserCommand() Command
 Solution: Abstract Creation of Objects
• Have the makeUserCommand() factory method implement the appropriate
subclass of UserCommand, e.g.,
UserCommandFactory & override the factory method
• Subclass
makeUserCommand()
UserCommandFactory
<<creates>>
makeUserCommand()
User
Command

PrintCommandFactory Print
<<creates>> Command
makeUserCommand()
 Solution: Abstract Creation of Objects
• Have the makeUserCommand() factory method implement the appropriate
subclass of UserCommand, e.g.,
UserCommandFactory & override the factory method
• Subclass
makeUserCommand()
UserCommandFactory
<<creates>>
makeUserCommand(Param)
User
* Command

1
MacroCommand PrintCommand SetCommand QuitCommand NullCommand

FormatCommand ExprCommand EvalCommand

• Or pass a parameter to the makeUserCommand() factory method

& use it to create the appropriate UserCommand subclass objects
 UserCommandFactory Class Overview
• Create the command corresponding to the user input.

Class methods

UserCommand makeUserCommand(String inputString)

...
 UserCommandFactory Class Overview
• Create the command corresponding to the user input.

Class methods

UserCommand makeUserCommand(String inputString)

...
This is a factory method
 UserCommandFactory Class Overview
• Create the command corresponding to the user input.

Class methods

UserCommand makeUserCommand(String inputString)

...

• Commonality: provides a common interface to create commands

• Variability: implementations of expression tree command factory
methods can vary depending on the requested commands
 UserCommandFactory Class Overview
• Create the command corresponding to the user input.

UserCommand Each factory command object implements

FactoryCommand UserCommandFactoryCommand & creates
execute() a different type of concrete UserCommand.

HashMap<String, UserCommand
UserCommandFactoryCommand>
Command Factory
Name Command
"expr" execute() Expr
Format Command
"format" execute()
Command
"eval" execute() Eval
Macro Command
"macro" execute()
Command
"quit" execute() Quit
Print Command
"print" execute()
Command
 UserCommandFactory Class Overview
• Create the command corresponding to the user input.

We could also use the Java

Function<String, UserCommand>
Function functional interface!
apply()

HashMap<String, UserCommand
Function<String, UserCommand>>
Command Factory
Name Command
"expr" apply() Expr
Format Command
"format" apply()
Command
"eval" apply() Eval
Macro Command
"macro" apply()
Command
"quit" apply() Quit
Print Command
"print" apply()
Command

See [Link]/javase/8/docs/api/java/util/function/[Link]
The Factory Method Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Factory Method pattern can be applied to extensibly
create variabilities in the expression tree processing app.
• Understand the structure & functionality of the Factory Method pattern.
Douglas C. Schmidt
Structure & Functionality of the
Factory Method Pattern
 Factory Method GoF Class Creational
Intent UserCommandFactory
• Provide an API for creating an makeUserCommand()
object, but leave the choice of
the object’s concrete type to
its subclass(es) UserCommand
execute()

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>

See [Link]/wiki/Factory_method_pattern
 Factory Method GoF Class Creational
Applicability UserCommandFactory
• When a class cannot anticipate makeUserCommand()
the objects it must create.

UserCommand
execute()

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>
 Factory Method GoF Class Creational
Applicability UserCommandFactory
• When a class cannot anticipate makeUserCommand()
the objects it must create.
• A class wants its subclasses to
specify the objects it creates. UserCommand
execute()

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>
 Factory Method GoF Class Creational
Applicability UserCommandFactory
• When a class cannot anticipate makeUserCommand()
the objects it must create.
• A class wants its subclasses to
specify the objects it creates. UserCommand
execute()
• This approach is optional.

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>
 Factory Method GoF Class Creational
Applicability UserCommandFactory
• When a class cannot anticipate makeUserCommand(Param) <<creates>>
the objects it must create.
• A class wants its subclasses to
specify the objects it creates. UserCommand
execute()
• This approach is optional.
• An alternative involves
passing a parameter to
the factory method.
Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Factory Method GoF Class Creational
Applicability UserCommandFactory
• When a class cannot anticipate makeUserCommand(Param) <<creates>>
the objects it must create.
• A class wants its subclasses to
specify the objects it creates. UserCommand
execute()
• Or there’s a need to decouple
object creation from its
subsequent use.

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command

This decoupling is really the essence of the Factory Method pattern!

 Factory Method GoF Class Creational
Structure & participants
 Factory Method GoF Class Creational
Structure & participants

UserCommand
 Factory Method GoF Class Creational
Structure & participants

UserCommandFactory
 Factory Method GoF Class Creational
Structure & participants

EvalCommand, Print
Command, MacroCommand, etc.
 Factory Method GoF Class Creational
Structure & participants

Unused

Our app passes a string to the factory method rather than using subclassing.
The Factory Method Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Factory Method pattern can be applied to extensibly
create variabilities in the expression tree processing app.
• Understand the structure & functionality of the Factory Method pattern.
• Know how to implement the Factory Method pattern in Java.
Douglas C. Schmidt
Implementing the Factory Method
Pattern in Java
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

private interface UserCommandFactoryCommand

{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();

UserCommandFactory(final TreeContext treeOps) {

[Link]("format", new UserCommandFactoryCommand(){
public UserCommand execute(String param)
{ return new FormatCommand(treeOps, param); }
});
...

See ExpressionTree/CommandLine/src/expressiontree/commands
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory { We first apply Command to
initialize UserCommandFactory.
private interface UserCommandFactoryCommand
{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();

UserCommandFactory(final TreeContext treeOps) {

[Link]("format", new UserCommandFactoryCommand(){
public UserCommand execute(String param)
{ return new FormatCommand(treeOps, param); }
});
...
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory { Command interface
private interface UserCommandFactoryCommand
{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();

UserCommandFactory(final TreeContext treeOps) {

[Link]("format", new UserCommandFactoryCommand(){
public UserCommand execute(String param)
{ return new FormatCommand(treeOps, param); }
});
...

UserCommandFactoryCommand is a Java “functional interface”

 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

private interface UserCommandFactoryCommand

{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();
Map strings to factory commands that create UserCommand objects

UserCommandFactory(final TreeContext treeOps) {

[Link]("format", new UserCommandFactoryCommand(){
public UserCommand execute(String param)
{ return new FormatCommand(treeOps, param); }
});
...
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

private interface UserCommandFactoryCommand

{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();
An anonymous inner class defines a factory
command that creates a FormatCommand.
UserCommandFactory(final TreeContext treeOps) {
[Link]("format", new UserCommandFactoryCommand(){
public UserCommand execute(String param)
{ return new FormatCommand(treeOps, param); }
});
...

We apply the Command pattern to define a factory method that creates a command!
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

private interface UserCommandFactoryCommand

{ UserCommand execute(String param); }

private HashMap<String,UserCommandFactoryCommand> mCommandMap =

new HashMap<>();

UserCommandFactory(final TreeContext treeOps) {

[Link]("format", param ->
new FormatCommand(treeOps, param));

... Java lambda that creates a FormatCommand

Java lambda expressions are more concise than anonymous inner classes!
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {
The factory method
public UserCommand makeUserCommand (String inputString) {
String commandRequest = ... /* get command from inputString */
String parameters = ... /* get parameters from inputString */

UserCommandFactoryCommand command =
[Link](commandRequest);

if (command != null)
return [Link](parameters);
else
return new QuitCommand(mTreeContext);
...

The factory method uses a map to find/execute the command that makes a command.
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

public UserCommand makeUserCommand (String inputString) {

String commandRequest = ... /* get command from inputString */
String parameters = ... /* get parameters from inputString */

Parse inputString to get command & params

UserCommandFactoryCommand command =
[Link](commandRequest);

if (command != null)
return [Link](parameters);
else
return new QuitCommand(mTreeContext);
...
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

public UserCommand makeUserCommand (String inputString) {

String commandRequest = ... /* get command from inputString */
String parameters = ... /* get parameters from inputString */

Try to find a pre-allocated factory command

UserCommandFactoryCommand command =
[Link](commandRequest);

if (command != null)
return [Link](parameters);
else
return new QuitCommand(mTreeContext);
...
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

public UserCommand makeUserCommand (String inputString) {

String commandRequest = ... /* get command from inputString */
String parameters = ... /* get parameters from inputString */

UserCommandFactoryCommand command =
[Link](commandRequest);
If found, execute it to make a command
if (command != null)
return [Link](parameters);
else
return new QuitCommand(mTreeContext);
...
 Factory Method GoF Class Creational
Factory Method example in Java
• UserCommandFactory creates UserCommands based on user input.
public class UserCommandFactory {

public UserCommand makeUserCommand (String inputString) {

String commandRequest = ... /* get command from inputString */
String parameters = ... /* get parameters from inputString */

UserCommandFactoryCommand command =
[Link](commandRequest);

if (command != null)
return [Link](parameters);
else
return new QuitCommand(mTreeContext);
...
Otherwise, user gave an
unsupported request, so quit
The Factory Method Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Factory Method pattern can be applied to extensibly
create variabilities in the expression tree processing app.
• Understand the structure & functionality of the Factory Method pattern.
• Know how to implement the Factory Method pattern in Java.
• Be aware of other considerations when applying the Factory Method pattern.
Douglas C. Schmidt
Other Considerations of the
Factory Method Pattern
 Factory Method GoF Class Creational
Consequences
+ Decoupling
• Clients are more flexible Instead of:
since they needn’t specify the
class name of the concrete UserCommand command =
class & the details of its new PrintCommand();
creation.

Use:
UserCommand command
= userCommandfactory.
makeUserCommand
("print"));
where userCommandFactory is an
instance of UserCommandFactory
 Factory Method GoF Class Creational
Consequences
Hard-codes a lexical
+ Decoupling dependency on
• Clients are more flexible PrintCommand
Instead of:
since they needn’t specify the
class name of the concrete UserCommand command =
class & the details of its new PrintCommand();
creation.

Use:
UserCommand command
= userCommandfactory.
makeUserCommand
("print");
where userCommandFactory is an
instance of UserCommandFactory
 Factory Method GoF Class Creational
Consequences
+ Decoupling
• Clients are more flexible Instead of:
since they needn’t specify the
class name of the concrete UserCommand command =
class & the details of its new PrintCommand();
creation.
No lexical dependency
Use: on any concrete class
UserCommand command
= userCommandfactory.
makeUserCommand
("print");
where userCommandFactory is an
instance of UserCommandFactory
 Factory Method GoF Class Creational
Consequences UserCommandFactory
− More classes makeUserCommand()
• Construction of objects may
require additional class(es).
UserCommand
execute()

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>
 Factory Method GoF Class Creational
Consequences UserCommandFactory
− More classes makeUserCommand(Param) <<creates>>
• Construction of objects may
require additional class(es).
UserCommand
• An alternative is to pass execute()
a param to the Creator
super class factory method.

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Factory Method GoF Class Creational
Implementation Considerations UserCommandFactory
• Must vs. may subclass makeUserCommand()
• The creator class is abstract, i.e.,
• It doesn’t implement factory UserCommand
methods & must be subclassed. execute()

…
FormatCommandFactory
Expr
makeUserCommand() Format Command
<<creates>>
Command

MacroCommandFactory Eval
Macro Command
makeUserCommand() Command
<<creates>>

PrintCommandFactory Quit
Print Command
makeUserCommand() Command
<<creates>>
 Factory Method GoF Class Creational
Implementation Considerations UserCommandFactory
• Must vs. may subclass makeUserCommand() <<creates>>
• The creator class is abstract.
• The creator class is concrete, i.e., UserCommand
• It provides a default factory execute()
method & may be subclassed.

…
Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Factory Method GoF Class Creational
Implementation Considerations UserCommandFactory
• Factory method creates variants makeUserCommand(Param) <<creates>>
• Pass a parameter to designate
the variant.
UserCommand
execute()

Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command
 Factory Method GoF Class Creational
Implementation Considerations UserCommandFactory
• Factory method creates variants makeUserCommand(Param) <<creates>>
• Pass a parameter to designate
the variant.
UserCommand
execute()

A Java string or enum

parameter indicates which
command the user wants.
Expr
Format Command
Command

Eval
Macro Command
Command

Quit
Print Command
Command

A string is more flexible, whereas an enum is more type-safe.

 Factory Method GoF Class Creational
Implementation Considerations
• Constructor references in modern Java may reduce the tedium of creating
Product subclasses
class ShapeFactory {
private Map<String, Supplier<Shape>> map =
new HashMap<>() {{
put("CIRCLE", Circle::new);
put("RECTANGLE", Rectangle::new);
...
}};

public Shape getShape(String shape) {

Supplier<Shape> shape = [Link]([Link]());
if (shape != null)
return [Link]();
throw new IllegalArgumentException
("No such shape " + [Link]());
}
}
}

See [Link]/articles/factory-pattern-using-lambda-expression-in-java-8
 Factory Method GoF Class Creational
Implementation Considerations
• Constructor references in modern Java may reduce the tedium of creating
Product subclasses
class ShapeFactory {
private Map<String, Supplier<Shape>> map =
new HashMap<>() {{
put("CIRCLE", Circle::new);
put("RECTANGLE", Rectangle::new);
...
}}; Constructor references can be used to create desired shapes.

public Shape getShape(String shape) {

Supplier<Shape> shape = [Link]([Link]());
if (shape != null)
return [Link]();
throw new IllegalArgumentException
("No such shape " + [Link]());
}
}
}

See [Link]/java-8/constructor-references-java-8-simplified-tutorial
 Factory Method GoF Class Creational
Implementation Considerations
• Constructor references in modern Java may reduce the tedium of creating
Product subclasses
class ShapeFactory {
private Map<String, Supplier<Shape>> map =
new HashMap<>() {{
put("CIRCLE", Circle::new);
put("RECTANGLE", Rectangle::new);
...
}};

public Shape getShape(String shape) {

Supplier<Shape> shape = [Link]([Link]());
if (shape != null)
return [Link](); Get & create the requested Shape subclass
throw new IllegalArgumentException
("No such shape " + [Link]());
}
}
}
 Factory Method GoF Class Creational
Implementation Considerations
• Constructor references in modern Java may reduce the tedium of creating
Product subclasses
class ShapeFactory {
private Map<String, Supplier<Shape>> map =
new HashMap<>() {{
put("CIRCLE", Circle::new);
put("RECTANGLE", Rectangle::new);
...
}};

public Shape getShape(String shape) {

Supplier<Shape> shape = [Link]([Link]());
if (shape != null)
return [Link]();
throw new IllegalArgumentException
("No such shape " + [Link]());
}
} Doesn’t scale if getShape() takes multiple
} arguments to pass to Shape constructors
 Factory Method GoF Class Creational
Implementation Considerations
• Apply Abstract Factory if many semantically-consistent factory methods needed

Create families of related

objects without specifying
subclass names

See [Link]/wiki/Abstract_factory_pattern
 Factory Method GoF Class Creational
Known uses
• InterViews Kits
• ET++ WindowSystem
• AWT Toolkit
• BREW feature phone frameworks
• The ACE ORB (TAO)
• iterator() factory method in
the Java Collection interface

See [Link]/javase/8/docs/api/java/util/[Link]#iterator
 Summary of the Factory Method Pattern
• Factory Method enables extensible creation of variabilities, such as iterators,
commands, & visitors.
Factory Method

InputHandler UserCommandFactory TreeContext

<<creates>>

* UserCommand
Command

1
MacroCommand PrintCommand SetCommand QuitCommand NullCommand

FormatCommand ExprCommand EvalCommand

Factory Method decouples the creation of objects from their subsequent use.
The Iterator Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Iterator pattern can
be applied to access all nodes in an
expression tree flexibly & extensibly.

ExpressionTree exprTree = ...;

for(Iterator<ExpressionTree> it =
[Link]();
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}
Douglas C. Schmidt
Motivating the Need for
the Iterator Pattern in
the Expression Tree App
A Pattern for Transparently Traversing Aggregates
Purpose: Create objects that traverse the Composite-based
expression tree & access each of its elements one at a time.

Bridge
ExpressionTree ComponentNode

<< create >>

Composite LeafNode
UnaryNode

Java Iterator
Composite
BinaryNode …

Iterator Composite

Iterator decouples expression tree traversal from its internal structure.

 Context: OO Expression Tree Processing App
• Several user command requests require
accessing all nodes in an expression tree.

Operation Behavior
format Allows the user to select the format of the input expression
expr Allows the user to designate the current input expression
set Sets a variable that can be used in an expression
print Print the current input expression using the designated
traversal order
eval Evaluate the value of the current input expression
quit Exit the program
 Problem: Inflexible Expression Tree Traversal
• Hard-coding the traversal logic into the expression tree itself is inflexible

public class ExpressionTree {

public expressionTree
(ComponentNode root) {
[Link] = root;
}
…

public void traverse

(NodeVisitor nv);
…
}
 Problem: Inflexible Expression Tree Traversal
• Hard-coding the traversal logic into the expression tree itself is inflexible, e.g.,
• Only one internal traversal is allowed
at a time
public class ExpressionTree {
public expressionTree
(ComponentNode root) {
[Link] = root;
}
…

public void traverse

(NodeVisitor nv);
…
}
 Problem: Inflexible Expression Tree Traversal
• Hard-coding the traversal logic into the expression tree itself is inflexible, e.g.,
• Only one internal traversal is allowed
at a time
• Hard to control where/when public class ExpressionTree {
to stop the traversal public expressionTree
(ComponentNode root) {
[Link] = root;
}
…

public void traverse

(NodeVisitor nv);
…
}
 Problem: Inflexible Expression Tree Traversal
• Having a client explicitly traverse an expression tree via its internal links
impedes extensibility.

public void preOrderTraversal

(ExpressionTree root) {
if (![Link]()) {
// Do something with root node
...

// traverse left branch

preOrderTraversal([Link] ());

// traverse right branch

preOrderTraversal([Link] ())
This code breaks if we }
enhance ExpressionTree
to support ternary nodes.
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5-5+34
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5 ~ 5+34

The ‘~’ is used for post-order negate since ‘–’ is ambiguous!

 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5 ~ 3
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5 ~ 3 4
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5 ~ 3 4 +
 Solution: Encapsulate Traversal as an Object
• Create an iterator object that encapsulates
the traversal of an expression tree without
requiring clients to know how the tree is
structured internally.

“Post-order” traversal =
5 ~ 3 4 +×
 Solution: Encapsulate Traversal as an Object
• Define methods to:
1. Create an iterator (via factory method)

ExpressionTree exprTree = ...;

for(Iterator<ExpressionTree> it = [Link]();
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}

See [Link]/wiki/Factory_method_pattern
 Solution: Encapsulate Traversal as an Object
• Define methods to:
1. Create an iterator (via factory method)
2. Check to see if it’s finished

ExpressionTree exprTree = ...;

for(Iterator<ExpressionTree> it = [Link]();
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}
 Solution: Encapsulate Traversal as an Object
• Define methods to:
1. Create an iterator (via factory method)
2. Check to see if it’s finished
3. Access & process each element
if it’s not finished

ExpressionTree exprTree = ...;

for(Iterator<ExpressionTree> it = [Link]();
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}
 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods

boolean hasNext()
E next()
void remove()
default void forEachRemaining()

[Link]/javase/8/docs/api/java/util/[Link] has more information.

 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods

Returns true if
iterator has boolean hasNext()
more elements E next()
void remove()
default void forEachRemaining()
 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods Returns the next

element in the iterator

boolean hasNext()
E next()
void remove()
default void forEachRemaining()
 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods

Removes last element returned

boolean hasNext() from collection by iterator
E next()
void remove()
default void forEachRemaining()
 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods

boolean hasNext()
E next()
void remove()
default void forEachRemaining()
Performs the given action
for each remaining element
 Java Iterator Interface Overview
• Defines a generic interface for traversing an aggregate data structure

Interface methods

boolean hasNext()
E next()
void remove()
default void forEachRemaining()

• Commonality: provides a common interface for expression tree

iterators that conform to the Java Iterator interface
• Variability: can be configured with specific expression tree iterator
implementation strategies via a Creational pattern
The Iterator Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Iterator pattern can be applied to access all nodes in an
expression tree flexibly & extensibly.
• Understand the structure & functionality of the Iterator pattern.
Douglas C. Schmidt
Structure & Functionality
of the Iterator Pattern
 Iterator GoF Object Behavioral
Intent
• Access elements of an aggregate
without exposing its representation

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Iterator GoF Object Behavioral
Applicability
• Require multiple traversal
algorithms over an aggregate

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Iterator GoF Object Behavioral
Applicability
• Require multiple traversal
algorithms over an aggregate
• Require a uniform traversal
interface over different
aggregates

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Iterator GoF Object Behavioral
Applicability
• Require multiple traversal
algorithms over an aggregate
• Require a uniform traversal
interface over different
aggregates
• When aggregate classes &
traversal algorithm(s) must vary
independently

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Iterator GoF Object Behavioral
Structure & participants
 Iterator GoF Object Behavioral
Structure & participants

ExpressionTree
 Iterator GoF Object Behavioral
Structure & participants
Java Iterator
 Iterator GoF Object Behavioral
Structure & participants

PreOrderIterator,
PostOrderIterator, etc.
 Iterator GoF Object Behavioral
Structure & participants

Unused in this example (but

used in Java collections)
The Iterator Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Iterator pattern can be applied to access all nodes in an
expression tree flexibly & extensibly.
• Understand the structure & functionality of the Iterator pattern.
• Know how to implement the Iterator pattern in Java.
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {
private Stack <ExpressionTree> mStack =
new Stack<>();

public PreOrderIterator(ExpressionTree tree)

{ if(![Link]()) [Link](tree); }

public boolean hasNext() { return ![Link](); }

...

See ExpressionTree/CommandLine/src/expressiontree/iterators
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {
private Stack <ExpressionTree> mStack =
new Stack<>();
PreOrderIterator implements
the Iterator interface

public PreOrderIterator(ExpressionTree tree)

{ if(![Link]()) [Link](tree); }

public boolean hasNext() { return ![Link](); }

...

See [Link]/javase/8/docs/api/java/util/[Link]
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {
private Stack <ExpressionTree> mStack =
new Stack<>();

Stack keeps track of nodes

that remain to be processed

public PreOrderIterator(ExpressionTree tree)

{ if(![Link]()) [Link](tree); }

public boolean hasNext() { return ![Link](); }

...
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {
private Stack <ExpressionTree> mStack =
new Stack<>();

public PreOrderIterator(ExpressionTree tree)

{ if(![Link]()) [Link](tree); }

Constructor initializes the iterator

public boolean hasNext() { return ![Link](); }

...
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {
private Stack <ExpressionTree> mStack =
new Stack<>();

public PreOrderIterator(ExpressionTree tree)

{ if(![Link]()) [Link](tree); }

public boolean hasNext() { return ![Link](); }

...
Check for end of iterator
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {

Advance iterator
...
public ExpressionTree next() {
ExpressionTree result = [Link]();
if(![Link]()) {
ExpressionTree temp = [Link]();
if(![Link]().isNull())
[Link]([Link]());
if(![Link]().isNull())
[Link]([Link]());
}
return result;
}
...

The use of a stack simulates recursion, one item at a time.

 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {

... Get the next item

public ExpressionTree next() {
ExpressionTree result = [Link]();
if(![Link]()) {
ExpressionTree temp = [Link]();
if(![Link]().isNull())
[Link]([Link]());
if(![Link]().isNull())
[Link]([Link]());
}
return result;
}
...
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {

...
public ExpressionTree next() {
ExpressionTree result = [Link]();
if(![Link]()) {
Remove the next
ExpressionTree temp = [Link]();
item from the stack
if(![Link]().isNull())
[Link]([Link]());
if(![Link]().isNull())
[Link]([Link]());
}
return result;
}
...
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {

...
public ExpressionTree next() {
ExpressionTree result = [Link]();
if(![Link]()) {
ExpressionTree temp = [Link]();
if(![Link]().isNull())
[Link]([Link]());
Update the stack
if(![Link]().isNull())
[Link]([Link]());
}
return result;
}
...
 Iterator GoF Object Behavioral
Iterator example in Java
• A Stack implements a non-recursive “pre-order” algorithm for tree traversal.
class PreOrderIterator implements Iterator<ExpressionTree> {

...
public ExpressionTree next() {
ExpressionTree result = [Link]();
if(![Link]()) {
ExpressionTree temp = [Link]();
if(![Link]().isNull())
[Link]([Link]());
if(![Link]().isNull())
[Link]([Link]());
}
return result; Return the next item
}
...
 Iterator GoF Object Behavioral
Iterator example in Java
• Implement the iterator() factory method in the ExpressionTree
class to return a new PreOrderIterator.

class ExpressionTree {
...
public Iterator<ExpressionTree> iterator() {
return new PreOrderIterator(this);
} This is an application of the
Factory Method pattern.
}

We’ll cover other Iterator implementations in the Strategy pattern discussion.

 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×−
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×−5
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×−5+
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×−5+3
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

×−5+34
 Iterator GoF Object Behavioral
Iterator example in Java
• Use PreOrderIterator to print expression tree contents.
ExpressionTree exprTree = ...;

[Link]("Tree contents:");

for (Iterator<ExpressionTree> it =
[Link]();
[Link]();
) {
ExpressionTree treeNode = [Link]();
if ([Link]() instanceof LeafNode)
[Link]((int)[Link]() + " ");
else
[Link]((char)[Link]() + " ");
}

Later we’ll show how the Visitor pattern can eliminate the use of downcasts!
The Iterator Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Iterator pattern can be applied to access all nodes in an
expression tree flexibly & extensibly.
• Understand the structure & functionality of the Iterator pattern.
• Know how to implement the Iterator pattern in Java.
• Be aware of other considerations when applying the Iterator pattern.
 Iterator GoF Object Behavioral
Consequences
+ Flexibility
• Aggregate & traversal objects are
decoupled & can (co-)evolve
separately ExpressionTree ComponentNode

Composite LeafNode
UnaryNode

Composite
BinaryNode …

Java Iterator

PreOrder
Iterator …
 Iterator GoF Object Behavioral
Consequences
+ Flexibility
• Aggregate & traversal objects are
decoupled & can (co-)evolve
separately ExpressionTree ComponentNode

Composite LeafNode
UnaryNode
Adding new traversal
algorithms shouldn’t affect
the expression tree elements. Composite
BinaryNode …

Java Iterator

PreOrder
Iterator …
 Iterator GoF Object Behavioral
Consequences
+ Flexibility
• Aggregate & traversal objects are
decoupled & can (co-)evolve
separately ExpressionTree ComponentNode

Composite LeafNode
UnaryNode

Composite
BinaryNode …

Java Iterator
Adding new subclasses of
CompositeBinaryNode
shouldn’t affect the iterators.
PreOrder
Iterator …
 Iterator GoF Object Behavioral
Consequences
+ Multiplicity
• Supports multiple iterators &
multiple traversal algorithms

These traversals can all occur • “In-order” traversal = -5×(3+4)

simultaneously on the same • “Pre-order” traversal = ×-5+34
expression tree instance.
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534

Later we’ll apply the Strategy pattern to support multiple traversal algorithms.
 Iterator GoF Object Behavioral
Consequences
– Overhead
Significant overhead can occur
• Additional communication between
if there is a distribution or
iterator & aggregate user/kernel boundary crossing.

This overhead is quite problematic for iterators in concurrent or distributed systems.

 Iterator GoF Object Behavioral
Consequences
– Dependencies
• The iterator implementation may
depend on the aggregate’s
implementation ExpressionTree ComponentNode

Composite LeafNode
UnaryNode

Composite
BinaryNode …
Java Iterator

PreOrder
Iterator …
 Iterator GoF Object Behavioral
Consequences
– Dependencies
• The iterator implementation may
depend on the aggregate’s
implementation ExpressionTree ComponentNode

Composite LeafNode
UnaryNode

Composite
BinaryNode …
Java Iterator

PreOrder
… Adding a new subclass for
Iterator
CompositeTernaryNode
may affect the iterators.
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. GoF iterators
• Java iterators are similar—but not identical to—GoF iterators, e.g.,
for(Iterator<ExpressionTree> it = [Link]();
[Link]();)
doSomethingWithIterator([Link]());

See [Link]/javase/8/docs/api/java/util/[Link]
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. GoF iterators
• Java iterators are similar—but not identical to—GoF iterators, e.g.,
for(Iterator<ExpressionTree> it = [Link]();
[Link]();)
doSomethingWithIterator([Link]());
• Here’s the equivalent Java code for GoF-style iterators
for(GoFIterator it = [Link]();
![Link]();
[Link]())
doSomethingWithIterator([Link]());
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. C++11 STL iterators
• C++ Standard Template Library (STL) iterators mimic native C/C++
pointer arithmetic syntax/semantics
for (auto it = expr_tree.begin ();
it != expr_tree.end ();
++it)
do_something_with_iterator (*it);

See [Link]/iterators-c-stl
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. C++11 STL iterators
• C++ Standard Template Library (STL) iterators mimic native C/C++
pointer arithmetic syntax/semantics
for (auto it = expr_tree.begin ();
it != expr_tree.end ();
++it)
do_something_with_iterator (*it);

• Java iterators are closer to the GoF Iterator pattern

for(Iterator<ExpressionTree> it = [Link]();
[Link]();)
doSomethingWithIterator(it);
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. C++11 STL iterators
• Modern Java also supports a “Spliterator” (splitable iterator)
Consumer<ExpressionTree> action;

for(Spliterator<ExpressionTree> s = [Link]();
[Link](action);)
doSomethingWithSpliterator(s);

Create a spliterator
for an expression tree

See [Link]/javase/8/docs/api/java/util/[Link]
 Iterator GoF Object Behavioral
Implementation considerations
• Iterator style
• Java iterators vs. C++11 STL iterators
• Modern Java also supports a “Spliterator” (splitable iterator)
Consumer<ExpressionTree> action;

for(Spliterator<ExpressionTree> s = [Link]();
[Link](action);)
doSomethingWithSpliterator(s);

tryAdvance() combines
hasNext() & next()
 Iterator GoF Object Behavioral
Implementation considerations
• Internal iterators vs.
List<URL> newUrls = urlList
external iterators
.stream()
.filter(s -> [Link]("[Link]"))
.map(s -> [Link]("[Link]",
"[Link]"))
.map(rethrowFunction(URL::new))
.collect(toList());

List<URL> newUrls =
new ArrayList<URL>();
...
for (Iterator<List> i = [Link](); [Link](); ) {
String url = [Link]();
if (![Link]("[Link]")) continue;
else
[Link](new URL([Link]("[Link]",
"[Link]")));
}
See [Link]/java-8/java-8-internal-iterators-vs-external-iterators
 Iterator GoF Object Behavioral
Implementation considerations
• Internal iterators vs.
List<URL> newUrls = urlList
external iterators
.stream()
.filter(s -> [Link]("[Link]"))
.map(s -> [Link]("[Link]",
"[Link]"))
.map(rethrowFunction(URL::new))
.collect(toList());

Java external iterators are more flexible,

but are more complicated to program.
List<URL> newUrls =
new ArrayList<URL>();
...
for (Iterator<List> i = [Link](); [Link](); ) {
String url = [Link]();
if (![Link]("[Link]")) continue;
else
[Link](new URL([Link]("[Link]",
"[Link]")));
}
 Iterator GoF Object Behavioral
Implementation considerations
• Internal iterators vs.
List<URL> newUrls = urlList
external iterators
.stream()
.filter(s -> [Link]("[Link]"))
.map(s -> [Link]("[Link]",
"[Link]"))
.map(rethrowFunction(URL::new))
.collect(toList());

Java internal iterators are much easier to

program & optimize, but are less flexible.
List<URL> newUrls =
new ArrayList<URL>();
...
for (Iterator<List> i = [Link](); [Link](); ) {
String url = [Link]();
if (![Link]("[Link]")) continue;
else
[Link](new URL([Link]("[Link]",
"[Link]")));
}
 Iterator GoF Object Behavioral
Implementation considerations
• Robust iterators
• Enable insertions & deletions on the
aggregate during the iteration process

See [Link]/publications/print_versions/pdf/[Link]
 Iterator GoF Object Behavioral
Implementation considerations
• Violating the aggregate’s private class Itr
implements Iterator<E> {
encapsulation
int cursor
int lastRet = -1;
int expectedModCount = modCount;

public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData =
[Link];
[Link]() hard-codes a
dependency on the if (i >= [Link])
ArrayList implementation. throw new
ConcurrentModificationException();
cursor = i + 1;
return (E)elementData[lastRet = i];
}
See share/classes/java/util/[Link]
 Iterator GoF Object Behavioral
Implementation considerations Fail Fast Fail Safe Iterator
• Overhead & behavior in Iterator
concurrent programs Throw Yes No
Concurrent
Modification
Exception

Clone No Yes
object

Memory No Yes
overhead

Examples HashMap, CopyOnWriteArrayList,

Vector, ConcurrentHashMap
ArrayList,
HashSet

See [Link]/2014/04/[Link]
 Iterator GoF Object Behavioral
Implementation considerations
• Batching in programs that
cross distribution or user/
kernel boundaries
Batch Iterator

Batch Iterator is a pattern compound

that minimizes the impact of latency.

See [Link]/~schmidt/[Link]
 Iterator GoF Object Behavioral
Known uses
• Unidraw Iterator
• C++ STL iterators
• C buffered I/O
• C++11 range-based for
loops & Java for-each
loops
• JDK Iterator, Iterable,
& Spliterator
 Summary of the Iterator Pattern
• Iterator creates objects that traverse the Composite-based expression tree &
access each of its elements one at a time.

Bridge
ExpressionTree ComponentNode

<< create >>

Composite LeafNode
UnaryNode

Java Iterator
Composite
BinaryNode …

Iterator Composite

We’ll combine Iterator with other patterns to further improve our app design.
The Strategy Pattern
Motivating Example

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Strategy pattern can be Java Iterator
applied in the expression tree processing next()
app to encapsulate variability of algorithm hasNext()
remove()
& platform behaviors via common APIs.

LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
Douglas C. Schmidt
Motivating the Need for
the Strategy Pattern in
the Expression Tree App
A Pattern for Changing Behaviors Transparently
Purpose: Encapsulate variability of behaviors via a common API whose
implementations can be changed transparently with respect to clients.

Bridge
ExpressionTree ComponentNode

<< create >>

Composite LeafNode
UnaryNode

Java Iterator

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator

Strategy decouples the interface of a behavior from its implementations.

 Context: OO Expression Tree Processing App
• Certain program behaviors must change in response to different user requests
& runtime platforms
 Context: OO Expression Tree Processing App
• Certain program behaviors must change in response to different user requests
& runtime platforms, e.g.,
• Different algorithms are needed to traverse
the expression tree in different orders.
• e.g., to print & evaluate the tree

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Context: OO Expression Tree Processing App
• Certain program behaviors must change in response to different user requests
& runtime platforms, e.g.,
• Different algorithms are needed to traverse
the expression tree in different orders.
• Different input & output mechanisms
are needed in different runtime platforms.
• e.g., Android GUI & command-line
platforms
 Problem: Obtrusive Behavior Changes
• Hard-coding certain implementations of these behaviors is problematic since
obtrusive changes would be needed to support alternatives

class ExpressionTree {
...
public
Iterator<ExpressionTree>
iterator() {

return new
PreOrderIterator
(this);
}
...
 Problem: Obtrusive Behavior Changes
• Hard-coding certain implementations of these behaviors is problematic since
obtrusive changes would be needed to support alternatives, e.g.,
• Adding new traversal algorithms

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
 Problem: Obtrusive Behavior Changes
• Hard-coding certain implementations of these behaviors is problematic since
obtrusive changes would be needed to support alternatives, e.g.,
• Adding new traversal algorithms
• Supporting different runtime platforms
Solution: Create an Abstraction to Select Behaviors
• Define a family of behaviors.
• e.g., algorithms for traversing an
expression tree in various orders

• “In-order” traversal = -5×(3+4)

• “Pre-order” traversal = ×-5+34
• “Post-order” traversal = 5-34+×
• “Level-order” traversal = ×-+534
Solution: Create an Abstraction to Select Behaviors
• Encapsulate all behaviors to have
a common API. Java Iterator

• e.g., the Java Iterator interface

Solution: Create an Abstraction to Select Behaviors
• Make implementations of the behavior
interchangeable. Java Iterator

• Different traversal orders all

implement the same Java
Iterator interface LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator

Strategy encapsulates multiple traversal algorithms via a common API.

Solution: Create an Abstraction to Select Behaviors
• Apply a Creational pattern to select the
desired behavior in a particular context. Java Iterator

• e.g., the Factory Method pattern

<<iterator>> LevelOrder
Iterator
ExpressionTree

InOrder
Iterator

PostOrder
Define an interface for creating Iterator
an object, but let implementation
PreOrder
decide which class to instantiate. Iterator

See [Link]/wiki/Factory_method_pattern
 Strategy Hierarchy Overview
• The root of the hierarchy is based on the Java Iterator
Iterator pattern & Java Iterator interface. next()
hasNext()
remove()
 Strategy Hierarchy Overview
• Implementations of the Java Iterator Java Iterator
interface define various iterator next()
strategies. hasNext()
remove()
• e.g., pre-order, post-order, level-order,
& in-order iterators
LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
 Strategy Hierarchy Overview
• Implementations of the Java Iterator Java Iterator
interface define various iterator next()
strategies. hasNext()
remove()
• e.g., pre-order, post-order, level-order,
& in-order iterators
LevelOrder
Iterator

InOrder
Iterator
Java
Queue PostOrder
Iterator
Java Stack & Queue objects
Java PreOrder
track the state needed to perform Stack Iterator
non-recursive tree traversals.
 Strategy Hierarchy Overview
• Implementations of the Java Iterator Java Iterator
interface define various iterator next()
strategies. hasNext()
remove()
• e.g., pre-order, post-order, level-order,
& in-order iterators
LevelOrder
Iterator

InOrder
Iterator
Java
Queue PostOrder
Iterator

Java PreOrder
Stack Iterator

• Commonality: the Java Iterator interface defines a common strategy API

• Variability: implementations of this interface define concrete strategies
The Strategy Pattern
Structure & Functionality

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Strategy pattern can be applied in the expression tree
processing app to encapsulate variability of algorithm & platform behaviors
via common APIs.
• Understand the structure & functionality of the Strategy pattern.
Douglas C. Schmidt
Structure & Functionality
of the Strategy Pattern
 Strategy GoF Object Behavioral
Intent Java Iterator
• Define a family of algorithms, encapsulate next()
each one, & make them interchangeable to hasNext()
remove()
let clients & algorithms vary independently

LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator

See [Link]/wiki/Strategy_pattern
 Strategy GoF Object Behavioral
Applicability Java Iterator
• When an object should be configurable next()
hasNext()
with one of many algorithms remove()

LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
 Strategy GoF Object Behavioral
Applicability Java Iterator
• When an object should be configurable next()
hasNext()
with one of many algorithms remove()
• And all algorithms can be encapsulated

LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
 Strategy GoF Object Behavioral
Applicability Java Iterator
• When an object should be configurable next()
hasNext()
with one of many algorithms remove()
• And all algorithms can be encapsulated
• And one interface covers all
LevelOrder
encapsulations Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
 Strategy GoF Object Behavioral
Structure & participants
 Strategy GoF Object Behavioral
Structure & participants
Java Iterator
 Strategy GoF Object Behavioral
Structure & participants

PreOrderIterator, PostOrderIterator,
LevelOrderIterator, InOrderIterator, etc.
 Strategy GoF Object Behavioral
Structure & participants

Unused

Context is primarily useful if some strategies need more than the common API.
 Strategy GoF Object Behavioral
Structure & participants

Strategy

Bridge

Strategy (object behavioral) closely resembles Bridge (object structural).

 Strategy GoF Object Behavioral
Structure & participants

Strategy

These classes play

very different roles.

Bridge

Strategy (object behavioral) closely resembles Bridge (object structural).

The Strategy Pattern
Implementation in Java

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Strategy pattern can be applied in the expression tree
processing app to encapsulate variability of algorithm & platform behaviors
via common APIs.
• Understand the structure & functionality of the Strategy pattern.
• Know how to implement the Strategy pattern in Java.
 Strategy GoF Object Behavioral
Strategy example in Java
• The iterator() factory method in the ExpressionTree class returns
the requested iterator strategy.

class ExpressionTree {
...
public Iterator<ExpressionTree> iterator
(String traversalOrderRequest) {
return [Link](this,
traversalOrderRequest);
}
}

See ExpressionTree/CommandLine/src/expressiontree/tree
 Strategy GoF Object Behavioral
Strategy example in Java
• The iterator() factory method in the ExpressionTree class returns
the requested iterator strategy.

class ExpressionTree {
...
public Iterator<ExpressionTree> iterator
(String traversalOrderRequest) {
return [Link](this,
traversalOrderRequest);
}
} This Factory Method forwards
to an internal factory.
 Strategy GoF Object Behavioral
Strategy example in Java
• The iterator() factory method in the ExpressionTree class returns
the requested iterator strategy.

class ExpressionTree {
...
public Iterator<ExpressionTree> iterator
(String traversalOrderRequest) {
return [Link](this,
traversalOrderRequest);
}
}

This application of Factory Method is accessed via Bridge & implemented

using Command to create the requested Strategy used as an Iterator to
access each node in the Composite expression tree.

This
See OO design & implementation exhibits high-pattern density!
ExpressionTree/CommandLine/src/expressiontree/iterators
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.

IteratorFactory Iterator
Command
execute()

InOrder PostOrder
Iterator
HashMap<String, IteratorFactoryCommand> Iterator

Traversal Name Constructor Reference

PreOrder LevelOrder
"in-order" InOrderIterator::new Iterator Iterator
"pre-order" PreOrderIterator::new
"post-order" PostOrderIterator::new
"level-order" LevelOrderIterator::new

Each iterator factory command object implements IteratorFactory

Command & creates a concrete Iterator via a constructor reference.

See [Link]/java-8/constructor-references-java-8-simplified-tutorial
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.

Function<Iterator<ExpressionTree>,
ExpressionTree> Iterator

apply()

HashMap<String,
Function<Iterator<ExpressionTree>, InOrder PostOrder
Iterator
ExpressionTree> Iterator

Traversal Name Constructor Reference

PreOrder LevelOrder
"in-order" InOrderIterator::new Iterator Iterator
"pre-order" PreOrderIterator::new
"post-order" PostOrderIterator::new
"level-order" LevelOrderIterator::new

We could also use the Java Function functional interface!

See [Link]/javase/8/docs/api/java/util/function/[Link]
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory {

private interface IteratorFactoryCommand

{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();

IteratorFactory() {
[Link]("in-order", new IteratorFactoryCommand(){
Iterator<ExpressionTree> execute(ExpressionTree tree)
{ return new InOrderIterator(tree); }});
...
}
} ...

See ExpressionTree/CommandLine/src/expressiontree/iterators
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory { We first apply Command to
initialize IteratorFactory.
private interface IteratorFactoryCommand
{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();

IteratorFactory() {
[Link]("in-order", new IteratorFactoryCommand(){
Iterator<ExpressionTree> execute(ExpressionTree tree)
{ return new InOrderIterator(tree); }});
...
}
} ...
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory { Command interface

private interface IteratorFactoryCommand

{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();

IteratorFactory() {
[Link]("in-order", new IteratorFactoryCommand(){
Iterator<ExpressionTree> execute(ExpressionTree tree)
{ return new InOrderIterator(tree); }});
...
}
} ...

IteratorFactoryCommand is a Java “functional interface.”

 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory {

private interface IteratorFactoryCommand

{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();
Map strings to factory commands that create Iterator objects

IteratorFactory() {
[Link]("in-order", new IteratorFactoryCommand(){
Iterator<ExpressionTree> execute(ExpressionTree tree)
{ return new InOrderIterator(tree); }});
...
}
} ...
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory {

private interface IteratorFactoryCommand

{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();
An anonymous inner class defines a factory
command that creates an InOrderIterator
IteratorFactory() {
[Link]("in-order", new IteratorFactoryCommand(){
Iterator<ExpressionTree> execute(ExpressionTree tree)
{ return new InOrderIterator(tree); }});
...
}
} ...
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory {

private interface IteratorFactoryCommand

{ Iterator<ExpressionTree> execute(ExpressionTree tree); }

private HashMap<String, IteratorFactoryCommand> mIteratorMap =

new HashMap<>();

IteratorFactory() {
[Link]("in-order",
InOrderIterator::new);
...
} Java lambda that creates
} ... an InOrderIterator via
a constructor reference
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
The factory method
public class IteratorFactory { ...
public Iterator<ExpressionTree> iterator(ExpressionTree tree,
String traversalOrderRequest) {

IteratorFactoryCommand command =
[Link](traversalOrderRequest);

if (command != null)
return [Link](tree);
else
throw new IllegalArgumentException
(traversalOrderRequest
+ " is not a supported traversal order");
...
}
The factory method uses a map to find/execute the command that makes an iterator.
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory { ...
public Iterator<ExpressionTree> iterator(ExpressionTree tree,
String traversalOrderRequest) {

Try to find a pre-allocated factory command.

IteratorFactoryCommand command =
[Link](traversalOrderRequest);

if (command != null)
return [Link](tree);
else
throw new IllegalArgumentException
(traversalOrderRequest
+ " is not a supported traversal order");
...
}
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory { ...
public Iterator<ExpressionTree> iterator(ExpressionTree tree,
String traversalOrderRequest) {

IteratorFactoryCommand command =
[Link](traversalOrderRequest);
If found, execute it to make an iterator.
if (command != null)
return [Link](tree);
else
throw new IllegalArgumentException
(traversalOrderRequest
+ " is not a supported traversal order");
...
}
 Strategy GoF Object Behavioral
Strategy example in Java
• The [Link]() factory method dynamically
allocates the appropriate Iterator strategy.
public class IteratorFactory { ...
public Iterator<ExpressionTree> iterator(ExpressionTree tree,
String traversalOrderRequest) {

IteratorFactoryCommand command =
[Link](traversalOrderRequest);

if (command != null)
return [Link](tree);
else
throw new IllegalArgumentException
(traversalOrderRequest
+ " is not a supported traversal order");
... Otherwise, user gave an unsupported
} request, so throw an exception.
The Strategy Pattern
Other Considerations

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Recognize how the Strategy pattern can be applied in the expression tree
processing app to encapsulate variability of algorithm & platform behaviors
via common APIs.
• Understand the structure & functionality of the Strategy pattern.
• Know how to implement the Strategy pattern in Java.
• Be aware of other considerations when applying the Strategy pattern.
 Strategy GoF Object Behavioral
Consequences
+ Greater flexibility & reuse
• e.g., by strategizing runtime platform I/O
mechanisms, most code can be reused across
the Android GUI variant & the command-line
variant of the expression tree processing app.
 Strategy GoF Object Behavioral
Consequences
+ Behaviors can change dynamically
class ExpressionTree {
public Iterator<ExpressionTree> iterator
(String traversalOrderRequest) {
return [Link](this,
traversalOrderRequest);
... The [Link]() method enables
transparent replacement of different iterator
strategies at runtime without breaking client code.
for(Iterator<ExpressionTree> it = [Link]("in-order");
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}
 Strategy GoF Object Behavioral
Consequences
+ Behaviors can change dynamically
class ExpressionTree {
public Iterator<ExpressionTree> iterator
(String traversalOrderRequest) {
return [Link](this,
traversalOrderRequest);
... The [Link]() method enables
transparent replacement of different iterator
strategies at runtime without breaking client code.
for(Iterator<ExpressionTree> it = [Link]("post-order");
[Link]();) {
ExpressionTree node = [Link]();
doSomethingWithNode(node);
}
e.g., can change from “in-order” to “post-order”
traversal simply by changing this parameter
 Strategy GoF Object Behavioral
Consequences
– Overhead of strategy creation & communication
• Strategy can increase the number of classes/objects created in a program.
Java Iterator
next()
hasNext()
remove()

LevelOrder
Iterator

InOrder
Iterator

PostOrder
Iterator

PreOrder
Iterator
 Strategy GoF Object Behavioral
Consequences
– Overhead of strategy creation & communication
• Strategy can increase the number of classes/objects created in a program.
Java Iterator
next()
hasNext()
remove()

LevelOrder
Iterator

InOrder
Iterator

Java lambda expressions may PostOrder

help reduce the tedium of Iterator

creating many objects. PreOrder

Iterator

See [Link]/articles/strategy-pattern-using-lambda
 Strategy GoF Object Behavioral
Consequences
– Overhead of strategy creation & communication
• Strategy can increase the number of classes/objects created in a program.
• Dynamically bound implementations of Strategy may incur additional
virtual method call overhead.

0 Pointer to vtable Pointer to method1 Executable method code

4 Member field1 Pointer to method2 Executable method code
8 Member field2 Pointer to method… Executable method code
12 Member field3
… Member field…
 Strategy GoF Object Behavioral
Consequences
– Overhead of strategy creation & communication
• Strategy can increase the number of classes/objects created in a program.
• Dynamically bound implementations of Strategy may incur additional
virtual method call overhead.

0 Pointer to vtable Pointer to method1 Executable method code

4 Member field1 Pointer to method2 Executable method code
8 Member field2 Pointer to method… Executable method code
12 Member field3
… Member field…

• However, modern Java compilers

optimize virtual method dispatching
so it’s as efficient as large switch
statements or if/else chains.

See [Link]/blog/2015/black-magic-method-dispatch
 Strategy GoF Object Behavioral
Consequences
– Inflexible strategy interface

See [Link]/wiki/Procrustes#Cultural_references
 Strategy GoF Object Behavioral
Consequences
– Inflexible strategy interface
• Motivates need for Context, which stores values beyond one-size-fits-all
interface
 Strategy GoF Object Behavioral
Consequences in args

– Semantic incompatibility of
OBJ operation()
Client REF Object (Servant)
out args +
return
multiple strategies used
together inconsistently
IDL
SKEL
IDL ORB
STUBS INTERFACE Object Adapter

ORB CORE GIOP/IIOP/ESIOPS

Null-lock
synchronization
strategy
Thread pool
concurrency Reactive event
strategy demuxing strategy

See [Link]/~schmidt/PDF/[Link]
 Strategy GoF Object Behavioral
Consequences in args

– Semantic incompatibility of
OBJ operation()
Client REF Object (Servant)
out args +
return
multiple strategies used
together inconsistently
• May require other patterns, IDL
SKEL
such as Abstract Factory IDL
STUBS
ORB
INTERFACE Object Adapter

ORB CORE GIOP/IIOP/ESIOPS

Null-lock
synchronization
strategy
Thread pool
concurrency Reactive event
strategy demuxing strategy

See [Link]/wiki/Abstract_factory_pattern
 Strategy GoF Object Behavioral
Implementation considerations
• Exchanging information between a strategy & its context

Each concrete strategy could contain a reference to the

context that it could use to obtain strategy-specific data
while still conforming to the uniform strategy interface.
 Strategy GoF Object Behavioral
Implementation considerations
• Static binding of strategy selection
• e.g., via Java generics or C++ parameterized types
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);

...
std::vector<int> v ({1, 6, 2, 8, 3, 9});

std::sort ([Link] (), [Link] (), std::greater<int>());

Comparison
strategy (functor)

See [Link]/wiki/Policy-based_design for “compile-time” strategies.

 Strategy GoF Object Behavioral
Implementation considerations <<iterator>>
Java Iterator
• Strategies in Java often implemented ExpressionTree
with interfaces & factories
• Rather than using the LevelOrder
Bridge pattern Iterator

class ExpressionTree { InOrder

... Iterator
public Iterator<ExpressionTree> PostOrder
iterator(String traversalOrder) Iterator
{ return [Link]
(this, traversalOrder); } PreOrder
Iterator
}

Java’s support for garbage collection often obviates the need for Bridge.
 Strategy GoF Object Behavioral
Known uses
• InterViews text formatting
• RTL register allocation & scheduling strategies
• ET++SwapsManager calculation engines
• The ACE ORB (TAO) real-time object request broker middleware
in args
Client
OBJ operation() Request demuxing
Object (Servant)
(De)marshaling REF out args + strategy
return
strategy

Request transport
IDL strategy
Connection SKEL
management strategy IDL ORB
STUBS INTERFACE Object Adapter

ORB CORE GIOP/IIOP/ESIOPS

Event demuxing
strategy
Concurrency Synchronization strategy
strategy

[Link]/~schmidt/PDF/[Link] has more information.

 Strategy GoF Object Behavioral
Known uses
• InterViews text formatting
• RTL register allocation & scheduling strategies
• ET++SwapsManager calculation engines
• The ACE ORB (TAO) real-time object request broker middleware
• C++ Standard Template Library (STL)
• Strategy can be applied to more than “algorithms”
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
Comparison
... strategy (functor)
std::vector<int> v ({1, 6, 2, 8, 3, 9});

std::sort ([Link] (), [Link] (), std::greater<int>());

See [Link]/wiki/Function_object#In_C_and_C++
 Strategy GoF Object Behavioral
Known uses
• InterViews text formatting
• RTL register allocation & scheduling strategies
• ET++SwapsManager calculation engines
• The ACE ORB (TAO) real-time object request broker middleware
• C++ Standard Template Library (STL)
• Java JDK class libraries

String[] nameArray = {"Barbara", "James", "Mary", "John",

"Robert", "Michael", "Linda", "james", "mary"};

[Link](nameArray, String::compareToIgnoreCase);

Comparison strategy
(method reference)

See [Link]/wiki/Function_object#In_Java
 Summary of the Strategy Pattern
• Strategy encapsulates the variability of behaviors via a common API whose
implementations can be changed transparently with respect to clients.

Bridge
ExpressionTree ComponentNode

<< create >>

Composite LeafNode
UnaryNode

Java Iterator

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator

Strategy decouples the interface of a behavior from its implementations.

Algorithmic Decomposition
of the Expression Tree
Processing App

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand how to develop an algorithmic decomposition of the expression
tree processing app.
Start

Initialize

Prompt User

Read Expr

Build Tree

Process Tree

No
EOF?
Yes

End
Douglas C. Schmidt
Lesson Introduction
 Lesson Introduction
• Algorithmic decomposition is a historically popular design Start
method that structures the software based on the actions
performed by the system. Initialize

Prompt User

Read Expr

Build Tree

Process Tree

B
No
[Link]/windows/software-complexity- EOF?
bringing-order-to-ch/199901062 contains more Yes
information on algorithmic decomposition. End
 Lesson Introduction
• Algorithmic decomposition is a historically popular design Start
method that structures the software based on the actions
performed by the system. Initialize

• It iteratively & recursively A

decomposes general actions Yes
Prompt User

in an algorithm into more Verbose?

specific actions. No A
Verbose
Prompt
Read Expr
Succinct
Prompt Build Tree
B
Process Tree
Yes
Print?
No Print Tree
B
Yes No
Eval? EOF?
No Eval Tree Yes
End

See [Link]/16.355/[Link]
 Lesson Introduction
• Algorithmic decomposition is a historically popular design
method that structures the software based on the actions
performed by the system.
• It iteratively & recursively
decomposes general actions
in an algorithm into more
specific actions.
• The design components in
an algorithmic decomposition
often correspond to the
processing steps in an
execution sequence.
 Lesson Introduction
• Algorithmic decomposition is a historically popular design
method that structures the software based on the actions
performed by the system.
• It iteratively & recursively typedef struct TreeNode {
decomposes general actions ...
} TreeNode;
in an algorithm into more
specific actions.
• The design components in void prompt_user(int verbose);
an algorithmic decomposition char *read_expr(FILE *fp);
often correspond to the TreeNode *build_tree
processing steps in an (const char *expr);
execution sequence. void process_tree
(TreeNode *root, FILE *fp);
• These steps are typically void eval_tree
implemented via functions. (TreeNode *root, FILE *fp);
void print_tree
(TreeNode *root, FILE *fp);
...
 Lesson Introduction
• Algorithmic decomposition is a historically popular design
method that structures the software based on the actions
performed by the system.
• It iteratively & recursively typedef struct TreeNode {
decomposes general actions ...
} TreeNode;
in an algorithm into more
specific actions. We’ll explore this shortly.
• The design components in void prompt_user(int verbose);
an algorithmic decomposition char *read_expr(FILE *fp);
often correspond to the TreeNode *build_tree
processing steps in an (const char *expr);
execution sequence. void process_tree
(TreeNode *root, FILE *fp);
• These steps are typically void eval_tree
implemented via functions. (TreeNode *root, FILE *fp);
void print_tree
(TreeNode *root, FILE *fp);
...
We’ll explore this shortly.
Douglas C. Schmidt
Algorithmic Decomposition
of an Expression Tree
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode {

enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3]; int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode {

enum { NUM, UNARY, BINARY } tag_; Type tag
short use_;
union {
char op_[3]; int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode {

enum { NUM, UNARY, BINARY } tag_;
short use_; Reference count
union {
char op_[3]; int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode {

enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3]; int num_;
} o_; Node value
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode {

enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3]; int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_, Node child(ren)
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• A typical algorithmic decomposition for implementing expression trees
would use a C struct/union to represent the main data structure.

typedef struct TreeNode { tag_ “Class”

enum { NUM, UNARY, BINARY } tag_; Relationships
short use_; use_
1
union {
op_ Tree
char op_[3]; int num_;
Node
} o_;
#define num_ o_.num_ num_ 0|1|2
#define op_ o_.op_
union {
struct TreeNode *unary_; unary_
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_ binary_
Memory
#define binary_ c_.binary_ Layout
} TreeNode;
Algorithmic Decomposition of an Expression Tree
• It would also use a switch statement & a recursive function to build &
evaluate a tree, e.g.,
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) { Switch on type tag
case NUM: fprintf(fp, "%d", root->num_); break;
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
Algorithmic Decomposition of an Expression Tree
• It would also use a switch statement & a recursive function to build &
evaluate a tree, e.g.,
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
case NUM: fprintf(fp, "%d", root->num_); break; Print
number
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
Algorithmic Decomposition of an Expression Tree
• It would also use a switch statement & a recursive function to build &
evaluate a tree, e.g.,
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
case NUM: fprintf(fp, "%d", root->num_); break;
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp); Make recursive call
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
Algorithmic Decomposition of an Expression Tree
• It would also use a switch statement & a recursive function to build &
evaluate a tree, e.g.,
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
case NUM: fprintf(fp, "%d", root->num_); break;
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp); Make recursive call
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp); Make recursive call
fprintf(fp, ")"); break;
...
}
Evaluating the Algorithmic
Decomposition of the Expression
Tree Processing App

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Understand how to develop an algorithmic decomposition of the expression
tree processing app.
Start
• Evaluate the benefits & limitations
of algorithmic decomposition. Initialize

Prompt User

Read Expr

Build Tree

Process Tree

No
EOF?
Yes

End

This material motivates our pattern-oriented OO expression tree processing app.

 Learning Objectives in This Lesson
• Understand how to develop an algorithmic decomposition of the expression
tree processing app.
• Evaluate the benefits & limitations
of algorithmic decomposition.
• Put all the pieces together.
Douglas C. Schmidt
Benefits of
Algorithmic Decomposition
 Benefits of Algorithmic Decomposition
• The top-down “divide & conquer” based on actions Start
performed by the system is “intuitive” to developers
trained to think algorithmically. Initialize

B
Prompt User
Yes
Print?
No A
Print Tree
Yes Read Expr
Eval?
No Eval Tree
Build Tree
A
Yes Process Tree
Verbose?
No
B
Verbose
Prompt No
EOF?
Succinct
Yes
Prompt
End
 Benefits of Algorithmic Decomposition
• Algorithmic steps map clearly onto typedef struct TreeNode {
relatively straightforward & efficient ...
language features found in second & } TreeNode;
third generation programming
languages.
void prompt_user(int verbose);
• e.g., structs & functions char *read_expr(FILE *fp);
in C/C++ TreeNode *build_tree
(const char *expr);
void process_tree
(TreeNode *root, FILE *fp);
void eval_tree
(TreeNode *root, FILE *fp);
void print_tree
(TreeNode *root, FILE *fp);
...
 Benefits of Algorithmic Decomposition
• No need to incur the overhead void print_tree(TreeNode *root,
of virtual function call in this FILE *fp) {
implementation switch(root->tag_) {
case NUM: fprintf(fp, "%d",
root->num_);
break;
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
Douglas C. Schmidt
Limitations With
Algorithmic Decomposition
 Limitations With Algorithmic Decomposition
• Complexity resides in (variable) algorithms rather than (stable) structure
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
case NUM: fprintf(fp, "%d", root->num_); TreeNode data
break; structure is “passive”
case UNARY: & functions do all
fprintf(fp, "(%s", root->op_[0]); the real work.
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
print_tree(root->binary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
 Limitations With Algorithmic Decomposition
• Complexity resides in (variable) algorithms rather than (stable) structure
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
case NUM: fprintf(fp, "%d", root->num_);
break;
case UNARY:
fprintf(fp, "(%s", root->op_[0]);
print_tree(root->unary_, fp);
fprintf(fp, ")"); break;
case BINARY:
fprintf(fp, "(");
It’s all too easy to
print_tree(root->binary_.l_, fp);
make mistakes when
fprintf(fp, "%s", root->op_[0]);
switching on type tags.
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
 Limitations With Algorithmic Decomposition
• Incomplete/inefficient modeling of application domain
typedef struct TreeNode {
enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3];
int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
 Limitations With Algorithmic Decomposition
• Incomplete/inefficient modeling of application domain
typedef struct TreeNode {
enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3]; Tight coupling between
int num_; nodes/edges in union
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
 Limitations With Algorithmic Decomposition
• Incomplete/inefficient modeling of application domain tag_
typedef struct TreeNode {
use_
enum { NUM, UNARY, BINARY } tag_;
short use_;
op_
union {
char op_[3];
num_
int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_ unary_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_; binary_
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
Wastes space by making
} TreeNode;
worst-case assumptions with
respect to structs & unions

Wasted space is very problematic for “NUM” nodes, which are more than 1/2.
 Limitations With Algorithmic Decomposition
• Little/no encapsulation
typedef struct TreeNode { Implementation details
enum { NUM, UNARY, BINARY } tag_; available to clients since all
short use_; fields are public in a struct!
union {
char op_[3];
int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_;
} c_;
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
 Limitations With Algorithmic Decomposition
• Little/no encapsulation
typedef struct TreeNode {
enum { NUM, UNARY, BINARY } tag_;
short use_;
union {
char op_[3];
int num_;
} o_;
#define num_ o_.num_
#define op_ o_.op_
union {
struct TreeNode *unary_;
struct { struct TreeNode *l_,
*r_;} binary_; Use of macros pollutes
} c_; global namespace.
#define unary_ c_.unary_
#define binary_ c_.binary_
} TreeNode;
 Limitations With Algorithmic Decomposition
• Changes ripple through the entire program
typedef struct TreeNode {
enum { NUM, UNARY, BINARY, TERNARY } tag_;
union {
char op_[4];
int num_;
} o_;
...
union { The TreeNode data structure
... must be modified, which will
struct { affect many parts of the app.
Tree_Node *l_,
*m_,
*r_;
} ternary_;
} c_;
#define ternary_ c_.ternary_
} TreeNode;
 Limitations With Algorithmic Decomposition
• Changes ripple through the entire program
void print_tree(TreeNode *root, FILE *fp) {
switch(root->tag_) {
...
case TERNARY: All functions that switch on tag_ must be modified.
fprintf(fp, "(");
print_tree(root->ternary_.l_, fp);
fprintf(fp, "%s", root->op_[0]);
print_tree(root->binary_.m_, fp);
fprintf(fp, "%s", root->op_[1]);
print_tree(root->binary_.r_, fp);
fprintf(fp, ")"); break;
...
}
Douglas C. Schmidt
Putting All the
Pieces Together
 Putting All the Pieces Together
• An algorithmic decomposition yields a top-down design Start
based on the actions performed by the system.
Initialize

A Prompt User
Yes
Verbose?
A
No
Verbose
Read Expr
Prompt

Succinct Build Tree

B Prompt

Yes Process Tree

Print?
No Print Tree B
Yes
Eval? No
EOF?
No Eval Tree
Yes
End
 Putting All the Pieces Together
• This design paradigm tightly couples typedef struct TreeNode {
apps with specific requirements, enum { NUM, UNARY, BINARY,
which impedes reuse & complicates TERNARY } tag_;
sustainment. union {
char op_[4];
int num_;
} o_;
...
union {
...
struct {
Tree_Node *l_,
*m_,
*r_;
} ternary_;
} c_;
#define ternary_ c_.ternary_
} TreeNode;
 Putting All the Pieces Together
• This design paradigm tightly couples typedef struct TreeNode {
apps with specific requirements, enum { NUM, UNARY, BINARY,
which impedes reuse & complicates TERNARY } tag_;
sustainment. union {
char op_[4];
• e.g., extending the program to int num_;
support ternary operators would } o_;
require changes to multiple data ...
structures & functions. union {
...
struct {
Tree_Node *l_,
*m_,
*r_;
} ternary_;
} c_;
#define ternary_ c_.ternary_
} TreeNode;
 Putting All the Pieces Together
• Overcoming the limitations of
algorithmic design requires

Bridge
ExpressionTree ComponentNode
rethinking modeling, design, << create >>
& implementation. Composite LeafNode
UnaryNode

Java Iterator

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator
Evaluating the Object-Oriented
Design of the Expression Tree
Processing App

Douglas C. Schmidt
 Learning Objectives in This Lesson
• Evaluate the pros & cons of OO design relative to
algorithmic decomposition.
ExpressionTree

ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Learning Objectives in This Lesson
• Evaluate the pros & cons of OO design relative to
algorithmic decomposition.
• Put all the pieces together.
Douglas C. Schmidt
Benefits of Object-
Oriented Design
 Benefits of Object-Oriented Design
• More accurate modeling of the application domain

Each node in the tree only contains the state

that’s associated with its own capabilities.
ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Benefits of Object-Oriented Design
• More effective encapsulation
ExpressionTree

Clients needn’t be aware of expression

tree node implementation details.
ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Benefits of Object-Oriented Design
• Straightforward to extend the app to add new types of nodes
ExpressionTree

New component subclasses ComponentNode

work wherever existing ones do.

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite Composite

ModNode MultiplyNode DivideNode
Douglas C. Schmidt
Limitations With Object-
Oriented Design
 Limitations With Object-Oriented Design
• The solution may be overly rich in classes & associated structures.
<< use >>
ExpressionTree TreeContext InterpreterContext

Interpreter

<< build >>

ComponentNode Expr

Composite Composite
LeafNode NumberExpr BinaryExpr UnaryExpr
BinaryNode UnaryNode

<<build>>
Composite Composite Composite
AddExpr SubtractExpr NegateExpr
AddNode SubtractNode NegateNode

Composite Composite
MultiplyExpr DivideExpr
MultiplyNode DivideNode <<build>>
 Limitations With Object-Oriented Design
• The solution may be overly rich in classes & associated structures.
<< use >>
ExpressionTree TreeContext InterpreterContext

Interpreter

<< build >>

ComponentNode Expr

Composite Composite
LeafNode NumberExpr BinaryExpr UnaryExpr
BinaryNode UnaryNode

<<build>>
Composite Composite Composite
AddExpr SubtractExpr NegateExpr
AddNode SubtractNode NegateNode

Composite Composite
MultiplyExpr DivideExpr
MultiplyNode DivideNode <<build>>

• Good configuration management is needed

to handle many files & dependencies.

See [Link]/wiki/Configuration_management
 Limitations With Object-Oriented Design
• The solution may be overly rich in classes & associated structures.
<< use >>
ExpressionTree TreeContext InterpreterContext

Interpreter

<< build >>

ComponentNode Composite Expr
Builder

Composite Composite
LeafNode NumberExpr BinaryExpr UnaryExpr
BinaryNode UnaryNode

<<build>>
Composite Composite Composite
AddExpr SubtractExpr NegateExpr
AddNode SubtractNode NegateNode

Composite Composite
MultiplyExpr DivideExpr
MultiplyNode DivideNode <<build>>

• Good configuration management is needed

to handle many files & dependencies.
• Knowledge of patterns is also essential!
 Limitations With Object-Oriented Design
• May be somewhat less efficient than the original algorithm decomposition
due to the time/space overhead of virtual method dispatching

0 Pointer to vtable Pointer to method1 Executable method code

4 Member field1 Pointer to method2 Executable method code
8 Member field2 Pointer to method… Executable method code
12 Member field3
… Member field…

[Link]/wiki/Dynamic_dispatch has more information.

 Limitations With Object-Oriented Design
• May be somewhat less efficient than the original algorithm decomposition
due to the time/space overhead of virtual method dispatching

0 Pointer to vtable Pointer to method1 Executable method code

4 Member field1 Pointer to method2 Executable method code
8 Member field2 Pointer to method… Executable method code
12 Member field3
… Member field…

• Modern Java compilers can optimize

virtual method dispatching so it’s
as efficient as large switch
statements or if/else chains

See [Link]/blog/2015/black-magic-method-dispatch
Douglas C. Schmidt
Putting All the
Pieces Together
 Putting All the Pieces Together
• OO designs are characterized by structuring software architectures around
objects & classes in specific domains.

ExpressionTree ComponentNode
Visitor
<< accept >>
<< create >>
Composite LeafNode
UnaryNode

Java Iterator EvaluationVisitor PrintVisitor

Composite
BinaryNode …

LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Iterator
 Putting All the Pieces Together
• OO designs are characterized by structuring software architectures around
objects & classes in specific domains. Start
• Rather than on actions performed
by the software Initialize

Prompt User

Read Expr

Build Tree

Process Tree

No
EOF?
Yes
End
 Putting All the Pieces Together
• OO designs are characterized by structuring software architectures around
objects & classes in specific domains.
• Systems evolve & functionality changes,
ExpressionTree

but well-defined objects & class roles &

relationships are often relatively stable
over time. ComponentNode

Composite
LeafNode
UnaryNode

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode
 Putting All the Pieces Together
• OO designs are characterized by structuring software architectures around
objects & classes in specific domains.
• Systems evolve & functionality changes,
ExpressionTree

but well-defined objects & class roles &

relationships are often relatively stable
over time. ComponentNode

• To enhance flexibility & reuse, therefore,

it’s often better to base the structure of Composite
LeafNode
the software on the objects & classes UnaryNode

rather than on the actions.

CompositeBinary CompositeNegate
Node Node

Composite Composite
AddNode SubtractNode

Composite Composite
MultiplyNode DivideNode

[Link]/wiki/SOLID_(object-oriented_design) has more information.

 Putting All the Pieces Together
• Knowledge of patterns is essential to understand key roles & responsibilities
in complex software systems.
Bridge Visitor
ExpressionTree ComponentNode
Visitor
<< accept >>
<< create >>
Composite LeafNode
UnaryNode

Java Iterator EvaluationVisitor PrintVisitor

Iterator
Composite
BinaryNode …
Composite
LevelOrder
Iterator

InOrder
Iterator
Java
Queue
PostOrder Java
Iterator Stack

PreOrder
Strategy Iterator