[Challenge] implementing the ambiguous operator in D

[Simen kjaeraas]

Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
> I convinced myself crossProduct is impossible to implement if one input  
> range and one infinite forward range are simultaneously present. It  
> works with any number of infinite forward ranges, and also with other  
> combinations. I couldn't formalize the exact requirements yet.

This is indeed correct. Now, I have found a working algorithm (it works
on paper, I swear!), but I can't seem to get it to work in code.

Special cases come for input ranges - I will not consider those. All
forward ranges can be treated the same, regardless of infiniteness.

We need to keep track of the active ranges, and the initial versions of
those (i.e. those passed to the constructor). In addition, we need to
keep the position of each range, probably as a ulong (2 ranges should
give 2^128 combinations, which will not cover the whole solution space
for infinite ranges, but will still be enough for practical purposes).
Also, we must maintain a stack of locked ranges.

The solution is recursive to the number of ranges, and is given in
pseudocode below. Critique is very, VERY welcome!

bool movedEnough( lastUnlocked, lockedStack.peek ) {
     if ( lastUnlocked.empty ) {
         // If range is empty, don't pop stuff off of it.

         return true;
     } else if ( lastUnlocked > lockedStack.peek ) {
         // If the last unlocked range has a higher index than
         // the next one the locked stack, check if popping
         // would bring us past its position.

         return pos[lastUnlocked] >= pos[lockedStack.peek];
     } else {
         // If the last unlocked range has a lower index than
         // the next one the locked stack, check if popping
         // would bring us to its position.

         return pos[lastUnlocked] >= pos[lockedStack.peek] -1;
     }
}

void popFront( ) {
     if ( !unlockedRanges.empty ) {
         // If there are unlocked ranges, use the first of them
         currentRange = unlockedRanges[0];
     } else {
         // No unlocked ranges, so unlock one.
         currentRange = lastUnlocked = lockedStack.pop;
         unlock( lastUnlocked );

         while ( movedEnough( lastUnlocked, lockedStack.peek ) ) {
             // We have moved far enough along this range, move the next  
one up.

             currentRange = lastUnlocked = lockedStack.pop;
             unlock( lastUnlocked );

             if ( // If there are more unlocked ranges below this one
                 ( lastUnlocked != unlockedRanges[$] ) ||
                 // Or there are no more locked ranges
                 ( lockedStack.empty ) ) {

                 // Move to the next range. Note that firstAfter would need  
to return 0 on being passed $.
                 currentRange = unlockedRanges.firstAfter( lastUnlocked );

                 // We have found the next range from which to pop.
                 break;
             }
         }
     }

     // Pop off the found range, the lock it, and reset all unlocked ranges  
to their saved states.
     currentRange.popFront();
     lock(currentRange);
     foreach ( unlockedRanges ) {
         reset();
     }
}

Given cartesian( [1,2], "ab" ), the result should be as follows:

tuple( 1, 'a' );
tuple( 2, 'a' );
tuple( 2, 'b' );
tuple( 1, 'b' );

And for cartesian( [1,2,3], "abc" ):

tuple( 1, 'a' );
tuple( 2, 'a' );
tuple( 2, 'b' );
tuple( 1, 'b' );
tuple( 3, 'a' );
tuple( 3, 'b' );
tuple( 3, 'c' );
tuple( 1, 'c' );
tuple( 2, 'c' );


-- 
Simen