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