3.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?

Comparison (2)

Fundamental issue: The key is a property of the context, NOT a property of the record.

KVpair

This is a truly general way to solve the problem.

// 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;
  }
}

.

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;
  }
}

.

Using the KVpair (1)

static <T extends Comparable<T>> void inssort(T[] A) {
  for (int i=1; i<A.length; i++) // Insert i'th record
    for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
      Swap.swap(A, j, j-1);
}

What is being compared?

What if we want to find the record that has a given key?

Binary Tree Implementation (1)

“Simple” node model.

Binary Tree Implementation (2)

Internal nodes can be different from leaf nodes.

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; }
}

Inheritance (2)

// 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; }
}

Inheritance (3)

Settings

Saving...

Server Error
Resubmit

Design Patterns

Design patterns capture reusable pieces of design wisdom.
Goals:
- Quickly communicate design wisdom to new designers
- Give a shared vocabulary to designers

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);
     }
   }

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(); }
     }
   }

Composite (3)

   /** Preorder traversal */
   public static void traverse(VarBinNode rt) {
     if (rt != null) { rt.traverse(); }
   }

Space Overhead (1)

From the Full Binary Tree Theorem:
- Half of the pointers are null.
If leaves store only data, then overhead depends on whether this is full tree.
Ex: Full tree, all nodes the same, with two pointers to children and one to element
- Total space required is \((3p + d)n\)
- Overhead: \(3pn\)
- If \(p = d\), this means \(3p/(3p + d) = 3/4\) overhead.

Space Overhead (2)

Eliminate pointers from the leaf nodes

\[\frac{n/2(2p)}{n/2(2p) + dn} = \frac{p}{p + d}\]

This is 1/2 if \(p = d\).

\((2p)/(2p + d)\) if data only at leaves \(\Rightarrow\) 2/3 overhead.

Note that some method is needed to distinguish leaves from internal nodes.