Short-circuit range counting algorithm?

Nordlöw per.nordlow at gmail.com
Fri Mar 16 19:39:17 UTC 2018


On Friday, 16 March 2018 at 17:41:22 UTC, H. S. Teoh wrote:
> Given a forward range r, I want to test whether it has exactly 
> n elements that satisfy some given predicate pred.  Is it 
> possible to do this using current Phobos algorithms such that 
> it does not traverse more members of the range than necessary?
>
> The naïve solution `r.count!pred == n` walks the entire range, 
> even though it may already have seen n+1 elements that 
> satisfies pred, and therefore should already know that the 
> answer must be false.
>
>
> T

I've implemented these by hand as special cases of count named 
countsExactly, countsAtLeast, countsAtMost beginning at

https://github.com/nordlow/phobos-next/blob/3682da65ecb8497946379b41d8027b8292c635a1/src/algorithm_ex.d#L1941


More information about the Digitalmars-d mailing list