Comparator and equals()?

While this might work, it is far from being a best practice.

While this might work, it is far from being a best practice. From the SortedSet docs: Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface 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 sorted set 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 sorted set, equal.

The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface. For objects that implement Comparable, there should always be a consistency between the methods equals(), hashcode() and compareTo(). I'm afraid a SortedSet is just not what you want, nor will a Guava MultiSet be adequate (because it will not let you independently retrieve multiple equal items).

I think what you need is a SortedList. There is no such beast that I know of (maybe in commons-collections, but those are a bit on the legacy side), so I implemented one for you using Guava's ForwardingList as a base class.In short: this List delegates almost everything to an ArrayList it uses internally, but it uses Collections.binarySearch() in it's add() method to find the right insertion position and it throws an UnsupportedOperationException on all optional methods of the List and ListIterator interfaces that add or set values at a given position. The Constructors are identical to those of ArrayList, but for each of them there is also a second version with a custom Comparator.

If you don't use a custom Comparator, your list elements need to implement Comparable or RuntimeExceptions will occur during sorting. Public class SortedArrayList extends ForwardingList implements RandomAccess{ private final class ListIteratorImpl extends ForwardingListIterator{ private final int start; public ListIteratorImpl(final int start){ this. Start = start; } @Override public void set(E element){throw new UnsupportedOperationException();} @Override public void add(E element){throw new UnsupportedOperationException();} @Override protected ListIterator delegate(){return inner.

ListIterator(start);}; } private Comparator comparator; private List inner; public SortedArrayList(){this(null, null, null);} @SuppressWarnings("unchecked") private SortedArrayList( final List existing, final Collection values, final Comparator comparator ){ this. Comparator = (Comparator) (comparator == null?Ordering.natural() : comparator ); inner = ( existing == null? (values == null?

New ArrayList(values) : new ArrayList() ) : existing; } public SortedArrayList(final Collection c){ this(null, c, null); } public SortedArrayList(final Collection c, final Comparator comparator){ this(null, c, comparator); } public SortedArrayList(final Comparator comparator){ this(null, null, comparator); } public SortedArrayList(final int initialCapacity){ this(new ArrayList(initialCapacity), null, null); } public SortedArrayList(final int initialCapacity, final Comparator comparator){ this(new ArrayList(initialCapacity), null, comparator); } @Override public boolean add(final E e){ inner. Add( Math. Abs( Collections.

BinarySearch(inner, e, comparator) ) + 1, e ); return true; } @Override public void add(int i, E e){throw new UnsupportedOperationException();} @Override public boolean addAll(final Collection collection){ return standardAddAll(collection); } @Override public boolean addAll(int i, Collection es){ throw new UnsupportedOperationException(); } @Override protected List delegate(){ return inner; } @Override public List subList(final int fromIndex, final int toIndex){ return new SortedArrayList( inner. SubList(fromIndex, toIndex), null, comparator ); } @Override public ListIterator listIterator(){ return new ListIteratorImpl(0); } @Override public ListIterator listIterator(final int index){ return new ListIteratorImpl(index); } @Override public E set(int i, E e){ throw new UnsupportedOperationException(); } }.

I update my question. If it well be better to move all compare logic to comparator so there will be such consistency. – Stas Kurilin Dec 3 '10 at 10:14 1 I updated my answer.

A SortedSet is probably not the right thing for you. – Sean Patrick Floyd Dec 3 '10 at 13:39 Oh. Today you code two classes for me.

Thanks a lot. – Stas Kurilin Dec 3 '10 at 14:22 no prob, implementing Guava-based classes is fun :-) – Sean Patrick Floyd Dec 3 '10 at 14:27 @seanizer: Very kind of you. +1 – Adeel Ansari Dec 3 '10 at 14:46.

Beware: even for two Foos f1,f2 with f1! = f2 you could get f1.hashCode() == f2.hashCode()! That means you won't get a stable sorting with your compare Method.

1 for noticing that the two hashcodes can be the same, -1 because if compare returns 0, the two objects are considered the same (even if equals() returns false). – Aaron Digulla Dec 3 '10 at 10:02 I don't need stable sort) – Stas Kurilin Dec 3 '10 at 10:11.

Hashcode() method doesn't guarantee any less than or greater than. Compare() and equals() should yield the same meaning, but its not necessary, though. As far as I can understand from your confusing code (no offence intended :)), you want to add duplicates to the TreeSet.

For that reason you came up with this implementation. Here is the reason, you can't put them in the TreeSet, quoting from the docs, 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. So, you need to do something with yor equals() method, so it can never return true whats so ever.

The best implementation would be, public boolean equals(Object o) { return false; } By the way, if I am right in my understanding, why not you use List instead and sort that.

