https://issues.dlang.org/show_bug.cgi?id=8405
--- Comment #4 from John Colvin <[email protected]> --- (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. --
