java TreeSet: comparing and equality

Question

I'd like to have list of object sorted with property 'sort_1'. But when I want to remove I'd like it to use property 'id'. The following code represents the problem.

package javaapplication1;

import java.util.TreeSet;

public class MyObj implements Comparable<MyObj> {
    public long sort_1;
    public long id;

    public MyObj(long sort, long id) {
        this.sort_1=sort;
        this.id=id;
    }

    @Override
    public int compareTo(MyObj other) {        
        int ret = Long.compare(sort_1, other.sort_1);               
        return ret;
    }    

    public String toString() {
        return id+":"+sort_1;
    }

    public static void main(String[] args) {
        TreeSet<MyObj> lst=new TreeSet<MyObj>();

                MyObj o1 = new MyObj(99,1);
        MyObj o2 = new MyObj(11,9);

        lst.add(o1);
        lst.add(o2);    

        System.out.println(lst);

                MyObj o3 = new MyObj(1234, 1);
                //remove myObje with id 1
                boolean remove=lst.remove(o3);

                System.out.println(lst);
    }

}

Output of this code is:

[9:11, 1:99]
[9:11, 1:99]

I need to have list sorted as I do a lot of additions to the list. I don't want to explicitly use any 'sort' method. What are my options ?

EDIT:

My requirement is to have: objects with 'id' as unique but there can be object's with duplicate 'sort' value.

Answer 1

Just by chance I found this out yesterday as well. This seems to be an artifact of the implementation of TreeMap (which is what TreeSet uses to store its entries).

TreeMap uses a binary search tree for storing the key/value pairs, but it only ever uses the given Comparator (or the compare function if the key class implements Comparable) to check for equality, as you can see in this code exxcerpt:

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

I'd almost call this a (not really fixable) bug since the JavaDoc of the Comparable interface explicitly says that returning 0 with the compareTo function does not have to imply "equalness":

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)).

You won't be able to store stuff in the TreeSet the way you want it to. I'd recommend using a normal HashMap or a LinkedHashMap and then just sorting the output when you need to sort it with Collections.sort.

Besides all of this, I always find it strange to implement the Comparable interface. Most things don't really have a "natural" ordering that is immediately obvious. Sometimes this can lead to strange bugs (like this one!), so I typically always sort only when I need it using custom Comparators. Java 8 makes writing those really easy as well!

Answer 2

I think the problem you're having is that you are implementing Comparable, but your implementation seems to be inconsistent with equals - and you have not implemented any equality methods. That is:

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C

In your case, when you build these three objects:

MyObj o1 = new MyObj(99,1);
MyObj o2 = new MyObj(11,9);
MyObj o3 = new MyObj(1234, 1);

You will see that o1.compareTo(o3) == -1, while o1.equals(o3) == false.

But you seem to want o1.equals(o3) == true.

Also, recognize that TreeSet.add() returns false if the object already exists in the set. This check is based on the equals() method.

To remedy this, override Object.equals() and Object.hashCode() such that they take into consideration the MyObj.id field, and continue to use the sort_1 field in the compareTo() method when they are not equal.

package javaapplication1;

import java.util.TreeSet;

public class MyObj implements Comparable<MyObj> {

    public long sort_1;
    public long id;

    public MyObj(long sort, long id) {
        this.sort_1 = sort;
        this.id = id;
    }

    @Override
    public int compareTo(MyObj other) {
        return (this.equals(other))? 0 : Long.compare(sort_1, other.sort_1);
    }

    @Override
    public boolean equals(Object obj) {
        MyObj other = (MyObj) obj;
        return this.id == other.id && this.sort_1 == other.sort_1;
    }

    @Override
    public int hashCode() {
        return (int) id;
    }


    public String toString() {
        return id + ":" + sort_1;
    }

    public static void main(String[] args) {
        TreeSet<MyObj> lst = new TreeSet<MyObj>();

        MyObj o1 = new MyObj(99L, 1L);
        MyObj o2 = new MyObj(11L, 9L);
        MyObj o3 = new MyObj(1234L, 1L);       
        MyObj o4 = new MyObj(1234L, 1L);   

        System.out.println( "Adding o1: " + lst.add(o1));
        System.out.println( "Adding o2: " + lst.add(o2));
        System.out.println( "Adding o3: " + lst.add(o3));
        System.out.println( "Adding o4: " + lst.add(o4));        

        System.out.println(lst);

        System.out.println("o1.compareTo(o3) : " + o1.compareTo(o3));
        System.out.println("o1.equals(o3) : " + o1.equals(o3));

        //remove myObje with id 1
        boolean remove = lst.remove(o3);

        System.out.println(lst);
    }

}

Output:

Adding o1: true
Adding o2: true
Adding o3: true
Adding o4: false
[9:11, 1:99, 1:1234]
o1.compareTo(o3) : -1
o1.equals(o3) : false
[9:11, 1:99]

Answer 3

Use Map<Long,MyObject> objectsByIDs; to store your data objects by id: objectsByIDs.put(id,myObjectInstance);. Then you may retrieve them from the map this wayMyObject o = objectsByIDs.get(id); And remove it from both: objectsByIDs.remove(o); lst.remove(o).

Answer 4

this is odd indeed. The documentation of TreeSet.remove() explicitly states that the method invokes equals() in order to find the argument in the Set. However, the stack trace for remove looks like this

Thread [main] (Suspended (breakpoint at line 18 in MyObj))  
    MyObj.compareTo(MyObj) line: 18 
    MyObj.compareTo(Object) line: 1 
    TreeMap<K,V>.getEntry(Object) line: not available   
    TreeMap<K,V>.remove(Object) line: not available 
    TreeSet<E>.remove(Object) line: not available   
    MyObj.main(String[]) line: 45   

Even using Comparator does not work. Seems to me like some smart developer at Sun/Oracle/openJDK thought that doing compareTo() == 0 is the same as equals(). it is not.

You're only option is either use an external data structure to check equality as was suggested, or do the loop yourself, find the item you want, and remove it.

EDIT: Now I get it. they search for the item using binary search, that is why they do compareTo().

Answer 5

Having a different logic for remove and sorting in TreeSet is almost certainly impossible, and even if it was possible it would break if you looked at it funny. Don't do that.

Trying to mess with the comparator so it does something magic is a terrible idea. Accept that there is one and only one notion of comparison the TreeSet will care about. Anything you want to do with another notion of comparison shouldn't use the TreeSet methods to do that.

What you can do instead is have a special removeId(int) method that does something like

void removeId(int id) {
  Iterator<MyObj> itr = set.iterator();
  while (itr.hasNext()) {
    if (itr.next().id == id) {
      itr.remove();
      break;
    }
  }
}