[OT] n-way union

[bearophile]

Andrei Alexandrescu:

>Needless to say, nWayUnion is a range :o).<

It's better for nWayUnion to be a lazy iterable.
As probably others have already said, you can keep an heap of pointers, and compute the heap invariant using as opCmp a function that uses the values they point to. When nWayUnion yields an item, the relative pointer goes one step forward and the heap invariant has to be restored. When one array finishes, the relative pointer is removed before restoring the heap invariant.

The algorithm can be generalized: the input can be an array (random access range? memory mapped file and arrays are among the most important cases) of sorted iterables (even lazy ones), that is an array of lazy sorted ranges.

The most general input is a lazy range of lazy sorted ranges, in this situation the nWayUnion has to first "duplicate" it into an eager array of such ranges, and then turn it into an heap as before.
I guess in most situations you don't have more than thausands of such sorted iterables, so cerating such temporary array isn't too much bad.
(nWayUnion may also have a small fixed size array of pointers/indexes on the stack, for the simple case of an array of 3-5 arrays).

Bye,
bearophile