www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - nWayUnion(tuple)?

reply "bearophile" <bearophileHUGS lycos.com> writes:
Currently std.algorithm.nWayUnion requires an array of ranges, 
because it internally keeps them in a heap, to be fast when you 
give it hundreds+ of ranges.

But in some cases I'd like to merge different types of ranges, 
that I can't put in an array. Is this use case worth supporting 
(usually the number of ranges is small so for such use cases a 
heap is not so needed)?


import std.algorithm: nWayUnion, map;
import std.range: iota;
import std.typecons: tuple;
void main() {
     auto a = iota(10);
     auto b = [3, 6, 9];
     auto c = iota(11).map!q{a * a};
     auto r = nWayUnion(tuple(a, b, c));
}


(Or maybe I am missing something, and this is already possible in 
Phobos. This happened some times in past because it's not easy to 
fully understand the high flexibility of std.algorithm).

Bye,
bearophile
Feb 27 2013
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 02/27/2013 11:36 AM, bearophile wrote:


 But in some cases I'd like to merge different types of ranges, that I
 can't put in an array. Is this use case worth supporting (usually the
 number of ranges is small so for such use cases a heap is not so needed)?


nWayUnion requires a range of ranges. The simplest thing to do for that 
is to pass an array. It is not very pretty, but to match the elements of 
that array, there is inputRangeObject:

import std.algorithm;
import std.range;
import std.stdio;

void main() {
     InputRange!int a = inputRangeObject(iota(10));
     InputRange!int b = inputRangeObject([3, 6, 9]);
     InputRange!int c = inputRangeObject(iota(11).map!q{a * a});
     auto r = nWayUnion([ a, b, c ]);

     writeln(r);
}

The output:

[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 16, 25, 36, 49, 64, 
81, 100]

Phobos could have a function so that the code could be cleaner. A 
function that supports "treat these as InputRanges of ints":

     nWayUnion(inputRanges(a, b, c));

But it is not there. :)

Ali
Feb 27 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Ali Çehreli:


 It is not very pretty, but to match the elements of that array, 
 there is inputRangeObject:


OK.



 Phobos could have a function so that the code could be cleaner. 
 A function that supports "treat these as InputRanges of ints":

     nWayUnion(inputRanges(a, b, c));

 But it is not there. :)


If we add an overload of nWayUnion (better named nWayMerge: 
http://d.puremagic.com/issues/show_bug.cgi?id=6718 ) then there's 
no need to use inputRangeObject...

The question is how much common my use case (mixed type 
iterables) is.

Thank you,
bearophile
Feb 27 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 02/27/2013 03:02 PM, bearophile wrote:


 If we add an overload of nWayUnion (better named nWayMerge:
 http://d.puremagic.com/issues/show_bug.cgi?id=6718 ) then there's no
 need to use inputRangeObject...

 The question is how much common my use case (mixed type iterables) is.


I agree with you. Every range that operates on a range of ranges must 
support different types of ranges. After all, chain does that:

     auto a = iota(10);
     auto b = [3.1, 6.2, 9.3];
     auto c = iota(11).map!q{a * a};
     auto r = chain(a, b, c);

Ali
Feb 27 2013
prev sibling parent reply "Chris Cain" <clcain uncg.edu> writes:
On Wednesday, 27 February 2013 at 19:36:44 UTC, bearophile wrote:

 But in some cases I'd like to merge different types of ranges, 
 that I can't put in an array. Is this use case worth supporting 
 (usually the number of ranges is small so for such use cases a 
 heap is not so needed)?


I'm not sure how common the use case is, but I think it'd be 
fairly easy to support.

Just internally have an array of indices to the tuple and use the 
heap with a less defined like "myTup[a] < myTup[b]" to use the 
indices to look into the tuple to sort the indices appropriately. 
Just add some compile-time checks to make sure all of the 
ElementTypes of the tuple agree and it's essentially the same 
thing as already implemented.

It actually probably wouldn't be a terrible idea to write a 
wrapper range that does this type of process so that it may be 
used with anything and the wrapper range could be a 
RandomAccessRange... this would (probably) make it possible to 
use tuples in a lot of places it isn't exactly allowed right now.
Feb 27 2013
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Wednesday, 27 February 2013 at 23:54:31 UTC, Chris Cain wrote:

 I'm not sure how common the use case is, but I think it'd be 
 fairly easy to support.

 Just internally have an array of indices to the tuple and use 
 the heap with a less defined like "myTup[a] < myTup[b]" to use 
 the indices to look into the tuple to sort the indices 
 appropriately. Just add some compile-time checks to make sure 
 all of the ElementTypes of the tuple agree and it's essentially 
 the same thing as already implemented.

 It actually probably wouldn't be a terrible idea to write a 
 wrapper range that does this type of process so that it may be 
 used with anything and the wrapper range could be a 
 RandomAccessRange... this would (probably) make it possible to 
 use tuples in a lot of places it isn't exactly allowed right 
 now.


I thought about this a bit more and I see that this is simply not 
a solution to the problem at all. I'm playing around with some 
things and if I come up with a solution in code, I'll post it.
Feb 27 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Chris Cain:


 I'm playing around with some things and if I come up
 with a solution in code, I'll post it.


If you have some useful idea then please add it to the ER itself:
http://d.puremagic.com/issues/show_bug.cgi?id=9611

Bye,
bearophile
Feb 27 2013
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Thursday, 28 February 2013 at 00:44:58 UTC, bearophile wrote:

 Chris Cain:


 I'm playing around with some things and if I come up
 with a solution in code, I'll post it.


 If you have some useful idea then please add it to the ER 
 itself:
 http://d.puremagic.com/issues/show_bug.cgi?id=9611

 Bye,
 bearophile


I'll post this to the ER as well, but here you go :)

https://gist.github.com/Zshazz/c4da4c3e0099062ab7e5
Feb 27 2013
parent "Chris Cain" <clcain uncg.edu> writes:
On Thursday, 28 February 2013 at 01:01:16 UTC, Chris Cain wrote:

 I'll post this to the ER as well, but here you go :)

 https://gist.github.com/Zshazz/c4da4c3e0099062ab7e5


And upon reading the ER, I see that this is (essentially) the 
solution it had. *doh* And I thought I was being pretty clever 
with this stuff :-p

But in any case, either a wrapper that does this or the code in 
nWayUnion itself could easily do this.
Feb 27 2013