Re-sorting a SortedSet

[Larry Coon]

If I build a SortedSet, and later change one of the elements in
the set so that the set should sort differently, how can I get
the SortedSet to re-order itself? Here's an example to illustrate
the issue:

import java.util.*;

public class Test {
public static void main(String[] args) {
SortedSet s = new TreeSet();

// Add nodes non-alphabetically to prove that the tree
// is built correctly.
s.add(new Thing("Third"));
s.add(new Thing("Second"));
s.add(new Thing("First"));

// The tree is initially in alphabetical order.
System.out.println("Original order: " + s);

// Change last element so it should sort differently.
((Thing) s.last()).setString("Fourth");

// I want the SortedSet to be ordered correctly, reflecting
// the change above. Note that the ordering hasn't changed
// even though "Third" is now "Fourth".
System.out.println("New order: " + s);

// Constructing a new SortedSet doesn't work.
SortedSet s2 = new TreeSet(s);
System.out.println("New set: " + s2);
}
}

class Thing implements Comparable {
private String string;

public Thing(String string) {setString(string); }
public void setString(String string) { this.string = string; }
public String toString() { return string; }
public int compareTo(Object o) {
return string.compareTo(((Thing) o).toString());
}
}

 

[Thomas Weidenfeller]

If I build a SortedSet, and later change one of the elements in
the set so that the set should sort differently, how can I get
the SortedSet to re-order itself?

You can't. In fact, what your code does is to destroy the integrity of
the TreeSet. Remove the element from the set, change the key, and then
add it again.

/Thomas

 

[Eric Sosman]

If I build a SortedSet, and later change one of the elements in
the set so that the set should sort differently, how can I get
the SortedSet to re-order itself? Here's an example to illustrate
the issue:

import java.util.*;

public class Test {
public static void main(String[] args) {
SortedSet s = new TreeSet();

// Add nodes non-alphabetically to prove that the tree
// is built correctly.
s.add(new Thing("Third"));
s.add(new Thing("Second"));
s.add(new Thing("First"));

// The tree is initially in alphabetical order.
System.out.println("Original order: " + s);

// Change last element so it should sort differently.
((Thing) s.last()).setString("Fourth");

This is forbidden (or at least discouraged) by the following
passage from the Javadocs for the Set interface:

"Note: Great care must be exercised if mutable objects
are used as set elements. The behavior of a set is not
specified if the value of an object is changed in a
manner that affects equals comparisons while the object
is an element in the set. [...]"

Instead of the above, use

Thing t = (Thing)(s.last());
s.remove(t);
t.setString("Fourth");
s.add(t);

 

[Roedy Green]

If I build a SortedSet, and later change one of the elements in
the set so that the set should sort differently, how can I get
the SortedSet to re-order itself? Here's an example to illustrate
the issue:

If contract says you can't change the values of the keys, you would
have to remove the element, change the key and insert it back again.

 

[Larry Coon]

This is forbidden (or at least discouraged) by the following
passage from the Javadocs for the Set interface:

"Note: Great care must be exercised if mutable objects
are used as set elements. The behavior of a set is not
specified if the value of an object is changed in a
manner that affects equals comparisons while the object
is an element in the set. [...]"

Instead of the above, use

Thing t = (Thing)(s.last());
s.remove(t);
t.setString("Fourth");
s.add(t);

Thanks Eric & Thomas. I missed that note in the Javadoc
because I was too busy looking for a method that did
what I wanted to do to notice things which explain why
I shouldn't.

I wasn't expecting something that ran in O(log n) time,
but I was initially thinking that a re-sort of some time
would be available -- or at least that constructing a
new one from the old one would just re-insert all the
elements and accomplish what I wanted. But it makes
sense now that I've thought about your remove/add
technique, since for any tree of non-trivial size,
removing and adding a single element is bound to be
more efficient than either method I was hoping for.

Thanks again.

 

[Chris Smith]

Instead of the above, use

Thing t = (Thing)(s.last());
s.remove(t);
t.setString("Fourth");
s.add(t);

This, too, requires great caution. It only works if every piece of your
application that operates on a Thing that might be in a Set happens to
know about the Set to properly remove and reinsert it. That's
potentially a huge violation of encapsulation. Instead, it would make
sense to strongly disfavor storing mutable objects in a SortedSet at
all... and to disfavor overriding equals and hashCode in a mutable
object so that use of Set is safe.

In that case, the solution to this problem (removing the old item and
adding the new one) would be obvious.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation