Transcript 22-The Singleton Pattern and Recursive Data

The Singleton Pattern II
Recursive Linked Structures
Recursive Data Structures
• A recursive data structure is either a basic
value, such as null, or contains a value of
the same type of data structure
• The OneWayNode class is a good example
The OneWayNode Class
public class OneWayNode{
public String value;
public OneWayNode next;
public OneWayNode(String s, OneWayNode n){
value = s;
next = n;
}
}
OneWayNode head = new OneWayNode("A", new OneWayNode("B", null));
head
“A”
“B”
Recursive Data Structures
A linked structure is either
– empty (null)
or
– contains a data value followed by another
linked structure (next) of exactly the same
form
Recursive Algorithms
When processing a linked structure
– Handle the case of empty (null)
– Do something with the data value and then
“recurse” with the linked structure (next) of
exactly the same form
– Package the algorithms as static methods in a
toolbox class (like Math)
Some Recursive Patterns:
Traversals
if the linked structure is not empty
process the value
process the rest of the linked structure
Note that there is an if statement rather than a while loop
The process just quits when the base case (the end of the
structure) is reached
Some Recursive Patterns:
Traversals
static void traverse(OneWayNode n){
if (n != null){
process(n.value)
traverse(n.next);
}
}
head
“A”
“B”
n
Some Recursive Patterns:
Traversals
static void traverse(OneWayNode n){
if (n != null){
process(n.value)
traverse(n.next);
}
}
head
“A”
“B”
n
n
Some Recursive Patterns:
Traversals
static void traverse(OneWayNode n){
if (n != null){
process(n.value)
traverse(n.next);
}
}
head
“A”
“B”
n
n
n
Some Recursive Patterns: Search
if the linked structure is empty
return false
else if the target equals the value
return true
else
return the result of searching the rest
of the linked structure
Some Recursive Patterns: Search
static boolean contains(OneWayNode n, String target){
if (n == null)
return false;
else if (target.equals(n.value))
return true;
else
return contains(n.next, target);
}
head
“A”
“B”
Some Recursive Patterns: get(i)
check preconditions
if i == 0
return the value
else
return the result of getting from the
rest of the linked structure at i - 1
Some Recursive Patterns: get(i)
static String get(OneWayNode n, int i){
if (i < 0 || i >= length(n)
throw new IllegalArgumentException(
"Index out of range");
if (i == 0)
return n.value;
else
return get(n.next, i - 1);
}
head
“A”
“B”
Some Recursive Patterns: length
if the linked structure is empty
return 0
else
return 1 + the length of the rest of the
linked structure
Some Recursive Patterns: length
static int length(OneWayNode n){
if (n == null)
return 0;
else
return 1 + length(n.next);
}
head
“A”
“B”
Some Recursive Patterns: Copy
the Structure
if the linked structure is empty
return null
else
return a new node whose value is the value
and whose next is the result of copying the
rest of the linked structure
Some Recursive Patterns: Copy
the Structure
static OneWayNode copy(OneWayNode n){
if (n == null)
return null;
else
return new OneWayNode(n.value, copy(n.next));
}
head
“A”
“B”
Recursion and Data Structures
• Recursive algorithms can be used to “back
up” through a data structure, such as a
string or a linked structure
• The calls move forward, and the real work
is done after each call returns or “backs up”
Some Recursive Patterns:
Right to Left Traversals
if the linked structure is not empty
process the rest of the linked structure
process the value
Note we just invert the order of the two statements within the if
statement
As the recursion unwinds from the end, each value is processed
Some Recursive Patterns:
Right to Left Traversals
static void backtrack(OneWayNode n){
if (n != null){
backtrack(n.next);
process(n.value);
}
}
head
“A”
“B”
n
Some Recursive Patterns:
Right to Left Traversals
static void backtrack(OneWayNode n){
if (n != null){
backtrack(n.next);
process(n.value);
}
}
head
“A”
“B”
n
n
Some Recursive Patterns:
Right to Left Traversals
static void backtrack(OneWayNode n){
if (n != null){
backtrack(n.next);
process(n.value);
}
}
head
“A”
“B”
n
n
n
Some Recursive Patterns:
Right to Left Traversals
static void backtrack(OneWayNode n){
if (n != null){
backtrack(n.next);
process(n.value);
}
}
head
“A”
“B”
n
n
Some Recursive Patterns:
Right to Left Traversals
static void backtrack(OneWayNode n){
if (n != null){
backtrack(n.next);
process(n.value);
}
}
head
“A”
“B”
n
Some Recursive Patterns: Output
in Reverse
static void reverseOutput(OneWayNode n){
if (n != null){
reverseOutput(n.next);
System.out.println(n.value);
}
}
head
“A”
“B”
Problems With Current Version
• Uses static methods for all of the
processing, not very object-oriented
OneWayNode n = new OneWayNode("Ken", null);
int myLength = NodeMethods.length(n);
• Uses null for the case of an empty
structure, so we must check for null with
if statements in every method
Problems With Current Version
• A linked structure should be able to
compute its own length
OneWayNode n = new OneWayNode("Ken", null);
int myLength = n.length();
• But a recursive implementation of this
would be pretty hard
Our View of the Current Version
A linked structure is either
– empty (null)
or
– contains a data value followed by another
linked structure (next) of exactly the same
form
A Better View
A linked structure is either
– empty (an empty node)
or
– compound (a compound node that contains a
data value and another linked structure)
From Data to Algorithms
• Two concrete classes of nodes that implement the same
interface
• The empty node’s methods handle the base cases
• The compound node’s methods handle the recursive ones
• Use polymorphism to make the choices (no explicit if
statements in the code!)
From Data to Algorithms
OneWayNode
CompoundNode
EmptyNode
The OneWayNode Interface
public interface OneWayNode{
public void traverse(Visitor v);
public void backwardTraverse(Visitor v);
public int length();
public OneWayNode copy();
public OneWayNode reverse();
public OneWayNode reverse(OneWayNode result);
}
A Visitor is an object that runs a method visit to process
each value during a traversal
Creating and Using a Visitor
public interface Visitor{
public void visit(String s);
}
Visitor v = new Visitor(){
public void visit(String s){
System.out.print(s + " ");
}
};
aOneWayNode.traverse(v);
aOneWayNode.backwardTraverse(v);
A Visitor is an object that runs a method visit to process
each value during a traversal
Node Classes, Etc.
• EmptyNode – The class of an empty node
• CompoundNode – The class of compound
nodes
• EmptyNode.THE_EMPTY_NODE – The
single instance used for any empty node
Using the New Structure
public class NodeTester{
public static void main (String[] args){
String[] strings = {"Bill", "Mary", "Sam", "Sue"};
OneWayNode n1 = EmptyNode.THE_EMPTY_NODE;
for (int i = 0; i < strings.length; i++)
n1 = new CompoundNode(strings[i], n1);
Visitor v = new Visitor(){
public void visit(String s){
System.out.print(s + " ");
}
};
System.out.println(n1.length());
System.out.print("[");
n1.traverse(v);
System.out.println("]");
System.out.print("[");
n1.backwardTraverse(v);
System.out.println("]");
OneWayNode n2 = n1.copy();
OneWayNode n3 = n1.reverse();
}
The OneWayNode Interface
public interface OneWayNode{
public void traverse(Visitor v);
public void backwardTraverse(Visitor v);
public int length();
public OneWayNode copy();
public OneWayNode reverse();
public OneWayNode reverse(OneWayNode result);
}
The EmptyNode Class
public class EmptyNode implements OneWayNode{
public void traverse(Visitor v){return;}
public void backwardTraverse(Visitor v){return;}
public int length(){return 0;}
public OneWayNode copy(){return THE_EMPTY_NODE;}
public OneWayNode reverse(){
return THE_EMPTY_NODE;
}
public OneWayNode reverse(OneWayNode result){
return THE_EMPTY_NODE;
}
static public final OneWayNode THE_EMPTY_NODE = new EmptyNode();
}
The singleton instance is created just once
The CompoundNode Class
public class CompoundNode implements OneWayNode{
private String value;
private OneWayNode next;
public CompoundNode(String value, OneWayNode next){
this.value = value;
this.next = next;
}
public CompoundNode(){
this("", EmptyNode.THE_EMPTY_NODE);
}
public void traverse(Visitor v){
v.visit(value);
next.traverse(v);
}
// NO IF STATEMENTS!
public void backwardTraverse(Visitor v){
next.backwardTraverse(v);
v.visit(value);
}
The CompoundNode Class
public int length(){
return 1 + next.length();
}
public OneWayNode copy(){
return new CompoundNode(value, next.copy());
}
public OneWayNode reverse(){
return reverse(EmptyNode.THE_EMPTY_NODE);
}
public OneWayNode reverse(OneWayNode result){
return next.reverse(new CompoundNode(value, result));
}
Recursive Objects
• Instead of using explicit if statements to handle choices,
try using polymorphism, which automatically handles them
• Divide the cases into different types of objects that obey
the same interface (avoid using null for the simple case)
• Use simple objects for the base cases and recursive objects
for the recursive ones