Keeping mutable objects sorted in TreeSets at all times

Question

It came to my notice that a TreeSet doesn't keep the mutable objects in sorted order if object attribute values are changed later on. For example,

public class Wrap { 
    static TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>(){
        @Override
        public int compare(Student o1, Student o2) {            
            return o1.age - o2.age;
        }       
    }); 
    public static void main(String []args){
        Student s = new Student(10);
        ts.add(s); 
        ts.add(new Student(50));
        ts.add(new Student(30));
        ts.add(new Student(15));
        System.out.println(ts);
        s.age = 24;      //Here I change the age of a student in the TreeSet
        System.out.println(ts);     
    }
}
class Student{
    int age;
    Student(int age){
        this.age = age;
    }   
    @Override
    public String toString() {
        return "Student [age=" + age + "]";
    }   
}

The output is :

[Student [age=10], Student [age=15], Student [age=30], Student [age=50]]
[Student [age=24], Student [age=15], Student [age=30], Student [age=50]]

After I change the age of a particular student, and then print the TreeSet, the Set seems no longer in sorted order. Why does this happen? and how to keep it sorted always?

Answer 1

Why does this happen?

Because the set cannot monitor all its objects for changes... How would it be able to do that?!

Same problem arises for HashSets. You can't change values affecting an objects hash-code when a HashSet holds the object.

and how to keep it sorted always?

You typically remove the element from the set, modify it, and then reinsert it. In other words, change

s.age = 24;      //Here I change the age of a student in the TreeSet

to

ts.remove(s);
s.age = 24;      //Here I change the age of a student in the TreeSet
ts.add(s);

You can also use for example a list, and call Collections.sort on the list each time you've modified an object.

Answer 2

You could make use of the observer pattern. Let your TreeSet implement Observer and let your Student extend Observable. The only change you need to make is to hide the age field by encapsulation so that you have more internal control over the change.

Here's a kickoff example:

public class ObservableTreeSet<O extends Observable> extends TreeSet<O> implements Observer {

    public ObservableTreeSet(Comparator<O> comparator) {
        super(comparator);
    }

    @Override
    public boolean add(O element) {
        element.addObserver(this);
        return super.add(element);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void update(Observable element, Object arg) {
        remove(element);
        add((O) element);
    }

}

and

public class Student extends Observable {

    private int age;

    Student(int age) {
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        if (this.age != age) {
            setChanged();
        }

        this.age = age;

        if (hasChanged()) {
            notifyObservers();
        }
    }

    @Override
    public String toString() {
        return "Student [age=" + age + "]";
    }
}

Now do a new ObservableTreeSet instead of new TreeSet.

static TreeSet<Student> ts = new ObservableTreeSet<Student>(new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge() - o2.getAge();
    }
});

It's ugly at first sight, but you end up with no changes in the main code. Just do a s.setAge(24) and the TreeSet will "reorder" itself.

Answer 3

This is a generic problem with Maps and Sets. The values are inserted using the hashCode/equals/compare at the moment of insertion, and if the values on which these methods are based change, then the structures can screw up.

One way would be to remove the item from the set and re-add it after the value has been changed. Then it would be correct.