[Issue 8405] Create overload for joiner which is random access for random access ranges

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=8405

--- Comment #4 from John Colvin <john.loughran.colvin at gmail.com> ---
(In reply to bearophile_hugs from comment #3)
> (In reply to Peter Alexander from comment #1)
> > How do you make opIndex O(1) for a joiner range? Surely you have to count up
> > the lengths of all the sub ranges until you hit the desired index? That's
> > O(n).
> 
> In the common use case I've shown, where you have an array of array, all
> array lengths are known. If joiner caches internally the lengths of all the
> rows, the successive accesses are O(1). This requires some heap memory...

Unless there is an exploitable pattern in the lengths (rectangular being the
easiest case), given a NxM range of ranges, it's still O(N).


Perhaps what we need is a generalisation of length for Ranges of Ranges (of
Ranges ...), called `dimensions` (or `dims`, or `shape`, or whatever seems
best), which, for an >=n-dimensional RoR, provides n lengths, either as a
static array (fixed dimensions) or a dynamic array (runtime number of
dimensions).

Given this information, joiner could easily provide O(1) random-access.

In general, phobos is quite weak for ranges of ranges. A lot more could be done
if we had `dimensions` info available where appropriate.

--