COSC 3P91: Week 4 Notes

Design Pattern - Factory

• a creational pattern

Intent

To define an interface for creating objects but let subclasses decide which class to instantiate and how

Motivation

• Display classes for different sorting algorithms
• SortDisplayFactory creates suitable instance depending on the algorithm actually used
  • One class which displays a bubble sort algorithm in an appropriate way in a window
  • Another class which displays an insertion sort in another appropriate way in a window
  • Based on what the user selects, it should show the proper one they selected
    • Can be done with if/else statements, but it is better practice to keep it separate

Factory Model

classDiagram
    class Factory {
        +createProduct()
    }
    
    class ConcreteFactory {
        +createProduct()
    }
    
    class Product {
    }
    
    class ConcreteProduct {
    }

    Factory <|-- ConcreteFactory
    Product <|-- ConcreteProduct
    ConcreteFactory --> ConcreteProduct : Creates

Design Pattern - Abstract Factory

• aka “Kit”
• a creational pattern

Intent

Provide interface for creating families of related objects without specifying concrete representation

Simplified Explanation

Lets say you are creating a game with 3 worlds (normal, fairy world, and medieval world). You can create each of these worlds separately, or you can create a Abstract Factory, which would have a single world that is changed based on which thing it is. For example, the enemies in the normal world could be zombies, and could be ogres in the medieval world. The rest of the game would be the same, but you can change the enemy and anything else you need to separate them.

Motivation

• toolkit that supports multiple standards
• e.g. look and feel of widgets
  • define WidgetFactory that declares interface for each kind of widget
  • concrete subclasses implements widgets for different look and feel standards
  • client call operations in WidgetFactory, remaining independent of actual look and feel

Abstract Factory Model

classDiagram
    class AbstractFactory {
        +CreateProductA()
        +CreateProductB()
    }
    
    class ConcreteFactory1 {
        +CreateProductA()
        +CreateProductB()
    }

    class ConcreteFactory2 {
        +CreateProductA()
        +CreateProductB()
    }

    class AbstractProductA {
    }

    class ProductA1 {
    }

    class ProductA2 {
    }

    class AbstractProductB {
    }

    class ProductB1 {
    }

    class ProductB2 {
    }

    class Client {
    }

    AbstractFactory <|-- ConcreteFactory1
    AbstractFactory <|-- ConcreteFactory2

    AbstractProductA <|-- ProductA1
    AbstractProductA <|-- ProductA2

    AbstractProductB <|-- ProductB1
    AbstractProductB <|-- ProductB2

    ConcreteFactory1 --> ProductA1
    ConcreteFactory1 --> ProductB1
    ConcreteFactory2 --> ProductA2
    ConcreteFactory2 --> ProductB2

    Client --> AbstractFactory
    Client --> AbstractProductA
    Client --> AbstractProductB

When should you use it?

• system should be independent of how products are created, composed, and represented
• family of products designed to be used together
  • everything from normal, fairy, and medieval worlds to be used together
• want to provide library of products and reveal only interfaces not implementation

What are the consequences?

• isolates concrete classes
• easy to exchange product “families”
• promotes consistency among products
• difficult to support new products
  • you need to modify multiple classes to add a new product
  • referring to Abstract Factory Model, you would need to create a whole new hierarchy for a new AbstractProductC

Design Pattern - Command

• aka “Action”
• a behavioural pattern

Intent

To encapsulate an action as an object, so that objects can be passed as parameters, queued, and possible undone

When should you use it?

• when actions need to be passed as parameters
• when actions need to be queued and then executed later
• when actions can be undone

Command Model

classDiagram
    class Client {
        +create()
    }
    class Invoker
    
    class Command {
        +execute()
    }
    
    class ConcreteCommand {
        +execute()
    }
    
    class Receiver {
        +action()
    }

    Client --> Receiver : create
    Invoker o-- Command
    Command <|-- ConcreteCommand
    ConcreteCommand --> Receiver : receiver
    ConcreteCommand ..> Receiver : receiver->action()

How to use it

