maintaining TreeSet sort as object changes value

Question

I've got a object that defines a 'natural sort order' using Comparable<>. These are being stored in TreeSets.

Other than removing and re-adding the object, is there another way to update the sort when the members that are used to define the sort order are updated?

Answer 1

I don't think there is a out-of-the-box way to do it.

You could use an observer pattern that notifies the treeset whenever you change a value inside an element, then it removes and re-inserts it.

In this way you can implicitly keep the list sorted without caring of doing it by hand.. of course this approach will need to extend TreeSet by modifying the behaviour of insertion (setting the observed/notify mechanics on the just added item)

Answer 2

Only built in way is to remove and re-add.

Answer 3

If you really need to use a Set, then you're out of luck, I think.

I'm going to throw in a wildcard, though - if your situation is flexible enough to work with a List instead of a Set, then you can use Collections.sort() to re-sort the List on demand. This should be performant, if the List order doesn't have to be changed much.

Answer 4

As others have noted, there is no in-built way. But you can always subclass that TreeSet, with your constructor(s) of choice, and add in the required functionality:

public class UpdateableTreeSet<T extends Updateable> extends TreeSet<T> {

    // definition of updateable
    interface Updateable{ void update(Object value); }

    // constructors here
    ...

    // 'update' method; returns false if removal fails or duplicate after update
    public boolean update(T e, Object value) {
       if (remove(e)) {
           e.update(value);
           return add(e);
       } else { 
           return false;
       }
    }
}

From then on, you will have to call ((UpdateableTreeSet)mySet).update(anElement, aValue) to update the sorting value and the sorting itself. This does require you to implement an additional update() method in your data object.

Answer 5

It helps to know whether your objects will be changing by small increments or large. If each change is very small, you would do very well to put your data in a List that you keep sorted. To do this, you have to

1. binarySearch to find the index of the element
2. modify the element
3. while the element is greater than its righthand neighbor, swap it with its righthand neighbor
4. or if that didn't happen: while the element is less than its lefthand neighbor, swap it with its lefthand neighbor.

But you have to make sure no one can change the element without going through "you" to do it.

EDIT: Also! Glazed Lists has some support for just this:

http://publicobject.com/glazedlists/glazedlists-1.5.0/api/ca/odell/glazedlists/ObservableElementList.html