BinaryHeap is a range so it goes in std.range. Agree?

[Andrei Alexandrescu]

On 06/08/2010 10:04 AM, Steven Schveighoffer wrote:
> On Tue, 08 Jun 2010 10:47:33 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> 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