Heap: container or range?

[Andrei Alexandrescu]

Sergey Gromov wrote:
> Thu, 29 Jan 2009 21:26:39 -0800, Andrei Alexandrescu wrote:
> 
>> Sean Kelly wrote:
>>> Sean Kelly wrote:
>>>> Andrei Alexandrescu wrote:
>>>>> Ah, never mind all that. I realized that I can't have a heap range. 
>>>>> This is because heaps must mutate the underlying range in-place and 
>>>>> any copy will mess the heap up. Here's the example that clarify it 
>>>>> for me:
>>>>>
>>>>>         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
>>>>>         auto h = Heap!(int[])(a);
>>>>>         assert(equal(take(5, h) == [ 8, 9, 10, 14, 16 ]);
>>>>>
>>>>> At this point the mutations done by take messed up h already!!
>>>> Hm... so assuming this is a min heap, I have:
>>>>
>>>> a = [4,1,3,2,16,9,10,14,8,7];
>>>> h = [1,2,3,4,7,9,10,14,8,16];
>>>> take(5, h);
>>>> h = [8,10,9,16,14];
>>>>
>>>> Shouldn't take call next repeatedly on the heap, which will in turn 
>>>> perform a popHeap operation?  It's difficult to be sure what the 
>>>> result will be after take(5,h) occurs, but it should still be a valid 
>>>> heap, correct?
>>> Oh, I would also expect:
>>>
>>> a = [8,10,9,16,14, garbage];
>>>
>>> Since it isn't aware of the length adjustment.  Perhaps this is what you 
>>> meant?
>>>
>>> Sean
>> Yah, that's what I meant. h still thinks its length is 10 and that those 
>> 10 elements respect the heap property.
> 
> Actually, if ranges are by value, I'd expect
> 
> assert(equal(take(5, h) == take(5, h)));

Me too. It does work indeed BUT NOT FOR INPUT RANGES. So in short you 
are showing yet another reason why heaps can't be good ranges.

> OTOH, I'd expect something like the following to also work:
> 
> auto f = new File("blah.txt");
> auto top = take(10, f.lines);

That also works (just that in the new std.stdio File is a struct, so 
it's not dynamically allocated). However, f.lines is understandably an 
input range so this will NOT work:

auto f = new File("blah.txt");
assert(equal(take(5, f.lines) == take(5, f.lines)));

The two f.lines instances operate on the same underlying file handle, so 
they are input ranges: advancing one advances all others.

> I.e. I'd expect some ranges to be Translators, and others to be
> Mutators.  Translators are read-only views into underlying anything
> which may involve some expensive bookkeeping.  Mutators are basically
> references into a particular container and make sure that the container
> and other Mutators stay consistent.

I think the distinction is input vs. forward and mutable vs. immutable 
ranges (the latter distinction is not checked in yet).

Andrei