4

In the code below, I believe it would look more appropriate to make the method argument be of type Comparable[] instead of Object[].

The first reason it would be more appropriate is that one can be safe from runtime exceptions because every passed object has to implement interface Comparable. Second, every object in Java inherits from class Object so one can typecast any object as (Object) to use the methods of class Object.

package java.util; 
public class Arrays {
.........
public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }
.........
}

Is there a reason why type Object[] is preferred over type Comparable[] as an argument type?

  • This scenario looks similar to clone() method where any object that calls clone() method has to implement marker interface Cloneable{}. Because, when i say obj.clone(), I guess that native method C implementation clone() internally checks kind of (obj instanceof Cloneable) this is why we get exception at runtime. am i correct? – overexchange Dec 12 '14 at 9:47
  • Nitpick: yo do not need to explicitly cast an object to Object in order to use methods of class Object. – Andres F. Dec 12 '14 at 21:02
  • @AndresF. Nice pick, i don't need to typecast[as (Object)], If an interface has no direct superinterfaces, then the interface implicitly declares a public abstract member method m with signature s, return type r, and throws clause t corresponding to each public instance method m with signature s, return type r, and throws clause t declared in 'class Object', unless an abstract method with the same signature, same return type, and a compatible throws clause is explicitly declared by the interface.---JLS. May be, you are close to the answer, But would not like to say it, Is that true? – overexchange Dec 13 '14 at 7:57
  • "one can be safe from runtime exceptions because every passed object has to implement interface Comparable" That would still not be safe from runtime exceptions. In order to sort, you need to make sure that the type is comparable to itself. You need a bound like <T extends Comparable<? super >>. Otherwise, it is still not safe. You will still get a warning. – user102008 Dec 13 '14 at 8:59
3

If you look at the mergeSort code you will see that it casts each member of array a to Comparable. If any object in the array is not a Comparable, a ClassCastException will be generated unless you have created a Comparator which knows how compare your objects and passed that to the sort method. Example of the two different techniques (comparable v comparator) here.

The Java developers decided that you should not be forced to add a Comparable interface to objects just because you want to store them in an array and may choose to sort them at some point. This gives you greater flexibility (and less cruft on your classes) at the minor risk of runtime failures rather than compile-time type checking. The flexibility is a win, in my opinion.

  • 2
    +1 I didn't think about the Comparator. But note that this is incomplete: with the single-argument sort method, we expect all objects to be Comparable. We could still argue that the signature of that method should use Comparable[]. – coredump Dec 12 '14 at 9:12
  • Say, If am yet to decide at design time the argument type of sort() method of util.Arrays class, Do i need to really understand/consider how mergeSort() or xyzSort() works internal to sort()? Because i would decide at design time that any passed object must implement Comparable, may be, later the sort() method would be implemented. – overexchange Dec 13 '14 at 8:02
2

There is a problem caused by the way java arrays work, which is this: every array has its own type, which is not necessarily the same type as the objects contained in the array, and the type cannot be changed at runtime.

For example:

Object [] a= new Object[]{
   (Integer)5,
   (Integer)2
};

Arrays.sort ((Comparable [])a);

Would cause a class cast exception, despite the fact that all of the elements in a are comparable.

Now, you could argue that we shouldn't create an Object array but rather a more specific type, but there's another problem with that. Consider this code:

class GenericArrayExample<T extends Comparable>
{ 
    T[] a;

    GenericArrayExample(int size)
    {
        a = new T[size];
    }
    public void sort ()
    {
        Arrays.sort (a);
    }
 }

What's the problem with this, you may ask: a is an array of Ts so should be comparable. There are two problems, however.

The first is that the constructor won't compile, because in order to create the new array it needs to know the type of T at runtime, but Java can't actually provide this information (google java generics erasure if you want to find out why). The usual solution is to use an array of objects instead. You could use Comparable [] instead, though, except:

Wouldn't it be nice if we could use an instance of this class to store non-Comparable objects too? We'd have to avoid using the sort method, of course, and it should throw some kind of exception if we try to use it..

This can only be achieved, however, if a is an array of objects, which means Arrays.sort must accept object arrays.

2

Basically, Java types don't always propagate nicely. If at any point, you cast to Object, you loose information about your types (this might not be always true in a block your compiler can analyze). And you can't always avoid Object, due to generics.

Details

If we look at OpenJDK's implementation, the comment says:

  1. Objects must implement Comparable
  2. Objects must be mutually comparable: you can't compare String and Integer instances.

Both checks can be done at runtime (throwing exceptions if needed). What you suggest enables to do the first check during compilation.

However, we must consider the method with respect to its usage, and unfortunately, you can't always know the type of some objects.

I originally wrote an example with List<String> and toArray, which returns an Object[]. The conversion to Object[] does not allow calling sort and I saw no easy way to convert Object[] to String[]. Thanks to SJuan76's comments, here is how to do it:

    String[] strings = names.toArray(new String[0]);

Then strings, thanks to array covariance, is suitable for comparison. However, this approach is not developper-friendly. Furthermore, it cannot be abstracted away by language constructs: generics use type erasing techniques that introduce Object instances. By the way, let's forget about generics for a moment: after all, early versions of Java, for which sort was implemented, did not provide generics.

As already said, the kind of code written above is certainly not convenient for use. But more importantly, even though it is checked at compile-time, I am pretty sure it is not optimized away: there is still an array copy operation at runtime: you don't want to write an API which imposes this kind of cost to the user (also consider the performance of original virtual machines).

Then, it is better to simply accept more parameters and perform checks dynamically. Since anyway, point (2) above already requires runtime checks and possibly throws exceptions, we might as well accept Object[] and test types at runtime.

Now, you might think that the fact that some functions loose type informations like toArray (without argument) is itself unfortunate but this is more an issue of the language's type system at this point.

  • 1
    You can use names.toArray(new String[names.size()]) or even names.toArray(new String[0]) to get directly an String[] (checked at compile time). – SJuan76 Dec 12 '14 at 11:10
  • @SJuan76 Thanks, I edited my answer. What you suggest still requires a copy during execution, right? Do you think it might be possible to write "cast-only" code, so that there is no runtime penalty? – coredump Dec 12 '14 at 13:37
  • More than a "copy", you just assign the references to the new array. Also, those "type-lossing" methods usually come from versions prior to java 5 (which introduced generics) – SJuan76 Dec 12 '14 at 18:43
  • @SJuan76 "More than a copy, you just ...": I am not sure I'am following. My understanding is that there is an array allocation (that arrays grows when using new String[0] initially); then we perform a shallow-copy of the elements: references are copied from one array to the other one. Isn't that right? – coredump Dec 12 '14 at 19:46
  • "Both checks can be done at runtime" If by "checked at runtime" you mean, try it and see if it throws an exception, then yes. Otherwise, #2 is not guaranteed to be checkable at runtime. – user102008 Dec 13 '14 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.