Slicing and Dicing Arrays in D

I was reading this article and thought these would be good to cover in D. However I will cover them in the opposite order.

Splice! Slice! Shoot, I meant Shift!

Laurie ・ Jul 30 '19

#webdev #javascript #learning #productivity

Split

splitter split

There are a number of variation of this, many of which I will use in the other examples.

import std.algorithm;

auto data = "one str\ntwo";
assert(data.splitter(" ").equal(
    ["one", "str\ntwo"]));

import std.array;

assert(data.split().equal(["one", "str", "two"]));

The first is a lazy operation with no memory allocation, the second eagerly evaluates into a new dynamic array. The second, when passing no arguments will also split on all whitespace including new lines.

Shift

dropOne

The objective here is to remove the first element of an array.

import std.range;

auto data = ["one", "two"];
auto head = data.front;
data.popFront();

There is no single call to give the front and move the range.

import std.range;

auto data = ["one", "two"];
auto tail = data.dropOne;

However, this function will remove the next element and return remaining range.

For those functional programmers you'd know these as head and tail.

Splice

Beginning and End of Array

slice findSplitBefore find

The first of the objectives is to obtain the first part and remaining part of an array. In D this is done by what is called array slicing.

auto content = ["post" , "tweet", "video", "talk"];
auto begin = content[0..2];
auto end = content[2..$];
// content is ["post" , "tweet", "video", "talk"];
// begin is ['post', 'tweet']
// end is ['video', 'talk']

The right index is exclusive and does not include that indexes content. These made no modifications to the original array and no allocation was performed. This does mean modifying the slice will modify the original.

import std.algorithm;
auto content = ["post" , "tweet", "video", "talk"];
auto end = content[2..$];
end.sort;
assert(content.equal(["post" , "tweet", "talk", "video"]));

However there is more than one way to splice a cat, and this can be done off the content.

import std.algorithm;
auto content = ["post" , "tweet", "video", "talk"];
auto splice = content.findSplitBefore(["video"]);
splice[1].sort;
assert(content.equal(["post" , "tweet", "talk", "video"]));

Or maybe you only need the first part. Or just the last part.

import std.algorithm;
auto content = ["post" , "tweet", "video", "talk"];
auto end = content.find("video");
auto begin = content.until("video");
assert(begin.equal(["post" , "tweet"]) );
assert(end.equal(["video", "talk"]));

Remove the Middle of Array

remove slice chain

In the two argument JS splice, the objective is removing a sequence of indices, basically keeping both ends.

import std.algorithm;
import std.typecons : tuple;
auto content = ["post" , "tweet", "video", "talk"];
content = content.remove(tuple(1,3));
assert(content.equal(["post" , "talk"]) );

The reassignment of content is necessary because while the the original array is modified it is not sized correctly. Let's take another look.

import std.algorithm;
import std.range : chain;
auto content = ["post" , "tweet", "video", "talk"];
auto outer = content[0..1].chain(content[3..$]);
assert(outer.equal(["post" , "talk"]) );

Here the original is not modified and no new memory is allocated. I'm not able to assign back to content because outer is not an array but a range which is a concept and not a concrete type. Everything we've been doing with std.algorithm has been operating on this concept which arrays take part in.

Using .array() will eagerly evaluate a range and allocate a new array. This can be very common after doing operation on a range and then wanting to sort on something. Not that it is strictly necessary just because you're working with a range. In an example for chain

import std.algorithm.comparison : equal;
import std.algorithm.sorting : sort;

int[] arr1 = [5, 2, 8];
int[] arr2 = [3, 7, 9];
int[] arr3 = [1, 4, 6];

// in-place sorting across all of the arrays
auto s = arr1.chain(arr2, arr3).sort;

assert(s.equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
assert(arr1.equal([1, 2, 3]));
assert(arr2.equal([4, 5, 6]));
assert(arr3.equal([7, 8, 9]));

We see no allocation with the original arrays modified. But I digress.

Removing From and Adding to

insertInPlace

The 3 argument JS splice is probably where the name comes from. The idea is to replace one sequence with another. I can't say I've ever used these semantics.

In D we already cover removing the elements. What is left is putting some stuff in the middle.

import std.algorithm;
import std.array;
auto content = ["post", "talk"];
content.insertInPlace(1, ["dev", "ten mile"]);
assert(content.equal(["post", "dev", "ten mile", "talk"]));

This could be done utilizing slices and chaining. I'll leave that as an excersise for the reader. The benefit would be no modification to the original range and no allocations (the in place operation may allocate if additional memory is needed.