Counting elements meeting a predicate in an enumerable without iterating the entire sequence

Question

I was reading this question, and the answer that mentioned streams, and a thought had occurred to me.

In many cases (at least in my usage) I want to determine if a sequence (or IEnumerable) has at least a certain number of elements, or has no more than a certain number, etc, that all match a predicate.

As it stands now, we have the IEnumerable<T>.Count(Func<T, bool>) method, but it will enumerate the entire IEnumerable<T> before returning. In some cases, we know we only care if there are certain numbers of values. (Such as exactly 8.)

As a result, I've built out a set of new extension methods to IEnumerable<T>, that add some functionality for counting only as needed. That is, if we care that we only have at least n, we can now deal with that in particular.

public static class IEnumerableTCountExtensions
{
    public static bool CountAtLeast<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count == required) { break; }
            }
        }
        return count == required;
    }
    public static bool CountAbove<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count > required) { break; }
            }
        }
        return count > required;
    }
    public static bool CountEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count > required) { return false; }
            }
        }
        return count == required;
    }
    public static bool CountNotEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count > required) { return true; }
            }
        }
        return count != required;
    }
    public static bool CountBelow<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count >= required) { return false; }
            }
        }
        return count < required;
    }
    public static bool CountNoMoreThan<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = 0;
        foreach (T item in items)
        {
            if (predicate(item))
            {
                count++;
                if (count == required) { return false; }
            }
        }
        return count <= required;
    }
}

There are 6 functions: one for each of the following:

• >=: CountAtLeast;
• >: CountAbove;
• ==: CountEqual;
• !=: CountNotEqual;
• <: CountBelow;
• <=: CountNoMoreThan;

Each of them short-circuits as reasonable, to allow us to only enumerate what we have to. The short-circuit path is taken in the case that it's acceptable.

A quick set of tests, with a pass/fail for each, is:

var things = new[] { 1, 2, 3, 4, 5 }.AsEnumerable().Select(x => { Console.WriteLine(x); return x; });
Console.WriteLine("T? " + things.CountAtLeast(x => x <= 5, 2));
Console.WriteLine("F? " + things.CountAtLeast(x => x <= 5, 6));
Console.WriteLine("T? " + things.CountAbove(x => x <= 5, 2));
Console.WriteLine("F? " + things.CountAbove(x => x <= 5, 5));
Console.WriteLine("F? " + things.CountEqual(x => x <= 5, 2));
Console.WriteLine("T? " + things.CountEqual(x => x <= 5, 5));
Console.WriteLine("F? " + things.CountEqual(x => x <= 5, 6));
Console.WriteLine("T? " + things.CountNotEqual(x => x <= 5, 2));
Console.WriteLine("F? " + things.CountNotEqual(x => x <= 5, 5));
Console.WriteLine("T? " + things.CountNotEqual(x => x <= 5, 6));
Console.WriteLine("T? " + things.CountBelow(x => x <= 5, 6));
Console.WriteLine("F? " + things.CountBelow(x => x <= 5, 2));
Console.WriteLine("T? " + things.CountNoMoreThan(x => x <= 5, 6));
Console.WriteLine("F? " + things.CountNoMoreThan(x => x <= 5, 2));

The Console.WriteLine(x); is included to demonstrate that each item is only being iterated as maximally necessary, and can be removed for easier visual.

Answer 1

There are so many different solutions already that I won't post another. But there is something else that bothers me, the names of the extensions. I find they are too confusing. Expecially Above and Below. They are not very technical (at leat in this context).

I think they should be called the same way we call the conditions they are based on and that are (or should be) familiar to all developers. This means:

Two of them already folow that pattern:

CountEqual
CountNotEqual

The rest should be:

CountLessThan
CountLessThanOrEqual
CountGreaterThan
CountGreaterThanOrEqual

Answer 2

You can use the Linq Take to accomplish the same thing

public static class IEnumerableTCountExtensions
{
    public static bool CountAtLeast<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required).Count();
        return count == required;
    }
    public static bool CountAbove<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required + 1).Count();
        return count > required;
    }
    public static bool CountEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required + 1).Count();
        return count == required;
    }
    public static bool CountNotEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required + 1).Count();
        return count != required;
    }
    public static bool CountBelow<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required).Count();
        return count < required;
    }
    public static bool CountNoMoreThan<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        var count = items.Where(predicate).Take(required + 1).Count();
        return count <= required;
    }
}

The only different in enumeration is the CountNoMoreThan as the original code has a short circuit on if (count == required) { return false; } which wouldn't know if there are more just that we hit the target and return false so it would seem a less than clause and not a less than or equal to. I'm thinking this might be a bug in the original code since the return statement is doing a less than or equals.

Also should add the guard clauses like Jesse C. Slicer suggested.

Answer 3

With the help of LINQ and some helper methods, you can achieve the same with a lot less repetitive code.

How do we do it? Well we extract the foreach loop into an iterator which will return the current count of predicate matches:

