Return the index of the first item in generics collections

Question

/**
 * Return the index of the first item in someCollection for which * aPredicate.test(o) is true, or -1.
 */
public static <T> int find(Collection<T> someCollection, Predicate<T> aPredicate) {
    List<T> list = new ArrayList<>();
    for (Iterator<T> iterator = someCollection.iterator(); iterator.hasNext(); ) {
        T value = iterator.next();
        if (aPredicate.test(value)) {
            list.add(value);
        }
    }
    return list[0]; // or return list.get(0)
}

With the code above, I cannot use list[0] since it needs to be replaced with list.get(0), but this method is only applicable to the collection of Integers. How can I return the index of the first element in such case?

If the intention is to return the first index found of the matching item, why store indices in a list at all? Why not replace `list.add(value)` with `return value`? — Abion47, Oct 21 '20 at 17:04
Not every Collection has indexes to begin with. So trying to write a method that gives you the first index from any Collection is an impossible task. If would work with List instead of Collection, but the List interface already has a method `indexOf` so there is no need for you to write it yourself — OH GOD SPIDERS, Oct 21 '20 at 17:04
@OHGODSPIDERS In fairness, `indexOf` doesn't accept an arbitrary `Predicate`. — Louis Wasserman, Oct 21 '20 at 17:08
@LouisWasserman Fair enough. Still doesn't change the fact that getting indexes from any Collection can ultimately not work when not every collection has indexes or even a stable iteration order. The JavaDoc for HashSet says in one of the first sentences: *" It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time."* - So even when you try tricks like counting the calls of iterator.next() to somehow simulate an index, you'll only end up tricking yourself and introducing potential problems. — OH GOD SPIDERS, Oct 21 '20 at 17:13

score 1 · Accepted Answer · answered Oct 21 '20 at 17:29

The purpose of your function is to return the first index of the first element in a Collection that matches the given Predicate. As such, not only should you be storing a List<int> rather than a List<T>, there's no reason to be storing a list at all if the point is to return the first thing found. As such, remove the buffer list entirely and return as soon as you find a matching element.

public static <T> int find(Collection<T> someCollection, Predicate<T> aPredicate) {
    // Collections don't necessarily natively support indices, so you must 
    // manually track the current index
    int index = 0;
    for (Iterator<T> iterator = someCollection.iterator(); iterator.hasNext(); ) {
        T value = iterator.next();
        if (aPredicate.test(value)) {
            // A matching element was found, so there's no point continuing to loop
            return index;
        }
        index++;
    }
    // No element was found, so return the conventional -1
    return -1;
}

@Eugene This answer directly addresses the question as asked by OP, nothing more. It has already been said by other commenters that it's largely nonsensical to get the index of an element in a non-indexed collection anyway, so discussing the behavior of said operation on such collections would be mostly academic in nature. — Abion47, Oct 21 '20 at 19:30
fair enough. This academic problem would not be a problem at all if java had a marker interface for ordered collections (like `RandomAccess`)... — Eugene, Oct 22 '20 at 01:23

score 0 · Answer 2 · answered Oct 21 '20 at 17:09

0

What you want isn't to store a List<T>, but a List<Integer>, essentially, containing the index of the elements you found. You will have to track that index yourself, but tracking how many calls to iterator.next() you have made.

answered Oct 21 '20 at 17:09

Louis Wasserman

191,574
25
345
413

I have to use generics because `find` supposed to work with Collection of any type, e.g. not only Integers but Strings as well. – feedthemachine Oct 21 '20 at 17:14
@feedthemachine: I understand that. Nevertheless, what I said is true. Your method should _accept_ a `List`, but `list` should still be a `List` in your code. – Louis Wasserman Oct 21 '20 at 17:37

score 0 · Answer 3 · answered Oct 21 '20 at 19:42

Let's first make sure your method does the correct thing:

public static <T> int find(Collection<T> someCollection, Predicate<T> aPredicate) {
    int i = -1;
    for (Iterator<T> iterator = someCollection.iterator(); iterator.hasNext();) {
        ++i;
        T value = iterator.next();
        if (aPredicate.test(value)) {
            return i;
        }
    }
    return -1;
}

Let's see if it works:

public static void main(String[] args) {
    List<Integer> list = List.of(1, 2, 3);
    System.out.println(find(list, x -> x == 4)); // -1
    System.out.println(find(list, x -> x == 2)); // 1
}

It does, but is it correct?...

public static void main(String[] args) {
    Set<String> set = Set.of("abc", "ade");
    System.out.println(find(set, "abc"::equals));
}

Run this a few times (with java-9) and be surprised how the index will change. A Set does not have any order and immutable collections added in java-9 do some internal randomization when they are first created, so the results might get entirely incorrect. For a broader read, look here.

You could think that java has a common interface for when a certain Collection would be ordered or not, but it does not. So you can't really do much, other then rethink what you want to do, may be.

Return the index of the first item in generics collections

3 Answers3