www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Chaining a dynamic number of Ranges

reply "Enerqi" <kelvin.d.ward googlemail.com> writes:
Hello

I'm playing around with my first D program and can't figure out a 
way to chain a dynamic number of ranges. In this example I'm 
trying to chain a two dimensional array into effectively a one 
dimensional array, so I can later sort it as one sequence.


--------
import std.algorithm;
import std.range;

// n is determined at runtime
uint[][] arrays = new uint[][n];
foreach(ref a; arrays)
{
     a = new uint[10];
     copy(iota(10), a);
}

auto c = chain(arrays[0], arrays[1]);
foreach(a; arr[2..$])
{
     c = chain(c, a);
}
--------

Gives a compile error:
Error: cannot implicitly convert expression (chain(c,a)) of type 
Result to Result

any ideas?

Thanks.
Jul 21 2012
parent reply "Nathan M. Swan" <nathanmswan gmail.com> writes:
On Saturday, 21 July 2012 at 16:42:50 UTC, Enerqi wrote:

 Hello

 I'm playing around with my first D program and can't figure out 
 a way to chain a dynamic number of ranges. In this example I'm 
 trying to chain a two dimensional array into effectively a one 
 dimensional array, so I can later sort it as one sequence.


 --------
 import std.algorithm;
 import std.range;

 // n is determined at runtime
 uint[][] arrays = new uint[][n];
 foreach(ref a; arrays)
 {
     a = new uint[10];
     copy(iota(10), a);
 }

 auto c = chain(arrays[0], arrays[1]);
 foreach(a; arr[2..$])
 {
     c = chain(c, a);
 }
 --------

 Gives a compile error:
 Error: cannot implicitly convert expression (chain(c,a)) of 
 type Result to Result

 any ideas?

 Thanks.


The problem is that the first auto c is a chaining of an array 
and array, and chain(c, a) is a chaining of a chain of arrays and 
an array.

The way to do this is std.algorithm.joiner:

auto c = joiner(arrays, []);

Forgive me if I'm wrong (untested),

NMS
Jul 21 2012
parent reply "Enerqi" <kelvin.d.ward googlemail.com> writes:
Thanks! That does join up the arrays as I'd like.
An issue remaining is that, unlike with the chain function, I 
can't sort the output of the joiner function.

