Checking if an element sastifying a condition in a list comes before another of a different condition

Question

This is for Java 6 and uses Guava.

It's a little ugly and I'm worried I missed some obvious way to do it a lot better.

1. If there is more than one element satisfying either condition I am saying it's false because the condition I am checking should be unique among the list.
2. If and only if the one element satisfying condition1 is in the list with a lower index than the one element satisfying condition2 should this return true.

condition1 and condition2 will never both be true for the same element.

private static <T> boolean isItemWithConditionBeforeAnother(Predicate<T> condition1, Predicate<T> condition2, List<T> list)
{
    if (Collections2.filter(list, condition1).size() != 1 || Collections2.filter(list, condition2).size() != 1)
    {
        return false;
    }
    boolean found1 = false;
    for (T t: list)
    {
        if (!found1)
        {
            if (condition1.apply(t))
            {
                found1 = true;
            }
            else if (condition2.apply(t))
            {
                return false;
            }
        }
        else
        {
            if (condition2.apply(t))
            {
                return true;
            }
        }
    }
    return false;
}

Answer 1

Currently, you are in fact looping through the entire list three times.

1. Collections2.filter(list, condition1).size()
2. Collections2.filter(list, condition2).size()
3. for (T t: list)

This is a bit inefficient, as ultimately, once should be enough.

To accomplish that, we need to check each item exactly once (or technically, at most once, as it is possible to return false early).

Also, to make the method slightly more useful, you can use Predicate<? super T>.

Which is easiest, checking if the list does adhere to your requirements or checking if it does not? In my opinion, it is easier to check if one of your requirements fail, which means that we can have the method return true; as the last statement and perform some early returns for false if something doesn't match your requirements.

What I would end up with is this, which is pretty much straight-forward:

private static <T> boolean isItemWithConditionBeforeAnother(Predicate<T> condition1, Predicate<T> condition2, List<T> list) {
    int found1 = 0;
    int found2 = 0;
    for (T t: list) {
        if (condition1.apply(t)) {
            found1++;
        }
        if (condition2.apply(t)) {
            found2++;
        }
        if (found1 > 1 || found2 > 1) {
            return false;
        }
        if (found2 > found1) {
            return false;
        }
    }
    return found1 == 1 && found2 == 1;
}

Using the found variables as int instead of boolean helps greatly here. It lets us check if any condition has been matched twice, and lets us use the trick found2 > found1 to check if condition2 was matched before condition1.

---

Alternative approach using booleans, inspired by @janos.

boolean found1 = false;
boolean found2 = false;
for (T value : list) {
    if (found1 && condition1.apply(value)) {
        return false;
    }
    if (found2 && condition2.apply(value)) {
        return false;
    }
    found1 = found1 || condition1.apply(value);
    found2 = found2 || condition2.apply(value);
    if (found2 && !found1) {
        return false;
    }
}
return found1 && found2;

An important thing here is that once found1 is true, it will never be set to false again thanks to the short-circuiting || operator.

Answer 2

In the worst case, the method will visit all elements of the list 3 times:

• The filter pass for condition1; this also creates a throw-away list
• The filter pass for condition2; this also creates a throw-away list
• The for loop

It would be better to rewrite this to accomplish the same thing in a single pass, and without creating throw-away lists like the filtering passes do:

boolean found1 = false;
boolean found2 = false;
for (T value : list) {
    if (!found1) {
        if (condition1.apply(value)) {
            found1 = true;
        } else if (condition2.apply(value)) {
            return false;
        }
    } else if (!found2) {
        if (condition1.apply(value)) {
            return false;
        } else if (condition2.apply(value)) {
            found2 = true;
        }
    } else {
        if (condition1.apply(value) || condition2.apply(value)) {
            return false;
        }
    }
}
return true;