Java: How to workaround the lack of Equatable interface?

Question

Hello, everyone!

As far as I know, things such as SortedMap or SortedSet, use compareTo (rather than equals) on Comparable<?> types for checking equality (contains, containsKey).

But what if certain types are equatable by concept, but not comparable?
(Hash codes, memory addresses, ...)

I have to declare a Comparator<?> and override the method int compareTo(T o1, To2). OK, I can return 0 for instances which are considered equal. But, for unqeual instances, what do I return when an order is not evident?

Is the approach of using SortedMap or SortedSet on equatable but (by concept) not comparable types good anyway?

Thank you!

EDIT:
I don't want to store things sorted, but would I use "usual" Map and Set, I couldn't "override" the equality-behavior.

EDIT 2:
Why I can't just override equals(...):
I need to alter the equality-behavior of a foreign class. I can't edit it.

EDIT 3:
Just think of .NET: They have IEquatable interface which cat alter the equality-behavior without touching the comparable behavior.

EDIT 4:
Can't I just make compareTo return 0 for equal and 1 for non-equal instances? What's the big problem? I've dome some tests, it seems that SortedMap/SortedSet call compareTo on a pair of instances once. Yes, the order would not make sense, but why should it be my problem? I don't need the order. *I just need altered equality-behavior. Sadly most people just can't understand this.
NOTE: The concept of returning 1 for non-equal instances now was proven wrong.

EDIT 5:
Altering equality-behavior of foreign classes is a bad concept? Sure? I don't think so: Why then am I allowed to alter comparison-behavior of foreign classes using Comparator?

EDIT 6:
Thanks to Mark Peters and waxwing for the idea of wrapping the key type in a custom class. This way, I can override equals and hashCode, thus altering the equality-behavior.

Answer 1

You cannot sort objects if they are not comparable; how would you know which of the two objects should come first if they are not comparable? So there is no way to put objects that are not comparable in a SortedMap or SortedSet. (Why would you want to? Use a different kind of Map or Set).

The equals() method in Java is defined in class Object, and since all classes extend Object, all objects have an equals() method. You have to take care that you override and implement equals() correctly in your classes if you want to be able to tell if two objects are equal.

If you want to put objects in a hash-based collection (such as HashMap or HashSet) you must also override hashCode() and you must make sure that hashCode() and equals() are implemented the right way (see the documentation of those methods in class Object for details on how to do that).

Answer 2

No, using SortedMap or SortedSet on equatable but not comparable types is a horrible idea. If they're not comparable intrisically or through a comparator, they should not be used in a SortedSet. Sorted implies there is ordering, meaning you can compare two items to see which is "less".

Just use a HashMap/Set.

Edit to your Edit #2

If you can't properly override equals, somewhere you've got a very bad design. You would need to give more info into what you're trying to accomplish.

Edit to your Edit #3

In Java, modifying equals does not change the comparable behaviour. You don't need an interface to accomplish that.

Edit to your Edit #4

NO, YOU CANNOT JUST RETURN 1 FOR NON-EQUAL ELEMENTS!!

SortedSets use the comparison to find your element in the set. The comparable interface has specific requirements. The one that you're breaking is that if A.compareTo(B) > 0, then necessarily B.compareTo(A) < 0. You're breaking that which would make it impossible to find elements in your set afterwords.

public static void main(String[] args) throws Exception {
    SortedSet<MyClass> set = new TreeSet<MyClass>();
    MyClass one = new MyClass(1);
    set.add(one);
    set.add(new MyClass(2));
    set.add(new MyClass(3));
    System.out.println(set.contains(one));
}
private static class MyClass implements Comparable<MyClass> {
    private final int data;
    private MyClass(int data) { this.data = data; }
    public int compareTo(MyClass o) { return (data == o.data ? 0 : 1); }
}

This code prints false, so obviously your comparator has broken the semantics of a Set.

Answer 3

It looks like you don't want/need to sort the elements.

In that case, maybe you can use HashMap and HashSet instead? There is no point of using SortedMap and SortedSet if you don't need it to be sorted.

Answer 4

I don't want to store things sorted, but would I use "usual" Map and Set, I couldn't "override" the equality-behavior.

If you don't want to store your elements sorted, then why are you using a sorted collection?

