Re-sorting a SortedSet

Discussion in 'Java' started by Larry Coon, Jun 2, 2004.

  1. Larry Coon

    Larry Coon Guest

    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());
    }
    }
     
    Larry Coon, Jun 2, 2004
    #1
    1. Advertising

  2. 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
     
    Thomas Weidenfeller, Jun 2, 2004
    #2
    1. Advertising

  3. Larry Coon

    Eric Sosman Guest

    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, Jun 2, 2004
    #3
  4. Larry Coon

    Roedy Green Guest

    On Wed, 02 Jun 2004 09:49:17 -0700, Larry Coon <>
    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.
     
    Roedy Green, Jun 2, 2004
    #4
  5. Larry Coon

    Larry Coon Guest

    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.
     
    Larry Coon, Jun 2, 2004
    #5
  6. Larry Coon

    Chris Smith Guest

    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
     
    Chris Smith, Jun 5, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sasha
    Replies:
    3
    Views:
    13,289
    Adam Jenkins
    Jan 13, 2004
  2. Timo Nentwig
    Replies:
    6
    Views:
    8,892
    el goog
    Feb 26, 2005
  3. Replies:
    2
    Views:
    1,491
    James Kanze
    Jul 6, 2010
  4. Jason
    Replies:
    0
    Views:
    412
    Jason
    Oct 4, 2006
  5. John Carter

    Bug: SortedSet gives warning.

    John Carter, Mar 4, 2005, in forum: Ruby
    Replies:
    2
    Views:
    126
    John Carter
    Mar 4, 2005
Loading...

Share This Page