Heap: container or range?

[Sergey Gromov]

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)));

OTOH, I'd expect something like the following to also work:

auto f = new File("blah.txt");
auto top = take(10, f.lines);

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.