Transcript presentation source

Linear Recursive Data Structures Using
Object-Oriented State Patterns
or
Just how smart is a a null node anyway?
Stephen Wong, Oberlin College
Dung “Zung” Nguyen, Pepperdine University
Squares and Rectangles
Is a square a rectangle?
Yes…No…..Aieeeeeee!…..
Two states of a rectangle?
Square
Non-Square
Recursive Definition of Linear
Structures (Lists)
What is a LRS/list?
Two different types of LRS’s:
Empty
Non-Empty
Are the different types really the same?
Do you care?
Abstraction, a la Matisse
A Process through which superfluous details are
systematically removed to reveal the intrinsic nature.
Recursive Definition of Linear
Structures (Lists)
Abstract the structure!
For non-empty LRS:
The data or “First” (= “car”)
The tail or “Rest” (= “cdr”), which is a LRS!
Abstract the behavior!
Separate the Invariant vs. Variant Behaviors
Get/Set methods for First and Rest.
State change methods (insertAsFirst, remove).
Other variant methods (queries, display, etc.)
The Power of Abstraction
Closest match between the reality of the
situation and the software model.
Helps control and understand the complexity
of a large system.
Creates robust, flexible and extensible code
State Diagram for a LRS
Empty List
Add
Item
Non-Empty List
Remove
Item
Rectangles and Lists?
Systems that change states dynamically.
Dynamic reclassification: an object that
behaves differently in different states as if it
changes classes.
Design solution for languages that do not
support this feature?
State Design Pattern
Encapsulate states as concrete classes.
Abstract them into an abstract class.
The system contains a reference to an
abstract state class, which can be an of the
concrete state classes dynamically.
How can we express this?
Unified Modeling Language
A way of focusing on the the structure
of a system of objects.
Separates the interfaces from the
implementations.
Shows classes, methods, and attributes.
Shows inheritance relationships and
associations.
UML Diagram of the
State Design Pattern
Invariant LRS Behaviors
Get/Set First
Get/Set Rest
InsertAsFirst
RemoveFirst
Intelligent States
The LRS’s user doesn’t necessarily care
which state the LRS is in.
Each case determines its own course.
No conditional statements are necessary.
The null (empty) case can handle itself.
Emptiness has behavior and intelligence!
Object-Oriented Data Structures
Represent the
pure behavior of the structure of the data,
independent of the data itself.
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. Stay tuned!!
Venn Diagram of Rectangles?
Non Square
Square
Nahhh….
The Yin-Yang of Rectangles
Square
Non Square
Just how smart is a null node?
Just because you don’t have any information
doesn’t mean you aren’t smart enough to
take care of yourself!