Sorry for the amount of text, but I tried to explain everything
in a clear and simple way.
I'm willing to volunteer for adding support for more types in
iota. The relevant discussion is:
https://d.puremagic.com/issues/show_bug.cgi?id=10762
A few preliminary considerations:
- iota() currently returns a Random Access range, and I'm sure
nobody would agree to downgrade the result to a ForwardRange or
an InputRange, because that would break an unknown amount of code.
- I think everyone agrees that even after enhancements, iota()
should always return a RA range, even if we use types that are
currently not supported. It would make little sense returning
different kind of ranges for different input types.
Let's define the types: When calling iota(start,end,inc)
S=typeof(start),
E=typeof(end),
I=typeof(inc),
C=CommonType!(S,E).
My proposal:
iota(start, end, inc) accepts any type, as long as
{C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is
valid code;
Since inc type might not be directly comparable to 0, we also
check if (start + inc < start). If this returns true, this means
that "inc is negative" in a more general sense. We can use this
information to return an empty range when needed, respecting the
behaviour defined by the library reference. eg: (start < end &&
inc < 0) => return empty range.
end is not required to be equal to (start + n*inc) for any given
n; eg: iota(4, 9, 2) should be valid and return [4, 6, 8]. We can
discuss if this makes sense or should be changed, but I think it
would be better this way.
If the code {int n; I n_inc = n * inc;} is valid, this
instruction is used for providing O(1) access for opIndex and
opSlice methods.
If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this
instruction is used for providing O(1) access for popBack()
method.
If no optimization is available, the code will provide O(n)
performance for those methods.
The real issue however is that construction of the range might
end up taking O(n) time, because we have to provide the length
and the back property. One work around is computing those lazily
only if the user requests them.
By doing this, anyone only using iota() for forward iteration
will still obtain O(1) performance.
iota(start, end) accepts any type, as long as
{C c; ++c; c < end;} or {iota(start, end, 1);} is valid code.
If both forms are valid, the iota(start, end, 1) version is
preferred (allowing possible optimizations as discussed before).
Everything else ends up being the same as before: popBack() can
be optimized if {--c;} is valid code, the opIndex, opSlice, back
and length methods will take O(n) time, no way around this sadly.
hsteoh suggested:
If start+inc is *not* supported but start-- is, and end <
start, should we support iota(start,end)?
I think this idea should be discarded since some code could
quickly become a minefield:
type T implements ++t and --t;
type P only implements ++p;
t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
And this behaviour really smells bad, IMHO. The only way to solve
this is requiring opUnary!"--" being implemented for the type to
be used, and I am not sure about this (most iota uses only really
need ++).
Any suggestion/critique? If this looks good to you, I can start
working on it. If you disagree on something (and I know you have
something to say!), discussion is more than welcome!
Francesco
