OO Design Patterns

Ref: Design Patterns, Elements of Reusable Object-Oriented Software by Gamma, Helm, Johnson, & Vlissides
[aka The Gang of Four]

Why Design Patterns?

A mature engineering discipline codies its experience:

Addison-Welsley, 1995. Basic idea: Reusable metaphors for designing OO software systems.
[But not all patterns are truly OO.]

When confronted with endless possibilities, rely on those who have gone before you:

CS211 ooDesignPatterns

I highly recommend you buy and read this book.

[Easy to read a few pages at a time.]

When this book came out, it caused a lot of excitement: Resonance with professional software developers. Oh yeah, Ive seen that before. We call it XXX in our group. Put into writing a lot of shared knowledge. Some people complained: Whats the big deal? Everyone knows that! Book describes 23 patterns: name and description abstract representation examples (high-level and code-level) applicability and usefulness

We software professionals have done a poor job of writing down what weve learned.

CS211 ooDesignPatterns

There are thousands of patterns out there and thousands more waiting to be discovered: Some are domain specic. Some are a lot like others, special cases, etc. There is no ocial person or group who decides what is/isnt a design pattern: many DP web pages newsgroups discussions more books academic conferences special term: patterns geek

CS211 ooDesignPatterns

trade os, caveats, experiences, relative (dis)advantages relationship to other patterns

but this list isnt meant to be the last word

CS211 ooDesignPatterns

What Use Are Design Patterns?

communicate about systems with other developers give guidance in resolving non-functional requirements and trade-os: portability extensibility maintainability, re-usability, scalability avoid known traps, pitfalls, and temptations ease restructuring, refactoring coherent, directed system evolution and maintenance

Think of as a low-level software architecture or a high-level programming abstraction. First, you learn the basics (data structures, algorithms, tool and lang details). Then, you learn modules/interfaces/information hiding, classes/OO programming. Design patterns are at the next level of abstraction: read, read, read, think, think, think, apply!
[How do chess players become world class?]

Design patterns help you: design new systems using higher-level abstractions than variables, procedures, and classes. understand relative tradeos, appropriateness, (dis)advantages of patterns understand essence of what youre constructing

CS211 ooDesignPatterns

CS211 ooDesignPatterns

Graphical Notation
[similar to Rumbaughs OMT]
className methodSig(); a class (with methods and vars)

The Adapter Pattern

Intent: Convert the interface of a class into another interface clients expect. Adapter lets classes work together that couldnt otherwise because of incompatible interfaces. Motivation:

ItalicClassName means abstract

dataSig;

A class B inherits from class A or class B implements abstract class A B

A class B instantiates from class A B

methodSig();

methodImpl()

CS211 ooDesignPatterns

object

an object

object objectRef anotherObject

When we want to reuse classes in an application that expects classes with a dierent and incompatible interface, we do not want to (and often cannot) change the reusable classes to suit our application.

CS211 ooDesignPatterns


Example of the Adapter Pattern
Editor Shape BoundingBox() CreateManipulator() TextView
GetExtent() text

TextShape
BoundingBox() CreateManipulator() return text -> GetExtent() return new TextManipulator

Structure of the Adapter Pattern

Client

Target Request()

Adaptee
SpecificRequest()

(implementation)

Adapter
Request() SpecificRequest()

Using Multiple Inheritance

LineShape
BoundingBox() CreateManipulator()

Client

Target Request()

Adaptee
SpecificRequest()

CS211 ooDesignPatterns

adaptee

Adapter
Request() adaptee -> SpecificRequest()

Using Object Composition

CS211 ooDesignPatterns

10

Participants of the Adapter Pattern

Target: Denes the application-specic interface that clients use. Client: Collaborates with objects conforming to the target interface. Adaptee: Denes an existing interface that needs adapting. Adapter: Adapts the interface of the adaptee to the target interface.

Class- vs. Object-level Adapter

Class-level (might) require real MI all trad. MI problems Is Is-a the right relationship? Object-level makes for messy interface/wrapping (but can be selective): extra syntax, wrapping how much adapting will you do? lose polymorphism

CS211 ooDesignPatterns

11

CS211 ooDesignPatterns

12


Intent:

The Bridge Pattern

