On Tue, 08 Jun 2010 11:12:01 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 06/08/2010 10:04 AM, Steven Schveighoffer wrote:
On Tue, 08 Jun 2010 10:47:33 -0400, Andrei Alexandrescu
<[email protected]> wrote:
I finalized BinaryHeap. It's pretty cool - it builds a forward range
on top of a random-access range - typically T[] - or a random-access
container - typically Array!T.
The difference is simple - if you build on top of a range the heap
can't grow beyond the size of that range. Building on top of a
container makes the heap growable.
Making BinaryHeap a range is actually pretty cool - just walking the
heap is tantamount to lazily sorting the container. (Of course
BinaryHeap has primitives in addition to the four range primitives.)
Do you agree with putting BinaryHeap in std.range (as opposed to
std.container)?
If BinaryHeap can be added to, how is it a range?
It is a forward range and also an output range by supporting put().
I would suspect that
BinaryHeap can be in std.range, but a BinaryHeap that takes a container
as an input is definitely not a range IMO.
Well it still is. I mean isForwardRange!(BinaryHeap!(Array!int)) is true.
Generally, a range with benefits (i.e. extra functions) is still a range
if it implements the required range primitives with the required
semantics.
Functionally yes, something that supports all the range functions can be
considered a range, but semantically, to me anyways, I always consider a
range to be a something that is a view into a container. Something that
destroys the container as it iterates, or can affect the topology of the
original container seems like it is a different animal. You could have
called std.container's removeFront popFront, and then containers could be
"ranges" too. Very slow and bizarre ranges :)
This is part of the reason why I have trouble accepting I/O ranges -- they
just behave so much differently than other ranges it seems like they
should have their own interface.
Have you ever seen that movie Wall-E? There's a scene where he finds a
spork, and in trying to place it, he gets to his bin of forks and spoons,
with a cup for each type. After going back and forth between spoons and
forks, he just places it on the shelf between the two cups. Maybe
BinaryHeap is a crange :)
You might say the same about
an array, but an array is special in that if I append to one array, it
does not affect the other.
I don't know where it belongs. To me, a range is a type that in itself
cannot affect the topology of the data structure. It's like a window
into the data structure that provides a common interface. A container is
the owner of the data structure, and can provide ranges over its data.
This may be an inadequate view, but its worked for me so far.
Actually if a heap is built on top of a container, it can affect its
topology because it has the sensible primitive of adding to the heap.
Yes, that is my point of why at least growable heaps should not be
considered ranges.
-Steve
