Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #23854 > unrolled thread

Alternative to TreeSet?

Back to article view | Back to comp.lang.java.programmer

Contents

  Alternative to TreeSet? laredotornado@zipmail.com - 2013-05-06 08:10 -0700
    Re: Alternative to TreeSet? Eric Sosman <esosman@comcast-dot-net.invalid> - 2013-05-06 11:19 -0400
      Re: Alternative to TreeSet? Lew <lewbloch@gmail.com> - 2013-05-06 11:33 -0700
      Re: Alternative to TreeSet? Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-05-06 18:01 -0300
    Re: Alternative to TreeSet? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2013-05-06 08:25 -0700
      Re: Alternative to TreeSet? Robert Klemme <shortcutter@googlemail.com> - 2013-05-07 07:58 +0200
    Re: Alternative to TreeSet? Roedy Green <see_website@mindprod.com.invalid> - 2013-05-07 09:21 -0700
    Re: Alternative to TreeSet? Sven Köhler <remove-sven.koehler@gmail.com> - 2013-05-07 19:36 +0300

#23854 — Alternative to TreeSet?

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

[toc] | [next] | [standalone]

#23855

On 5/6/2013 11:10 AM, laredotornado@zipmail.com 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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#23862

> 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

[toc] | [prev] | [next] | [standalone]

#23866

On 05/06/2013 12:19 PM, Eric Sosman wrote:
> On 5/6/2013 11:10 AM, laredotornado@zipmail.com 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

[toc] | [prev] | [next] | [standalone]

#23856

On 5/6/13 8:10 AM, laredotornado@zipmail.com 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.

[toc] | [prev] | [next] | [standalone]

#23883

On 06.05.2013 17:25, Daniel Pitts wrote:
> On 5/6/13 8:10 AM, laredotornado@zipmail.com 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/

[toc] | [prev] | [next] | [standalone]

#23896

On Mon, 6 May 2013 08:10:48 -0700 (PDT), laredotornado@zipmail.com
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)

[toc] | [prev] | [next] | [standalone]

#23897

On 05/06/2013 06:10 PM, laredotornado@zipmail.com 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web