• parameterize objects by actions to perform
• specify, queue, and execute requests at different times
• support undo

What are the consequences?

• patterns are first-class objects
• you can assemble commands into a composite command (design pattern - composite)
• easy to add new commands

Design Pattern - Observer

• Aka “Dependents”, “Publish-and-Subscribe”
• a behavioural pattern
• Initially implemented in SmallTalk

Intent

• define dependencies between objects
• when an object changes state, ensure all dependents are notified and updated

Motivation

• need to maintain consistency among cooperating classes
• e.g. MVC GUI model
  • multiple views of same data
    • multiple windows on same text file
  • subject
  • observers

Model View Controller Model

graph TD;
    Subject["Subject\na = 50% \nb = 30% \nc = 20%"]
    
    TableObserver["Table Observer\n(Data Table: values of a, b, c for x, y, z)"]
    BarChartObserver["Bar Chart Observer\n(Bar chart representing a, b, c percentages)"]
    PieChartObserver["Pie Chart Observer\n(Pie chart representing a, b, c percentages)"]

    Subject -->|change notification| TableObserver
    Subject -->|change notification| BarChartObserver
    Subject -->|change notification| PieChartObserver

    TableObserver -.->|requests, modifications| Subject
    BarChartObserver -.->|requests, modifications| Subject
    PieChartObserver -.->|requests, modifications| Subject

When should you use it?

• abstraction has two aspects, one dependent on the other
• change to an object requires changing an unknown number of others
• object needs to notify other objects without knowing details about them

What are the consequences?

• abstract coupling between Subject and Observer
• broadcast communication
• unexpected updates

Considerations

• mapping subjects to observers
• observing more than one subject
• triggering the update
• deleted subjects
• self-consistent state in subject
• how much information to send on update

Observer Structure

classDiagram
    class Subject {
        +Attach(Observer)
        +Detach(Observer)
        +Notify()
    }

    class Observer {
        +Update()
    }

    class ConcreteSubject {
        +GetState()
        +SetState()
        -subjectState
    }

    class ConcreteObserver {
        +Update()
        -observerState
    }

     Comments to describe behavior
     ConcreteObserver retrieves state from ConcreteSubject

Observer - Interaction

sequenceDiagram
    participant aConcreteSubject
    participant aConcreteObserver
    participant anotherConcreteObserver

    aConcreteObserver ->> aConcreteSubject: SetState()
    aConcreteSubject ->> aConcreteSubject: Notify()
    aConcreteSubject ->> aConcreteObserver: Update()
    aConcreteObserver ->> aConcreteSubject: GetState()
    aConcreteSubject -->> aConcreteObserver: return state
    aConcreteSubject ->> anotherConcreteObserver: Update()
    anotherConcreteObserver ->> aConcreteSubject: GetState()
    aConcreteSubject -->> anotherConcreteObserver: return state

Design Pattern - Strategy

• aka “Policy”
• a behavioural pattern

Intent

• allow different variants of an algorithm

Motivation

• different traversals for sorted aggregates based on different orderings
• it is difficult to add new orderings or vary existing once when they are an integral part of the traversal

Strategy Model

classDiagram
    class Context {
        +ContextInterface()
    }
    
    class Strategy {
        +AlgorithmInterface()
    }
    
    class ConcreteStrategyA {
        +AlgorithmInterface()
    }

    class ConcreteStrategyB {
        +AlgorithmInterface()
    }

    class ConcreteStrategyC {
        +AlgorithmInterface()
    }

    Context --> Strategy : Uses
    Strategy <|-- ConcreteStrategyA
    Strategy <|-- ConcreteStrategyB
    Strategy <|-- ConcreteStrategyC

More information on the Strategy Model will be added in the next lecture

Ordering and Sorting

Order (partial order)

Total order versus strictly partial order

Natural Order

By implementing Comparable interface

Imposed Order

By use of Comparator

Comparable

• compareTo
  • parameter: a.compareTo(b)
  • result
  • total order
  • consistency with equals

Comparator

