Java: TreeSet compareTo method triggered at first add call

Question

The following java code utilizes a TreeSet to collect objects derived from the class MyClass which doesn't implement the Comparable interface nor have a compareTo() method to perform the comparison between objects. By not providing that comparison method, we expect the raising of an exception during the addition of the second object, not the first one as soon as comparison is ambiguous with only one object.

JDK: 1.7

Question: Why the compareTo() is triggered on the first add tree.add(m1) ?

Code:

package javaapplication1;

import java.util.*;

class MyClass
{
    int _x;
    MyClass(int x)
    {
        _x = x;
    }
}

public class JavaApplication1 
{
     public static void main(String[] args) 
     {
         MyClass m1 = new MyClass(5);
         MyClass m2 = new MyClass(3);

         TreeSet tree = new TreeSet();
         tree.add(m1);
         tree.add(m2);
     }
}

Answer 1

TreeSet is implemented on top of TreeMap. So TreeSet.add() calls to TreeMap.put(Object, Object) method. Please see the below:

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); //this is the culprit

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
    ……………
    ……………
    ……………
}

Now as the root is null so the flow will go inside the if (t == null) { hence calls compare(key, key).

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

As inside the compare method it is typecasting k1, k2 Comparable and your class does not implement Comparable hence the exception:

Exception in thread "main" java.lang.ClassCastException: .

This code is as per JDK 1.7.

Answer 2

This is the actual code from TreeMap's put method. You will get a ClassCastException the first time you try to add because your key is not Comparable. Please note that TreeSet uses a TreeMap internally and anything you put in a TreeSet will be a key (value is not used).

    Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            // ^^ -- ClassCastException here
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }