Java 8 Stream indexOf method based on predicate

Question

I just encountered the situation that I needed to know the index (position) of an element inside a list, but only had a predicate expression to identify the element. I had a look for a Stream function like

int index = list.stream().indexOf(e -> "TESTNAME".equals(e.getName()));

but to no avail. Of course, I could write it like this:

int index = list.indexOf(list.stream().filter(e -> "TESTNAME".equals(e.getName()))
    .findFirst().get());

But this would a) iterate over the list twice (in the worst case that the element would be the last one) and b) would fail if no element matches the predicate (where I would prefer a -1 index).

I wrote a utility method for this functionality:

public static <T> int indexOf(List<T> list, Predicate<? super T> predicate) {
    int idx = 0;
    for (Iterator<T> iter = list.iterator(); iter.hasNext(); idx++) {
        if (predicate.test(iter.next())) {
            return idx;
        }
    }

    return -1;
}

But as this seems to be a really trivial algorithm, I would have expected it somewhere in the Java 8 Stream API. Did I just miss it, or is there really no such function? (Bonus question: In case there is no such method, is there a good reason? Is working with the index in functional programming perhaps an anti-pattern?)

Iterate over the elements instead of indexing ... if `list` does not have O(1) access, you are turning this into an O(N^2) algorithm instead of O(N) — MFisherKDX, Apr 09 '18 at 14:40
@BheshGurung No, not in the meaning that an indexed access should be possible (`get(23)`). But asking for the *position* of an element in a stream seems, at least in my case, not completely absurd. — Florian Albrecht, Apr 09 '18 at 14:40
@MFisherKDX Good hint, you are absolutely right. Will edit - although I am looking for a more elegant solution anyway... — Florian Albrecht, Apr 09 '18 at 14:42
Stream is per definition not ordered and as a such has no notion of concept such as 'position of an item'. Beware also the difference between index of any matching item / distinct item and first matching item. — Michal, Apr 09 '18 at 14:43
Streams aren't indexed, so I doubt you'll find a more-elegant solution unless you change your data type to a `Map` or something. — Jacob G., Apr 09 '18 at 14:46
@Michal Well, `stream().ordered()` **is** ordered, and - had you had a look in the Javadoc of `Stream.findFirst()`? — Florian Albrecht, Apr 09 '18 at 14:46
@JacobG. I mean *elegant* in the sense of readability, not performance... As there is `findFirst()`, there is no technical reason why there shouldn't be a method like `countUntilEncounterFirst()` (what would be an `indexOf`). — Florian Albrecht, Apr 09 '18 at 14:48
Well, there's `Stream#dropWhile` in Java 9, but you'd still have to use an `IntStream` to get the *index*. — Jacob G., Apr 09 '18 at 14:49
@JacobG. Interesting hint! `dropWhile(e -> !"TESTDATA".equals(e.getName())).count()` would do the trick, wouldn't it? Unfortunately, I am bound to Java 8... — Florian Albrecht, Apr 09 '18 at 14:53
@Florian Albrecht: The JavaDoc states the findFirst() returns any matching item unless the stream has encounter order. — Michal, Apr 09 '18 at 14:53
IMHO, your static utility, with a for and if, is elegant and readable. It will never be more readable than that with the stream APIs. — Bhesh Gurung, Apr 09 '18 at 14:55
@JacobG. Yes, but `takeWhile()` would, wouldn't it? My fault... — Florian Albrecht, Apr 09 '18 at 14:55
@JacobG. Ah, understood now. Sorry, read the Javadoc too fast. — Florian Albrecht, Apr 09 '18 at 14:56
@FlorianAlbrecht Thinking about it, I think using `Stream#dropWhile` will work if you subtract the resulting `Stream#count` from `List#size`, but it's unfortunate that you're limited to Java 8. — Jacob G., Apr 09 '18 at 15:10
@JacobG. And still, that would not *directly* help my fellow developer colleagues to understand the code ;-) — Florian Albrecht, Apr 09 '18 at 15:11

