Combining infinite ranges

[Andrei Alexandrescu]

On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>>> All forward ranges should be doable, too.
>>
>> How would the spanning strategy work for two forward infinite ranges?
>
> In a complex, horrible way?
>
> 0. Save initial states (position = 0)
> 1. Pop first until past the position of the other
> 2. Restore other
> 3. Pop other until past the position of the first
> 4. Restore first
> 6. Goto 1.
>
> Screw that, as you cannot save positions. Well, I guess a long should
> be enough for most, but it might not be. As long as there is no way
> to compare positions, 'tis unpossible.
>
> If we accept saving the position (the number of pops), this approach
> should be applicable to any number of ranges.

It's ok to store positions in ulong objects. Most uses of infinite range 
combinations use only the first few elements; the computation will 
anyway take a very, very long time when any of the ranges overflows a ulong.

That being said, I didn't understand the algorithm. What is its 
complexity? From what I understand there's a lot of looping going on. We 
need something that makes progress in O(1).


Andrei