maintaining TreeSet sort as object changes value

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?

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.

I had a similar problem, found this thread and tucuxi's answer (thanks!) based on which I implemented my own UpdateableTreeSet. My version provides means to

• iterate over such a set,
• schedule (deferred) element updates/removals from within the loop
• without having to create a temporary copy of the set and finally
• do all the updates/removals as a bulk operation after the loop has ended.

UpdateableTreeSet hides a lot of the complexity from the user. In addition to deferred bulk updates/removals, single-element update/removal as shown by tucuxi still remains available in the class.

Update 2012-08-07: The class is available in a little GitHub repository including an introductory README with schematic sample code as well as unit tests showing how (not) to use it in more detail.

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.

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

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

I looked up this problem when I was trying to implement a kinetic scroll pane similar to the apple iPhone wheel scrolls. The items in the TreeSet are this class:

/**
 * Data object that contains a {@code DoubleExpression} bound to an item's
 * relative distance away from the current {@link ScrollPane#vvalueProperty()} or
 * {@link ScrollPane#hvalueProperty()}. Also contains the item index of the
 * scrollable content.
 */
private static final class ItemOffset implements Comparable<ItemOffset> {

    /**
     * Used for floor or ceiling searches into a navigable set. Used to find the
     * nearest {@code ItemOffset} to the current vValue or hValue of the scroll
     * pane using {@link NavigableSet#ceiling(Object)} or
     * {@link NavigableSet#floor(Object)}.
     */
    private static final ItemOffset ZERO = new ItemOffset(new SimpleDoubleProperty(0), -1);

    /**
     * The current offset of this item from the scroll vValue or hValue. This
     * offset is transformed into a real pixel length of the item distance from
     * the current scroll position.
     */
    private final DoubleExpression scrollOffset;

    /** The item index in the list of scrollable content. */
    private final int index;

    ItemOffset(DoubleExpression offset, int index) {
        this.scrollOffset = offset;
        this.index = index;
    }

    /** {@inheritDoc} */
    @Override
    public int compareTo(ItemOffset other) {
        double d1 = scrollOffset.get();
        double d2 = other.scrollOffset.get();

        if (d1 < d2) {
            return -1;
        }
        if (d1 > d2) {
            return 1;
        }

        // Double expression has yet to be bound
        // If we don't compare by index we will
        // have a lot of values ejected from the
        // navigable set since they will be equal.
        return Integer.compare(index, other.index);
    }
    
    /** {@inheritDoc} */
    @Override
    public String toString() {
        return index + "=" + String.format("%#.4f", scrollOffset.get());
    }
}

The DoubleExpression may take a moment to be bound in a runLater task of the JavaFX platform, this is why the index is included in this wrapper class.

Since the scrollOffset is always changing based on the user scroll position on the scroll wheel, we need a way to update. Usually the order is always the same, since the offset is relative to the item index position. The index never changes, but the offset could be negative or positive depending on the items relative distance from the current vValue or hValue property of the ScrollPane.

To update on demand only when needed, simply follow the guidance of the above answer by Tucuxi.

ItemOffset first = verticalOffsets.first();
verticalOffsets.remove(first);
verticalOffsets.add(first);

where verticalOffsets is a TreeSet<ItemOffset>. If you do a print out of the set each time this update snippet is called, you will see that it is updated.

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)