public interface Comparator<T> {
	public int compare(T o1, T o2);
	public boolean equals(Object obj);
}

• Strategy Design Pattern
• compare
  • parameters: c.compare(a,b)
  • result
  • total order
  • consistency with equals

End of lecture 1

Design Pattern - Composite

Intent

Compose objects into tree structures to represent part-whole hierarchies.

When should you use it?

• you want to represent part-whole hierarchies of objects
• you want clients to be able to ignore the difference between compositions of objects and individual objects

Composite Structure

classDiagram
    class Client {
    }

    class Component {
        <<abstract>>
        Operation()
        Add(c : Component)
        Remove(c : Component)
        GetChildren() : Collection
    }

    class Leaf {
        Operation()
    }

    class Composite {
        Operation()
        Add(c : Component)
        Remove(c : Component)
        GetChildren() : Collection
    }

    Client --> Component
    Component <|-- Leaf
    Component <|-- Composite
    Composite --> "children" Component : contains
    Composite ..|> Component

    note for Leaf "forall g in children\ng.Operation();"

Composite Example

public abstract class Tree<E> implements Iterable<E> {
	
	private E element;
	
	public Tree(E element) {
		this.element = element;
	}
	
	public E getElement() {
		return element;
	}
		
	public abstract boolean contains(E element);
 
	public boolean containsAll(Collection<E> collection) {
		boolean result = true;
		for(E element : collection) 
					result &= contains(element);
		return result;
	}
 
		public abstract int size();
	public abstract int depth();
	
	public Iterator<E> iterator() {
		return new DfsTreeIterator<E>(this);
	}
}

public class Leaf<E> extends Tree<E> {
	
	public Leaf(E element) {
		super(element);
	}
	
	public boolean contains(E element) {
		return element.equals(getElement());
	}
 
	public int size() {
		return 1;
	}
	
	public int depth() {
		return 1;
	}
	
}

public class Node<E> extends Tree<E> {
	
	private Tree<E> left;
	private Tree<E> right;
	
	public Node(E element, Tree<E> left, Tree<E> right) {
		super(element);
		this.left = left;
		this.right = right;
	}
	
	public boolean contains(E element) {
		return element.equals(getElement()) || left.contains(element) || right.contains(element);
	}
 
	public int size() {
		return left.size() + right.size() + 1;
	}
 
	public int depth() {
		return Math.max(left.depth(),right.depth()) + 1;
	}
	
	public Tree<E> getLeftSubTree() {
		return left;
	}
	
	public Tree<E> getRightSubTree() {
		return right;
	}
}

A tree

graph TD;
    1 --> 2;
    1 --> 3;
    2 --> 4;
    2 --> 5;
    3 --> 6;
    3 --> 7;
    6 --> 8;
    6 --> 9;

 
public static Tree<Integer> createTree() {
	Tree<Integer> t1 = new Leaf<Integer>(8);
	Tree<Integer> t2 = new Leaf<Integer>(9);
	Tree<Integer> t3 = new Node<Integer>(6,t1,t2);
	Tree<Integer> t4 = new Leaf<Integer>(7);
	Tree<Integer> t5 = new Node<Integer>(3,t3,t4);
	Tree<Integer> t6 = new Leaf<Integer>(4);
	Tree<Integer> t7 = new Leaf<Integer>(5);
	Tree<Integer> t8 = new Node<Integer>(2,t6,t7);
	return new Node<Integer>(1,t8,t5);
}

Iterators for Tree

Depth-first Traversal

public class DfsTreeIterator<E> implements Iterator<E> {
 
	private Iterator<E> iter;
	
	public DfsTreeIterator(Tree<E> tree) {
		List<E> list = new ArrayList<E>();
		toList(tree,list); 
		iter = list.iterator();
	}		
	
	public E next() {
		return iter.next();
	}
 
	public boolean hasNext() {
		return iter.hasNext();
	}
	
	public void remove() {
		throw new UnsupportedOperationException();
	}
	