Xwindow

But sometimes, we want a hierarchy for A on its own, independent of these concrete classes:
Window

Decouple an abstraction from its implementation so the two can vary independently. Motivation: Usually, when an abstraction has several possible implementations, use an abstract base class with several concrete derived classes:
AbsClass

MSwindow

IconWindow

TransientWindow

IconXwindow

IconMSwindow

TransientXwindow

Could add ag to all Windows

Window::WindowKind enum {X, Win, MacOS};

and add switch statement to all routines, ... but this defeats OO programming and polymorphism!

CS211 ooDesignPatterns

13

The basic problem is that we have two dimensions: 1. Abstract windows i.e., Window, IconWindow, TransientWindow 2. Window implementations i.e., X, MS, MacOS Bridge solution: use two inheritance hierarchies and add a level of indirection.
Bridge
Window
DrawText() DrawRect() impl

Bridge

Lots of code duplication

[cloning, not good reuse]

less maintainable

CS211 ooDesignPatterns

14

Structure of the Bridge Pattern

Abstraction
Operation()

impl

Implementor
OperationImpl()

impl -> OpImpl()

WindowImpl
DevDrawText() DevDrawLIne()

RefinedAbstraction

ConcreteImplementorA
OperationImpl()

ConcreteImplementorB
OperationImpl()

CS211 ooDesignPatterns

impl->DevDrawLine() impl->DevDrawLine() impl->DevDrawLine() impl->DevDrawLine()

TransientWindow

IconWindow
DrawCloseBox()

XWindowImp
DevDrawText() DevDrawLine()

MSWindowImp
DevDrawText() DevDrawLine()

DrawBorder()

DrawRect() DrawText()

DrawRect()

XDrawLine()

XDrawString()

15

CS211 ooDesignPatterns

16

Participants
Abstraction (Window) denes interface of abstraction maintains a reference to an object of Implementor RenedAbstraction (Icon Window) extends interface of Abstraction Implementor (WindowImpl) denes interface for implementation classes often quite dierent from Abstraction usually denes primitives which Abstraction combines usefully

The Composite Pattern

Intent: Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly. Motivation: If pattern not used, clients must treat primitives and containers dierently.

CS211 ooDesignPatterns

Line
Draw()

ConcreteImplementor (XWindowImpl) implements primitives dened in Implementor

17

Usually, clients shouldnt need to know if object is primitive or composite.

CS211 ooDesignPatterns

18

Example of the Composite Pattern

Structure of the Composite Pattern

Graphic Draw()

Client Component Operation()

graphics
children

Rect.
Draw()

Text
Draw()

GraphicContainer
Draw() Add(Graphic) Remove(Graphic) GetChild(int) forall g in graphics g.Draw()

Leaf
Operation()

Leaf
Operation()

ComponentContainer
Operation() Add(Component) Remove(Component) GetChild(int) forall g in children g.Operation()

CS211 ooDesignPatterns

Picture
Draw() Add(Graphic) Remove(Graphic) GetChild(int)

19

ConcreteCompContainer1
Operation() Add(Component) Remove(Component) GetChild(int)

ConcreteCompContainer2
Operation() Add(Component) Remove(Component) GetChild(int)

CS211 ooDesignPatterns

20


Notes on the Composite Pattern
Gamma et al. think that the management routines should be declared at the top level, even if leaves (e.g., Rectangle) have no use for them their motivation is transparency: only one interface which everyone implements. This is WRONG OO-wise. If you use a second interface (i.e., Container), can still use the Graphic interface most of the time

Participants of Composite Pattern

Component (Graphic) Declares the interface for objects in the composition. Implements default behavior for the interface common to all classes. BUT should NOT declare an interface for accessing and managing its child components (Gamma et al. says it should) Leaf (Rectangle) Represents leaf objects in the composition. A leaf has no children. denes behavior for primitive objects in the composition.

CS211 ooDesignPatterns

Client

Why did they do this? Confusion of C++ RTTI with proper dynamic type information. This is completely safe in Java.

21

CS211 ooDesignPatterns

22

The Facade Pattern