In order to maintain a sorted collection, an insert operation (typically) has O(log n) complexity to place the element in the correct place. If you don't need sorting, then this is wasteful, as you could be using a hash-based collection (HashMap, HashSet) which would give you O(1) insertion time.

Answer 5

Is the approach of using SortedMap or SortedSet on equatable but (by concept) not comparable types good anyway?

No. The point of these collections is to allow you to sort the objects in them, if the objects don't have a natural sorting order then what is the point of putting them in a sorted collection?

You should override the equals() and hashcode() methods and use the standard Map/Set classes instead.

Answer 6

As others have said, if there is no natural order a SortedXXX isn't really an option. However, assuming you just want some kind of consistent way of listing the elements, if you just consider the fields that you are using for equality testing, as these constitute the "primary key", and come up with some sort of numerical or alphabetical ordering around them that might suit your purpose.

Answer 7

If you need to override hashCode but can't, I think you're looking at extending HashMap or writing your own.

Answer 8

Just use a (custom) Comparator provided to the implementation of Sorted[Set|Map] when you create it...

The javadocs would tend to suggest this: All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified comparator).

SortedSet<MyObject> s = new TreeSet<MyObject>(new Comparator<MyObject>() {
    @Override
    public int compare(T o1, T o2) {
        // your very specific, fancy dancy code here
    }
});

http://java.sun.com/javase/6/docs/api/

Answer 9

I am not sure if I see your point (I think you're trying to solve a problem from the wrong direction on), but if you after all just want a Set or Map which maintains insertion order, then use LinkedHashSet or LinkedHashMap respectively.

---

Update: as per your quote:

I need to alter the equality-behavior of a foreign class. I can't edit it.

Inside a sorted set/map? Then use a TreeSet or TreeMap which you construct with a custom Comparator. E.g.

SortedSet<String> set = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);

(which constructs a set of Strings ordered in case insensitive order).

See also:

• Sun tutorial: Ordering objects
• Different ways to order objects

Answer 10

I don't want to store things sorted, but would I use "usual" Map and Set, I couldn't "override" the equality-behavior.

You are trying to override the equals() method of an unknown type. You are thinking about the problem wishing you had the IEquatable interface. If you must use SortedSet/SortedMap then provide a Comparator like @ptomli mentions in his answer.

Using HashMap/HashSet instead seems to be a good suggestion. Have you looked at those?

Answer 11

It's not clear, but it could be that all you're trying to do is get a Collection of somethings, using the same semantics of Set/Map, but with somethings that don't adequately implement Object.equals.

In that case I suggest you subclass AbstractSet or AbstractMap and override AbstractCollection.contains to use your version of equals.

It's not something I'd recommend, but your question doesn't actually make it clear what you're trying to achieve.

See http://java.sun.com/javase/6/docs/api/java/util/AbstractSet.html and http://java.sun.com/javase/6/docs/api/java/util/AbstractCollection.html#contains(java.lang.Object)

Answer 12

Consider wrapping your foreign class inside your own instead.

public class Foreign {
  // undesired equals() and hashCode() implementation
}


public class ForeignWrapper {
   private Foreign foreign;

   public ForeignWrapper(Foreign foreign) {
      this.foreign = foreign;
   }

   public void equals() {
       // your equals implementation, using fields from foreign
   }

   public int hashCode() {
       // your hashCode implementation, using fields from foreign
   }

}

Then add new ForeignWrapper(foreign) to the standard HashSet / HashMap. Not applicable in all situations, but maybe in yours.

Answer 13

If memory is not a big problem subclass HashMap and HashSet to take an Equality class

interface Equality<T>//Defines the equality behavior
{
   int hashCode(T t);//Required, always make sure equals = true => same hashCode
   boolean areEqual(T t,Object t2);
}
class EqualWrapper<T>//Wraps object and equality for the HashMap/Set
{
   T object;
   Equality<T> equal;
   int hashCode(){return equal.hashCode(object);}
   boolean equals(Object o){return equal.areEqual(object,o);}

}
class MySet<T>extends AbstractSet<T>
{
   private HashSet<EqualWrapper<T> > internalSet = new HashSet<T>();
   private Equality<T> equal;
   public MySet(Equality<T> et){equal = et;}
   // TODO implement abstract functions to wrapp 
   // objects and forward them to 
   // internalSet  
}

This way you can define your own equality behavior. Strange that it is missing from the jre