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;
}

• Simon Forsberg: What if the same element satisfies both condition1 and condition2, should that return true or false?
• Captain Man: @Simon They're mutually exclusive.
• Simon Forsberg: @CaptainMan Not when looking at the method as a general-purpose one.
• Captain Man: @Simon Shall I rename the method isItemWithMutuallyExclusiveConditionBeforeAnother?
• Simon Forsberg: @CaptainMan Okay, probably not :) It seems like it doesn't matter how the case when they are at the same index should be handled.

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.

• maaartinus: Your second approach took me a while to see that no condition gets evaluated twice. Your first approach is nice, a bit clever as already said, but it does the condition evaluation first and then works with foundX only, which makes it simple again. Nice.
• Captain Man: I understand generics but when it comes to ? extends Foo and ? super Foo I get a little lost. What's the difference between (Predicate<T> condition, List<? extends T> list) and (Predicate<? super T> condition, List<T> list)?
• Simon Forsberg: @CaptainMan I hope reading this will help: stackoverflow.com/q/2723397/1310566 . In your case, as you have two predicates, using Predicate<? super T> will allow one Predicate to be of one type, and the other Predicate to be of another type. If you do Predicate<T> and List<? extends T> then both Predicates must have the same T for their generic parameter.
• Captain Man: I forget PECS is from the point of view of the Collection usually. Suppose there is only one condition though, how would this behave?

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;

• Simon Forsberg: You can do cleaner than that, janos!
• janos: That's arguable ;-)
• Simon Forsberg: See bottom part of my answer for what I consider cleaner at least, using only booleans.
• janos: Your implementations are shorter. But a bit clever, which hurts understandability. Mine is straight and simple, and as such, I think it's cleaner. Not that it matters though. As far as I'm concerned, our answers are practically duplicates. I didn't post mine to compete with yours (it's not better), but because I already wrote it when I saw yours, and since it does differ by a nuance, I posted anyway to share, rather than discard.
• Simon Forsberg: Yeah I definitely think that you should keep your answer around. Just because I don't like that way doesn't mean that nobody else will, of course.