ComponentContainer (GraphicContainer ) Denes interface for components having children. Stores child components. Implements some child-related operations in the component interface; defers others to its derived classes ConcreteCompContainer (Picture) Denes remaining behavior (for components having children) not dened by ComponentContainer.

Intent: Provide a single, unied interface to a set of interface/modules in a subsystem. Abstracts a whole subsystem into one interface. Motivation: Reduce complexity of a system. Increase cohesion within a subsystem and reduce coupling with other parts of the system.

CS211 ooDesignPatterns

Manipulates objects in the composition through the component interface.

23

Fewer, simpler, interactions within system Easier to use, reuse Easier to replace components.

CS211 ooDesignPatterns

24

Example of the Facade Pattern

Structure of the Facade Pattern

Compiler Compile() Scanner CodeGenerator Parser Token

Client Classes

Facade
ProgNodeBuilder RISCCG ProgNode StackMachineCG

StatementNode

CS211 ooDesignPatterns

ExpressionNode VariableNode

Compiler Subsystem Classes

25

Another Example of the Facade Pattern

Subsystem Classes

CS211 ooDesignPatterns

26

Participants of the Facade Pattern

Facade (Compiler)

MINITUNIS

USER_SYS
main Control Family User State

Knows which subsystem classes are responsible for a request. Delegates client requests to appropriate subsystem objects. Subsystem still does the work; facade just directs trac. Subsystem Classes (Other SS components)

FILE_SYS
File Directory FileTable Computer Memory

INODE_SYS
Inode InodeTable FileIO FreeInode InodeGlobals Disk DiskMutex

DEVICE_SYS
DeviceDriver Tty

Implement subsystem functionality.

CS211 ooDesignPatterns

GLOBALS
System Panic

27

Handle work assigned by the facade object. Have no knowledge of the facade; that is, they keep no references to it.

CS211 ooDesignPatterns

28


Intent:

The Mediator Pattern

An Object-Level Example
aListBox aClient
director director

aFontDialogDirector aButton
director

Dene an object that encapsulates how a set of objects interact, rather than having the objects refer to each other explicitly. Motivation: Simpler model; components send messages to the manager who decides how to reroute them. Easier to evolve components, less special knowledge scattered around subsystem

anotherButton
director

CS211 ooDesignPatterns

Allows for dierent kinds of dependencies/communication between components.

29

CS211 ooDesignPatterns

30

A Class-Level Example

Structure: Object-Level

DialogDirector
ShowDialog() CreateWidget() WidgetsChanged(Widget)

director

Widget
Changed()

aColleague aColleague
mediator
director->WidgetsChanged(this)

mediator

aConcreteMediator
ListBox
GetSelection()

EntryField
SetText()

FontDialogDirector
CreateWidget() WidgetsChanged(Widget)

list

aColleague
mediator
field

aColleague
mediator

CS211 ooDesignPatterns

31

CS211 ooDesignPatterns

32


Structure: Class-Level
Mediator
mediator

Participants of the Mediator Pattern

Mediator (DialogDirector) denes an interface for communicating with colleague observers ConcreteMediator (FontDialogDirector) implements co-operative behaviour by co-ordinating Colleague objects
ConcreteColleague1 ConcreteColleague2

Colleague

knows and maintains its list of colleagues Colleague classes (Listbox)

ConcreteMediator

CS211 ooDesignPatterns

33

each colleague knows who its mediator object is each colleague communicates with its mediator when it wants to send messages

CS211 ooDesignPatterns

34

The Observer Pattern

Most appropriate when:

Intent: Dene a one-to-many dependency between objects so that when one object changes state, all its dependents are notied and updated automatically. Motivation:

(Dis)Advantages:

A common side-eect of partitioning a system into a collection of cooperating classes is the need to maintain consistency between related objects.

CS211 ooDesignPatterns

35

You dont want to achieve consistency by making the classes tightly coupled, because that reduces their re-usability.

CS211 ooDesignPatterns

36


Example of the Observer Pattern
a x y z b c a a b c b c
60 30 10 50 30 20 80 10 10

Subject
Attach(Observer) Detach(Observer) Notify()

Structure of the Observer Pattern

The key objects in this pattern are subject and observer. A subject may have any number of dependent observers. All observers are notied whenever the subject undergoes a change in state.
observers

