Register

DSA Coursenotes

Chapter 4 Week 5

Show Source | | About « 4.3. Over-Constrained Code :: Contents :: 5.1. Heaps »

4.4. Comparison¶

4.4.1. Comparison¶

4.4.1.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.4.1.2. Comparison (2)¶

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

4.4.1.3. KVpair¶

This is a truly general way to solve the problem.

// 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.4.1.4. .¶

.

4.4.1.5. 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.4.1.6. .¶

.

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

Contact Us || Privacy | | License « 4.3. Over-Constrained Code :: Contents :: 5.1. Heaps »