-2

Why are there non generic versions of binary search in Java?

Is it because they don't want to crash existing implementations?

Merni
  • 2,842
  • 5
  • 36
  • 42
  • 3
    Which BS implementation are you talking about ? – Konstantin Yovkov Apr 14 '14 at 09:40
  • 6
    [Sure](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch%28T[],%20T,%20java.util.Comparator%29) [there](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch%28T[],%20int,%20int,%20T,%20java.util.Comparator%29) [are](http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch%28java.util.List,%20T%29) [generic versions](http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch%28java.util.List,%20T,%20java.util.Comparator%29) of that method. – Rohit Jain Apr 14 '14 at 09:40
  • 1
    @kocko: I had to read that a second time before my brain took in the appropriate meaning of BS. – W.K.S Apr 14 '14 at 09:44
  • 1
    @W.K.S … I honestly didn’t get it until your comment. – Konrad Rudolph Apr 14 '14 at 09:56

2 Answers2

8

There is of course a generic version of binarySearch1.

The reason why there are non-generic overloads is performance: value types would need to be boxed (and thus copied) in order to be able to use a generic binarySearch. Same goes for sort and other algorithms.

1 In fact there’s more than one generic overload but that’s not relevant here.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • Ok, so what's the difference between generics in Java and Templates, since in C++ they only have one Binary Search. – Merni Apr 14 '14 at 10:00
  • @Merni [What are the differences between Generics in C# and Java... and Templates in C++?](http://stackoverflow.com/q/31693) – Konrad Rudolph Apr 14 '14 at 10:02
  • @newacct Of course it does. OP is probably **not** talking about the `Object` overload (otherwise I’d agree) but about the separate overloads for all primitive types (point 1 in your answer). And here performance is everything, because lack of the separate overloads means that we would need to copy the array (to box the values) in order to call the method. – Konrad Rudolph Apr 15 '14 at 09:16
  • @KonradRudolph: The lack of separate overloads means that you cannot use it with arrays of primitives. Of course you can copy the array but that's a completely separate thing. – newacct Apr 15 '14 at 09:21
  • @newacct “that’s a completely separate thing” – well, it solves the problem. If performance is not an issue, then the non-generic versions of `binarySearch` would be implemented in terms of boxing the array and calling the `Object` (or generic) version of `binarySearch` ([like so](https://gist.github.com/klmr/10718254)). Obviously that’s not the case because it’s inefficient. Instead, the whole binary search implementation is literally copy pasted multiple times around in the `Arrays` code. That’s *really* bad practice, and the only justification for that is performance. – Konrad Rudolph Apr 15 '14 at 09:41
  • @KonradRudolph: In that case (implementing non-generic versions by copying arrays), there would still be "non-generic versions". So it doesn't answer the OP's question of why there are "non-generic versions". – newacct Apr 15 '14 at 09:46
1

It is unclear what "non generic versions of binary search" you are talking about.

  1. If you are talking about the versions of binarySearch that take arrays of primitive types, it's because generics only apply to reference types, so a generic binary search method could not possibly handle arrays of primitive types.

  2. If you are talking about the versions of binarySearch that take Object[]:

    public static int binarySearch(Object[] a, Object key)
public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)

    How would they make it generic?

    • Option 1: public static <T> int binarySearch(T[] a, T key)

      In this case, there is no benefit to making it generic.

      The following two method signatures would be equivalent -- any set of arguments that you can pass to one, you can pass to the other:

      public static int binarySearch(Object[] a, Object key)
public static <T> int binarySearch(T[] a, T key)

      This is because 1) T can be chosen to be Object, so the generic version includes the non-generic version; and 2) any reference array type is a subtype of Object[], and any reference type is a subtype of Object, so the non-generic version includes the generic version.

      Since they are equivalent, and thus the T is useless, the simpler version (without the generic type parameter) is better.

    • Option 2: they could have made it

      public static <T extends Object & Comparable<? super T>>
    int binarySearch(T[] a, T key)

      but this would break compatibility with old code depending on it taking Object[] and Object (without any constraint on it being a type that is comparable to itself). APIs that take previously non-generic classes that now take a parameterized type do not break compatibility, because old code would still work with raw types. However, in this case, raw types do not help because arrays are reified both before and after generics.

