Alternative to TreeSet?

[laredo...@zipmail.com]

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

[Eric Sosman]

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

[Daniel Pitts]

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.

[Lew]

> 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

[Arved Sandstrom]

Bang on.

AHS

[Robert Klemme]

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

[Roedy Green]

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

[Sven Köhler]

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