On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <[email protected]> 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