Observer Update()

a = 50% b = 30% c = 20%

for all o in observers { o -> Update() }

CS211 ooDesignPatterns

change notification

requests, modifications

37

Participants of the Observer Pattern

GetState() SetState() subjectState

ConcreteObserver
Update() subject return subjectState observerState observerState = subject->GetState()

ConcreteSubject

CS211 ooDesignPatterns

38

When to use the observer pattern:

Subject Knows its numerous observers. Provides an interface for attaching and detaching observer objects. Sends a notication to its observers when its state changes. Observer Denes an updating interface for concrete observers. ConcreteSubject Stores state of interest to concrete observers. ConcreteObserver lets you vary subject and observer independently decouples structure between objects when a change to one object requires changes to others, but you dont know (or ought to know) which ones those are when an the objects should not be tightly coupled

Notes:
after being informed of a change, Observer may query subject for more information

CS211 ooDesignPatterns

Maintains a reference to a concrete subject object. Stores state that should stay consistent with the subjects. Implements the updating interface.

39

can use abstract classes for Subject and Observer more exible, easier variation and composition ...

CS211 ooDesignPatterns

40

There are two basic models of updating: 1. push all observers notied whether they want the information or not

Flyweight Pattern
Intent: Use sharing to support large numbers of nely-grained objects eciently. Motivation: Some applications use lots of nely-grained (i.e., little) objects. BUT objects entail overhead (wrapping). If LOTS of such objects are required AND if such objects are really values at heart, then make a single pool of these objects for everyone to share.

2. pull subjects are sent little or no information (There has been a change; contact me for more details.) Might not want to push all of the information around to all observers: Not all objects need or ought to know everything. Message passing takes time, space, overhead. Some changes are undone or superuous

CS211 ooDesignPatterns

Subjects may register for only some kinds of information Have to specialize kinds of messages, more detail to manage.

41

Examples of the Flyweight Pattern

Java scalar wrapper classes (e.g., Integer) + GC Java Strings + GC Word processing system would like to treat all entities as objects for sake of system uniformity, even chars Solution: Treat chars as object-values Global pool of constant objects; likely stored in a table of some kind for look up, but clients can link to these objects directly. only one object instantiated to represent, say, letter m. All uses of m are links to the global object representing this letter. each letter-object represents a constant value rather than an interesting independent object with mutable state.

CS211 ooDesignPatterns

42

Round and round the ragged rock the ragged rascal ran (apparently with no ill effects from the DDT on the grass). She sells sea shells by the sea shore; however, failure to disclose such earnings is a direct violation of federal income tax laws. Dont try this at home.

User text

row object

character object references

Representation

CS211 ooDesignPatterns

43

Letter Object Pool

a b k u

d n x

e o y

f p z

h i s

j t
character objects

l m v w

q r

CS211 ooDesignPatterns

44


Glyph
Draw (Context) Intersects (Point, context)
children children

Row Character
Draw (Context) Intersects (Point, context) char c

Column
Draw (Context) Intersects (Point, context)

Draw (Context) Intersects (Point, context)

Could have separate object pool for each font family, pass in locations, size, slant, text colour to drawChar Allows for exible font family hierarchies rather than monolithic character class Call yweight because each object stores minimal information about its state

Notes:
letter-objects cannot (easily) have back references to the containing object When it comes time to draw the character, will have to pass in appropriate context that would normally be part of the object state e.g., (x, y ) screen locations, font information, text colour

CS211 ooDesignPatterns

45

CS211 ooDesignPatterns

46

Structure of the Flyweight Pattern

Participants of the Flyweight Pattern

Flyweight (Glyph)

FlyweightFactory
getFlyweight(key)

flyweights

Flyweight
Operation (extrinsicState)

ConcreteFlyweight1
Operation (extrinsicState) intrinsicState

ConcreteFlyweight2
Operation (extrinsicState) intrinsicState

declares an interface through which yweights can receive and act on extrinsic state Concrete Flyweight (Character) implements the Flyweight interface and adds storage for intrinsic state (if any).

Client

CS211 ooDesignPatterns

if (flyweight[key] exits) { return existing flyweight } else { create new flyweight add it to the pool return a ref. to it }

47

