• bearophile <bearophileHUGS lycos.com> May 25 2009
• Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> May 25 2009

bearophile <bearophileHUGS lycos.com> writes:

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

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

bearophile wrote:
 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).


The policy of std.algorithm is to not surreptitiously allocate memory if 
it can help it. So the user is left responsible with creating a range of 
ranges with random access.

Andrei