4.3. Design Patterns¶
4.3.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.3.2. Comparison (2)¶
Fundamental issue: The key is a property of the context, NOT a property of the record.
4.3.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.3.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.3.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.3.6. Binary Tree Implementation (1)¶
“Simple” node model.
4.3.7. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
4.3.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.3.9. Inheritance (3)¶
4.3.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.3.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.3.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(); }
}
