5

I have been using Collections.max(list) for many projects, but I occasionally want to find the index of that maximum element. I feel silly writing a function to do this for myself in every program I write.

Why does the Collections Interface not supply a Collections.maxIndex(list)?

  • This is precisely why C++ has an algorithms library, and you can write your own. Seems like it should be easy enough to write a general algorithm that takes a List<T extends Comparable> and a Lambda, returning the index of the first element that meets the criteria of the Lambda (similar to a FileFilter). – user22815 Sep 30 '14 at 21:44
16

While there can be exactly one max value in a collection, there can be more than item representing that value. E.g {1, 9, 2, 9, 0} has max value of 9, represented by both elements [1] and [3].

Note that not all collections support index access; e.g. a Set<Integer> can have a meaningful maximum but accessing an element by index makes no sense in it.

Even if we limit the method to List, it would be a bit hard to come up with one method to find indices of the maximum value that is not clumsy. You could return a list of indices, but then you'd lose the value, and in some collections, e.g. linked lists, accessing an element by index is slow. Since Java does not have an easy syntax for tuples, you'd have to return a special type of object with .getValue() and .getIndices().

But I think that such an operation is just not common enough to be supported in the standard library. Finding a maximum is literally 3-4 lines of code, and tracking the index is another 1-2 lines, and there's no much room to do it wrong. If you do it a lot, you can easily put it in your own utility class.

  • ... or extend the interface List and an associated implementation class. – user40980 Sep 28 '14 at 1:33
  • 5
    Note also that not all Objects are Comparable, so a maxIndex function would also have to take a Comparator in the general case. – amon Sep 29 '14 at 9:41
2

Please take a look at Java 8 Streams API.

Link: http://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

(Disclaimer: I haven't used it before.)

However, there's no out-of-the-box implementation of maxIndex. To enable that, someone will have to provide a high performance primitive pair or tuple stream implementation for Java 8 Streams.

The reason is this. Functionally speaking, maxIndex is:

  • Convert each value into a pair (tuple of 2) as: (value, position)
  • Reduce the stream as follows:
    • Compare the two items, (value1, position1) with (value2, position2),
    • Keep the item with the higher value, and copy along its position.
      • Namely, return (item1.value > item2.value) ? item1 : item2;
    • If a tie is possible, a tie-breaking mechanism is also needed, as pointed out in 9000's answer. It will no longer be a reduction over the tuple, but will become a "collection of (value, position) tuples all having the same maximum value".
      • As long as a tie-breaking mechanism is implemented, the approach outlined here will still be applicable.
  • At the end of operation, return item.value as the maximum value, and item.position as the maximum index.
    • As pointed out by 9000's answer, depending on the tie-breaking mechanism, there may be multiple results.

Unfortunately, as many Java advocates have pointed out, Java as a language is experiencing from an explosion of class-happiness, and this is due to the limitation of Java generics support. As a result, if you need anything not found in Java API, you have to roll your own, or find a library or toolbox that does.

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.