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
