Java Comparator Interface

Question

I have a misunderstanding about Comparator interface and its method compare here is the following code and i am wondering why compare method return -33 i believe that it should return 33

import java.util.*;
public class Sorted implements Comparable<Sorted>, Comparator<Sorted> {
private int num;
private String text;

Sorted(int n, String t) {
    this.num = n;
    this.text = t;
}

public String toString() {
    return "" + num;
}

public int compareTo(Sorted s) {
    return text.compareTo(s.text);
}

public int compare(Sorted s1, Sorted s2) {
    System.out.println(s1.num-s2.num); // return -33
    return s1.num - s2.num;
}
public static void main(String[] args) {
    Sorted s1 = new Sorted(88, "a");
    Sorted s2 = new Sorted(55, "b");
    TreeSet<Sorted> t1 = new TreeSet<>();
    t1.add(s1); t1.add(s2);
    TreeSet<Sorted> t2 = new TreeSet<>(s1);
    t2.add(s1); t2.add(s2);
    System.out.println(t1 + " " + t2);
    System.out.println(s1.num-s2.num); // prints 33
} }

Answer 1

You probably know that if a-b=c then b-a=-c.

What happens here is very similar. You seem to have assumed that TreeSet is calls the compare method like this:

comparator.compare(s1, s2)

(Note that I used s1 and s2 for demonstrative purposes. They are obviously not in scope in TreeSet. s1 is the same instance as your s1 and s2 is the same instance as your s2`.)

But it could call compare like this as well:

comparator.compare(s2, s1)

couldn't it?

If it called it the second way, then the result of -33 is to be expected.

EDIT:

I looked into the source code for TreeSet.add and found that it calls TreeMap.put with the item you are adding as the key. If you look further into TreeMap.put, you will find:

Comparator<? super K> cpr = comparator;
if (cpr != null) {
    do {
        parent = t;
        cmp = cpr.compare(key, t.key); // <--- "key" is the key passed into this method
                                       // "t" is an element that is already in the map
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);
    } while (t != null);
}

This shows that TreeSet indeed calls compare the way I described.

EDIT:

As Holger said in the comments, you should not implement Comparator by subtracting the two integers. Instead, you should use Integer.compare:

return Integer.compare(s1.num, s2.num);

In fact, there is no need to implement Comparator at all, you can pass in a Comparator.comparingInt(s -> s.num) when you create the TreeMap:

TreeSet<Sorted> t1 = new TreeSet<>(Comparator.comparingInt(s -> s.num));

Answer 2

The s1 and s2 in compare(Sorted s1, Sorted s2) are local variable definitions, you must not confuse them with the definitions in main(). It is not defined (algorithmically, only by the implementation) how TreeSet compares the two elements.

compare(s1, s2) //yields 33
compare(s2, s1) //yields -33

---

TreeSet internally uses a TreeMap. put calls compare in several places, usually with the element you put into the TreeSet as first element. Therefore put(s2)will call compare(s2, s1). See Code excerpt below:

public V put(K key, V value) {    
        Entry<K,V> t = root;    
        if (t == null) {
            compare(key, key); // type (and possibly null) check       
            root = new Entry<>(key, value, null);  
            size = 1;
            modCount++;    
            return null;    
        }    
        int cmp;    
        Entry<K,V> parent;    
        // split comparator and comparable paths    
        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();    
            @SuppressWarnings("unchecked")    
                Comparable<? super K> k = (Comparable<? super K>) key;   
            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);    
        }    
        Entry<K,V> e = new Entry<>(key, value, parent);    
        if (cmp < 0)
                parent.left = e;    
        else    
            parent.right = e;    
        fixAfterInsertion(e);    
        size++;    
        modCount++;

        return null;
    }

Other implementations or methods might have different behaviour.