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

.

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() {
    return theKey.toString() + ", " + theVal.toString();
  }
}

.

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(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
interface VarBinNode {
  boolean isLeaf(); // All subclasses must implement
}

/** Leaf node */
class VarLeafNode implements VarBinNode {
  private String operand;                 // Operand value

  VarLeafNode(String val) { operand = val; }
  boolean isLeaf() { return true; }
  String value() { return operand; }
}

Inheritance (2)

/** Internal node */
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; }
  boolean isLeaf() { return false; }
  VarBinNode leftchild() { return left; }
  VarBinNode rightchild() { return right; }
  Character value() { return operator; }
}

Inheritance (3)

1 / 44 Settings

<<<>>>

Preorder traversal begins on pointer-based binary tree.

public static void traverse(VarBinNode rt) {
if (rt == null) { return; } // Nothing to visit
if (rt.isLeaf()) { // Process leaf node
Visit.VisitLeafNode(((VarLeafNode)rt).value());
}
else { // Process internal node
Visit.VisitInternalNode(((VarIntlNode)rt).value());
traverse(((VarIntlNode)rt).leftchild());
traverse(((VarIntlNode)rt).rightchild());
}
}

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 */
   interface VarBinNode {
     boolean isLeaf();
     void traverse();
   }

   /** Leaf node: Composite */
   class VarLeafNode implements VarBinNode {
     private String operand;                 // Operand value

     VarLeafNode(String val) { operand = val; }
     boolean isLeaf() { return true; }
     String value() { return operand; }

     void traverse() {
       Visit.VisitLeafNode(operand);
     }
   }

Composite (2)

   /** Internal node: Composite */
   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; }
     boolean isLeaf() { return false; }
     VarBinNode leftchild() { return left; }
     VarBinNode rightchild() { return right; }
     Character value() { return operator; }

     void traverse() {
       Visit.VisitInternalNode(operator);
       if (left != null) left.traverse();
       if (right != null) right.traverse();
     }
   }

Composite (3)

   /** Preorder traversal */
   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.