Alternative to TreeSet?

[laredotornado]

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]

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.

 

[Daniel Pitts]

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.

 

[Lew]

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

 

[Arved Sandstrom]

None that I know of.


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

 

[Robert Klemme]

On 5/6/13 8:10 AM, (e-mail address removed) wrote:

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

 

[Roedy Green]

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.

 

[Sven Köhler]

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