Is there a dynamic chain primitive, so that you can add to the chain at runtime?

Context: the following example on the front page is interesting.

void main()
{
    int[] arr1 = [4, 9, 7];
    int[] arr2 = [5, 2, 1, 10];
    int[] arr3 = [6, 8, 3];
    sort(chain(arr1, arr2, arr3));
    writefln("%s\n%s\n%s\n", arr1, arr2, arr3);
}

But it would be much more useful in practice if "chain" was a dynamic array.

On Monday, 13 June 2022 at 08:51:03 UTC, Ola Fosheim Grøstad wrote:

Already so:

int[] arr = [4, 9, 7, 5, 2, 1, 10, 6, 8, 3];

int[] arr1 = arr[0..3];
int[] arr2 = arr[3..7];
int[] arr3 = arr[7..$];

sort(chain(arr1, arr2, arr3));
writefln("%s\n%s\n%s\n", arr1, arr2, arr3);
typeid(arr).writeln(": ", arr);
writeln(&arr[0], " == ", &arr1[0]);

/* Print Out:
[1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10]

int[]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7F7FBE348000 == 7F7FBE348000
*/

On Monday, 13 June 2022 at 09:08:40 UTC, Salih Dincer wrote:

I meant something like: chain = [arr1, arr2, …, arrN]

I don't use ranges, but I thought this specific use case could be valuable.

Imagine you have a chunked datastructure of unknown lengths, and you want to "redistribute" items without reallocation.

On 6/13/22 4:51 AM, Ola Fosheim Grøstad wrote:

void main()
{
     int[] arr1 = [4, 9, 7];
     int[] arr2 = [5, 2, 1, 10];
     int[] arr3 = [6, 8, 3];
     sort(chain(arr1, arr2, arr3));
     writefln("%s\n%s\n%s\n", arr1, arr2, arr3);
}

chain allows ranges of different types.
joiner should be the equivalent for a dynamic range of ranges of the same type.

I would think sort(joiner([arr1, arr2, arr3])) should work, but it's not a random access range. Most likely because the big-O constants are no longer constant.

-Steve

On Monday, 13 June 2022 at 13:22:52 UTC, Steven Schveighoffer wrote:

Yes, I got the error «must satisfy the following constraint: isRandomAccessRange!Range`».

It would be relatively easy to make it work as a random access range if arr1, arr2, etc were fixed size slices.

Or I guess, use insertion-sort followed by merge-sort.

On 6/13/22 9:44 AM, Ola Fosheim Grøstad wrote:

Merge sort only works if it's easy to manipulate the structure, like a linked-list, or to build a new structure, like if you don't care about allocating a new array every iteration.

-Steve

On Monday, 13 June 2022 at 14:03:13 UTC, Steven Schveighoffer wrote:

The easiest option is to have two buffers that can hold all items, in the last merge you merge back to the input-storage. But yeah, it is only «fast» for very large arrays.