1 for "you can't order objects by hashcode" – Aaron Digulla Dec 3 '10 at 9:52 Question updated. – Stas Kurilin Dec 3 '10 at 10:08.

Very interesting question. As far as I understand your problem is duplicate elements. I think that if o1.

Equals(o2) their hash codes might be equal too. It depends on the implementation of hashCode() in your Foo class. So, I'd suggest you to use System.

IdentityHashCode(x) instead.

If o1. Equals(o2) they can be counted as duplicates. – Stas Kurilin Dec 3 '10 at 10:10.

You have a Foo class wich is comparable but want to use a different sorting in a TreeSet structure. Then your idea is the correct way to do it. Use that constructor to "overrule" the natural sorting of Foo.

I can move this logic to comparator. It would be better? I updated my question.

– Stas Kurilin Dec 3 '10 at 10:15.

There is no rule in Java which says that the hash codes of two objects must be different just because they aren't equal (so o1.hashCode() - o2.hashCode() could return 0 in your case). Also the behavior of equals() should be consistent with the results from compareTo(). This is not a must but if you can't maintain this, it suggests that your design has a big flaw.

I strongly suggest to look at the other fields of the objects and use some of those to extend your comparison so you get a value! = 0 for objects were equals() == false.

I updated my question with moving logic to Comparator. – Stas Kurilin Dec 3 '10 at 10:20 1 The logic is flawed; it doesn't matter where you put it. – Aaron Digulla Dec 3 '10 at 13:56.

If you have no specific expected ordering for any two given elements, but still want to consider them un-equal, then you have to return some specified ordering anyway. As others have posted, hashCode() isn't a good candidate, because the hashCode() values of both elements can easily be equal. System.

IdentityHashCode() might be a better choice, but still isn't perfect, as even identityHashCode() doesn't guarantee unique values either The Guava arbitrary() Ordering implements a Comparator using System. IdentityHashCode().

Thanks. Example with Guava is a good argument. – Stas Kurilin Dec 3 '10 at 10:22.

Yes, as others said above, hashCode() is not secure to use here. But if you don't care about the ordering of objects that are equal in terms of o1. CompareTo(o2) == 0, you could do something like: public int compare(Foo o1, Foo o2) { int res = o1.

CompareTo(o2); if (res == 0 &&! O1. Equals(o2)) { return -1; } return res; }.

I think it isn't good if compare(o1, o2)! = compare(o2, o1). – Stas Kurilin Dec 3 '10 at 10:32.

Int res = o1. CompareTo(o2); if(res == 0 ||! O1.

Equals(o2)){ return o1.hashCode() - o2.hashCode(); } Can be problematic, since if 2 objects are equal (i.e.In your res == 0) then these 2 objects return the same hashcode. Hashcodes are not unique for every object. Edit @Stas, The System.

IdentityHashCode(Object x); still won't help you. The reason is described on the javadoc: Returns the same hash code for the given object as would be returned by the default method hashCode(), whether or not the given object's class overrides hashCode(). The hash code for the null reference is zero.

Will System. IdentityHashCode() save me? – Stas Kurilin Dec 3 '10 at 10:17 @Stas, see my updated answer.

– The Elite Gentleman Dec 3 '10 at 10:22 @The Elite Gentleman, I don't understand it. If there is two different objects their default hashCode() would be different with high probability. – Stas Kurilin Dec 3 '10 at 10:30 It simply means that System.

IdentityHashCode() returns (x.hashCode()). So, in your case, it makes no difference whether you use o1.hashCode() or System. IdentityHashCode(o1).

– The Elite Gentleman Dec 3 '10 at 10:40 @The Elite Gentleman, thanks, now I see. – Stas Kurilin Dec 3 '10 at 14:10.

There are a couple of problems here: Hash codes are not generally unique, and in particular System. IdentityHashCode will not be unique on vaguely modern JVMs. This is not a question of stability.

We are sorting an array, but creating a tree structure. The hash code collisions will cause compare to return zero, which for TreeSet means one object wins and the other is discarded - it does not degrade to a linked-list (the clue is having "Set" in the name). There is generally an integer overflow issue with subtracting one hash code from another.

This means the comparison won't be transitive (i.e. It is broken). As luck would have it, on the Sun/Oracle implementation, System.

IdentityHashCode always returns positive values. This means that extensive testing will probably not find this particular sort of bug. I don't believe there is a good way to achieve this using TreeSet.

Two points may be relevant and these are that the return in one situation is shown as -1 and this depends if a negative value is permitted in the function parameter variable or in the relevant country of use, and also if the method you are using is permitted. There are standard data arranging methods like selector or selection sort and the paper description or code is usually available from a national authority if a copy is not in your workplace. Using comparisons like greater than or less than can speed up the code and avoids the use of a direct comparison for equality by implied dropthrough to later script or code.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.