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

[Steven Schveighoffer]

On Tue, 08 Jun 2010 11:12:01 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

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

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