	private void toList(Tree<E> tree, List<E> list) {
	    list.add(tree.getElement());
		if (tree instanceof Node<?>) {
		     toList(((Node<E>) tree).getLeftSubTree(),list);
		     toList(((Node<E>) tree).getRightSubTree(),list);
		}
	}
}

Running: for(Integer n : tree) System.out.print(n + " ");

graph TD;
    1 -->|1| 2;
    1 -->|4| 3;
    2 -->|2| 4;
    2 -->|3| 5;
    3 -->|5| 6;
    3 -->|8| 7;
    6 -->|6| 8;
    6 -->|7| 9;

    1 -.->|1| 2;
    2 -.->|2| 4;
    4 -.->|3| 5;
    5 -.->|5| 6;
    6 -.->|7| 9;
    3 -.->|5| 6;
    7 -.->|8| 9;

Prints 1 2 4 5 3 6 8 9 7

Breadth-first Traversal

public class BfsTreeIterator<E> implements Iterator<E> {
 
	private Iterator<E> iter;	
	
	public BfsTreeIterator(Tree<E> tree) {
		List<E> list = new ArrayList<E>();
		LinkedList<Tree<E>> openList = new LinkedList<Tree<E>>();
		openList.add(tree);
		toList(openList,list); 
		iter = list.iterator();
	}		
	
	public E next() {
		return iter.next();
	}
	
	public boolean hasNext() {
		return iter.hasNext();
	}
 
	public void remove() {
		throw new UnsupportedOperationException();
	}
	
	private void toList(LinkedList<Tree<E>> openList, 
                       List<E> list) {
		while (!openList.isEmpty()) {
			Tree<E> tree = openList.removeFirst();
			list.add(tree.getElement());
			if (tree instanceof Node<?>) {
				openList.addLast(
					((Node<E>) tree).getLeftSubTree());
				openList.addLast(
					((Node<E>) tree).getRightSubTree());
			};
		}
	}
}

Running:

for(Iterator<Integer> it = new BfsTreeIterator<Integer>(tree); 
it.hasNext(); )
System.out.print(it.next() + " ");

graph TD;
    1 --> 2;
    1 --> 3;
    2 --> 4;
    2 --> 5;
    3 --> 6;
    3 --> 7;
    6 --> 8;
    6 --> 9;

    1 -.->|1| 2;
    2 -.->|2| 3;
    2 -.->|3| 4;
    4 -.->|4| 5;
    5 -.->|5| 6;
    6 -.->|6| 7;
    6 -.->|7| 8;
    8 -.->|8| 9;

Prints 1 2 3 4 5 6 7 8 9

Design Pattern - Decorator

• aka “filter”, “wrapper”

Intent

Attach additional responsibilities to an object dynamically

When should you use it?

• to add responsibilities to individual objects dynamically and transparently, that is, without affecting other objects
• for responsibilities that can be withdrawn
• when extension by subclassing is impractical

Decorator Structure

TODO: add diagram when we get access to slides

Decorator Example

TODO: add code when we get access to slides

Adapter

• aka “Wrapper”
• a structural pattern

Intent

convert interface of a class into another interface clients expect

Motivation

• sometimes object provides appropriate behaviour but uses a different interface than is required

E.g.

• TextShape as adapted TextView in a drawing editor
• Shape hierarchy
• Existing TextView class
  • modify TextView class?
• TextShape as adapter
  • via inheritance (class adapter)
  • via composition (object adapter)

TextShape as Adapter

TODO: add diagram when we get access to slides

Class Adapter

TODO: add diagram when we get access to slides

When should you use it?

• want to use existing class without proper interface
• want ot create reusable class that cooperates with unrelated or unforeseen classes
• want to use several existing subclasses but impractical to adapt interface by subclassing every one

Model

Consequences

Class Adapter (inheritance)

TODO: Add info for the rest of adapter (didn't show slides for that long)

Design Pattern - Facade

• a structural pattern

Intent

Provide a unified interface to a set of interfaces in a subsystem

Motivation

• most clients don’t care about details
• powerful, low-level interfaces complicate task
• e.g. a compiler

TODO: add the rest of facade info