private static IEnumerable<int> GetMatchingValues<T>(IEnumerable<T> items, Predicate<T> predicate)
{
    int count = 0;
    foreach (var item in items)
    {
        if (predicate.Invoke(item))
        {
            yield return ++count;
        }
    }
}

Once you have that it's a lot easier to see the pattern, most of those functions are either .Any or .All invocations, except for 1 odd case which really annoys me, perhaps someone smarter can figure it out:

public static bool CountAtLeast<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return GetMatchingValues(items, predicate).Any(count => count == required);
}

public static bool CountAbove<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return GetMatchingValues(items, predicate).Any(count => count > required);
}

public static bool CountEqual<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    int finalCount = 0;
    foreach (int count in GetMatchingValues(items, predicate))
    {
        finalCount = count;
        if (finalCount > required) { break; }
    }
    return finalCount == required;
}

public static bool CountNotEqual<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return !CountEqual(items, predicate, required);
}

public static bool CountBelow<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return !GetMatchingValues(items, predicate).Any(count => count >= required);
}

public static bool CountNoMoreThan<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return GetMatchingValues(items, predicate).All(count => count != required);
}

Answer 4

Two minor recommendations:

1. Rename items to source to be in-line with how LINQ does it.

2. Add parameter checking to the beginning of the methods as LINQ does:

       if (source == null)
       {
           throw new ArgumentNullException(nameof(source));
       }
   
       if (predicate == null)
       {
           throw new ArgumentNullException(nameof(predicate));
       }
   

And it looks solid!

ETA: Given the other super-cool answers, adding in the magic of C#7, I've refactored a little bit:

public static class IEnumerableTCountExtensions
{
    public static bool CountGreaterThanOrEqual<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required).Count() == required);

    public static bool CountGreaterThan<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required + 1).Count() > required);

    public static bool CountEqual<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required + 1).Count() == required);

    public static bool CountNotEqual<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required + 1).Count() != required);

    public static bool CountLessThan<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required).Count() < required);

    public static bool CountLessThanOrEqual<T>(this IEnumerable<T> source, Func<T, bool> predicate, int required) => source == null
        ? throw new ArgumentNullException(nameof(source))
        : (predicate == null
            ? throw new ArgumentNullException(nameof(predicate))
            : source.Where(predicate).Take(required + 1).Count() <= required);
}

Answer 5

The action which is taken if the if condition is true isn't consitent. Sometimes you return out of the if and sometimes you break out of the loop althougth you could do it the same way.

E.g

In CountAbove you break if count > required to return count > required but in CountEqual you return false if count > required and if that if condition is never evaluated to true you return count == required.

---

You could use some pre-check to make sure you won't need to iterate at all by soft-casting the IEnumerable<T> items to an ICollection<T>/ICollection and if the soft-cast succeed you can check the Count property.

You may say but what about the predicate? Well e.g. for CountAbove the Count property of the ICollection<T>/ICollection needs to be at least greater than required like so

public static bool CountAbove<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
{
    ICollection<T> collectionOfT = items as ICollection<T>;
    if (collectionOfT != null && collectionOfT.Count <= required) { return false; }
    ICollection collection = items as ICollection;
    if (collection != null && collection.Count <= required) { return false; }

    var count = 0;
    foreach (T item in items)
    {
        if (predicate(item))
        {
            count++;
            if (count > required) { break; }
        }
    }
    return count > required;
}

Answer 6

This is a variation on Denis' answer. While his answer works, it is returning a progressive count (1,2,3,4,5) for no good reason. In the end, you're only interested in the last number (5) that is returned, so there is no point to wrapping the count in an IEnumerable.

Furthermore, because of the combined use of logical inversions, Any and All, Denis' code (while it does work) becomes quite hard to quickly read through. There is a difference between e.g. !myList.All(x => x == myValue) and myList.All(x => x != myValue), but the distinction is hard to miss here.

Comparatively, the distinction between myCount == myValue and myCount != myValue is much easier to parse at a glance, which is why I think my answer is better from a readability standpoint (even though it is functionally equivalent, which I do concede).

---

The counting algorithm

private static int CountMatchesUpTo<T>(IEnumerable<T> items, Predicate<T> predicate, int boundary)
{
    int count = 0;
    foreach (var item in items)
    {
        if (predicate.Invoke(item))
        {
            count++;
        }

        if(count == boundary)
        {
            break;
        }
    }

    return count;
}  

There are two possible ways that the return statement can be reached:

• Because the foreach completed. This happens if you have less than boundary matches in your list, since you keep looking for matches up to the boundary.
• Because the boundary was reached. At this point, the foreach is forcefully broken out of, and the count (equal to boundary) is returned. The remaining items of the list were never iterated over.

---

The wrapper methods

The implementation of most of the other methods is relatively easy to do.

Notice that in some cases, I use required + 1 as the upper bound. This is relevant in cases where you want to distinguish between a match count that is either equal to or greater than the boundary.

Assuming you're using a boundary of 5, you then instruct the counting method to look for 6 items.

