Combining infinite ranges

[Simen kjaeraas]

Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:

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

With the algorithm (attempted) explained above, it's actually 2^128, which
is acceptably high, I think.

> 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).

Should be O(1). Each pop in the described algorithm is a call to popFront:

void popFront( ) {
     ranges[active].popFront;
     position[active]++;
     if (position[active] > position[inactive]) {
         active = !active;
         position[active] = 0;
         ranges[active] = savedRange[active];
     }
}

-- 
Simen