Comparable and Comparator contract with regards to null

Question

Comparable contract specifies that e.compareTo(null) must throw NullPointerException.

From the API:

Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

On the other hand, Comparator API mentions nothing about what needs to happen when comparing null. Consider the following attempt of a generic method that takes a Comparable, and return a Comparator for it that puts null as the minimum element.

static <T extends Comparable<? super T>> Comparator<T> nullComparableComparator() {
   return new Comparator<T>() {
      @Override public int compare(T el1, T el2) {
         return
            el1 == null ? -1 :
            el2 == null ? +1 :
            el1.compareTo(el2);
      }
   };
}

This allows us to do the following:

List<Integer> numbers = new ArrayList<Integer>(
   Arrays.asList(3, 2, 1, null, null, 0)
);
Comparator<Integer> numbersComp = nullComparableComparator();
Collections.sort(numbers, numbersComp);
System.out.println(numbers);
// "[null, null, 0, 1, 2, 3]"

List<String> names = new ArrayList<String>(
   Arrays.asList("Bob", null, "Alice", "Carol")
);
Comparator<String> namesComp = nullComparableComparator();
Collections.sort(names, namesComp);
System.out.println(names);
// "[null, Alice, Bob, Carol]"

So the questions are:

• Is this an acceptable use of a Comparator, or is it violating an unwritten rule regarding comparing null and throwing NullPointerException?
• Is it ever a good idea to even have to sort a List containing null elements, or is that a sure sign of a design error?

Solution 1

Comparable doesn't allow null simply because:

a.compareTo(b) == -b.compareTo(a)

for all objects a and b where !a.equals(b). More specifically:

a.equals(b) ? b.equals(a) && a.compareTo(b) == 0 &&
                  b.compareTo(a) == 0 && a.hashCode() == b.hashCode()
            : !b.equals(a) && a.compareTo(b) != 0 &&
                  a.compareTo(b) == -b.compareTo(a)

must evaluate to true to satisfy the relevant contracts.

So null isn't allowed because you can't do:

null.compareTo(a)

Comparator is more flexible so handling of null is an implementation-specific issue. Support it or not depending on what you want your Comparator to do.

Solution 2

Is it ever a good idea to even have to sort a List containing null elements, or is that a sure sign of a design error?

Conceptually, null means "nothing", and placing nothing in a list seems weird to me. Also, the Java List contract states that

Some list implementations have restrictions on the elements that they may contain. For example, some implementations prohibit null elements

so a List implementation in Java is not even required to support null elements at all. To sum up, if you do not have a good reason to put null into a list, don't, and if you do, test that it actually works as expected.

Solution 3

Is it ever a good idea to even have to sort a List containing null elements, or is that a sure sign of a design error?

Well, it probably doesn't make sense for the list to contain a null Object, but maybe your List contains a "business object" and you can sort on different properties of the business object, some of which may contain nulls.

Is this an acceptable use of a Comparator

The BeanComparator allows you to sort on a propery in a business object even if the property contains null, so I would have to say it is an acceptable use of a Comparator.

Comments

[polygenelubricants]

+1 for catching that null support in List isn't even mandatory.

[polygenelubricants]

The a.b == -b.a test is convincing, but I prefer the API's argument: Comparable defines natural ordering for instances of a class, and null is simply not an instance of any class. Would you address the null in the List in the first place, though? I hope that's not [subjective].

[Nico]

(Such an equation a.compareTo(b) == -b.compareTo(a) is not necessarily correct for every type. The return value of compareTo() needs not to represent the difference of any fields of two objects. Although this is a way in which compareTo() is programmed very often, it's not a good idea! - A calculated difference could overflow and then result in a wrong positive/negative value. (Better literally return -1, 0 or 1 from compareTo() only. - It's not so sneak, but correct.))

[ymajoros]

Which "BeanComparator"? This is not part of the JDK, we can't count on it to prove anything in that regard.

[camickr]

@ymajoros, Which "BeanComparator"? the one found in the link.

[ymajoros]

which isn't part of the JDK... Besides being a bad idea anyway (unsafe, breaks upon refactoring, etc.).

[camickr]

@ymajoros, what does the JDK have to do with anything? Problems are solved by writing reusable code. How is this unsafe and how does it break on refactoring? What are you even refactoring? This class is just a tool that you can use so you don't need to write a custom Comparator every time you want to do sorting.

[ymajoros]

Why would it be an "acceptable use of a Comparator" because someone somewhere wrote a BeanComparator (which is a bad idea anyway)? Comparator has a contract, this alien BeanComparator thing isn't necessarily observing it and you can't count on it for proving that comparing null attributes is ok.

[ymajoros]

not type-safe to begin with, and it will break whenever you rename the field; compilation doesn't check if it's working, it will break at runtime when used instead; difficult to find the field's usages, etc.

[camickr]

@ymajoros, - not type-safe to begin with how does that matter? It just compares two objects of the same type, whatever type they are. it will break whenever you rename the field and how often do you rename a field? compilation doesn't check if it's working, it will break at runtime when used instead there are many runtime exceptions in the JDK. Why is this a problem? You usually do test a class before moving it to production. difficult to find the field's usages, no idea what that means. It is just a comparator, you don't care about the fields usage you just compare the values.

[camickr]

Comparator has a contract it just returns a value indicating greater than, less than, or equality. If you have some special comparison rules then create a custom Comparator. I'm not suggesting this be used in all cases. I have also noted that it is inefficient so it should not be used on large sorts but it can be satisfactory in small applications. you can't count on it for proving that comparing null attributes is ok it has default logic for handling nulls. Again if it doesn't meet your requirements, then create a custom Comparator. This is just an optional class.

[ymajoros]

#camickr it's just better to have safe code that fails as expected at compile time rather than at runtime. Using strings to refer to fields is definitely a bad practise. But not the subject here, I suggest we go on in a chat if needed

[ymajoros]

#camickr indeed, Comparator's contract is the right answer to the original question (and is more than returning -1/0/1, see javadoc). Citing this BeanComparator doesn't prove anything regarding the original contract, which BeanComparator could enforce, or not. We're not improving anything here, I suggest we proceed in a chat session, if needed.

[camickr]

@ymajoros, agreed, this is NOT a good answer to the original question if that is what you are complaining about.