Let's say I have a class called RandomObject:

public class RandomObject implements Comparable<RandomObject> {

    private String name;
    private int value;

    public RandomObject(String name, int value) {
        this.name = name;
        this.value = value;
    }

          . 
          .
          .

    public int compareTo(RandomObject rn) {
        return Integer.compare(value, rn.value);
    }

And this array of RandomObjects (each one of them holding a random int value that will be used for comparison purposes):

RandomObject[] arr = new RandomObject[10];
for (int i = 0; i < arr.length;   i) {
        arr[i] = new RandomObject(" ", (int) (Math.random() * 50));
    }

I also have a class called Quicksort containing the following sort methods:

public static <T extends Comparable<? super T>> void sort(T[] a) {
    sort(a, 0, a.length - 1);
}

 public static <T extends Comparable<? super T>> void sort(T[] a, int start, int end) {
    int left = start, right = end;
    T pivot = a[(left   right) / 2];

    do {
        while (a[left].compareTo(pivot) < 0) {
            left  ;
        }
        while (a[right].compareTo(pivot) > 0) {
            right--;
        }
        if (left <= right) {
            T temp = a[left];
            a[left  ] = a[right];
            a[right--] = temp;
        }
    } while (left <= right);

    if (start < right) {
        sort(a, start, right);
    }
    if (left < end) {
        sort(a, left, end);
    }
}

Calling Quicksort.sort(arr) works normally and sorts arr by value.

However, I also have a BinarySearch class with the following search method:

public static <T extends Comparable<? super T>> int search(T[] a, T value) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start   (end - start) / 2;
        if (a[mid].compareTo(value) == 0) {
            return mid;
        } else if (a[mid].compareTo(value) > 0) {
            end = mid;
        } else {
            start = mid   1;
        }
    } while (start < end);
    return -1;
}

And when I try to perform a search like this:

Integer x = 2;
System.out.println("Trying to find x: "   BinarySearch.search(arr, x));

Something goes wrong:

"java: method search in class br.com.algorithms.BinarySearch cannot be applied to given types;
required: T[],T
found: br.com.algorithms.RandomObject[],java.lang.Integer
reason: inference variable T has incompatible bounds
lower bounds: br.com.algorithms.RandomObject,java.lang.Integer,java.lang.Comparable<? super T>
lower bounds: java.lang.Integer,br.com.algorithms.RandomObject"

no instance(s) of type variable(s) exist so that RandomObject conforms to an Integer

I'm struggling to understand why the sort method works while the search one doesn't in this case. If both methods require T[] and I am providing RandomObject[] for both cases, why isn't search compiling? What's exactly the difference here?

CodePudding user response：

What's exactly the difference here?

search takes a T[] and a T, which means that the array element type of the first parameter needs to be the same as the type of the second parameter. You have given it RandomObject[] and Integer, which is clearly not valid.

On the other hand, sort only takes a single T[], so you can just give it any reference type array, and there is no further constraints between parameters. After all, there is only one parameter.

Note that it is impossible to search for an integer in a RandomObject[] with your current implementation. This is because compareTo compares instances of RandomObject. It does not compare RandomObjects against Integers.

What you can do instead, is create a "dummy" RandomObject using x, and pass that to search:

int x = 1;
RandomObject key = new RandomObject("this does not matter", x);
System.out.println("Trying to find x: "   BinarySearch.search(arr, key));

You can also create a non-generic version of search that only searches RandomObject[]. In this non-generic version, you can change the second parameter to int:

public static int search(RandomObject[] a, int value) { ... }

But in a generic method, it is difficult to know what key the caller wants to search by. It is not impossible though - you can create such an interface:

interface BinarySearchableByKey<T extends Comparable<? super T>> {
    T getKey();
}

Instead of (or in addition to) implementing Comparable, RandomObject should implement BinarySearchableByKey<Integer>, as it is searchable by an integer key.

public class RandomObject implements BinarySearchableByKey<Integer> {
    // ...

    @Override
    public Integer getKey() { return value; }
}

Change search to have two type parameters - the array's type, and the search key type:

public static <K extends Comparable<? super K>, T extends BinarySearchableByKey<? extends K>> int search(T[] a, K value) {
    int start = 0, end = a.length - 1;
    do {
        int mid = start   (end - start) / 2;
        if (a[mid].getKey().compareTo(value) == 0) {
            return mid;
        } else if (a[mid].getKey().compareTo(value) > 0) {
            end = mid;
        } else {
            start = mid   1;
        }
    } while (start < end);
    return -1;
}

CodePudding user response：

If both methods require T[] and I am providing RandomObject[] for both cases

The binary search argument requires two things: a T[] and a T.

You are providing a RandomObject[] and an Integer. Those aren't the same T. Your binary search method would expect a RandomObject[] and a RandomObject.