Alternative to TreeSet?

Discussion in 'Java' started by laredotornado@zipmail.com, May 6, 2013.

  1. Guest

    Hi,

    We're using Java 6. Is there a java.util.Set data structure that can return a sorted list of elements and can contain two elements even if compareTo returns 0 against those two elements but calling equals against the two elements returns false? TreeSet doesn't do the job.

    In our example, we have products with an order ID column, so two products could have the same order ID but may not be equal. We would like to sort the products based on this order ID, however.

    Thanks for any advice, - Dave
     
    , May 6, 2013
    #1
    1. Advertising

  2. Eric Sosman Guest

    On 5/6/2013 11:10 AM, wrote:
    > Hi,
    >
    > We're using Java 6. Is there a java.util.Set data structure that can return a sorted list of elements and can contain two elements even if compareTo returns 0 against those two elements but calling equals against the two elements returns false? TreeSet doesn't do the job.


    None that I know of.

    > In our example, we have products with an order ID column, so two products could have the same order ID but may not be equal. We would like to sort the products based on this order ID, however.


    Sounds like the compareTo() method should take the products' other
    attributes into account, and not use the order ID alone. If compareTo()
    is not easily changed (for example, if some other piece of the system
    relies on its ID-only sensitivity), use a TreeSet with a custom
    Comparator.

    --
    Eric Sosman
    d
     
    Eric Sosman, May 6, 2013
    #2
    1. Advertising

  3. Daniel Pitts Guest

    On 5/6/13 8:10 AM, wrote:
    > Hi,
    >
    > We're using Java 6. Is there a java.util.Set data structure that can return a sorted list of elements and can contain two elements even if compareTo returns 0 against those two elements but calling equals against the two elements returns false? TreeSet doesn't do the job.
    >
    > In our example, we have products with an order ID column, so two products could have the same order ID but may not be equal. We would like to sort the products based on this order ID, however.
    >
    > Thanks for any advice, - Dave
    >

    It sounds like you don't want a set, but a sorted bag. There may be
    something in Apache Commons to solve this problem for you. Depending on
    the size of the data set, I'd probably just use an ArrayList and call
    Collections.sort().

    Especially if you expect to change the ordering.
     
    Daniel Pitts, May 6, 2013
    #3
  4. Lew Guest

    > laredotornado wrote:
    >> We're using Java 6. Is there a java.util.Set data structure that can return a sorted list of elements
    >> and can contain two elements even if compareTo returns 0 against those two elements but calling
    >> equals against the two elements returns false? TreeSet doesn't do the job.


    Well, duh. I mean what did you expect, given the documentation?

    http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
    "Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be
    consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator
    for a precise definition of consistent with equals.) This is so because the Set interface is defined in
    terms of the equals operation, but a TreeSet instance performs all element comparisons using its
    compareTo (or compare) method, so two elements that are deemed equal by this method are, from the
    standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent
    with equals; it just fails to obey the general contract of the Set interface."

    Since they mention "an explicit comparator":

    http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html
    "Caution should be exercised when using a comparator capable of imposing an ordering inconsistent
    with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit
    comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is
    inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted
    set (or sorted map) will violate the general contract for set (or map), which is defined in terms of
    equals."

    --
    Lew
     
    Lew, May 6, 2013
    #4
  5. On 05/06/2013 12:19 PM, Eric Sosman wrote:
    > On 5/6/2013 11:10 AM, wrote:
    >> Hi,
    >>
    >> We're using Java 6. Is there a java.util.Set data structure that can
    >> return a sorted list of elements and can contain two elements even if
    >> compareTo returns 0 against those two elements but calling equals
    >> against the two elements returns false? TreeSet doesn't do the job.

    >
    > None that I know of.
    >
    >> In our example, we have products with an order ID column, so two
    >> products could have the same order ID but may not be equal. We would
    >> like to sort the products based on this order ID, however.

    >
    > Sounds like the compareTo() method should take the products' other
    > attributes into account, and not use the order ID alone. If compareTo()
    > is not easily changed (for example, if some other piece of the system
    > relies on its ID-only sensitivity), use a TreeSet with a custom
    > Comparator.
    >

    Bang on.

    AHS
     
    Arved Sandstrom, May 6, 2013
    #5
  6. On 06.05.2013 17:25, Daniel Pitts wrote:
    > On 5/6/13 8:10 AM, wrote:


    >> We're using Java 6. Is there a java.util.Set data structure that can
    >> return a sorted list of elements and can contain two elements even if
    >> compareTo returns 0 against those two elements but calling equals
    >> against the two elements returns false? TreeSet doesn't do the job.
    >>
    >> In our example, we have products with an order ID column, so two
    >> products could have the same order ID but may not be equal. We would
    >> like to sort the products based on this order ID, however.


    > It sounds like you don't want a set, but a sorted bag. There may be
    > something in Apache Commons to solve this problem for you. Depending on
    > the size of the data set, I'd probably just use an ArrayList and call
    > Collections.sort().


    And there are methods for binary search which will help with finding
    element positions efficiently, e.g.
    http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#binarySearch(java.lang.Object[],
    int, int, java.lang.Object)

    I am not entirely sure though whether OP really wants a multiset (bag)
    or just a custom ordering which takes more fields into account. It
    depends on the operations executed on the collection.

    Kind regards

    robert

    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
     
    Robert Klemme, May 7, 2013
    #6
  7. Roedy Green Guest

    On Mon, 6 May 2013 08:10:48 -0700 (PDT),
    wrote, quoted or indirectly quoted someone who said :

    >TreeSet doesn't do the job.


    Yet another approach is to extract some fields from your objects and
    create a new object type for which you can safely redefine your
    natural comparisons. In that object can be a reference to the original
    object.
    --
    Roedy Green Canadian Mind Products http://mindprod.com
    Nothing is so good as it seems beforehand.
    ~ George Eliot (born: 1819-11-22 died: 1880-12-22 at age: 61) (Mary Ann Evans)
     
    Roedy Green, May 7, 2013
    #7
  8. Sven Köhler Guest

    On 05/06/2013 06:10 PM, wrote:
    > Hi,
    >
    > We're using Java 6. Is there a java.util.Set data structure that can
    > return a sorted list of elements and can contain two elements even if
    > compareTo returns 0 against those two elements but calling equals
    > against the two elements returns false? TreeSet doesn't do the job.


    Implement a Comparator and pass it to the TreeSet. The Comparator can
    sort objects for which equals returns false in any arbitrary (but
    deterministic) order.

    > In our example, we have products with an order ID column, so two
    > products could have the same order ID but may not be equal. We would
    > like to sort the products based on this order ID, however.


    The Comparator would sort the products based on their ID first - and if
    the IDs are equal it would sort them based on other attributes.

    Is that what you want?



    Regards,
    Sven
     
    Sven Köhler, May 7, 2013
    #8
    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. Sandip Chitale

    Re: JList customized with TreeSet

    Sandip Chitale, Aug 23, 2003, in forum: Java
    Replies:
    0
    Views:
    687
    Sandip Chitale
    Aug 23, 2003
  2. Rhino

    TreeSet size() Problem

    Rhino, Feb 21, 2005, in forum: Java
    Replies:
    2
    Views:
    678
    Anton Spaans
    Feb 22, 2005
  3. Rhino
    Replies:
    17
    Views:
    1,094
    Rhino
    Feb 24, 2005
  4. Stefan Ram

    Re: correct use of TreeSet

    Stefan Ram, Feb 26, 2006, in forum: Java
    Replies:
    2
    Views:
    436
    Stefan Schulz
    Feb 26, 2006
  5. jacksu

    TreeSet bug?

    jacksu, Jun 15, 2006, in forum: Java
    Replies:
    2
    Views:
    1,258
    jacksu
    Jun 15, 2006
Loading...

Share This Page