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
