Arrays - Inserting and moving data

[Ali Çehreli]

On 02/09/2012 11:03 AM, H. S. Teoh wrote:
 > On Thu, Feb 09, 2012 at 10:30:22AM -0800, Ali Çehreli wrote:
 > [...]
 >> But if you don't actually want to modify the data, you can merely
 >> access the elements in-place by std.range.chain:
 >>
 >> import std.stdio;
 >> import std.range;
 >>
 >> void main()
 >> {
 >>      int[] arr = [0,1,2,3,4,5,6,7,8,9];
 >>      immutable position = arr.length / 2;
 >>      immutable newValue = 42;
 >>
 >>      auto r = chain(arr[0 .. position], [ newValue ], arr[position +
 >> 1 .. $]);
 >>      writeln(r);
 >> }
 >>
 >> 'r' above is a lazy range that just provides access to the three
 >> ranges given to it. 'arr' does not change in any way.
 > [...]
 >
 > Wow! This is really cool. So you *can* have O(1) insertions in the
 > middle of an array after all. :)
 >
 > Of course, you probably want to flatten it once in a while to keep
 > random access cost from skyrocketing.

O(1) would be violated only if there are too many actual ranges.

 > (I'm assuming delegates or
 > something equivalent are involved in generating the lazy range?)

Simpler than that. :) The trick is that chain() returns a range object 
that operates lazily. I have used chain() as an example for finite 
RandomAccessRange types (I used the name 'Together' instead of Chain). 
Search for "Finite RandomAccessRange" here:

   http://ddili.org/ders/d.en/ranges.html

And yes, I note there that the implementation is not O(1). Also look 
under the title "Laziness" in that chapter.

Ali