Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Re-sorting a SortedSet (http://www.velocityreviews.com/forums/t134042-re-sorting-a-sortedset.html)

Larry Coon 06-02-2004 04:49 PM

Re-sorting a SortedSet
 
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 06-02-2004 05:16 PM

Re: Re-sorting a SortedSet
 
Larry Coon wrote:
> 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 06-02-2004 05:29 PM

Re: Re-sorting a SortedSet
 
Larry Coon wrote:
> 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);

--
Eric.Sosman@sun.com


Roedy Green 06-02-2004 07:15 PM

Re: Re-sorting a SortedSet
 
On Wed, 02 Jun 2004 09:49:17 -0700, Larry Coon <lcnospam@assist.org>
wrote or quoted :

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

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Larry Coon 06-02-2004 07:20 PM

Re: Re-sorting a SortedSet
 
Eric Sosman wrote:

> 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 06-05-2004 12:48 AM

Re: Re-sorting a SortedSet
 
Eric Sosman wrote:
> 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


All times are GMT. The time now is 04:33 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.