## digitalmars.D - Short-circuit range counting algorithm?

```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

T

--
The early bird gets the worm. Moral: ewww...
```
Mar 16 2018
```On 3/16/18 1:41 PM, 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

r.count!pred.walkLength(n) == n
```
Mar 16 2018
```On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu
wrote:
On 3/16/18 1:41 PM, 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

r.count!pred.walkLength(n) == n

Shouldn't this be using filter (count is eager)?

r.filter!pred.walkLength(n) == n
```
Mar 16 2018
```On 3/16/18 2:07 PM, Seb wrote:
On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:
On 3/16/18 1:41 PM, 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

r.count!pred.walkLength(n) == n

Shouldn't this be using filter (count is eager)?

r.filter!pred.walkLength(n) == n

r.filter!pred.walkLength(n + 1) == n

-Steve
```
Mar 16 2018
```On Fri, Mar 16, 2018 at 02:58:36PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
On 3/16/18 2:07 PM, Seb wrote:
On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:
On 3/16/18 1:41 PM, 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
false.

r.count!pred.walkLength(n) == n

Shouldn't this be using filter (count is eager)?

r.filter!pred.walkLength(n) == n

r.filter!pred.walkLength(n + 1) == n

[...]

Aha, so the trick is the 2-argument overload of walkLength.  That's what
I was looking for.  Thanks!

And yes, it should be .walkLength(n+1) because otherwise you don't know
if the actual count is >n.

T

--
Don't drink and derive. Alcohol and algebra don't mix.
```
Mar 16 2018
```On 03/16/2018 03:10 PM, H. S. Teoh wrote:
On Fri, Mar 16, 2018 at 02:58:36PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
On 3/16/18 2:07 PM, Seb wrote:
On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:
On 3/16/18 1:41 PM, 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
false.

r.count!pred.walkLength(n) == n

Shouldn't this be using filter (count is eager)?

r.filter!pred.walkLength(n) == n

r.filter!pred.walkLength(n + 1) == n

[...]

Aha, so the trick is the 2-argument overload of walkLength.  That's what
I was looking for.  Thanks!

And yes, it should be .walkLength(n+1) because otherwise you don't know
if the actual count is >n.

Noice, thanks for the correx all.
```
Mar 17 2018    =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
```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