Holger · Accepted Answer · 2019-07-10T12:49:15.023

Your loop is not bad, but you can simplify it:

public static <T> int indexOf(List<T> list, Predicate<? super T> predicate) {
    for(ListIterator<T> iter = list.listIterator(); iter.hasNext(); )
        if(predicate.test(iter.next())) return iter.previousIndex();
    return -1;
}

You can use a stream like

public static <T> int indexOf(List<T> list, Predicate<? super T> predicate) {
    return IntStream.range(0, list.size())
        .filter(ix -> predicate.test(list.get(ix)))
        .findFirst().orElse(-1);
}

but this will become quite inefficient if the list is large and not random access. I’d stay with the loop.

Starting with Java 9, there’s the alternative

public static <T> int indexOf(List<T> list, Predicate<? super T> predicate) {
    long noMatchPrefix = list.stream().takeWhile(predicate.negate()).count();
    return noMatchPrefix == list.size()? -1: (int) noMatchPrefix;
}

which is really expressive regarding the task “count the elements up to the first match”, but is not exactly the same as “get the index of the first matching element”, which shows when there is no match, so we need to replace the result with -1 then.

Thanks for the simplification! Good idea to use `listIterator()`. Still, I would love to have such a simple API available on the Stream or List interface... — Florian Albrecht, Apr 10 '18 at 07:43

Jacob G. · Answer 2 · 2018-04-09T15:22:54.097

2

I'd say a simple solution would be to use an IntStream:

IntStream.range(0, list.size())
         .filter(i -> Objects.nonNull(list.get(i)))
         .filter(i -> "TESTNAME".equals(list.get(i).getName()))
         .findFirst()
         .orElse(-1);

Filtering out null elements will prevent this from throwing a NullPointerException.

edited Apr 09 '18 at 15:22

answered Apr 09 '18 at 14:27

Jacob G.

28,856
5
62
116

Hm, will definitely work, but readability is slightly limited, I'd say... Most likely I would still end up putting this in a utility method. – Florian Albrecht Apr 09 '18 at 14:31
The `null` limitation applies to my current solution as well, good hint. – Florian Albrecht Apr 09 '18 at 14:33
Thanks for letting me know, I'll edit the answer to filter out `null`s. – Jacob G. Apr 09 '18 at 14:34
1

If the list is not random access, then this is O(N²). – DodgyCodeException Apr 09 '18 at 15:00
1

Yup! And downvoters, explain yourselves! :P – Jacob G. Apr 09 '18 at 15:03
In your second code, if you filter out the nulls, you won't get the correct index. – DodgyCodeException Apr 09 '18 at 15:21
@DodgyCodeException That's funny, `null` elements would have to be mapped to something else, and I don't think it's worth it. – Jacob G. Apr 09 '18 at 15:23

score 1 · Answer 3 · answered Apr 09 '18 at 15:25

    IntPredicate isNotNull = i -> Objects.nonNull(list.get(i));
    IntPredicate isEqualsTestName = i -> list.get(i).getName().equals("TESTNAME");

    int index = IntStream.range(0, list.size())
                .filter(isNotNull.and(isEqualsTestName))
                .findFirst()
                .orElse(-1);

score 1 · Answer 4 · answered Apr 09 '18 at 15:53

The reason is that the concept of an "index" only has meaning in an "ordered Collection". A Stream can come from any Collection such as a Set; having an "indexOf" method would essentially mean giving the source Set a get(int index) operation. Not to mention that a Stream can also come from any other source but a collection.

Another reason is that the implementation of an indexOf operation is that it basically requires a stateful Visitor of the Streams element type; stateful because it has to count the members it already has visited. Stateful operations and Streams don't match well.

As for your utility function, I don't see why you'd write it your way and not like this:

static <T> int indexOf(List<T> findIn, Predicate<? super T> pred) {
    for (int i = 0; i < findIn.size(); i++) {
        if (pred.test(findIn.get(i))) {
            return i;
        }
    }
    return -1;
}

Java 8 Stream indexOf method based on predicate

4 Answers4