What does "Mutually Comparable" mean?

Question

I read that :

whenever a collection need to be sorted, the elements must be mutually comparable.

I wrote the below code and it worked correctly. Can you please tell how class b and class c are mutually comparable and what is the meaning of being "mutually comparable"?

import java.util.ArrayList;
import java.util.Collections;

class b implements Comparable<c> {
    String str1;

    b(String str1) {
        this.str1 = str1;
    }

    public int compareTo(c object) {
        return str1.compareTo(object.str1);
    }
}

class c implements Comparable<b> {
    String str1;

    c(String str1) {
        this.str1 = str1;
    }

    public int compareTo(b object) {
        return str1.compareTo(object.str1);
    }
}

public class a {

    public static void main(String[] args) {
        b obj1 = new b("monster");
        c obj2 = new c("aman");

        ArrayList list  = new ArrayList();
        list.add(obj1);
        list.add(obj2);
        System.out.println("unsorted list = "+list);
        Collections.sort(list);
        System.out.println("sorted list = "+list);
    }
}

Answer 1

In order for classes A and B to be mutually comparable, these requirements need to be satisfied:

• A call of compareTo on an instance of A passing an instance of B must be allowed
• A call of compareTo on an instance of B passing an instance of A must be allowed
• If a.compareTo(b) returns x, then b.compareTo(a) must return a value y with the opposite sign, or zero, when x is zero.

The classes in your code are not mutually comparable, because an attempt to pass an instance of c to b's compareTo (and vice versa) works fine. However, they are not comparable to instances of their own classes, which would create a problem if you were to add more items to the collection to be sorted.

In order for the container to be sortable, your class needs to be comparable to instances of its own type as well.

Answer 2

Mutually comparable means that instances of both classes must be comparable to the other.

In case of type A and type B:

• A must implement Comparable<T> where T extends B (or is B)
• B must implement Comparable<U> where U extends A (or is A)
• The comparison must be consistent. Consistent means that if a>b then it must be so b<a. And if a<b then it must be so b>a. And if a==b then it must be so b==a.

So that the following code can be written:

A a = ...;
B b = ...;

int rab = a.compareTo(b);  // A is comparable to B
int rba = b.compareTo(a);  // B is comparable to A

// And also consistent:
if (   !(rab<0 && rba>0)
    || !(rab>0 && rba<0)
    || !(rab==0 && rba!=0))
    System.out.println("Not consistent!");

If type A and type B are the same, then a and b are obviously mutually comparable.

Sorting algorithms usually require the elements to be mutually comparable so they can compare any 2 of the sortable elements to each other.

Back to your question

Your case is special. Your 2 objects obj1 and obj2 are mutually comparable according to the definition. Your obj1 and obj2 instances are mutually comparable, but your b and c classes are not.

However, if you would pass another instance of either type a or type b, all elements would be not. Because if we would select 2 instances from the collection of the same type, they would not implement Comparable to the same type.

obj1.compareTo(obj2); // This is valid, b implements Comparable<c>
obj2.compareTo(obj1); // This is also valid, c implements Comparable<b>

obj1.compareTo(obj1); // This is NOT valid! b does not implement Comparable<b>

Answer 3

Your code works only by chance and it has so many mistakes that they cancel out each other resulting into working code.

1. You use raw type: ArrayList list = new ArrayList(); What is a raw type and why shouldn't we use it?
2. If a class implements Comparable<T>, T should be a super type of that class. For example Integer implements Comparable<Number> would be just as fine.

the elements must be mutually comparable

That means that each element from that collection must be comparable to each other and in your case that works only because you added only 2 elements (adding more would result into ClassCastException at runtime).

If you want a sortable collection containing both B and C, find common parent of those classes (or perhaps create an interface for it, lets call it BC) then you would go:

class B implments BC, Comparable<BC> { ... }
class C implments BC, Comparable<BC> { ... }

and changle your list declaration and creation to: ArrayList<BC> list = new ArrayList<>();

EDIT:

To truly guarantee that ArrayList<BC> is sortable, we need to change the BC's declaration to:

 interface BC extends Comparable<BC> { }

Otherwise we could have class D implements BC but not Comparable<BC>. With this new annotation we say "anything that implements BC must implement Comparable<BC> as well".

Now you can write only

class B implments BC { ... }
class C implments BC { ... }

(Also note that you can add getString() method to interface BC to avoid the instanceof testing and casting in the compare method)

Answer 4

It means that for any two items in the collection, you must be able to compare A to B and vice versa.