Generic methods to find the maximal element in part of a list

Question

This is the question from Oracle docs:

Write a generic method to find the maximal element in the range [begin, end) of a list.

I had my implementation like this:

    public static <T extends Comparable> T maximalElement (List<T> list, int from, int to) {
        T max = list.get(from);
        for (int i = from + 1; i < to; i++) {
            T elem1 = list.get(i);
            if (elem1.compareTo(max) > 0) {
                max = elem1;
            }
        }
        return max;
    }

When I viewed the answer, it was something like this:

     public static <T extends Object & Comparable<? super T>> T max (List<? extends T> list,
                                                                    int begin, int end) {

        T maxElem = list.get(begin);

        for (++begin; begin < end; ++begin) {
            if (maxElem.compareTo(list.get(begin)) < 0) maxElem = list.get(begin);
        }
        return maxElem;
    }

So, I got the results running like this:

        List<Integer> c = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        System.out.println(Test.maximalElement(c, 3, 8));
        System.out.println(Test.max(c, 3, 8));

Results are same, so I am quite excited that my version of generics is more simpler than one implemented in the answer. So, I want to check if my implemented version is really simpler and okay or am I not seeing something? Because oracle developers are not dumb enough to complex things out for nothing.

So, can you experts please help me understanding the difference or scenarios where my implemented version fails?

Answer 1

I'd just say to go with your implementation; just because it is easier to read! Also, you only .get() from the list once, whereas the proposed solution does it twice.

Shorter is not a synonym for better!

However, the generics are not good; you should at least use <T extends Comparable<? super T>>. Not sure why the proposed solution uses Object as a lower bound...

Answer 2

The extends Object bound in the reference solution is completely useless, since there are no types for which this isn't true. (Primitives don't count, they can't be generic arguments.)

Making the parameter List<? extends T> instead of List<T> will rarely be useful; the most important part of that is that it allows another generic function that has a good reason to have a List<? extends T> to call your function. (However, even that can be worked around by simply giving that other function an explicitly named type parameter for that ?.)

The most important change is that Comparable alone is a raw type and shouldn't be used that way; Comparable<? super T> is clearly better. I personally would find Comparable<T> acceptable as well, because IMO classes that implement Comparable should not be derived from anyway.

I prefer your use of a dedicated loop variable over the reuse of the argument in the reference solution; much more readable, especially the initialization. I also prefer your caching of the result of get(). At least this way, if someone passes a LinkedList, your version will do half as many walks over the list. (It will still be quadratic though.)

A better implementation would just take a List and no indices, and then use an iterator to traverse the list. Then you can implement the version with indices by simply calling the basic version with a subList() of the argument.

An even better implementation would have a version that takes a Comparator to compare elements instead of just working with Comparable objects. Then you can implement the version without a comparator by just passing a natural order comparator (Comparator.naturalOrder() in Java 8).

Finally, it's sometimes useful if ordering-related algorithms are "stable", which means that when multiple elements are considered equivalent, those earlier in the sequence should be seen as lower than the later ones. When an algorithm can be stable at no additional cost, it should be. In the case of minimum/maximum, this means that if there are multiple smallest elements, the first one of those should be returned, but the last one of multiple biggest elements. Both your and the reference implementation return the first of multiple biggest elements; changing this is as easy as replacing > with >= in your check of the compareTo() result.

Answer 3

Error handling

Since this is going to be a public utility method, you should pay closer attention to error handling (unless you're told likewise in this... assignment?):

public static <T extends Comparable<? super T>> T maximalElement (List<T> list,
        int from, int to) {
    Objects.requireNonNull(list);
    if (from < 0 || to > list.size()) {
        throw new IndexOutOfBoundsException();
    }
    if (from <= to) {
        // throw or swap? or return null when from == to?
    }
}

The suggestion above opens the possibility of treating from <= to cases differently from the usual IndexOutOfBoundsException. You may want to just swap the indices, or optionally return null when both are equal.

Alternative

You can consider iterating through a subList() of the input List as such:

public static <T extends Comparable<? super T>> T maximalElement (List<T> list,
        int from, int to) {
    T max = null;
    for (Iterator<T> iterator = list.subList(from, to).iterator(); iterator.hasNext(); ) {
        T current = iterator.next();
        if (max == null || (current != null && current.compareTo(max) > 0)) {
            max = current;
        }
    }
    return max;
}

First, the slight benefit of doing a subList() is that it does the error handling for you. Second, it removes the need for indices, which depending on the List implementation, may be more optimal (see: LinkedList).

The additional null check on current is to ensure that we do not compare with null values. Here, they will simply be skipped, but you may want to consider a more stringent version that rejects the List outright by throwing an Exception at this point.

Readability

Whether one does a current.compareTo(max) > 0 or max.compareTo(current) < 0 is just down to one's interpretation (and thus readability). Since the task is to find the maximal element, I will tend to think in terms of 'great-ness', and thus prefer your version that uses the greater-than sign.

Alternative (Java 8)

As usual, if you happen to be on Java 8, stream-based processing saves the day with less verbosity:

public static <T extends Comparable<? super T>> T maximalElement (List<T> list,
        int from, int to) {
    return list.subList(from, to).stream()
                .max(Comparator.naturalOrder())
                .orElseThrow(IndexOutOfBoundsException::new);
}

Here, doing a Stream.max(Comparator) using a Comparator.naturalOrder() is all that's required.