• If it returns 6, then you know that there are more than 5 matches.
• If it returns 5, then you know that there are exactly 5 matches (the same applies for a smaller return value).

This takes care of the "upper" short circuit. The "lower" short circuit is already taken care of as you will receive a lower number if not enough matches were found.

public static bool CountEqual<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required + 1) == required;
}

public static bool CountNotEqual<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required + 1) != required;
}

public static bool CountAbove<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required + 1) > required;
}

public static bool CountAtLeast<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required) == required;
} 

---

public static bool CountBelow<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
{
    var count = 0;
    foreach (T item in items)
    {
        if (predicate(item))
        {
            count++;
            if (count >= required) { return false; }
        }
    }
    return count < required;
}

public static bool CountNoMoreThan<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
{
    var count = 0;
    foreach (T item in items)
    {
        if (predicate(item))
        {
            count++;
            if (count == required) { return false; }
        }
    }
    return count <= required;
}

There are two things to notice here:

1 - In one method, you do if (count >= required) { return false; }, and in the other, you do if (count == required) { return false; }. Since count is incrementing one at a time, count >= required will evaluate to true because it count is equal to required. Count will never be greater than required since you exit the method when it already equals it.

2 - CountNoMoreThan is also unintuitive for another reason: you do if (count == required) { return false; } and then return count <= required;.
The return statement will never find a case where count equals required, since you've already explicitly returned false when you find an equality. The return statement can therefore be refactored to return count < required;.

Combining the findings of 1 and 2, this means that CountBelow and CountNoMoreThan are currently functionally equivalent methods. There's no point to having both methods.

From the method names, I surmise that the difference between the two is < or <=. Using my refactored approach, the difference is easy to implement:

public static bool CountNoMoreThan<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required + 1) <= required;
}

Note that we again use required+1, to allow for the count method to tell us if there are more matches than the boundary.

public static bool CountBelow<T>(this IEnumerable<T> items, Predicate<T> predicate, int required)
{
    return CountMatchesUpTo(items, predicate, required) < required;
}

---

Footnote

As it stands, all the listed methods are merely an enumeration of int comparisons: ==, !=, >, >=, <, <=.

There is little point to doing this. You can simply make CountMatchesUpTo a publically accessible method, and rely on your caller to do their own evaluation.

If you're already expecting your caller to know which method to use, that means that they know which evaluation they want to take place. There is no added benefit from putting it in an additional method layer.

If you're doing more cumbersome logic (e.g. checking if two datetimes overlap), that is relevant to put into a method, as it would be cumbersome to write every time. But your current evaluations are not complex enough to warrant their own method layer.

The issue here is that your additional layer is an additional place for bugs to sneak into the code. And it already did, as I found a bug in CountNoMoreThan. If uncaught, external consumers of your methods would be hunting for bugs in their own code, unaware that your method is simply not doing what its name advertises.

---

Update

Update is not correct. See below.

Two of your tests appear to be incorrect:

Console.WriteLine("F? " + things.CountEqual(x => x <= 5, 2));
Console.WriteLine("T? " + things.CountNotEqual(x => x <= 5, 2));

Since you set the boundary at 2, the "count up to" algorithm will logically stop iterating over the collection once it reaches a count of 2.

This means that things.CountEqual(x => x <= 5, 2) will return true, and things.CountNotEqual(x => x <= 5, 2) will return false.

Your test seemingly expects that the counting method will still count 5 elements; which violates the algorithm (as it should stop after the defined boundary, which in this case is 2).

It's an easy mistake to make; one that I had initially glossed over too, as I understood what you were trying to test. But the expected outcome of these two tests should be inverted; otherwise it would violate your proposed algorithm.

Update to the update

The requirements were clarified by OP in chat. The above code has been altered to reflect that.

Answer 7

A method that returns a count and stop at a target count can do all that logic.
I like more mathematical names.

public static class IEnumerableTCountExtensions
{
    private static int CountMatchingStopAt<T>(IEnumerable<T> items, Func<T, bool> predicate, int stopAt)
    {
        int count = 0;
        foreach (var item in items)
        {
            if (predicate.Invoke(item))
            {
                count++;
                if(count == stopAt)
                {
                    break;
                }
            }
        }
        return count;
    }
    public static bool GreaterThanOrEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required + 1) >= required;
    }
    public static bool GreaterThan<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required + 1) == required + 1;
    }
    public static bool Equal<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required + 1) == required;
    }
    public static bool NotEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required + 1) != required;
    }
    public static bool LessThan<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required) < required;
    }
    public static bool LessThanOrEqual<T>(this IEnumerable<T> items, Func<T, bool> predicate, int required)
    {
        return CountMatchingStopAt(items, predicate, required + 1) <= required;
    }
}

Answer 8

Each of them short-circuits as reasonable, to allow us to only enumerate what we have to. The short-circuit path is taken in the case that it's acceptable.

Not quite. There are some missing corner cases when required <= 0 (or required < 0 for the exact test).