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?

Solution 1

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.

Solution 2

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.

Solution 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.

Solution 4

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

Solution 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

View more solutions

Comments

[b3s1m0t7]

Is this just morbid curiosity, or are you looking for a specific benefit, say in performance or code simplicity?

[Stevko]

I was looking for a simple noninvasive way to maintain the sort order of a collection as events update the objects within it. Altering the membership has side effects on other consumers of the collection. IMO, triggering a resort of an element seems like basic functionality for a sorted collection.

[mike]

GUIs have the same problem, and MVC is the solution. The GUI which corresponds to your TreeSet calls update in periodic intervals, or the controller (observer pattern) gets triggered by the model if a value changes

[Stevko]

The fingered by architecture pretty accurately. The TreeSet is my model of DOTs listening to a websocket jms events which then relay the Model updates thru the presenter/controller layer to view widgets.

[tucuxi]

Not much of an advantage to doing that - Set guarantees fast lookup, insertion and removal, while a List would require using Collections.binarySearch first to locate the element. It is better to stick to removal and re-insertion.

[skaffman]

I realise that, which is why I said "if your situation is flexible enough". The performance requirements may be loose enough to permit a List to be practical.

[Kevin Bourrillion]

@tucuxi binary search in a List is O(log n). Lookup in a TreeSet? Also O(log n).

[Michael Borgwardt]

I don't think that will work. If the element's value changes in a way that affects the sort order, it's quite likely that you will be unable to find it in the tree or remove it.

[tucuxi]

@Kevin but you have to go through the motions of implementing versions of add(), remove() and contains() that do binary searches internally. In essence, you are reimplementing TreeSet with a sorted list inside. That is why I wrote that removal&reinsertion seemed easier. Not because of performance, but because of coding time.

[Stevko]

I liked this idea if the collection could be sorted in place rather than create a new instance.

[tucuxi]

I like the idea - it would just imply placing the "deferred-update" array inside the UpdateableTreeSet, and then calling "do-deferred-updates" to first remove all of the updates, and then re-insert them.

[kriegaex]

As my code example implies, this is what I have done. It is not just an idea, it is a real implementation. Have you followed the link to the source code and also checked out other files in the project to see how the class is used in more complicated cases?

[tucuxi]

No need - the idea is clear enough, and although your explanation is somewhat over-lengthy, I up-voted it as useful.

[kriegaex]

I have reacted on your comment that the posting was over-lengthy and shortened it dramatically. I also removed the sample code snippet. Instead there is a pointer to a dedicated Git repository with the full code now for further reference. Thanks for the feedback.

[CorayThan]

I think if you will often be modifying the objects, but there aren't very many and their order doesn't change very much, it's easier to implement a wrapper that performs a lot of Collections.sort. At least for my use case this seems a lot easier than (somehow) remembering to remove the object from the TreeSet, then modify it, then readd it every time.

[aioobe]

@KevinBourrillion, also, insertion is still O(n) in a list, unless you use a linked list, but then lookup is no longer O(log n).

[Damien MIRAS]

@MichaelBorgwardt there is no reason it will not work, this is the exact same solution of the best answer BUT with an additionnal observer pattern. by the way this is also implemented like that in many library in different languages, for exemple QT c++ lib use a sorted list that observes a model

[Michael Borgwardt]

@DamienMIRAS: No, this is not the same solution, and as stated it most definitely will not work. The accepted answer first removes the element, then changes its value, then reinserts it. That works. An Observer will not work because if you notify it after changing the value, you have already corrupted the internal state of the TreeSet, and if you notify it before changing the value, it can't do anything yet. It only works if the Observer ends up actually changing the value like in the accepted answer, but then it's not really an Observer (and won't work with multiple ones).

[Damien MIRAS]

Damn yes you are true ! I missed that "little detail" ^^ thanks. It could work by encapsulating the internal value : onChange the observable notify the Set, then the instance is removed from the set, then the field of the instance is update and finaly added back to the set. But I find this is an overkill, it could be fun to have a try on a github.