Comparable; generic binary search tree

ed Lesson

Table of contents

• Comparable interface
• Implementing Comparable

Comparable interface

IntSearchTree relies on maintaining the binary search tree invariant to determine the location of a given element. However, the < (less than) and > (greater than) operators only work with numeric types such as int and double. In this lesson, we’ll see how we can generalize this idea to any data type with the help of the Comparable interface, and also write some of our own classes that implement the Comparable interface.

The Comparable interface is Java’s standard approach for defining a natural comparison order for any implementing class. The interface requires classes to implement a single method, compareTo.

public interface Comparable<T> {
    public int compareTo(T o);
}

In contrast to other interfaces we’ve seen such as List, Set, Queue, and Map, the Comparable interface is used in a different way than the usual client-implementer relationship. The List interface, for example, is typically used by clients that want to store data in a list.

The Comparable interface, on the other hand, is designed to help data structure and algorithm implementers. For example, we can generalize IntSearchTree as a SearchTree class that only works with certain Comparable data types.

Implementer

public class SearchTree<T extends Comparable<T>> {
    // pre : Binary search tree invariant.
    // post: Returns true if the value is in this tree, false otherwise.
    public boolean contains(T value) {
        return contains(overallRoot, value);
    }

    private boolean contains(TreeNode root, T value) {
        if (root == null) {
            return false;
        }
        int cmp = value.compareTo(root.data);
        if (cmp == 0) { // value == root.data
            return true;
        } else if (cmp < 0) { // value < root.data
            return contains(root.left, value);
        } else { // value > root.data
            return contains(root.right, value);
        }
    }

    ...
}

T extends Comparable<T> is a bit of generic syntax that reads, “some data type T that can be compared against other instances of T”. This idea is more generally known as delegation. For example, instead of handling the logic for comparing strings inside of the SearchTree class, we ask the String class to define the relationship between any two strings.

Implementer

public class String implements Comparable<String> {
    ...
}

This way, the SearchTree class is generic: it doesn’t depend on any particular implementation details of String, and it supports any user-defined class as long as the class implements Comparable. Delegation of comparison allows the implementer of the String class to communicate information back to the SearchTree implementer.

Implementing Comparable

Suppose we have a Dog class, where each Dog has a name and a size.

Implementer

public class Dog {
    private String name;
    private int size;

    ...
}

Let’s say that we want to compare dogs by their size field so that smaller dogs come before larger dogs. There are a few steps to follow for Dog to implement Comparable.

1. Declare the Comparable relationship to Java in the class header by implementing Comparable<Dog>.
2. Implement the interface by adding a public int compareTo(Dog other) method.

The compareTo method returns a negative integer if this < other, zero if this == other, or a positive integer if this > other. There’s a nice symmetry between the comparison operators and the compareTo method expectations.

• If this < other, then this.compareTo(other) < 0.
• If this == other, then this.compareTo(other) == 0.
• If this > other, then this.compareTo(other) > 0.

Implementer

public int compareTo(Dog other) {
    if (this.size < other.size) {
        return -1;
    } else if (this.size == other.size) {
        return 0;
    } else { // this.size > other.size
        return 1;
    }
}

The Java developers anticipated programmers would need to write classes that implemented Comparable, so they provided helper methods for many commonly-used data types including Integer, Double, and String. However, we can’t call this.size.compareTo(other.size) directly since size is an int primitive value, not an Integer object. To get around this unfortunate design decision, the Integer and Double classes provide a special static method compare that returns the compareTo result between two numbers, x and y.

Implementer

public int compareTo(Dog other) {
    return Integer.compare(this.size, other.size);
}

public int compareTo(Dog other) {
    return -Integer.compare(this.size, other.size);
}

Oftentimes, we’ll want to introduce more complex behavior for compareTo. If the two dogs are equal in size, then we want to compare on their name fields.

Implementer

public int compareTo(Dog other) {
    int cmp = Integer.compare(this.size, other.size);
    if (cmp == 0) {
        cmp = this.name.compareTo(other.name);
    }
    return cmp;
}