Best way to find whether a collection does or does not contain an element with a specific desired quality

Question

It seems to be a very common thing to have to tell whether some list or set contains at least one object matching a given condition, yet my prior searching and reading have never found a satisfactory best practice or design pattern to speak of. In the situations I am thinking of, merely using "contains" is not sufficient, as the test we want to perform is not strictly based on the equals method of the class in question.

Some things I have seen:

// for-each with break
private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    boolean foundIt = false;
    for (Foo item: candidates) {
        if (<< item passes some test >>) {
            fountIt = true;
            break;
        }
    }
    return foundIt;
}   

// while-do with index counter
private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    boolean foundIt = false;
    int index = 0;
    while(!fountIt && index < candidates.size() - 1) {
        Foo item = candidates.get(index++);
        if (<< item passes some test >>) {
            fountIt = true;
        }
    }
    return foundIt;
}

Both of these get the job done and quit as soon as a success is found, possibly saving some time if we are lucky enough to have the desired item early in the list. However, both require looping the entire list in order to get a false result

Another technique I've seen in some circumstances is that at the same time the original List<Foo> is generated (i.e. retrieved from database) to then simultaneously generate a Map<FooKey, Foo>. In this technique, FooKey is an additional (often inner) class holding only those attributes of a Foo that form the "desired quality" and overrides equals and hash code methods based on that. When you need to determine if there exists a desired Foo, you make a new FooKey() instance with exactly that you want, then call hasKey() on the map. Extra effort up front, but quick and easy at the moment you need it.

I can't put a finger on it. Each idea works, yet each feels just a little hacky and inefficient.

Answer 1

Algorithmically, the for-each and the while-with-indexing version implement linear search. This is okay for small collections or when you only do such a check very occasionally, but if it's an important building block of your program, you'd want a dedicated mapping structure which speeds up these queries by doing something fundamentally different from linear search. Examples include binary search trees (where you need to define a consistent ordering) and hash tables (where you need to define a consistent hash function). For most predicates this is trivial, for others it would be some extra code (defining FooKey), and for yet others it is hard or completely impractical. This is a judgement call depending on the criteria by which you search.

When you've decided on linear search, there are several options to implement it (provided there isn't already a good implementation — if so, prefer that!). The for-each variant is quite general and IMHO elegant: It works with any iterable, it doesn't even have to be backed by a concrete collection (cf. streams in Java 8). The while loop with indexing, on the other hand, is very restricted: It's offensively slow for containers that can't do random access (e.g. linked lists), and it doesn't work at all for things that can't be indexed. I would never recommend this one. There are probably other variations, but they are even more specialized. If you implement linear search, implement it for iterables.

Another issue is how you supply the predicate. You could write essentially the same loop again and again with only the condition different. But this is error prone, verbose, and inefficient. There should be only one copy of this loop, with the condition being passed as parameter. If your language (version) can do this, use a first-class function/lambda. Otherwise, you could emulate it with an interface and anonymous classes. Once you do this, Maps lose some of their appeal: It's no longer a long loop versus map.get(whatIWant), it's list.find(whatIWant). Of course they still have a performance benefit for large collections.

Side note: The loops can be slightly simpler, for example I'd write the for-each loop as:

private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    for (Foo item: candidates) {
        if (<< item passes some test >>) {
            return true;
        }
    }
    return false;
}

Answer 2

Both your suggestions are unnecessarily verbose, and the input type is too specific. Prior to Java 8 I would write:

private boolean doFoosHaveGoodQuality(Iterable<Foo> candidates) {
    for (Foo item: candidates) {
        if (<< item passes some test >>) return true;
    }
    return false;
}

With Java 8 these boring loops are unnecessary:

private boolean doFoosHaveGoodQuality(Collection<Foo> foos) {
    return foos.stream().anyMatch(foo -> ... some test ... );
}

Answer 3

When your problem doesn't have a good solution, solve a different problem.

Instead of iterating over the collection, wrap that collection in another class that tracks the information you want whenever elements are added or removed. Don't make the mistake of assuming that Java's provided collection interfaces satisfy all the needs that you'll meet.

For the basic case, your new class will have two objects: the original List and a new Set field for the property you care about. This, of course, assumes that you are only querying a small number of properties.

This means that you must never allow mutating operations on the inner containers. There are some utility functions in java.util.Collections to return an unmodifiable view of various collections, to ease porting your callers, but if mutating e.g. through an Iterator is a feature that some of your callers use, you'll need to implement that.