4.2. Design Patterns¶
4.2.1. Comparison (1)¶
How do we generalize the concept of comparison?
“<” is not good enough. String < String won’t give you what you want.
Need a general way to get the key out of a record
Define a method record.key()?
[Note for C++ users: Operator overloading is effectively the same thing.]
That is not good enough. What if we want to search on different key fields?
4.2.2. Comparison (2)¶
Fundamental issue: The key is a property of the context, NOT a property of the record.
4.2.3. KVpair: A Truly General Solution¶
// KVPair class definition
public class KVPair implements Comparable {
Comparable theKey;
Object theVal;
KVPair(Comparable k, Object v) { theKey = k; theVal = v; }
public int compareTo(Object it) throws ClassCastException {
if (it instanceof KVPair) // Compare two KVPair objects
return theKey.compareTo(((KVPair)it).key());
else if (it instanceof Comparable) // Compare against a key value
return theKey.compareTo(it);
else
throw new ClassCastException("Something comparable is expected.");
}
public Comparable key() { return theKey; }
public Object value() { return theVal; }
public String toString() {
String s = "(";
if (theKey != null) { s += theKey.toString(); }
else { s += "null"; }
s += ", ";
if (theVal != null) { s += theVal.toString(); }
else { s += "null"; }
s += ")";
return s;
}
}
4.2.4. KVpair: Generics¶
// KVPair class definition
public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> {
K theKey;
E theVal;
KVPair(K k, E v) { theKey = k; theVal = v; }
// Compare KVPairs
public int compareTo(KVPair<K,E> it) {
return theKey.compareTo(it.key());
}
// Compare against a key
public int compareTo(K it) {
return theKey.compareTo(it);
}
public K key() { return theKey; }
public E value() { return theVal; }
public String toString() {
String s = "(";
if (theKey != null) { s += theKey.toString(); }
else { s += "null"; }
s += ", ";
if (theVal != null) { s += theVal.toString(); }
else { s += "null"; }
s += ")";
return s;
}
}
4.2.5. Using the KVpair (1)¶
static void inssort(int[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j] < A[j-1]); j--)
swap(A, j, j-1);
}
What is being compared?
What if we want to find the record that has a given key?
4.2.6. Binary Tree Implementation (1)¶
“Simple” node model.
4.2.7. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
4.2.8. Inheritance (1)¶
// Base class for expression tree nodes
public interface VarBinNode {
public boolean isLeaf(); // All subclasses must implement
}
/** Leaf node */
public class VarLeafNode implements VarBinNode {
private String operand; // Operand value
VarLeafNode(String val) { operand = val; }
public boolean isLeaf() { return true; }
public String value() { return operand; }
}
// Internal node
public class VarIntlNode implements VarBinNode {
private VarBinNode left; // Left child
private VarBinNode right; // Right child
private Character operator; // Operator value
VarIntlNode(Character op, VarBinNode l, VarBinNode r)
{ operator = op; left = l; right = r; }
public boolean isLeaf() { return false; }
public VarBinNode leftchild() { return left; }
public VarBinNode rightchild() { return right; }
public Character value() { return operator; }
}
4.2.9. Inheritance (3)¶
4.2.10. Design Patterns¶
Design patterns capture reusable pieces of design wisdom.
Goals:
Quickly communicate design wisdom to new designers
Give a shared vocabulary to designers
4.2.11. Composite (1)¶
/** Base class: Composite */
public interface VarBinNode {
public boolean isLeaf();
public void traverse();
}
/** Leaf node: Composite */
public class VarLeafNode implements VarBinNode {
private String operand; // Operand value
VarLeafNode(String val) { operand = val; }
public boolean isLeaf() { return true; }
public String value() { return operand; }
public void traverse() {
Visit.VisitLeafNode(operand);
}
}
4.2.12. Composite (2)¶
/** Internal node: Composite */
public class VarIntlNode implements VarBinNode { // Internal node
private VarBinNode left; // Left child
private VarBinNode right; // Right child
private Character operator; // Operator value
VarIntlNode(Character op,
VarBinNode l, VarBinNode r)
{ operator = op; left = l; right = r; }
public boolean isLeaf() { return false; }
public VarBinNode leftchild() { return left; }
public VarBinNode rightchild() { return right; }
public Character value() { return operator; }
public void traverse() {
Visit.VisitInternalNode(operator);
if (left != null) { left.traverse(); }
if (right != null) { right.traverse(); }
}
}
/** Preorder traversal */
public static void traverse(VarBinNode rt) {
if (rt != null) { rt.traverse(); }
}
4.2.13. Flyweight¶
The Problem:
Composite Design does not work well with NULL pointers.
(Do you understand why?)
Need to make an empty node object
Empty nodes carry no information (aside from noting the fact that they are empty). Having a lot of them wastes a lot of space.
Solution:
Make a Flyweight
This is a single, specific, recognizeable object pointed to by all places that need to reference an empty node.
Flyweights may never carry state information (since there is only one).
