Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 7 down vote accepted

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...

share|improve this answer
1  
I really liked the idea of `T extends Comparable<? super T>> since it will help checking the safety that Comparable is atleast a subtype of T ;) Thanks a lot @fge – ssc Mar 30 at 17:25
3  
The Object lower bound is preserve binary compatibility. Bit of a dirty hack and not necessary in modern code, but very common in the Java Collections API. – Boris the Spider Mar 30 at 20:41

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.

share|improve this answer
    
>= will make execution of assignment to max statement more, in case of duplicates in the provided collection. So, I think, the first one biggest should be given priority for such algorithms. – ssc Mar 30 at 20:02
    
I realized my answer shares a lot in common with yours, perhaps I should have read it in greater details first... – h.j.k. Mar 31 at 3:37
    
@ssc Assigning a reference to a local variable is so cheap (a register move) as to be irrelevant. The real performance issue is that you'll get more branch mispredictions. I still think it's worth it. – Sebastian Redl Mar 31 at 7:42
    
Extends object has an effect. It changes what type T is replaced with after type erasure, which impacts backwards compatability. See Boris the Spiders comment to fge's answer. – Taemyr Mar 31 at 12:11
    
To avoid any potential problems with using >= rather than > you can simply start counting at the last element and go backward. Not that I would worry much about performance difference of the two comparisons. – Taemyr Mar 31 at 12:13

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.

share|improve this answer
1  
I like your discussion of error handling and the stream version. – Sebastian Redl Mar 31 at 7:47
1  
This is not any assignment. I am just practicing generics. And thanks for pointing out error handling, although, in real applications, I will definitely never forget ;) – ssc Mar 31 at 8:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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