Thread overview | ||||||||
---|---|---|---|---|---|---|---|---|
|
May 23, 2020 How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
I have tried to implement a simple flatten function for multidimensional arrays with recursive templates but got stuck. Then I googled a little and stumped into complex https://rosettacode.org/wiki/Flatten_a_list#D implementation which requires your arrays to be either TreeList or Algebraic. That is, it does not work out-of-the-box on something like int[][][]. I'd like to clarify a couple of questions first. How come Phobos doesn't have "flatten" function for arrays? Is there an implementation of flatten that works out-of-the-box on N-dim arrays outside of Phobos? Excluding "flattened" from mir.ndslice since it works on Slices. |
May 23, 2020 Re: How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Pavel Shkadzko | On 5/23/20 11:15 AM, Pavel Shkadzko wrote:> I have tried to implement a simple flatten function for multidimensional > I'd like to clarify a couple of questions first. > > How come Phobos doesn't have "flatten" function for arrays? We call in 'joiner'. I wrote something like this: import std.stdio; import std.algorithm; import std.range; int value = 0; auto makeNdim(size_t N)(size_t length) if (N == 1) { auto result = iota(value, value + length).array; value += length; return result; } auto makeNdim(size_t N)(size_t length) if (N > 1) { return iota(N).map!(n => makeNdim!(N - 1)(length)).array; } auto flatten(R)(R range) if (!isInputRange!(ElementType!R)) { return range.joiner; } auto flatten(R)(R range) if (isInputRange!(ElementType!R)) { return range.map!(r => r.joiner).joiner; } void main() { auto a = makeNdim!3(5); writefln!"Original : %s"(a); writefln!"Flattened: %s"(a.flatten); } Output: Original : [[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]], [[10, 11, 12, 13, 14], [15, 16, 17, 18, 19]], [[20, 21, 22, 23, 24], [25, 26, 27, 28, 29]]] Flattened: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29] Ali |
May 24, 2020 Re: How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | On Saturday, 23 May 2020 at 19:59:30 UTC, Ali Çehreli wrote:
> On 5/23/20 11:15 AM, Pavel Shkadzko wrote:> I have tried to implement a simple flatten function for multidimensional
>
> [...]
Thank you, I was lacking practical examples for templates with "if" constructs, ehh.
|
May 24, 2020 Re: How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Pavel Shkadzko | On Saturday, 23 May 2020 at 18:15:32 UTC, Pavel Shkadzko wrote:
> I have tried to implement a simple flatten function for multidimensional arrays with recursive templates but got stuck. Then I googled a little and stumped into complex https://rosettacode.org/wiki/Flatten_a_list#D implementation which requires your arrays to be either TreeList or Algebraic. That is, it does not work out-of-the-box on something like int[][][].
>
> I'd like to clarify a couple of questions first.
>
> How come Phobos doesn't have "flatten" function for arrays?
>
> Is there an implementation of flatten that works out-of-the-box on N-dim arrays outside of Phobos? Excluding "flattened" from mir.ndslice since it works on Slices.
If the common nd-array isn't jugged (a parallelotop), you can use fuse function.
----------
/+dub.sdl:
dependency "mir-algorithm" version="~>3.8.12"
+/
import std.stdio: writeln;
import mir.ndslice;
void main() {
auto arr =
[[[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9]],
[[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19]],
[[20, 21, 22, 23, 24],
[25, 26, 27, 28, 29]]];
auto flatten = arr.fuse.field;
static assert(is(typeof(flatten) == int[]));
assert(flatten == 30.iota);
}
----------
It performs exactly one allocation.
|
May 24, 2020 Re: How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to 9il | On Sunday, 24 May 2020 at 11:21:00 UTC, 9il wrote:
> On Saturday, 23 May 2020 at 18:15:32 UTC, Pavel Shkadzko wrote:
>> [...]
>
> If the common nd-array isn't jugged (a parallelotop), you can use fuse function.
>
> ----------
> /+dub.sdl:
> dependency "mir-algorithm" version="~>3.8.12"
> +/
> import std.stdio: writeln;
> import mir.ndslice;
>
> void main() {
> auto arr =
> [[[0, 1, 2, 3, 4],
> [5, 6, 7, 8, 9]],
> [[10, 11, 12, 13, 14],
> [15, 16, 17, 18, 19]],
> [[20, 21, 22, 23, 24],
> [25, 26, 27, 28, 29]]];
> auto flatten = arr.fuse.field;
>
> static assert(is(typeof(flatten) == int[]));
> assert(flatten == 30.iota);
> }
> ----------
>
> It performs exactly one allocation.
Yep, I know about Mir fuse. I was more wondering about the absence of flatten in Phobos. But on dlang forum some people claimed that when it comes to anything multidimensional, use Mir.
|
May 24, 2020 Re: How to flatten N-dimensional array? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Pavel Shkadzko | On 5/24/20 2:37 AM, Pavel Shkadzko wrote:
> On Saturday, 23 May 2020 at 19:59:30 UTC, Ali Çehreli wrote:
>> On 5/23/20 11:15 AM, Pavel Shkadzko wrote:> I have tried to implement a simple flatten function for multidimensional
>>
>> [...]
>
> Thank you, I was lacking practical examples for templates with "if" constructs, ehh.
Template constraints are great but 'static if' can be more useful as it allows custom error messages:
auto makeNdim(size_t N)(size_t length) {
static if (N == 1) {
auto result = iota(value, value + length).array;
value += length;
return result;
} else static if (N > 1) {
return iota(N).map!(n => makeNdim!(N - 1)(length)).array;
} else {
static assert(false, "N cannot be 0.");
}
}
Ali
|
Copyright © 1999-2021 by the D Language Foundation