Error: template instance std.algorithm.sort!("a <
b",cast(SwapStrategy)0,Result) error instantiating

Seems the return type of joiner doesn't implement random access 
in the same way the return type of chain does.
Chain's documentation says "If all input ranges offer random 
access and $(D
length), $(D Chain) offers them as well."

I wonder if joiner is sortable somehow?


On Saturday, 21 July 2012 at 17:00:02 UTC, Nathan M. Swan wrote:

 On Saturday, 21 July 2012 at 16:42:50 UTC, Enerqi wrote:

 Hello

 I'm playing around with my first D program and can't figure 
 out a way to chain a dynamic number of ranges. In this example 
 I'm trying to chain a two dimensional array into effectively a 
 one dimensional array, so I can later sort it as one sequence.


 --------
 import std.algorithm;
 import std.range;

 // n is determined at runtime
 uint[][] arrays = new uint[][n];
 foreach(ref a; arrays)
 {
    a = new uint[10];
    copy(iota(10), a);
 }

 auto c = chain(arrays[0], arrays[1]);
 foreach(a; arr[2..$])
 {
    c = chain(c, a);
 }
 --------

 Gives a compile error:
 Error: cannot implicitly convert expression (chain(c,a)) of 
 type Result to Result

 any ideas?

 Thanks.


 The problem is that the first auto c is a chaining of an array 
 and array, and chain(c, a) is a chaining of a chain of arrays 
 and an array.

 The way to do this is std.algorithm.joiner:

 auto c = joiner(arrays, []);

 Forgive me if I'm wrong (untested),

 NMS
Jul 21 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, July 21, 2012 21:47:19 Enerqi wrote:

 Thanks! That does join up the arrays as I'd like.
 An issue remaining is that, unlike with the chain function, I
 can't sort the output of the joiner function.
 
 Error: template instance std.algorithm.sort!("a <
 b",cast(SwapStrategy)0,Result) error instantiating
 
 Seems the return type of joiner doesn't implement random access
 in the same way the return type of chain does.
 Chain's documentation says "If all input ranges offer random
 access and $(D
 length), $(D Chain) offers them as well."
 
 I wonder if joiner is sortable somehow?


For sort to work, it needs a random access range. Operating on anything else 
would be horribly inefficient. With the overload of joiner which doesn't take a 
seperator, it might be possible to make joiner return a random access range if 
all of the ranges passed to it were random access and had length, but it's not 
implemented that way right now, and certainly if any of the ranges passed in 
weren't random access, then that wouldn't work regardless. And it would never 
work with the separator, since the separator would be in the range multiple 
times, and sorting it could really mess it up.

The solution is to create an array and sort that. You can either use 
std.array.array on the result of joiner, or - since I believe that you're 
operating on arrays specifically - you can use std.array.join which will just 
create an array immediately rather than generating a lazy range.

- Jonathan M Daves
Jul 21 2012
parent reply "Enerqi" <kelvin.d.ward googlemail.com> writes:
Ok thanks! I was hoping to avoid making a copy of the arrays, 
which I think std.array.join does, when treating them as a single 
array range. Wishful thinking perhaps :)

On Saturday, 21 July 2012 at 20:18:25 UTC, Jonathan M Davis wrote:

 On Saturday, July 21, 2012 21:47:19 Enerqi wrote:

 Thanks! That does join up the arrays as I'd like.
 An issue remaining is that, unlike with the chain function, I
 can't sort the output of the joiner function.
 
 Error: template instance std.algorithm.sort!("a <
 b",cast(SwapStrategy)0,Result) error instantiating
 
 Seems the return type of joiner doesn't implement random access
 in the same way the return type of chain does.
 Chain's documentation says "If all input ranges offer random
 access and $(D
 length), $(D Chain) offers them as well."
 
 I wonder if joiner is sortable somehow?


 For sort to work, it needs a random access range. Operating on 
 anything else
 would be horribly inefficient. With the overload of joiner 
 which doesn't take a
 seperator, it might be possible to make joiner return a random 
 access range if
 all of the ranges passed to it were random access and had 
 length, but it's not
 implemented that way right now, and certainly if any of the 
 ranges passed in
 weren't random access, then that wouldn't work regardless. And 
 it would never
 work with the separator, since the separator would be in the 
 range multiple
 times, and sorting it could really mess it up.

 The solution is to create an array and sort that. You can 
 either use
 std.array.array on the result of joiner, or - since I believe 
 that you're
 operating on arrays specifically - you can use std.array.join 
 which will just
 create an array immediately rather than generating a lazy range.

 - Jonathan M Daves
Jul 21 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, July 22, 2012 02:34:47 Enerqi wrote:

 Ok thanks! I was hoping to avoid making a copy of the arrays,
 which I think std.array.join does, when treating them as a single
 array range. Wishful thinking perhaps :)


It works as long as you don't need capabilities that the new range doesn't 
have. For instance, iterating over it works just fine without creating a new 
array. But it's not uncommon that if you want a random-access range, you need 
to allocate a new array (or some other type of container) to get it rather 
than using the wrapper range that you got back from a range-based function.

- Jonathan M Davis
Jul 21 2012
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, July 21, 2012 13:18:15 Jonathan M Davis wrote:

 And it would never work with the separator, since the separator
 would be in the range multiple times, and sorting it could really mess it


Actually, I take that back. Since the separator is a forward range, it could 
probably be done. It's just messier, because you'd have to create several 
copies of it, whereas right now, it just has two copies: the one that it's 
currently iterating over (if it's currently in the seprataor) and the original 
that it uses to get the new one to iterate over (via save) when it needs it 
later.

- Jonathan M Davis
Jul 21 2012