An instance of this class must be sharable Any state it stores must be intrinsic

CS211 ooDesignPatterns

48


Flyweight Factory creates and manages Flyweight objects as needed might create all yweight objects at start or just as needed Client maintains references to yweights computes/stores extrinsic state of yweight objects

Applicability of Flyweight Pattern

All of the following should be true: Applications uses LARGE number of objects most object state can be made extrinsic practically proliferation of objects will be greatly reduced by using a shared pool (non-extrinsic) object identity doesnt matter

ensures sharing is done properly, provides (and sometimes creates) instances as requested

CS211 ooDesignPatterns

49

CS211 ooDesignPatterns

50

Notes on Flyweights
creation may be done once at initialization or as needed on the y need to manage context (extrinsic state) separately from the objects This is unnatural and awkward! Watch out for errors, funny assumptions, odd glue commonly done to manage system resources

Consider how Java handles strings:

String instances are immutable once created
[Use StringBuffer for mutable strings] String s1, s2; s1 = "hello"; s2 = "hello"; if (s1 == s2) { ...

% Probably wrong

[You probably meant to say if (s1.equals(s2))]

Also, all Java scalars have corresponding wrapper classes (e.g., Integer.

CS211 ooDesignPatterns

e.g., system fonts, colour maps

51

CS211 ooDesignPatterns

52


Intent:

The Iterator Pattern

How its done in various programming languages: Lisp-y functional languages provide mapcar-like function to do this. Pass in a function as an argument. C/C++ allow function-as-arguments, but C++ also provides an iterator class in the STL Java does not allow function-as-arguments, but does an iterator construct called an Enumeration.

Provide a clean, abstract way to access all of the elements in an aggregate (container) without exposing the underlying representation. Also, moves responsibility for access and traversal to a separate iterator object.

Motivation:
Often want to say to a container (e.g., tree, graph, table, list, graphic), Apply f() to each of your objects. . Dont want to expose implementation details of the container AND want to allow multiple simultaneous traversals Create separate interface/class that provides simple hooks.

CS211 ooDesignPatterns

53

CS211 ooDesignPatterns

54

Example in Java Java Enumerations

java.util.Enumeration is an interface that may be implemented by any class.
public interface Enumeration public abstract boolean hasMoreElements(); public abstract Object nextElement(); class CardPlayer { ... // CardPile extends java.util.Vector CardPile tricks; // Count up how many points Ive earned in // my tricks this round and add it to my // running total. public void countAndAddPoints () { int numPointsThisRound = 0; Enumeration tricksEnum = tricks.elements(); while (tricksEnum.hasMoreElements()) { Card c = (Card) tricksEnum.nextElement(); numPointsThisRound += c.value(); } points += numPointsThisRound; }

java.util.Vector (array with resizable bounds) denes a method called elements that returns an enumeration of the vector.

CS211 ooDesignPatterns

public class Vector public final synchronized Enumeration elements();

55

CS211 ooDesignPatterns

56


Structure of the Iterator Pattern
list

List ListIterator
First() Next() IsDone() CurrentItem() index

Participants of the Iterator Pattern

Iterator Denes an interface for accessing and traversing elements. ConcreteIterator Implements an iterator interface. Keeps track of the current position in the traversal of the aggregate. Aggregate Denes an interface for creating an iterator object.

Count() Append(Element) Remove(Element)

...

CS211 ooDesignPatterns

57

ConcreteAggregate Implements the iterator creation interface to return an instance of the proper concrete iterator.

CS211 ooDesignPatterns

58

Notes on the Iterator Pattern

The iterator interface basically provides two hooks: Next, please. All done? Can provide a few others hooks too (how many left, go back, start over, etc.) Can dene dierent iterator implementation that redene what next element means.

Can have multiple iterations ongoing simultaneously (enumerator state basically consists how far along it is in the list). Of course, if you change (or allow others to change) the aggregate (add/remove) or its contained objects, then chaos may result! May therefore want to lock out changes during an iteration (concurrency control) iterator may take fast snapshot of aggregate state and use that to iterate through may want to buer requested changes while an iterator is active, then commit

CS211 ooDesignPatterns

walk through a tree, alphabetical order, LRU

59

Complicated structures may be dicult to iterate through Store path taken or nodes visited

CS211 ooDesignPatterns

60

The Template Method Pattern

};

Example (Cargill again)

Intent: Dene the skeleton of an algorithm in an operation, deferring some steps to subclasses. Template Method lets subclasses redene certain steps of an algorithm without changing the algorithms structure. Motivation: By dening some of the steps of an algorithm using abstract operations, the template method xes their ordering.

class Vehicle { private: char *plate; protected: virtual char *group () = 0; public: Vehicle () {plate=NULL;} Vehicle (char *p) { plate = new char [strlen(p)+1]; strcpy (plate, p); } virtual ~Vehicle () {delete [] plate;} virtual void identify () { char *p = plate ? plate : "<none>"; printf ("%s with plate %s\n", group(), p); }

CS211 ooDesignPatterns

Provide the skeleton of a method, where parts are dened/overridden by derived classes.

Typically, do NOT override the template method itself.

61

// Define similarly for Truck class Car : public Vehicle { private: char *group () {return "Car";}; public: Car () : Vehicle () {} Car (char *p) : Vehicle (p) {} };

CS211 ooDesignPatterns

62

Participants of the Template Pattern Structure of the Template Method Pattern

AbstractClass (Vehicle) Denes abstract primitive operations that concrete subclasses dene to implement steps of an algorithm. Implements a template method dening the skeleton of an algorithm. The template method calls primitive operations as well as operations dened in AbstractClass or those of other objects. ConcreteClass (Car, Truck)

AbstractClass
TemplateMethod()

...
PrimitiveOp1()

... ...

PrimitiveOp1() PrimitiveOp2()

PrimitiveOp2()

ConcreteClass

CS211 ooDesignPatterns

PrimitiveOp1() PrimitiveOp2()

63

Implements the primitive operations to carry out subclass-specic steps to the algorithm.

CS211 ooDesignPatterns

64


Notes on the Template Method Pattern
Very common to have in abstract base classes, esp. libraries intended for reuse and customization. A kind of polymorphism (think about it) practised within a class hierarchy. Whatever object I turn out to be, use my denition on primitiveOp(), then print, ... This is a common pattern to recognize during secondary passes at design.

Intent:

The Memento Pattern

Without violating encapsulation, capture and externalize an objects internal state so that the object can be restored to this state later. Motivation: Often want to be able to take snapshots of an objects current state in case: want to unroll changes debugging store sequence of abstract transactions by class that is not privy to underlying representation of transaction.

CS211 ooDesignPatterns

state

Refactor commonalities into the parent class; push as much as possible as high as possible.

65

BUT dont want to break encapsulation/information hiding state type must be opaque

CS211 ooDesignPatterns

66

Participants of the Memento Pattern

Memento

Structure of the Memento Pattern

memento

Originator
SetMemento (Memento m) CreateMemento()

Memento
GetState() SetState() state

Caretaker

Stores internal state of the Originator object. The memento may store as much or as little of the originators internal state as necessary at its originators discretion. Protects against unwanted access by objects other than the Originator. Eectively has two interfaces: narrow and wide Originator

return new Memento (state);

state = m->getState();

CS211 ooDesignPatterns

67

Creates a memento containing a snapshot of its current internal state. Uses the memento to restore its internal state.

CS211 ooDesignPatterns

68


Caretaker is responsible for the mementos safekeeping. never directly operates on or examines the contents of a memento.

Notes on the Memento Pattern

Simplies Originator as others may now maintain collections of state, albeit without being able to look under the hood Dont forget TNSTAAFL Temptation to store all states for unlimited undo BUT dont forget that everything takes storage.
[Did you keep every mail message you ever received?]

CS211 ooDesignPatterns

69

Design Patterns Summary

CS211 ooDesignPatterns

70

Intended to provide a common: vocabulary for inter-developer communication. set of abstract building blocks for system designers set of patterns to look for when refactoring / redesigning / reverse engineering existing systems. Not exclusively OO, despite the book title; really based on encapsulation and interacting objects. Seems particularly useful for concurrent/distributed systems where logic is hard to get right and possibilities are too numerous. Early days yet, but many are very excited.

CS211 ooDesignPatterns

71