Transcript presentation source

Patterns for Decoupling Data
Structures and Algorithms
or
How visitors can help you grow!
Stephen Wong, Oberlin College
Dung “Zung” Nguyen, Pepperdine University
Where were we anyway?
Abstracting the structure and behavior of a
linear recursive structure (“LRS” or “list”):
Empty vs Non-Empty States
State Transitions
State Design Pattern
Single LRS class that changes states.
Intelligent states that can handle themselves.
First, the invariant behaviors…
UML Diagram of a LRS
The public list
The non-empty
state
The abstract
state
The empty
state
Object-Oriented Data Structures
Represent the
pure behavior of the structure of the data,
independent of the data itself.
Let’s take a look when we add the variant behaviors…
UML Diagram of a LRS
Variant behaviors
declared and
accessed here
Passed through
this interface
Or here
Executed here
What’s wrong with this picture?
Why are the variant behaviors coded together
with the invariant behaviors?
But aren’t the variant behaviors still the
domain of the data structure object?
But who can predict future behavioral needs?
We need extensibility.
We need to de-couple the variant algorithms
from the data structure. Now let’s fix it!
The Issue of Extensibility
Modern software engineering is driven by a
need to handle change:
Code will be modified many times.
New features will be added on short intervals.
The complexity of modern system demands
adherence to strict protocols.
Proper abstraction is crucial.
Need public interfaces that allow for expansion.
Examples of Extensible Programs
Netscape’s plug-ins.
MS Office’s add-ins and MS Active-X.
Dynamic Link Libraries (DLL’s).
I/O drivers
All of these can handle multiple extensions...
But none of these can handle multiple hosts
with different needs….
Why shouldn’t they??
Designing for the Unknown
Identify the variant and invariant behaviors.
Encapsulate the invariant behaviors into a
class.
Add hooks to this class to define
communication protocols to other classes.
Encapsulate the variant behaviors into classes
that comply with the above protocols.
The Visitor Design Pattern
Visitors
Encapsulate the variant behaviors.
All conform to a set invocation interface.
Provide different methods for different hosts.
Hosts
Provide a consistent “hook” for visitors.
Each different host calls only its desired method
in the visitor.
Framework Control
Algorithm handed to the data structure rather
than the other way around.
The data structure incapsulates the invariant
behaviors and the algorithms are variant
behaviors being added to it.
Visitors with a Common Interface
Fixed visitor interface
presents methods for
each host.
Conforming algorithms
Abstracted Hosts
User class calls for variant behavior in its abstract host:
result = _host.visit(visitor, param);
result = visitor.method1(this, param);
result = visitor.method2(this, param);
Each host calls its desired method
result = visitor.method3(this, param);
Binary Tree Structure
Using the State Pattern
Invariant behaviors plus a hook
for the variant behaviors.
Binary Tree Structure Visitors
What Visitors Bring
Algorithms encapsulated separately from the
data structure.
Invariant behaviors in the data structure.
Variant behaviors in the visitors.
Unlimited future capabilities.
Multiple host capable: Can handle statedependent algorithms.
Recursive and non-recursive capable.
There’s more to come...
Recursive indexing schemes for arbitrarily
branched tree structures.
Building a binary search tree using visitors.
But not today…...
Growing with Visitors
Bring on the visitors,
for they bring abilities
never before imagined.