std.range.iota enhancement: supporting more types (AKA issue 10762)

Francesco Cattoglio francesco.cattoglio at gmail.com
Mon Dec 23 07:00:25 PST 2013


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


More information about the Digitalmars-d mailing list