D-Programming-Language/phobos — pull request #880 by monarchdodra (2012-10-17 13:55:43+00:00)
Title: Update walkLength doc and impl; support for inf.

First, this updates the documentation, outlining that just like any algorithm, you should SAVE before calling walkLength.

Adds support for infinite ranges.

Having two different implementations means we avoid the runtime check of `if (upTo == size_t.max)`.

It also means we can turn down `walkLength(infiniteRange)`, which would make no sense, but still accept `walkLength(infiniteRange, size_t.max)`, which makes sense.

Also contains new unittests.

BEFORE
```D
/**
This is a best-effort implementation of $(D length) for any kind of
range.

If $(D hasLength!(Range)), simply returns $(D range.length) without
checking $(D upTo).

Otherwise, walks the range through its length and returns the number
of elements seen. Performes $(BIGOH n) evaluations of $(D range.empty)
and $(D range.popFront()), where $(D n) is the effective length of $(D
range). The $(D upTo) parameter is useful to "cut the losses" in case
the interest is in seeing whether the range has at least some number
of elements. If the parameter $(D upTo) is specified, stops if $(D
upTo) steps have been taken and returns $(D upTo).
*/
auto walkLength(Range)(Range range, const size_t upTo = size_t.max)
if (isInputRange!Range)
{
static if (hasLength!Range)
{
return range.length;
}
else
{
size_t result;
// Optimize this tight loop by specializing for the common
// case upTo == default parameter
if (upTo == size_t.max)
for (; !range.empty; range.popFront()) ++result;
else
for (; result < upTo && !range.empty; range.popFront()) ++result;
return result;
}
}

```

AFTER
```D
/**
This is a best-effort implementation of $(D length) for any kind of
range.

If $(D hasLength!Range), simply returns $(D range.length) without
checking $(D upTo) (if specified).

Otherwise, walks the range through its length and returns the number
of elements seen. Performes $(BIGOH n) evaluations of $(D range.empty)
and $(D range.popFront()), where $(D n) is the effective length of $(D
range). Note that this may consume the range, so a saved range must be
passed if the range is meant to be re-used.

The $(D upTo) parameter is useful to "cut the losses" in case
the interest is in seeing whether the range has at least some number
of elements. If the parameter $(D upTo) is specified, stops if $(D
upTo) steps have been taken and returns $(D upTo).

Infinite ranges are compatible, provided the parameter $(D upTo) is
specified, in which case the implementation simply returns upTo.
*/
auto walkLength(Range)(Range range)
if (isInputRange!Range && !isInfinite!Range)
{
static if (hasLength!Range)
return range.length;
else
{
size_t result;
for ( ; !range.empty ; range.popFront() )
++result;
return result;
}
}
/// ditto
auto walkLength(Range)(Range range, const size_t upTo)
if (isInputRange!Range)
{
static if (hasLength!Range)
return range.length;
else static if (isInfinite!Range)
return upTo;
else
{
size_t result;
for ( ; result < upTo && !range.empty ; range.popFront() )
++result;
return result;
}
}
```

UNITTEST
```D
unittest
{
//Random Access Range
int[] a = [ 1, 2, 3 ];
assert(walkLength(a) == 3);
assert(walkLength(a, 0) == 3);

//Forward Range
auto b = SList!int([1, 2, 3, 4]);
assert(b[].walkLength() == 4);
assert(b[].walkLength(2) == 2);

//Infinite Range
auto fibs = recurrence!"a[n-1] + a[n-2]"(1, 1);
assert(!__traits(compiles, fibs.walkLength()));
assert(fibs.take(10).walkLength() == 10);
assert(fibs.walkLength(55) == 55);
}
```