newacct
  • 119,665
  • 29
  • 163
  • 224
  • “The following two method signatures would be equivalent” – no they are not. The generic signature ensures that all values in the array have the same type `T` (or one derived from that). The first signature places no such restriction on the array, it can contain values of wildly different types. Using generics here is anything but useless. – Konrad Rudolph Apr 15 '14 at 09:18
  • @KonradRudolph: "ensures that all values in the array have the same type T (or one derived from that)" Right. All reference types in Java derive from `Object`. "Using generics here is anything but useless." Try to find one example of inputs that can be used with one method but not the other. – newacct Apr 15 '14 at 09:23
  • “All reference types in Java derive from `Object`” – so in other words, that’s a tautology, and saying nothing. – “Try to find one example of inputs that can be used with one method but not the other” – that’s not the point. The point is that the generic signature is *more* restricted. That’s a *good* thing! Good APIs are not liberal, they are restrictive because only like that we can use the compiler to provide useful diagnostics. – Konrad Rudolph Apr 15 '14 at 09:29
  • @KonradRudolph: Yes, so what you said is a tautology and does't mean anything. "The point is that the generic signature is more restricted." The point is that it is NOT more restricted. There is no case where it "restricts". It's like saying that ` void print(T x)` is "more restricted" than `void print(Object x)`. It is not. – newacct Apr 15 '14 at 09:45
  • No, it’s not the same thing, because in the `print` case there’s only one value. In the case of `binarySearch` there are multiple values and the type `T` expresses something about the relation between their types. Of course you can always bind `T` to `Object`, in which case these two are truly identical. But you can also (explicitly or implicitly) bind `T` to another, more restricted type, if you so wish: `Arrays.binarySearch(arr, key, comp);` (and you don’t always need to specify the generic type, Java will tell you if the parameter types mismatch). – Konrad Rudolph Apr 15 '14 at 09:53
  • @KonradRudolph: If you explicitly specify the wrong parameter, then it doesn't work; so? The fact that it's generic means it works if there is some choice of parameter that works. According to the same logic, `MyClass.print("foo")` also doesn't work, so the two `print` functions are not equivalent. Again, `T` expresses no relation because fixing `T` to `Object` does not narrow the types of expressions that can be passed. – newacct Apr 15 '14 at 10:02
  • That’s desired: we *want* the compiler to complain when we (accidentally) specify the wrong parameter. The non-generic variant cannot provide that. That’s precisely my point. From the beginning. And it’s the whole point of using strong typing to begin with. Using `Object` is the opposite of that – it’s weak typing. There’s an overwhelming consensus in the Java world that strong typing is superior to weak typing. – Konrad Rudolph Apr 15 '14 at 10:16
  • @KonradRudolph: That's like saying anywhere in the Java API where we have `Object` or any other concrete type, we should change it to a generic type parameter, to enable you to explicitly specify the wrong parameter and make the compiler complain. And thus in fact in this example, we should actually have ` int binarySearch(X[] arr, Y key)` because that is more "generic" than the one with just one type parameter, so you can explicitly specify X and Y and have more ways for it to not compile. – newacct Apr 15 '14 at 10:54
  • @KonradRudolph: You must also think that `Arrays.fill()` should be ` void fill(T[] a, T val)` instead of `void fill(Object[] a, Object val)`. But it isn't, because it would make no difference to a user who does not explicitly specify the wrong type parameter to make it complain. Everywhere in the Java API, where adding a type parameter does not change the set of inputs allowed, it is not added. – newacct Apr 15 '14 at 10:57
  • Or maybe have you considered that these APIs precede the introduction of generic types, or that Java’s type system is simply not perfect and thus the ideal state of things isn’t implemented? Other languages do it exactly as you just mockingly proposed (e.g. Haskell and C++). – Konrad Rudolph Apr 15 '14 at 11:46
  • @KonradRudolph: "these APIs precede the introduction of generic types" has nothing to do with it. The version `public static int binarySearch(T[] a, T key, Comparator super T> c)` existed from before generics (Java 1.2), but use `T` now. Why? Because in this case, the `T` narrows the set of allowed inputs. In the case of the versions without the comparator, the `T` does not narrow the set of allowed inputs. It is therefore pointless to add it. – newacct Apr 15 '14 at 18:20