3
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • \$\begingroup\$ What if the same element satisfies both condition1 and condition2, should that return true or false? \$\endgroup\$ Jul 29, 2015 at 22:08
  • \$\begingroup\$ @Simon They're mutually exclusive. \$\endgroup\$ Jul 29, 2015 at 22:21
  • 1
    \$\begingroup\$ @CaptainMan Not when looking at the method as a general-purpose one. \$\endgroup\$ Jul 29, 2015 at 22:25
  • \$\begingroup\$ @Simon Shall I rename the method isItemWithMutuallyExclusiveConditionBeforeAnother? \$\endgroup\$ Jul 30, 2015 at 14:15
  • 1
    \$\begingroup\$ @CaptainMan Okay, probably not :) It seems like it doesn't matter how the case when they are at the same index should be handled. \$\endgroup\$ Jul 30, 2015 at 15:36

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – maaartinus
    Jul 30, 2015 at 6:02
  • \$\begingroup\$ 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)? \$\endgroup\$ Jul 30, 2015 at 14:19
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 30, 2015 at 15:35
  • \$\begingroup\$ I forget PECS is from the point of view of the Collection usually. Suppose there is only one condition though, how would this behave? \$\endgroup\$ Jul 30, 2015 at 17:42
3
\$\begingroup\$

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;
\$\endgroup\$
5
  • \$\begingroup\$ You can do cleaner than that, janos! \$\endgroup\$ Jul 29, 2015 at 21:57
  • \$\begingroup\$ That's arguable ;-) \$\endgroup\$
    – janos
    Jul 29, 2015 at 21:58
  • \$\begingroup\$ See bottom part of my answer for what I consider cleaner at least, using only booleans. \$\endgroup\$ Jul 29, 2015 at 22:05
  • \$\begingroup\$ 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. \$\endgroup\$
    – janos
    Jul 29, 2015 at 22:31
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 29, 2015 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.