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.
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.
Andrei
