18
\$\begingroup\$

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.

\$\endgroup\$
13
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Totally agree, I screwed the pooch on that one. :) \$\endgroup\$ – Der Kommissar May 3 '18 at 11:40
16
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ MoreLinq is also available. It contains AssertCount, AtLeast and AtMost. \$\endgroup\$ – Dan Friedman May 3 '18 at 2:52
  • \$\begingroup\$ Doesn't an in-memory IEnumerable (i.e. not an IQueryable) iterate over the entire array directly when calling Where()? If so, that would defeat OP's purpose. Or does it still do the "IQueryable approach" (deferred execution) even if the collection is in-memory? \$\endgroup\$ – Flater May 3 '18 at 7:53
  • 5
    \$\begingroup\$ @Flater yes, execution is deferred. \$\endgroup\$ – Adriano Repetti May 3 '18 at 7:58
  • \$\begingroup\$ Aye, this is how I would do it in F#, so it makes sense to do the same here. :) \$\endgroup\$ – Der Kommissar May 3 '18 at 11:44
8
\$\begingroup\$

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);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ @Flater the iterator does not know when the end is. That's why it returns all the values. If you believe there is a cleaner approach please post an answer or add a short snippet in Fiddle and drop it here. I will be very interested in it. \$\endgroup\$ – Denis May 3 '18 at 7:32
  • 1
    \$\begingroup\$ @Flater It is effectively omitting the local variable declaration and it allows us to operate on the predicate matches as a sequence of elements instead of separate integers. It's true that only the last is important but I don't see a way of doing it otherwise, that's why I asked you to add a snippet if you know a better way of doing it. \$\endgroup\$ – Denis May 3 '18 at 7:41
  • 1
    \$\begingroup\$ @Flater The iterator is not aware of the magic number. It needs to return 1,2,3,4,5 because the iterator does not know the magic number is 5. The magic number may have been 3. \$\endgroup\$ – paparazzo May 3 '18 at 9:36
  • 1
    \$\begingroup\$ @Flater The benefit is less repeated code compared to the OP. \$\endgroup\$ – paparazzo May 3 '18 at 10:16
  • 1
    \$\begingroup\$ @Flater would you like to continue the discussion in a chat room? I feel there is some misunderstanding here. \$\endgroup\$ – Denis May 3 '18 at 10:54
7
\$\begingroup\$

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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I know this is just a style preference but I never like using ternary conditional operator for throwing. I prefer to either have the guard clause or have a static guard class that does the checking. Or even better to use code contracts. \$\endgroup\$ – CharlesNRice May 3 '18 at 13:32
5
\$\begingroup\$

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;
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ As far as I like your comments (+1) I always find this argument very weak: The issue here is that your additional layer is an additional place for bugs to sneak into the code. - I treat creating convenience extensions (or any other resusable code) always a good thing because I'm a lazy engineer ;-) sure, there might be some bugs (usually at the beginning) but you know where to find them and they are easier to test and to fix and what's even more imporatnt, you're doing this only once and when you're done, you never have to implement this logic again so it's actually a good thing. \$\endgroup\$ – t3chb0t May 3 '18 at 10:30
  • \$\begingroup\$ @t3chb0t: I'm all for convenience extensions (as I mentioned for datetime overlap). However, the current methods are wrapping the most elementary of comparison operators. There is a reasonability argument here; if the method doesn't shorten the code and choosing the correct method requires the same level of knowledge as doing the comparison yourself; there's no convenience from having the method. Comparatively, Datetime overlap comparison is a reasonable convenience, because it's cumbersome to always write the multiple comparison evaluations needed to correctly check for an overlap. \$\endgroup\$ – Flater May 3 '18 at 10:36
  • \$\begingroup\$ For us outsiders/readers, it's always difficult to tell whether something is useful/convenient or not as we might not have the need for it yet but I guess OP might have already be using similar code multiple times so in his projects this is a convenience. Another such example could be my extensions for testing common interfaces. Not much feedback received, probalby because nobody is doing this but I'm using them in many projects; it's relative :-] \$\endgroup\$ – t3chb0t May 3 '18 at 10:49
  • \$\begingroup\$ CountEqual and CountNotEqual don't quite work, at least the way it's posted here, you should run the tests OP has provided. \$\endgroup\$ – Denis May 3 '18 at 10:51
  • \$\begingroup\$ @Flater those 2 tests specifically Console.WriteLine("F? " + things.CountEqual(x => x <= 5, 2));, Console.WriteLine("T? " + things.CountNotEqual(x => x <= 5, 2));. \$\endgroup\$ – Denis May 3 '18 at 11:00
4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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